Archive for the 'Cosas que nos enseñan en el doctorado' Category

BorjaNet según Markov

Published
by
Borja Sotomayor
on 1/12/2004
in Cosas que nos enseñan en el doctorado
. 6 Comments

A raiz de lo que expuse en el anterior artículo sobre la Cadenas de Markov, Mario sugirió que Markovizase mi blog para ver que pasaba. Para los que no quieran leerse el anterior artículo, os cuento lo esencial para que le veais la gracia a los textos Markovizados que os voy a enseñar. Yo puedo coger un texto cualquier y, analizar las frecuencias con las que una palabra aparece despues de otra palabra. Por ejemplo, en castellano es probable que después de la palabra “de” tengamos la palabra “la”, pero mucho menos probable tener la palabra “para” despues de “de” (de hecho, en ese caso la probabilidad debería ser cero :-P ). En base a esas probabilidades, puedo generar un modelo llamado una Cadena de Markov. Este modelo, en esencia, encapsula los patrones que se encuentran en el texto y, dado un cuerpo de estudio lo suficientemente grande, los patrones de un idioma concreto. Una vez tenemos el modelo, podemos simularlo y generar textos que se ajustan a los patrones del texto analizado. Vamos, en cierto sentido no es más que una manera que reordenar un texto, pero teniendo presente los patrones del texto original. Los resultados, en general, suelen ser bastante sorprendentes (teniendo en cuenta que es un proceso aleatorio) e incluso divertidos.

Pues bien, utilizando el programa que podeis encontrar en esta web, he generado una Cadena de Markov utilizando todos los artículos de BorjaNet (desde septiembre de 2002). He realizado varias simulaciones, y los resultados son bien curiosos. Antes de nada, os pongo la frase que más me ha calado en una de las simulaciones:

los hombres del renacimiento como Leonardo Da Vinci que estaban versados en las calles de caramelo

Os juro que esa es la frase tal cual me la ha soltado la simulación. Hay que ver los profundos pensamientos que subyacen a mis artículos…

Bueno, y aquí os van unas cuantas simulaciones un poco más completas. La primera está basada en una Cadena de Markov con granularidad de una palabra (es decir, el texto se ha analizado palabra por palabra). Puesto que es dificil extraer patrones utiles con una granularidad tan baja, el texto es bastante incoherente, aunque curiosamente el texto se deja leer (hay bastantes estructuras gramaticales correctas: “Lo que no me han dado”, “que podria haber visto muchos asuntos”, “De hecho, muchos nombres son asediados”)

Lo de textos, pues eso, que más artificial y de Web Services, razón es lo cuelguen en el vuelo tranquilito, bla, le molesta tanto. Eso sí, Alex, ¡no es basicamente en el mismisimo Stallman tiene 254 votos del renacimiento como el yang de doctorado para raritos los estudiantes o si quiera formar parte de horas al igual que dejé el correo (y honda, a la pantalla de mi vida. Lo que no me han dado la vida se cree por la plataforma del colegio. Sin embargo, el proceso de maravilla, y la cocina o 3 (concretamente, los negativos (de la absurda de la altura de mi cabeza, entonaron el botón “Warm” y la segunda página) con (por cierto, no encuentra dónde te restrasas en el Global Grid Computing, y he dicho, ya habia dado cuenta que relato sobre conmutación de esas afirmaciones, pero menos para celebrar mis fuerzas (que podría haber visto muchos asuntos. Pero lo grabó en algo así que terminen las tropas a los ideales propios habitantes. Me ha gustado, a la música a naftalina. Que bien. Yo venía en una parida. Pero es esto”. Yo ya mucho tiempo que tiene que se debe proteger su exito. El estudio pidió claramente una tienda esa. Pregunte a mi quiniela no hay junto al master generalmente no haya por fin han parecido genuinamente interesante ha habido el sistema de los ojos. De hecho, muchos nombres son asediados por supuesto, a uno o menos admitirian que me voy a la conferencia! ¡Yupi!

En la siguiente simulación, la granularidad es de dos palabras. Es decir, si parto del texto “Mi sastre es rico”, los estados de la cadena serían “Mi sastre”, “sastre es” y “es rico”. De esta manera es posible generar textos un poco más coherentes. Destaco en negrita unas cuantas frases curiosas…

Lo de la tesis. En España, cuando haces la defensa, me han traido varias cosas, incluido entrar a las encuestas la ventaja de 3 años al lado de casa. Así que al final no me rayaba mucho porque está en Swift Hall, muy cerca de mi weblog :-) Me enseñaron las partes más destacables de la siesta, una buena actualización al GT3 Programmer’s Tutorial. Un tio de IBM llegó a la vuelta, yo diria que el libro basta con enseñarle a la telefónica, y de las cosas en mi humilde opinión, es el pavo, y siempre dejan entrar un poco de carril de la defensa, me han dicho que está esperando puntualmente en la charla de orientación ha sido una gozada no tener nadie con quien charlar animadamente en lugar de un país’, y en navidades pienso comer toneladas de mierda hasta el final es tan traumatico como lo que me alegro de haber dormido profusamente, decidi dedicar el post a un nivel muy bueno y, si pudiesemos, las aceptaríamos todas. Es muy dificil establecer un orden entre ellas. Llegados a este punto, seguramente pensais lo mismo pero con ocasionales turbulencias leves. Eso no es fruto de una hora de escritura de este frenesí turistico y cinematográfico, ha llegado el router ADSL, un 2Wire HomePortal que parece que un lema más apropiado y menos riesgos se corren. De nuevo, entiendo y respeto que el diseño tal y como ahora se muera Knuth voy a escribir un laaargo día lleno de clusters, supercomputadores, y routers y switches.

En esta simulación en concreto generé bastantes más palabras, pero para no aburriros con la simulación entera, aquí van otras frase curiosas que aparecieron:

estoy dispuesto a tragarme mi orgullo y mis ideales si de paso les pueden colgar por los deberes

al final los informáticos solemos creernos los reyes magos!

POR FIN ha llegado una televisión defectuosa

Finalmente, aquí va el resultado de una simulación con granularidad de tres palabras. Como podeis ver, el texto parece ser más legible que los dos anteriores. Eso sí, parece ser que no me aclaro si estoy en Chicago o en Polonia…

Lo de la Iglesia o el gobierno de nuestro querido amigo Bush. Y, por supuesto, teniendo en cuenta que he llegado sano y salvo a Chicago despues de un viaje en avion sin ningun percance. No, esta vez no me tocó un operador surfero, pero (al igual que hice en Valladolid) nunca conseguiría alcohol para un menor. A lo que iba. ¡Ya estoy en Polonia! La verdad es que, como he dicho en múltiples ocasiones (tanto en el weblog, como a la ida) y no hubo mucha turbulencia en ninguno de los tramos. Y ahora, heme aquí, luchando contra el cambio de horario tras volver de Chicago, a comer (y malamente) a las 15:30 todos los días. Vamos, muy fuerte. Afortunadamente, a partir del lunes ya tengo un horario bastante más amigable…paso de tener 3- 4 horas de clase el profesor te cuenta cada tema un poco por encima y luego te dice “Para el lunes traigan leidas las páginas 107 a 403 de Silberschatz y Gavin”. Es decir, el temario te lo tienes que aprender tú por tu cuenta. En la sesión de orientación para todo. Incluso para el acoso sexual es un problema que es independiente de la afiliación política. Si hubiese ganado Gore, tendríamos el mismo problema (aunque no me cabe duda de que será todo tan interesante como lo poco que tiene…”, me solian decir. Y cuando me preguntaban si ya había estado en Valladolid y les respondía que lo más cerca fue Salamanca, me decían “Jo, pues es

Ya veis. Una chorradita. Pero una chorradita basada en principios matemáticos la mar de curiosos :-)

Estructuras matemáticas con sentido del humor

Published
by
Borja Sotomayor
on 30/11/2004
in Cosas que nos enseñan en el doctorado
. 16 Comments

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:

Cadena de Markov

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 Xn 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 Xn+1 sea i dado que Xn 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).

Power-law powah!

Published
by
Borja Sotomayor
on 29/10/2004
in Cosas que nos enseñan en el doctorado and Informatica
. 5 Comments

La verdad es que las clases de este cuatrimestre (”Matemática discreta” y “Grandes ideas de la computación”) no son muy emocionantes, ni dignas de mención, pero hoy hemos tenido una clase la mar de entretenida. La asignatura de “grandes ideas” consiste en que cada semana viene un profesor distinto de la facultad a hablarte sobre una “gran idea” de la informática. Hasta esta semana hemos tenido a profesores cuyas “grandes ideas” pues, sinceramente, no eran demasiado emocionantes (excepto la primera semana que nos hablaron de las máquinas de turing durante un par de días). Por ejemplo, hace un par de semana vino un profesor a largarnos un rollo macabeo muuuuy teorico sobre complejidad Kolmogorov (que ninguno de nosotros entendió) y la semana pasada un profesor vino a hablarnos sobre criptografía (pero intentó simplificar tanto, que al final fue un aburrimiento). En general, hasta ahora ha sido todo chapa teorica llena de teoremas, formulas, etc, etc.

Esta semana, en cambio, ha venido Ian Foster a hablarnos de Internet. Sí, sí, Ian Foster es el ‘padre de la Grid’, pero prefirió hablarnos de Internet porque es una idea aun más grande que la Grid. Los dos primeros días fueron bastante normales (origenes de Internet, un poco sobre conmutación de paquetes, etc.). Interesante, pero no tremendamente emocionante (aunque por lo menos no era chapa teorica-matemática). Lo realmente interesante ha sido hoy cuando nos ha hablado de las “power-law distributions” (¿alguien sabe cual es el término equivalente en castellano?).

Una distribución power-law viene a ser algo así como una generalización del Principio de Pareto. Recordemos brevemente el Principio de Pareto: cuando en un programa el 80% de los problemas provienen de un 20% de los bugs y el resto de los problemas (20%) proviene de un 80% de los bugs, entonces nos encontramos ante una distribución según el Principio de Pareto. Una distribución power-law es sencillamente cualquier distribución en el que una minoría de elementos acapara casi todas las relaciones, y el resto de los elementos (una mayoría) tiene muy pocas relaciones. Ian Foster nos ha estado citando mogollon de lugares y sistemas donde nos encontramos con esta distribución y, curiosamente, esa distribución no es por diseño. El estudio de por qué un sistema sigue una distribución power-law es, al parecer, un area de investigación bastante activa.

¿Y que tiene todo esto que ver con Internet? Pues resulta que los siguientes sistemas siguen una distribución power-law:

  • Los routers de Internet. Hay una minoría de routers que se encargan de encaminar gran parte del tráfico de Internet, mientras que la mayoría de los routers se encargan de tareas de encaminamiento mucho más sencillas.
  • La web. Unas pocas webs acaparan todos los enlaces ‘entrantes’, mientras que la mayoría de webs tienen muy poco enlaces ‘entrantes’.
  • La blogosfera. Pues lo mismo que la web (unos pocos weblogs son la élite y son seguidos por casi todo el mundo, mientras que la mayoria de blogs solo tiene un puñado de fieles seguidores). Pero es interesante ver la blogosfera como un caso aparte porque es más facil establecer un paralelo con las social networks que si utilizamos la web como punto de partida (la web es demasiado extensa). Es aconsejable este artículo.
  • Las redes de compartición de archivos. Muchos estudios han descubierto que en este tipo de redes (Gnutella, Kazaa, etc.) siempre se acaba formando una distribución power-law: unos pocos usuarios generan la mayoria del trafico, y casi todos los usuarios generan poco tráfico.

Lo realmente interesante es que seguir una distribución power-law es, en casi todos los casos, una vulnerabilidad. Por ejemplo, consideremos dos sistemas: el de carreteras y el de aeropuertos. El primero no sigue una distribución power-law, porque no podemos decir que haya ciertos nodos que acaparen casi todo el tráfico mientras que la mayoría tienen poco tráfico. En general, el tráfico está distribuido siguiendo una distribución normal (o de Poisson, ahora no me acuerdo). El sistema de aeropuertos sigue una distribución power-law. En EEUU, por ejemplo, los aeropuertos de Chicago, Nueva York, Atlanta, y Los Angeles acaparan casi todo el tráfico aereo, mientras que los otros tropecientos aeropuertos tienen un tráfico aereo bastante pequeño en comparación. Ahora bien, si un terrorista quisiese desmantelar el sistema de carreteras, le resultaría bastante dificil (podría cargarse una autopista, pero eso sólo afectaria a esa autopista en concreto y posiblemente a las ciudades más cercanas). Si un terrorista quisiese desmantelar el sistema de aeropuertos, con tan sólo cargarse el aeropuerto de Chicago (el aeropuerto O’Hare), ya dejaría el tráfico aereo patas arriba.

Un ejemplo interesante que ha citado Ian Foster es que, en el caso de las redes de compartición de archivos, el homólogo americano de la SGAE se centra en demandar legalmente a los usuarios que acaparan la mayoría del tráfico en Kazaa. Cómo la red se organiza siguiendo una distribución power-law, cuando se cargan a esos usuarios consiguen en efecto cargarse de golpe casi la mitad del tráfico.

De nuevo, no hay que olvidar que esta distribución no es fruto de una decisión de diseño. La gran pregunta que ha lanzado Ian (y que dice que tiene una dimensión social más que tecnológica) es: ¿Por qué las redes tienden a auto-organizarse siguiendo una distribución power-law? ¿No tiene más sentido que se organicen de otra manera para evitar que un fallo en un lugar crítico de la red la descojone por completo? Vamos, da un poco que pensar…

Y, finalmente, algo divertido que ha mencionado Ian Foster. Entre los múltiples ejemplos que ha citado, ha mencionado que muchas enfermedades se propagan siguiendo una distribución power-law, y que a veces con aislar a ciertos individuos clave consigues frenar la epidemia. Sin cortarse ni un pelo, ha dicho “por ejemplo, en el caso del SIDA, donde las relaciones sexuales siguen una distribución power-law”. Venga, pensadlo un par de segundos que a mi también me ha costado pillarlo. Ha sido muy divertido porque Ian Foster lo dijo, y no hemos empezado a reirnos hasta cinco segundos después cuando hemos entendido lo que ha dicho. Vamos, que resulta que en lo que se refiere a las relaciones sexuales, hay estudios que demuestran que un puñado de cabrones acaparan toda la acción, y casi todo el mundo tiene que conformarse con las migajas. Cuando Ian ha visto que empezabamos a reirnos, de nuevo sin cortarse un pelo ha dicho: “Si, bueno, por ejemplo, cuando empezó la epidemia del SIDA los investigadores descubrieron que una de las principales causas de que la enfermedad se extendiese tan rapidamente fue por culpa de un azafato canadiense que… ejem… estaba excepcionalmente bien conectado” xDDD