BorjaNet

Hoy hemos tenido una clase de Matemática Discreta genuinamente interesante y divertida. Tanto así que, al igual que cuando aprendimos sobre las Leyes de Potencia, no puedo resistir el impulso de contar en el blog lo que hemos aprendido hoy.

Llevamos ya un par de días aprendiendo sobre las Cadenas de Markov, una estructura matemática que explicaré en seguida. Antes de dar la explicación, me parece que tengo que aclarar que lo que voy a contar está basado en las clases que nos ha dado Carly Klivans, nuestra profesora de Matemática Discreta y que ella, a su vez, se ha basado en esta web. Vamos, para que sepais que los ejemplos que voy a dar no me los he inventado yo, nos los han dado preparaditos y bien explicaditos :-P

En fin, a lo que iba. Las Cadenas de Markov. Primero os voy a explicar lo que son, y seguramente cuando termine la explicación direis: “Muy bonito, ¿y esto para que sirve?”. Ese es realmente el objetivo de este artículo. Demostraros, a través de los ejemplos que nos ha enseñado la profa, que una estructura matemática (como las Cadenas de Markov) pueden tener un sentido del humor :-)

Una Cadena de Markov tiene una definición formal un tanto espesa que requiere ciertos conocimientos de probabilidad . Afortunadamente, podemos evitarnos todos esos formalismos si definimos una Cadena de Markov como un grafo. En concreto, como un digrafo, en el que las aristas entre nodos están dirigidos. Para que nos entendamos: circulitos conectados con flechitas (”Ahhhhhh”, exclama el público). A cada vértice/ nodo/circulito lo llamaremos estado, y a cada arista/flecha la llamaremos transición. Desde un estado podemos tener una transición a cualquier otro estado del grafo, incluido el propio estado del que partimos. Y ahora atentos: cada transición tiene una probabilidad asociada, y la suma de las probabilidades de las transiciones salientes de un estado siempre suman 100% (ó 1, según se mire).

Vale, me imagino que a estas alturas os habré perdido a la mitad, así que vamos a pasar rapidamente a un ejemplo para que nos entendamos mejor. Imaginaros que estamos analizando un lenguaje que no conocemos y, siendo personas muy matemáticas, queremos descubrir los patrones que hay en ese lenguaje. En concreto, imaginaros que la unica frase de ese lenguaje es HELLO THERE. De hecho, imaginaros que nos encontramos con esa frase repetida muchas veces, y que consideramos el espacio como un caracter más (vamos a denotarlo con el caracter de subrayado para que salte a la vista): HELLO_THERE_HELLO_THERE_HELLO_THERE (etc, etc.)

Ahora, creamos un grafo en el que tenemos un estado por cada letra (sin repeticiones, en este caso: H, E, L, O, _, T, R). Ahora, ponemos las transiciones. Empecemos por las transiciones del estado H. Desde la letra H sólo podemos pasar a la letra E, por lo cual esa transición tiene probabilidad 100% (si nos encontramos con una H, entonces por narices habrá una E después). Ahora nos fijamos en el estado E. En este caso, resulta que después de la E podemos tener una L, una R o un espacio. Por lo tanto, hay tres transiciones (a los estados L, R, _) cada una con probabilidad 33%. Si completamos el grafo entero, nos encontramos con esto:

Fijaos en que (tal y como he dicho antes) la suma de las probabilidades de las transiciones salientes siempre suman 100% (vale, supongamos que 33+33+33=100). [Si no te gustan las matemáticas, puedes ignorar el resto de este parrafo] La propiedad que distingue a las Cadenas de Markov (que estrictamente es lo que llamariamos un proceso) es que las cadenas de Markov ‘no tienen memoria’. Llamemos X_n al estado en el que nos encontramos tras recorrer n transiciones. Ahora escojamos arbitrariamente dos estados i y j. Resulta que la probabilidad de que X_n+1 sea i dado que X_n haya sido j no depende en el resto de estados por los que hemos pasado antes. Es decir, si me situo en un estado arbitrariamente, la probabilidad de pasar a otro estado depende unicamente del estado en el que estoy, no de los estados por los que he pasado anteriormente. Esto es lo que se conoce como la propiedad de Markov. Finalmente, otro dato matematico curioso: podemos representar una Cadena de Markov como una matriz estocástica, lo que nos permite realizar cálculos muy interesantes.

Llegados a este punto, seguramente pensais lo mismo que pensé yo en su momento: “Vale, muy bonito el dibujo del grafo pero, ¿para qué cojones sirve esto?”. Bueno, una de las cosas que podemos hacer con una cadena de Markov (aunque no la más impresionante) es hacer una simulación. La profesora hizo una simulación en su ordenador, y le salió el siguiente texto: herellllo here helo thelo the he herere lllo thelo thellllo. Un texto un tanto inutil, pero aun así podemos ver que han aparecido palabras del idioma inglés (”the”, “he” y “here”) que no eran palabras en la frase que estudiamos (”hello there”). Otra razón por la que el texto generado es un tanto inutil es porque la frase que estudiamos no es muy representativa de todo el idioma inglés, y porque es dificil formar palabras (y mucho menos frases) si nos fijamos en las letras una por una. Si las tomamos, por ejemplo, dos por dos (en cada estado, dos letras consecutivas) los resultados mejoran un poco, aunque todavía no se forman frases con sentido.

Bueno, y aquí es donde ha empezado la diversión. La profesora ha cogido un capitulo entero de “Guerra y Paz”, y ha creado (con un programa) tres cadenas de Markov: una que analiza el texto letra a letra, una que analiza el texto cogiendo las letras de tres en tres, y una que analiza el texto palabra a palabra. Los resultados fueron a la vez fascinantes y a la vez divertidisimos. Con las dos primeras cadenas no habia frases con sentido, pero era increible ver que creando una cadena que tomaba las letras de tres en tres, la simulación (que no hace más que saltar aleatoriamente de estado en estado, atendiendo a las probabilidades de las transiciones) generaba mogollon de palabras del idioma inglés, incluidas palabras complejas (me parece que aparecia la palabra “invariablemente”… que esa palabra haya surgido de un proceso aleatorio me asombra un poco). Y cuando nos ha enseñado el texto generado por la tercera cadena (la que analizaba palabra por palabra) han empezado las mofas cuando hemos visto frases perfectamente construidas, pero un tanto ridiculas (como “Me parece que vengo pero no vengo aunque el cuerpo es gordo”). Las carcajadas han llegado cuando nos ha enseñado un ejemplo que aparece en esta web. El ejemplo consiste en coger Alicia en el Pais de las Maravillas, la Biblia, y unas cuantas obras de Shakespeare, y generar una cadena de Markov analizando los textos palabra a palabra. El resultado de la simulación generó un texto que empezaba con este profetico texto:

Alice was beginning to write out a history of all flesh, as God hath judged me, and I will tell you my adventures–beginning from this my oath, when thou fleddest from the engine, and everybody jumped up in alarm, For the Baker had met with again!’

Y con la siguiente joya:

And he was circumcised in the land of Egypt

Y quiero insistir en que estos textos han sido generados aleatoriamente tras analizar los patrones que se producen y se repiten en el idioma inglés. Evidentemente, esto es un ejemplo un tanto cómico. Sin embargo, las Cadenas de Markov son una herramienta muy potente para el reconocimiento de patrones. De hecho, hay un tipo de Cadena de Markov conocido como “Modelos Ocultos de Markov” (Hidden Markov Model) que se utiliza mucho en programas de reconocimiento óptico, de voz, de lenguaje natural, etc. Los Modelos Ocultos de Markov los vimos fugazmente en la otra asignatura que cursamos este cuatrimestre (Grandes Ideas de la Computación) y, aunque conceptualmente son sencillos de entender, los algoritmos que operan sobre ellos son muuuy complicados. Sin embargo, cuando nos lo explicaron me quedé impresionado porque por fin entendí (a grosso modo) como funcionan los programas que extraen información de cosas tan complejas como el habla humana.

Bueno, igual he aburrido a más de uno :-) Ya lo siento, pero es que cuando nos han contado todo esto, la verdad es que me ha parecido tremendamente interesante (y de las pocas estructuras/abstracciones matemáticas que me han parecido genuinamente útiles).