The Inside-Outside Recursive Neural Network model for Dependency Parsing

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 729–739, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics The Inside-Outside Recursive Neural Network model for Dependency Parsing Phong Le and Willem Zuidema Institute for Logic, Language, and Computation University of Amsterdam, the Netherlands {p.le,zuidema}@uva.nl Abstract We propose the first implementation of an infinite-order generative dependency model. The model is based on a new recursive neural network architecture, the Inside-Outside Recursive Neural Network. This architecture allows information to flow not only bottom-up, as in traditional recursive neural networks, but also top- down. This is achieved by computing content as well as context representations for any constituent, and letting these rep- resentations interact. Experimental re- sults on the English section of the Uni- versal Dependency Treebank show that the infinite-order model achieves a per- plexity seven times lower than the tradi- tional third-order model using counting, and tends to choose more accurate parses in k-best lists. In addition, reranking with this model achieves state-of-the-art unla- belled attachment scores and unlabelled exact match scores. 1 Introduction Estimating probability distributions is the core is- sue in modern, data-driven natural language pro- cessing methods. Because of the traditional defi- nition of discrete probability Pr(A) ≡ the number of times A occurs the size of event space counting has become a standard method to tackle the problem. When data are sparse, smoothing techniques are needed to adjust counts for non- observed or rare events. However, successful use of those techniques has turned out to be an art. For instance, much skill and expertise is required to create reasonable reduction lists for back-off, and to avoid impractically large count tables, which store events and their counts. An alternative to counting for estimating prob- ability distributions is to use neural networks. Thanks to recent advances in deep learning, this approach has recently started to look very promis- ing again, with state-of-the-art results in senti- ment analysis (Socher et al., 2013), language mod- elling (Mikolov et al., 2010), and other tasks. The Mikolov et al. (2010) work, in particular, demon- strates the advantage of neural-network-based ap- proaches over counting-based approaches in lan- guage modelling: it shows that recurrent neu- ral networks are capable of capturing long histo- ries efficiently and surpass standard n-gram tech- niques (e.g., Kneser-Ney smoothed 5-gram). In this paper, keeping in mind the success of these models, we compare the two approaches. Complementing recent work that focused on such a comparison for the case of finding appropriate word vectors (Baroni et al., 2014), we focus here on models that involve more complex, hierarchical structures. Starting with existing generative mod- els that use counting to estimate probability distri- butions over constituency and dependency parses (e.g., Eisner (1996b), Collins (2003)), we develop an alternative based on recursive neural networks. This is a non-trivial task because, to our knowl- edge, no existing neural network architecture can be used in this way. For instance, classic recur- rent neural networks (Elman, 1990) unfold to …

Content truncated to 500 words