VISITAS:

martes, 29 de septiembre de 2009

Precision y Recall en clasificadores

Definiciones:
  • True Positives (TP) para la clase C: son instancias pertenecientes a la clase C que se clasifican correctamente en la clase C
  • True Negatives (TN) para la clase C: son instancias no pertenecientes a la clase C y que no se clasifican como clase C
  • False Positives (FP) para la clase C: son instancias no pertenecientes a la clase C pero que se clasifican como clase C
  • False Negatives (FN) para la clase C: son instancias pertenecientes a la clase C pero que no se clasifican como clase C
En resumen:

Categoría CManual
NO
AutomáticaTPFP
NOFNTN

  • Precision para la clase C: es un valor entre 0 y 1. Su valor aumenta cuando hay pocos falsos positivos. Mide que las instancias clasificadas como clase C sean realmente de la clase C, aunque haya instancias de la clase C que se clasifiquen como otra clase
P(C) = TP / (TP + FP)
  • Recall para la clase C: es un valor entre 0 y 1. Su valor aumenta cuando hay pocos falsos negativos. Mide que las instancias de la clase C se clasifiquen como clase C, aunque otras instancias también se clasifiquen como clase C sin serlo.
R(C) = TP / (TP + FN)

viernes, 18 de septiembre de 2009

Weka para clasificación de textos

Tras haber estudiado y evaluado algunos entornos y librerías de machine learning y procesamiento de lenguaje natural (Weka, Rapid Miner, NLTK), he llegado a las siguientes conclusiones:
  • Weka es sencillo de utilizar, está escrito en Java y puede utilizarse en tres modos: GUI para empezar a probar, línea de comandos para ejecutar algoritmos y guardar resultados, y por último como una librería embebida dentro de un programa Java
  • RapidMiner, tiene unas características muy similares a Weka (de hecho, incluye todos los algoritmos de Weka y algunos más) e incluye un módulo para procesamiento de texto (que no lo veo útil por lo básico). Sin embargo es bastante complejo de utilizar y está peor documentado que Weka
  • NLTK está muy bien para empezar a hacer experimentos, pero no permite muchas facilidades. Y sobre todo, es Python, que aunque no está mal como lenguaje, no me termina de convencer

Me quedo con Weka, por lo menos para empezar. Con unos pocos tutoriales he sido capaz de hacer muchas cosas. Weka está orientado a Data Mining, sin embargo soporta un formato de fichero llamado Sparse ARFF que permite introducirle términos dispersos.

jueves, 10 de septiembre de 2009

FRAWA

Frawa ya está liberado en la comunidad Morfeo:
http://frawa.morfeo-project.org/

miércoles, 19 de agosto de 2009

Resumen de Expresiones Regulares

/afgd/
Secuencia de caracteres simples. Busca la secuencia afgd (case sensitive).
/[Jj]osé/
Busca José o josé
/[A-Z]/
Busca una letra mayúscula
/[^a]/
Busca cualquier carácter que no sea una a. El carácter ^ debe ser el primero dentro de los corchetes, si no, se considera un carácter normal.
/[^A-Z]/
Busca un carácter que no sea una letra mayúscula
/colou?r/
El carácter anterior a ? es opcional. En este ejemplo, se busca color o colour.
/ba*rco/
Busca cero o más ocurrencias del carácter anterior a *. En este ejemplo se busca barco, baarco, baaarco, etc.
/aa*/
Busca una o más a's
/[ab]*/
Busca cero o más a's o b's
/a+/
Busca una o más ocurrencias del carácter anterior a +. En este ejemplo busca una o más a's consecutivas
/[0-9]+/
Busca uno o más dígitos.
/beg.n/
El punto significa "cualquier carácter". En este ejemplo se busca begin, began, begun, etc.
/casa.*casa/
La palabra casa tiene que aparecer dos veces.
/^The/
La palabra The al comienzo de una línea
/dog$/
La palabra dog al final de una línea
/\bthe\b/
La palabra the individual (no vale other)
/\Bthe\B/
Los caracteres the dentro de una palabra
/cat|dog/
Las palabras cat o dog
/part(y|ies)/
Lo que va entre paréntes¡s se trata como un único carácter. Aquí busca party o parties.
/\./
El carácter punto

jueves, 18 de junio de 2009

Etapas en el procesamiento de un texto

1. Análisis lingüístico
  1. Corrección ortográfica: corregir palabras mal escritas ayudado con un corrector ortográfico como ASpell. A veces aparecen abreviaturas y/o palabras recurrentemente mal escritas que el corrector ortográfico no puede corregir. En este caso se construye un diccionario de palabras especiales.
  2. Tokenización: partir el texto en unidades básicas (palabras, números, símbolos de puntuación)
  3. Segmentación en sentencias: partir el texto en sentencias y párrafos
  4. Etiquetado PoS: asignar una categoría gramatical a cada token
  5. Lematización: asignar un único lema (raíz) a cada token
  6. Filtrado de stop words: eliminación de palabras no relevantes. Se puede hacer bien mediante una lista de palabras o bien eliminando las categorías gramaticales que no aportan significado (artículos, preposiciones, conjunciones,etc)

RESULTADO: Corpus anotado lingüísticamente

2. Análisis Léxico-Semántico

  1. Análisis de frecuencia de palabras: frecuencia de cada palabra en cada documento y en todos los documentos
  2. Análisis de frecuencia de n-gramas: secuencias de n palabras consecutivas que aparecen con frecuencia (bigramas, trigramas, etc)
  3. Análisis de collocations: estudio estadístico de lemas que aparecen juntos frecuentemente, separados por un número limitado de palabras (habitualmente una ventana de 4 palabras a cada lado)
  4. Cálculo de la ganancia de información de los n-gramas. Eliminación de los n-gramas que den poca ganancia de información
  5. Construcción de Diccionario de features: se escogen los n-gramas más frecuentes de cada categoría (se pone un umbral por frecuencia de aparición o eligiendo los N más frecuentes)
  6. Opcional: construcción de diccionario de conceptos con sinónimos a partir de las features
  7. Construcción de term vector sobre el corpus: se utiliza el diccionario de features para obtener los n-gramas del corpus. Se puede utilizar el diccionario de conceptos para agrupar n-gramas sinónimos

miércoles, 10 de junio de 2009

Introducción a Information Retrieval

1. Vector Space Model (VSM)

VSM representa los documentos y las cadenas de búsqueda como vectores de T dimensiones (donde T es el número de terminos distintos que hay en la colección de documentos).

Cuando se indexa un documento se siguen las siguientes etapas:
  1. tokenización: separa las palabras delimitadas por espacios o signos de puntuación.

  2. filtrado de stop words: elimina las palabras muy frecuentes (preposiciones, artículos, pronombres)

  3. stemming: elimina los sufijos de las palabras (palabras, conjugaciones verbales, etc) para reducirlas a su raíz

Los términos resultantes de este proceso son los términos del documento. Los componentes o pesos del vector de un documento se construyen según el número de veces que aparece cada término en el documento. Estos pesos se dividen después por el número de documentos que contienen cada término. Así, el peso de un término es directamente proporcional al número de veces que aparece el término en el documento e inversamente proporcional a los documentos que contienen dicho término en toda la colección. Esta forma de definir los pesos se denomina TF-IDF (term frequency inverse document frequency).

Para buscar en los documentos, el usuario introduce una cadena de búsqueda. El motor de búsqueda genera una lista de documentos ordenada según la similitud con la cadena de búsqueda. La similitud entre la cadena de búsqueda y un documento se obtiene utilizando como métrica de similitud el coseno del ángulo que forman los dos vectores (el de la cadena de búsqueda y el del documento). Para ello se calcula el producto escalar de los dos vectores y se divide por la raíz cuadrada del producto de los módulos de los dos vectores. La similitud de un documento y una cadena de búsqueda depende altamente del número de términos que tienen ambos en común.

A veces, el vector de términos se compone de varios subvectores. Cada subvector representa un aspecto diferente del documento. Por ejemplo, un subvector podría contener los términos extraidos del documento, otro subvector podría contener las frases del documento, y otro subvector podría contener metadatos del documento (autor, fecha, etc). La similitud en este caso se calcularía como la suma ponderada (con pesos que hay que definir) de las similitudes de los distintos subvectores.

2. Efectividad de los sistemas de information retrieval

Existen varias medidas de la efectividad de un sistema de búsqueda. Habitualmente se confrontan precisión y recall. Precisión es la proporción de documentos resultados de la búsqueda que son relevantes. Recall es la proporción de documentos relevantes que se obtienen como resultado (frente a todos los documentos relevantes). Un sistema ideal de búsqueda obtendría un valor de 1.0 para ambas medidas. En la práctica, precisión y recall están inversamente relacionadas.

martes, 9 de junio de 2009

Búsquedas conceptuales utilizando WordNet

1.Introducción
Cuando se realiza una búsqueda en un motor de búsqueda tradicional se introducen una serie de palabras clave (cadena de búsqueda) y el motor nos devuelve una gran cantidad de páginas como resultado. Estas páginas están ordenadas según su relevancia (cada motor tiene su propio algoritmo para determinar la relevancia de cada página resultado).
Hay dos problemas con los buscadores tradicionales:



  1. algunas páginas resultado no son relevantes (no interesan al usuario)

  2. las páginas no se agrupan por contenidos similares


El primer problema se puede resolver extendiendo la cadena de búsqueda, para que los resultados tengan mayor precisión, es decir, se acerquen más a lo que está buscando el usuario.



El segundo problema se puede resolver analizando los resultados obtenidos y calsificándolos según la ocurrencia o no de términos relevantes.



Para ambos problemas podemos utilizar WordNet. WordNet es una base de datos de conceptos. Cada concepto contiene la palabra o palabras con las que se expresa el concepto. Además, los conceptos se relacionan entre sí mediante relaciones conceptuales (herencia, composición, etc.). Cuando una palabra tiene múltiples significados, aparecerá asociada a múltiples conceptos.



2.Búsqueda inteligente



Con la información disponible en WordNet podemos mejorar los resultados de los buscadores tradicionales de dos modos:




  1. antes de la búsqueda: especificando el concepto exacto que se quiere buscar (en lugar de especificar la palabra)

  2. después de la búsqueda: clasificando los resultados obtenidos (agrupando los resultados en función del concepto del que se habla)


2.1 Mejora antes de la búsqueda

Cuando el usuario escribe una palabra a buscar, el sistema le presenta la opción de elegir entre todos los conceptos asociados a esa palabra (utilizando los conceptos asociados a una palabra en WordNet). Se muestra para cada concepto su definición y un ejemplo de uso, para facilitar su elección. El usuario puede elegir uno de estos conceptos o bien buscar todos los sentidos.


Cuando el usuario elige un concepto determinado, la cadena de búsqueda se expande utilizando la información que almacena WordNet. La cadena de búsqueda extendida se envía al buscador para que retorne únicamente resultados que están asociados al concepto seleccionado.

Para extender la cadena de búsqueda se añaden las palabras asociadas al mismo concepto (sinónimos), después se añaden las palabras asociadas a los conceptos hipónimos (conceptos hijos en herencia). Si no existieran conceptos hipónimos, se utilizarían las palabras de los conceptos hipérnimos (conceptos padre en herencia).

2.2 Mejora después de la búsqueda
Cuando el usuario no selecciona ningún concepto antes de la búsqueda, la cadena de búsqueda original se lanza como tal al motor de búsqueda. Los resultados se clasificarán según la información disponible en WordNet.
Junto a los resultados de la búsqueda, se mostrarán los conceptos asociados a la palabra buscada.

Pinchando sobre uno de esos conceptos, se expandirá la búsqueda para filtrar por dicho concepto.

WSI. Identificación de sentidos de las palabras

La identificación del sentido o sentidos (en adelante WSI, Word Sense Identification en inglés) de una palabra en un texto de forma automática es una labor muy compleja para un ordenador. Se trata de asociar cada palabra del texto (usualmente sólo los sustantivos y a veces los verbos) al sentido adecuado. Si cada palabra tuviera un único sentido, esta tarea sería muy sencilla. Pero los idiomas como el español o el inglés son polisémicos, es decir, una palabra puede tener múltiples significados. Por tanto, la tarea de WSI consiste en identificar el sentido adecuado de cada palabra dentro de un texto.
El 12% de las palabras del inglés son polisémicas. Sin embargo, ese 12% (que parece una cifra muy baja) supone aproximadamente el 83% de las palabras utilizadas habitualmente.
Existen dos métodos para realizar WSI:
  • topical context
  • local context

Topical context busca sustantivos que co-ocurren habitualmente para un significado de una palabra polisémica. Por ejemplo, la palabra Java puede significar un lenguaje de programación o una isla del Pacífico (entre otras cosas). En un texto donde aparezcan co-ocurrencias como "java", "objeto", "clase", hay una probabilidad alta de que la palabra "java" se refiera aquí al lenguaje de programación. Sin embargo, si aparecen palabras como "java", "Pacífico", Indonesia", "budismo", probablemente se esté refiriendo a la isla de Java.

Local context busca pistas sintácticas y semánticas en palabras vecinas. Por ejemplo, "lenguaje java", "isla de java", permitirían identificar claramente el significado de la palabra "java" en cada uno de los casos.

Topical context funciona muy bien para identificar sentidos que no están relacionados semánticamente, como en el caso de la palabra "java" (sus significados están muy alejados semánticamente). Se trata de buscar las palabras vecinas en una ventana (de por ejemplo 50 palabras, o de dos sentencias) sobre la palabra a identificar.

Cuando los significados están cercanos semánticamente, el rendimiento de topical context cae. Por ejemplo, la palabra "bajo" que puede ser (entre otros significados) un instrumento musical o una voz en un coro. Ambos significados están cercanos semánticamente, ya que ambos están dentro del contexto de la música. En este caso, habría que utilizar local context. Se ha demostrado que las personas, cuando escriben, asignan un significado a una palabra polisémica en una ventana de 2 palabras alrededor de la palabra (o sea, 5 palabras en total: la palabra polisémica, las dos palabras anteriores y las dos palabras posteriores).

miércoles, 3 de junio de 2009

Video de las RASPINAS

Raquel, Cristina y Patri han hecho un video increible, es de lo más divertido que haya visto nunca:
http://www.youtube.com/watch?v=nIJyGjYt2do

Aquí lo teneis:

Bienvenida

Hola, este es mi blog.
Soy José Antonio Quiles Follana , joseanquiles en internet. Empecé mi carrera profesional en INISEL (ahora INDRA) en el departamento de Guerra Electrónica en 1990, luego estuve como científico colaborador en el departamento de bioingeniería y telemedicina de la Universidad Politécnica de Madrid, después pasé a Telefónica I+D donde estuve 15 años y finalmente he vuelto al grupo Indra, donde llevo desde octubre de 2010. Me apasiona la informática y todo lo que le rodea. Pero además tengo otras aficiones como la lectura, la fotografía y la acuarela, sobre las que también escribiré en este blog.

Trataré sobre:
  • Java
  • J2EE
  • Servicios Web
  • Interfaces de Usuario
  • Generación automática de código
  • Procesamiento de lenguaje natural (NLP)
  • Text mining
  • etc etc etc

Pero ahora mismo me voy a centrar fundamentalmente en NLP y Text Mining, dos áreas que estoy empezando a investigar. Me voy a centrar además en el idioma español, donde hay muy pocos recursos y donde la complejidad inherente al propio idioma hace que tengamos un reto muy interesante por delante.

Espero que os guste y que escribais muchos comentarios...