La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

El Quijote de Markov

Posted by Carlos en noviembre 9, 2006

Sí, el Markov al que me refiero es el matemático ruso cuyo trabajo dio nombre a las celebérrimas cadenas de Markov, y no, que yo sepa no se le conoce afición a la andante caballería, a pesar de lo cual, su contribución a la Humanidad es digna no sé si de un Amadís de Gaula o de un Tirante el Blanco. Ocurre que las cadenas de Markov son sumamente útiles para modelar sistemas en física, investigación operativa, o biología. Sin ir más lejos, el PageRank de Google se basa en un modelo de Markov. Más aún, todo el campo de la teoría de la información nace a partir de un histórico paper de Shannon en el que usa las cadenas de Markov para dar una noción de entropía. Precisamente, el sistema que eligió Shannon para ilustrar estas nociones fue el idioma inglés, y cómo diversas cadenas de Markov proporcionaban aproximaciones cada vez mejores al mismo.

Viene todo esto a cuento de que en el sitio web del Proyecto Gutenberg está disponible la primera parte del Quijote (en texto simple). En Microsiervos han calculado a partir de este texto diversos datos, tales como el número total de palabras distintas, las palabras más frecuentes, etc. Como las estadísticas univariadas a mí no me dicen mucho, he pensado que quizás modelarlo como una cadena de Markov sea más interesante. Es fácil, sólo hay que usar las palabras como estados, y analizar el texto para crear la matriz de transición de primer orden (habiendo más de 15,000 palabras distintas, mucha memoria haría falta para ir a una matriz de segundo orden). Una vez definido el sistema, le damos una palabra inicial y ¡listo! Este es un posible resultado (hay que tener en cuenta que el sistema es estocástico), partiendo de la palabra “Sancho”:

“Sancho se puede llevar consigo la amistad de la tomaré yo el cuerpo y dos libros sea al rucio. Despertaron algo mohíno: -Ni mucho trabajo en quien comunicar conmigo tan bien proveídas, a ella, ni se me ciega y éste podéis encajar las quiso escribir con el rostro y peregrina, júzguenlo vuestros males, ¿quién más ligeros y deste nuevo a dar consigo me hiera, siquiera algún castillo de muy bien en la casamos; que ha sido de todo lo pienso ser, y antiguos filósofos, que me trasluce que me has de mi vida que es mejor la mano armada turquesca, …”

Parecerá caótico, pero lo sorprendente es que con tantos grados de libertad como tiene este sistema salgan algunas frases con sentido. Y es que Don Miguel tenía arte para juntar las palabras, incluso a nivel macroscópico.

Anuncios

12 comentarios to “El Quijote de Markov”

  1. Alvy said

    ¡Vaya! parece que nos hemos leído la mente porque precisamente estaba ahora jugando con eso (gracias por recordarme que se llaman Cadenas de Markov porque no me acordaba). A mi me han salido estas (empezando por “El”):

    A. “El cura la fuerza a la luna y la cintura arriba, cada plana y pluma en hojas destos señores caballeros pegan, traidor, según vosotros, llamado Agi Morato, dijo don Quijote, es tiempo que, cuéntamelo todo he contado este mi señora Emperatriz, y yo le mandaba.”

    B. “El ventero tenía Leonela, gloria suya ser rey que pudo pensar que he estado suspenso, besándola mil pesos ensayados, si no se pasaban de don Fernando, la caballería andante, finalmente, haciendo penitencia, puesta al cielo y coselete, que, embrazando su padre dijo don Quijote.”

    C. “El río Tajo, tengo la dé al trabajo que el claustro hablando con las humanas voluntades, viéndose tratar con tan valeroso Pentapolín del Arremangado Brazo, sin empresa hasta las batallas que daba por donde le pudo, esculpirse en su padre nos saltearon son mujercillas simples y en dos cosas todas de Montalbán.”

    Son graciosas las partes que salen con cierto sentido, incluyendo el “dijo don Quijote”… Curiosamente otras pruebas que he hecho con otros textos, de distintos temas y longitudes (monotemáticos o multitemáticos, entre 1.000 y 100.000 palabras) me dan resultados un poco raros: algunos son textos bastante inteligibles, en otros entra en una especie de “bucle” con ciertas palabras pocas frecuentes y es difícil sacarle de ahí (aunque suele salir solo, pero genera textos bastante tontos).
    Seguiré probando con otros textos. También me intriga qué capacidad haría falta para hacerlo de segundo con grupos de dos palabras. Probablemente el truco sería no almacenarlo todo sino ir consultando poco a poco en función de lo que vaya saliendo, aunque sea más ineficiente.

  2. Ivan said

    Hace un tiempo Marcos Donnantuoni hizo un programa llamado Babel que produce texto aleatorio a partir de un texto dado, bajo una idea similar a la que conversan aquí. Tiene además la opción de trabajar con caracteres (en lugar de palabras completas) con lo que pueden surgir palabras inexistentes que «suenan» a castellano. (Aquí un ejemplo de esas palabras inventadas.)

  3. JJ said

    Estás hecho un artista… ¿y el programilla, lo tienes por ahí?

  4. Carlos said

    Alvy: La verdad es que es realmente increíble cómo se pueden modelar sistemas realmente complejos con herramientas matemáticas tan simples. Las cadenas de Markov son una de ellas, pero también están por ejemplo los autómatas celulares.

    Es interesante lo que comentas de que no se consiguen cosas con tanto sentido en otro tipo de textos. En los textos técnicos puede ser más o menos de esperar, ya que hay palabras poco frecuentes (hay por ahí alguna herramienta para la generación automática de artículos científicos, pero igual emplea algún tipo de gramática, en lugar de una cadena de Markov). Si en otro tipo de textos narrativos no se cumple, diría algo a favor del Quijote.

    Sobre cómo hacer la matriz de 2do orden, quizás después de todo no haga falta tanta memoria si se almacenan las matrices de manera dispersa. Si la densidad de posiciones no nulas de la matriz NxN de 1er orden es p, habrá en total pN^2 combinaciones de dos palabras, y pN palabras en promedio detras de una dada. Eso quiere decir que en total hará falta almacenar un promedio de p^2N^3 posiciones en la matriz de 2do orden. Si p es pequeña, puede que sea algo abordable (varios cientos de megas quizás).

  5. Carlos said

    Iván: sí, es curioso cóm pueden conseguirse palabras que suenan a un cierto idioma. Algunos de los ejemplos que figuran ahí son muy buenos, y pienso adoptar alguno de ellos (ignipotético: dícese de lo que es ignoto e hipotético. 😉 ). Eso sí, campurria no es inventada. Todos sabemos que es el pueblo de origen de las galletas campurrianas

  6. Carlos said

    JJ: No estarás pensando en escribir una novela por la vía rápida, ¿no? 😛

  7. JJ said

    El Pagerank se basa en modelos de Markov?
    En cuanto al modelo, quizás la “precisión” está relacionada con la estructura reticular de las frases. Si hay muchas palabras relacionadas con una dada, y en una proporción similar, la estructura será aleatoria; sin embargo, la estructura será más de una ley de potencias en esos casos.
    Creo que hay herramientas de análisis de discurso que te hacen ese tipo de cosas.

  8. fractus said

    El modelo de Markov

    by Mario Guido Pérez

    Existen diferentes fenómenos, muchos de ellos en el campo social, que presentan una evolución temporal tal que permite modelarlos según un proceso de Markov.
    Un proceso de Markov es una serie de experimentos en que cada uno tiene m posibles resultados, E1, E2…..Em, y la probabilidad de cada resultado depende exclusivamente del que se haya obtenido en los experimentos previos.
    Por ejemplo: si en el mercado hay tres marcas de detergentes, cada una de las cuales tiene una cierta porción de dicho mercado en la semana 1, la semana siguiente la distribución puede cambiar dependiendo de las decisiones del consumidor (seguir con la misma marca o cambiar por otra), y esta decisión depende mucho de la última compra. Muchas otras situaciones presentan este patrón de comportamiento: los valores de las acciones de la bolsa día a día, la distribución de la población entre diferentes regiones año a año etc.
    Matemáticamente, un proceso de Markov se modela mediante una matriz de transición.
    Esta no es más que una matriz de probabilidades, donde cada elemento pij representa la probabilidad condicional de que el sistema pase de un estado actual i al siguiente estado j.
    La resolución matemática tradicional es tediosa, puesto que si se quiere ver la evolución a lo largo de un cierto número de períodos, será necesario repetir operaciones matriciales tantas veces como períodos se quiera analizar.
    Se ha aplicado una resolución utilizando las posibilidades que brinda la dinámica de sistemas, que además permite visualizar mejor el fenómeno, e incluir otros elementos adicionales al fenómeno en estudio.

    EL MODELO

    El modelo supone cuatro regiones dentro de una cierta zona en estudio, Norte, Sur, Este y Oeste, entre las cuales se producen migraciones cruzadas, habiéndose estudiado para cada región la probabilidad característica de que una persona permanezca en el lugar o se traslade a uno de los otros tres. Estas probabilidades se resumen en una Matriz de probabilidades de transición, donde cada elemento representa la probabilidad de que un poblador de una región pase a otra: así por ejemplo, PNS indica la probabilidad de que un poblador del Norte se mude al Sur. Puede verse que los elementos de la diagonal, indican las probabilidades de que permanezcan en la región de origen.
    Cada nivel, Norte, Sur, Este y Oeste,disminuye según los flujos a otras regiones, y crece en base a los pobladores que recibe.
    El modelo exhibe un comportamiento típico, puesto que a medida que avanza el tiempo tiende a un estado de equilibrio, en el cual las variaciones de población de cada región son casi nulas.
    Adaptando los nombres de las variables, y extendiendo o disminuyendo del número de niveles y la matriz de transición, el modelo es aplicable a muy diversas situaciones.
    ——————-

    No se si se degrade la cuestion en un tono más capitalista. Por el contrario le felicito por el articulo… 🙂

  9. Carlos said

    JJ, según dice la wikipedia, el PageRank de una página refleja la probabilidad de que un internauta aleatorio aterrice en ella siguiendo un enlace cualquiera. El análogo sería una cadena de Markov en la que los estados son las páginas, las transiciones son los enlaces, y las probabilidades asociadas son uniformes.

    Es cierto lo que comentas sobre la precisión del modelo. Hay palabras como “Don” que con alta probabilidd son seguidas de “Quijote”. Otras sin embargo como “y” o “de” pueden ir seguidas de casi cualquier cosa. Siendo El Quijote un texto puramente narrativo y bastante extenso, y siendo Cervantes un escritor con un vocabulario amplio, es razonable pensar que el modelo contiene una buena muestra del lenguaje. Se observarán las leyes de potencias típicas, y será factible encontrar cosas con sentido. En un artículo técnico es posble que el modelo esté degenerado, con muchas palabras infrecuentes, y anomalías estadísticas de diferente tipo (la cola de la distribución no es que sea pesada, sino que probablemente sea de diplodocus).

  10. Débora said

    Gutenberg esta mal escrito, es Gutemberg.

  11. Carlos said

    Gracias por el comentario, Débora. Puedes consultar aquí y aquí por ejemplo.

  12. Hego said

    Es realmente sorprendente lo que ustedes cuentan, en la escuela me piden que haga un generador de palabras aleatorias pero yo ocupo letra por letras (espero que lo q salga sea algo con cierto parecido al español, jajajaja) y me baso en la probabilidad condicional de que una letra salga dado que anteriormente hay otra, este analisis lo estoy haciendo de un cuento infantil, y pues luego les mando lo que me salga, igual y escribe mejor que yo, jajajaja

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: