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

Finalmente, después de un par de semanas de muchísimo trabajo, hoy y mañana son los días clave: hoy la presentación del abstract del poster, y mañana los posters en sí. En una hora arrancan las presentaciones así que no tengo tiempo para un post muy largo…

Estoy muy contento con cómo salió todo acá; el evento superó ampliamente mis expectativas y sobre todo disfruté muchísimo el tiempo dedicado a investigar en lógica, además que creo que los resultados de mi trabajo acá son interesantes lo que hace que sienta que valió la pena dedicarle tanto tiempo y esfuerzo.

No tuve mucho tiempo para bloguear, aunque sí muchísimo material para hacerlo… acá tuve oportunidad de conocer a gente interesantísima y de gran trayectoria, incluyendo a Stephen Wolfram, como ya contaba en el post anterior, y de casualidad por esas cosas de la vida, a John Conway que estaba dando unas conferencias para chicos genio de 12 años que por algún motivo están reunidos acá (ayer Wolfram les dio una también, muy divertida por cierto).

Ya se termina, mañana se cierra este evento, paso un par de días por Boston y me vuelvo para Buenos Aires.

Estos días podría haber escrito montones de blog posts por día, ya que la estoy pasando muy bien en la Summer School de Wolfram Research y encontrando muchísimas cosas interesantes todo el tiempo. El campus de UVM es maravilloso y la ciudad de Burlington es hermosísima, además de tener ardillas y gaviotas (supongo que son gaviotas) que en Buenos Aires jamás tenemos oportunidad de ver.

Las conferencias de la escuela de verano fueron escalando en dificultad e interés: empezaron siendo un poco básicas y enseguida se pusieron muchísimo más atractivas, y algunas de ellas fueron claramente reveladoras. Pero más allá de las conferencias en sí, lo que más me atrae de esta experiencia es la oportunidad de estar acá con gente de todo el mundo y de todo Estados Unidos, y de algunas de las universidades más importantes del mundo, compartiendo los avances y dificultades de nuestras investigaciones, lo que hace que haya un continuo clima intelectual que es absolutamente fascinante. Y quizás de algún modo, ése es el propósito verdadero de esta escuela de verano: juntar a gente de todo el mundo y de áreas diversas a investigar sobre temas relacionados.

Por otra parte, tiene que mencionarse, por aquí anda el señor Stephen Wolfram. Hacia fines de los 80s era uno de los científicos más conocidos del mundo en particle physics, trabajando con premios Nobeles como Richard Feynman, Murray Gell-Mann, etc; y a partir de entonces inició una serie de emprendimientos que de un modo u otro cambiaron la historia de nuestra ciencia: la investigación exhaustiva de autómatas celulares elementales (también, por lo que entiendo, descubiertos por él, la abstracción última del camino iniciado por Ulam, Von Neumann y otros), la creación del programa SMP, ahora Mathematica, que hoy día es usado masivamente para matemática e ingeniería en todo el mundo (y que lo hizo millonario), y muchos pequeños impactos más que surgen muchas veces de anécdotas por aquí.

NKS en sí, si cambiará el mundo o no lo sabremos en muchos años, como siempre en estos casos, pero sin duda como metodología permite acceder a ciertos nuevos puntos de conocimiento, y sin duda en el libro en sí de forma inequívoca Wolfram con sus colaboradores nuevamente encuentra soluciones a problemas interesantes: la universalidad de 110, el sistema de axiomas más corto de la lógica, etcétera, además de brindar un extenso y ordenado recorrido por muchísimas áreas de la ciencia y la matemática, y de hacer un recorrido exhaustivo por los estudios de los autómatas celulares y de otros tipos de sistemas simples también. Y por otra parte he visto aquí algunas otras cosas de las que, simplemente, no puedo decir más que W-O-W. Creo que Wolfram está a punto de hacerlo otra vez.

Estando aquí nosotros tenemos que desarrollar unos proyectos de investigación sobre complejidad, y el mío en este caso es sobre el análisis del grafo de demostraciones en lógica abstracta. Estoy muy feliz con este proyecto, estoy muy feliz de estar haciendo investigación sobre algo que me fascina desde siempre, la lógica abstracta y sus fundamentos, y además tengo en muchas oportunidades el feedback, y apoyo de la gente de Wolfram Research o de Stephen Wolfram mismo! sobre el avance de este proyecto (de hecho, la idea inicial para el mismo fue de SW; es para tratar de avanzar sobre un problema abierto en lógica que yo no conocía).

En definitiva, estoy en un lugar maravilloso, rodeado de gente maravillosa y, como decía en la carta de Wolfram Research, outstanding, sin duda. Y estoy cerquita del polo norte, los días son un poco más largos, además es verano, escucho todo el día conversaciones en inglés y encontrar una ardilla es siempre cómico. Y en cualquier momento puede surgir, al azar, la idea que estabas buscando, o una conversación sobre complejidad en la mesa.

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.

Hace un par de días tuve el gusto de ver una charla de Gonzalo Frasca en Educ.ar, sobre la que Alejandro Piscitelli cuenta algunos detalles aquí (en realidad sólo asistí a la segunda de las que relata).

Gonzalo es uno de los teóricos de videojuegos más conocidos del mundo (con mérito: ya que fue quien dio origen a toda la nueva corriente de ludología), además de ser dueño de un estudio de desarrollo que produce algunas joyas en materia de videojuegos.

Sigan atentos a su blog, ya que es posible que siga dando conferencias por aquí, y realmente vale la pena verlas.

Una breve explicación de esta pausa en el blog: estoy trabajando muchísimo, y cuando no, haciendo los preparativos para un viaje inminente a los Estados Unidos. Pronto haré un post sobre el tema, pero lo que puedo decir por ahora es que voy a estar estudiando unas semanas en University of Vermont, y luego voy a hacer una breve visita a Boston, por motivos que ya explicaré luego.

Más detalles pronto, o quizás durante el mismo viaje.

Segundo evento de complejidad 2.0 este jueves 15. Más info aquí: http://www.lukasnet.com.ar/blog/archives/000390.php

Complejidad 2.0

Esta vez con expositores: Andrés Ricardo Schuschny, Marina Umaschi, Mateo Ortega, Viviana Dehaes y Nacho Uman (y de nuevo Mario Lucas Kiektik como coordinador).

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.