Fast Unsupervised Incremental Parsing

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 384–391, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Fast Unsupervised Incremental Parsing Yoav Seginer Institute for Logic, Language and Computation Universiteit van Amsterdam Plantage Muidergracht 24 1018TV Amsterdam The Netherlands yseginer@science.uva.nl Abstract This paper describes an incremental parser and an unsupervised learning algorithm for inducing this parser from plain text. The parser uses a representation for syntactic structure similar to dependency links which is well-suited for incremental parsing. contrast to previous unsupervised parsers,In the parser does not use part-of-speech tags and both learning and parsing are local and fast, requiring no explicit clustering or global optimization. The parser is evalu- ated by converting its output into equivalent bracketing and improves on previously pub- lished results for unsupervised parsing from plain text. 1 Introduction Grammar induction, the learning of the grammar of a language from unannotated example sentences, has long been of interest to linguists because of its relevance to language acquisition by children. In recent years, interest in unsupervised learning of grammar has also increased among computational linguists, as the difficulty and cost of constructing annotated corpora led researchers to look for ways to train parsers on unannotated text. This can ei- ther be semi-supervised parsing, using both anno- tated and unannotated data (McClosky et al., 2006) or unsupervised parsing, training entirely on unan- notated text. The past few years have seen considerable im- provement in the performance of unsupervised parsers (Klein and Manning, 2002; Klein and Man- ning, 2004; Bod, 2006a; Bod, 2006b) and, for the first time, unsupervised parsers have been able to improve on the right-branching heuristic for pars- ing English. All these parsers learn and parse from sequences of part-of-speech tags and select, for each sentence, the binary parse tree which maxi- mizes some objective function. Learning is based on global maximization of this objective function over the whole corpus. In this paper I present an unsupervised parser from plain text which does not use parts-of-speech. Learning is local and parsing is (locally) greedy. As a result, both learning and parsing are fast. The parser is incremental, using a new link representa- tion for syntactic structure. Incremental parsing was chosen because it considerably restricts the search space for both learning and parsing. The represen- tation the parser uses is designed for incremental parsing and allows a prefix of an utterance to be parsed before the full utterance has been read (see section 3). The representation the parser outputs can be converted into bracketing, thus allowing evalua- tion of the parser on standard treebanks. To achieve completely unsupervised parsing, standard unsupervised parsers, working from part- of-speech sequences, need first to induce the parts- of-speech for the plain text they need to parse. There are several algorithms for doing so (Sch¨utze, 1995; Clark, 2000), which cluster words into classes based on the most frequent neighbors of each word. This step becomes superfluous in the algorithm I present here: the algorithm collects lists …

Content truncated to 500 words