Annealing Techniques For Unsupervised Statistical Language Learning

Annealing Techniques for Unsupervised Statistical Language Learning Noah A. Smith and Jason Eisner Department of Computer Science / Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {nasmith,jason}@cs.jhu.edu Abstract Exploiting unannotated natural language data is hard largely because unsupervised parameter estimation is hard. We describe deterministic annealing (Rose et al., 1990) as an appealing alternative to the Expectation- Maximization algorithm (Dempster et al., 1977). Seek- ing to avoid search error, DA begins by globally maxi- mizing an easy concave function and maintains a local maximum as it gradually morphs the function into the desired non-concave likelihood function. Applying DA to parsing and tagging models is shown to be straight- forward; significant improvements over EM are shown on a part-of-speech tagging task. We describe a vari- ant, skewed DA, which can incorporate a good initializer when it is available, and show significant improvements over EM on a grammar induction task. 1 Introduction Unlabeled data remains a tantalizing potential re- source for NLP researchers. Some tasks can thrive on a nearly pure diet of unlabeled data (Yarowsky, 1995; Collins and Singer, 1999; Cucerzan and Yarowsky, 2003). But for other tasks, such as ma- chine translation (Brown et al., 1990), the chief merit of unlabeled data is simply that nothing else is available; unsupervised parameter estimation is notorious for achieving mediocre results. The standard starting point is the Expectation- Maximization (EM) algorithm (Dempster et al., 1977). EM iteratively adjusts a model’s parame- ters from an initial guess until it converges to a lo- cal maximum. Unfortunately, likelihood functions in practice are riddled with suboptimal local max- ima (e.g., Charniak, 1993, ch. 7). Moreover, max- imizing likelihood is not equivalent to maximizing task-defined accuracy (e.g., Merialdo, 1994). Here we focus on the search error problem. As- sume that one has a model for which improving likelihood really will improve accuracy (e.g., at pre- dicting hidden part-of-speech (POS) tags or parse trees). Hence, we seek methods that tend to locate mountaintops rather than hilltops of the likelihood function. Alternatively, we might want methods that find hilltops with other desirable properties.1 1Wang et al. (2003) suggest that one should seek a high- In §2 we review deterministic annealing (DA) and show how it generalizes the EM algorithm. §3 shows how DA can be used for parameter estimation for models of language structure that use dynamic programming to compute posteriors over hidden structure, such as hidden Markov models (HMMs) and stochastic context-free grammars (SCFGs). In §4 we apply DA to the problem of learning a tri- gram POS tagger without labeled data. We then de- scribe how one of the received strengths of DA— its robustness to the initializing model parameters— can be a shortcoming in situations where the ini- tial parameters carry a helpful bias. We present a solution to this problem in the form of a new algorithm, skewed deterministic annealing (SDA; §5). Finally we apply SDA to a grammar induc- tion model and demonstrate significantly improved performance over EM (§6). …

Content truncated to 500 words