Generación de expresiones referenciales bajo incertidumbre con teoría de modelos

Abstract

En esta tesis investigamos la generación automática de rankings de expresiones referenciales en contextos con incertidumbre. Las posibles aplicaciones de la generación de expresiones referenciales que deben referirse al mundo real (software para robots, sistemas gps, etc.) sufren de incertidumbre por datos ruidosos de sensores y modelos incompletos de la realidad. Extendemos técnicas y algoritmos de teoría de modelos y simulaciones integrando una distribución finita de probabilidades que representa esta incertidumbre. El objetivo es generar un ranking de las expresiones referenciales ordenado por la probabilidad de ser correctamente interpretada en el contexto. En primer lugar, se desarrollaron técnicas y algoritmos de generación de expresiones referenciales que extienden algoritmos clásicos de minimización de autómatas. Los algoritmos de minimización se aplicaron a la caracterización de modelos de primer orden. Dichos algoritmos fueron extendidos usando probabilidades aprendidas de corpora con técnicas de aprendizaje automático. Los algoritmos resultantes fueron evaluados usando técnicas automáticas y evaluaciones de jueces humanos sobre datos de benchmarks del área. Finalmente se recolectó un nuevo corpus de expresiones referenciales de puntos de interés en mapas de ciudades con distintos niveles de zoom. Se evaluó el desempeño del algoritmo en este corpus relevante a aplicaciones sobre mapas del mundo real.

In this thesis we investigate the automatic generation of referring expression rankings in uncertain contexts. The potential applications of automatic generation of referring expressions that need to refer to the real world (e.g. robot software, gps systems, etc) suffer from uncertainty due to noisy sensor data and incomplete models. We extend techniques and algorithms from model theory with a finite probability distribution that represents this uncertainty. Our goal is to generate a ranking of referring expressions ordered by the probability of being interpreted successfully. First, we developed techniques and algorithms for generating referring expressions that extend classical algorithms for automata minimization applied to first order model characterization. Such algorithms were extended using probabilities learned from corpora using machine learning techniques. The resulting algorithms were evaluated using automatic metrics and human judgements with respect to benchmarks from the area. Finally, we collected a new corpus of referring expressions of interest points in city maps with different zoom levels. The algorithms were evaluated on this corpus which is relevant to applications with maps of the real world.