31/5/13

Generación de textos por cadenas de Markov







Una forma de generar texto automáticamente y que “parezca” suficientemente inteligible y razonable se basa en aplicar el concepto matemático de las cadenas de Markov.
Sucesión
Es bien conocido el concepto matemático de sucesión. Una sucesión es una lista ordenada de objetos, cada uno de los cuales se denomina término, elemento o miembro. Al número de elementos ordenados (que pueden ser finitos o infinitos) se le denomina como longitud de la sucesión. Es importante señalar que el orden es relevante. Podemos decir también que una sucesión es una función aplicada sobre un conjunto. Normalmente, este orden de los elementos de la sucesión viene creado por una regla interna que los ordena de una determinada manera.
Por ejemplo, si tenemos el conjunto de los números naturales (0,1,2,3,4,5,6,7...) la sucesión de los números pares sería la resultante de aplicar la regla de avanzar de 2 en 2, desechando los elementos intermedios (0,2,4,6...). O la sucesión de Fibonnaci se calcula con la regla de que un elemento es suma de los dos anteriores. Así, si partimos del 0 y el 1, el siguiente sería su suma 1; el siguiente la suma de 1 y 1, es decir 2; el siguiente la suma de 1 y 2, es decir 3; y así sucesivamente: (0,1,1, 2,3,5,8,13,...).
Las sucesiones no tienen por qué ser sólo aritméticas. Por ejemplo, podríamos hablar de una sucesión de meses (enero, febrero, marzo,....) o podríamos crear una sucesión de meses aplicando la regla de que tengan sólo 30 días (abril, junio, septiembre, noviembre), etc.


Procesos estocáticos

¿Qué ocurre si cada elemento del conjunto es no ya un dato o un concepto o un valor fijo, sino una variable? Imaginemos que en vez de (1,2,3,...) tuviéramos (x1, x2, x3,...) donde cada variable Xi pudiera ser el resultado de aplicar una fórmula determinada (por ejemplo, Xi=X i-1*2+ Xi-4). Seguiríamos pudiendo aplicar el concepto de sucesión igualmente.
Pero, en muchos casos, esas variables son aleatorias (estocásticas). Por ejemplo, la sucesión de la temperatura máxima medida en el centro de Madrid durante un año, comenzando por el 1 de enero (grados centígrados): ( -2, 0, 1, 3, 4, 3, 5, 6, 2, 2, 0, -3, 0, 1,...) no sigue ninguna regla. O bien el valor de las acciones de cierta compañía que cotiza en bolsa, en euros (10, 10.5, 11, 11, 10.8, 10.7, 10.93,...) fluctúa aleatoriamente.

Llegamos, así, al concepto de proceso estocástico que es fundamental para posteriormente entender las cadenas de Markov.
Simplificando, un proceso estocástico es un conjunto de variables aleatorias {Xt, con t ∈ T}, indexadas por otro conjunto T y definidas en algún estado de probabilidad.
En muchas ocasiones, el conjunto de indexación es el tiempo (conjunto T de, por ejemplo minutos t1, t2, ... tn), de modo que las variables se definen para cada instante de tiempo t, obteniendo así una variable aleatoria distinta  para cada momento,  representada por Xt. De este modo, un proceso estocástico puede interpretarse como una sucesión de variables aleatorias cuyas características pueden variar a lo largo del tiempo.
Por ejemplo, en el ejemplo anterior mencionado, las variables  son las temperaturas de cada día y estas se ordenan en función del conjunto de los días del año. Estas variables, estas temperaturas, son aleatorias y no podemos predecir su valor. O, en el otro ejemplo, de la bolsa de valores, las variables son el valor de las acciones de la empresa ordenadas en función del minuto en que se miden a lo largo de la sesión en el parqué.
Continuemos ampliando el concepto.
Tenemos ya una sucesión de variables aleatorias. ¿Pero son totalmente incontrolables e impredecibles? Si la temperatura del día 5 de enero en Madrid ha sido de 4ºC y la del día 6 ha sido de 3ºC, ¿sería razonable pensar que durante el día 7 se alcanzarán los 35ºC como en verano? ¿O los -23ºC como en Helsinki? Se intuye que no, se intuye que la temperatura del día 7 estará “probablemente” en el entorno de 3º, 4º, 5º ,6ºC ya que sabemos que no se producen cambios tan bruscos. Lo mismo puede decirse del caso de las acciones bursátiles donde, excepto un caos súbito económico, un crack en toda regla, el valor de la acción evolucionará suavemente.
Por tanto, para cada una de la variables de la sucesión (la temperatura del día, el valor de la acción,...) podremos establecer “una regla de probabilidad” de tipo de “si la temperatura de los dos días anteriores han estado entre 0º y 5ºC, hay una probabilidad del 50% de que al día siguiente la temperatura se repita”. 
La sucesión pasa de ser una distribución de puntos discretos a ser una distribución de probabilidades.
 
Resumiendo, una sucesión de observaciones X1, X2, . . . se denomina proceso estocástico si los valores de estas observaciones no se pueden predecir exactamente pero se pueden especificar las probabilidades para los distintos valores posibles en cualquier instante de tiempo del modo siguiente:
X1: variable que define el estado inicial del proceso
Xn: variable que define el estado del proceso en el instante de tiempo n
Para cada posible valor del estado inicial s1 y para cada uno de los sucesivos valores son de los estados Xn, n = 2, 3, . . ., especificamos: P (X n+1 = s n+1 | X1 = s1, X2 = s2, . . . , Xn = sn )
A los posibles valores que puede tomar la variable aleatoria se les denomina  estados, y es posible tener un espacio de estados discreto o un espacio de estados continuo. Asimismo, la variable tiempo puede ser de tipo discreto (segundo, día, año, ...) o de tipo continuo (cualquier instante, medición continua). Podríamos, por tanto, clasificar los procesos estocásticos en función de cómo sean las variables aleatorias y el conjunto de subíndices:
• Si el conjunto T es continuo, por ejemplo el conjunto de los números reales, diremos que Xt es un proceso estocástico de parámetro continuo.
• Si por el contrario T es discreto, por ejemplo el conjunto de los números naturales, diremos que nos encontramos frente a un proceso estocástico de parámetro discreto.
• Si para cada instante t la variable aleatoria Xt es de tipo continuo, diremos que el proceso estocástico es de estado continuo.
• Si para cada instante t la variable aleatoria Xt es de tipo discreto, diremos que el proceso estocástico es de estado discreto.
Puede interpretarse un proceso estocástico como la evolución en el tiempo de algún fenómeno cuya dinámica se rige por el azar.
Numerosas facetas de la actividad humana y hechos de la naturaleza pueden modelarse con procesos estocásticos: movimientos sísmicos, señales biomédicas, transmisión de comunicaciones,  evolución demográfica, evolución de machas solares, ciclos meteorológicos, evolución del grado de congelación del mar ártico, tiempos de espera, índices de accidentes, evolución económica, velocidad de un vehículo, fallos de la maquinaria, evolución de la temperatura de un horno, índice de nubosidad, evolución del sonido de una voz, presión hidráulica en una conducción, posición de un cuerpo en movimiento, elección de un cliente entre diferentes marcas de un producto, producción diaria de un bien, estimación de votos electorales, flujos fluviales, etc., etc.
 
Cadenas de Markov
En los procesos estocásticos de estados discretos puede ocurrir, como caso particular, que la probabilidad del estado siguiente X n+1 depende sólo del estado anterior Xn y no de todos los estados anteriores. Por así decirlo, se trata de un proceso sin memoria en donde la historia pasada es irrelevante. A esta característica se le denomina Propiedad de Markov  y a aquellas cadenas que cumplen tal propiedad se las denomina Cadenas de Markov.
Desde un punto de vista matemático, podemos decir que:
·         para un proceso estocástico con una secuencia de variables que indica el valor del proceso en instantes sucesivos representado como:
{X0 = x0,X1 = x1, ...,X n−1 = x n−1,Xn = xn}
·        en la que cada variable Xi, i = 0, ..., n, tiene una distribución de probabilidades que, en general, es distinta de las otras variables.
·        Si en el instante [ n – 1] se está en el estado x n−1, ¿con qué probabilidad se estará en el estado xn en el instante siguiente n?. Esta probabilidad es:
P (Xn = xn/X n−1 = x n−1)
A esta probabilidad condicionada entre un estado y el anterior se le denomina probabilidad de transición o de cambio de estado. A las probabilidades del tipo P (Xn = xn) se les denomina probabilidades de ocupación de estado. Se observa que el proceso no depende de la historia pasada sino sólo del instante anterior.
Por tanto, matemáticamente, la propiedad de Markov se da cuando toda la historia pasada del proceso puede resumirse en la posición actual que ocupa el mismo, de modo que la probabilidad de cambiar al siguiente estado es:
P (Xn = xn/X0 = x0,X1 = x1, ...,X n−1 = x n−1) = P (Xn = xn/X n−1 = x n−1)
Que, también, puede indicarse como:
(Xn = j/X n−1 = i) = pij(n)  
 
Matrices de transición
Las transiciones entre los diferentes estados pueden representarse mediante matrices. Imaginemos, por ejemplo, un laberinto con sus habitaciones numeradas del 1 al 9.
 
 
Un explorador que esté en una casilla determinada puede elegir hacia dónde dirigirse y lo que haya caminado anteriormente ya no tiene ninguna importancia, su decisión tan sólo depende de donde se halla en este momento (propiedad de Markov).
Imaginemos que la probabilidad de que tome un camino u otro es igual para todas las opciones posibles en ese instante. En tal caso, si nuestro viajero está en la casilla 5, tendremos que puede dirigirse a las casillas 2, 4, 6 y 8 y la probabilidad de que vaya a una u otra será igual. Como en esa casilla hay 4 opciones, la probabilidad de cada una será de 1/4 (25%). Es decir, para la casilla 5 tenemos que:
 
 
Podríamos repetir este cálculo para cada casilla, cada habitación, y representar los resultados en forma de matriz que llamaremos matriz de transición.
 
 
 
Por ejemplo, la probabilidad de que el viajero que está en la casilla 3 pase a la casilla 6 es la mostrada en el elemento (fila 3, columna 6), o sea 1/2, cosa lógica si vemos que de esa casilla 3 puede irse a la 2 o a la 6, o sea dos posibilidades.
La probabilidad de caminar desde la casilla 2 a la 9 es 0 porque, obviamente, no están conectadas.
La probabilidad de que el viajero siga la trayectoria 1-2-5-8-9 sería:
P 12 . P 25 . P 58 .P89
Obsérvese que la matriz es cuadrada y que la suma de probabilidades de cada fila es siempre 1.
 
Gráficas de las matrices de transición
Sea una matriz de transición del tipo:
 
 
 
Esta matriz puede representarse por un grafo del tipo:
 
 
 
Se ve que en los círculos se representan los 4 estados posibles (0,1,2,3). En la matriz vemos, por ejemplo, que la probabilidad de pasar del estado 0 al 1 es de ¼. En el grafo esto se representa con una flecha y dicha probabilidad. Del estado 2 al 3 es 1/3 e igualmente se ve la flecha entre el nodo 2 y el nodo 3 con esa probabilidad. Así, sucesivamente.
 
Aplicación de las cadenas de Markov a la generación de textos
¿Y qué tiene que ver todo esto con la generación de textos?
Aunque crear un algoritmo que genere texto de calidad es muy complicado y estamos lejos de tener procedimientos que lo permitan, sí se observa que podemos imitar –siempre con calidad baja- la forma de escribir de algún escritor.
La técnica se fundamenta en la realidad práctica  de que casi todos los escritores tienen una forma particular de redactar, utilizan un vocabulario que se repite y crean frases con esquemas más o menos similares. Existen pocos escritores que cambien radicalmente su forma de narrar entre obras o entre capítulos. Por así decirlo, las obras de un escritor cualquiera son “reconocibles” porque incorporan esquemas de escritura (“patterns”). Aun cuando no conozcamos los datos de una novela, podemos intuir que es de un autor particular. Quizá no conozcamos la obra pero podemos ser capaces de decir  “parece de Benavente, o de Calderón o de Rubén Darío”. Lo mismo ocurre en música. Podemos escuchar una sinfonía que no conocemos pero seguramente seremos capaces de decir “esto suena a Mozart, o a Mahler, o a Chopin”.
¿Y por qué ocurre este fenómeno? Sencillamente porque todo escritor tiende a repetirse en la forma en que construye sus frases, en las palabras que usa, en la sintaxis que utiliza.
Si tomamos un texto cualquiera (por ejemplo, las 40.000 palabras de una novela) podemos considerar a esa sucesión de 40.000 palabras como un  proceso estocástico, como una cadena de Markov. Podemos imaginar que la aparición de la palabra “k” depende sólo de la anterior palabra, o de las dos anteriores palabras, o de las tres anteriores palabras, porque el escritor cuando escribe unas palabras “tiende” a continuarlas con sólo otras determinadas palabras, no con cualquiera.
Es importante indicar que para que esta técnica sea efectiva, el volumen de texto que se considera debe ser grande. No sirve con frases cortas, con pocas páginas, porque cualquier escritor- en espacios breves- controla que no haya repeticiones. Pero, cuando hablamos de 40.000 palabras, los modelos de escritura se detectan con cierta sencillez.
No podemos aquí examinar un texto de tal tamaño. Si tuviéramos 30.000 palabras y nos limitáramos exclusivamente a ver cuál puede ser la siguiente palabra, tendríamos una matriz de 30.000 x 30.000 términos, o sea de 900.000.000 de términos, un coloso que sólo con ordenadores puede tratarse.
Para ver, no obstante, cómo trabajaríamos, utilizaremos un texto muy corto y repetitivo a propósito:
El hombre armado miró enojado a su alrededor. Juan miró nervioso al hombre enjuto que rebuscaba entre las cajas, y ciertamente le miró enojado por la situación. Miró a su alrededor  y le vio tan enojado y nervioso que Juan se asustó.
Elegimos como significativos los siguientes elementos: ( Juan, miró, hombre, armado, enojado, a su alrededor, y nervioso, se asustó, por la situación, enjuto). La matriz 10 x 10 se construirá analizando para cada palabra cuáles son las que le siguen. Por ejemplo, a “miró” le siguen “enojado” (2 veces), “nervioso”, “a su alrededor”. Es decir hay 4 casos donde 2 de ellos (50%=0.5) apuntan a “enojado” y otros dos casos (25% cada uno) a los otros dos términos

 
 
Tomemos ahora un cuento de Camilo José Cela, todavía muy poco extenso, pero en el que ya vemos repeticiones “naturales”:
“Chindo” es un perrillo de sangre ruin y de nobles sentimientos. Es rabón y tiene la piel sin lustre, corta la alzada, flácidas las orejas. “Chindo” es un perro hospiciano y sentimental, arbitrario y cariñoso, pícaro a la fuerza, errabundo y amable, como los grises gorriones de la ciudad. “Chindo” tiene el aire, entre alegre e inconsciente, de los niños pobres, de los niños que vagan sin rumbo fijo, mirando para el suelo en busca de la peseta que alguien, seguramente, habrá perdido ya.
“Chindo”, como todas las criaturas del Señor, vive de lo que cae del cielo, que a veces es un mendrugo de pan, en ocasiones una piltrafa de carne, de cuando en cuando un olvidado resto de salchichón, y siempre, gracias a Dios, una sonrisa que sólo “Chindo” ve.
“Chindo”, con la conciencia tranquila y el mirar adolescente, es perro entendido en hombres ciegos, sabio en las artes difíciles del lazarillo, compañero leal en la desgracia y en la obscuridad, en las tinieblas y en el andar sin fin, sin objeto y con resignación.
El primer amo de “Chindo”, siendo “Chindo” un cachorro, fue un coplero barbudo y sin ojos, andariego y decidor, que se llamaba Josep, y era, según decía, del caserío de Soley Avall, en San Juan de las Abadesas y a orillas de un río Ter niño todavía.
Josep, con su porte de capitán en desgracia, se pasó la vida cantando por el Ampurdán y la Cerdaña, con su voz de barítono montaraz, un romance andarín que empezaba diciendo:
Si t´agrada córrer mon,
algun dia, sense pressa,
emprèn la llarga travessa
de Ribes a Camprodon,
passant per Caralps i Núria,
per Nou Creus, per Ull de Ter
i Setcases, el primer
llogaret de la planúria.
“Chindo”, al lado de Josep, conoció el mundo de las montañas y del agua que cae rodando por las peñas abajo, rugidora como el diablo preso de las zarzas y fría como la mano de las vírgenes muertas. “Chindo”, sin apartarse de su amo mendigo y trotamundos, supo del sol y de la lluvia, aprendió el canto de las alondras y del minúsculo aguzanieves, se instruyó en las artes del verso y de la orientación, y vivió feliz durante toda su juventud.
Pero un día… Como en fábulas desgraciadas, un día Josep, que era ya muy viejo, se quedó dormido y ya no se despertó más. Fue en la Font de Sant Gil, la que está sota un capelló gentil.
“Chindo” aulló con el dolor de los perros sin amo ciego a quien guardar, y los montes le devolvieron su frío y desconsolado aullido. A la mañana siguiente, unos hombres se llevaron el cadáver de Josep encima de un burro manso y de color ceniza, y “Chindo”, a quien nadie miró, lloró su soledad en medio del campo, la historia -la eterna historia de los dos amigos Josep y “Chindo”- a sus espaldas y por delante, como en la mar abierta, un camino ancho y misterioso.
¿Cuánto tiempo vagó “Chindo”, el perro solitario, desde la Seo a Figueras, sin amo a quien servir, ni amigo a quien escuchar, ni ciego a quien pasar los puentes como un ángel? “Chindo”contaba el tránsito de las estaciones en el reloj de los árboles y se veía envejecer -¡once años ya!- sin que Dios le diese la compañía que buscaba.
Probó a vivir entre los hombres con ojos en la cara, pero pronto adivinó que los hombres con ojos en la cara miraban de través, siniestramente, y no tenían sosiego en le mirar del alma. Probó a deambular, como un perro atorrante y sin principios, por las plazuelas y por las callejas de los pueblos grandes -de los pueblos con un registrador, dos boticarios y siete carnicerías- y al paso vio que, en los pueblos grandes, cien perros se disputaban a dentelladas el desmedrado hueso de la caridad. Probó a echarse al monte, como un bandolero de los tiempos antiguos, como un José María el Tempranillo, a pie y en forma de perro, pero el monte le acuñó en su miedo, la primera noche, y lo devolvió al caserío con los sustos pegados al espinazo, como caricias que no se olvidan.
“Chindo”, con gazuza y sin consuelo, se sentó al borde del camino a esperar que la marcha del mundo lo empujase adonde quisiera, y, como estaba cansado, se quedó dormido al pie de un majuelo lleno de bolitas rojas y brillantes como si fueran de cristal.
Por un sendero pintado de color azul bajaban tres niñas ciegas con la cabeza adornada con la pálida flor del peral. Una niña se llamaba María, la otra Nuria y la otra Montserrat. Como era el verano y el sol templaba el aire de respirar, las niñas ciegas vestían trajes de seda, muy endomingados, y cantaban canciones con una vocecilla amable y de cascabel.
“Chindo”, en cuanto las vio venir, quiso despertarse, para decirles:
-Gentiles señoritas, ¿quieren que vaya con ustedes para enseñarles dónde hay un escalón, o dónde empieza el río, o dónde está la flor que adornará sus cabezas? Me llamo “Chindo”, estoy sin trabajo y, a cambio de mis artes, no pido más que un poco de conversación.
“Chindo” hubiera hablado como un poeta de la Edad Media. Pero “Chindo” sintió un frío repentino. Las tres niñas ciegas que bajaban por un sendero pintado de azul se fueron borrando tras una nube que cubría toda la tierra.
“Chindo” ya no sintió frío. Creyó volar, como un leve vilano, y oyó una voz amiga que cantaba:
Si t´agrada córrer mon,
algun dia, sense pressa…
“Chindo”, el perrillo de sangre ruin y de nobles sentimientos, estaba muerto al pie del majuelo de rojas y brillantes bolitas que parecían de cristal.
Alguien oyó sonar por el cielo las ingenuas trompetas de los ángeles más jóvenes.

 
Si tomamos este texto y lo estudiamos con cualquier analizador  de textos (por ejemplo, este en línea
http://textalyser.net/ ), el programa nos da las frecuencias con las que aparece cada palabra individualmente. He aquí un extracto:
Frequency and top words :
 

Word

Occurrences

Frequency

Rank

que

23

3.4%

1

“chindo”

20

3%

2

las

18

2.7%

3

los

16

2.4%

4

como

16

2.4%

4

del

14

2.1%

5

con

14

2.1%

5

sin

12

1.8%

6

por

8

1.2%

7

una

6

0.9%

8

josep

6

0.9%

8

perro

5

0.7%

9

quien

5

0.7%

9

pero

4

0.6%

10

amo

4

0.6%

10

hombres

4

0.6%

10

frío

3

0.4%

11

ciegas

3

0.4%

11

niñas

3

0.4%

11

para

3

0.4%

11

per

3

0.4%

11

era

3

0.4%

11

pie

3

0.4%

11

artes

3

0.4%

11

más

3

0.4%

11

ojos

3

0.4%

11

dónde

3

0.4%

11

probó

3

0.4%

11

pueblos

3

0.4%

11

otra

2

0.3%

12

azul

2

0.3%

12

pintado

2

0.3%

12
 
Si exceptuamos las preposiciones, artículos, etc. y nos centramos en sustantivos y verbos podemos generar la cadena de Markov.
Así, para la palabra (elemento) “perro” vemos que le suceden las palabras “hospiciano”, “entendido”, “pero el monte”, “solitario”, “atorrante”. Como no se repiten, podemos otorgar una probabilidad de 20% a cada una de las 5.
Para la palabra “hombres” las que siguen son “ciegos”, “se llevaron”, “con ojos”, “con ojos”. Podemos decir que la probabilidad de que a hombres le siga “con ojos” es del 50% mientras que las otras dos continuaciones tienen cada una un valor del 25%.<>
 Para la palabra “pueblos”, las continuaciones son “grandes” (x2) o “con un registrador”. Podemos aplicar una probabilidad del 66% a “grandes” y 33% a la otra opción.
Este proceso se puede repetir de manera masiva. Primero tomando continuaciones tras una única palabra (como hemos hecho arriba), luego continuaciones a dos palabras juntas o a tres, etc. Y, por supuesto, en un análisis genérico se usan también los artículos, preposiciones, etc., incluso los signos de puntuación.
 

 
Algoritmo
Un algoritmo muy sencillo, muy básico, que crearía textos que “parecieran” de un autor determinado podría ser del tipo que se ve a continuación. Hay que decir que “parecer” no es “ser”, que incluso pueden generarse frases sin sentido pero que parecen, a primera vista, correctas. Para que el tiempo de cálculo no se dispare exponencialmente, hacemos el análisis restringiéndolo a una sola palabra seguida de otra. También hay que señalar que se trata, ahora, de entender los conceptos, no de hacer que el algoritmo sea elegante y/o rápido.
1.- Introducir un texto largo en el sistema, en una variable de texto. Debe ser un texto suficientemente largo. Esta introducción puede hacerse, por ejemplo, “pegándolo” en una caja de lectura de datos.
2.- Detectar todas y cada una de la palabras distintas de ese texto y adscribirlas a una variable del tipo array. Por ejemplo a$.
3.- Para cada palabra, ver todas las posibles palabras distintas que la siguen y apuntar la frecuencia con que aparecen en una variable de varias dimensiones del tipo b$(palabrainicio)= {[palabra-1, frecuencia-1, palabra-2, frecuencia-2..., palabra-n, frecuencia-n], [....], [....],....}
4.- Reordenar esta variable en su segunda dimensión por frecuencias (es decir,  frecuencia-1 mayor que frecuencia-2 mayor que frecuencia-3 mayor que ....).
4.- Introducir en el sistema una semilla de arranque (una palabra o, si es un frase, la palabra importante será sólo  la última). Por ejemplo  textinicial$=”Un hombre”.
5.- Ver cuántas palabras siguientes posibles tiene esa semilla. Llamamos a este número N. Si una palabra tiene una frecuencia  distinta de 1, contarla como tantas veces como se repita. Es decir, si por ejemplo la palabra “mesa” aparece 6 veces, cuanta por 6 a la hora de calcular N.
7.- Generar un número aleatorio entre 1 y N que llamaremos “t”.
8.- Elegir la palabra siguiente de entre las de b$(semilla, palabras siguientes) tal que “t” sea el primer mayor que la suma de frecuencias anteriores empezando por cero.
Ejemplo:
Si b$(mesa)=(blanca, 6, alta, 3, sucia, 2, verde, 1, solitaria,1) y, por tanto, N=13:
y hemos generado un t=10, la palabra elegida será “sucia” (10 mayor que 6+3). Si t=5, elegiríamos “blanca” ya que (5 mayor que 0). Si t=8, elegiríamos “alta” porque (8 mayor que 5). Si t=12 elegiríamos “verde” porque (12 mayor que 6+3+2), etc.
9.- La nueva palabra que acabamos de hallar es la nueva semilla. Repetimos el proceso a partir del paso 6 tantas veces como queramos.
 
Aplicaciones ya realizadas
Este artículo tiene como finalidad explicar sólo los fundamentos muy básicos de la generación de textos utilizando cadenas de Markov. Hay muchos autores que han creado algoritmos al respecto y que los ha puesto gentilmente en red para el uso público. Son, además, programas más elaborados en donde pueden usarse cadenas de Markov de mayor orden que la unidad.
Uno es, por ejemplo, el creado por Brian W. Kernighan and Rob Pike y que puede disfrutarse en este enlace: http://www.owlnet.rice.edu/~cz1/prog/markov/markov.html y que estaba referenciado y explicado en el libro The Practice of Programming
Permite elegir el orden de la cadena y cuántas palabras queremos generar con el ciclo interactivo.  Está programado en javascript (+ CSS) y el código está a disposición de los usuarios como rutina markov.js que puede descargarse de esa misma página para su estudio. Una rutina muy bien concebida, muy compacta y muy eficiente.
 
 
Probémoslo con el texto anterior de Cela. Eligiendo un orden 2 y 500 palabras de salida, el resultado es:
"Chindo” es un mendrugo de pan, en ocasiones una piltrafa de carne, de cuando en cuando un olvidado resto de salchichón, y siempre, gracias a Dios, una sonrisa que sólo “Chindo” ve. “Chindo”, con gazuza y sin ojos, andariego y decidor, que se llamaba Josep, y era, según decía, del caserío de Soley Avall, en San Juan de las Abadesas y a orillas de un río Ter niño todavía. Josep, con su voz de barítono montaraz, un romance andarín que empezaba diciendo: Si t´agrada córrer mon, algun dia, sense pressa… “Chindo”, el perro solitario, desde la Seo a Figueras, sin amo ciego a quien servir, ni amigo a quien guardar, y los montes le devolvieron su frío y desconsolado aullido. A la mañana siguiente, unos hombres se llevaron el cadáver de Josep encima de un burro manso y de la lluvia, aprendió el canto de las zarzas y fría como la mano de las alondras y del agua que cae del cielo, que a veces es un mendrugo de pan, en ocasiones una piltrafa de carne, de cuando en cuando un olvidado resto de salchichón, y siempre, gracias a Dios, una sonrisa que sólo “Chindo” ve. “Chindo”, con la pálida flor del peral. Una niña se llamaba María, la otra Montserrat. Como era el verano y el mirar adolescente, es perro entendido en hombres ciegos, sabio en las artes difíciles del lazarillo, compañero leal en la desgracia y en la cara, pero pronto adivinó que los hombres con ojos en la cara, pero pronto adivinó que los hombres con ojos en la Font de Sant Gil, la que está sota un capelló gentil. “Chindo” aulló con el dolor de los dos amigos Josep y “Chindo”- a sus espaldas y por delante, como en la obscuridad, en las artes difíciles del lazarillo, compañero leal en la Font de Sant Gil, la que está sota un capelló gentil. “Chindo” aulló con el dolor de los niños que vagan sin rumbo fijo, mirando para el suelo en busca de la orientación, y vivió feliz durante toda su juventud. Pero un día… Como en fábulas desgraciadas, un día Josep, que era ya muy viejo, se quedó dormido al pie de un burro manso y de la Edad Media. Pero “Chindo” sintió un frío repentino. Las tres niñas ciegas con la conciencia tranquila y el sol templaba el aire de respirar, las niñas ciegas con la cabeza adornada con la cabeza adornada con la pálida flor del peral. Una niña se llamaba María, la otra Montserrat. Como era el verano y el mirar adolescente, es perro entendido en hombres ciegos, sabio en las artes del verso y de nobles sentimientos, estaba muerto al pie del majuelo de rojas y brillantes bolitas que parecían de cristal. Alguien oyó sonar por el Ampurdán y la otra Montserrat. Como era el verano y el sol templaba el aire de respirar, las niñas ciegas con la cabeza adornada con la conciencia tranquila y el sol templaba el aire "
Un texto sin sentido que, sin embargo, tiene el mismo estilo que el original y en ocasiones resulta francamente divertido.
Si elegimos orden 4, el texto se reduce a:
“Chindo” es un perrillo de sangre ruin y de nobles sentimientos, estaba muerto al pie del majuelo de rojas y brillantes bolitas que parecían de cristal. Alguien oyó sonar por el cielo las ingenuas trompetas de los ángeles más jóvenes"

Esto es lógico porque es complicado o casi imposible encontrar cadenas tan largas como para crear continuaciones evidentes.
Con orden=1, el texto es menos inteligible:

“Chindo” aulló con la Edad Media. Pero un perro atorrante y de mis artes, no tenían sosiego en la planúria. “Chindo”, el Tempranillo, a veces es perro entendido en ocasiones una sonrisa que está sota un perrillo de Soley Avall, en la cara miraban de Sant Gil, la primera noche, y sentimental, arbitrario y sin ojos, andariego y misterioso. ¿Cuánto tiempo vagó “Chindo”, a veces es un frío repentino. Las tres niñas ciegas vestían trajes de la llarga travessa de mis artes, no tenían sosiego en fábulas desgraciadas, un perro hospiciano y no tenían sosiego en busca de la vida cantando por delante, como estaba cansado, se fueron borrando tras una voz de un día Josep, que a Dios, una voz amiga que Dios le diese la compañía que alguien, seguramente, habrá perdido ya. “Chindo”, sin lustre, corta la planúria. “Chindo”, el Tempranillo, a quien pasar los hombres con ojos en la conciencia tranquila y de bolitas rojas y en la piel sin consuelo, se quedó dormido al borde del majuelo lleno de la primera noche, y de “Chindo”, con una sonrisa que no sintió un río Ter i Núria, per Caralps i Núria, per Nou Creus, per Ull de Soley Avall, en la obscuridad, en los pueblos con ustedes para el perrillo de las callejas de los niños que parecían de las artes difíciles del lazarillo, compañero leal en forma de las alondras y desconsolado aullido. A la ciudad. “Chindo” ya muy endomingados, y por las alondras y del verso y tiene el suelo en medio del cielo, que bajaban tres niñas ciegas que los pueblos con su amo ciego a quien servir, ni ciego a orillas de un perro atorrante y brillantes como en el río, o dónde hay un perro hospiciano y por las vírgenes muertas. “Chindo”, siendo “Chindo” aulló con el andar sin fin, sin apartarse de la llarga travessa de bolitas que cubría toda la otra Montserrat. Como era el andar sin apartarse de los sustos pegados al paso vio que, en la desgracia y sin fin, sin trabajo y, como un perro solitario, desde la Edad Media. Pero un olvidado resto de las callejas de Soley Avall, en ocasiones una sonrisa que era el aire de Ter niño todavía. Josep, con ustedes para decirles: -Gentiles señoritas, ¿quieren que alguien, seguramente, habrá perdido ya. “Chindo”, el verano y la obscuridad, en la orientación, y “Chindo”, al monte, como el mirar adolescente, es un sendero pintado de sangre ruin y la Edad Media. Pero “Chindo” es un poco de nobles sentimientos. Es rabón y no se fueron borrando tras una sonrisa que se fueron borrando tras una piltrafa de Soley Avall, en la marcha del agua que se llamaba María, la ciudad. “Chindo” es un olvidado resto de Sant Gil, la historia -la eterna historia -la eterna historia de la vida cantando por las peñas abajo, rugidora como un perro hospiciano y se veía envejecer -¡once años ya!- sin lustre, corta la que alguien, seguramente, habrá

Conclusiones

Los textos generados aplicando las cadenas de Markov pueden acercarse a textos humanos en la medida en que se utilicen ficheros de gran longitud y se utilicen matrices de probabilidad de gran tamaño. Puede mejorarse el resultado combinando técnicas: por ejemplo, combinando párrafos creados con cadenas de Markov con párrafos construidos manualmente por humanos, párrafos que utilicen moldes o gramática generativa.
 

2 comentarios :

T.H. dijo...

me ha resultado muy interesante. De todos modos, el automatismo que este procedimiento sugiere seguramente nunca tendrá el alma de un escritor real por muy grande que sea el volumen de datos.

Anónimo dijo...

Me ha resultado muy util tu post, ya que estoy desarrollando un Modelo de NPL con capa de Markov oculta.