Constituent Parsing with Incremental Sigmoid Belief Networks

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 632–639, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Constituent Parsing with Incremental Sigmoid Belief Networks Ivan Titov Department of Computer Science University of Geneva 24, rue G´en´eral Dufour CH-1211 Gen`eve 4, Switzerland ivan.titov@cui.unige.ch James Henderson School of Informatics University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW, United Kingdom james.henderson@ed.ac.uk Abstract We introduce a framework for syntactic parsing with latent variables based on a form of dynamic Sigmoid Belief Networks called Incremental Sigmoid Belief Networks. We demonstrate that a previous feed-forward neural network parsing model can be viewed as a coarse approximation to inference with this class of graphical model. By construct- ing a more accurate but still tractable ap- proximation, we significantly improve pars- ing accuracy, suggesting that ISBNs provide a good idealization for parsing. This gener- ative model of parsing achieves state-of-the- art results on WSJ text and 8% error reduc- tion over the baseline neural network parser. 1 Introduction Latent variable models have recently been of in- creasing interest in Natural Language Processing, and in parsing in particular (e.g. (Koo and Collins, 2005; Matsuzaki et al., 2005; Riezler et al., 2002)). Latent variables provide a principled way to in- clude features in a probability model without need- ing to have data labeled with those features in ad- vance. Instead, a labeling with these features can be induced as part of the training process. The difficulty with latent variable models is that even small numbers of latent variables can lead to com- putationally intractable inference (a.k.a. decoding, parsing). In this paper we propose a solution to this problem based on dynamic Sigmoid Belief Net- works (SBNs) (Neal, 1992). The dynamic SBNs which we peopose, called Incremental Sigmoid Be- lief Networks (ISBNs) have large numbers of latent variables, which makes exact inference intractable. However, they can be approximated sufficiently well to build fast and accurate statistical parsers which in- duce features during training. We use SBNs in a generative history-based model of constituent structure parsing. The probability of an unbounded structure is decomposed into a se- quence of probabilities for individual derivation de- cisions, each decision conditioned on the unbounded history of previous decisions. The most common ap- proach to handling the unbounded nature of the his- tories is to choose a pre-defined set of features which can be unambiguously derived from the history (e.g. (Charniak, 2000; Collins, 1999)). Decision prob- abilities are then assumed to be independent of all information not represented by this finite set of fea- tures. Another previous approach is to use neural networks to compute a compressed representation of the history and condition decisions on this represen- tation (Henderson, 2003; Henderson, 2004). It is possible that an unbounded amount of information is encoded in the compressed representation via its continuous values, but it is not clear whether this is actually happening due to the lack of any principled interpretation for these continuous values. Like the former approach, we …

Content truncated to 500 words