Heuristic Search for Non-Bottom-Up Tree Structure Prediction

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 899–908, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Heuristic Search for Non-Bottom-Up Tree Structure Prediction Andrea Gesmundo Department of Computer Science University of Geneva andrea.gesmundo@unige.ch James Henderson Department of Computer Science University of Geneva james.henderson@unige.ch Abstract State of the art Tree Structures Prediction techniques rely on bottom-up decoding. These approaches allow the use of context-free fea- tures and bottom-up features. We discuss the limitations of mainstream techniques in solving common Natural Language Process- ing tasks. Then we devise a new framework that goes beyond Bottom-up Decoding, and that allows a better integration of contextual features. Furthermore we design a system that addresses these issues and we test it on Hierar- chical Machine Translation, a well known tree structure prediction problem. The structure of the proposed system allows the incorpora- tion of non-bottom-up features and relies on a more sophisticated decoding approach. We show that the proposed approach can find bet- ter translations using a smaller portion of the search space. 1 Introduction Tree Structure Prediction (TSP) techniques have become relevant in many Natural Language Pro- cessing (NLP) applications, such as Syntactic Pars- ing, Semantic Role Labeling and Hierarchical Ma- chine Translation (HMT) (Chiang, 2007). HMT approaches have a higher complexity than Phrase- Based Machine Translation techniques, but exploit a more sophisticated reordering model, and can produce translations with higher Syntactic-Semantic quality. TSP requires as inputs: a weighted grammar, G, and a sequence of symbols or a set of sequences en- coded as a Lattice (Chappelier et al., 1999). The input sequence is often a sentence for NLP applica- tions. Tree structures generating the input sequence can be composed using rules, r, from the weighted grammar, G. TSP techniques return as output a tree structure or a set of trees (forest) that generate the input string or lattice. The output forest can be rep- resented compactly as a weighted hypergraph (Klein and Manning, 2001). TSP tasks require finding the tree, t, with the highest score, or the best-k such trees. Mainstream TSP relies on Bottom-up Decod- ing (BD) techniques. With this paper we propose a new framework as a generalization of the CKY-like Bottom-up ap- proach. We also design and test an instantiation of this framework, empirically showing that wider con- textual information leads to higher accuracy for TSP tasks that rely on non-local features, like HMT. 2 Beyond Bottom-up Decoding TSP decoding requires scoring candidate trees, cost(t). Some TSP tasks require only local features. For these cases cost(t) depends only on the local score of the rules that compose t : cost(t) = � ri∈t cost(ri) (1) This is the case for Context Free Grammars. More complex tasks need non-local features. Those fea- tures can be represented by a non-local factor, nonLocal(t), into the overall t score: cost(t) = � ri∈t cost(ri) + nonLocal(t) (2) 899 For example, in HMT the Language Model (LM) is a non-local fundamental feature that approximates the adequacy …

Content truncated to 500 words