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

Abstract

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.