Una reseña sobre LDA

Hace un tiempo estuve probando para el desarrollo mi tesis una herramienta llamada MALLET (MAchine Learning for LanguagE Toolkit). MALLET es un producto de la universidad de Massachusetts  Amherst realizada bajo la dirección de el profesor Andrew McCallum cuyo primer lanzamiento fue en el año 2002, pero fue años mas tarde cuando empezó a recibir un interés mas considerable.

David Blei, autor de la técnica LDA.

El corazón de MALLET aplica una técnica llamada LDA (Latent Dirichlet Allocation) que ayuda a explorar grandes cantidad de textos. Esta técnica se encarga de  buscar clusters de palabras que aparecen con mayor frecuencia juntas, también llamados “tópicos” o temas. Con mas detalle el algoritmo imagina que cualquier texto o documento es un “mix” de diferentes tópicos. Cada uno de los tópicos se puede ver como una distribución de probabilidades de los términos que los componen a través de todo el cuerpo del documento.

Esta técnica nos lleva a obtener dos salidas principales como resultado; por un lado una lista de los tópicos y de las palabras que los constituyen (con sus probabilidades) y por otro lado la lista de documentos con la porción (probabilidades) de tópicos que los constituyen a estos. Los resultados que se obtienen pueden llegar a ser asombrosos dado que se pueden obtener relaciones inesperadas.

Estos resultados se pueden interpretar con dos matrices como salida, como pueden ver en la siguiente figura.

Camino desde los datos puros hasta llegar al Modelo de Tópicos. En este caso el modelo es el introducido arriba, LDA.

 

Los datos puros seria la parva de documentos que tenemos que procesar. Obviamente a estos datos “puros” se le aplico un pre-proceso para limpiar un poco el ruido. Eso depende de el tipo de documentos en particular. Luego estos datos son interpretados medieante una matriz denominada VSM. VSM, o Vector Space Model, tampoco esta definido como un modelo en sí según algunos investigadores. Pero, bue, en fin. Lo que hace es desglosar a los documentos por los términos o palabras que los componen. En cada celda tenemos la cantidad de ocurrencias de cada uno de ellos en cada documento. Luego a este cuadrado o matriz, jeje, se puede optimizar para ahorrar espacio, Finalmente eso es lo que se mete en el modelo de tópicos. Finalmente obtenemos los dos resultados que mencione arriba.

Lo que se ve en la figura como “Entradas” son algunos parámetros necesarios para que funcione el algoritmo. Uno de ellos es el número de tópicos que queremos obtener y algunos parámetros mas para ajustar las distribuciones de probabilidad que compone al modelo LDA.

Para entender un poco como funciona este algoritmo voy con el siguiente ejemplo. Supongamos que tenemos los siguientes tres documentos:

d1= “Predicting the incidence of faults in code has been commonly associated with measuring complexity. In this paper, we propose complexity metrics that are based on the code change process instead of on the code.”

d2= “Bug prediction models are often used to help allocate software quality assurance eorts (for example, testing and code reviews). Mende and Koschke have recently proposed bug prediction models that are eort-aware.”

d3= “There are numerous studies that examine whether or not cloned code is harmful to software systems. Yet, few of these studies study which characteristics of cloned code in particular lead to software defects (or faults).”

En el ejemplo tenemos un total de 101 términos y un vocabulario total de 71 términos únicos. En el d1 tenemos 34 términos, en d2 con 35 y en d3 32. Entonces el VSM quedaria con la siguiente pinta:

VSM.

En esta matriz podemos observar que por ejemplo para el término code en el documentos d1 aparece con una frecuencia de tres veces y en el documento d3 dos veces. Luego esta matriz (pre-procesada o no) se mete en el modelo de tópicos junto con los parámetros de entrada mencionados arriba. Sin ahondar en el funcionamiento matemático del modelo las salidas que obtenemos serían las siguientes:

Salida del modelo de tópicos.

En el ejemplo (mirando la matriz de abajo) tenemos que cuando el término es extraído del tópico 1 hay un 25% de chances de que sea el término code y un 30% de chances de que el término sea software. En la otra matriz de arriba cuando un tópico es seleccionado para el documento d1, tiene una probabilidad del 25% de que sea seleccionado el tópico Z1 y un 70% de que sea seleccionado el tópico Z4.

Mas adelante voy subir algún ejemplo de implementación de alguna variante de LDA usando MALLET en Java.