jueves, 7 de febrero de 2013

Diccionario de Entidades Colombianas - Extraccion de Informacion

He trabajado las ultimas semanas en un sistema basado en bootstrapping para capturar automaticamente Entidades (Personas, Lugares, Organizaciones del ambito colombiano) de Texto puro.

La idea de estos diccionarios es que sean utiles en diferentes tareas en las areas de Extraccion de informacion y mineria de datos.
Agrege ciertas entidades de manera manual  y espero seguir agregando nuevas entradas para posteriormente crear una taxonomia de diccionarios.

Para completar la lista agrege un diccionario de jerga latinoamericana (Inclueyendo expresiones multipalabras (Multiword Expressions)) generada automaticamente. Tambien una lista creada manualmente de adjetivos positivos, negativos y sensoriales que pienso extender proximamente.

El repositorio Diccionario de Entidades Colombianas en Github contiene las listas.
Aqui dejo una descripcion



Diccionario de Entidades Colombianas

Esta es una lista de Gazeteers( Diccionarios de Entidades) generados automatica y manualmente. Contiene diccionarios de:

Personas

  • Politicos Colombianos
  • Senadores Colombianos por Partido
  • Presidentes Colombianos
  • Periodistas Colombianos
  • Criminales Colombianos
  • Atletas Colombianos
  • Actores Colombianos

Locaciones

  • Ciudades Colombianas

Organizations

  • Empresas Colombianas
  • Equipos Colombianos de Futbol
  • Abreviaciones de Organizaciones Colombianas
  • Bandas de Musica Colombianas

Utilidades

  • Lista de Adjetivos Negativos
  • Lista de Adjetivos Positivos
  • Lista de Adjetivos Sensoriales
  • Lista de Jerga Latinoamericana con expresiones multipalabra

jueves, 24 de enero de 2013

Semisupervised Learning - Label Propagation

I attach my slides for my seminar presentation on "Semisupervised Learning - Label Propagation ".
The slides are based on the paper: "Learning from Labeled and Unlabeled Data with Label Propagation " by  the very famous Xiaojin Zhu


Implementations of Label Propagation:


Java Label Propagation by Kohei Ozaki
Junto by Partha Pratim Talukdar
Label Propagation (C++ Implementation) with visualization by Kohei Ozaki



Slides



lunes, 14 de enero de 2013

Arriving to Saarbruecken - a guide for students

If you are reading this post, you are coming to Saarbruecken, and as I was in 2011 this is your first time living abroad or at least in Germany, you are probably travelling soon and you want to get some information.
I arrived to Saarbruecken in 2011 in order to study my master degree, and I write this entry as it might be helpful for anybody arriving here.

Accommodation:

There are for me two options, either one studio or a room in a flatshare.
I've always lived in flatshares, I think it is nice to share with people and at same time the prices are lower than a studio.
If you plan to look for either of them from abroad it will be rather difficult.
People will requite to see you face to face, and doubt of those who do not want to.
The best option is to contact people who are studying the same degree as you will be studying and are seniors. Students here are really willing to help,  they will help you by letting you stay somedays at their places while you find a good offer.
The other option is to pay a hostel, the drawback is: there are not that many hostels in SB.
When renting watch out the contract, most of the times is in German and some very few people will take advantage of this is you are not careful enough.

Some Contracts will require you to : paint your place before cancelling, some of them will have a notice period of at least 3 months(the usual) but it can be longer or none at all.
Usually the contract also establishes the concept of a deposit, this is usually given back to you within  6 months after you return the room to the landlord.


Locations to live?


In saarbruecken you can find all kind of prices everywhere. There are many areas with their own advantages and disadvantages.
I would divide them into:
Saarbruecken city, Dudweiler and Scheidt.

Saarbruecken city is the 'city', where all the pubs are, where the parties take place. If you plan on having an active life in the pubs ,parties and other social activities you should pick this area.
Why? The public transportation in Saarbruecken is good, I love it, but in the night many services to many areas are shut down, so if you live in another area, forget about staying in saarbruecken longer than 1am.

Scheidt and Dudweiler. This is where I live (Dudweiler), I love it. why? it is small, beautiful and I can take a bus which is 5mins away from university. there is nothing more to say, this used to be a small town that was absorved by Saarbruecken. There is no much activity here ,but many students live in this area.
Scheidt is a little bit further, but it is more or less the same as Dudweiler.

When comparing prices, you can find similar prices in all the areas.

websites for looking accommodation: http://www.wg-gesucht.de/


I arrived, what to do next?

Once you arrived focus on finding a place and once you have signed a contract with your landlord.
you have to register in the Burgeramt. The Burgeramt is an office which will register where you are living. You just have to take your passport and contract with you, they will give you a piece of paper called "Anmeldungbestaetigung", this is an important document for opening a bank account and doing other bureaucracy procedures.









martes, 11 de diciembre de 2012

Automatic Generation of Domain Models for Call Centers from Noisy Transcriptions

I attach my slides for my seminar presentation on "Ontologies and Knowledge Representation".
The slides are based on the paper:
"Automatic Generation of Domain Models for Call Centers from Noisy Transcriptions " by  Shourya Roy and Venkata Subramaniam

The paper considers an automatic way to build a taxonomy from raw text. It also considers potential applications of the automatic built taxonomy

lunes, 10 de diciembre de 2012

Presentacion sobre Tecnologias del Lenguaje

Hace poco hice una corta presentacion para la semana de la expresion en la Universidad del Valle sede Tulua sobre Tecnologias del Lenguaje.

Me aventure a realizar mi presentacion con www.prezi.com
La presentacion esta disponible aqui para quienes quieran verla,usarla o mejorarla;
http://prezi.com/3azvcqs6rtkr/ensenandole-a-la-computadora-a-hablar-semana-expresion-2012-univalle/

Para mas informacion sobre el evento http://comunicaciones.univalle.edu.co/InformesPrensa/2012/noviembre/OC-299-2012.html


lunes, 5 de noviembre de 2012

Como funciona Google Search Voice de Android - Sistema de Preguntas-Respuestas


La nueva versión de Android introduce un sistema de búsqueda por voz mas sofisticado que en versiones anteriores.
Pero como funciona esta tecnología? entienden realmente estos dispositivos lo que Preguntamos?.
Como puede responder a preguntas como:  ¿Cuando es el día del padre, o ¿Cual es la capital de Suecia?

Los Lenguajes naturales son la interfaz de usuario mas avanzada, imaginen un dispositivo que pueda entender en principio todo lo que decimos,
seria impresionante no? imaginen que en vez de programar en 'lenguajes de programación' pudiéramos darles ordenes a un alto nivel a nuestros dispositivos en espaniol, imaginen a la abuelita programando!

En este post intentare explicar los principios de como funcionan los sistemas de Preguntas & Respuestas..

La diferencia entre Conocimiento e Información


Vivimos en la era de la información, o eso dicen, pero ¿que quiere decir exactamente?
para mi quiere decir que tenemos acceso a gran cantidad de contenidos y al mismo tiempo
que estamos en capacidad de generar contenidos y compartirlos con otros.

Por ejemplo: compartimos contenido cuando tweeteamos, cuando opinamos sobre productos en twitter estamos generando información, generamos información cuando publicamos en 4square que estamos en un restaurante y que nos agrada o detestamos lo que ordenamos para comer.
Conocimiento es usar grandes cantidades de información para establecer ,por ejemplo, patrones de comportamiento, tomar decisiones, predecir sucesos.
generas información cuando escuchas música y usas el scrobber de last.fm para almacenar las canciones que has escuchado durante el ultimo anio, conocimiento es cuando last.fm en base a todas esas canciones te recomienda una canción nueva que probablemente te agrade.

Ahora mismo vivimos un boom en cuanto a la generacion de conocimiento, el boom esta tomando lugar por que existen las plataformas para generar y compartir informacion. Esto implica dos problemas:

1. Es demasiada información ? como procesarla?, de allí el éxito de la computación en la nube y frameworks como hadoop que facilitan a los desarrolladores trabajar en ambientes distribuidos

2. La información no esta estructurada, es decir no es una gran Base de datos a la cual podemos consultar con sql, todo lo que la gente escribe en blogs, foros, twitter,facebook,reddit es lenguaje natural.. el reto esta en como extraer información y relaciones entre la información descrita en estos lenguajes.


Recuperación de Información


Recuperación de información es lo que ha hecho Google durante todo este tiempo. Formalmente es: dado un conjunto de palabras clave, retornar una lista de documentos que se relacionen con las palabras clave.
Este es el paradigma que hemos usado todo este tiempo, Si es el mejor o no, es una discusión.
Lo que si es cierto, es que queremos optimizar nuestro tiempo, no queremos perder nuestro tiempo buscando y leyendo documentos que no nos interesan.
Imagina que quieres comprar un nuevo teléfono , el teléfono X, probablemente antes de comprarlo quieras saber:

1.Que opina la gente que ya compro ese teléfono
2.Comparativas entre el teléfono X y sus competidores mas cercanos


Lo que tu haces, es generar distintas búsquedas en Google, leer un foro, probablemente alguien hizo una pregunta en Yahoo Answers como "cual teléfono debo comprar el X o el Y?" ..etc.. generas varias búsquedas, lees un poco de los resultados arrojados.. ¿talvez buscas algo relacionado en twitter?, y finalmente tomas tu decisión.

Imagina un sistema, que no solo indexe la información de la web si no que ademas razone sobre ella,que entienda lo que esta escrito.
Entonces le podrías decir que te haga un resumen/compendio sobre el teléfono X, y en vez de una lista de sitios web , te devuelva talvez una lista solo con las opiniones, comparaciones que es realmente lo que te interesa para tomar tu desicion...
esto, para mi, es la recuperación de inforamcion en el futuro...¿por que? : por tiempo (vas a usar menos tiempo), el resultado que obtengas sera tan preciso como sea tu pregunta, y si no es precisa sera un overview a gran escala de muchas fuentes diferentes, así, talvez los resultados que obtengas no sea información si no, conocimiento, eso es el poder de la información.

Ok... lo anterior fue un poco de fantasía, talvez en 5? 10? anios?, no lo se.
Aterrizando un poco al 2012 creo que Google le apunta a ello, tienen la información y quieren procesarla, de allí apuntarle a los sistemas de preguntas y respuestas.



Sistemas de Pregunta/Respuesta


A un sistema de preguntas y respuestas, le lanzas una pregunta, el sistema en vez de responderte con una lista de documentos que se relacionen con las palabras en la pregunta, te da una respuesta concreta o cercana a la pregunta que fue ingresada.
¿Esto es magia?.. no, es procesamiento de lenguaje natural.

Lo que probablemente esta haciendo Google en estos momentos es generando una ontologia ( una representación del conocimiento) donde se especifican conceptos y relaciones entre esos conceptos. Creo que ello hace parte de lo que ellos llaman "TheKnowledge Graph" , si van al sitio web, pueden navegar entre conceptos (ejemplo: Italia) y como se relaciona un concepto con otros (ejemplo: Italia<-> davinchi).
La que probablemente están haciendo es algo llamado: OpenInformation Extraction, que consiste en extraer conceptos y relaciones de texto en lenguaje natural.

Por ejemplo, a partir de un noticia que diga:

"La esposa de barack obama, michell, ha participado con la fundación X..."

El sistema de Google extrae un registro:

( michell obama, participar, fundacion X)

Obviamente mas relaciones son posibles aun para este ejemplo juguete que acabo de dar.
Ejemplo:
(michell, esposa de, obama).. (fundacion X, trabaja con, michell obama)....



A partir de esos registros crea una ontologia como la 'the knowledge graph' automáticamente.
Obviamente esto requiere muchos procesos relacionados con inteligencia artificial , tienes que entrenar sistemas para que reconozcan cosas mas avanzads por ejemplo que a partir de una relación como :

 "X fue asesinado por Y" se concluye que otra relacion : "X esta muerto"

se que parece muy sencillo, pero a nivel computacional es muy muy difícil, por que involucra lo que llamamos "sentido común"...

Apatir de esta ontologia se puede crear un sistema que permita responder preguntas, aquí el sistema tiene que 'entender la pregunta'.. y en base a ello calcular la posible respuesta



¿Como entender la pregunta y encontrar la respuesta?


Lamentablemente no contamos con sistemas muy avanzados con respecto al entendimiento de lenguajes. En mi humilde opinión, solo son trucos estadísticos que crean la fantasía que la computadora puede entender lo que decimos.

Supongamos que la pregunta al sistema es, "donde murio Michael Jackson?".
El componete del sistema encargado de procesarla se fija en varias cosas:

1,Encontrar una partícula que le indique que tipo de pregunta es y que es lo que esta buscando.
en este caso "Donde" le indica que lo que esta buscando como respuesta es una "locación", lo que sea la respuesta debe de ser en su base de conocimientos una "locación"..

2.Encontrar el tema de la pregunta, tiene que descartar las palabras menos relevantes, y encontrar la mas predominante, en este caso el tema es "michael Jackson".

3.Usar las palabras del contexto para encontrar posibles relaciones. en este caso podría ser la palabra "morir"..


A partir de ello el sistema sabe que va a buscar algo en la ontologia que tiene que ver con "Michael Jackson", que lo que va a retornar como respuesta tiene que ser una locación en la ontologia, y ademas que la relación entre ese lugar y "Michael Jackson" tiene que ver con: "muerte","morir"..

Peros...


Pero como saber si todas las relaciones que se extraen son correctas? que tal si alguien escribe: "Michael Jackson murio en Bogota, Colombia..."" entonces la Base de conocimientos es errónea..y las respuestas serán erradas..
Lo que ocurre en este tipo de casos es que muy probablemente Google descarta las relaciones encontradas en ciertos sitios, o usa por ejemplo el sistema de búsquedas actual lanzando una búsqueda como "michael jackson muere en bogota" si esta consulta arroja menos de cierta cantidad de resultados entonces la considera como una relación falsa.

Una pregunta con la partícula "Donde" es fácil de responder, buscas un lugar, pero ¿que pasa con: "Como" o "Por que"?..
estas preguntas requieren un razonamiento mas avanzado, y no creo que tengamos pronto un sistema que pueda resolverlas.


Finalmente..


El tema de lenguaje natural es algo filosófico al momento:) lo que si es seguro es que companias como Google y Apple le apuesten fuertemente a iniciativas en esta dirección, y en mi opinión el siguiente gran salto en interfaces de usuario va relacionado con poder entender los lenguajes naturales y poder generar frases en estos lenguajes tal que estas frases suenen lo menos robóticas posibles. (alguien ha escuchado a Hatsune Miku? <3 )

este es un articulo divertido con varias preguntas que le hacen al sistema "70 things to try with Google's Android 4.1 Voice Search"

Espero este articulo les de una idea de como funcionan ciertos servicios, los cuales probablemente se van a volver muy sofisticados en los próximos anios.


@dav009

jueves, 25 de octubre de 2012

Analizadores Sintacticos : Dependency Parsing

Analizadores Sintacticos : Dependecy Parsing

Un Analizador Sintactico es un componente de Software cuya entrada es una oracion especificada en un lenguaje (formal o no formal) y como salida arroja una estructura que representa las relaciones entre los componentes de la oracion de entrada.

En Ciencias de la computacion normalmente un parser o analizador sintactico es un sub-componente de los compiladores de los lenguajes de programacion.
Este componente se encarga de asegurarse que las intrucciones esten definidas correctamente segun una gramatica.
Adicionalmente el analizador sintactico retorna una estructura de datos, usualmente un arbol que establece relaciones entre los componentes de la oracion de entrada, usualmente este arbol es usado posteriormente por un analizador semantico que se encarga de 'traducir' el significado de una oracion a lenguaje de maquina.
 Los lenguajes de programacion se consideran lenguajes formales y parsearlos es, digamos, un problema resuelto.


Parsing en Procesamiento de Lenguaje Natural

En el procesamiento de Lenguaje Natural existen componentes de software que analizan sintacticamente una oracion. Sin embargo en el contexto de lenguajes no formales el reto es mas complicado, existen una gran cantidad de variaciones, y posibilidades para expresar ideas, de manera correcta.
A nivel Linguistico existen muchas discusiones en las que se debaten como saber si algo es gramatical o no, la mejor respuesta al momento es: preguntele a un nativo de ese idioma si una frase es gramatical o no.

A nivel de Lenguaje Natural existen algoritmos de parseo muy conocidos como es el Algoritmo de CYK(
Cocke–Younger–Kasami),  este algoritmo recibe una gramatica libre de contexto que especifica las reglas para formar oraciones correctas en un lenguaje (por ejemplo: espaniol, ingles...etc) y apartir de estas reglas es capaz de establecer : 

  • Si una oracion  es correcta o no con respecto a la gramatica
  • En caso de ser una oracion correcta construye un arbol de derivacion sintactica. Es decir un arbol en el cual se especifica la relacion entre los componentes de la oracion con respecto a la gramatica especificada

Arbol de derivacion Sintactica de Ejemplo

El arbol en la imagen representa la salida de un analizador sintactico para la oracion "john ha limpiado la impresora". 
NP= Noun Phrase (frase Nominal)
Aux=Verbo Auxiliar
VP=Verb Phrase (Frase Verbal)
Det =Determiner = Determinante
N=Noun=Sustantivo
Este arbol fue establecido a una gramatica que define cada uno de los componentes anteriormente mencionados. Las gramaticas en este caso CFG( context free grammar) usualmente se escriben en notacion BNF.
En esta gramatica almenos deberia existir una regla que diga por ejemplo que:

S=NP AUX VP
Npr= John
N=impresora
NP=Npr | DET N
...
Para poder generar este tipo de arboles sintacticos se necesita de un experto, seguramente un linguista que pueda especificar las reglas del lenguaje que se desea modelar. Ello puede ser un trabajo muy arduo y complicado, se necesitan muchas reglas para poder capturar la esencia de un lenguaje.

Dada la dificultad mencionada se empezo a usar aprendizaje de maquina para construir analizadores sintacticos que puedan aprender en base a un conjunto de ejemplos con arboles de parseo.
De esta forma no se necesita de la especificacion de miles de reglas para cosntruir un analizador que arroje resultados medianamente buenos.


Dependency Parsing 

El analisis sintactico que mencione en la seccion anterior genera arboles que establecen la relacion entre los constituyentes linguisticos de una oracion, es decir establece cual es la verbo de una oracion, y atraves de la construccion del arbol establece cual es posible sujeto y objeto de una oracion.
Este tipo de parseo resulta no solo computacionalmente caro (la complejidad de CYK(O(N^3)) ) si no que ademas el resultado es dificil de usar en las aplicaciones.

Los analizadores sintacticos nacieron de  la necesidad de tener un analizador sintactico que sea computacionalmente mas 'barato' y cuyos resultados sean mas faciles de usar a nivel aplicativo.
Un analizador sintactico retorna como salida un Grafo dirigido no ciclico, este grafo recibe el nombre de grafo de dependencias.
En este grafo las palabras corresponden a Nodos y las aristas corresponden a relaciones entre palabras.
Cada arista del grafo tiene una etiqueta que identifica la relacion entre las dos palabras.

Ejemplo:
Ejemplo Derivacion Sintactica por Dependencias

En este ejemplo 'Subj' significa que la relacion entre john y hit, es la de 'sujeto'.
Y que 'the' es el determinante de 'Ball'.
Es una estructura mucho mas simple que la de un arbol de constituyentes (La imagen del primer ejemplo) porque es una estructura mas facil de procesar computacionalmente hablando, pues no contiene otros constituyentes anidados como es el caso del primer ejemplo.

El parseo por dependencias se usa en una gran cantidad de aplicaciones, por ejemplo en extraccion de informacion para identificar cuales son los objetos asociados a una relacion, extraccion de entidades...

Existen dos implementaciones de Analizadores sintacticos muy famosas, el MaltParser  y el MSTParser.


MaltParser
Web: http://www.maltparser.org/

El MaltParser funciona usando un algoritmo basado en transiciones.
Basicamente tiene una serie de estados y un clasificador basado en ejemplos es capaz de determinar para cada caso en particular que estado es el mas adecuado para llegar a un grafo de dependencias correcto.

Para la toma de esta desicion el clasificador entrenado toma en cuenta que tipo es la palabra que actualemtne esta analizando, que otras palabras se encuentan alrededor, que otras relaciones ha identificado al momento.

El Maltparser ha arrojado en sus experimentos buenos resultados con lenguajes cuyo orden es menos flexible por ejemplo: chino, ingles, espaniol.
Para lenguajes donde el orden es flexible Mlatparser tiene problemas , es el caso de turco y checo por ejemplo.
Lo anterior se debe a que el MaltParser asume ciertas restricciones sobre los grafos de dependencias, estas restricciones no le permiten manejar cierta cantidad de construcciones que son mas comunes en lenguajes cuyo orden es mas flexible.



MSTParser
Web: http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html

Este Constructor de Analizadores Sintactico aprende al igual que el Malt apartir de una serie de ejemplos parseados.
Apartir de esos ejemplos el MSTParser es capaz de calcular una funcion que dado un grafo evalua que tan probable es que ese grafo sea correcto. Apartir de esa funcion esta estrategia busca dada una oracion, el grafo para esa oracion cuyo valor  es el maximo.
El MST es en otras palabras un problema de optimizacion donde se busca el grafo con mayor peso posible segun una funcion de peso.

Comparacion

Ambos Malt y MST tienen puntajes excelentes de porencima del 80% analizando sintacticamente diferentes lenguajes.

El MaltParser usa un algoritmo que es Voraz (Greedy) para cada estado dentro de su procesamiento escogera aquel que parezca de momento el mas adecuado. En contraste el MSTParser busca dentro todo el espacio de posibles grafos, cual seria la combinacion mas apropiada para obtener el grafo mas probable.
Ambos tienen sus ventajas y desventajas. Por ejemplo el MaltParser es capaz de capturar con mejor rendimiento construcciones particulares, esto con el costo que un error sera propagado para el resto de las desiciones a tomar.

Algunos Papers han propuesto la union de ambos metodos, como es el caso de: Integrando MST y MALT