Departamento de Lenguajes y Sistemas Informáticos

Comunicación

Título:ATENCIÓ CANVI DE SALA: Algoritmos eficientes de estados finitos para la aplicación de gramáticas locales Incorpóralo a tu calendario:
Tipo:Conferència
Por:Javier M. Sastre-Martínez
Lugar:Seminari de 3r cicle
Día/hora:26/09/2011 12:30
Duración aproximada:1:30 horas
Persona de contacto:

Forcada Zubizarreta, Mikel L. (mlf[Perdone'm]dlsi.ua.es)
Resumen:
Este trabajo se centra en la investigación y el desarrollo de algoritmos
eficientes de aplicación de gramáticas locales, tomando como referencia
aquellos que están siendo usados en sistemas open-source, a saber: el
analizador sintáctico top-down de Unitex y el analizador sintáctico à
la Earley de Outilex. Las gramáticas locales son un formalismo basado en
autómatas finitos para la representación de la sintaxis de los lenguajes
naturales. Estas gramáticas constituyen un modelo de construcción de
descripciones precisas y a gran escala de la sintaxis de los lenguajes
naturales mediante la observación sistemática y la acumulación metodológica
de información. La idoneidad de las gramáticas locales para esta tarea ha
sido demostrada por múltiples trabajos. Debido a la naturaleza ambigua de
la lengua y a las propiedades de las gramáticas locales, los analizadores
sintácticos clásicos tales como LR, el de CYK y el de Tomita no son viables
o requieren modificaciones no triviales para ser usados en el contexto de
este trabajo. Los analizadores sintácticos top-down y de Earley son posibles
alternativas, aunque tienen un coste asintótico exponencial en el caso de las
gramáticas locales. Partiendo del algoritmo de Earley, hemos desarrollado un
nuevo algoritmo de aplicación de gramáticas locales con un coste polinomial
en el peor de los casos. A continuación, hemos desarrollado estructuras
de datos más eficientes que aquellas propuestas por la Standard Template
Library (STL) para la gestión de conjuntos de elementos y de secuencias;
estas estructuras han permitido mejorar la eficiencia de nuestro algoritmo
en condiciones generales. Finalmente hemos comparado nuestro algoritmo
con aquellos de los sistemas Unitex y Outilex (y nuestras estructuras de
datos con aquellas de la STL) en el contexto de una aplicación industrial
propuesta por Telefónica I+D: aumentar la capacidad de comprensión del agente
conversacional MovistarBot mediante el uso de gramáticas locales. A pesar
del dominio restringido de las gramáticas aplicadas (oraciones de solicitud
de servicios en línea), obtuvimos tiempos de ejecución menores con nuestros
algoritmos y estructuras de datos. Gracias al coste asintótico reducido de
nuestro algoritmo, tiempos de ejecución significativamente inferiores son
de esperar para el caso de gramáticas de gran cobertura.
[ Tancar ]