Bootstrapping Without the Boot

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 395–402, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Bootstrapping Without the Boot∗ Jason Eisner and Damianos Karakos Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {eisner,damianos}@jhu.edu Abstract “Bootstrapping” methods for learning require a small amount of supervision to seed the learning process. We show that it is sometimes possible to eliminate this last bit of supervision, by trying many candidate seeds and selecting the one with the most plausible outcome. We discuss such “strapping” methods in general, and exhibit a particular method for strapping word- sense classifiers for ambiguous words. Our experiments on the Canadian Hansards show that our unsupervised technique is sig- nificantly more effective than picking seeds by hand (Yarowsky, 1995), which in turn is known to rival supervised methods. 1 Introduction Some of NLP’s most interesting problems have to do with unsupervised learning. Human language learners are able to discover word senses, grammatical genders, morpho- logical systems, grammars, discourse registers, and so forth. One would like to build systems that discover the same linguistic patterns in raw text. For that matter, one would also like to discover patterns in bilingual text (for translation), in document collections (for categorization and retrieval), and in other data that fall outside the scope of humans’ language learning. There are relatively few successful methods for fully unsupervised learning from raw text. For example, the EM algorithm (Dempster et al., 1977) extracts the “wrong” patterns or gets stuck in local maxima. One of the most promising avenues in recent years has been the use of “minimally supervised” methods. Such methods are initialized with some sort of “seed” that grows into a full classifier (or generative model). We say that a seed is “fertile” if it grows into a classifier (or model) that performs well on some desired criterion. Ordinarily, it is up to a human to choose a seed that he or she intuitively expects to be fertile. While this may be easy when building a single classifier, it is prohibitive when building many classifiers. For example, we may wish to build • word-sense classifiers for all words of a language (e.g., to get sharper lexical translation probabilities in a ma- chine translation system) • named-entity extractors for many languages • new clusters or classifiers every day (for an evolving document collection) ∗We thank David Yarowsky for advice on the choice of data and for the plant/tank dataset. • new clusters or classifiers every minute (for the docu- ment sets retrieved by ad hoc queries) • many distinct classifiers that correspond to different views of the data1 Even when building a single classifier, a human may not know how to pick a good seed when working with an unfamiliar language or sublanguage, or when trying to induce less intuitive hidden variables, such as grammar rules or fine-grained senses. And there is no reason to expect humans to have good intuitions …

Content truncated to 500 words