Unsupervised induction of stochastic context-free grammars using distributional clustering

Unsupervised Induction of Stochastic Context-Free Grammars using Distributional Clustering Alexander Clark Cognitive and Computing Sciences, University of Sussex, Brighton BN1 9QH, United Kingdom alexc@cogs.susx.ac.uk ISSCO / ETI, University of Geneva, UNI-MAIL, Boulevard du Pont-d’Arve, 40 CH-1211 Gen`eve 4, Switzerland Abstract An algorithm is presented for learning a phrase-structure grammar from tagged text. It clusters sequences of tags to- gether based on local distributional in- formation, and selects clusters that sat- isfy a novel mutual information crite- rion. This criterion is shown to be re- lated to the entropy of a random vari- able associated with the tree structures, and it is demonstrated that it selects lin- guistically plausible constituents. This is incorporated in a Minimum Descrip- tion Length algorithm. The evaluation of unsupervised models is discussed, and results are presented when the al- gorithm has been trained on 12 million words of the British National Corpus. 1 Introduction In this paper I present an algorithm using con- text distribution clustering (CDC) for the un- supervised induction of stochastic context-free grammars (SCFGs) from tagged text. Previ- ous research on completely unsupervised learn- ing has produced poor results, and as a result re- searchers have resorted to mild forms of super- vision. Magerman and Marcus(1990) use a dis- tituent grammar to eliminate undesirable rules. Pereira and Schabes(1992) use partially bracketed corpora and Carroll and Charniak(1992) restrict the set of non-terminals that may appear on the right hand side of rules with a given left hand side. The work of van Zaanen (2000) does not have this problem, and appears to perform well on small data sets, but it is not clear whether it will scale up to large data sets. Adriaans et al. (2000) presents another algorithm but its performance on authentic natural language data appears to be very limited. The work presented here can be seen as one more attempt to implement Zellig Harris’s distri- butional analysis (Harris, 1954), the first such at- tempt being (Lamb, 1961). The rest of the paper is arranged as follows: Section 2 introduces the technique of distribu- tional clustering and presents the results of a pre- liminary experiment. Section 3 discusses the use of a novel mutual information (MI) criterion for filtering out spurious candidate non-terminals. Section 4 shows how this criterion is related to the entropy of a certain random variable, and Sec- tion 5 establishes that it does in fact have the de- sired effect. This is then incorporated in a Min- imum Description Length (MDL) algorithm out- lined in Section 6. I discuss the difficulty of eval- uating this sort of unsupervised algorithm in Sec- tion 7, and present the results of the algorithm on the British National Corpus (BNC). The pa- per then concludes after a discussion of avenues for future research in Section 8. 2 Distributional clustering Distributional clustering has been used in many applications at the word level, but as has been noticed before (Finch et al., 1995), it can also be applied to the induction of grammars. Sets …

Content truncated to 500 words