Unsupervised Grammar Induction by Distribution and Attachment

Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL-X), pages 117–124, New York City, June 2006. c⃝2006 Association for Computational Linguistics Unsupervised Grammar Induction by Distribution and Attachment David J. Brooks School of Computer Science University of Birmingham Birmingham, B15 2TT, UK d.j.brooks@cs.bham.ac.uk Abstract Distributional approaches to grammar in- duction are typically inefficient, enumer- ating large numbers of candidate con- stituents. In this paper, we describe a simplified model of distributional analy- sis which uses heuristics to reduce the number of candidate constituents under consideration. We apply this model to a large corpus of over 400000 words of written English, and evaluate the results using EVALB. We show that the perfor- mance of this approach is limited, provid- ing a detailed analysis of learned structure and a comparison with actual constituent- context distributions. This motivates a more structured approach, using a process of attachment to form constituents from their distributional components. Our find- ings suggest that distributional methods do not generalize enough to learn syntax effectively from raw text, but that attach- ment methods are more successful. 1 Introduction Distributional approaches to grammar induction ex- ploit the principle of substitutability: constituents of the same type may be exchanged with one another without affecting the syntax of the surrounding con- text. Reversing this notion, if we can identify “sur- rounding context” by observation, we can hypothe- size that word sequences occurring in that context will be constituents of the same type. Thus, distri- butional methods can be used to segment text into constituents and classify the results. This work fo- cuses on distributional learning from raw text. Various models of distributional analysis have been used to induce syntactic structure, but most use probabilistic metrics to decide between candi- date constituents. We show that the efficiency of these systems can be improved by exploiting some properties of probable constituents, but also that this reliance on probability is problematic for learning from text. As a consequence, we propose an exten- sion to strict distributional learning that incorporates more information about constituent boundaries. The remainder of this paper describes our expe- riences with a heuristic system for grammar induc- tion. We begin with a discussion of previous dis- tributional approaches to grammar induction in Sec- tion 2 and describe their implications in Section 3. We then introduce a heuristic distributional system in Section 4, which we analyze empirically against a treebank. Poor system performance leads us to ex- amine actual constituent-context distributions (Sec- tion 5), the implications of which motivate a more structured extension to our learning system, which we describe and analyze in Section 6. 2 Previous approaches Distributional methods analyze text by alignment, aiming to find equivalence classes covering substi- tutable units. We align common portions of texts termed contexts, leaving distinct contiguous word- sequences, termed expressions. An expression and its context form an alignment pattern, which is de- 117 fined as: Cleft | Expression | Cright (AP1) From this alignment pattern, we can extract context- free grammar rules: NT …

Content truncated to 500 words