Structured Penalties for Log-Linear Language Models

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 233–243, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Structured Penalties for Log-linear Language Models Anil Nelakanti,*‡ C´edric Archambeau,* Julien Mairal,† Francis Bach,‡ Guillaume Bouchard* *Xerox Research Centre Europe, Grenoble, France †INRIA-LEAR Project-Team, Grenoble, France ‡INRIA-SIERRA Project-Team, Paris, France firstname.lastname@xrce.xerox.com firstname.lastname@inria.fr Abstract Language models can be formalized as log- linear regression models where the input fea- tures represent previously observed contexts up to a certain length m. The complexity of existing algorithms to learn the parameters by maximum likelihood scale linearly in nd, where n is the length of the training corpus and d is the number of observed features. We present a model that grows logarithmically in d, making it possible to efficiently leverage longer contexts. We account for the sequen- tial structure of natural language using tree- structured penalized objectives to avoid over- fitting and achieve better generalization. 1 Introduction Language models are crucial parts of advanced nat- ural language processing pipelines, such as speech recognition (Burget et al., 2007), machine trans- lation (Chang and Collins, 2011), or information retrieval (Vargas et al., 2012). When a sequence of symbols is observed, a language model pre- dicts the probability of occurrence of the next sym- bol in the sequence. Models based on so-called back-off smoothing have shown good predictive power (Goodman, 2001). In particular, Kneser-Ney (KN) and its variants (Kneser and Ney, 1995) are still achieving state-of-the-art results for more than a decade after they were originally proposed. Smooth- ing methods are in fact clever heuristics that require tuning parameters in an ad-hoc fashion. Hence, more principled ways of learning language mod- els have been proposed based on maximum en- tropy (Chen and Rosenfeld, 2000) or conditional random fields (Roark et al., 2004), or by adopting a Bayesian approach (Wood et al., 2009). In this paper, we focus on penalized maxi- mum likelihood estimation in log-linear models. In contrast to language models based on unstruc- tured norms such as ℓ2 (quadratic penalties) or ℓ1 (absolute discounting), we use tree-structured norms (Zhao et al., 2009; Jenatton et al., 2011). Structured penalties have been successfully applied to various NLP tasks, including chunking and named entity recognition (Martins et al., 2011), but not lan- guage modelling. Such penalties are particularly well-suited to this problem as they mimic the nested nature of word contexts. However, existing optimiz- ing techniques are not scalable for large contexts m. In this work, we show that structured tree norms provide an efficient framework for language mod- elling. For a special case of these tree norms, we obtain an memory-efficient learning algorithm for log-linear language models. Furthermore, we aslo give the first efficient learning algorithm for struc- tured ℓ∞ tree norms with a complexity nearly lin- ear in the number of training samples. This leads to a memory-efficient and time-efficient learning algo- rithm for generalized linear language models. The paper is organized as follows. The model and other preliminary material is introduced …

Content truncated to 500 words