Inteligencia Artificial en Oz

En el tercer libro de Oz ("Ozma of Oz"), L. Frank Baum juega (tal vez sin querer) con algunos de los problemas de la Inteligencia Artificial. Obviamente, este no es el tema principal del libro, pero uno de los personajes principales es Tiktok, una máquina capaz de pensar, hablar y caminar; y las situaciones que se viven a su alrededor dan lugar a pensar en la IA.

Una de las primeras escenas que me llamó la atención al respecto es cómo Tiktok, a pesar de que puede hacer todo lo que los otros hacen (y tener muy buenas ideas cuando piensa) resulta "inferior" a los otros, porque no está "vivo" (esto es en particular interesante porque el no temer morir le resulta una ventaja en ocasiones):

"That's all right," replied the Scarecrow. "Dorothy will soon be free, and then she'll attend to your works. But it must be a great misfortune not to be alive. I'm sorry for you."

"Why?" asked Tiktok.

"Because you have no brains, as I have," said the Scarecrow.

"Oh, yes, I have," returned Tiktok. "I am fit-ted with Smith & Tin-ker's Im-proved Com-bi-na-tion Steel Brains. They are what make me think. What sort of brains are you fit-ted with?"

"I don't know," admitted the Scarecrow. "They were given to me by the great Wizard of Oz, and I didn't get a chance to examine them before he put them in. But they work splendidly and my conscience is very active. Have you a conscience?"

"No," said Tiktok.

"And no heart, I suppose?" added the Tin Woodman, who had been listening with interest to this conversation.

"No," said Tiktok.

"Then," continued the Tin Woodman, "I regret to say that you are greatly inferior to my friend the Scarecrow, and to myself. For we are both alive, and he has brains which do not need to be wound up, while I have an excellent heart that is continually beating in my bosom."

"I con-grat-u-late you," replied Tiktok. "I can-not help be-ing your in-fer-i-or for I am a mere ma-chine. When I am wound up I do my du-ty by go-ing just as my ma-chin-er-y is made to go. You have no i-de-a how full of ma-chin-er-y I am."

Pero lo que más me llama la atención son algunos de los problemas morales con las máquinas capaces de tomar decisiones. Este es un tema que debería tratarse seriamente muy pronto, dados los avances en computación, pero que pocas veces he visto que se traigan a colación.
Digamos que BMW produce un coche que se maneja solo (de los que ya han desarrollado prototipos y en ocasiones han aparecido en noticiarios y programas de tecnología). Ahora, la gente compra estos coches y va feliz viajando de un lugar a otro hasta que de pronto hay un accidente. ¿De quién es la culpa? ¿Es culpa de BMW, del que desarrolló el software, del dueño del coche, de la ciudad, o de quién? Esta pregunta no es fácil de responder, y se plantea también en Ozma of Oz después de que Tiktok haya dicho una cosa que al final resultó incorrecta. ¿A quién hay que culpar? Baum va por la puerta fácil diciendo "a nadie; nadie tiene la culpa". Pero, en general, esto no es suficiente.

Macondo y la red semántica

Hay un pasaje maravilloso en Cien años de soledad en que los habitantes de Macondo comienzan a perder la memoria. Entonces, la gente comienza a etiquetar todas las cosas con su nombre. Desafortunadamente, al pasar el tiempo, incluso el nombre es insuficiente, pues olvidan para qué sirven las cosas; la solución es aumentar las etiquetas para describir también el uso de cada cosa.

Bueno, pues esto (mas o menos) es la red semántica. La idea comienza con etiquetar cada página o elemento de la red con sus contenidos. Una página puede estar marcada como "gatos", es decir que habla sobre gatos, y otra como "sillas" - su tema son las sillas.
Todo esto está muy bien, pero "gatos" y "sillas" son meras palabras que, por si mismas, carecen de significado. Las etiquetas solamente resultan útiles si sabemos qué significan. La página marcada como "gatos" sirve si buscamos información sobre felinos, o sobre Silvestre, pero no si nuestro interés son los muebles.
Necesitamos asociar un significado a cada palabra. Pero mas interesante es que queremos dar ese significado sin recurrir a un meta-lenguaje que simplemente transladaría los problemas del significado a un nivel superior, pero no los resolvería.

Desafortunadamente, definir todos los términos dentro del lenguaje es imposible. Es algo que vemos al hojear un diccionario, en que hay algunas definiciones circulares y palabras que se requieren a sí mismas en su descripción.
En lugar de dar definiciones absolutas se dan descripciones de las relaciones entre las distintas palabras. Asi, un "gato" es un "felino" y "Silvestre" es un "gato", pero no hay nada que nos obligue a interpretar esas palabras como gato, felino y Silvestre, siempre y cuando las interpretaciones satisfagan las relaciones establecidas.

Y eso es el gran reto de la red semántica: describir todas esas relaciones adecuadamente para permitir un entendimiento lo suficientemente correcto de Macondo como para seguir viviendo.

La repetición que atonta

Permítanme comenzar este texto con un pequeño ejercicio, bajo la promesa de que después se revelará la importancia del mismo. Si el ejercicio los aburre, les invito a saltárselo e ir directo a la carne del final.

El ejercicio consiste en realizar operaciones aritméticas simples. Olvidemos todo lo que sabemos de aritmética por un momento, y comencemos por lo más básico. Primero tenemos que aprender a contar: aprendemos los números naturales 0,1,2,... con su órden específico (que es lo que nos permite contar).
¿Listo? Pefecto, pasemos entonces a algo un poco más interesante y difícil: la suma. Para realizar una suma es suficiente con saber contar. Por ejemplo, si queremos sumar 5+4 lo que tenemos que hacer es empezar en 5 y contar hasta 4 moviéndonos cada vez una posición sobre los números reales.
Pero una vez que sabemos sumar, podemos entonces multiplicar, simplemente contando. Usando de nuevo un ejemplo, si queremos multiplicar 6*3, entonces comenzamos en 0 y contamos hasta 3, haciendo en cada ocasión una suma de 6. Es decir, comenzamos en 0, contamos "1" y sumamos, 0+6=6; contamos "2" y sumamos 6+6=12; contamos "3" y sumamos 12+6=18, y terminamos.
Obviamente, contando podemos también calcular potencias y, tal vez más interesante, hacer restas, divisiones, etc.

La pregunta que surge entonces es, ¿por qué se nos enseña entonces a multiplicar en formas tan complejas, cuando todo lo que necesitamos saber es contar? La respuesta creo que es obvia: aunque el algoritmo aquí descrito es muy sencillo en cuanto a su descripción, en realidad sería muy difícil para nosotros como humanos aplicarlo, simplemente porque muy fácilmente podemos equivocarnos mientras contamos. Si quisieramos hacer 2^10, por ejemplo, tendríamos que repetir 10 veces un producto por 2; cada uno de esos productos significa sumar 2 veces el número hasta entonces calculado y cada una de esas sumas consiste en contar hasta el mismo número. Es decir, tenemos tres contadores anidados, y el proceso nos llevaría desde el número 1 hasta el 1024; un tanto tedioso, ¿no lo creen?

En realidad resulta más sencillo y mucho más eficiente realizar las operaciones como nos enseñan en la escuela. Y es esta razón, la eficiencia, lo que hace que en las computadoras se implementen algoritmos más inteligentes para realizar operaciones aritméticas que el simple uso de contadores. De hecho, las máquinas son muy buenas haciendo repeticiones y los contadores son mucho muy fáciles de implementar, pero los diseñadores de hardware y software dedican mucho tiempo (o tal vez en la actualidad ya no tanto, pero en un principio lo hacían) a implementar las operaciones aritméticas más veloces.

Y ahora viene la pregunta que ronda mi cabeza desde hace unas semanas. Si esto es así, ¿cómo es posible que ahora la gente promueva el uso de algoritmos que únicamente se dedican a repetir métodos más simples, sin pensar en que puede haber métodos más eficientes de hacer lo mismo si nos dedicamos a construir un algoritmo especializado? No hace mucho leí un comentario que decía que no valía la pena dedicar tiempo a desarrollar algoritmos especializados si los métodos repetitivos eran suficientemente rápidos (en ese caso, rápido significaba que acababa en menos de una hora con datos medianamente grandes).

La única posible respuesta a ese comentario que me viene a la mente es: la repetición que nos dan las máquinas, ese poder que nos permite simplemente iterar sin pensar, y hacerlo velozmente y sin aburrirnos nosotros, nos está haciendo no sólo tontos, sino flojos para pensar en un mejor método.

¿Algún comentario?

Inteligencia en máquinas

Según la gente en Boing Boing, la Prueba de Turing ha sido superada. En sus palabras:

Just as you can't be sure of the age and gender of the person you're IMing in a chat room, you can't be sure that your opponent in an online poker game is human.

¿O será que los que no pueden distinguir, son justamente aquellos que juegan poker en línea? Eso no me sorprendería.

Y la computadora ...

Resulta que la computadora no tenía nada!
Pero fue buen pretexto para que le dieran un masajito y le instalaran Firefox 2.0 :D

No cabe duda, soy suertudo

Pues sigo sin internet, y ayer eché a perder una computadora, y aún así me considero una persona MUY afortunada; ¿por qué? Echemos un vistazo a los hechos.
Ayer era la fecha límite para entregar un artículo (el del contraejemplo). Hoy en la mañana tenía también que publicar un reporte técnico (antes de las 10 AM), en Dresden.
Pues bueno, me levanté tranquilamente y me apresuré a terminar mis deberes en la oficina. Antes de las 3 PM había terminado ya, tanto el artículo como el reporte técnico. Entonces, mandé el artículo (no sin pasar algunos problemas, por lo que tuve que recurrir a la desesperada solución de mandarlo por correo electrónico), con toda calma envié todos mis archivos a mi respaldo en linea (gracias Gmail :P) y me dispuse a respaldar de nuevo en mi memoria USB.
Como todos los días, conecté la memoria en el puerto y de pronto ZAS! se fue la red de mi máquina. Esto no sería un gran problema, si no fuera porque la configuración de las computadoras está hecha de tal forma que sin red todo se vuelve lentísimo (o no funciona, como el caso de LaTex, que está en la red). Revisé los cables, y todo estaba bien.
Bueno, pensé, no pasa nada, simplemente reinicio y listo, todo como nuevo. Perfecto, la máquina se apaga, y luego prende... y ... NADA! No arrancó. Bueno, la apago de nuevo (de forma forzada ahora) y la prendo y ... sigue sin arrancar. Ahí me mesé los cabellos.
Salí corriendo a buscar a Gabrielle Queck, de soporte técnico. Y sí, en el la sección de Sistemas Inteligentes, de el Instituto de Computación tenemos soporte técnico (por suerte para la gente, como yo, que no le hace a los fierros).
Pues total, va Gabrielle con su sonrisa sempiterna a mi oficina y con toda calma, intenta prenderla de nuevo. No, pues nada (Ni siquiera hacía el beep inicial).
Así que la solución, para ella, fue de lo más sencilla: con toda calma me dijo "Vete a tu casa, y regresa mañana, y ya va a estar funcionando" (todo esto sin dejar nunca de sonreir).
Así fue, me retiré a casa, un poco nervioso por haber tronado mi computadora (todavía no sé ni cómo) pero tranquilo de que en cierta forma los pendientes del día ya los había cumplido.
No quiero ni pensar de qué habría pasado si en artículo no hubiera sido enviado antes.

No creo en Santa Claus

Las ciencias de la computación son un niño pequeño aún en desarrollo. Y así como los niños, madurando y aprendiendo de su experiencia son capaces de decir un día, sin dudas en su interior "no creo en Santa Claus", así los científicos de la computación deberán un día respirar hondo y decir claramente "no creo en la Inteligencia Artificial"

Generalizaciones

Como comenté ayer, Torsten se graduó de la maestría con una tesis titulada Decomposition of Weighted Multi-operator Tree Automata. Aparte de ser una de las pocas pláticas técnicas que realmente he entendido en mi vida, la presentación de este trabajo me trajo unas ideas sobre las generalizaciones, que quiero compartir.
Por favor, no se espanten con los nombres, que los detalles de qué son o para qué sirven no son importantes para el punto que quiero mostrar.
La teoría de autómatas surge para reconocer un tipo de lenguajes. En este caso, un lenguaje es un conjunto de palabras. Pero, ¿por qué quedarse ahí? Hay aplicaciones para las que conjuntos de palabras no son interesantes, sino que se quieren distinguir conjuntos de árboles. Para esto, la teoría de autómatas fue generalizada, dando lugar a los autómatas de árboles.
En este caso, para un árbol dado, el autómata contesta "si" o "no"; o para los computólogos, 0 o 1. Pero, ¿es esto suficiente? Digamos que no solo queremos saber si el árbol tiene cierta propiedad, sino además asociar un costo al mismo; así surgen los autómatas de árboles con pesos. En ellos, dado un árbol, el autómata regresa un número, perteneciente a una estructura algebráica previamente definida.
Ahora generalicemos un poco más. En lugar de simplemente aceptar un árbol con un costo, creamos un mecanismo, que actúa de la misma forma que los autómatas, que dado un árbol da como resultado un conjunto de árboles junto con unos pesos. Estos son transformadores de árboles con pesos.
Un punto importante aquí, es que los transformadores pueden hacer estrictamente más cosas que los autómatas.
Pero, regresando por un momento a los autómatas, ¿qué pasa si en lugar de números usamos como pesos operadores? Bueno, pues eso es lo que en la tesis de Torsten se llama autómata multi-operador de árboles con pesos. Ahora, durante su plática, mientras estaba mostrando resultados de descomposición, Torsten muestra, casi sin notarlo, que un transformador de árboles es un caso particular de uno de estos autómatas. ¿A alguien le suena una campanita aquí?
Tenemos que los autómatas con pesos usando operadores son más generales que los transformadores que son estrictamente más generales que los autómatas con pesos. ¡Aquí hay un problema!
Obviamente, no existía tal problema, sino que yo estaba dejando de lado un hecho muy importante: el conjunto de operadores no es un semianillo, y por tanto, los autómatas multi-operador son también estrictamente más generales que los autómatas de pesos originales. Es decir que, lo que parecía un caso particular (usar la estructura de los operadores cuando puedes usar cualquier otra) era realmente una generalización.
La pregunta viene ahora: ¿se puede generalizar más?; ¿hay algo más que quisiéramos hacer con autómatas que no se pueda hacer ya? Bueno, pues la respuesta es: si la Tesis de Church es correcta, entonces no.
Torsten demostró que sus autómatas son capaces de simular una máquina de Turing. Y esto me regresa al punto que quería tomar: se comienza con la máquina de Turing, y se hace un caso particular para resolver un problemita: los autómatas. Poco a poco se va generalizando, agregando propiedades deseables y, de pronto, estamos de regreso en la máquina de Turing.
Yo siempre he sido adepto de las generalizaciones (vean mi tesis de maestría, o mis reportes técnicos como prueba de ello), pero cuando las generalizaciones se van de las manos, ¿sirven de algo?

Problema de parado

Ya había hablado antes de los problemas de decisión. Ahora voy a hablar de un "caso particular" de estos: el de decidir si una palabra pertenece a un lenguaje específico. Puse entrecomillado lo de caso particular porque en realidad cualquier problema de decisión se puede escribir de esta forma, pero eso es cosa aparte.
Veamos, una palabra es eso, una secuencia de símbolos de un alfabeto dado; un lenguaje es un conjunto de palabras. Por ejemplo la palabra palabra pertenece al lenguaje palabras en español, pero aerdssmensfeas no pertenece a ese lenguaje. Sin embargo, aerdssmensfeas pertenece al lenguaje palabras que comienzan en 'a', pero palabra no.
Entonces, si me yo tengo un lenguaje, y me dan una palabra, ¿cómo decido si pertenece a ese lenguaje? Una forma es usar una máquina de Turing. No se dejen asustar; una máquina de Turing es simplemente un mecanismo que tiene 4 cosas: una memoria física (cinta), una memoria virtual (estado), un apuntador en la cinta, y una lista de instrucciones.
La máquina únicamente ve el símbolo que está escrito en la celda de la cinta que marca el apuntador, y el estado que contiene, y sigue la instrucción adecuada. Una instrucción dice básicamente "si el símbolo es 'a' y el estado es 'q', escribe 'b' y muévete hacia adelante/atrás". Entonces, si el apuntador señala al símbolo 'a' y la memoria contiene el estado 'q', la máquina va a borrar esa 'a' y escribir 'b' en su lugar, y luego mover el apuntador a la siguiente o anterior celda de memoria, dependiendo de lo que diga la instrucción.
Ahora, para decidir si una palabra pertenece o no al lenguaje, se incluyen también dos estados particulares: acepta y rechaza. Si la máquina encuentra alguno de estos estados, entonces se detiene y hace lo que el estado le indica. Existe otro caso adicional, que es cuando la máquina jamás encuentra uno de esos estados; en ese caso, la máquina debe rechazar la palabra.
Aqui nos topamos con un problema, porque si queremos implementar la máquina, nos gustaría saber si esta se va a detener cuando le demos la palabra, para poder rechazarla sin tener que dejar la máquina corriendo por siempre. ¿Es posible hacer esto?, es decir, ¿podemos saber de antemano si una máquina se va a detener?
Primero veamos que, utilizando únicamente máquinas de Turing, esto no es posible. Para esto vamos a usar una variación de la paradoja de Russell (¡qué maravillosas son las paradojas!).
Supongamos que existe una máquina de Turing, llamémosla T (de Todopoderosa), que puede decir en tiempo finito, dada otra máquina y una palabra, si esa otra máquina se va a detener o no cuando se ejecute con la palabra dada. Entonces, dada la máquina y la palabra, podemos saber si esta se acepta o no: primero ejecutamos la T, sabemos que se va a detener, y nos va a decir si la otra máquina se detendrá o no. Si dice que no, entonces simplemente decimos que la máquina rechaza la palabra; si dice que sí, entonces la ejecutamos y damos el resultado que da la máquina.
Ahora podemos crear la máquina D (de Demoniaca) que acepta a todas las máquinas de no se aceptan a sí mismas, es decir, que si se da una codificación de la máquina y ella misma, esta va a rechazar.
La pregunta ahora es ¿D se acepta a sí misma?. Ahí tenemos una contradicción por donde lo veamos, pues si se acepta, entonces se tiene que rechazar, y viceversa.

Validez y completud

Nota:quería titular este texto correctud y completud pero, al no encontrar ninguna referencia a que la palabra correctud es correcta [;)], decidí cambiarlo por el actual.
Permítanme comenzar con unas definiciones. Un problema de decisión es aquel donde las únicas respuestas posibles, para cualquier entrada, son SI o NO. Un problema de decisión es decidible si existe un algoritmo que da la respuesta a cualquier entrada en tiempo finito. Es semi-decidible si existe un algoritmo que, siempre que la respuesta es positiva, contesta acertadamente en tiempo finito, pero que puede no contestar en caso de respuestas negativas.
Por ejemplo, decidir si un algoritmo concluye sus operaciones dada una entrada para el mismo, es semidecidible pues simplemente podemos correr el algoritmo sobre esa entrada y, si termina, contestar SI, pero si no termina, no podremos contestar nada.
Ahora, un mismo problema se puede resolver con distintos algoritmos. Un algoritmo es correcto si siempre que contesta SI lo hace acertadamente, y es completo si siempre que la respuesta es SI este la contesta adecuadamente. Obviamente, el algoritmo ideal sería aquel que es a la vez correcto y completo, pues eso significa que jamás comete errores (cuando contesta).
Un ejemplo trivial de un algoritmo completo es el que siempre, ante cualquier entrada, contesta SI. Sobre algoritmos correctos hay dos ejemplos triviales: uno, el que siempre contesta NO, y otro el que siempre se cicla y no da nunca una solución. [Recuerdo haber leído un ejemplo similar hace poco en Planeta Linux, pero no puedo encontrar la referencia adecuada].
En algunos casos, en especial cuando se quiere implementar algo eficientemente, no se puede tener un algoritmo correcto y completo, pues este demoraría demasiado tiempo. En esos casos hay que hacer una elección: completo e incorrecto, o correcto e incompleto. Históricamente, esta cuestión se ha resuelto fácilmente y con poca controversia: que sea correcto, aunque resulte incompleto.
Hace poco, ante una implementación de Lógica Descriptiva Difusa, un computólogo expresó su duda al respecto entre sus colegas. Muchos de ellos se mostraron incluso sorprendidos ante la pregunta, y contestaron como lo dije antes: "es mejor que sea correcto". Yo por mi parte, me puse a buscar problemas y me resultó dificil encontrar casos en que prefiriera que fuera correcto sobre la completud; de hecho, los únicos tales casos que hallé pertenecían a lógica: satisfacibilidad, subsuma, inclusión. Todos los problemas de "la vida real" que pude pensar era mejor que fueran completos a correctos. Por supuesto, el mismo algoritmo cambia de completo a correcto, y viceversa, si se resuelve el dual del problema inicial, pero los humanos tenemos una forma de expresar esos problemas (generalmente en forma negativa, como: ¿la planta nuclear va a estallar?) que hace que los problemas duales suenen muy irreales (¿es la planta nuclear segura?).
Para entender esto, volví la mirada a la estadística. Ahí, cuando se hacen pruebas de hipótesis, siempre (o generalmente) se elije como hipótesis inicial aquella que está del lado seguro, pues de acuerdo con estas pruebas, sólo vas a rechazar tu hipótesis si tienes evidencia suficiente para ello.
Así, siempre voy a asumir que la planta va a estallar, que el acusado es culpable (aunque esto contradiga las iniciativas judiciales de muchos países), que el león va a atacar, y un muy largo etcétera. Bajo esta perspectiva, si asumimos que nuestro problema de decisión está relacionado con una hipótesis inicial de una prueba de hipótesis como esta, en el caso general preferiríamos errar contestando SI cuando era NO, pues no había evidencia suficiente para refutar la hipótesis inicial, pero que siempre que la respuesta sea SI sea esa la respuesta. En otras palabras, a pesar de lo que digan los lógicos y computólogos, en general, y siempre y cuando el problema esté planteado en forma segura, es preferible un algoritmo completo sobre uno correcto.