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: | 12:30 26/09/2011 | |
Duración aproximada: | 1:30 horas | |
Persona de contacto: | Forcada Zubizarreta, Mikel L. ( ) | |
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 ]