A* CCG Parsing with a Supertag and Dependency Factored Model

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 277–287 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1026 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 277–287 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1026 A* CCG Parsing with a Supertag and Dependency Factored Model Masashi Yoshikawa and Hiroshi Noji and Yuji Matsumoto Graduate School of Information and Science Nara Institute of Science and Technology 8916-5, Takayama, Ikoma, Nara, 630-0192, Japan { masashi.yoshikawa.yh8, noji, matsu }@is.naist.jp Abstract We propose a new A* CCG parsing model in which the probability of a tree is decom- posed into factors of CCG categories and its syntactic dependencies both defined on bi-directional LSTMs. Our factored model allows the precomputation of all probabil- ities and runs very efficiently, while mod- eling sentence structures explicitly via de- pendencies. Our model achieves the state- of-the-art results on English and Japanese CCG parsing.1 1 Introduction Supertagging in lexicalized grammar parsing is known as almost parsing (Bangalore and Joshi, 1999), in that each supertag is syntactically infor- mative and most ambiguities are resolved once a correct supertag is assigned to every word. Re- cently this property is effectively exploited in A* Combinatory Categorial Grammar (CCG; Steed- man (2000)) parsing (Lewis and Steedman, 2014; Lewis et al., 2016), in which the probability of a CCG tree y on a sentence x of length N is the product of the probabilities of supertags (cate- gories) ci (locally factored model): P(y|x) = ∏ i∈[1,N] Ptag(ci|x). (1) By not modeling every combinatory rule in a derivation, this formulation enables us to employ efficient A* search (see Section 2), which finds the most probable supertag sequence that can build a well-formed CCG tree. Although much ambiguity is resolved with this supertagging, some ambiguity still remains. Fig- ure 1 shows an example, where the two CCG 1 Our software and the pretrained models are available at: https://github.com/masashi-y/depccg. (a) a house in Paris in France NP (NP\NP)/NP NP (NP\NP)/NP NP > > NP\NP NP\NP < NP < NP (b) a house in Paris in France NP (NP\NP)/NP NP (NP\NP)/NP NP > NP\NP < NP > NP\NP < NP Figure 1: CCG trees that are equally likely under Eq. 1. Our model resolves this ambiguity by mod- eling the head of every word (dependencies). parses are derived from the same supertags. Lewis et al.’s approach to this problem is resorting to some deterministic rule. For example, Lewis et al. (2016) employ the attach low heuristics, which is motivated by the right-branching tendency of English, and always prioritizes (b) for this type of ambiguity. Though for English it empirically works well, an obvious limitation is that it does not always derive the correct parse; consider a phrase “a house in Paris with a garden”, for which the correct parse has the structure corresponding to (a) instead. In this paper, we provide a way to resolve these remaining …

Content truncated to 500 words