Simple Unsupervised Grammar Induction from Raw Text with Cascaded Finite State Models

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1077–1086, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Simple Unsupervised Grammar Induction from Raw Text with Cascaded Finite State Models Elias Ponvert, Jason Baldridge and Katrin Erk Department of Linguistics The University of Texas at Austin Austin, TX 78712 {ponvert,jbaldrid,katrin.erk}@mail.utexas.edu Abstract We consider a new subproblem of unsuper- vised parsing from raw text, unsupervised par- tial parsing—the unsupervised version of text chunking. We show that addressing this task directly, using probabilistic finite-state meth- ods, produces better results than relying on the local predictions of a current best unsu- pervised parser, Seginer’s (2007) CCL. These finite-state models are combined in a cascade to produce more general (full-sentence) con- stituent structures; doing so outperforms CCL by a wide margin in unlabeled PARSEVAL scores for English, German and Chinese. Fi- nally, we address the use of phrasal punctua- tion as a heuristic indicator of phrasal bound- aries, both in our system and in CCL. 1 Introduction Unsupervised grammar induction has been an ac- tive area of research in computational linguistics for over twenty years (Lari and Young, 1990; Pereira and Schabes, 1992; Charniak, 1993). Recent work (Headden III et al., 2009; Cohen and Smith, 2009; H¨anig, 2010; Spitkovsky et al., 2010) has largely built on the dependency model with valence of Klein and Manning (2004), and is characterized by its re- liance on gold-standard part-of-speech (POS) anno- tations: the models are trained on and evaluated us- ing sequences of POS tags rather than raw tokens. This is also true for models which are not successors of Klein and Manning (Bod, 2006; H¨anig, 2010). An exception which learns from raw text and makes no use of POS tags is the common cover links parser (CCL, Seginer 2007). CCL established state- of-the-art results for unsupervised constituency pars- ing from raw text, and it is also incremental and ex- tremely fast for both learning and parsing. Unfortu- nately, CCL is a non-probabilistic algorithm based on a complex set of inter-relating heuristics and a non-standard (though interesting) representation of constituent trees. This makes it hard to extend. Note that although Reichart and Rappoport (2010) improve on Seginer’s results, they do so by select- ing training sets to best match the particular test sentences—CCL itself is used without modification. Ponvert et al. (2010) explore an alternative strat- egy of unsupervised partial parsing: directly pre- dicting low-level constituents based solely on word co-occurrence frequencies. Essentially, this means segmenting raw text into multiword constituents. In that paper, we show—somewhat surprisingly—that CCL’s performance is mostly dependent on its ef- fectiveness at identifying low-level constituents. In fact, simply extracting non-hierarchical multiword constituents from CCL’s output and putting a right- branching structure over them actually works better than CCL’s own higher level predictions. This result suggests that improvements to low-level constituent prediction will ultimately lead to further gains in overall constituent parsing. Here, we present such an improvement by using probabilistic finite-state models for phrasal segmen- tation …

Content truncated to 500 words