Code Kata: cadenas de Márkov

El code kata de esta semana trata sobre las cadenas de markov, una herramienta matemática que acecha oculta en cursos de estadística o investigación operativa y que si visitáis la Wikipedia veréis que se utiliza para infinidad de cosas como la redacción de spam.

¿Qué es una cadena Márkov? No es más que un proceso estocástico en el que el último suceso nos aporta todo lo que podemos saber acerca de los siguientes sucesos o, en castellano llano, un generador aleatorio en el que el último resultado determina las probabilidades para el siguiente. Si además es homogéneo, de primer orden y el resto de cosas para no complicarnos demasiado podemos representar la cadena de Márkov como una matriz de n x n en el que P(i,j) nos marca la probabilidad de que j le siga a i.

Los que sigan leyendo esta entrada se preguntarán para qué puede ser útil todo esto y por qué no están escribiendo las memorias de sus prácticas, TFCs, documentación de su proyecto o alguna otra cosa útil o inevitable. Quizá no estéis perdiendo el tiempo, las cadenas de Márkov pueden utilizarse para generar textos de relleno tan incoherentes como los que deberíais estar escribiendo sin el riesgo de que alguien se de cuenta de que habéis copyshiteado media wikipedia. Para ello basta con tomar las palabras y signos de puntuación como los símbolos de salida de la cadena y entrenarla con un corpus de texto inicial (otros documentos o prácticas anteriores). Los resultados son fascinantes y pondré dos ejemplos.

Garkov es una tira cómica que se autogenera con cada visita. Se basa en un catálogo de tiras de Garfield de las que han borrado los textos y una cadena de Márkov que genera el texto. El resultado varía entre surrealista y plausible, podéis probar todo lo que os apetezca.

Garfield + cadenas de Markov = Garkov

El segundo ejemplo ha sido generado con una cadena de primer orden entrenada a partir de algunos documentos antiguos en los que he participado, es difícil juzgar si la causa del sentimiento de irrealidad es debido a la cadena o al corpus para entrenarla.

In this task is responsible for the planned work packages, Definition R it will also Coordinator will be used technical risk are described in the creation of technology for carrying out, to existing know how will is a common state of the two different concern within level of architecture of Lifecycle other cases.

A veces, el resultado puede dar miedo y/o ser poético:

Mashup platforms, family that involve human Embryos?

Code kata: cadenas de Márkov

El bueno de Andrey Markov

Volviendo al code kata, nuestro objetivo consistirá en implementar un generador aleatorio mediante una cadena de Márkov de primer orden (y no volver a tener que escribir relleno a mano).

El primer problema a resolver consistirá en la capacidad de convertir el corpus, en principio uno o varios ficheros de texto plano, en una secuencia de tokens que podrán ser o bien palabras o bien signos de puntuación. El punto y el final de fichero tendrán una función especial, marcarán el fin de la sentencia.

Este primer paso puede ser más o menos elaborado dependiendo del tiempo e interés que se quiera dedicar. En el mejor de los casos se deberían intentar preservar más información del fichero de entrada, como por ejemplo considerar una o varias líneas en blanco como otro fin de sentencia.

El siguiente elemento a resolver será la representación de la cadena, que en teoría sería una matriz cuadrada con todas las palabras de corpus como filas y columnas. Quizás se deba recurrir a alguna técnica para almacenar matrices dispersas...

Opcionalmente se puede considerar la carga y el almacenamiento de cadenas desde ficheros en disco para ahorrarse el proceso de entrenamiento de la cadena.

Finalmente se debe implementar la generación de texto.

Buena suerte y no dudéis en mirar la Wikipedia o rastrear Internet para reunir más información, es parte del ejercicio.