A General-Purpose Algorithm for Constrained Sequential Inference

Proceedings of the 23rd Conference on Computational Natural Language Learning, pages 482–492 Hong Kong, China, November 3-4, 2019. c⃝2019 Association for Computational Linguistics 482 A General-Purpose Algorithm for Constrained Sequential Inference Daniel Deutsch,∗† Shyam Upadhyay,∗‡⋄ and Dan Roth† †Department of Computer and Information Science, University of Pennsylvania ‡Google, New York {ddeutsch,danroth}@seas.upenn.edu shyamupa@google.com Abstract Inference in structured prediction involves finding the best output structure for an input, subject to certain constraints. Many current approaches use sequential inference, which constructs the output in a left-to-right man- ner. However, there is no general framework to specify constraints in these approaches. We present a principled approach for incorporat- ing constraints into sequential inference algo- rithms. Our approach expresses constraints us- ing an automaton, which is traversed in lock- step during inference, guiding the search to valid outputs. We show that automata can express commonly used constraints and are easily incorporated into sequential inference. When it is more natural to represent con- straints as a set of automata, our algorithm uses an active set method for demonstrably fast and efficient inference. We experimentally show the benefits of our algorithm on con- stituency parsing and semantic role labeling. For parsing, unlike unconstrained approaches, our algorithm always generates valid output, incurring only a small drop in performance. For semantic role labeling, imposing con- straints using our algorithm corrects common errors, improving F1 by 1.5 points. These ben- efits increase in low-resource settings. Our ac- tive set method achieves a 5.2x relative speed- up over a naive approach.1 1 Introduction The key challenge in structured prediction prob- lems (like sequence tagging and parsing) is infer- ence (also known as decoding), which involves identifying the best output structure y for an in- put instance x from an exponentially large search 1All code available at https://cogcomp.seas. upenn.edu/page/publication_view/884 ∗Equal contribution, authors listed alphabetically ⋄Work done while at University of Pennsylvania. input: Alice Smith gave a flower to Bob gold tags: B-A0 I-A0 O O B-A1 O B-A2 predicate: gave legal args: A0, A1, A2 (from PropBank) spans: [Alice Smith] gave a [flower] to [Bob] invalid tags: B-A0 I-A0 O O B-A0 O B-A2 reason: duplicate A0 invalid tags: B-A5 I-A5 O O B-A1 O B-A2 reason: illegal arg A5 for predicate “gave” invalid tags: B-A0 O O O B-A1 O B-A2 reason: span [Alice Smith] should have single label Figure 1: An example SRL instance (input, predicate, gold tags) with different invalid tag sequences and the constraints they violate (details in §4.2). space Y (Taskar, 2004; Tsochantaridis et al., 2005). The search is restricted to set of valid y ∈ Yx ⊆ Y for x by imposing constraints during inference. Figure 1 shows examples of constraints used in Semantic Role Labeling (SRL) (Gildea and Jurafsky, 2002). Currently, inference for most structured pre- diction problems is solved sequentially, predict- ing the output in a left-to-right manner (Sutskever et al., 2014; Luong et al., 2016). Such sequential inference approaches enforce constraints in differ- ent ways. For example, a shift-reduce parser con- sults a …

Content truncated to 500 words