Reversibility reconsidered: finite-state factors for efficient probabilistic sampling in parsing and generation

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1990–1995, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Reversibility reconsidered: finite-state factors for efficient probabilistic sampling in parsing and generation Marc Dymetman†, Sriram Venkatapathy‡, Chunyang Xiao† †Xerox Research Centre Europe, Grenoble, France ‡Amazon, Machine Learning Team, Bangalore, India∗ †{first.last}@xrce.xerox.com, ‡vesriram@amazon.com Abstract We restate the classical logical notion of generation/parsing reversibility in terms of feasible probabilistic sampling, and argue for an implementation based on finite-state factors. We propose a modular decompo- sition that reconciles generation accuracy with parsing robustness and allows the in- troduction of dynamic contextual factors. (Opinion Piece) 1 Introduction The objective of Natural Language Understanding (NLU) is to map linguistic utterances to semantic representations, that of Natural Language Genera- tion (NLG) to map semantic representations to lin- guistic utterances. In most of NLP practice, these two objectives are handled by different processes, and computational linguists rarely operate at the intersection of the two subdomains. For a few years around the early nineties, based both on cognitive, linguistic, and engineering con- siderations, there was a surge of interest in so called reversible grammar approaches to NLP, where one and the same grammatical specification could serve both for parsing utterance x into logi- cal form z, but also for generating x from z (Strza- lkowski, 1994). We start by a brief review of this historical non- probabilistic notion of reversibility and point out certain of its weaknesses, in particular regarding robustness; we then give in section 3 a new proba- bilistic definition of reversibility; then, in section 4 we argue for a reversibility model based on modu- lar weighted finite-state transducers. We end with a discussion of recent related work. ∗Work done while at XRCE. 2 Classical reversibility The most direct approaches to NLU attempt to de- sign procedures for semantic parsing that, given an input utterance x, produce a semantic repre- sentation z, by following a number of interme- diate steps where the surface form is gradually transformed into semantic structure. Such “pro- cedural” approaches to semantic parsing are typ- ically very hard or impossible to invert: start- ing from a semantic representation z, there is no simple process that is able to find an x which, when given to the parser, would produce z. For- mally, a Boolean relation r(x, z) can be such that the question ?∃z r(x, z) is decidable for all x’s, while the reciprocal question ?∃x r(x, z) is unde- cidable for some z’s (Dymetman, 1991).1 One of the motivations for the emerging paradigm of uni- fication grammars at the end of the eighties was the clean separation they promised between spec- ifying well-formed linguistic structures, both on the syntactic and semantic levels, through a for- mal description of the relation r(x, z), and pro- ducing efficient implementations of the specifi- cation; in particular, there was much hope that such formalisms would be conductive to effec- tive reversibility (by contrast to variable assign- ment, variable unification is inherently …

Content truncated to 500 words