Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1983–1995, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Breaking Out of Local Optima with Count Transforms and Model Recombination: A Study in Grammar Induction Valentin I. Spitkovsky valentin@cs.stanford.edu Hiyan Alshawi hiyan@google.com Daniel Jurafsky jurafsky@stanford.edu Abstract Many statistical learning problems in NLP call for local model search methods. But accu- racy tends to suffer with current techniques, which often explore either too narrowly or too broadly: hill-climbers can get stuck in local optima, whereas samplers may be inefficient. We propose to arrange individual local opti- mizers into organized networks. Our building blocks are operators of two types: (i) trans- form, which suggests new places to search, via non-random restarts from already-found local optima; and (ii) join, which merges candidate solutions to find better optima. Experiments on grammar induction show that pursuing dif- ferent transforms (e.g., discarding parts of a learned model or ignoring portions of train- ing data) results in improvements. Groups of locally-optimal solutions can be further per- turbed jointly, by constructing mixtures. Us- ing these tools, we designed several modu- lar dependency grammar induction networks of increasing complexity. Our complete sys- tem achieves 48.6% accuracy (directed depen- dency macro-average over all 19 languages in the 2006/7 CoNLL data) — more than 5% higher than the previous state-of-the-art. 1 Introduction Statistical methods for grammar induction often boil down to solving non-convex optimization problems. Early work attempted to locally maximize the likeli- hood of a corpus, using EM to estimate probabilities of dependency arcs between word bigrams (Paskin 2001a; 2001b). That parsing model has since been extended to make unsupervised learning more feasi- ble (Klein and Manning, 2004; Headden et al., 2009; Spitkovsky et al., 2012b). But even the latest tech- niques can be quite error-prone and sensitive to ini- tialization, because of approximate, local search. In theory, global optima can be found by enumer- ating all parse forests that derive a corpus, though this is usually prohibitively expensive in practice. A preferable brute force approach is sampling, as in Markov-chain Monte Carlo (MCMC) and random restarts (Hu et al., 1994), which hit exact solutions eventually. Restarts can be giant steps in a parameter space that undo all previous work. At the other ex- treme, MCMC may cling to a neighborhood, reject- ing most proposed moves that would escape a local attractor. Sampling methods thus take unbounded time to solve a problem (and can’t certify optimal- ity) but are useful for finding approximate solutions to grammar induction (Cohn et al., 2011; Mareˇcek and ˇZabokrtsk´y, 2011; Naseem and Barzilay, 2011). We propose an alternative (deterministic) search heuristic that combines local optimization via EM with non-random restarts. Its new starting places are informed by previously found solutions, unlike con- ventional restarts, but may not resemble their prede- cessors, unlike typical MCMC moves. We show that one good way to construct such steps in a parame- ter space is by forgetting some aspects of a learned model. …

Content truncated to 500 words