An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints

First Joint Conference on Lexical and Computational Semantics (*SEM), pages 209–217, Montr´eal, Canada, June 7-8, 2012. c⃝2012 Association for Computational Linguistics An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints Dipanjan Das∗ Andr´e F. T. Martins∗† Noah A. Smith∗ ∗Language Technologies Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, Lisboa, Portugal {dipanjan,afm,nasmith}@cs.cmu.edu Abstract We present a novel technique for jointly predict- ing semantic arguments for lexical predicates. The task is to find the best matching between seman- tic roles and sentential spans, subject to struc- tural constraints that come from expert linguistic knowledge (e.g., in the FrameNet lexicon). We formulate this task as an integer linear program (ILP); instead of using an off-the-shelf tool to solve the ILP, we employ a dual decomposition algorithm, which we adapt for exact decoding via a branch-and-bound technique. Compared to a baseline that makes local predictions, we achieve better argument identification scores and avoid all structural violations. Runtime is nine times faster than a proprietary ILP solver. 1 Introduction Semantic knowledge is often represented declara- tively in resources created by linguistic experts. In this work, we strive to exploit such knowledge in a principled, unified, and intuitive way. An ex- ample resource where a wide variety of knowledge has been encoded over a long period of time is the FrameNet lexicon (Fillmore et al., 2003),1 which suggests an analysis based on frame semantics (Fill- more, 1982). This resource defines hundreds of semantic frames. Each frame represents a gestalt event or scenario, and is associated with several se- mantic roles, which serve as participants in the event that the frame signifies (see Figure 1 for an exam- ple). Along with storing the above data, FrameNet also provides a hierarchy of relationships between frames, and semantic relationships between pairs of roles. In prior NLP research using FrameNet, these interactions have been largely ignored, though they 1http://framenet.icsi.berkeley.edu have the potential to improve the quality and consis- tency of semantic analysis. In this paper, we present an algorithm that finds the full collection of arguments of a predicate given its semantic frame. Although we work within the conventions of FrameNet, our approach is general- izable to other semantic role labeling (SRL) frame- works. We model this argument identification task as constrained optimization, where the constraints come from expert knowledge encoded in a lexi- con. Following prior work on PropBank-style SRL (Kingsbury and Palmer, 2002) that dealt with simi- lar constrained problems (Punyakanok et al., 2004; Punyakanok et al., 2008, inter alia), we incorporate this declarative knowledge in an integer linear pro- gram (ILP). Because general-purpose ILP solvers are propri- etary and do not fully exploit the structure of the problem, we turn to a class of optimization tech- niques called dual decomposition (Komodakis et al., 2007; Rush et al., 2010; Martins et al., 2011a). We derive a modular, extensible, parallelizable ap- proach in which semantic constraints map not just to declarative components of the algorithm, but also to procedural ones, …

Content truncated to 500 words