Inteligencia Artificial


(Desde 2008 que no escribo en este blog; en esta serie de posts sobre esteganografía quizás reinicie mis posts al blog, o quizás no… ya veremos)

Hace unos días presenté un trabajo en JAIIO/WSegI sobre este tema, que pueden ver aquí: http://www.41jaiio.org.ar/WSegI_Contribuciones. A continuación presento brevemente y de forma muy informal sobre qué se trata este artículo. Los detalles formales y la matemática están en el paper.

Esteganografía es la disciplina que estudia el envío de mensajes escondidos (dentro de mensajes u objetos), de forma que no se sospeche que estos están allí. Un ejemplo típico es: un individuo A le quiere enviar un mensaje a un individuo B, pero hay un individuo C que intercepta los mensajes. La idea es que es necesario poder enviar los mensajes escondidos de forma tal que C ni siquiera sospeche que estos están allí.

En el caso de esteganografía de textos, se envían textos de aspecto inocente que ocultan, dentro de ellos, otros mensajes (que pueden ser textos o bits arbitrarios). Una forma de esteganografía de textos trivial y que todos conocen es partir de un texto como “ahora lo veo”, y agregar mayúsculas al mismo en lugares que indiquen qué letras son las que contienen el segundo mensaje escondido: “aHOra Lo veO”. En este caso el submensaje es, por supuesto, “hola”. Claro que la esteganografía estudia métodos más difíciles de detectar que éste.

El segundo concepto interesante que se usa en este proyecto son las cadenas de Markov. En vez de explicarlas como un modelo de proceso estocástico y explicar sus propiedades matemáticas, voy a tratar de dar una intuición sencilla de lo que son estos objetos.

Supongamos que tengo un texto, que es una secuencia de palabras como “w1 w2 w3 w4 …”. Hay varias formas de analizar este texto, una bastante sencilla es por ejemplo contar cuantas veces aparece cada palabra. Por ejemplo “la” aparece 1000 veces, “casa” aparece 300, etc. Más interesante, son las combinaciones de dos palabras, lo que se conoce como bigramas. Podemos decir, “la casa” aparece 120 veces; “el perro”, 50, y así sucesivamente.

Estas propiedades que extraigo de los textos definen un modelo de lenguaje. A partir de las mismas puedo entender cómo funciona un lenguaje a través de lo que veo en textos (a partir de sus propiedades estadísticas), y también puedo hacer cosas interesantes como generar nuevos textos haciendo de cuenta que mi modelo representa perfectamente el lenguaje. Más sobre esto luego.

Si usamos un poco de probabilidad por un momento, podemos decir algo un poco más interesante aún, que sólo trabajar con las frecuencias de los bigramas. Usando una notación de probabilidad condicional como

P(Xn+1 = casa | X n = la) = 0.5

estamos obteniendo una caracterización más interesante. Lo que esto significa es: si la palabra número n en el texto es “la”, la probabilidad que la siguiente palabra sea “casa” es 0.5. Es decir, la mitad de las veces que aparece la palabra “la”, la siguiente palabra es “casa”. Estas probabilidades (que se pueden computar fácilmente desde las frecuencias) definen la cadena de Markov, pero la forma más familiar para los programadores de la cadena de Markov es en su forma gráfica, que es una máquina de estados como la siguiente:

Markov chain

donde las transiciones son las probabilidades condicionales, y los estados son las palabras (y generalmente hay un estado inicial para indicar el inicio). Por supuesto las cadenas de Markov no funcionan sólo con palabras, esto es sólo para los efectos de este caso particular de análisis sencillo de textos.

A partir de un texto cualquiera puedo extraer una cadena de Markov que modela el lenguaje que se usa en el mismo. Esto (y otros modelos de lenguaje) tiene algunas ventajas muy interesantes para nosotros:

1- dada una cadena de Markov y un texto cualquiera, puedo averiguar cuál es la probabilidad que el texto haya sido generado por esa cadena de Markov… puedo hacer, por ejemplo, un detector simple de lenguaje español o inglés

2- más interesante para nuestros propósitos: dada una cadena de Markov, puedo generar nuevos textos al azar. Estos textos generados se parecerán en cuanto al lenguaje usado, al texto a partir del cual se extrajo la cadena.

Ambas ventajas se obtienen a partir de una idea sencilla. Supongamos que yo quiero saber cuál es la probabilidad de que la frase “el perro azul” sea generado por una cadena de Markov con estados que son palabras. Todo lo que tengo que hacer es calcular las probabilidades de P(perro|el) y P(azul|perro) y multiplicarlas entre sí:

P(el perro azul) = P(Xn+1 = perro | Xn = el) * P(Xn+1 = azul | Xn = perro)

En la siguiente parte, explicaré cómo es que se usan las cadenas de Markov en esteganografía, y contaré un poco más sobre mi trabajo en este tema.

En menos de una semana voy a estar saliendo para Vermont, Estados Unidos, a pasar una temporada en el campus de University of Vermont.

¿El motivo? Voy a asistir a una escuela de verano organizada por Wolfram Research (la empresa desarrolladora del programa Mathematica, usada en ingeniería y matemática en todo el mundo), sobre el tema de sistemas complejos / complejidad matemática. Va a estar en la misma nada menos que Stephen Wolfram, uno de los grandes científicos de este siglo, que trabajó junto a premios Nobel como Feynman y Gell-Mann en importantes avances a la física, y que fue uno de los pioneros de la ciencia de la complejidad.

El evento es la NKS Summer School 2008, la escuela de verano sobre el nuevo esquema para el estudio de la complejidad y la ciencia iniciado por el libro “A New Kind of Science”, de Stephen Wolfram. Va a ser una oportunidad increíble, sin duda, de aprender mucho sobre la complejidad matemática, de la mano de sus fundadores.

Como último detalle, Wolfram Research y FQXi (un science fund muy importante de USA) me dieron una sponsorship parcial para esta escuela de verano, con lo cual imagínense que mi alegría es completa! Estoy muy contento por participar de este evento, y obviamente mientras pueda durante el viaje les voy a ir contando las novedades que tenga sobre el mismo.

En un post reciente, aquí, hablé de la beta de Powerset, un muy interesante buscador semántico. La novedad ahora es que el buscador ya está abierto para todo público, así que se lo puede probar a gusto.

La dirección: http://www.powerset.com/

Finalmente avanza la IA en el Go, el milenario juego chino. Aunque la variante principal (y más complejo) de este juego sucede en tableros de 19×19, es posible jugar al juego en otras variantes, entre ellas una de dificultad intermedia de 9×9. Y es en esta última variante en la que acaba de suceder que un Maestro de Go perdió en una partida contra un programa de Inteligencia Artificial.

Esto es una noticia porque hasta no hace mucho, aún los mejores sistemas de IA no podían ganarle a jugadores con poca experiencia en el juego, ni hablar de ganarle a los mejores jugadores del mundo en este juego. En cambio, para otros juegos como el Ajedrez, ya desde hace muchos años las computadoras pueden ganarle las partidas aún a los campeones. En el Go esto no era todavía así porque el juego presenta una variedad de jugadas (y posiblemente una complejidad estratégica) muy superior a la del Ajedrez, y por tanto representa un desafío mucho mayor para las computadoras que éste.

Más detalles sobre la noticia aquí.

Si queda alguien interesado en robótica que todavía no haya visto este video, está a tiempo. No puedo recomendarlo lo suficiente: es lo que más me impresionó de todo lo que ví sobre robots en mucho tiempo, sin ninguna duda. Un robot cuadrúpedo que se desplaza de forma totalmente natural, pero que además es capaz de evitar caídas en todo tipo de circunstancias que dejarían a cualquier otro robot patas para arriba. Muy impresionante.

Pueden verlo en el sitio de la empresa desarrolladora, Boston Dynamics, aquí.

Tetris AI: computer plays Tetris” es un proyecto verdaderamente curioso. Desarrollado por Colin Fahey, el proyecto presenta un software que juega al Tetris solo, es decir sin ningún tipo de asistencia humana.

tetris_ai_256x192.jpg

Más interesante todavía es el funcionamiento del programa: el software interpreta lo que sucede en la pantalla del juego a través de la información que ingresa desde una webcam, y realiza sus movimientos directamente ingresando las teclas presionadas por el puerto de teclado.

En definitiva, el programa combina algoritmos de visión artificial (para reconocer la imagen en pantalla), de inteligencia artificial (para realizar las jugadas), y una sencilla interfaz de hardware para lograr su objetivo.

standard_tetris_demo_ai.jpg

El sistema de reconocimiento de piezas en acción
(la segunda computadora)

Una instalación típica de este programa se haría en dos computadoras separadas: la primera corriendo el Tetris; la segunda capturando la pantalla de la primera a través de una webcam, tomando las decisiones correspondientes y enviándolas de nuevo a la primer computadora a través de una interfaz de teclado (hmm… creo que los que estudian la cibernética, y los ciclos de feedback, etc. estarían muy felices con este sistema).

Menciono este proyecto acá porque cuando lo vi me pareció realmente interesante, además de ingenioso. Digo ingenioso refiriéndome sobre todo al enfoque que usa para realizar el reconocimiento por visión de las fichas, que permite simplificar mucho un problema que de otro modo resultaría bastante más complicado. Pero además hay que decir que ya el concepto básico del proyecto (hacer un programa que juegue solo al Tetris) es curioso y original por sí mismo.

Más info sobre este proyecto en la página dedicada a “Tetris AI: computer plays Tetris“.

Creo que ya no se escucha tanto sobre Powerset ahora, pero hace un par de meses todo el mundo parecía estar hablando de este sitio. ¿Podría Powerset desbancar a Google del mundo de las búsquedas? Que sí, que no, muchas teorías diversas (algunas más conspirativas que otras), y algún que otro texto interesante sobre el sistema de IA, que permite hacer búsquedas inteligentes en la web.

powerlabs.png

Así que finalmente conseguí mi ingreso a la prueba del sitio, y hoy empecé a ver realmente cómo funciona. Y la verdad, no me decepcionó en lo más mínimo, aunque como ya había anticipado alguien, es un poco desalentador que sólo se puedan hacer búsquedas estructuradas por ahora, y dentro de ciertos conjuntos de datos limitados (principalmente la Wikipedia).

Igual, me pude sorprender por los buenos resultados de las búsquedas en lenguaje natural, y por la buena comprensión del motor sobre los textos que analiza. Sabiendo que ninguna búsqueda textual iba a ayudarle a encontrar una respuesta, puse “Who killed Napoleón?” y Powerset me retrucó con un conjunto de resultados referidos a quienes lo derrotaron, y no a quienes lo mataron (que no lo mató nadie… al menos no de forma completamente comprobada).

gauss.png

En definitiva… interesante prototipo de la gente de Powerlabs; no sé si será el nuevo Google o algo por el estilo, pero sin duda es una herramienta interesante, al menos por lo curiosa. Y por lo monstruosamente sofisticado (o ingenioso) que debe ser el motor de lenguaje que permite tamaño prodigio.

Página siguiente »