 |
Contar Mal |
| Segunda parte de mi cuento chino sobre serpientes, barajas y grafos. O como clasificar un metajuego en 30 segundos. Dejémoslo en tres cuartos de hora, contando recogida y etiquetado. |
La primera parte estuvo aquí. Todo será más fácil si ya la habeis leído.
Esta segunda es grande, aunque la parte que entra en el examen es fácil de entender. Siempre podeis usar los nombres de secciones en negrita para saltaros cosas, aunque no está concebido así.
En episodios anteriores...
Buscando una manera de automatizar la clasificación de barajas en arquetipos, pensé en una aplicación primitiva de un concepto cuantitativo de arquetipo, sin mucho éxito. Meses después, ¡me topo con un problema de grafos que puede modelar la situación! "Búsqueda de Comunidades en Redes Complejas."
Una pequeña corrección: dije en la primera parte que cuando me di cuenta de que mi algoritmo primitivo no iba a llegar lejos, era Septiembre del 2010. En realidad, era antes del verano, durante la temporada de Amsterdam, en la que empecé a utilizarlo. Caso claro de tu-cerebro-no-encuentra-la-información-en-ese-momento-así-que-se-la-inventa-pero-no-te-lo-dice. Desde entonces hasta que me puse de nuevo con el problema estuve con otra cosa más, que tuve que dejar temporalmente plantada.
El problema intenta encontrar organización interna, "comunidades"; en grafos densos que representen desde redes sociales hasta tráfico aéreo, "redes complejas." Una red de similitudes entre barajas es un caso concreto de este problema. No significa que sea la mejor manera de resolverlo, pero es la mejor que conozco ahora mismo.
"Búsqueda de Comunidades" es un problema de optimización intratable (hay pruebas de que es NP-Duro, pero hay más interés por mejorar las soluciones que por demostrarlo), no se puede obtener la solución óptima en tiempo razonable, nos tenemos que conformar con optimales (locales al óptimo). Repito: no sabemos si cualquier solución que podamos calcular es la mejor, sólo que es buena.
Pero para poder optimizar necesitamos saber qué optimizar.
Parecerá estúpido, pero coge un grafo y optimiza las comunidades. ¿Eh? ¡Y yo que sé, man! ¡Estoy ocupado con tu vecina! Más quisieras. ¿Qué es una "comunidad"? Que mejoro, ¿el número de comunidades? ¿Su tamaño? ¿Otra propiedad? Esa meninge mentirosa me ofrece las palabras pulpo y garaje.
Estos algoritmos de optimización siguen un esquema general llamado "voraz" (greedy), que podemos apodar "de búsqueda":
- Empieza con una división inicial en comunidades.
- Escoge un nodo, sácalo de su comunidad y compara si añadiendo el nodo a cada una de las demás comunidades, la divisón es mejor.
- Si una la mejora, esa es mi nueva partición candidata. La tomo y sigo probando a mover nodos.
- Si no mejora o me quedo sin nodos, es la mejor solución que hemos podido encontrar.
Título ominoso
Ya tengo que poner algún vocabulario, si no esto va a ser muy largo (¿si no?).
- Nodo: Elemento de un grafo. Punto, vértice. Representa a los objetos que estemos modelando. En mi caso, una baraja.
- Arco: Elemento de un grafo. Arista, borde, lado, enlace. La relación entre dos nodos. En mi caso, porcentaje de cartas similares entre dos barajas.
- Grafo dirigido / no-dirigido: Las relaciones pueden tener dirección o no. Si es dirigido (directed), una arista entre los nodos A y B se considera distinta que una desde B hacia A (las tendrás que distinguir con una flecha o similar). Si no importa, es no-dirigido.
- Grafo ponderado: Si a las relaciones les asignas valores, se dice que el grafo es ponderado (weighted) y a los valores se les llama pesos.
- Comunidad: Cluster, agrupamiento, módulo. Ya lo he dicho, subconjunto de nodos del grafo con más densidad de enlaces intra-comunidad que inter-comunidad.
- Partición: Conjunto de subconjuntos disjuntos de un conjunto, tal que la unión de todos ellos es igual que dicho conjunto original.
Empezaron a salir algoritmos que optimizaban la moduralidad como setas. Directamente o aprovechando algunas propiedades. Cambiando ligeramente la definición o el método de generar los grafos aleatorios contra los que mide.
¡Pero hay un problema! Me he quedado sin croissants.
La optimización de modularidad tiene un límite de resolución. Es incapaz de detectar comunidades de cierto tamaño pequeño, relativo al tamaño total del grafo. Santo Fortunato remarca en su biblia (no me he leído las 103 páginas) del 2010 sobre "Búsqueda de Comunidades" que se debe a la definición de los grafos aleatorios, pero que aún nadie sabe como crear otra definición que arregle la debilidad que lo provoca. Este es un campo de actualidad, no está cerrado en absoluto. Digamos que el usar grafos completamente aleatorios introduce "ruido".
... ahora es cuando no uso nada de esto y me voy a otro sitio. Bueno, más o menos.
Resumiendo, reduje los algoritmos que optimizan modularidad a un par que quería probar, incluyendo el reconocido como más preciso (que menos sufre el límite de resolución, a costa de ser más lento), el Simulated Annealing, perfeccionado por físicos/químicos españoles.
Pero encontré también otro que utilizaba un concepto completamente distinto. Information Map, por Rosvall y Bergstrom en el 2008. Como ya tenían en su página web código en C, fácil de compilar, lo probé el primero. Después probé uno de modularidad, pero me pareció demasiado lento y sensible comparado con el infomap. Especialmente cuando vi que había una versión que detectaba más de un nivel de jerarquía, de Octubre del 2010. ¡Recién salido del horno!
Infomap concibe el problema como el cartografiar un mapa. Para esto simula un caminante aleatorio, un agente imaginario que efectúa un recorrido aleatorio sobre el grafo. Recorrido aleatorio quiere decir que en cada nodo, se mueve a cualquiera de sus nodos adyacentes con la misma probabilidad, o con probabilidades proporcionales a los pesos de cada enlace, si el grafo es ponderado. Si el grafo es dirigido, las dirección del movimiento está restringida por la dirección de cada enlace en cada nodo.
Un caminante lanzado en un recorrido aleatorio infinito se quedará más tiempo, de media, "atascado" en las comunidades que haya en el grafo que viajando entre ellas, puesto que, por definición, una comunidad tiene más enlaces dentro que hacia fuera. Para garantizar que en algún recorrido no se queda siempre atrapado, infomap hace trampa y añade siempre una baja probabilidad fija de que el caminante se "teleporte" a un nodo al azar en lugar de seguir el flujo. Esto lo convierte en el bot que usa Google para mapear internet. Volviendo a la metáfora del mapa, el caminante es el cartógrafo. Las comunidades que estamos intentando detectar son "cuidades." ¿Qué optimizo?
Esa es la gracia, esto es un problema de compresión. Dentro de las ciudades hay calles, pero los nombres de calles se pueden repetir de una ciudad a otra. De hecho, hacer eso minimiza el número total de nombres de calles que necesito. ¿Cómo diferencio entre dos calles con el mismo nombre pero en distintas ciudades? Pues con Google Maps... y (yuxta)poniendo el nombre de la ciudad delante.
Concretamente, usa simple codificación Huffman. Un código de longitud variable, como nuestro alfabeto (todas las palabras se forman a partir de los mismos 26 símbolos, pero no todas las palabras tienen la misma longitud); que asigna códigos largos a los símbolos que se usan con menos frecuencia, y viceversa. No hay que saber más.
Cuando Shannon estaba demostrando el teorema del muestreo en el 48, produjo un teorema que dice que la longitud media de un código de longitud variable, como el que Huffman perfeccionó tres años después, que se use para representar los estados de una variable aleatoria -que ocurran cada uno con una frecuencia-, no puede ser menor que la entropía de dicha variable. Entropía que tiene una ecuación extremadamente sencilla y rápida de calcular (suma de productos de logaritmos).
Si consideramos las comunidades de una partición concreta como los estados de esa variable aleatoria, y las frecuencias de cada estado como la fracción de tiempo que el caminante aleatorio infinito medio estuvo en esa comunidad; entonces la entropía de la variable es la longitud mínima de cualquier código de Huffman posible que describa ese número concreto de comunidades.
Pero faltan las calles de dentro de las ciudades. Combinando también la entropía del código de Huffman medio para describir los nodos dentro de las comunidades, yuxtaponiendo como dije, tenemos finalmente una función que describe la longitud mínima del código de Huffman medio que describe todos los nodos del grafo, pero aprovechando una estructura concreta de comunidades. ¡Awesome!
Probando particiones minimizando esa función ya tenemos un algoritmo de optimización igual que los que maximizan la modularidad. De hecho, infomap utiliza un simulated annealing como algoritmo de búsqueda, garantizando que es bastante preciso. Juraría que infomap también sufre de un límite de resolución, diferente al de la modularidad, pero no he conseguido encontrar la referencia, así que mejor me callo.
Lo que sí ocurre es que infomap utiliza un aspecto distinto de una red que los que usan la modularidad. A infomap le interesan los patrones de flujo de información que la red representa, tal y como los revela el caminante aleatorio. A la modularidad le interesan unas propiedades púramente numéricas de los enlaces. En la práctica, esto quiere decir que, dependiendo de la naturaleza de la red, los resultados de infomap y de una optimización de modularidad podrían ser radicalmente diferentes.
Por suerte, la aplicación a la clasificación en arquetipos es un caso muy concreto.
¡Magic, apenas te conocí!
Concretamente, definí la similitud entre dos barajas como el porcentaje de cartas del maindeck de la baraja más grande que también está en el maindeck de la pequeña. Gracias a esa definición, la operación es conmutativa y el grafo correspondiente es no-dirigido, simplicando bastante los cálculos. No me interesa tanto la precisión como la intuición de que si comparo un Battle of Wits con otra baraja, el resultado debe de ser muy pequeño.
Estos porcentajes los asigno como pesos de las relaciones entre barajas, luego el grafo final es ponderado no-dirigido.
En realidad, sería más apropiado optimizar la modularidad. Después de todo, no me interesa cual sea el flujo entre los arquetipos, sino que la clasificación sea lo más granulada posible. Pero como sabemos que los arquetipos existen y la mayoría están razonablemente aislados, realmente cualquiera de las dos aproximaciones detecta fácilmente los arquetipos independientes. La diferencia está en los arquetipos grandes, que no son necesariamente independientes.
Como dije, me gustaron más los resultados del infomap jerárquico (infomaphier a partir de ahora), pero cuando se acabe la temporada y deje de tener prisa, volveré a probar los de modularidad.
Uno podría pensar que con lo holísticas que son ambas aproximaciones, bastaría con lanzarles el grafo de similitudes directamente y ver que sale. Pero no es así, quizás por mi empeño en usar el infomap. Mi algoritmo primitivo usaba un umbral para considerar a partir de cuando dos barajas son lo suficientemente similares como para poder pertenecer al mismo arquetipo. Por ejemplo, 50%.
El comportamiento es el msimo que entonces: umbral más alto, más separación entre arquetipos (granularidad), luego más arquetipos. La diferencia es que, obviamente, el algoritmo es mucho más avanzado y se traga un número arbitrario de barajas.
Esta es la clasificación que puse para extendido hasta mitad de Enero. Usa un umbral de similitud del 58%.
Esta es la clasificación aplicada a los mismos datos, pero con umbral 50%.
Recordad que dejando el ratón sobre cualquier círculo, sea azul o naranja, se ve la etiqueta que buenamente le he puesto.
La diferencia inmediata es que, permitiendo similitudes más bajas, todos los mazos de control con Cryptic Command estaban en una gran familia. Recuerdo perfectamente que el esqueleto de ese superarquetipo era 3xCryptic Commands, 2xMana Leaks y una Island. Después, Faeries se independizó, y las otras se separaraon en "Multicolor Control" y "UR Based Control".
Cambios menores son la separación de Boros de RDW, y el desglose del superarquetipo de Valakut en otros dos pequeños arquetipos.
Pero lo que realmente me hizo subir el umbral fue la incapacidad de distinguir entre Bant y
Trap. El conflicto entre la definición cualitativa y la cuantitativa vuelve a asomar. ¡Trap juega distinto de Bant! ¿Debería importarme? ¿Me solucionará la modularidad estos problemas? ¿Terminaré la frase con una pregunta a modo de chiste? ¿O con una meta-pregunta? ¿Quizás meta-meta-pregunta?¿Y Polymorph, que sé que existe? Infomaphier dice que no pasa el suficiente flujo de información por el como para merecerse su propia "cuidad". O eso o es víctima del posible límite de resolución, ese que no he podido confirmar.
¿Por qué 58% de umbral? ¿Y por qué no? Eres bueno, Griffin.
Es arbitrario. Resulta que si empiezo filtrando con 50% de umbral, los valores atípicos leves en la distribución de similitudes de este metajuego de extendido están por debajo del 58%. Si no filtrase nada, ¡los valores atípicos serían los que superan el 50% de similitud! En realidad la distribución es bastante distinta a lo que creía:
- Más o menos el ~25% de las similitudes dan 0%.
- Sólo el ~10% de todas superan el 50%.
No sé si os dais cuenta de que si ahora filtro al 58%, los valores atípicos son otros. Podría seguir subiendo así el umbral hasta la inutilidad. Al final todo se reduce a "me gustó el resultado". Por cierto, en ese momento, subir de 50% a 58% sólo desechaba el ~6% de enlaces filtrados, pero fué suficiente para inducir cambios.
Otro ejemplo que pensé fue Prismatic Omen. Valakut Wargate naturalmente tiene 4xPrismatic Omen en su esqueleto (intersección de todas sus barajas), pero me sorprendió ver Prismatic Omen en el agregado (unión de todas sus barajas) de Valakut
. Quizás esto no sea una noticia para alguien que se haya pasado el tiempo estudiando el formato, en lugar de cómo clasificarlo, pero ocurre que el ~96% de las barajas en Valakut tienen Primeval Titan y cerca del 50% tienen Prismatic Omen. Yo lo que pensaba era que las de ahí dentro que llevasen Prismatic Omen, no tendrían Primeval Titan, y que informaphier no había identificado "Valakuts con Prismatic Omen" como una distinción relevante. Vamos, que me equivocaba y Primeval Titan+Prismatic Omen es una variante legítima de Valakut, no una diferencia entre las definiciones cualitativa y cuantitativa.Mirar al suelo
Estaría bien entonces ver qué hay por debajo de esos círculos naranjas. Quizás una optimización de modularidad bien empleada me lo enseñe en el futuro; pero si el infomaphier con umbral no lo hace en el presente, tendré que usar otra cosa: El Agrupamiento de Datos (Data Clustering).
Todo está relacionado. Eso es sobre lo que estaba leyendo cuando me topé con "Búsqueda de Comunidades en Redes Complejas". En realidad pensaba usar Clustering para todo esto, pero los grafos me parecieron más apropiados. El Clustering es demasiado preciso, sin dejar de ser arbitrario. Al final del día, esto sigue siendo un problema intratable, no hay una única solución correcta.
No es que tenga mucha idea de "Búsqueda de Comunidades" aparte de lo que estuve leyendo, pero de Clustering sí que no sé nada. He estado usando un software de Jinwook Seo, de la Universidad de Maryland, para mirar por debajo de Faeries (por ejemplo); y sí que hay una división clara e inmediata entre el resto del arquetipo y un par de barajas
Polymorph, sin importar el método que use para el agrupamiento. También dos o tres con blanco para Esper Charm etc.Mi intuición me dice que están cerca de ser detectadas por infomaphier, subiendo el umbral de similitud. Cosas que experimentar.
Por lo demás, es el caos ordenado que esperaba. No estoy preparado para mostrar un mosaico coloreado a modo de mapa de calor tan grande, pero basta con decir que es demasiado complicado y correlaciones, bien pocas. En realidad esperaba ver "paquetes de cartas", al menos para intentar clasificar banquillos, pero los banquillos son aún peor. Cuando dije que los banquillos varían demasiado, no sabía cuanto... los tags tendrán que poner un poco de orden.
Básicamente los únicos agrupamientos de cartas significativos que encontré en el maindeck de Faeries es "cartas que llevan casi todas" y "cartas esporádicas". Para eso tengo otras herramientas, no necesito hacer Clustering. Un poco decepcionante, pero la magia no existe.
En los banquillos, la única correlación que encontré es entre Vampire Nighthawk y Tectonic Edge, y negativa de ambos con Wall of Tanglecord. Vampire Nighthawk y Tectonic Edge se suelen banquillear juntos, a costa de Wall of Tanglecord. Por las cartas que son, diría que es una evolución temporal, pero eso es algo que tengo que mirar usando series temporales; que aún no he hecho. Eso sí dará resultados.
Créditos
Sólo porque no pase más tiempo sin ponerlo, las gráficas dinámicas interactivas las hago (torpemente, de momento) con protovis, un proyecto de código abierto, como debe de ser, de la Universidad de Stanford.
Por lo demás, he puesto por todas partes links y he mencionado autores de los research papers en los que principalmente me basé para aprender estas cosas, así que me niego a agruparlo todo aquí también. Leí bastantes más, pero esos son en los que más me basé. Por cierto, que eran lo suficientemente fáciles como para leer lo que necesitaba. Salvo LA BIBLIA, ninguno tiene más de 12 páginas. No os dejeis intimidar por palabrería, ¿para qué está el diccionario?
Los enlaces a wikipedia sólo están para saber mejor de qué estoy hablando, con leer el primer párrafo basta.
También les debo bastante a los libros de divulgación sobre estadística/economía que por casualidad es lo que tenía para leer mientras aprendía esto:
- Freakonomics. Steven Levitt y Stephen Dubner (¡pronto en documental!).
- The Undercover Economist. Tim Harford.
- A Mathematician plays the Stock Market. John Allen Paulos.
Después leí The Prince de Maquiavelo y no me pareció lo suficientemente maquiavélico. Tristemente lo absorbimos hace tiempo.
Ahora me voy a terminar de leer Tenjou Tenge, que hay tetas. Hasta la próxima y recordad:
By learning you will teach, by teaching you will learn.
Aprendiendo enseñarás, enseñando aprenderás.
-Proverbio latino
Considera dar soporte a nuestro esfuerzo: 