Unsupervised Induction of Labeled Parse Trees by Clustering with Syntactic Features

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 721–728 Manchester, August 2008 Unsupervised Induction of Labeled Parse Trees by Clustering with Syntactic Features Roi Reichart ICNC Hebrew University of Jerusalem roiri@cs.huji.ac.il Ari Rappoport Institute of computer science Hebrew University of Jerusalem arir@cs.huji.ac.il Abstract We present an algorithm for unsupervised induction of labeled parse trees. The al- gorithm has three stages: bracketing, ini- tial labeling, and label clustering. Brack- eting is done from raw text using an un- supervised incremental parser. Initial la- beling is done using a merging model that aims at minimizing the grammar descrip- tion length. Finally, labels are clustered to a desired number of labels using syn- tactic features extracted from the initially labeled trees. The algorithm obtains 59% labeled f-score on the WSJ10 corpus, as compared to 35% in previous work, and substantial error reduction over a random baseline. We report results for English, German and Chinese corpora, using two label mapping methods and two label set sizes. 1 Introduction Unsupervised learning of grammar from text (‘grammar induction’) is of great theoretical and practical importance. It can shed light on language acquisition by humans and on the general structure of language, and it can potentially assist NLP ap- plications that utilize parser output. The problem has attracted researchers for decades, and interest has greatly increased recently, in part due to the availability of huge corpora, computation power, and new learning algorithms (see Section 2). A fundamental issue in this research direction is the representation of the resulting induced gram- c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. mar. Most recent work (e.g., (Klein and Manning, 2004; Dennis, 2005; Bod, 2006a; Smith and Eis- ner, 2006; Seginer, 2007)) annotates text sentences using a hierarchical bracketing (constituents) or a dependency structure, and thus represents the in- duced grammar through its behavior in a parsing task. Solan et al. (2005) uses a graph representa- tion, while (Nakamura, 2006) simply uses a gram- mar formalism such as PCFG. When the bracket- ing approach is taken, some algorithms label the resulting constituents, while most do not. Each of these approaches can be justified or crit- icized; a detailed discussion of this issue is be- yond the scope of this paper. The algorithm pre- sented here belongs to the first group, annotating given sentences with labeled bracketing structures. The main theoretical justification for this approach is that many linguistic and psycho-linguistic theo- ries posit some kind of a hierarchical labeled con- stituent (or constructional) structure, arguing that it has a measurable psychological (cognitive) reality (e.g., (Goldberg, 2006)). The main practical argu- ments in favor of this approach are that it enables a detailed and large-scale evaluation using anno- tated corpora, as is done in this paper, and that the output format is suitable for many applications. When an algorithm generates labeled structures, the number of labels is an important issue. From a theoretical point of view, the algorithm should …

Content truncated to 500 words