Learning Distributions over Logical Forms for Referring Expression Generation

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1914–1925, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Learning Distributions over Logical Forms for Referring Expression Generation Nicholas FitzGerald Yoav Artzi Luke Zettlemoyer Computer Science & Engineering University of Washington Seattle, WA 98195 {nfitz,yoav,lsz}@cs.washington.edu Abstract We present a new approach to referring ex- pression generation, casting it as a density es- timation problem where the goal is to learn distributions over logical expressions identi- fying sets of objects in the world. Despite an extremely large space of possible expres- sions, we demonstrate effective learning of a globally normalized log-linear distribution. This learning is enabled by a new, multi-stage approximate inference technique that uses a pruning model to construct only the most likely logical forms. We train and evaluate the approach on a new corpus of references to sets of visual objects. Experiments show the approach is able to learn accurate models, which generate over 87% of the expressions people used. Additionally, on the previously studied special case of single object reference, we show a 35% relative error reduction over previous state of the art. 1 Introduction Understanding and generating natural language re- quires reasoning over a large space of possible meanings; while many statements might achieve the same goal in a certain situation, some are more likely to be used than others. In this paper, we model these preferences by learning distributions over sit- uated meaning use. We focus on the task of referring expression gen- eration (REG), where the goal is to produce an ex- pression which uniquely identifies a pre-defined ob- ject or set of objects in an environment. In prac- tice, many such expressions can be produced. Fig- ure 1 shows referring expressions provided by hu- man subjects for a set of objects (Figure 1a), demon- strating variation in utterances (Figure 1b) and their corresponding meaning representations (Figure 1c). Although nearly a third of the people simply listed the colors of the desired objects, many other strate- gies were also used and no single option dominated. Learning to model such variation would enable sys- tems to better anticipate what people are likely to say and avoid repetition during generation, by pro- ducing appropriately varied utterances themselves. With these goals in mind, we cast REG as a den- sity estimation problem, where the goal is to learn a distribution over logical forms. Learning such distributions is challenging. For a target set of objects, the number of logical forms that can be used to describe it grows combinatori- ally with the number of observable properties, such as color and shape. However, only a tiny fraction of these possibilities are ever actually used by peo- ple. We must learn to efficiently find these few, and accurately estimate their associated likelihoods. We demonstrate effective learning of a globally normalized log-linear distribution with features to account for context dependence and communicative goals. We use a stochastic gradient descent algo- rithm, where the key challenge is …

Content truncated to 500 words