PDF de programación - Analizadores morfológicos aplicados al lenguaje natural, aplicaciones para búsqueda de información

Analizadores morfológicos aplicados al lenguaje

natural, aplicaciones para búsqueda de

información

Gunnar Wolf -

Desarrollador del Proyecto

Instituto de Investigaciones Económicas -

[email protected]

Debian

UNAM

Advertencia



1. Introducción

Aguas

Voy a hablar en buena medida de cómo yo veo las cosas.
A ratos no voy a usar los términos más aceptados en la literatura de la materia
Esto incluye varias interpretaciones poco ortodoxas mías
El tema me encanta. Eso es lo que cuenta, ¿no? ;-)


Analizadores morfológicos aplicados al lenguaje natural, aplicaciones

para búsqueda de información

Contenido

1. Introducción
2. Ejemplo de una aplicación
3. TSearch2 en español a través de Snowball
4. ¿Y el verdadero análisis de lenguaje natural?

http://www.gwolf.org/soft/an_morf_leng_nat/

¿De qué vamos a hablar?

1. Introducción

¿Qué es un lenguaje? ¿Qué tipos de lenguaje hay?


¿Por qué puede interesarnos analizar el lenguaje natural?


Ejemplo de una aplicación (simple pero válida) para la recuperación y análisis de


información, aprovechando el análisis morfológico sobre lenguaje natural

¿Hasta dónde podemos llegar con el análisis?


¿Qué hay al respecto en la academia?


¿Cuándo utilizamos el análisis de lenguajes?

1. Introducción

Prácticamente todo sistema de cómputo puede ser definido como un analizador de un

lenguaje determinado

Toma datos de entrada
Procesa estos datos
Genera una salida
Posiblemente volviendo a la misma entrada, modificando su operación


No en vano esto suena a la descripción de una máquina de Turing


Hay diferentes tipos de lenguaje, que conllevan diferentes grados de complejidad.

Podemos (casi) decir que cada una de las siguientes categorías engloba a sus
predecesores.



Tipos de lenguajes: 1- Lenguajes descriptivos

1. Introducción

Describen una situación, un objeto, un estado, una configuración
Realmente sencillos de manejar - ¿A quién se le ocurre realizar un estudio sobre de ellos?

¡Los hay! Buscan una mayor simplicidad, legibilidad para humano y para computadora,
etc.

Incluso analizadores gramaticales simples

¿Herramientas para su análisis?
Expresiones regulares / PCRE
Analizadores léxicos simples

¿Qué entra en esta clasificación?
Archivos de configuración
Datos generados (manual o automáticamente) expresamente para su interpretación
Ejemplos
Archivos de configuración (planos, con jerarquía, etc.)
HTML / XML / YAML
Estructuras de datos simples (.DBF, .CSV, etc.)


Tipos de lenguajes: 2- Protocolos

1. Introducción

Hechos para permitir la comunicación entre (procesos|sistemas|computadoras) diferentes
Dentro de un universo de posibilidades de interacción claramente acotado


No basta analizar un pedazo estático de información, hay que analizar una charla entre


dos partes

La estructura más adecuada para representar esta conversación es un autómata de

estado finito

Una serie de estados, y eventos que ocasionan transiciones entre ellos
Estados iniciales, estados terminales


¿Qué entra en esta clasificación?
Prácticamente todos los protocolos de uso común en Internet (RFC)
Buena parte de los esquemas de comunicación entre procesos (IPC, RPC)


Tipos de lenguajes: 3- Lenguajes formales

1. Introducción

Hechos para permitir la descripción de un procedimiento (un algoritmo, un programa) o


una relación compleja

Toda construcción en un lenguaje formal se ciñe a una gramática determinada


La información escrita en un lenguaje formal es expresable en términos de un árbol de


análisis gramatical

En caso de haber posibilidad de ambigüedad, debe haber una forma clara de resolverla


La definición del lenguaje puede establecer ciertos supuestos, pero más allá de ellos, todo


debe ser explícitamente indicado

¿Aplicaciones más comunes?
Compiladores
Procesadores de texto


Tipos de lenguajes: 4- Lenguajes naturales

1. Introducción

Los lenguajes empleados por los seres humanos para su comunicación


Si bien todo lenguaje natural tiene un conjunto de reglas básicas, hay una cantidad


espeluznante de excepciones

Estamos acostumbrados a resolver ambigüedades


Podemos razonar incluso con ausencia de información importante relativa al tema
Es imposible razonar con ausencia absoluta de información externa
Emplear lenguaje natural presupone un universo de conocimiento circundante


Analizadores morfológicos aplicados al lenguaje natural, aplicaciones

para búsqueda de información

Contenido

1. Introducción
2. Ejemplo de una aplicación
3. TSearch2 en español a través de Snowball
4. ¿Y el verdadero análisis de lenguaje natural?

http://www.gwolf.org/soft/an_morf_leng_nat/

Planteamiento de la problemática

2. Ejemplo de una aplicación

Cuerpo Académico Historia del Presente

http://anuario.upn.mx/



Base de datos de artículos publicados en periódicos nacionales


50,264 artículos (al 15/2/2004), creciendo a ritmo de ~2500 mensuales


Los artículos miden en promedio 3Kb, con máximos de hasta 70Kb


La base de datos está en PostgreSQL, obviamente ;-)


Los artículos se catalogan según una serie de criterios/categorías, pero la interfaz pública


permite únicamente especificar fecha, diario, estado o texto a buscar

Planteamiento de la problemática: Velocidad

2. Ejemplo de una aplicación

¿Qué pasa cuando una persona sólo busca una palabra, sin ninguna restricción?


EXPLAIN ANALYZE SELECT id from articulo where nota like ’%analisis%’;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Seq Scan on articulo (cost=0.00..19121.67 rows=1 width=4) (actual time=3833.432..41438.090 rows=2 loops=1)
Filter: (nota ~~ ’%analisis%’::text)
Total runtime: 41438.198 ms
(3 rows)

PostgreSQL no provee un mecanismo interno para indexar campos de texto completo (FTI


- Full Text Index)

Con suficiente memoria, para las búsquedas inmediatas subsecuentes el tiempo de

consulta se reduce hasta al 5% (pues la base completa queda en cache)

No es escalable - Tarde o temprano la BD será más grande que la memoria
El uso normal del programa no implica búsquedas demasiado frecuentes
No es elegante


Planteamiento de la problemática: Inexactitud (1)

2. Ejemplo de una aplicación

Diferencia entre mayúsculas y minúsculas, acentos, etc.
6190 artículos mencionan "Educación"
5626 artículos mencionan "educación"
104 artículos mencionan "EDUCACIÓN"
147 artículos mencionan "educacion"
37 artículos mencionan "Educacion"
9 artículos mencionan "EDUCACIÓN"
8614 artículos totales (una palabra aparece de diferentes maneras en el mismo)



...Seguro hay términos con mayor variabilidad.

Este problema se aminora con el uso del operador ~* en vez de LIKE
La comparación con regex es algo más lenta que la textual (
Aunque comparando con el tiempo que toma el acceso al disco, puede ser

irrelevante

El problema sigue sin resolverse del todo (8416 para "educación", 280 para


"educacion"). No podemos asumir que todo usuario del sistema piense en ello

Planteamiento de la problemática: Inexactitud (2)

2. Ejemplo de una aplicación

Los términos relacionados deberían aparecer también como resultados
13163 artículos para "educativo"
1179 artículos para "educado"
1047 artículos para "educador"
739 artículos para "educar"
665 artículos para "educando"
73 artículos para "eduque"


...Y no estamos tomando en cuenta sinónimos, parónimos, etc.


9069 artículos para "conocimiento" mas sus variaciones (2538 no mencionan

"educación"+variantes)

2007 para "enseñanza" (574 no mencionan "educación")
1864 para "instrucción" (852 no mencionan "educación")


Buscando la solución

2. Ejemplo de una aplicación

La problemática que busqué resolver en un principio fue sólo la de la velocidad


Por un sistema previo en el que había trabajado, conocía un proyecto en Postgres que

implementaba indexado sobre texto completo: FTI

Pero no es ya considerado la mejor opción por los desarrolladores de Postgres
Requiere la construcción de tablas adicionales para cada punto donde se emplea
Tiene una sintaxis poco natural, requiere estar amarrando tablas por OIDs
Carece de un mecanismo que ordene por relevancia


El proyecto TSearch2 es desde la versión 7.3 de Postgres suficientemente maduro para


ser incluído como parte del contrib oficial

Detalles de la implementación de TSearch2

2. Ejemplo de una aplicación

TSearch2 basa su indexación en el Árbol de Búsqueda Generalizado (GiST), desarrollado

por Teodor Sigaev y Oleg Bartunov

Generaliza los mecanismos de indexación para presentar una interfaz adecuada para


diferentes tipos de comparaciones/criterios

Crea siete tipos de datos adicionales. Los principales que manipularemos directamente

son:



tsvector: Conjunto de lexemas únicos junto con su posición en el documento, con una
estructura optimizada para acceso y búsqueda rápidos. Todo documento es convertido
en su tsvector, y éste es indexado.
tsquery: Combinación booleana de lexemas, utilizada para realizar las búsquedas sobre
el índice de tsvectors

Crea cuatro tablas para regular el comportamiento general
pg_ts_dict: Definiciones de los diccionarios a emplear
pg_ts_parser: Referencia (por OID) a los analizadores morfológicos disponibles
pg_ts_cfg: Qué reglas utilizar con qué locales
pg_ts_cfgmap: Qué diccionari