Programación


(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 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í.

palermovalley.jpgEs increíble lo que está pasando con Palermo Valley: todo empezó en Twitter, con un meme y una idea, y en menos de tres semanas ya se había organizado un evento de empresarios y emprendedores web 2.0 que fue un impresionante éxito.

A éste evento siguió otro, y ya vendrá otro enseguida. Pero lo interesante es que realmente esto que pasó sirvió para mostrar: 1) cómo cambiaron los ritmos en unos pocos años, y cómo una herramienta como Twitter puede iniciar una revolución en los negocios, 2) cuántas empresas web 2.0 hay en Argentina (en particular en Palermo y alrededores), y cuánta energía hay volcada en éstas… posiblemente la mayor parte de la energía emprendedora de tecnología actual.

Por otra parte, está muy claro que esto solamente puede crecer, a partir de ahora. Una industria puede nacer de una comunidad, como el caso de la ADVA nos lo demostró hace algunos años ya, y en este caso una comunidad de muy grandes dimensiones, con capital monetario e intelectual muy impresionante se afianzó con una rapidez increíble, lo que me hace augurar lo mejor para esta industria.

startmeup.pngPor otra parte, algunas de las personas que impulsaron Palermo Valley vienen trabajando hace rato en un evento de mayor magnitud, Start Me Up Argentina, un evento destinado a juntar programadores, diseñadores, emprendedores e inversores en un mismo lugar, que puedo decir por lo que me contaron que va a ser muy, muy poderoso. Recomiendo visitar su sitio web, para ver los objetivos del evento y los conferencistas invitados.

Estos días, con la presentación de una demo del software que estoy desarrollando estos días, me ausenté un poco del blog. Ahora, aunque sigo bastante ocupado, vuelvo con la intención de mantener cierta regularidad, aunque sea a fuerza de posts breves y sencillos (que era un poco la idea nueva para el blog).algo-resour1.png

Hoy quiero recomendar sencillamente un link muy interesante que encontré hace poco, aunque ya no recuerdo dónde: un sitio web con interesantísimos papers de Pixar, que no sólo muestran un poco de la cocina de las películas de esta empresa, sino que también dan una idea de la capacidad de R&D de la misma, con una importante producción de papers sobre temas de matemática y programación gráfica.

(Además, por cierto, me parece que hay que destacar que la empresa exponga sus trabajos al mundo, sin quedarse en el secretismo y en documentos privados.)

Pueden encontrar los papers de Pixar aquí: http://graphics.pixar.com/

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“.

Página siguiente »