Resumen de Mecanismos formales para la representación y extracción de expresiones de referencia en sistemas data-to-text

Gustavo Rivas Gervilla

• español

  En el ámbito de la Generación de Lenguaje Natural, los sistemas data-to-text tienen como objetivo producir descripciones textuales de aspectos de interés de un conjunto de datos. Uno de los problemas clave en este ámbito es la generación de expresiones de referencia, que son frases nominales destinadas a identificar unívocamente un objeto o conjunto de objetos, denominado objetivo, de otros objetos presentes en un contexto, en cuyo caso se dice que las expresiones tienen éxito referencial, y se dice que el objetivo es referible. Las expresiones de referencia permiten a los sistemas data-to-text generar descripciones mediante la referencia y la caracterización de estructuras en los datos como, por ejemplo, las regiones en las imágenes digitales. Un primer paso en la generación de expresiones de referencia en lenguaje natural es obtener una representación computacional de la semántica de la expresión utilizando algún formalismo de representación del conocimiento. Un enfoque habitual es representar una expresión de referencia como un conjunto de propiedades básicas de los objetos, que se referirá al conjunto de objetos del contexto que satisfacen todas las propiedades, si las hay. Desde un punto de vista lógico, la expresión de referencia tiene la semántica de una conjunción de propiedades. En la literatura es posible encontrar diferentes propuestas ad-hoc para determinar una expresión de referencia para un objeto o conjunto dado. Además, se han empleado varios marcos formales como la Teoría de Grafos, los Grafos Conceptuales, la Satisfacción de Restricciones y las Lógicas Descriptivas para resolver el problema de la generación de expresiones de referencia (ger). El uso de marcos formales contribuye a la solución del problema en varios aspectos. Por ejemplo, permitiendo en algunos casos un poder expresivo más allá de las simples conjunciones de propiedades. Además, la formulación de ger en términos de estos marcos formales nos permite aprovechar los algoritmos y resultados existentes en el ámbito de estos marcos para resolver el problema ger. Una de las principales contribuciones de esta Tesis Doctoral es la propuesta de un nuevo marco para ger basado en el uso del Análisis de Conceptos Formales (acf), una teoría matemática que formaliza los conceptos en un contexto como aquellos pares (A, B) tales que A es el conjunto de objetos que comparten todas las propiedades en B y, al mismo tiempo, B es el conjunto de propiedades que son satisfechas por todos los objetos en A. Demostramos que un conjunto de objetos A es referible en un contexto si, y sólo si, existe un concepto formal de la forma (A, B) en el contexto, por lo que podemos determinar los conjuntos referibles obteniendo todos los conceptos formales de un contexto, que es uno de los principales problemas en acf, y para el que existen diferentes algoritmos. Más concretamente, estos algoritmos calculan el retículo asociado al orden parcial entre conceptos formales que puede definirse en términos de inclusión de conjuntos de los conjuntos de objetos. También hemos podido utilizar este retículo para proporcionar caracterizaciones del conjunto de expresiones de referencia para cada conjunto referible, un recurso crucial para elegir la expresión más adecuada para un determinado conjunto objetivo en términos de preferencias del usuario. Estas capacidades proporcionadas por el uso de acf para ger no son proporcionadas simultáneamente por ningún otro marco formal. La otra contribución principal de nuestro trabajo se refiere a la generalización de ger al caso de propiedades graduales como «alto» para las que no es posible definir una frontera clara entre el cumplimiento y el incumplimiento de la propiedad. Una forma habitual de representar tales propiedades es mediante conjuntos difusos definidos por funciones de pertenencia que asignan un grado de pertenencia en [0, 1] a cada elemento del dominio de la propiedad. En este ámbito hemos aportado avances en dos direcciones: 1. Cuando las propiedades son graduales, el éxito referencial también lo es. Por lo tanto, es necesario proporcionar medidas del éxito referencial de las expresiones de referencia que implican propiedades graduales. En este contexto, hemos proporcionado los axiomas que debe satisfacer cualquier medida de este tipo. También hemos mostrado que es posible definir medidas de éxito referencial a partir de medidas de especificidad de conjuntos difusos, que miden el grado en que un conjunto difuso es un singleton crisp. Esto nos ha llevado a profundizar en el estudio de la especificidad, con varios resultados novedosos: primero, una caracterización de las medidas de especificidad en tres familias con comportamientos diferentes, siendo cada familia apropiada para diferentes propósitos durante la construcción y evaluación final de las expresiones de referencia. En segundo lugar, una metodología para construir medidas de especificidad a partir de medidas de distancia entre conjuntos difusos. Por último, la propuesta de medidas de posibilidad y necesidad de éxito referencial para aquellos casos en los que los grados asociados a las propiedades representan incertidumbre posibilista. Para medir el éxito referencial cuando el objetivo es un conjunto de objetos, algunos de estos resultados se han generalizado al caso de las medidas de k-especificidad, que miden el grado en que un conjunto difuso es un conjunto clásico con k elementos. 2. Hemos proporcionado una extensión de acf al caso gradual basada en la Teoría de Representación por Niveles, que es una alternativa a la Teoría de Conjuntos Difusos para representar la gradualidad. Nuestra extensión se beneficia de las principales características de la Teoría de Representación por Niveles: en primer lugar, se emplea un conjunto finito de niveles en (0, 1] para representar diferentes grados de «relajación» de los criterios de pertenencia; en segundo lugar, los conjuntos graduales se representan como asignaciones de conjuntos clásicos a niveles; finalmente, las operaciones entre conjuntos graduales se realizan como las correspondientes operaciones clásicas aplicadas a los conjuntos clásicos en los mismos niveles de forma independiente. Más allá de los conjuntos, las representaciones por niveles pueden emplearse para cualquier otro objeto y noción matemática, como elementos (como asignaciones de elementos individuales a niveles), predicados, algoritmos, etc. En consecuencia, la extensión de cualquier sistema formal crisp al caso gradual es única y directa. Además, a diferencia de los conjuntos difusos, las extensiones mantienen todas las propiedades del caso crisp. Utilizando estas características hemos podido extender nuestros resultados crisp sobre el uso de acf para ger al caso de las propiedades graduales. Para poner a prueba nuestras propuestas, hemos desarrollado un prototipo de prueba de concepto, denominado Refer4Learning, que implementa un juego referencial, un tipo muy conocido de sistema de image-to-text. El prototipo está orientado a la enseñanza de conceptos visuales básicos como el color, la forma, el tamaño, etc. a estudiantes de las primeras etapas educativas. Utilizando este prototipo, hemos realizado experimentos con sujetos adultos para analizar la correspondencia entre algunas de nuestras medidas de calidad y el rendimiento del sistema en función de las preferencias de los usuarios. Adicionalmente, mediante una colaboración interdisciplinar con investigadores en Visión por Computador, hemos demostrado que nuestras técnicas pueden integrarse con la extracción de objetos y propiedades graduales a partir de imágenes utilizando técnicas basadas en Aprendizaje Profundo, permitiendo generar automáticamente expresiones referenciales para objetos y conjuntos de objetos a partir de imágenes. Estos resultados son potencialmente útiles en varias aplicaciones como sistemas de imagen a texto, recuperación de información visual y sistemas de diálogo interactivo sobre información visual.

• English

  In the area of Natural Language Generation, data-to-text systems aim to produce textual descriptions of aspects of interest of a dataset. One of the key problems in this setting is the generation of referring expressions, which are noun phrases intended to identify and distinguish an object or set of objects, called target, from other objects present in a context, in which case the expressions is said to achieve referential success, and the target is said to be referable. Referring expressions allow data-to-text systems to generate descriptions by referring to and characterizing structures in data like, for instance, regions in digital images. A first step in the generation of referring expressions in natural language is to obtain a computational representation of the semantics of the expression using some knowledge representation formalism. A usual approach is to represent a referring expression as a set of basic properties of objects, which will refer to the set of objects in the context that satisfy all the properties, if any. From a logical point of view, the referring expression has the semantics of a conjunction of properties. In the literature it is possible to find different ad-hoc proposals for determining a referring expression for a given object or set. In addition, several formal frameworks like Graph Theory, Conceptual Graphs, Constraint Satisfaction, and Description Logics have been employed for solving the referring expression generation (reg) problem. The use of formal frameworks contribute to the solution of the problem in several respects. For instance, allowing in some cases an expressive power beyond simple conjunctions of properties. Also, the formulation of reg in terms of these formal frameworks allow us to take benefit of the existing algorithms and results in the frameworks for solving the reg problem. One of the main contributions of this Ph.D. Thesis is the proposal of a new framework for reg based on the use of Formal Concept Analysis (fca), a mathematical theory that formalize concepts in a context as those pairs (A, B) such that A is the set of objects that share all properties in B and, at the same time, B is the set of properties that are satisfied by all objects in A. We show that a set of objects A is referable in a context if and only if a formal concept of the form (A, B) exists in the context, so we can determine the referable sets by computing all the formal concepts in a context, which is one of the main problems in fca, and for which different algorithms are available. More specifically, these algorithms compute the lattice associated to the partial order between formal concepts that can be defined in terms of set inclusion of the sets of objects. We have also been able to use this lattice in order to provide characterizations of the whole set of referring expressions for every referable set, a crucial resource for choosing the most appropriate expression for a certain target set in terms of user’s satisfaction. These capabilities provided by the use of fca for reg are not simultaneously provided by any other formal framework. The other main contribution of our work concerns the generalization of reg to the case of gradual properties like “tall’’ for which it is not possible to define a clear boundary between the fulfillment and the unfulfillment of the property. A usual way to represent such properties is by means of fuzzy sets defined by membership functions assigning a membership degree in [0, 1] to every element in the domain of the property. In this setting we have provided advances in two directions: 1. When properties are gradual, referential success becomes gradual as well. Hence, it is necessary to provide measures of the referential success of referring expressions involving gradual properties. In this setting, we have provided axioms that any such measure should satisfy. We have also shown that it is possible to define measures of referential success from specificity measures of fuzzy sets, which measure the degree to which a fuzzy set is a crisp singleton. This led us to deepen into the study of specificity, with several novel results: first, a characterization of specificity measures into three families with different behaviours, each family being appropriate for different purposes during the construction and final evaluation of referring expressions. Second, a methodology for building specificity measures on the basis of measures of distances between fuzzy sets. Finally, the proposal of possibility and necessity measures of referential success for those cases in which the degrees attached to properties represent possibilistic uncertainty. In order to measure referential success when the target is a set of objects, some of these results have been generalized to the case of k-specificity measures, which measure the degree to which a fuzzy set is a crisp set with k elements. 2. We have provided an extension of fca to the gradual case based on the Theory of Representation by Levels, which is an alternative to Fuzzy Set Theory for representing graduality. Our extension benefits from the main features of the Theory of Representation by Levels: first, a finite set of levels in (0, 1] is employed in order to represent different degrees of “relaxation’’ of the membership criteria; second, gradual sets are represented as assignments of crisp sets to levels; finally, operations between gradual sets are performed as the corresponding crisp operations applied to the crisp sets in the same levels independently. Beyond sets, representations by levels can be employed for any other mathematical object and notion, such as elements (as assignments of individual elements to levels), predicates, algorithms, etc. As a consequence, the extension of any crisp formal system to the gradual case is unique and direct. In addition, contrary to fuzzy sets, the extensions keep all the properties of the crisp case. Using these features we have been able to extend our crisp results about using fca for reg to the case of gradual properties. In order to test our proposals, we have developed a proof of concept prototype, called Refer4Learning, that implements a referential game, a well-known type of image-to-text system. The prototype is oriented to teaching basic visual concepts like color, shape, size, etc. to students in the earlier stages of education. Using this prototype, we have performed experiments with adult subjects in order to analyze the correspondence between some of our quality measures and the performance of the system in terms of user’s preferences. Additionally, by means of an interdisciplinary collaboration with researchers in Computer Vision, we have shown that our techniques can be integrated with the extraction of objects and gradual properties from images using Deep Learning based techniques, allowing to automatically generate referring expressions for objects and sets of objects from images. These results are potentially useful in several applications like image-to-text systems, visual information retrieval, and interactive dialogue systems about visual information.