Thursday, November 15, 2012

Nota de datos de región de Twitter

Hemos visto que Semiocast lleva a cabo reportes anuales sobre el crecimiento de Twitter en el mundo. Se tiene estadísticas sobre las características de los usuarios, lugar de origen, tipos de dispositivos empleados, etc.

Al profundizar en la búsqueda de la obtención de datos para determinar el origen geográfico de los mensajes en Twitter, se encontró el siguiente párrafo:

Semiocast used its proprietary platform, databases and tools to process user profiles in order to determine the location of each user using all available information: free-form location declared in user profile, time zone, language used to post tweets and GPS coordinates for the very few concerned tweets. Indeed, more than 2.5 years after Twitter introduced the ability to post tweets with GPS coordinates, this feature is only used in 0.77% of all public tweets.

Al conocer esto, se conoce la posibilidad de no tener una manera trivial de conocer los datos de origen de los usuarios de Twitter a menos que se hayan escrito explícitamente.

Neural Network Approaches for Text Document Categorization

Para este artículo se emplea un perceptrón multicapa como componente base para la categorización de documentos de texto en una gran cantidad de documentos con una gran cantidad de categorías. Se exploran dos arquitecturas, una categórica y otra jerárquica.

Una categorización multinivel de documentos consiste en una estructura jerárquica que contiene enlaces y nodos para representar la relación entre los conceptos de la categoría del documento cubiertos por la clasificación. La primera tope esta conformada por el concepto en general del dominio del documento. Se puede definir a dicha categoría como un conjunto de subcategorías (C1, C2, … Cn) que forman al primer nivel (L1) dentro del sistema. La composición de subcategorías se muestra en la siguiente figura:

image

La red tradicional fue entrenada una metodología de todos contra todos debido al gran número de clases y al gran tamaño del conjunto de entrenamiento. Esta red fue entrenada para comparar sus resultados con los dos enfoques presentados dentro del artículo.

En el modelo categórico, se entrenó a una red neuronal por cada categoría de nivel 1. Cada red tiene distintas salidas incluyendo la posibilidad que un tema no pertenezca a la categoría. Al final, todo se conjunta en un módulo de decisión que se encarga de asignar una categoría en base a un umbral que puede ser modificado. Esta arquitectura se puede paralelizar fácilmente y las estructuras de cada una de las redes neuronales son independientes entre sí así como sus parámetros. También el espacio necesario para esta representación es menor al de una sola red. La arquitectura se presenta en la siguiente figura:

image

El modelo jerárquico consiste en una primera red neuronal para el nivel 1. Esta red comparte un solo espacio y las salidas son binarias (pertenece o no pertenece). Se procede a un segundo conjunto de redes en las que cada una tiene un espacio más específico para la categoría que busca. El entrenamiento del primer nivel se hace de manera rápida y eficiente debido a la salida binaria mientras que para las redes del siguiente nivel se pueden paralelizar y al contar con espacios personalizados, requieren menos recursos que el uso de una sola red. La arquitectura se muestra a continuación:

image

Se utilizaron datos de diagnóstico de la industria automotriz para los experimentos. Se tienen 7 categorías de nivel 1 y cada una tiene un número distinto de datos siendo la segunda la más grande con 911. La siguiente figura presenta una descripción de los datos:

image

Uno de los principales motivos para realizar estas comparaciones consistió en el tiempo requerido para ejecutar los pasos. Los resultados se muestran en la siguiente figura:

image

Por otro lado, se debió llevar a cabo una medición de la confiabilidad de clasificación entre los tres modelos. Los resultados se presentan a continuación:

image

Murphey, Y. L. (2006). Neural Network Approaches for Text Document Categorization. The 2006 IEEE International Joint Conference on Neural Network Proceedings (pp. 1054–1060). IEEE. doi:10.1109/IJCNN.2006.246805

Document Classification and Recurrent Neural Networks

Se habla sobre un sistema de clasificación automática de documentos llamado NeuroClass. Es una herramienta de clasificación sobre texto en lenguaje natural basado en redes neuronales recurrentes.

Los documentos empleados para entrenamiento fueron cinco tipos de veintiocho posibles de la sección de aeropuertos de Transport Canada. Se emplearon aproximadamente 1000 documentos en la construcción del sistema. Las clases son las siguientes:

  • 5151 Establishment & Operations – General
  • 5157 Marketing
  • 5158 Construction & Maintenance – Airside
  • 5160 Emergency Services & Rescue
  • 5164 Light & Power

De los 1000 documentos, 400 fueron empleados en la construcción de un diccionario que contiene aproximadamente 14000 palabras. El diccionario contiene las palabras más empleadas en los documentos junto a la información requerida para convertir a los documentos en secuencias de vectores de probabilidad correspondientes a las palabras. Se guardan las palabras, su frecuencia en todos los documentos y la frecuencia en cada documento.

La primera codificación de los documentos se basó en el uso de los valores ASCII de las letras. Cada palabra era convertida en un vector de números reales en el rango [0,1]. Cada vector era normalizado al dividir cada componente entre 255. Sin embargo, surgió un problema al clasificar las palabras ya que sucedía que en palabras con una longitud similar, con letras cercanas (en valores), no lograban diferenciarse lo suficiente.

La representación corregida consiste en leer los documentos mediante una rutina, palabra por palabra. Cada palabra es buscada dentro del diccionario, al encontrarse se convierte a la palabra en un vector de probabilidades pi al dividir la frecuencia de la frecuencia en cada clase fi entre la frecuencia total de la palabra ftot. Si no se encuentra la palabra dentro del diccionario, se hace uso de una probabilidad de 1/n donde n=5 ya que es el número de clases consideradas para las pruebas.

La primera arquitectura propuesta consistía en dos redes. La primera se encargaba de obtener las palabras claves de cada documento mientras que la segunda llevaba a cabo la clasificación del mismo. Los resultados con esta arquitectura no fueron los deseados y se decidió utilizar una sola red entrenada con las secuencias de vectores de probabilidad que representan las palabras contenidas en el documento. El paradigma de Elman fue elegido en base a experimentos.

El progreso de eficiencia de clasificación fue avanzando gradualmente. Con 500,000 iteraciones, solo se pudo clasificar la clase 5160 al 100%. Con 1,000,000 de iteraciones, sólo la clase 5158 fue propiamente identificada. Después de 1,500,000 iteraciones se empezó a diferenciar entre clases y no fue sino hasta las 3,000,000 de iteraciones que todas empezaron a obtener un 100% de precisión.

Se creó una herramienta de validación estadística para medir la confiabilidad del sistema. Después de asignar una clase a un documento, se calcula un nivel de confianza C(x, y) mediante la siguiente fórmula:

image

En la fórmula, X representa el total del número de palabras en un documento en que pi ≥ 0.55 y Y es el número total de palabras en el documento. Los experimentos que realizaron mostraron que los casos en que C(x, y) ≥ 0.30, la mayoría de los documentos fueron correctamente clasificados mientras que en el caso C(x, y) < 0.30 eran incorrectamente clasificados. La siguiente gráfica muestra los resultados finales:

image

En general, el sistema puede asegurar la correcta clasificación al alcanzar los 3,500,000 ciclos de entrenamiento.

Farkas, J. (1995). Document classification and recurrent neural networks. Proceeding CASCON ’95 Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research. Retrieved from http://dl.acm.org/citation.cfm?id=781936

Thursday, November 8, 2012

POS-Taggers

Revisar características a detalle de los siguientes POS-Taggers:

Neural network for theme recognition in twitter

Tweets -> Normalization -> Label -> Train Neural network -> Works for just 1 theme?
                |-> POS Tagger
                |-> Unsupervised Learning
                |-> Ontology

¿Clasificar en base a la estructura? ¿En base al contenido?

Automatic labeling? -> Entity Relationship? -> Clustering?
                                  |-> Web n-gram?
                                  |-> Wikipedia?

Empirical Study of Machine Learning Based Approach for Opinion Mining in Tweets

El artículo se encuentra basado en minería de opiniones (análisis de sentimientos). La minería de opiniones se define como el estudio computacional de las opiniones, sentimientos y emociones expresadas en texto.

Formalmente definen a una opinión como la siguiente quíntupla:

  • oj – Es el objeto de la opinión, en caso de Twitter, de la entidad o entidades sobre las que se habla en un mensaje.
  • fjk – es la característica del objeto de opinión, en el caso del artículo se ignora esta parte.
  • ooijkl – es la polaridad de la opinión, en este caso es la polaridad del mensaje entero y puede ser: positiva, negativa o neutral.
  • hi – es quien emite la opinión, en este caso quien escribió el mensaje en Twitter.
  • t1 – es el tiempo en que la opinión fue emitida, en este caso el momento en que se publicó el mensaje.

Para la clasificación, se representa al texto como una serie de características. Las características son n-grams formados por las palabras extraídas de los mensajes. Se emplea una representación morfológicamente normalizada. Al utilizar POS n-grams, se emplean los tags que arroja el POS en lugar de las palabras del mensaje. Por ejemplo se menciona el uso de Noun en lugar de batería, Verb en lugar de descargar, etc.

Se menciona que no encontraron una referencia anterior que utilice Twitter en español como cuerpo de estudio por lo que tuvieron que diseñar todo el pre-procesamiento de datos.

Para el cuerpo de datos, se recolectaron 32,000 mensajes correspondientes a una lista de entidades predefinidas sobre marcas de teléfonos celulares. 8,000 mensajes fueron clasificados manualmente como: Positivo, Negativo, Neutral e Informativo.

Los mensajes en Twitter suelen contener errores, en el caso específico del español se mencionan algunos representados en la siguiente figura:
image

Para poder llevar a cabo el análisis se requiere realizar una normalización del texto, en su caso decidieron emplear los siguientes cuatro procesos:

  • Error correction – en errores ortográficos como “muertooo” se corrigen basados en un diccionario de español y un modelo estadístico sobre letras dobles comunes en el idioma. Se hicieron reglas a mano sobre la jerga y las palabras comunes tomadas del inglés. No se detectan otro tipo de errores ortográficos.
  • Special tags – se emplean USER_TAG, WINK_TAG, HASH_TAG, y URL_TAG para remplazar palabras con formato especial conocido para Twitter. Por ejemplo @usuario se cambia por USER_TAG y =) se cambia por WINK_TAG.
  • POS-tagging – Utilizaron freeling como POS-Tagger ya que no solo lleva a cabo el etiquetado, también lleva a cabo una lematización de las palabras para reducir el número de conjugaciones y formas que se pueden presentar.
  • Negation process – las negaciones alteran el sentido de la opinión en el texto, para lidiar con ellas, cada que se presentan, se adhieren a su siguiente palabra. Por ejemplo “no tener” quedaría como “no_tener”.

Para las entradas a los clasificadores se emplean dos vectores. Cada entrada en un vector corresponde a una característica arrojada por el POS-tagger y se emplean: verbs, nouns, adjetives, adverbs e interjections.

De los 8000 mensajes manualmente marcados, 7000 son utilizados para el conjunto de entrenamiento y 1000 para pruebas de los cuales 236 son positivos, 145 negativos, 342 neutrales y 257 informativos.

Para las pruebas se quiso medir el efecto del tamaño del cuerpo, del tamaño de los n-grams, número de clases y balance del cuerpo.

Los resultados obtenidos se muestran en las siguientes figuras:

image

image

image

image

image

image

image

Según los resultados obtenidos, consideraron que los mejores parámetros para llevar a cabo la clasificación en tuits en español constan de lo siguiente:

  • Utilizar unigrams
  • Tener un conjunto de entrenamiento de al menos 3000 tuits
  • Utilizar SVM como clasificador
  • Tener solo dos clases polarizadoras
  • Que el conjunto de entrenamiento y el de prueba sean sobre el mismo dominio

Al emplear estos parámetros, lograron conseguir una precisión del 85.8%.

Los errores más comunes al clasificar los mensajes se dividen en lo siguiente:

  • Mensajes acortados – suceden cuando ni el humano es capaz de etiquetar el mensaje como una de las clasificaciones planteadas debido a la falta de información.
  • Faltas de ortografía – las palabras mal escritas evitan la posibilidad de poder identificar la opinión dentro del mensaje.
  • Humor, ironía y sarcasmo – interpretar el sentido de la oración cuando se emplean este tipo de connotaciones se vuelve complejo y completamente dependiente de un contexto general que a veces no es fácilmente identificable ni por un humano.
  • Errores en el etiquetado – De nuevo, no todos los mensajes se pueden etiquetar fácilmente y se requiere de cierta interpretación que no siempre concuerda con el enfoque original.

Grigori Sidorov, Sabino Miranda-Jiménez, Francisco Viveros-Jiménez, Alexander Gelbukh, Noé Castro-Sánchez, Francisco Velásquez, Ismael Díaz-Rangel, Sergio Suárez-Guerra, Alejandro Treviño, and Juan Gordon. Empirical Study of Machine Learning Based Approach for Opinion Mining in Tweets. LNAI 7630, 2012, pp. 1-14.

Aplicación del Procesamiento de Lenguaje Natural en la Recuperación de Información

La aplicación está basada en Recuperación de Información (RI) que consiste en la acción de recibir una consulta o pregunta de un usuario y devolver un conjunto o serie de documentos ordenados según su relevancia respecto a lo que se pidió. El propósito general consiste en mejorar la calidad de los resultados arrojados al hacer uso de técnicas de procesamiento de lenguaje natural (PLN).

El modelo propuesto se basa en que un documento puede estar representado por sus entidades y las relaciones que existen entre ellas. Las entidades son representadas por sintagramas nominales (Noun Phrase NP). Para las relaciones se emplean cláusulas en las que el verbo es el núcleo y los modificadores son los NP y los sintagramas preposicionales (Prepositional Phrase PP).

El ejemplo que indican para su análisis inicia con la siguiente oración: “Mary Blake arrived late, so Mary Spencer who is the secretary of ARS fined her, the president of ISS, with 1000€”. Se identifican dos entidades: Mary Blake y Mary Spencer, además se puede obtener datos de Mary Spencer (secretary of ARS). Al resolver la referencia anafórica entre her y Mary Blake se puede obtener que ella es the president of ISS. Esto permite que se pueda responder al usuario por consultas por Mary Blake, the president of ISS y descartar otras como Mary Blake, the president of ARS.

Para obtener el conocimiento emplearon el Slot Unification Parser for Anaphora Resolution (SUPAR). El sistema necesita como entrada el resultado de un etiquetador POS tagger (para el idioma español emplearon Maco) y se realiza un análisis sintáctico parcial del texto.

Para implementar las entidades y relaciones dentro del modelo vectorial tradicional de RI, se emplean 3 tablas NPT, PPT y CCT. NPT almacena la información de las entidades NP. PPT Y CCT almacenan información adicional sobre las entidades o las relaciones entre ellas ya sea en sintagramas preposicionales o clausulas. Por ejemplo se maneja la frase architecture in San Louis, la preposición in indica que es muy probable que San Louis sea un lugar en lugar de una persona por lo que se debe dar más puntaje al documento en que una PP aparezca como in San Louis a que aparezca solo. CCT se dedica a guardar información sobre las relaciones entre entidades en base a los verbos. A continuación se presentan ejemplos de las tablas:

image

image

image

image

En general el modelo se utiliza para enfrentar al concepto tradicional del modelo de sacos de palabras que asumen que los términos ocurren independientemente unos de otros al indexar entidades y las relaciones entre ellas.

Se adaptó el modelo vectorial al cambiar los términos por entidades y modificar la medida de similitud al introducir NLPfactor y proximity como valores.

En general los resultados muestran una mejoría respecto al modelo vectorial original en dos idiomas (inglés y español) en consultas largas y cortas. En inglés, las preguntas cortas tuvieron una mejoría en precisión de 35.11% mientras que en las largas fue de 12.96%. En español se lograron mejorías de 27.42% y 37.18% respectivamente. Comparándolos contra el método de coseno pivotado se obtuvo que en inglés se mejoró en 21.12% y 9.91% mientras que en español resultó con 19.76% y 36.67%.

Rojas, Y., Ferrández, A., & Peral, J. (2005). Aplicación del procesamiento de lenguaje natural en la recuperación de información. Procesamiento del lenguaje natural, (1999). Retrieved from http://www.sepln.org/revistaSEPLN/revista/34/02.pdf