Implementación de asignación jerárquica latente de Dirichlet para modelado de temas

Equation Chapter 1 Section 1 Trabajo Fin de Máster Ingeniería de Telecomunicación Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Autor: María Silvestre Gómez Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 iii Trabajo Fin de Máster Ingeniería de Telecomunicación Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Autor: María Silvestre Gómez Tutor: Juan José Murillo Fuentes Profesor Catedrático de Universidad Dep. de Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 v Trabajo Fin de Máster: Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Autor: María Silvestre Gómez Tutor: Juan José Murillo Fuentes El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2018 El Secretario del Tribunal vii A mi familia ix Agradecimientos A mi abuela porque siempre estarás conmigo y por enseñarme a ser una mejor persona. Espero que estés orgullosa. A mi madre por el esfuerzo realizado todos estos años, por estar a mi lado y por ayudarme a crecer. A mi hermana por las aventuras compartidas, incluso las más pequeñas, y las que nos quedan por vivir. A mis tíos, Cinta y Jesús, y mis dos pequeños, Rubén y Manuel, por alegrarme todos los días y por estar en los buenos y en los malos momentos. A todos ellos, gracias por creer en mí. A mi tutor, Juan José Murillo, por ofrecerme la oportunidad de realizar este proyecto y permitirme profundizar en este área de conocimiento fascinante. A él, junto al resto de profesores que me han acompañado a lo largo de estos años, agradecer todo lo que he aprendido de cada uno de ellos. A todos los que siempre estuvieron a mi lado dándome su apoyo incondicional y a las maravillosas personas con las que he coincidido durante estos años universitarios, con los que he compartido grandes historias y junto a los que he crecido, gracias. A las todas las personas que he conocido en este último año, de los que he aprendido tanto profesional como personalmente y de las que espero seguir aprendiendo, gracias por enseñarme con tanta paciencia y por la confianza depositada en mí. Y en especial, a Jesús, por su ayuda, motivación cuando lo necesitaba y por alegrarme en los días de estrés. María Silvestre Gómez Sevilla, 2018 4.2.2 HierarchicalLDA 33 5 Resultados. Análisis de Parámetros 37 5.1 Base de datos NIPS 38 5.1.1 Análisis del hiperparámetro α 38 5.1.2 Análisis del hiperparámetro γ 46 5.1.3 Análisis del hiperparámetro η 50 5.1.4 Comparativa de hiperparámetros 54 5.2 Base de datos CORA 54 5.2.1 Resultados con 10 niveles 55 5.2.2 Comparativa número de niveles 70 6 Conclusiones 73 Referencias 75 Anexo 77 ÍNDICE DE TABLAS Tabla 1. Conjunto de experimentos para la validación del algoritmo 37 Tabla 2. Hiperparámetros del caso de estudio 1 38 Tabla 3. Resultados del caso de estudio 1 39 Tabla 4. Resumen de los resultados del caso de estudio 1 39 Tabla 5. Código de colores del árbol de topics 39 Tabla 6. Hiperparámetros del caso de estudio 2 40 Tabla 7. Resultados del caso de estudio 2 41 Tabla 8. Resumen de los resultados del caso de estudio 2 42 Tabla 9. Hiperparámetros del caso de estudio 3 42 Tabla 10. Resultados del caso de estudio 3 43 Tabla 11. Resumen de los resultados del caso de estudio 3 43 Tabla 12. Hiperparámetros del caso de estudio 4 43 Tabla 13. Resultados del caso de estudio 4 44 Tabla 14. Resumen de los resultados del caso de estudio 4 45 Tabla 15. Hiperparámetros del caso de estudio 5 46 Tabla 16. Resultados del caso de estudio 5 47 Tabla 17. Resumen de los resultados del caso de estudio 5 48 Tabla 18. Hiperparámetros del caso de estudio 6 48 Tabla 19. Resultados del caso de estudio 6 49 Tabla 20. Resumen de los resultados del caso de estudio 6 49 Tabla 21. Hiperparámetros del caso de estudio 7 50 Tabla 22. Resultados del caso de estudio 7 51 Tabla 23. Resumen de los resultados del caso de estudio 7 51 Tabla 24. Hiperparámetros del caso de estudio 8 52 Tabla 25. Resultados del caso de estudio 8 53 Tabla 26. Resumen de los resultados del caso de estudio 8 53 Tabla 27. CORA - Hiperparámetros del caso de estudio 1 55 Tabla 28. CORA - Resultados del caso de estudio 1 56 Tabla 29. CORA - Resumen de los resultados del caso de estudio 1 56 Tabla 30. CORA - Código de colores del árbol de topics 57 Tabla 30. CORA - Hiperparámetros del caso de estudio 2 58 Tabla 31. CORA - Resumen de los resultados del caso de estudio 2 58 Tabla 33. CORA - Hiperparámetros del caso de estudio 3 59 Tabla 34. CORA - Resumen de los resultados del caso de estudio 3 60 Tabla 35. CORA - Hiperparámetros del caso de estudio 4 61 Tabla 36. CORA - Resumen de los resultados del caso de estudio 4 61 Tabla 37. CORA - Hiperparámetros del caso de estudio 5 62 Tabla 38. CORA - Resumen de los resultados del caso de estudio 5 63 Tabla 39. CORA - Hiperparámetros del caso de estudio 6 64 Tabla 40. CORA - Resumen de los resultados del caso de estudio 6 64 Tabla 41. CORA - Hiperparámetros del caso de estudio 7 65 Tabla 42. CORA - Resumen de los resultados del caso de estudio 7 66 Tabla 43. CORA - Hiperparámetros del caso de estudio 8 67 Tabla 44. CORA - Resumen de los resultados del caso de estudio 8 67 ÍNDICE DE FIGURAS Figura 1. Ejemplo de clasificación usando support vector machine (SVM) 2 Figura 2. Ejemplo de Regresión 2 Figura 3. Ejemplo de clustering usando el algoritmo de K-means 3 Figura 4. Clasificación de los algoritmos de Topic Modelling (V. Jelisavčić, 2012) 6 Figura 5. Representación de los datos en pLSA (V. Jelisavčić, 2012) 8 Figura 6. Modelo asimétrico 8 Figura 7. Modelo simétrico 8 Figura 8. Representación gráfica del modelo LDA 10 Figura 9. Modelo hLDA (Blei, Griffiths, Jordan, & Tenebaum, Hierarchical Topic Models and the Nested Chinese Restaurant Process, 2013) 13 Figura 10. Representación gráfica del modelo DTM 14 Figura 11. Representación gráfica CTM 15 Figura 12. A la izquierda, representación gráfica del modelo PAM de 4 niveles. A la derecha, correlación en PAM de 4 niveles. (Li & McCallum, 2006) 16 Figura 13. Modelo ATM 16 Figura 14. Representación del modelo sLDA 17 Figura 15. Representación gráfica del modelo TNG (Wang, McCallum, & Wei, 2007) 18 Figura 16. Representación de la segmentación AHMM (Blei & Moreno, 2001) 19 Figura 17. Representación gráfica de HMM (Mohit, 2014) 20 Figura 18. Distribución de Dirichlet para distintos valores de α . 24 Figura 19. Histograma resultado de aplicación del algoritmo SBC. A la izquierda, con α2=1 . A la derecha con α2=50 . (Blei Lab, s.f.) 25 Figura 20. Representación de algoritmo CRP (Gershman & Blei, 2011) 26 Figura 21. nCRP de tres niveles (Blei, Griffiths, & Jordan, 2010) 27 Figura 22. Diagrama de flujo de main() 33 Figura 23. Diagrama de flujo de la creación del árbol de topics 34 Figura 24. Diagrama de flujo de la estimación del camino 35 Figura 25. Representación parcial del árbol de topics resultante del caso de estudio 1 40 Figura 26. Gráfica comparativa de distintos valores del hiperparámetro α 46 Figura 27. Gráfica comparativa de distintos valores del hiperparámetro γ 50 Figura 28. Gráfica comparativa de distintos valores del hiperparámetro η 53 Figura 29. Comparativa general casos de estudio 54 Figura 30. Árbol de topics resultante del caso de estudio 1 para la base de datos CORA 57 Figura 31. Árbol de topics de 10 niveles del caso de estudio 2 de la base de datos CORA 59 Figura 32. Árbol de topics de 10 niveles del caso de estudio 3 de la base de datos CORA 60 Figura 33. Árbol de topics de 10 niveles del caso de estudio 4 de la base de datos CORA 62 Figura 34. Árbol de topics de 10 niveles del caso de estudio 5 de la base de datos CORA 63 Figura 35. Árbol de topics de 10 niveles del caso de estudio 6 de la base de datos CORA 65 Figura 36. Árbol de topics de 10 niveles del caso de estudio 7 de la base de datos CORA 66 Figura 37. Árbol de topics de 10 niveles del caso de estudio 8 de la base de datos CORA 68 Figura 38. Gráfica comparativa de la base de datos CORA 69 Figura 39. CORA - Comparativa parcial de cada hiperparámetro 69 Figura 40. Representación de topics en función del número de niveles y del experimento 70 Figura 41. CORA - Representación de topics resultante de cada experimento 71 Notación < Menor o igual > Mayor o igual 1 OBJETIVO Y MOTIVACIÓN lo largo de los últimos años, la cantidad de datos disponibles se ha vuelto tan grande y de tal variedad que el ser humano puede extraer gran cantidad de información. Nos encontramos en la era del Big Data. Ante esta inundación de información, es necesario desarrollar técnicas que permitan el manejo de los datos. La información que se puede extraer es muy variada: estados de ánimo, intereses de las personas, incluso predecir el comportamiento. Estos métodos se engloban en lo que se conoce como machine learning (ML) o aprendizaje máquina. En particular, se define el ML (Murphy, 2012) como un conjunto de técnicas o métodos que permiten extraer patrones en los datos y usar otros patrones para realizar predicciones u otras decisiones que poseen cierta incertidumbre. En la actualidad, se invierte un gran esfuerzo en alcanzar soluciones a estos problemas, empleando estas técnicas automáticas en las que el factor humano se ve ampliamente reducido. En concreto, este proyecto busca poder manejar la información contenida en textos de diversa índole. Por ejemplo, para manejar la gran cantidad de artículos disponibles en cualquier plataforma, es necesario un sistema que clasifique estos textos y que, el usuario, haciendo una búsqueda pueda encontrar la información deseada. Este proyecto surge como un punto de partida en la investigación de técnicas de aprendizaje máquina para resolver el problema de clasificación de textos en función de su contenido (topic modeling). Los problemas que actualmente intentan resolver los algoritmos de ML se pueden dividir en tres grandes grupos: • Aprendizaje supervisado. En este caso, se busca obtener un dato de salida, llamada etiqueta, en función de los datos de entrada que se denominan características. Se dispone de un conjunto de datos de entrenamiento en los que las etiquetas son conocidas para poder llevar a cabo la primera fase del algoritmo, el aprendizaje. Las características pueden ser de distintos origen: edad, género de una persona, una imagen, textos, etcétera. Por otro lado, las etiquetas también pueden ser de diferentes clases: valores categóricos o no categóricos. • Aprendizaje no supervisado. En estos tipos de problemas se dispone de un conjuntos de datos de entrada a los que se les quiere extraer los patrones que siguen para poder así obtener información interesante. A diferencia del caso anterior, no se dispone de etiquetas definidas. Estos problemas no están tan bien definidos como los anteriores debido a que no se conoce a priori qué patrón se busca, por tanto, la dificultad se ve incrementada. • Aprendizaje con refuerzo. Es menos conocido que los anteriores y se basa en la idea de llevar a cabo el aprendizaje usando retroalimentación, feedback (Wiering, 2012). Se emplea en campos como la teoría de juegos, teoría de control, etcétera. A El verdadero progreso es el que pone la tecnología al alcance de todos -Henry Ford- Objetivo y Motivación 2 En un segundo nivel, más específico, se pueden diferenciar tres tipos de problemas de ML: • Clasificación. Es un tipo de problema de aprendizaje supervisado que se caracteriza por tener datos de salida categóricos, es decir, datos que toman valores reales de un conjunto previamente definido. Su objetivo es obtener un dato de salida, ) , en función de las características de entrada, * . Se pueden diferenciar dos tipos de clasificadores: binarios, en los que la salida puede tomar dos valores, y multiclase, en los que la salida toma diversos valores. Con el clasificador se busca una función que relacione las entradas con una salida: )=+(*) Esta función, sistema de clasificación, es desconocida y se desea encontrar aquella con la que se obtenga menor error de clasificación. Para ello, se emplea un conjunto de datos de entrenamiento cuyas etiquetas son conocidas y, posteriormente, se empleará esta función al resto de datos en los que la salida es desconocida. A esto se le llama generalización. Se debe obtener un clasificador que generalice correctamente a todos los datos de entrada. Figura 1. Ejemplo de clasificación usando support vector machine (SVM) • Regresión. Este tipo de problemas se diferencian de los de clasificación en que la salida es una variable continua. Algunos ejemplos de regresión son: la predicción de la bolsa, predicción de localización o predicción de la temperatura. Se pueden encontrar diversas clases: a. Regresión lineal, que realiza la predicción empleando una función lineal. b. Regresiones no lineales, que pueden usar funciones cuadráticas, polinómicas, radiales, … Figura 2. Ejemplo de Regresión • Clustering. Es un problema no supervisado en la que los datos no están etiquetados y que busca poner los datos de entrada en diversos conjuntos. El número de conjuntos o clusters, K, se encuentra definido por el usuario. En la actualidad, hay diversas técnicas que buscan obtener el número de 3 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas clusters de forma automática, haciendo que la intervención humana sea mínima. Hay diferentes modelos en función de cómo se deseen agrupar los datos: k-means, basado en centroides y la distancia de los datos a éstos; algoritmo expectation-maximization (EM) que emplea distribuciones estadísticas para definir los clusters. Figura 3. Ejemplo de clustering usando el algoritmo de K-means Otra clasificación de los métodos de ML se basa en el conocimiento de los parámetros de éstos. De esta forma, se distinguen dos modelos (Alpaydin, 2014): • Modelos paramétricos. En estos métodos, los parámetros del algoritmo están definidos en un conjunto finito. Por tanto, se puede ver que la intervención humana es necesaria. Tienen la ventaja de ser más rápidos. Sin embargo, cuentan con un mayor error por el factor humano. • Modelos no paramétricos. En estos métodos, no se definen previamente los parámetros, ofreciendo una mayor flexibilidad de los algoritmos. Sin embargo, estos modelos se hacen intratables para conjuntos de datos (dataset) muy extensos. Un ejemplo de modelo no paramétrico es el estimador K- NN (K- nearest neighbor). Este proyecto, como se ha mencionado anteriormente, tiene como objetivo clasificar unos documentos en función de su contenido. Es un problema en el que no se conoce previamente el tema del texto, sino que el usuario únicamente posee los textos como entrada para el algoritmo. Por tanto, con este proyecto se busca emplear técnicas de clustering para clasificar los documentos. Existen diversos métodos que pueden emplearse para extraer las palabras más significativas de los textos y diferenciarlos en función de éstas. Latent Dirichlet Allocation, Named-Entity Recognition o Word2vec son algunos de los algoritmos empleados en los problemas de Topic Modeling. En el siguiente apartado se realizará una introducción a los problemas de aprendizaje automáticos definidos como Topic Modeling. 1.1. Introducción a Topic Modeling En este apartado se tratará el problema de ML relacionado con el procesado de textos, en concreto, se introducirán algoritmos destinados a la extracción de información de dichos textos. Debido a la gran cantidad de datos y de contenido muy diverso de la que se dispone actualmente, el problema de minería de datos ha ido cobrando importancia en los últimos años. Hay una gran necesidad de diseñar algoritmos que procesen estos datos y extraigan información de forma eficiente (Aggarwal & Zhai, 2012). Estos algoritmos tienen como objetivo buscar patrones en los datos de forma dinámica y escalable. Entre las fuentes de información disponibles se encuentran: artículos científicos, periodísticos, correos electrónicos, publicaciones en redes sociales, … (Murphy, 2012)). Estado del Arte 10 Se suponen \ topics; ] palabras en el vocabulario; ^ _ ` , un vector de tamaño \ que se emplea como parámetro de la distribución de Dirichlet que define la proporción de los topics de cada documento y a , un escalar empleado en la distribución de Dirichlet que define la distribución de cada topic en función de las palabras (Blei & Lafferty, Topic Models, 2009). El algoritmo LDA se puede resumir en los siguientes pasos: 1. Para cada topic: a. Definir una distribución de las palabras. Q _ ` b~dAe](a) 2. Para cada documento: a. Definir un vector de proporciones de topic. f _ ` 0~dAe(^ _ ` ) b. Para cada palabra: i. Asignar un topic. Para ello se sigue una distribución multinominal. g0,=~<hUi j f _ ` 0 k ,g0,=∈{1,…,\} ii. Muestrear una palabra del vocabulario. Se escoge siguiendo una distribución multinomial. l0,=~<hUi m Q _ ` g0,= n ,l0,=∈{1,…,]} La siguiente figura, muestra un gráfico del modelo LDA, donde cada nodo representa una variable aleatoria y las flechas, las dependencias entre variables. Q ` 1:F representa la estructura de topics; f ` 1:p , las proporciones de cada topic por documento y B1:p,1:4 , la asignación de un topic a cada palabra. Como se ha mencionado anteriormente, el modelo LDA hace uso de la distribución de Dirichlet que pertenece a la familia de las distribuciones exponenciales y se caracteriza porque sus valores suman uno. El algoritmo LDA tiene dos variables Dirichlet, la proporción de los topics, f ` O , y la distribución de estos topics por el vocabulario, Q ` q . El modelo LDA proporciona la distribución conjunta de las variables aleatorias ocultas y observadas. Para hallar la descomposición de topics se calcula el posterior de las variables ocultas dados los documentos. r j f ` 1:p,B1:p,1:4,Q ` 1:F s 71:p,1:4,^,a)=C r j f ` 1:p,B ` 1:p,Q ` 1:F s 7 _ _ ` 1:p,^,a) ∫ ∫ r j f ` 1:p,B ` 1:p,Q ` 1:F s 7 _ _ ` 1:p,^,a) u _ _ ` v:w x _ _ ` v:y Esta expresión es intratable debido a la integral del denominador. Por tanto, es necesario aplicar métodos de aproximación. Cada una de ellas posee ventajas e inconvenientes, pero es muy importante elegir aquella en la que exista un compromiso entre la velocidad, la complejidad, la precisión y la simplicidad conceptual. Existen diversas técnicas: • Inferencia variacional de campo medio (D. M. Blei, 2003). Este método busca simplificar la expresión del posterior empleando una parametrización que se acerque al verdadero valor. Parte de la idea de que el motivo de que la expresión sea intratable es la dependencia existente entre las variables. Por tanto, se harán uso de unos parámetros con los que se conseguirá la independencia de dichas variables. ^ fO gO,z lO,z Qq a N D K Figura 8. Representación gráfica del modelo LDA 11 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Se asignará un parámetro a cada una de las variables. Finalmente, el cálculo del posterior se realiza con la siguiente expresión: {(f ` 1:p,B1:p,1:4,Q ` 1:F)= | { j Q ` q s F q}1 ~ ` q) |• {(f ` O|Ä ` O) | {(BO,z|Å _ ` O,z) 4 z}1 Ç p O}1 donde cada variable oculta se describe por una distribución: Q ` 1:F son los topics cuyos valores vienen dados por la distribución de Dirichlet de parámetro ~ ` q ; la proporción de los topics f ` 1:p viene dada por la distribución de Dirichlet de parámetro Ä ` O ; y la asignación del topic viene descrita por una distribución multinomial de parámetro Å _ ` O,z . Una vez calculado el posterior, la función objetivo a minimizar viene dada por la distancia Kullback- Leibler (KL): ÉeW min Ä _ ` 1:d,~ _ ` 1:\,Å _ _ ` 1:d,1::\á({ j f _ ` 1:d,B1:d,1::,Q _ ` 1:\ k ||Cr j f _ ` 1:d,B1:d,1::,Q _ ` 1:\ s 71:d,1::)) Esta función objetivo no es tratable y debe reemplazarse por otra que hace uso de los parámetros previamente introducidos: ℒ= I â ä logr j Q ` q s a) ã F q}1 + I â ä logr j f ` O s ^ ` ) ã p O}1 + II â ä logr j gO,z s f ` O) ã 4 z}1 p O}1 + II â ä logr j 7O,z s gO,z,Q ` 1:F) ã 4 z}1 p O}1 +å({) Donde å hace referencia a la entropía. • Muestreo de Gibbs (Griffiths & Steyvers, 2004). Método propuesto por Griffiths y Steyvers que toma muestras del posterior para aproximarlas con una distribución. Se considera uno de los métodos de Monte Carlo de cadenas de Markov (MCMC, Markov Chain Monte Carlo). Estos métodos construyen cadenas de markov con la distribución deseada a partir de una serie de muestras. El proceso de muestreo comienza tras la ejecución de un gran número de pasos para asegurar la estabilidad. Este método obtiene la distribución condicional de la variable latente B a partir de la expresión: G(B>=@|Bç>,7)∝ =ç>,? (éè)+Q =ç>,? (·) +lQ=ç>,? (Oè)+^ =ç> (Oè)+\^ donde: =−A,@ (7A) es el número de veces que aparece la palabra 7A en el topic @ =−A,@ (·) es el número total de palabras asignadas al topic @ =−A,@ (0A) es el número de palabras del documento 0A asignadas al topic @ =0A es el número total de otras palabras en el documento 0A Para realizar el muestreo se inicializa la variable BA a un valor comprendido entre 1 y el número total de topics \ y se va actualizando en cada iteración con la expresión. Tras numerosas iteraciones, cuando se alcanza una distribución estacionaria, se tomarán las muestras de BA . Estado del Arte 12 2.3 Hierarchical LDA (hLDA) Este modelo es una extensión del método LDA propuesto por Blei en 2003 (Blei, Griffiths, Jordan, & Tenebaum, Hierarchical Topic Models and the Nested Chinese Restaurant Process, 2013) que organiza los topics en una estructura en árbol en lugar de la estructura plana usada en LDA. Este modelo se caracteriza por combinar el cálculo del prior con la verosimilitud basándose en la variación jerárquica del LDA. Dado un corpus en el que cada documento contiene unas palabras, se busca descubrir los topics presentes en cada documento, organizándolos jerárquicamente. Emplea una aproximación bayesiana no paramétrica que permite construir el árbol de topics conforme van llegando los datos, este modelo se denomina nested Chinese Restaurant Process (nCRP) y es una adaptación del algoritmo CRP para emplearlo con jerarquías. Cada nodo de la estructura representa una variable aleatoria que tiene asociada la distribución palabra-topic. Este algoritmo tiene en cuenta dos consideraciones: se debe definir la profundidad del árbol y cada documento queda asociado a una rama de dicho árbol, aunque idealmente pueda pertenecer a varias. Considerando el conjunto de datos de entrada, corpus, formado por documentos que contienen palabras de cierto vocabulario, el modelo asume que estas palabras se han generado siguiendo un método de mezcla de palabras donde cada proporción, Cf, es aleatoria. Cada una de estas palabras está asociada a uno o varios topics, B . El modelo parte de un árbol previamente definido de L niveles y define un proceso de tres pasos para generar los documentos: • Primero, se elige un camino desde un nodo raíz a una hoja. • Segundo, se define un vector de proporciones de topics, Cf, siguiendo la distribución de Dirichlet. • Tercero, se generan las palabras del documento mediante una mezcla de topics desde el nodo raíz al nodo hoja empleando el vector previamente calculado, Cf . El algoritmo CRP se emplea para generar la estructura del árbol de forma aleatoria, define el prior de las proporciones de cada topic. Finalmente, el algoritmo hLDA puede estructurarse en: 1. Elegir el nodo raíz, ë1 2. Para cada nivel UC∈{2,…,á} : a. Elegir el nodo, ëU−1 , atendiendo a las expresiones del algoritmo de nCRP: r ( =V0VCVëhrÉ0VCAC | CrÉUÉíeÉìCreîïAÉì)=C ñ> Ä+ñ−1 r ( ìAWhAî=iîC=V0VC0îìVëhrÉ0VC | CrÉUÉíeÉìCreîïAÉì)=C Ä Ä+ñ−1 b. Elegir nodo ëU a partir del anterior. 3. Calcular el vector de proporciones de topics, f , empleando la distribución de Dirichlet. 4. Para cada palabra =C∈{2,…,:} : a. Seleccionar un topic BC∈{2,…,g} siguiendo la distribución multinomial. b. Seleccionar las palabras asociadas al topic ëB . Este modelo se ilustra en la siguiente figura, donde el nodo T hace referencia al conjunto infinito de ramas de L niveles creados con el algoritmo nCRP. Dado un T, la variable ëñ,U hace referencia al topic asociado al nivel U y al camino ñ . En el caso de que llegue un nuevo documento que no está reflejado en el árbol, se empleará el algoritmo nCRP para asociarlo a su camino. Se debe tener en cuenta que este nuevo documento puede compartir camino con otro documento previamente asociado, o partir de uno completamente nuevo. Esto se traduce en que el posterior de un nuevo documento puede depender del posterior de los documentos previamente procesados. 13 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Figura 9. Modelo hLDA (Blei, Griffiths, Jordan, & Tenebaum, Hierarchical Topic Models and the Nested Chinese Restaurant Process, 2013) Al igual que en el método LDA, el posterior requiere de una aproximación para poder ser calculable. En este caso, el método propuesto por Blei es el muestreo de Gibbs, detallado en el apartado anterior. Las variables necesarias son: 7ó,z , corresponde a la n-ésima palabra del m-ésimo documento; ëó,ò , el nodo correspondiente al l-ésimo topic en el m-ésimo documento; y Bó,z , que corresponde a la asignación de la n-ésima palabra del m-ésimo documento a uno de los L topics disponibles. Con el método de Gibbs se quiere muestrear las variables ëó,ò y Bó,z . El proceso de muestreo se divide en dos partes: 1. Muestrear Bó,z con el método descrito en LDA. 2. Dados los valores de las variables ocultas en LDA, muestrear ëó,ò , empleando el prior de CRP. La distribución de los L topics asociados al documento ñ viene dado por: r ( ôó | ö,ôçó,õ)C∝Cr ( öó | ô,öçó,õ)r ( ôó | ôçó)CC Para calcular la verosimilitud es necesario hacer la aproximación: r ( öó | ô,öçó,õ)=C | Γ m =ùû,ü,çó (·) +la n ∏ Γ m =ùû,ü,çó (é) +a n é ∏ Γ m =ùû,ü,çó (é) +=ùû,ü,ó (é) +a n é Γ m =ùû,ü,çó (·) +=ùû,ü,ó (·) +a n ° ò}1 donde: =ùû,ü,çó (é) es el número de veces que aparece la palabra 7 en el topic ëó,ò en los documentos que no sean el actual. l es el tamaño del vocabulario. Γ(·) es la función gamma estándar. 2.4 Dynamical Topic Model (DTM) Es un modelo publicado en 2006 (Blei & Lafferty, Dynamic Topic Models, 2006) y se presenta como una mejora del modelo LDA en el que se tiene en cuenta la evolución temporal de los topics en una colección de documentos. En los métodos propuestos anteriormente, los documentos se suponían independientes. Sin embargo, en numerosos textos la evolución temporal se considera un factor importante, por ejemplo, en los correos electrónicos, artículos periodísticos, etc. Por tanto, la fecha de los documentos que forman el corpus corresponde a un metadato empleado por el algoritmo. El modelo DTM separa los datos por fecha, por ejemplo, agrupándolos por año. Se modelan los documentos Estado del Arte 14 de cada grupo, teniendo en cuenta que los topics del grupo i evolucionan de los topics del grupo i−1 . Este método no emplea las distribuciones de Dirichlet, como lo hacían los modelos anteriores, debido a que no resulta manejable. En su lugar, usa una distribución Gaussiana de media ^ para el cálculo de proporciones de los topics. El proceso generativo para el grupo temporal i es: 1) Seleccionar los topics Qi|CQi−1~9(Qi−1,¢2£) 2) Calcular las proporciones ^i|C^i−1~9(^i−1,§2£) 3) Para cada documento: a. Definir a~9(^•,ɶ£) b. Para cada palabra: i. Calcular el topic gC~<hUi j ß ( a )k ii. Obtener la palabra asociada al topic li,0,=C~<hUi m ß j Qi,B kn La representación gráfica de este modelo, como puede apreciarse en la figura, es más compleja. Cada columna corresponde a un grupo temporal y puede apreciarse cómo se encuentran relacionadas. Figura 10. Representación gráfica del modelo DTM En incremento de la complejidad de este modelo hace que el cálculo del posterior sea intratable. Además, los modelos de aproximaciones empleados en los métodos estáticos no son adecuados, sino que requiere de otros más complejos que buscan optimizar los parámetros de las variables latentes empleando la divergencia KL respecto al valor real del posterior, incorporando el factor temporal. Los posibles métodos de aproximación son: • Variational Kalman Filtering. Este modelo no considera la existencia de topics, los cálculos son más simples Q ® i|CQi~9(Qi,© ™ i2£) . Seguidamente, empleando el filtro de Kalman se obtiene la media y la varianza del posterior y, se repiten los pasos para cada grupo temporal. • Variational Wavelet Regression. Emplea la descomposición de Wavelet para realizar las aproximaciones del posterior y el método de gradiente ascendente para obtener el óptimo. El modelo DTM ofrece la ventaja de la introducción de la variable temporal en los datos de entrada para obtener nuevas relaciones entre documentos. Sin embargo, también cuenta con algunos inconvenientes como son: el número de topics fijo, la discretización del tiempo o la complejidad del algoritmo que crece rápidamente con la granularidad del tiempo que afecta a la carga computacional. 2.5 Correlated Topic Model (CTM) Método propuesto por Blei en 2007 que mejora el modelo LDA introduciendo correlaciones entre topics (Blei 15 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas & Lafferty, A Correlated Topic Model of Science, 2007). En los modelos anteriores, cada uno de los topics se suponen independientes del resto. Con este modelo se quiere encontrar una estructura de documentos más compleja teniendo en cuenta las relaciones entre topics. Generalmente, este modelo se adapta mejor a los datos debido a la mayor información que se tiene en cuenta. CTM hace uso de distribuciones normales para el cálculo de las proporciones de los topics, permitiendo ver la correlación entre éstos. La notación que sigue este modelo es la siguiente: o 7O,z es la n-ésima palabra del documento d-ésimo. o Qq es la distribución del topic b o BO,zC se refiere a la asignación de un topic a la n-ésima palabra del d-ésimo documento. o fO es la proporción de cada topic del d-ésimo documento. Este modelo sigue el proceso generativo: 1) Estimar la distribución de los topics f=+ ( a ) =C ´¨≠C{Æ} ∑ ´¨≠C{Æè} è donde a sigue una distribución multinomial. 2) Para cada palabra de cada documento a. Asignar un topic BO,z|CaC~<hUi(fO) b. Asignar una palabra 7O,z| Ø BO,z,Q1:F ∞ ~<hUi(QJ±,≤) Este proceso se muestra en la siguiente imagen: Figura 11. Representación gráfica CTM Como puede observarse, este método es muy parecido al LDA salvo en la obtención de las proporciones de los topics. En este caso se emplea una distribución multinomial en lugar de la de Dirichlet. Al igual que en LDA, se emplea el método de aproximación de inferencia variacional de campo medio para calcular los parámetros de forma que la divergencia KL entra la aproximación y el verdadero posterior sea mínima. Sin embargo, al emplear distribuciones normales, este proceso se complica. 2.6 Parachinko Allocation Model (PAM) Método introducido en 2006 como alternativa a CTM (Li & McCallum, 2006). Al igual que este último, PAM tiene en cuenta las correlaciones entre topics para extraer la información oculta en los documentos. Sin embargo, para considerar las correlaciones se realiza una redefinición del concepto de topic. En este modelo se considera como una distribución tanto de las palabras como de otros topics. Para ello, hace uso del método conocido como directed acyclic graph, DAG, es un modelo en árbol, en el que cada nodo interno representa un topic que sigue una distribución de Dirichlet frente a sus hijos. Partiendo del nodo raíz, se muestrea uno de sus hijos siguiendo para ello la distribución multinomial y se continúa con el proceso hasta llegar a una hoja del árbol, una palabra. Estado del Arte 16 Figura 12. A la izquierda, representación gráfica del modelo PAM de 4 niveles. A la derecha, correlación en PAM de 4 niveles. (Li & McCallum, 2006) Al igual que el resto de modelos, es necesario aplicar una aproximación para el cálculo del posterior. PAM propone hacer uso del muestreo de Gibbs, método previamente presentado. PAM posee la ventaja de poder obtener correlaciones anidadas y no se restringe a usar la distribución normal. Además, soluciona el problema de escalado de CTM, donde únicamente se modela la correlación por pares. 2.7 Author Topic Model (ATM) Se publica en 2004 como una extensión del modelo LDA (Rosen-Zvi, Griffiths, Steyvers, & Smyth, 2004) y, posteriormente, es revisado en 2010. Se fundamenta en los mismos principios que los modelos anteriores, pero añade el uso de metadatos para extraer la información del autor del texto. Cada palabra de un documento se asociará a un topic y a un autor. Este modelo ve a cada autor como una distribución de topics y, al igual que en LDA, cada topic es una distribución de palabras. Con estos modelos se puede extraer más información de los documentos, por ejemplo, los temas sobre los que escribe determinado autor o qué autores escriben sobre un determinado tema. Parte de la idea de que un grupo de autores, É0 , deciden escribir sobre determinado tema. Cada palabra de esos documentos se elige por el autor siguiendo una distribución y, de la misma manera que en LDA, se elige el topic siguiendo una distribución tanto de palabras como de autores. En la siguiente figura se representa el modelo ATM. Figura 13. Modelo ATM 17 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas donde ; es el autor correspondiente a una palabra, 7 , elegido del conjunto É0 . Los pesos de cada autor se emplean para seleccionar el topic B y cada palabra se genera siguiendo la distribución Å . Como método de aproximación del posterior se emplea el muestreo de Gibbs debido a su simplicidad. En este caso, el número de variables latentes se incrementa. No sólo se considera la distribución de los topics, CB , sino que también se ha de tener en cuenta la distribución de los autores, ;. 2.8 Supervised LDA (sLDA) A diferencia de los modelos anteriores, sLDA es un método supervisado que surge en 2007 como extensión del LDA que añade una variable observable, etiqueta, a cada documento (Blei & McAuliffe, Supervised Topic Models, 2007). Busca resolver los problemas de predicción, es decir, el objetivo del algoritmo es obtener aquellos topics que mejor se adapten a futuros documentos no etiquetados. Este modelo deberá modelar no sólo los documentos, como hacía LDA, sino también la respuesta de cada uno. Por tanto, los pasos a seguir son: 1) Modelar las proporciones de topics. f ` O~dAe(^ ` ) 2) Para cada palabra: a. Asignar un topic. Para ello se sigue una distribución multinominal. gO,z~<hUi j f ` O k b. Elegir una palabra del vocabulario. Se escoge siguiendo una distribución multinomial. lO,z~<hUi j Q ` ¥±,≤ k 3) Modelar la respuesta: )~9(aµB ¶ ,¢¶) donde B ∑ =(1 : ∑ B= : ==1 ) Se puede observar que la única diferencia con el método LDA es la adición del modelado de la respuesta. La siguiente imagen muestra la representación gráfica de este modelo. Figura 14. Representación del modelo sLDA Por último, para realizar el cálculo del posterior se emplea el método de aproximación Expectation- Maximization (EM), al igual que en el modelo LDA. Con la diferencia de que es necesario añadir la variable respuesta. 2.9 Dirichlet Multinomial Regression (DMR) Modelo publicado en 2008 como extensión del LDA cuya idea principal es la incorporación de metadatos de los documentos aleatoria sin una codificación adicional (Mimno & McCallum, 2008). Al igual que sLDA, es un método de aprendizaje supervisado. La inclusión de los metadatos se realiza mediante un prior en las distribuciones que es una función de algunas características de los documentos, como son el autor, fechas o referencias. Dado un documento, 0 , sea ;0 un vector que contiene la característica que representa a los metadatos. Para cada topic, i , se dispone de un vector con la longitud del número de características, ~i . Con estos parámetros definidos, el modelo generativo de DMR es: 1) Para cada topic i : Estado del Arte 18 a. Estimar ~i~9 ( 0,¢2£ ) b. Estimar Åi~dAe ( Q ) 2) Para cada documento 0 : a. Definir para cada topic ^0i=expC(;0ª~i) b. Estimar la proporción de cada topic f0~dAe(^0) c. Para cada palabra A i. Estimar el topic asociado: BA~<hUi(f0) ii. Estimar las palabras asociadas al topic: 7A~<hUi(ÅBA) Este modelo incluye tres hiperparámetros: ¢2 , la varianza del prior; Q , parámetro de las distribuciones topicpalabra; y ª , el número de topics. Posteriormente, se debe calcular la verosimilitud. Para ello, es necesario aplicar el método de muestreo EM en el que en un paso se muestrea la asignación de topics a partir del topic actual dadas unas características y, en el otro, se optimiza ~ dada una asignación. 2.10 Topical N-Grams (TNG) Modelo definido en 2007 que, al contrario de LDA que supone que cada documento es un simple conjunto de palabras (bag of words), tiene además en cuenta la consideración de la relación secuencial entre las palabras, siendo capaz de modelar frases complejas (Wang, McCallum, & Wei, 2007). Por tanto, este método no sólo descubre los topics de un documento sino también frases relacionadas con el topic. El procedimiento de generación de palabras se puede ver en dos partes: primero, muestrea un topic asociado a dicha palabra y su estado como un bigram, una secuencia de dos elementos adyacentes; segundo, muestrea la palabra a partir de la distribución del bigram. La siguiente imagen muestra la representación de este modelo. Este esta figura puede apreciarse la introducción del bigram en la variable ¢ , que sigue una distribución multinomial de parámetro § , así como la variable º , que representa la distribución de las palabras teniendo en cuenta la palabra anterior. Figura 15. Representación gráfica del modelo TNG (Wang, McCallum, & Wei, 2007) Para la aproximación del posterior se emplea, al igual que en otros métodos anteriormente explicados, el muestreo de Gibbs. Como conclusión de TNG, es un modelo que emplea las relaciones semánticas permitiendo el modelado de conceptos o frases compuestas. Sin embargo, eso hace que los costes computacionales se vean incrementados considerablemente. 19 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 2.11 Aspect Hidden Markov Model (AHMM) Modelo presentado en 2001 como combinación de HMM y aspect model (AM) para la aplicación en procesado de lenguaje natural (Blei & Moreno, 2001). Este modelo ve a cada documento como una colección de palabras mutuamente independientes, cada una de estas palabras ha sido generada siguiendo un variable oculta que refleja el topic. AHMM segmenta un nuevo documento tomando palabras Vi con una ventana de tamaño L y empleando el algoritmo de Viterbi para encontrar la secuencia de topics B más probable en esta ventana. Para la aproximación se emplea el método EM. Figura 16. Representación de la segmentación AHMM (Blei & Moreno, 2001) 2.12 Named Entity Recognition (NER) Named Entity Recognition es un problema de ML que busca categorizar palabras importantes en un texto. Entre sus diversas aplicaciones se encuentra la extracción de información de los documentos para una posterior clasificación (Mohit, 2014). Los algoritmos NER se introdujeron por primera vez en 1996 en la sexta conferencia sobre entendimiento del mensaje (MUC – Message Understanding Conference). Antes de profundizar en los algoritmos es importante introducir el concepto Named Entity, que es una palabra o frase que identifica claramente una entidad (frase, párrafo, texto, etcétera) de otro conjunto con atributos parecidos. En MUC se definieron tres posibles etiquetas: • ENAMEX, que incluye tres tipos: personas, organizaciones y lugares. • TIMEX, que incluye fecha y tiempo. • NUMEX, que hace referencia al dinero, porcentaje y cantidad. Posteriormente, se introdujo otro estándar de etiquetado, denominado BIO, el cual utiliza las clases de la forma B – X, I – X y O, donde X es el nombre de una categoría (PER – persona, ORG – organización, LOC – localización), B corresponde al primer token (palabra) de la entidad X, I es un token de X que no es el primero y O, cuando no pertenece a ninguna categoría. Otra alternativa es el formato BILOU, donde L identifica al último token y U a una entidad de una única palabra. Originalmente, NER se empleaba para extraer personas, lugares y organizaciones. Sin embargo, con la entrada de otros dominios, es necesario introducir nuevos marcadores o clases. Existen dos posibles ramas de algoritmos NER: basados en reglas y estadísticos. En los siguientes apartados se introducen cada uno de ellos. 2.12.1 NER basado en regla Son los primeros sistemas de reconocimiento de entidades y emplean reglas manuales para detectar las entidades. La mayoría de estos sistemas presentan los siguientes componentes: 1) Reglas para la extracción de entidades 2) Diccionarios geográficos, gazeteers 1 , para los diferentes tipos de las clases de entidades 1 Gazeteers es un término empleado normalmente para referirse al léxico específico de un dominio. Antecedentes 26 mesa ocupada con probabilidad proporcional al número de clientes anteriores o en una mesa desocupada con probabilidad proporcional a Ä : œ r ( ñîìÉCVëhrÉ0ÉCAC | ëUAî=iîìCÉ=iîeAVeîì)=C =A Ä+=−1 r ( ìAWhAî=iîCñîìÉC0îìVëhrÉ0É | ëUAî=iîìCÉ=iîeAVeîì ) =C Ä Ä+=−1 donde =A es el número de clientes que actualmente están sentados en la mesa A y = , el número de clientes que hay actualmente en el restaurante. Se puede observar cómo a mayor valor de Ä , mayor número de mesas ocupadas, es decir, menos clientes por mesa. En el caso de topic modeling se traduciría en que habría un mayor número de topics y menos documentos en cada uno. Por tanto, se concluye que los temas serían más específicos y, por tanto, habría menos documentos en cada uno. La siguiente figura muestra un ejemplo de asignación de mesas con el algoritmo CRP. Figura 20. Representación de algoritmo CRP (Gershman & Blei, 2011) Tras sentarse : clientes, tenemos una partición de : elementos cuya estructura es similar a la obtenida con los procesos de Dirichlet. Si se asume que cada mesa se caracteriza por el parámetro fA que sigue una distribución, cada cliente se asociará al parámetro de la mesa en la que se siente. El resultado es una secuencia de estos parámetros que puede verse como un clustering probabilístico. Con el modelo CRP es posible determinar el número de clusters (número de mesas ocupadas) a partir de los datos y, posteriormente, permite asignar a estos clusters nuevos datos. Este método es muy útil para los algoritmos de topic modeling, por ejemplo, LDA, debido a que se pueden establecer relaciones uno a uno entra las mesas y los componentes del algoritmo. Sin embargo, en modelos de jerarquía, como HLDA, se emplea una extensión de CRP, denominada Nested Chinese Restaurant Process (nCRP) debido a que cada dato se puede asociar a múltiples componentes de la jerarquía. Una característica del modelo CRP es su intercambiabilidad de su distribución. Esto quiere decir que dicha distribución no depende del orden de llegada de los clientes. Esta propiedad es muy importante para el cálculo del posterior ya que permite el uso de técnicas de Monte Carlo para hacerlo más manejable. 3.4 Nested Chinese Restaurant Process Como se ha mencionada anteriormente, es una extensión del algoritmo CRP que se emplea en el modelado de topics jerárquico. nCRP se puede definir suponiendo el escenario donde hay un número infinito de restaurantes chinos de infinitas mesas en una ciudad. Uno de estos restaurantes será el nodo raíz y en cada una de sus infinitas mesas habrá una tarjeta con el nombre de otro restaurante. En todos los siguientes restaurantes sucederá lo mismo, tendrán en cada una de sus mesas una tarjeta de otro restaurante. Se supondrá que cada restaurante se refiere una única vez. Por tanto, los restaurantes de la ciudad se organizan en un árbol de infinitas ramas, donde cada uno de ellos se asocia a un nivel en el árbol. Cada vez que un cliente entra en un restaurante elige una mesa 27 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas siguiendo el proceso de CRP. Un ejemplo es un turista que llega a una ciudad y en su primera noche entra en el restaurante raíz donde elige sentarse en una mesa determinada por CRP. La segunda noche se dirige al restaurante recomendado por la tarjeta de la mesa en la que se sentó y allí elige otra mesa. Esto se repite durante L días cuando el cliente tiene un conjunto de L restaurantes visitados que constituyen un trayecto desde el nodo raíz hasta el L-ésimo restaurante. Si este proceso lo repiten M turistas, el conjunto de trayectos forman un árbol de L niveles. Esta distribución se emplea como prior en el modelado de topics jerárquico en el que cada documento describe uno de los trayectos del árbol. La siguiente figura muestra la estructura en árbol del modelo nCRP donde cada nodo representa uno de los restaurantes. Puede apreciarse cómo cinco clientes llegan al primer restaurante y se sientan en determinadas mesas que los llevan a otro restaurante. Figura 21. nCRP de tres niveles (Blei, Griffiths, & Jordan, 2010) 4 ALGORITMO IMPLEMENTADO. HLDA Those who can imagine anything, can create the impossible - Alan Turing - n este capítulo se desarrollará el algoritmo implementado para resolver el problema de topic modeling. Ese modelo se denomina Hierarchical Latent Dirichlet Allocation, hLDA, y emplea los métodos descritos en el capítulo anterior para elaborar una estructura jerárquica en árbol con los topics de los documentos empleados como datos de entrada. Cada nodo se corresponde a un topic y cada documento poseerá tantos topics como nodos tenga su trayecto. El algoritmo LDA definido en el Capítulo 2 define los topics como distribuciones de probabilidad sin relación entre ellos. Esto presenta el inconveniente de que se desconoce el nivel de abstracción de los topics así como la posible relación entre ellos. Estos problemas se solucionan con el uso de nCRP, que sirve como base para el modelo hLDA. El algoritmo nCRP permite definir el prior en una topología en árbol sin limitar la ramificación o profundidad del árbol, de forma que los topics más genéricos se encuentran situados en los nodos más cercanos al raíz y los más específicos, alrededor de las hojas del árbol. Una vez definido el modelo se empleará una inferencia probabilística para identificar tanto los topics como las relaciones entre éstos. Se considerará un conjunto de datos formado por un corpus de documentos. Cada documento es una colección de palabras y cada palabra forma parte de un vocabulario. hLDA asume que las palabras de un documento se han generado conforme a un modelo probabilístico. Considerando la variable multinomial, B , y el conjunto de distribuciones asociadas a cada palabra, r(7|B,Q) donde Q es un hiperparámetro. Este conjunto de distribuciones conformará los topics del documento. Cada documento pertenecerá a un topic con cierta probabilidad, f . Temporalmente se asume un conjunto de topics finito, \ . Por tanto, la variable B tomará valores entre los \ posibles topics y f será un vector de \ dimensiones que define la probabilidad de pertenencia a cada topic. Definidos estos parámetros, el algoritmo LDA se define como un proceso generativo de dos niveles en los que cada documento se asocia a cada topic con una determinada proporción y el corpus se modela como una distribución de Dirichlet de estas proporciones. Los dos niveles son: 1) Elegir un vector f . 2) Para cada documento, muestrear palabras siguiendo la distribución r(7|f) para el valor escogido de f . Puede apreciarse la independencia existente entre topics. Como alternativa, se propone el modelo hLDA donde se supone que se parte de un árbol de á niveles en el que cada nodo es un topic. Un documento se genera siguiendo este proceso: 1) Elegir un camino desde el nodo raíz al nodo hoja. 2) Estimar el vector de proporciones de topics f a partir de la distribución de Dirichlet de á dimensiones. 3) Generar las palabras del documento a partir de los topics presentes en el camino desde el nodo raíz a la hoja. Finalmente, se empleará el algoritmo nCRP para relajar la condición de estructura fija del árbol, calculando el prior. Un documento se genera primero eligiendo un camino del árbol de á niveles y se escogen las palabras atendiendo a los á topics asociados a dicho camino. E Algoritmo Implementado. hLDA 30 Formalmente, considerando el árbol infinito construido por nCRP y definiendo ë0 como el camino trazado por el 0 -ésimo documento, el modelo hLDA tiene el siguiente proceso generativo: Algoritmo hLDA 1) Para cada mesa del árbol infinito bC∈C– : a) Estimar su topic asociado a partir de la distribución de Dirichlet: QqC~CdAe(a) 2) Para cada documento del corpus 0∈{1,2,…,d} : a) Elegir un camino del árbol siguiendo el algoritmo nCRP: ëOC~C=—“G(Ä) b) Estimar la proporción de cada topic de su rama del árbol: fO|[ñ,ß]~Ãâ<(ñ,ß) c) Para cada palabra: i. Elegir un nivel/topic: gO,zC|CfOC~dAìëeîiî(fO) ii. Elegir una palabra según el nivel/topic en el que se encuentre: lO,zCsC{gO,z,ëO,Q∞~dAìëeîiî(Qù±ägO,zã) que se encuentra parametrizado por el topic gO,z del camino ëO Cabe mencionar que los componentes probabilísticos son variables latentes, por ejemplo, los topics. Esto quiere decir que no se asumen unos topics predefinidos sino que se infieren estos valores a partir del posterior, condicionado al corpus de documentos y a las probabilidades de las variables latentes. Por ejemplo, suponiendo que 0 documentos han sido previamente generados, el documento 0+1 puede seguir uno de los trayectos del árbol previamente definido o crear uno nuevo. Por tanto, el número de parámetros del modelo propuesto puede crecer, según el corpus. Esta flexibilidad permite optimizar el posterior para finalmente obtener el árbol que mejor se ajuste al conjunto de datos de entrada. Sin embargo, existen otros parámetros que deben ser previamente definidos: el número de niveles del árbol o la forma son algunos ejemplos. Éstos se conocen como hiperparámetros. Por ejemplo, el parámetro de la distribución de Dirichlet, a , define la dispersión de los topics, es decir, a menor valor, los topics estarán formados por menos palabras lo que llevará a soluciones donde los árboles son más grandes. Se debe considerar que el valor de estos parámetros depende en gran medida del corpus de documentos. Por tanto, es muy importante hacer un análisis con distintos valores hasta obtener aquellos que mejor se ajusten a los datos. En el siguiente capítulo se mostrarán los distintos resultados obtenidos para diversos valores de los hiperparámetros. 4.1 Inferencia probabilística Tal y como se ha mencionado anteriormente, una vez seguido el proceso generativo de documentos, se deberá realizar la optimización del modelo hasta conseguir el árbol que mejor se ajuste a los datos, es decir, obtener el árbol que mejor estime la estructura de topics oculta en los documentos. Esta optimización se conoce como inferencia probabilística y empleará el posterior. Sin embargo, la expresión del posterior no resulta tratable y deben emplearse técnicas de aproximación. En el caso propuesto, se hará uso del muestreo de Gibbs colapsado, un algoritmo MCMC (Markov Chain Monte Carlo) en el que las variables latentes se muestrean iterativamente condicionadas a las observaciones y que marginaliza algunas de ellas para acelerar la convergencia. Se muestrearán los trayectos por documentos y las asignaciones de topics por nivel y se marginalizarán los parámetros de Dirichlet, Qq , y de proporciones de topics, fO . Con esto se aproximará el posterior r(ë1:p,B1:p|Ä,a,ñ,ß,71:p) donde Ä define la tendencia de los clientes de compartir mesa en cada restaurante, a refleja la varianza de topics y ñ y ß , la asignación de palabras en los distintos niveles. El algoritmo se divide en dos partes principales: el muestreo de asignación de niveles y el muestreo de asignación de trayectos. 31 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 4.1.1 Muestreo de asignación de niveles Dada una elección de trayecto, se deberá muestrear la asignación de la variable de asignación de topics por niveles, B0,= , que para la palabra = del documento 0 sigue la expresión: r(BO,z|Bç ( O,z ) ,ë,7,ñ,ß,a)∝r(BO,z|BO,çz,ñ,ß)r(7O,z|B,ë,7ç ( O,z ) ,a) donde B− ( 0,= ) y 7− ( 0,= ) son los vectores de asignación de niveles y de palabras observadas, extrayendo B0,= y 70,= , respectivamente. La primera parte de la expresión es una distribución de niveles que, al tener un número infinito de componentes, se muestrea por etapas. Primero se muestrea de una distribución de todo el espacio de niveles presente en el documento y un nivel más profundo al actual. r j BO,z=b s BO,çz,ñ,ß k =â ” ]q |j 1−]? k |BO,çz,ñ,ß qç1 ?}1 ‘ =â ä ]q s BO,çz,ñ,ß ã| â[ j 1−]? k |BO,çz,ñ,ß qç1 ?}1 =Cñß+#[BO,çz=b] ß+#[BO,çz≥b] |( 1−ñ ) ß+#[BO,çz>@] ß+#[BO,çz≥@] qç1 ?}1 donde #[·] cuenta los elementos que cumplen determinada condición. La segunda parte de la expresión es la probabilidad de una palabra basado en su asignación. r j 7O,z s B,ë,7ç ( O,z ) ,a k ∝#[Bç ( O,z ) =BO,z,ëJ±,≤=ëO,J±,≤,7ç ( O,z ) =7O,z]+Ca 4.1.2 Muestreo de trayecto Dadas las variables de elección de nivel, se muestrea el trayecto asociado a cada documento condicionado a los otros trayectos y palabras observadas. Para ellos, la expresión que se sigue es: r(ôO|ö,ôçO,õ,a,Ä)∝r(ôO|ôçO,Ä)r(öO|ô,öçO,õ,a) Esta expresión puede verse como una instancia del teorema de Bayes donde r(öO|ô,öçO,õ,a) es la probabilidad de una palabra dada una asignación de trayecto y r(ôO|ôçO,Ä) es el prior de trayectos definido con nCRP. La probabilidad de los datos se obtiene integrando los parámetros multinomiales, derivando en la siguiente expresión: r ( öO | ô,öçO,õ,a ) = | Γ( ∑ #[õçO=U,ôçO,ò=ëO,ò,öçO=7] é+]a) ∏ Γ( é#[õçO=U,ôçO,ò=ëO,ò,öçO=7]+a) ∏ Γ( é#[õ=U,ôò=ëO,ò,ö=7]+a) Γ( ∑ #[õ=U,ôò=ëO,ò,ö=7]+]a é) ÷◊¨C(J±) ò}1 Se debe tener en cuenta que cada trayecto de define en bloque debido a que su valor en cada nivel depende del anterior. 4.1.3 Algoritmo de muestreo de Gibbs Una vez definidos los pasos a seguir, el algoritmo de muestreo de Gibbs se resume en: dado el estado actual, ÿ ë1:p ( • ) ,B1:p ( • )Ÿ, se muestrea iterativamente cada variable condicionada al resto: Algoritmo Implementado. hLDA 32 Algoritmo de muestreo de Gibbs 1) Para cada documento del corpus 0∈{1,2,…,d}: a) Estimar aleatoriamente ë0(i+1)empleando: r(ôO|ö,ôçO,õ,a,Ä)∝r(ôO|ôçO,Ä)r(öO|ô,öçO,õ,a b) Estimar aleatoriamente B=,0 (i+1)empleando: r(BO,z|Bç(O,z),ë,7,ñ,ß,a)∝r(BO,z|BO,çz,ñ,ß)r(7O,z|B,ë,7ç(O,z),a) para cada palabra =∈{1,2,…,:O} La distribución estacionaria de la cadena Markov correspondiente es la distribución condicional de las variables latentes en el modelo hLDA dado el corpus. Tras varias iteraciones del algoritmo se alcanza una distribución estacionaria y se comienza a extraer muestras en determinados intervalos seleccionados para minimizar la autocorrelación y aproximar el verdadero posterior con la distribución empírica correspondiente. 4.2 Implementación del algoritmo Una vez definido el modelo implementado, en este apartado se presenta la estructura del código. El lenguaje de programación elegido para la implementación ha sido Python debido a la multitud de librerías de las que dispone y al ser un lenguaje que ha ido cobrando gran importancia en los últimos años. Las librerías que se han empleado en el código han sido: 1. numpy. Importa operaciones matemáticas. 2. csv. Se emplea para leer/escribir ficheros .csv. 3. math. Contiene funciones matemáticas. De aquí se importará la función log. 4. sys. Se empleará en la salida por línea de comandos de los resultados. 5. re. Se empleará para el uso de expresiones regulares. Para transformar el vocabulario de la base de datos en un formato adecuado para su posterior procesado. 6. scipy. Para importar además de las operaciones de numpy, otras estadísticas. Este código se estructura en varias funciones presentadas en la siguiente tabla. Interfaz Descripción main() Función principal del programa. En ella se llaman al resto de funciones. convert_doc_to_list(doc_index, doc_words) Esta función se emplea para construir el corpus de documentos con el formato adecuado. load_vocab(vocab_file) Esta función carga el vocabulario empleado en el corpus de documentos. load_corpus(corpus_file) Esta función carga el corpus de documentos y lo transforma hasta conseguir el formato adecuado para el algoritmo. HierarchicalLDA(corpus, vocab, alpha, gamma, eta, num_levels) Clase donde se definen las distintas funciones que se emplearán en el algoritmo hLDA. 33 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas nCRP_node(num_levels, vocab, parent, level) Clase que define a un nodo del árbol resultante del algoritmo nCRP. Todas estas funciones y clases han sido desarrolladas en este proyecto, excepto convert_doc_to_list(doc_index, doc_words) que se ha reutilizado de un código de libre acceso el cuál hace uso de una de las bases de datos empleadas en este proyecto (GitHub, s.f.). La siguiente figura muestra el diagrama de flujo de la función principal main(). Figura 22. Diagrama de flujo de main() 4.2.1 nCRP_node Es una clase donde se definen las distintas funciones que se emplean en la creación del árbol de topics. Estas funciones son: 1. add_child. Añade un nuevo nodo al árbol. 2. check_leaf. Comprueba si un nodo es una hoja o no, es decir, si pertenece o no al último nivel. 3. add_new_path. Añade nodos hasta llegar a la hoja (último nivel). 4. remove_path. Elimina un documento de un camino. 5. remove_child. Elimina un nodo hijo. 6. add_to_path. Añade un documento el camino. 7. select_node. Elegir un nodo o crear uno nuevo cuando llega un nuevo documento. Base del algoritmo nCRP. 8. get_top_words. Obtiene las palabras más usadas en un topic. 4.2.2 HierarchicalLDA Es una clase donde se definen las distintas funciones que se emplean en el algoritmo hLDA. Este algoritmo se estructura en diversas partes: Algoritmo Implementado. hLDA 34 1. Inicializar un camino, fijando un nodo raíz. 2. Para cada documento del corpus, recorrer cada nivel e ir fijando su camino en el árbol de topics. Para ello se llamará a la función select_node definida en el apartado anterior. Finalmente, se recorre cada palabra del documento y se asigna a un nodo de su camino. 3. Estimación y optimización de la solución aplicando el muestreo de Gibbs. La Figura 23 muestra el diagrama de flujo de la clase HierarchicalLDA, donde se inicializan variables y se forma el árbol de topics. Figura 23. Diagrama de flujo de la creación del árbol de topics Dentro de esta clase se definen a su vez otras funciones que se emplean en la parte de estimación y optimización del algoritmo. Estas funciones son: 1. estim_path. En esta función se implementa el algoritmo de muestreo de Gibbs, donde se recorre cada documento y se muestrea el camino, llamando a la función sample_path. Finalmente, se muestrea el topic asociado a cada palabra del documento haciendo uso de la función 35 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas sample_topics. 2. sample_path. Define el camino que sigue un documento desde el nodo raíz hasta la hoja. Calcula la aproximación de la verosimilitud para esa solución. 3. calculate_prior. Calcula el prior del camino siguiendo el algoritmo nCRP. 4. calculate_doc_likelihood. Calcula la verosimilitud de un documento. 5. calculate_word_likelihood. Calcula la verosimilitud de una palabra, siguiendo la ecuación definida en apartados anteriores. 6. sample_topics. Muestrea el topic al que pertenece cada palabra del documento. Figura 24. Diagrama de flujo de la estimación del camino Por último, se definen dos funciones que se emplean en la representación de los resultados: 1. print_node. Imprime la información de cada nivel: topic, número de documentos en el topic, palabras más usadas en el topic y el número de repeticiones de dichas palabras. 2. print_nodes. Se emplea en la función estim_path y llama a su vez la print_node para mostrar por pantalla los resultados del algoritmo. Resultados. Análisis de Parámetros 42 49 696 (231 de los cuales no tienen coincidencia de palabras, por tanto, se quedan en el nivel 48) Tabla 8. Resumen de los resultados del caso de estudio 2 5.1.1.3 Caso de estudio 3 En este tercer caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 0.5 1 2 Tabla 9. Hiperparámetros del caso de estudio 3 Los resultados correspondientes a algunas ramas del árbol obtenidos en este caso se resumen en la siguiente tabla. Nivel Rama Topic Número de documentos Palabras más empleadas 0 0 0 1499 studentship, teaching, overlapped, committees, replicas, physic, ensembles, biasing, phased, sabes 1 - 44 0 379 - 561 1499 Bootstrapping, visualisation, modeled, cellular, place, directional, responses, eyes, boundaries, vectorial, problematic, resultant, functional, algorithmic, learnt 45 1 562 525 translates, parallelizable, visit, movie, learn, hornik, prototypes, analysis, puddle, france 46 1.1 563 278 davies, johnson, jan, thompson, geometric, alleviate, michalski, manipulated, rohwer, meador 47 1.1.1 564 196 learnt, traced, ilk, dates, semiparametric, continuing, laughton, tissues, regularizer, nature 48 1.1.1.1 565 189 asa, multimodal, obscure, parcor, ternational, flexibility, rounded, system, ibl, esti 49 1.1.1.1.1 566 169 circuitry, chir, analogical, curried, vlvp, outseg, voltages, neuronal, implemented, systematic 49 1.1.1.1.2 665086 7 * En este caso ninguna palabra coincide con el texto. Esto significa que esos siete documentos tendrían 48 topics 49 1.1.1.1.3 666106 4 thomas, rub, tinmann 49 1.1.1.1.4 666832 2 quantization, competitor 49 1.1.1.1.5 666884 7 trivially, structuring, detectable, nonparametric 43 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 48 1.1.1.2 662090 4 multilayered, simplified, cup, sized, restore, memoryless, blind, reasoning, plausible 49 1.1.1.2.1 666482 1 * En este caso ninguna palabra coincide con el texto. Esto significa que ese documento tendría 48 topics 49 1.1.1.2.2 666753 3 composed, going Tabla 10. Resultados del caso de estudio 3 Finalmente, en la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 44 1 45 7 (1 de los cuales no tiene coincidencia de palabras. Por tanto, esos documentos se quedan en el nivel 44) 46 34 (2 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 45) 47 135 (45 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 46) 48 391(182 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 47) 49 804 (444 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 48) Tabla 11. Resumen de los resultados del caso de estudio 3 5.1.1.4 Caso de estudio 4 Los valores de los hiperparámetros analizados en este caso son los siguientes: ⁄ € ‹ 0.2 1 2 Tabla 12. Hiperparámetros del caso de estudio 4 Los resultados obtenidos en este caso se resumen en la siguiente tabla. Al igual que en el apartado anterior, se ha representado únicamente algunas ramas del árbol de topics devuelto por el algoritmo. Nivel Rama Topic Número de documentos Palabras más empleadas 0 0 0 1499 circuitry, chir, analogical, curried, outseg, vlvp, voltages, neuronal, systematic, implemented 1 - 33 0 97 - 21008 1499 Dynamical, pointed, functional, algorithmic, learnt, controllable, problematic, optimally, systematic, methologies, parameterised, distributional, database, modeled, boundaries, Resultados. Análisis de Parámetros 44 objection, cellular 34 - 40 1 21010- 21016 1498 Genetically, poral, played, fitted, classifies, neighborhood, decisive, gamma, gramatical, representational, symbolic, stringent, languages 41 1.1 21017 1497 entire, phased, autoassociation, variance, legal, burke, breast, complex, scale, sram 42 1.1.1 21018 1492 book, essential, systematic, jude, recorded, agglomerative, ima, cybern, similarities, helpful 43 1.1.1.1 21019 1045 arrangement, structuring, entries, recommendation, simard, commanded, carry, similarly, comfort, dealt 44 1.1.1.1.1 21020 239 improved, nonterminal, green, diffusive, postsubiculum, home, highlight, decides, crosscorrelation 45 1.1.1.1.1.1 21021 78 psychologically, trajec, compartment, uncorrelated, calif, harder, supported, competence, shaped, biological 46 1.1.1.1.1.1.1 21022 62 modules, exclusive, official, pendulum, york, lwpcr, explanatory, sirosh, som 47 1.1.1.1.1.1.1.1 21023 45 hikaridai, intelli, appealing, iteratively, generafive, invest, subsequence, settle, pursuing, redefine 48 1.1.1.1.1.1.1.1.1 21024 13 shapley, freq, nel, sardnet 49 1.1.1.1.1.1.1.1.1.1 62299 11 davies, michalski, johnson, richardson, petersen, autistic, indexed, thompson, erkki, williamson 49 1.1.1.1.1.1.1.1.1.2 1598221 2 * En este caso ninguna palabra coincide con el texto. Esto significa que esos dos documentos tendrían 48 topics 48 1.1.1.1.1.1.1.1.2 1589571 31 * En este caso ninguna palabra coincide con el texto. Esto significa que esos 31 documentos tendrían 47 topics 48 1.1.1.1.1.1.1.1.3 1596164 1 metrical, stably Tabla 13. Resultados del caso de estudio 4 Finalmente, en la siguiente tabla se muestran el número de niveles obtenidos en este caso de estudio para realizar comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 33 1 45 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 34 - 40 2 (1 de los cuales no tiene coincidencia de palabras. Por tanto, ese documento se queda en el nivel 33) 41 3 (2 de los cuales no tiene coincidencia de palabras. Por tanto, esos documentos se quedan en el nivel 40) 42 4 (3 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 41) 43 8 (3 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 42) 44 17 (8 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 43) 45 59 (18 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 44) 46 173 (90 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 45) 47 410 (282 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 46) 48 746 (597 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 47) 49 1101 (903 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 48) Tabla 14. Resumen de los resultados del caso de estudio 4 5.1.1.5 Conclusiones tras la variación del hiperparámetro ⁄ Tras la realización de diversos experimentos, cambiando el valor del hiperparámetro ^ , se pueden llegar a las siguientes conclusiones: 1) A mayor valor de ^ , hay menor número de niveles más altos. Esto quiere decir que la clasificación es menos selectiva y se centra en extraer temas más genéricos o comunes a un mayor número de documentos. 2) En el caso de una clasificación más selectiva, es decir, menores valores de ^ , hay una mayor variedad de topics. Sin embargo, se ha de considerar que el número de documentos que se quedan en niveles más altos es mayor. Esto se puede traducir a que, debido al carácter específico de los temas, hay muy pocos documentos que cumplan esos criterios de pertenencia. La siguiente figura muestra una comparativa de los casos de estudio del hiperparámetro ^. Cada columna representa el número de topics diferentes existentes en cada nivel, cada topic puede tener uno o más documentos. Por ejemplo, el caso de estudio 4 posee 41 topics distintos en el nivel 45 del árbol. Resultados. Análisis de Parámetros 46 Figura 26. Gráfica comparativa de distintos valores del hiperparámetro ^ 5.1.2 Análisis del hiperparámetro € En este apartado se llevará a cabo un estudio del hiperparámetro Ä presente en el algoritmo implementado. En este caso, esta variable afecta al método nCRP, encargado de la formación del árbol de topics. En los siguientes sub-apartados se presentan los diversos casos de estudio. 5.1.2.1 Caso de estudio 5 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 2 2 Tabla 15. Hiperparámetros del caso de estudio 5 Los resultados obtenidos en este caso se resumen en la siguiente tabla. Al igual que en el apartado anterior, se ha representado únicamente algunas ramas del árbol de topics devuelto por el algoritmo. Nivel Rama Topic Número de documentos Palabras más empleadas 0 0 0 1499 proctolin, blocked, instructive, parallelism, built, stark, simi, communities, operational, bob 1 - 31 0 50 - 53160 1499 Stringent, symbolic, gramatical, languages, trees, known, contextual, recognizable, modeled, inquiry, learnt, neurally, unitary, analogical, visualisation, objection, features, characterised 32 - 39 1 53161- 53168 1498 Prototypical, fundamentally, database, algorithmic, functional, parameterised, 1 1 1 3 6 32 139 454 1 1 1 2 7 53 207 465 1 1 1 6 32 90 209 360 1 5 9 41 83 128 149 198 0 -42 43 44 45 46 47 48 49 COMPARATIVA ALPHA nº niveles caso 1 nº niveles caso 2 nº niveles caso 3 nº niveles caso 4 47 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas methologies, boundaries, theoretic, resultant 40 - 45 1.1 53169- 53174 1497 Labelling, stressed, syllables, templates, learnable, shared, marking, primate, perpendicular, classifies, decisive 46 1.1.1 53175 1062 styles, context, bilistic, stylistic, median, illegal, asymmetrical 47 1.1.1.1 53176 221 spaces, proving, angles, numerous, patrice, dependences, run, entirely, neurophysiol, brauer 48 1.1.1.1.1 53177 125 Anand, rotating, parametrization, regard, illustrates, ret, hrtf, simmon, actuator, restart 49 1.1.1.1.1.1 53178 107 controllable, modeled, motorola, moves, controlling, arma, inversely, tral, foster, dynamical 49 1.1.1.1.1.2 308497 4 believe, innate, testable, severity, eta 49 1.1.1.1.1.3 310200 4 prototypes, graz, maryland, frg, generically, string, templates, noiseless 49 1.1.1.1.1.4 312111 4 gang, addemup 49 1.1.1.1.1.5 312258 3 * En este caso ninguna palabra coincide con el texto. Esto significa que esos tres documentos tendrían 48 topics 49 1.1.1.1.1.6 312375 1 Denoting, kanji 49 1.1.1.1.1.7 312588 2 Symbolic, circles Tabla 16. Resultados del caso de estudio 5 Finalmente, en la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 31 1 32 - 39 2 (1 de los cuales no tiene coincidencia de palabras. Por tanto, ese documento se queda en el nivel 31) 40 - 45 3 (2 de los cuales no tiene coincidencia de palabras. Por tanto, esos documentos se quedan en el nivel 39) 46 5 (2 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 45) 47 25 (3 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 46) 48 159 (15 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 47) Resultados. Análisis de Parámetros 48 49 596 (194 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 48) Tabla 17. Resumen de los resultados del caso de estudio 5 5.1.2.2 Caso de estudio 6 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 0.5 2 Tabla 18. Hiperparámetros del caso de estudio 6 Los resultados obtenidos en este caso se resumen en la siguiente tabla donde se muestran únicamente algunas ramas del árbol de topics devuelto por el algoritmo. Nivel Rama Topic Número de documentos Palabras más empleadas 0 0 0 1499 functional, algorithmic, learnt, setpoint, database, erties, vectorial, pointed, methodologies, problematic 1 - 42 0 1 - 3815 1499 Inquirí, unitary, neurally, learnt, weighted, systematic, recognizable, contextual, boundaries, controllable, static, optimality, frequent, modeled, characterised, objection, recognizable, features 43 1 3816 1133 relative, sufficiently, arising, operated, gilk, consequent, brownian, rationale, visited, turner 44 1.1 3817 1133 formulas, tively, ascertain, albrecht, accurately, frequently, alternatively, arithmetic, proposing, generatire 45 1.1.1 3818 474 decayed, setting, carrying, delusion, blackburn, lin, define, adjustable 46 1.1.1.1 3819 220 discussed, gest, fractal, lag, larly, branching, kirkpatrick, flatness, lowe, assimilation 47 1.1.1.1.1 3820 204 steepest, supply, bhalla, pattern, favored, generation, sinh, proce, agation, consecutively 48 1.1.1.1.1.1 3821 178 intention, talker, areas, johnson, houghton, obtaining, laminar, scanning, phasic, circuitry 49 1.1.1.1.1.1.1 3822 164 circuitry, chir, analogical, curried, outseg, voltages neuronal, implemented, systematic 49 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 49 1.1.1.1.1.1.2 53263 12 davies, michalski, Johnson, richardson, petersen, indexed, autistic, thompson, erkki, pause 49 1.1.1.1.1.1.3 410545 2 Theoretically, space, malignant Tabla 19. Resultados del caso de estudio 6 Finalmente, en la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 42 1 43 2 44 4 45 11 46 36 (1 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 45) 47 114 (11 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 46) 48 297 (57 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 47) 49 648 (213 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 48) Tabla 20. Resumen de los resultados del caso de estudio 6 5.1.2.3 Conclusiones tras la variación del hiperparámetro € Tras la realización de diversos experimentos, cambiando el valor del hiperparámetro Ä , es decir los casos de estudio 2, 5 y 6, se pueden llegar a las siguientes conclusiones: 1) A mayor valor de Ä , hay una menor dispersión del árbol de topics. Esto quiere decir que los temas son más genéricos y, por tanto, hay un mayor número de documentos que cumplen cierto criterio. 2) En el caso de una clasificación más selectiva, es decir, menores valores de CÄ , hay una mayor variedad de topics. Además, la dispersión del árbol comienza en niveles más cercanos al nodo raíz. Por ejemplo, en el caso de estudio 6, donde el valor de Ä es 0.5, la diferencia entre documentos se aprecia en niveles más cercanos al raíz (en el nivel 43 ya se diferencian dos ramas del árbol) mientras que, para valores más altos, esta diferenciación se produce en niveles más bajos. Resultados. Análisis de Parámetros 50 Figura 27. Gráfica comparativa de distintos valores del hiperparámetro Ä 5.1.3 Análisis del hiperparámetro ‹ En este apartado se llevará a cabo un estudio del hiperparámetro a presente en el algoritmo implementado. En este caso, esta variable afecta al cálculo de pesos de cada nivel que, a su vez, se empleará en la asignación de un documento a determinado topic del árbol. En los siguientes sub-apartados se presentan los diversos casos de estudio. 5.1.3.1 Caso de estudio 7 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 1 1 Tabla 21. Hiperparámetros del caso de estudio 7 Los resultados obtenidos en este caso se resumen en la siguiente tabla. Al igual que en el apartado anterior, se ha representado únicamente algunas ramas del árbol de topics devuelto por el algoritmo. Nivel Rama Topic Número de documentos Palabras más empleadas 0 0 0 1499 signaled, noiseless, filterbank, frequent, chaos, spikes, informational, correlational, detector, trainable 1 - 43 0 379 - 27556 1499 Predictive, modeled, database, setpoint, regressive, validatory, testable, selective, motivate, directional, visualisation, systematic, 1 1 1 2 7 53 207 465 1 1 1 1 3 22 144 402 1 2 4 11 35 103 240 435 0 -42 43 44 45 46 47 48 49 COMPARATIVA GAMMA nº niveles caso 2 nº niveles caso 5 nº niveles caso 6 51 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas objection, features, classifies, characterised, algorithmic 44 1 27557 1375 dominant, ocularity, mapped, eyes, developmental, orientational, eytan, competitive, borel 45 1.1 27558 974 patient, semantically, nance, attribute, damaged, optical, apical, farber, cleaned, damasio 46 1.1.1 27559 242 subsequently, sing, baxter, florham, biologically, ifr, pleasure, hecht, playing, motivated 47 1.1.1.1 27560 73 confusion, cell, absorb, error, extremely, jagota, close, achievement, picked, soybean 48 1.1.1.1.1 27561 37 establishing, enhances, pay, theo, inhomogeneous, sifter, rap, extremes, interactive, ild 49 1.1.1.1.1.1 27562 17 voronoi, eyes, veloped, header, rotational, gained, vestibule, reflexive, vet, store 49 1.1.1.1.1.2 62086 13 davies, michalski, Johnson, richardson, petersen, indexed, autistic, thompson, williamson, pause 49 1.1.1.1.1.3 436779 5 controlled 49 1.1.1.1.1.4 437281 2 Engineer, confer Tabla 22. Resultados del caso de estudio 7 Finalmente, en la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 43 1 44 2 45 4 (1 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 44) 46 14 (1 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 45) 47 72 (11 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 46) 48 282 (58 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 47) 49 737 (279 de los cuales no tienen coincidencia de palabras. Por tanto, llegan al nivel 48) Tabla 23. Resumen de los resultados del caso de estudio 7 Resultados. Análisis de Parámetros 58 5.2.1.2 Caso de estudio 2 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 1 2 Tabla 31. CORA - Hiperparámetros del caso de estudio 2 Finalmente, en la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 3 1 4 2 5 2 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 4) 6 2 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 5) 7 7 (dos de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 29 (siete de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 82 (37 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 32. CORA - Resumen de los resultados del caso de estudio 2 59 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Figura 31. Árbol de topics de 10 niveles del caso de estudio 2 de la base de datos CORA 5.2.1.3 Caso de estudio 3 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 0.5 1 2 Tabla 33. CORA - Hiperparámetros del caso de estudio 3 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Resultados. Análisis de Parámetros 60 Nivel Número de niveles 0 - 3 1 4 2 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 3) 5 6 (cuatro de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 4) 6 15 (ocho de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 5) 7 35 (18 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 65 (40 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 114 (72 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 34. CORA - Resumen de los resultados del caso de estudio 3 Figura 32. Árbol de topics de 10 niveles del caso de estudio 3 de la base de datos CORA 61 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 5.2.1.4 Caso de estudio 4 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 0.2 1 2 Tabla 35. CORA - Hiperparámetros del caso de estudio 4 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 2 1 3 3 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 2) 4 7 (tres de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 3) 5 19 (12 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 4) 6 37 (21 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 5) 7 57 (41 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 89 (73 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 134 (116 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 36. CORA - Resumen de los resultados del caso de estudio 4 Resultados. Análisis de Parámetros 62 Figura 33. Árbol de topics de 10 niveles del caso de estudio 4 de la base de datos CORA 5.2.1.5 Caso de estudio 5 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 2 2 Tabla 37. CORA - Hiperparámetros del caso de estudio 5 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. 63 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Nivel Número de niveles 0 - 4 1 5 2 6 3 7 10 (3 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 29 (8 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 81 (31 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 38. CORA - Resumen de los resultados del caso de estudio 5 Figura 34. Árbol de topics de 10 niveles del caso de estudio 5 de la base de datos CORA Resultados. Análisis de Parámetros 64 5.2.1.6 Caso de estudio 6 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 0.5 2 Tabla 39. CORA - Hiperparámetros del caso de estudio 6 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 4 1 5 2 6 5 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 5) 7 19 (3 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 50 (11 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 99 (46 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 40. CORA - Resumen de los resultados del caso de estudio 6 65 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas Figura 35. Árbol de topics de 10 niveles del caso de estudio 6 de la base de datos CORA 5.2.1.7 Caso de estudio 7 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 1 1 Tabla 41. CORA - Hiperparámetros del caso de estudio 7 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Resultados. Análisis de Parámetros 66 Nivel Número de niveles 0 - 5 1 6 5 (uno de los cuales no tiene coincidencia de palabras, por tanto, llegará hasta el nivel 5) 7 13 (3 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 6) 8 43 (15 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 94 (36 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 42. CORA - Resumen de los resultados del caso de estudio 7 Figura 36. Árbol de topics de 10 niveles del caso de estudio 7 de la base de datos CORA 67 Implementación de Asignación Jerárquica Latente de Dirichlet para Modelado de Temas 5.2.1.8 Caso de estudio 8 En este caso se analizarán los siguientes valores de los hiperparámetros: ⁄ € ‹ 1 1 0.5 Tabla 43. CORA - Hiperparámetros del caso de estudio 8 En la siguiente tabla se muestran los resultados obtenidos en este caso de estudio a un nivel más genérico que nos permitirá hacer comparativas entre las diferentes ejecuciones del algoritmo. Nivel Número de niveles 0 - 4 1 5 2 6 3 7 11 8 36 (6 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 7) 9 90 (36 de los cuales no tienen coincidencia de palabras, por tanto, llegarán hasta el nivel 8) Tabla 44. CORA - Resumen de los resultados del caso de estudio 8 Por último, se representa el árbol de topics resultante. REFERENCIAS (s.f.). Obtenido de GitHub: https://github.com/dongwookim-ml/python-topic-model Aggarwal, C., & Zhai, C. (2012). Text Mining Data. Springer. Aldous, D. (1985). Exchangeability and related topics. École d'été de probabilités de Saint-Flour, XIII -1983, 1-198. Alghamdi, R., & Alfalqi, K. (2015). A Survey of Topic Modeling in Text Mining. International Journal of Advanced Computer Science and Applications, 6(1), 147-153. Alpaydin, E. (2014). Introduction to Machine Learning. MIT Press. Andrew McCallum, U. o. (s.f.). Obtenido de https://people.cs.umass.edu/~mccallum/data.html Blei Lab. (s.f.). Obtenido de https://github.com/blei-lab/edward Blei, D., & Lafferty, J. (2006). Dynamic Topic Models. Proceedings of the 23rd international conference on Machine learning (ICML '06), 113-120. Blei, D., & Lafferty, J. (2007). A Correlated Topic Model of Science. The Annals of Applied Statistics, 1(1), 17-35. Blei, D., & Lafferty, J. (2009). Topic Models. Blei, D., & McAuliffe, J. (2007). Supervised Topic Models. Proceedings of the 20th International Conference on Neural Information Processing Systems. Blei, D., & Moreno, P. (2001). Topic segmentation with an aspect hidden Markov model. Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, 343-348. Blei, D., Griffiths, T., & Jordan, M. (2010). The Nested Chinese Restaurant Process and Bayesian Nonparametric Inference of Topic Hierarchies. Journal of the ACM, 57(2). Blei, D., Griffiths, T., Jordan, M., & Tenebaum, J. (2013). Hierarchical Topic Models and the Nested Chinese Restaurant Process. Center of Machine Learning and Intelligent Systems, University of California. (s.f.). UCI Machine Learning Repository. Obtenido de https://archive.ics.uci.edu/ml/datasets/bag+of+words D. M. Blei, A. Y. (2003). Latent Dirichlet Allocation. The Journal of Machine Learning Research, 3, 99-1022. Frigyik, B. A., Kapila, A., & Gupta, M. R. (2010). Introduction to the Dirichlet Distribution and Related Processes. University of Washington, Department of Electrical Engineering, Seattle. Gershman, S., & Blei, D. (2011). A tutorial on Bayesian nonparametric models. Journal of Mathematical Psychology. Griffiths, T., & Steyvers, M. (2004). Finding scientifics topics. Proceedings of the National academy of Sciences of the United States of America 101, 5228-5235. Hofmann, T. (1999). Probabilistic latent semantic indexing . Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, 50-57. https://github.com/dongwookim-ml/python-topic-model/blob/master/ptm/utils.py. (s.f.). Li, W., & McCallum, A. (2006). Pachinko Allocation: DAG-structured mixture models of topic correlations. Proceedings of the 23rd international conference on Machine Learning. Lichman, M. (2013). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. University of California, School of Information and Computer Science. Irvine, CA. Referencias 76 Mimno, D., & McCallum, A. (2008). Topic models conditioned on arbitrary features with Dirichletmultinomial regression. Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, 411-418. Mohit, B. (2014). Named Entity Recognition. En I. Zitouni, Natural Language Processing of Semitic Languages (págs. 221-245). Springer Berlin Heidelberg. Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. The MIT Press. Nishma Laitonjam, V. P. (2015). Topic Modelling for Songs. IEEE 2015 International Conference on Information Technology. Rosen-Zvi, M., Griffiths, T., Steyvers, M., & Smyth, P. (2004). The Authos-Topic Model for Authors and Documents. Proceedings of the 20th conference on Uncertainty in artificial intelligence, 487-494. V. Jelisavčić, B. F. (2012). Topic Model and Advanced Algorithms for Profiling of Knowledge in Scientific Papers. MIPRO, 2012 Proceedings of the 35th International Convention, 1030-1035. Wang, X., McCallum, A., & Wei, X. (2007). Topical n-grams: Phrase and topic discovery, with an application to information retrieval. Proceeding of the 7th IEEE International Conference on Data Mining, 697- 702. Wiering, M. y. (2012). Reinforcement learning: State-of-the-art. Springer. ANEXO