Identifying Patterns for Unsupervised Grammar Induction

Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pages 38–45, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Identifying Patterns for Unsupervised Grammar Induction Jes´us Santamar´ıa U. Nacional de Educaci´on a Distancia NLP-IR Group, Madrid, Spain. jsant@lsi.uned.es Lourdes Araujo U. Nacional de Educaci´on a Distancia NLP-IR Group, Madrid, Spain. lurdes@lsi.uned.es Abstract This paper describes a new method for un- supervised grammar induction based on the automatic extraction of certain pat- terns in the texts. Our starting hypoth- esis is that there exist some classes of words that function as separators, mark- ing the beginning or the end of new con- stituents. Among these separators we dis- tinguish those which trigger new levels in the parse tree. If we are able to detect these separators we can follow a very simple procedure to identify the constituents of a sentence by taking the classes of words be- tween separators. This paper is devoted to describe the process that we have followed to automatically identify the set of sepa- rators from a corpus only annotated with Part-of-Speech (POS) tags. The proposed approach has allowed us to improve the re- sults of previous proposals when parsing sentences from the Wall Street Journal cor- pus. 1 Introduction Most works dealing with Grammar Induction (GI) are focused on Supervised Grammar Induction, using a corpus of syntactically annotated sen- tences, or treebank, as a reference to extract the grammar. The existence of a treebank for the lan- guage and for a particular type of texts from which we want to extract the grammar is a great help to GI, even taking into account the theoretical limi- tations of GI, such as the fact that grammars can- not be correctly identified from positive examples alone (Gold, 1967). But the manual annotation of thousands of sentences is a very expensive task and thus there are many languages for which there are not treebanks available. Even in languages for which there is a treebank, it is usually composed of a particular kind of texts (newspaper articles, for example) and may not be appropriate for other kind of texts, such as tales or poetry. These rea- sons have led to the appearance of several works focused on unsupervised GI. Thanks to our knowledge of the language we know that some classes of words are particularly influential to determine the structure of a sentence. For example, let us consider the tree in Figure 1, for which the meaning of the POS tags appears in Table 1. We can observe that the tag MD (Modal) breaks the sentence into two parts. Analogously, in the tree appearing in Figure 2 the POS tag VBZ breaks the sentence. In both cases, we can see that after the breaking tag, a new level appears in the parse tree. A similar effect is observed for other POS tags, such as VB in the tree of Figure 1 and IN in the tree of Figure 2. We call these kind of POS tags separators. …

Content truncated to 500 words