The Infinite Tree

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 272–279, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics The Infinite Tree Jenny Rose Finkel, Trond Grenager, and Christopher D. Manning Computer Science Department, Stanford University Stanford, CA 94305 {jrfinkel, grenager, manning}@cs.stanford.edu Abstract Historically, unsupervised learning tech- niques have lacked a principled technique for selecting the number of unseen compo- nents. Research into non-parametric priors, such as the Dirichlet process, has enabled in- stead the use of infinite models, in which the number of hidden categories is not fixed, but can grow with the amount of training data. Here we develop the infinite tree, a new infi- nite model capable of representing recursive branching structure over an arbitrarily large set of hidden categories. Specifically, we develop three infinite tree models, each of which enforces different independence as- sumptions, and for each model we define a simple direct assignment sampling inference procedure. We demonstrate the utility of our models by doing unsupervised learning of part-of-speech tags from treebank depen- dency skeleton structure, achieving an accu- racy of 75.34%, and by doing unsupervised splitting of part-of-speech tags, which in- creases the accuracy of a generative depen- dency parser from 85.11% to 87.35%. 1 Introduction Model-based unsupervised learning techniques have historically lacked good methods for choosing the number of unseen components. For example, k- means or EM clustering require advance specifica- tion of the number of mixture components. But the introduction of nonparametric priors such as the Dirichlet process (Ferguson, 1973) enabled develop- ment of infinite mixture models, in which the num- ber of hidden components is not fixed, but emerges naturally from the training data (Antoniak, 1974). Teh et al. (2006) proposed the hierarchical Dirich- let process (HDP) as a way of applying the Dirichlet process (DP) to more complex model forms, so as to allow multiple, group-specific, infinite mixture mod- els to share their mixture components. The closely related infinite hidden Markov model is an HMM in which the transitions are modeled using an HDP, enabling unsupervised learning of sequence models when the number of hidden states is unknown (Beal et al., 2002; Teh et al., 2006). We extend this work by introducing the infinite tree model, which represents recursive branching structure over a potentially infinite set of hidden states. Such models are appropriate for the syntactic dependency structure of natural language. The hid- den states represent word categories (“tags”), the ob- servations they generate represent the words them- selves, and the tree structure represents syntactic de- pendencies between pairs of tags. To validate the model, we test unsupervised learn- ing of tags conditioned on a given dependency tree structure. This is useful, because coarse-grained syntactic categories, such as those used in the Penn Treebank (PTB), make insufficient distinctions to be the basis of accurate syntactic parsing (Charniak, 1996). Hence, state-of-the-art parsers either supple- ment the part-of-speech (POS) tags with the lexical forms themselves (Collins, 2003; Charniak, 2000), manually split the tagset into a finer-grained one …

Content truncated to 500 words