martes, 19 de abril de 2016

Las redes (y las probabilidades) de Juego de Tronos



¿Quién es el siguiente? La predicción de muerte en (la serie) El Juego de Tronos * - Parte 1: De los libros a las redes sociales
Por Clemente Fredembach | Teradata

Información de los primeros 5 libros se discute, que corresponde a los primeros 5 temporadas de la serie de televisión con algunas variaciones (la serie de televisión es más avanzado, pero omite una serie de personajes secundarios para mayor claridad y razones presupuestarias).


¿Tiene la ficción realmente que tener sentido? Este blog explora la aplicación de la ciencia de datos para contar historias a través de la lente de G.R.R. serie épica de Martin (~ 1,4 millones de palabras). Juego de Tronos (GOT) ha sido, en parte, ser famoso porque para cualquier personaje es "juego limpio" que puede morir en cualquier momento, independientemente de la forma en que prevalece/n él/ella/ellos hasta ese momento. ¿Son esas muertes el resultado de "caprichos" del autor, o son parte de una narrativa ya construida?

Para responder a estas preguntas, nos dirigimos a grafos de red. A partir de los datos de texto sin formato, que:
  • crea automáticamente una red social de caracteres para cualquier período de tiempo de la historia
  • Analizada la estructura y las historias de los libros individuales a través de una red de relaciones
  • Medido la importancia y la posición de los personajes a lo largo de la historia basada en su centralidad y la visualizaciones de grafos de red 
  • Predecirse con exactitud grandes muertes de caracteres con un algoritmo de propagación de las creencias (LBP) a través de la red social

Los resultados completos basados en grafos sólo se requiere los datos de texto y una lista de nombres de los personajes. No fue necesaria ninguna información "experto" sobre los libros o historia. A pesar de esta aparente simplicidad, las redes creadas representan fielmente la historia y las principales muertes de caracteres se predicen con exactitud.

¿Por qué los libros?

Ambos libros y series de televisión requieren aproximadamente 50 horas para leer / ver y contienen vagamente [2] la misma información. Texto, sin embargo, es mucho más fácil de analizar y gestionar de vídeo. Además, los libros corresponden a G.R.R. la historia original de Martin, mientras que las adaptaciones siempre vuelven a escribir el material en cierta medida.

En primer lugar, cargamos los archivos de libros electrónicos en una base de datos de Aster y los separamos en capítulos; la preservación de todo el contenido del texto. Debido a que tenemos es escrito como una serie de capítulos "Punto de vista" (POV), es decir, cada capítulo es contada desde la perspectiva de un personaje, se puede estimar cuya historia efectivamente se está contando en los libros contando el número de palabras dedicadas a la perspectiva de cada personaje POV.



A pesar de su simplicidad, recuento de palabras se obtiene información valiosa sobre la estructura de la historia:

  • Los dos primeros libros se cuentan desde la perspectiva de los Stark (Tyrion y Daenerys, dos marginados, son los otros), lo que lleva naturalmente a la "Stark = buena Lannister = mal," percepción de la historia
  • La parte de la historia contada por el "segundo nivel" personajes POV (4º en adelante) disminuye constantemente con el tiempo como la historia se vuelve más compleja y se introducen nuevos personajes POV.
  • Mientras que sólo cuatro [3] POV personajes son definitivamente muerto por este punto [4], la muerte de Eddard Stark es una sorpresa porque él es el narrador principal del primer libro.

Más allá de conteo de palabras: la creación de una red social de texto

Tenemos es una historia larga y complicada, con una gran cantidad de caracteres. Tal vez el contador-intuitivo, esta complejidad es una ventaja: en lugar de referencia de los pronombres constantes, conseguido por lo general explica en detalle los nombres de personajes completos [5]. Por otra parte, el nombre del personaje POV sí se menciona con frecuencia en sus respectivos capítulos [6].

Hemos creado las redes sociales de información de texto menciona hallazgo de 102 caracteres [7] a través de los libros. Esto incluye apodos comunes de los apéndices del libro, por ejemplo, Matarreyes, -Khaleesi.

En cada capítulo, se contó el número de ocurrencias de todos los nombres de los personajes para crear un vínculo entre el carácter POV y los personajes cuyo nombre ocurrir en el capítulo. Por ejemplo, en un capítulo POV "Arya", si "Arya" se menciona 20 veces, 'Sansa' 12 veces y 'Jon' 11 veces, tendríamos (ver tabla):



Arriba: Salida del algoritmo de recuento de caracteres. Cada mención de los 102 caracteres "orugas" es contada por cada capítulo. El valor R y última fila (Sansa-Jon) no se obtienen directamente por análisis de texto, pero en una etapa posterior se describe a continuación.

Esta metodología produce naturalmente una red de "radios", ya que las relaciones entre los personajes no POV no son capturados. Derivamos las relaciones "-carácter transversal" por:

1) La normalización de carácter menciona (por capítulos) para crear un valor mención R
2) Cálculo de la R 2 entre caracteres no POV con una medida de la distancia euclidiana de tipo [8]

La producción de este proceso se muestra en la tabla anterior. Para cualquier capítulo único, la fuerza relación (R) entre dos caracteres no POV no puede exceder su fuerza relación con el carácter POV.

La medición de las relaciones entre los personajes en un capítulo-base, podemos crear una red social para cualquier capítulo único, o entre dos puntos en el tiempo en la historia de la suma de los valores de R para los capítulos considerados. Hemos visualizado los grafos a través de Aster App Center, con las siguientes propiedades:

  • el color de nodo corresponde a la salida del algoritmo de modularidad (basado en la agrupación grafo de comunidades sociales)
  • el tamaño de nodo representa el número de las menciones de un carácter
  • el grosor y color del enlace representan la fuerza relativa de las conexiones entre los personajes (= más gruesas y más rojas más fuertes)

La temporada (TV) libro en particular es posiblemente la escala más natural a la parte de la historia; generamos visualizaciones de grafos para cada libro (información no acumulativo) y uno que cubre toda la historia (todos los libros de la página 1).

Libro 1 conduce a un gran grupo de púrpura centrada en los acontecimientos en Desembarco del Rey con fuertes vínculos entre Eddard, el rey Roberto y el Consejo Pequeño. El racimo grande de color rojo se refiere a los acontecimientos en el Norte y las Tierras de los Ríos, con una familia Stark firmemente conectado y la captura de Tyrion más adelante en el libro. La decisión de Jon a la pared le da su propio clúster cian, mientras que los eventos a través del mar se representan correctamente con el pequeño pero firmemente conectado racimo verde de la Targaryen / Dothrakis.


Arriba: Grafo de la red social de "Juego de Tronos": el primer libro de "Canción de Hielo y Fuego" de la serie. Los grupos y la estructura de la red se adhieren bien a la historia a pesar de haber sido obtenido de forma automática desde los libros "texto sin formato". Las relaciones más fuertes se pueden ver entre Eddard y Robert, Eddard y Catelyn, Daenerys y Khal Drogo

La historia principal del segundo libro narra los acontecimientos en Desembarco del Rey (cian) con Tyrion, Sansa y Joffrey, así como la "guerra de los reyes" que implican los Stark y Baratheon (amarillo). Un número de grupos individuales más pequeños aparecen alrededor de Bran en Invernalia (rojo) y de Arya (verde) escapar se separado de la "historia principal". La Bahía de pared (púrpura) y Esclavos (azul) todavía tienen el individuo, grupos bastante independientes.



Arriba: Grafo de la red social de "Choque de Reyes": el segundo libro de "Canción de Hielo y Fuego" de la serie. Las relaciones más fuertes se pueden ver entre Joffrey-Sansa-Tyrion, Renly-Stannis. Vemos nuevas relaciones fuertes en desarrollo entre Jon-Qhorin, así como Daenerys y Jorah. En comparación con el conseguido, el segundo libro tiene una estructura más compleja, con dos historias principales (Desembarco del Rey y las Tierras de los Ríos) flanqueados por grupos independientes más pequeños que siguen personajes centrales POV.

La progresión basada en el grafo de los libros ilustra lo que la mayoría de los lectores sabrán [9]: más personajes y sub-historias aparecen (Dorne y las islas del Hierro en el Libro 4, Quentyn Martell en el Libro 5). Las redes sociales correspondientes toman la forma de pequeños interrelaciones centradas en personajes POV que tienen cada vez menos contacto entre sí. Esta estructura es particularmente evidente en los libros 4 y 5 A pesar de la línea de tiempo entrelazados (Libro 4 y 5 están divididos geográficamente más bien que en el temporal) [10].


Arriba: Grafo de la red social de "Tormenta de Espadas": el tercer libro de "Canción de Hielo y Fuego" de la serie. El libro continúa la evolución hacia las comunidades más pequeñas y separadas, con Aria y Bran tener sus propias historias que se entrecruzan poco con la historia principal más pequeña (Robb-Catelyn-Walder "rojo de la boda" y Joffrey-Sansa-Tyrion "púrpura de la boda"). Un cambio importante es el crecimiento de la agrupación de pared con la llegada de Stannis en el norte (rosa).


Arriba: Grafo de la red social de "Festín de Cuervos": el cuarto libro de "Canción de Hielo y Fuego" de la serie. La red toma una forma muy distinta, con casi las comunidades aisladas "rayos" y la aparición de nuevos personajes (Dorne es celeste y los isleños de Hierro en rojo). El libro trata de Cersei y Jaime; mientras que Daenerys y la pared no son parte del libro 4.



Arriba: Grafo de la red social de "Danza de Dragones": el quinto libro de "Canción de Hielo y Fuego" de la serie. El último libro de la serie hasta el momento sigue para ilustrar el cambio en la estructura de la red, con un menor número de enlaces globales y una estructura más central en torno a sus personajes principales. Tyrion ha dejado Poniente y ahora aparece en la Bahía de los Esclavos. La proliferación de las "historias de lado" y la introducción de personajes principales haber estirado la red en una serie de individuos.


La medición de la importancia del carácter con grafos

Una estructura de red de los grafo de la historia nos permite comprender y medir la importancia relativa de los personajes mejor que a través de la cantidad de palabras solas: en particular, con las medidas de centralidad de 'intermediación' (la cantidad de tránsitos a través de un nodo de la información) y 'cercanía' (lo céntrico un nodo está dentro de su red local).

Los personajes que viajan o actúan como puerta de entrada a sus comunidades puntuación alta en intermediación, mientras que los personajes centrales de sus comunidades (grandes) tienen un alto cercanía. Los personajes como Jon Tyrion o "Enlace" otros personajes (y la historia) juntos, mientras que los caracteres con alta cercanía, por ejemplo, Catelyn o Sansa forman relaciones fuertes dentro de su red. Tyrion puntúa altos en tanto, convirtiéndose en el personaje central global de la historia hasta el momento.


Arriba: Valores de centralidad de intermediación y los valores de proximidad para el personajes a través de los libros. Libro 1 se trata de Eddard, Libro 2 sobre Tyrion y Joffrey, libro 3 es la mejor equilibrada. El Libro 4 es Lannister centrada, mientras que el último es todo sobre el Norte. El aumento de la intermediación en el libro 5 es el resultado directo de una red más descentralizada (véanse los grafos correspondientes).



Arriba: La historia hasta ahora: Grafo de la red social sobre la totalidad de los 5 libros. Canción de Hielo y Fuego es la historia de los Lannister (rojo), los Stark (verde, azul, púrpura oscura) y una mujer con los dragones (oro). Desde una perspectiva de la estructura de red, Tyrion y Jon son los protagonistas de la historia. En cuanto a personajes muertos hasta el momento, observamos que están, todas ellas situadas en el centro dentro de su red o son nodos hoja (es decir, unos personajes 'hub' se mata a) [11].

¿La muerte de Eddard: una sorpresa?

Ser capaz de calcular las redes sociales en cualquier punto de la historia nos permite monitorear el estado de la red social hasta el punto de las principales muertes (es decir, el capítulo antes de la muerte se produce) y determinar si la muerte personaje fue una sorpresa, o Ya ordenado por la estructura de la red y las muertes anteriores.

Para predecir las muertes de caracteres, empleamos un algoritmo de propagación de las creencias (LBP), que se propaga creencias terreno la verdad de un estado de carácter (es decir, la información verdadera, con 0 = vivos, 1 = muerto) a lo largo de los grafos, de acuerdo con pesos de las aristas [12].

valores de verdad terreno "muertas" son fáciles de obtener (un personaje se le asigna un terreno la verdad de "1" a su / su muerte). Por otro lado, la verdad terreno "Alive" es más difícil de definir en una serie conocida por su alta tasa de mortalidad. Podemos, sin embargo, utilizar LBP para mostrar que las grandes muertes de caracteres se pueden predecir a partir de sólo las redes sociales y poner a prueba nuestra hipótesis inicial "Alive", al mismo tiempo (es decir, si nuestra realidad del terreno conduce a predicciones exactas entonces es creíble).

Nuestras reglas de predicción son:

  • Jon Arryn, Viserys y Robert Baratheon están "muertos" (es decir, que no hacen predicción antes de la muerte de Robert, no hay suficiente información)
  • Cuando los personajes mueren (o no importante) se añade a la realidad del terreno "muerto"
  • Daenerys y Jon Snow están vivos [13] (nuestro único "vivo" verdad del suelo)

Las terreno la verdad "creencias" (vivos o muertos) se propagan a lo largo de la red con el valor R calculado anteriormente [14]. Es importante destacar que la LBP no utiliza ningún "información futura" o aprendizajes para el cálculo de las creencias (aparte de la realidad del terreno "vivo"), sólo se utiliza la estructura de la red social en el momento del evento.

¿Quién es el siguiente? LBP resultados de predicción de muerte?

El riesgo de muerte (caracteres clasificados en la parte superior) antes de la ejecución de Eddard Stark



Arriba: La "probabilidad de muerte" (segunda columna de la tabla anterior) no debe ser tomada literalmente; no tenemos datos suficientes cerca de terreno la verdad (o datos en total) para el valor para ser más precisos, la orden es más significativo aquí.

En ese momento de la historia (el capítulo antes de su muerte), Eddard es la persona más probabilidades de morir. Tenga en cuenta que Khal Drogo (que muere casi al mismo tiempo) es segundo en la lista.

Podría decirse que, Eddard era el centro de todas las medidas de la red, por lo que este resultado podría deberse a "el personaje más central está marcado como el más probable de morir". En realidad, el estado de la red social en el momento de la muerte de Eddard indica que es su proximidad al rey Robert que eleva su riesgo.

Siguiendo adelante, tenemos:

El riesgo de muerte (caracteres clasificados en la parte superior) antes del asesinato de Renly Baratheon




Arriba: Después de Eddard y Khal Drogo, Renly es la próxima gran personaje de la muerte [15]. Por otra parte, él no es un carácter particularmente central: la baja intermediación, y ningún capítulo POV. El algoritmo LBP lo recoge con precisión como el carácter más probable que muera.

El riesgo de muerte (caracteres clasificados en la parte superior) antes de que el "rojo de la boda".


El capítulo (y Episodio de TV) etiquetado como el "rojo de la boda" ve todo el anfitrión amigo Stark + obtención asesinada, pero sobre todo Robb y Catelyn Stark.



La predicción de dolor lumbar sigue siendo fiable: el carácter "más probable morir" se determina que es Catelyn Stark, mientras que 5 de las 10 personas con las más altas probabilidades son parte de la "Red de boda" en sí. Catelyn puntuaciones significativamente superiores a su hijo Robb, debido a su participación más estrecha con Stannis y Renly (en el segundo libro). En ese momento de los libros, la relación entre Robb y Catelyn es el más fuerte entre dos caracteres, es decir, cuando uno muere, el otro será superior al instante la lista de riesgos.

La precisión de LBP durante los 3 primeros libros es notable teniendo en cuenta la limitada información que utiliza [16]. De hecho, solamente la muerte de Joffrey se perdió (que ocupa el 7º de ~ 80 caracteres). En los libros hay poco tiempo entre las dos bodas (10 capítulos más o menos); sin nueva realidad del terreno o las relaciones, las predicciones de dolor lumbar son muy inclinada hacia los sobrevivientes de la "roja de la boda".

Desde el cuarto libro en adelante, sin embargo, la exactitud de la LBP se baja por tres razones:


  1. El número de muertos sigue creciendo mientras que los "sobrevivientes" adicionales son difíciles de precisar sin utilizar retrospectiva 20/20, por lo que la mayoría de los personajes se predice a morir
  2. La historia se vuelve menos centrado, con un "hub and spoke" modelo [17]; la propagación de creencias a lo largo de este tipo de grafos puede ser inexacta
  3. Libro 4 y 5 se producen "al mismo tiempo" [18], por lo que la predicción de propagación más difícil.


¿Jon Snow está muerto?

A pesar de su sencillez y limitaciones, dolor lumbar proporciona información increíblemente precisa.

Para el final del libro 5 de la "línea de tiempo" es volver a la normalidad, lo que nos permite predecir que muere en el libro 6 en función del estado de la red social en toda la historia.

Sin embargo, tuvimos que tomar una decisión: Jon Snow se marcó con el estado "vivo" para el análisis. Por lo tanto, la LBP predijo que está vivo. Si quitamos su condición de realidad del terreno, se puede predecir la mayoría de los personajes de morir (ya que sólo Daenerys se mantendría como "vivo").

Por lo tanto, se corre el algoritmo bajo dos hipótesis distintas:


  • Etiqueta Jon Snow "desconocido" y Tyrion como "vivo" para predecir quién será el próximo a morir bajo el supuesto de que Jon Snow es "juego limpio"
  • Mantener "vivo" (nuestra hipótesis de pie) Jon.

Predicción del Libro 6 



Arriba: Los números están cerca uno del otro, que se espera teniendo en cuenta el bajo número de caracteres "vivo". Las relaciones se construyen más de 5 libros sin embargo; pequeñas diferencias son más significativas que en las medidas anteriores.

Conclusión


Si Jon Snow no se mantiene viva manualmente, que está muerto [19]. Si Jon está vivo y luego Brienne, Walder (Frey), Sam, Edmure y los Lannister son parte superior de la lista [20].

¡¡¡¡No te pierdas!!!!

Lea la segunda parte en los "Predecir muerto en Juego de Tronos 'Series Blog mañana en Análisis y conclusión de supervivencia basada en eventos.

------------------------

Notas al pie

* Mientras que el libro se llama "Canción de Hielo y Fuego", la mayoría de la gente lo conoce como Juego de Tronos

[2] Los libros tienen un contenido más detallado y más historias secundarias

[3] Catelyn (no hay chanchullos señora stoneheart aquí), Eddard, Arys Oakheart y Quentyn Martell

[4] De hecho ser un POV es la segunda característica más precisa para predecir la supervivencia

[5] Necesario cuando se mencionan tantos personajes en un solo capítulo

[6] De hecho, es el nombre que más se menciona en todos menos en un par de capítulos

[7] De http://iceandfire.wikia.com

[8] En concreto, si dos caracteres A y B que tienen una resistencia de la conexión con el carácter PoV de R (A) y R (B), respectivamente, se calcula la fuerza de la relación AB como 1 - sqrt (((1- R (A)) * (1-R (A)) + ((1-R (B)) * (1-R (B)))

[9] Y la mayoría de los físicos, así: la entropía siempre aumenta

[10] La serie de televisión se han omitido o acortar una serie de personajes secundarios e historias y mantuvo una línea de tiempo unificado, por lo que es "más coherente"

[11] Lo que es un buen augurio para Jon Snow

[12] Este algoritmo ha utilizado anteriormente en los datos históricos del renacimiento aquí: http://blogs.teradata.com/international/a-crazy-belief-predicting-outcomes-from-network-graphs/

[13] Se trata de "Canción de hielo y fuego" después de todo ...

[14] He calculado modificaciones en el valor de R en función de los personajes son de casas amigables enemigos / o relaciones de lealtad. Cambió los números un poco, pero no el orden de los "caracteres de probabilidades de morir / sobrevivir"

[15] Con un importante papel en la serie de televisión

[16] ¿El G.R.R. Martin sabe más acerca de la teoría de grafos lo que deja ver?

[17] Véase los grafos de redes para el libro 4 y 5

[18] La serie de televisión "fija" este

[19] Esto puede llegar a ser literalmente cierto

[20] Como cobertura gratuita, estas predicciones son para los libros; la serie de televisión puede llegar a ser diferente

No hay comentarios:

Publicar un comentario en la entrada