Clasificación Semi-Supervisada de Documentos Roxana K. Aparicio Carrasco Ciencias e Ingeniería de la Información y la Computación, Universidad de Puerto Rico Mayagüez, 00681-5000, Puerto Rico [email protected] y

Edgar Acuña Fernández Departamento de Ciencias Matemáticas, Universidad de Puerto Rico Mayagüez, 00681-5000, Puerto Rico [email protected]

RESUMEN Las técnicas de minería de datos y KDD han sido exitosamente utilizadas en el ámbito de documentos de texto. Particularmente, el aprendizaje supervisado es ampliamente usado para tareas como detección de correo electrónico malicioso, clasificación automática de páginas web, entre otras. Sin embargo, para entrenar estos sistemas, se requiere de una cantidad muy grande de documentos manualmente etiquetados, lo cual conlleva el uso de recursos humanos, el cual es costoso en tiempo y dinero. Por otro lado, una gran cantidad de documentos sin etiquetar es fácilmente obtenible. La clasificación semi-supervisada se refiere al uso de una gran cantidad de documentos sin etiquetar junto con una cantidad menor de documentos etiquetados en el proceso de aprendizaje. La clasificación semi-supervisada de documentos es un aspecto emergente que está cobrando mucha importancia debido a la gran proliferación de documentos en formato digital, principalmente existente en la World Wide Web. En este articulo presentamos una revisión de los avances en la clasificación semisupervisada de documentos y presentamos algunos resultados de la literatura y algunos problemas abiertos.

Palabras Clave: Minería de Texto, Clasificación semi-supervisada, Recuperación Maquinas de Soporte Vectorial.

de

Información,

1. INTRODUCCIÓN La clasificación supervisada de documentos es una técnica de minería de texto, en la cual, se predefine un conjunto de clases, y se entrena un sistema mediante un conjunto de documentos manualmente clasificados o etiquetados. Una vez entrenado el sistema, es usado para clasificar automáticamente un nuevo documento en la clase correspondiente. Esta técnica ha sido utilizada con

mucho éxito en la detección de correo electrónico malicioso, clasificación automática de páginas web, y una gran variedad de problemas de este género. El problema con la clasificación supervisada, es que requiere de una gran cantidad de documentos manualmente etiquetados para realizar el entrenamiento. Este es un proceso costoso ya que requiere la participación de personas que inviertan su tiempo en leer los documentos y etiquetarlos. Por otro lado, existe una gran cantidad de documentos sin etiquetar disponibles que pueden ser obtenidos fácilmente y en forma gratuita, especialmente cuando hablamos conjuntos de datos online, páginas web, correos electrónicos, noticias online, etc. Nigam et. al. mostraron en [7] que, en ciertas circunstancias, es posible entrenar un sistema utilizando tanto documentos etiquetados como no etiquetados y mostraron las bases teóricas sobre las cuales apoyan esta teoría. Posteriormente, otros autores como Hofmann [4] y Krithara et al. en [6] aplicaron la clasificación semisupervisada de documentos utilizando la técnica de Probabilistic Latent Semantic Analisys PLSA y en [5] la utilizo conjuntamente con la técnica de Aprendizaje Activo (Active learning). Otra técnica relacionada, que también es ampliamente investigada es la del uso de maquinas de soporte vectorial en el aprendizaje semi-supervisado [2], [3],[8]. En este articulo damos una revisión de los avances en la clasificación semi-supervisada de documentos, en particular revisaremos las propuestas previamente mencionadas, y presentamos algunos resultados de la literatura y problemas abiertos.

2. LA IMPORTANCIA DE LOS DOCUMENTOS NO ETIQUETADOS PARA LA CLASIFICACIÓN

3. APRENDIZAJE SEMI-SUPERVISADO SEMI USANDO EL ALGORITMO EM Y CLASIFICADOR NAIVE BAYES

Aunque parezca que no se ganaría nada del uso de los datos no etiquetados, existen muchos estudios que demuestran que, en determinadas circunstancias los datos no etiquetados son de gran importancia en la tarea de clasificación.

Kamal Nigam en [7] presentó un modelo probabilístico para el aprendizaje semi-supervisado supervisado en texto. Mediante este modelo probaron la facti actibilidad del aprendizaje semi-supervisado.

La razón del uso de los documentos no etiquetados y del por qué estos pueden ayudar al proceso de aprendizaje es expuesta intuitivamente en [7], mediante un ejemplo que fue obtenido después ués de un experimento con WebKb, un de datos de páginas web de universidades:: Suponga que contamos con algunas páginas web correspondientes a cursos académicos, junto con un gran conjunto de páginas web sin etiquetar. Observando tan solo los documentos etiquetados quetados podemos verificar que la palabra "asignación"" tiende a estar contenida en paginas correspondientes a cursos académicos.. Si usamos este hecho para estimar las clases de los documentos sin etiquetar, es posible que encontremos que la palabra "notas" ocurre frecuentemente en los documentos sin etiquetar que fueron clasificadoss positivamente como pertenecientes a la clase curso. Esto significa que estamos obteniendo una información del uso de los documentos sin etiquetar debido a la co--ocurrencia de estas palabras que se presentan frecuentemente en páginas web de cursos. Visualmente, en la figura [1] se muestra un ejemplo de cómo mo la distribución de los datos no etiquetados pueden determinar la correcta clasificación dee los datos.

Modelo Multinomial Naive Bayes para Texto Con el fin de modelar los datos, datos se asume que los documentos son generados por un modelo de mezclas con distribución multinomial, donde cada componente de la mezcla corresponde a una clase. Sea k el numero de clases y un vocabulario de tamaño |V|; cada documento di con |di| palabras. palabras (1)

La verosimilitud de ver el documento di es una sumatoria de la probabilidad total sobre todos los componentes de la mezcla: (2)

Usando la suposición de independencia condicional Naive Bayes, podemos expandir el segundo termino de la ecuación 1, y expresar la probabilidad de un documento dado un componente de la mezcla en términos de la longitud de las palabras que contiene el documento y de la longitud del documento. El modelo completo, combinando nando las ecuaciones Ec. (1) y Ec. (2), asigna la probabilidad P(Di|Ө) de generar el documento di mediante la siguiente ecuación: (3)

Usando la estimación de parámetros maximum a posteriori (MAP) asumiendo como distribución a priori una Dirichlet, tenemos: Figura 1. El triángulo y la cruz corresponden a los datos etiquetados. Los puntos corresponden a datos sin etiquetar. La línea negra corresponde a la frontera de decisión.

(4)

(5)

Teniendo los estimados de estos parámetros, es posible calcular la probabilidad de que un componente de la mezcla genere un documento dado para realizar la clasificación. Aplicando la regla de Bayes:

(6)

Para clasificar un documento en una clase, se selecciona la clase con la máxima probabilidad posterior. Algoritmo EM para Aprendizaje Semi-supervisado

4. APRENDIZAJE SEMI-SUPERVISADO USANDO PLSA Probabilistic Latent Semantic Analysis (PLSA) ha sido presentado por Hofmann [4] como una versión probabilística de Latent Semantic Analysis LSA. PLSA, asocia una variable latente no observada α a cada observación correspondiente a la ocurrencia de una palabra ω Є W dentro de un documento d Є D. (8)

donde K es el número de componentes latentes y c = 1..K.

Como tenemos datos sin etiquetar, se utiliza la técnica llamada Expectation-Maximization (EM), para encontrar máximos locales de los estimados de los parámetros. El valor esperado de la log-probabilidad de los datos es: (7)

El algoritmo EM conocido así por las siglas en ingles de Expectation-Maximization es un proceso de dos pasos que permite encontrar un máximo local de los parámetros del modelo. El paso E del algoritmo estima el valor esperado de la clase dada la última iteración de los parámetros del modelo. El paso M maximiza la probabilidad de los parámetros utilizando los valores estimados en la iteración anterior. En la práctica, el paso E corresponde a clasificar un documento utilizando la ecuación 6. El paso M corresponde al cálculo de un nuevo máximo a posteriori de la estimación de parámetros, utilizando las ecuaciones Ec. (4) y Ec.(5) con las estimaciones actuales. El algoritmo itera hasta que converge en un punto en el que los parámetros no cambian de una iteración a la siguiente, en la práctica utilizando un criterio de parada.

Luego, se usa una variante del algoritmo EM para entrenar el modelo. En el paso E se calcula: (9)

En el paso M, los parámetros son actualizados utilizando las siguientes ecuaciones: (10) (11) (12)

Krithara [6] realiza una extensión de PLSA en el contexto de aprendizaje semi-supervisado. Teniendo en cuenta que cuando se tienen muy pocos documentos etiquetados, algunos componentes contendrán tan solo documentos no etiquetados. Para resolver este problema, se introduce un etiqueta "falsa" de tal forma que todos los documentos etiquetados mantengan su etiqueta y los no etiquetados tengan la nueva etiqueta "falsa". Después de entrenar el modelo se distribuye la probabilidad obtenida por la etiqueta falsa entre las etiquetas reales.

EM_Semi-supervised_NaiveBayes Entradas: Dl= Conjunto de documentos etiquetados Du= Conjunto de documentos sin etiquetar 1. Entrenar un clasificador con los datos etiquetados y estimar los parámetros iniciales. 2. Iterar mientras los parámetros del clasificador mejoren, observado por el cambien en l(θ|D,Y). (Paso E) Usar el actual clasificador para estimar la clase a la que pertenece cada documento, P(cj|Di;θ). (Paso M) Re-estimar el clasificador dadas las estimaciones de cada documento, encontrar θ=argmaxθP(D,Y|θ)P(θ).

5. EXPERIMENTOS DE LA LITERATURA Los conjuntos de documentos disponibles en forma libre y gratuita más populares para clasificación son los siguientes: • 20 Newsgroups, el cual consiste de 20,017 artículos divididos entre 20 grupos de discusión de UseNet • WebKb, el cual contiene páginas web de departamentos de ciencias de computo recolectadas de cinco universidades. • Reuters, el cual consiste de 12902 artículos y 135 categorías de noticias de la Reuters.

Nigam [7] usó los tres conjuntos de datos mencionados anteriormente. El mejor rendimiento se obtuvo con 20 Newsgroups. EM superó significativamente al algoritmo Naive Bayes supervisado, aun considerando un número pequeño de datos etiquetados. Con tan solo 20 documentos etiquetados, con Naive Bayes se obtuvo 19% de precisión, con EM 39%. Con 300 documentos etiquetados Naive Bayes alcanzó 55%, mientras que con EM se obtuvo 70%. A medida que el número de documentos etiquetados se incrementó, se notó menor ganancia en precisión. Con el conjunto de datos WebKB, EM mejoró la precisión solo cuando la cantidad de documentos sin etiquetar fue pequeña. Sin embargo, a medida que se incrementó la cantidad de documentos sin etiquetar bajó el rendimiento de EM. Krithara [6], presentó una versión de PLSA para aprendizaje semi-supervisado y las aplico a los tres conjuntos de datos mencionados anteriormente. Se comparo este modelo con la versión supervisada de PLSA. Con el conjunto de datos 20 Newsgroups se obtuvo una ganancia de hasta 32% en precisión por parte del modelo semi-supervisado en relación al supervisado. Sin embargo el comportamiento de este clasificador depende en gran medida del número de variables latentes por clase. Los resultados son muy similares para los otros dos conjuntos de datos.

6. OTROS TRABAJOS RELACIONADOS Un problema relacionado a la clasificación semisupervisada es el uso de documentos etiquetados que corresponden solo a la clase de interés, esta es llamada la clase positiva. Denis et. al. [3] propone una variante al clasificador Naive Bayes para este contexto y utiliza un estimado de la probabilidad de la clase positiva, obteniendo buenos resultados. Estas pruebas se hicieron para clasificación binaria con un subconjunto de 20Newsgroups. El Aprendizaje Activo (Active learning), consiste en seleccionar los ejemplos más informativos entre los no etiquetados con la finalidad de etiquetarlos y luego agregarlos al conjunto de entrenamiento. Krithara, en [5] hace uso de esta técnica en conjunción con aprendizaje semi-supervisado. El documento con mas alta entropía es considerado como el más valioso para etiquetar por ser el más ambiguo de entre todos los documentos sin etiquetar. En el caso de clasificación binaria es simplemente el ejemplo con probabilidad cercana a 0.5. Después de etiquetar el documento, se agrega al conjunto de documentos etiquetados y se re-entrena el modelo. Los experimentos realizados por Krithara [5] se realizaron usando sólo clasificación binaria con el conjunto de datos 20 Newsgroups, para lo cual se seleccionaron tres grupos de documentos, cada grupo

conteniendo solo documentos de dos clases. La diferencia de los grupos es el grado de dificultad para la clasificación. En estos se observa una ganancia pequeña con respecto al uso de solo PLSA supervisado, la ganancia mayor es observada cuando el tipo de problema es más difícil. Transductive Learning es una técnica muy relacionada al aprendizaje semi-supervisado. La diferencia es que en Transductive Learning no se infiere ninguna regla de decisión. Se trata de estimar el valor de una función de clasificación en puntos dados del conjunto de prueba [1]. Esto contrasta con el aprendizaje inductivo que lo que hace es estimar una función de clasificación en todos los valores posibles y luego usar esta función para deducir las clases del conjunto de prueba. Bennet [1] propone un modelo llamado S3VM, para aprendizaje semi supervisado usando Maquinas de Soporte Vectorial, en sus experimentos muestra que en algunos casos mejora la performance frente al enfoque tradicional.

6. CONCLUSIONES Y PERSPECTIVAS FUTURAS Extraer conocimiento de información textual es un proceso complejo debido a que los documentos son poco estructurados y a la complejidad propia del lenguaje. Sin embargo, los avances y resultados existentes en la actualidad dan mensajes esperanzadores de lo que se puede obtener sin necesidad de recurrir al análisis semántico y sintáctico de la información escrita. También es importante el hecho de poder clasificar los documentos teniendo sólo una cantidad pequeña de documentos manualmente etiquetados, reduciendo así el costo que representa etiquetar un conjunto de entrenamiento muy grande. Aun no está muy claro si existe una configuración de parámetros ideal para los sistemas de clasificación de texto. Tampoco existe acuerdo en las técnicas de preprocesamiento recomendables como stemming en la que se considera las palabras con la misma raíz como un solo termino o remoción de palabras comunes (stop words). Frecuentemente depende de la naturaleza del problema. Con respecto a la clasificación semi-supervisada, sería importante tratar de determinar la proporción de documentos sin etiquetar con respecto a la cantidad de documentos etiquetados que beneficia a estos sistemas, de acuerdo a las características de la información. Más aún, lograr caracterizar el problema para poder aplicar la técnica que mejor se ajuste a la naturaleza particular del problema que se esté tratando.

REFERENCIAS 1.

Bennett, K. and Demiriz, A. (1998). Semi-Supervised Support Vector Machines. In Advances in Neural Information Processing Systems, 12, 368-374.

2.

Chapelle, O., Sindhwani, V., and Keerthi, S. S. 2008. Optimization Techniques for Semi-Supervised Support Vector Machines. J. Mach. Learn. Res. 9 (Jun. 2008), 203-233.

3.

Denis F., Gilleron R., Tommasi M., Text Classification from Positive and Unlabeled Examples, The 9th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2002.

4.

Hofmann T. "Probabilistic Latent Semantic Analysis" Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI'99), 1999.

5.

Krithara A., Goutte C., Massih A., Renders J.. "Active, Semi-Supervised Learning for Textual Information Access" IIIA , International Workshop on Intelligent Information Access, Helsinki, Finland, 6-8 July, 2006.

6.

Krithara A., Massih A., Renders J., Goutte C. "Semi-supervised Document Classification with a Mislabeling Error Model" Advances in Information Retrieval, 30th European Conference on IR Research (ECIR'08). Glasgow, UK. March 2008. pp. 370-381.

7.

Nigam, K., McCallum, A., Thrun, S., and Mitchell, T. 1998. Learning to classify text from labeled and unlabeled documents. In Proceedings of the Fifteenth National/Tenth Conference on Artificial intelligence/innovative Applications of Artificial intelligence (Madison, Wisconsin, United States). American Association for Artificial Intelligence, Menlo Park, CA, 792-799.

8.

Tong, S. and Koller, D. "Support Vector Machine Active Learning with Applications to Text Classification". Journal of Machine Learning Research, November 2001. p. 45-66.