When and why are log-linear models self-normalizing?

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 244–249, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics When and why are log-linear models self-normalizing? Jacob Andreas and Dan Klein Computer Science Division University of California, Berkeley {jda,klein}@cs.berkeley.edu Abstract Several techniques have recently been pro- posed for training “self-normalized” discrimi- native models. These attempt to find parameter settings for which unnormalized model scores approximate the true label probability. How- ever, the theoretical properties of such tech- niques (and of self-normalization generally) have not been investigated. This paper exam- ines the conditions under which we can ex- pect self-normalization to work. We character- ize a general class of distributions that admit self-normalization, and prove generalization bounds for procedures that minimize empiri- cal normalizer variance. Motivated by these results, we describe a novel variant of an estab- lished procedure for training self-normalized models. The new procedure avoids computing normalizers for most training examples, and decreases training time by as much as factor of ten while preserving model quality. 1 Introduction This paper investigates the theoretical properties of log-linear models trained to make their unnormalized scores approximately sum to one. Recent years have seen a resurgence of interest in log-linear approaches to language modeling. This includes both conventional log-linear models (Rosen- feld, 1994; Biadsy et al., 2014) and neural networks with a log-linear output layer (Bengio et al., 2006). On a variety of tasks, these LMs have produced sub- stantial gains over conventional generative models based on counting n-grams. Successes include ma- chine translation (Devlin et al., 2014) and speech recognition (Graves et al., 2013). However, log-linear LMs come at a significant cost for computational ef- ficiency. In order to output a well-formed probability distribution over words, such models must typically calculate a normalizing constant whose computa- tional cost grows linearly in the size of the vocab- ulary. Fortunately, many applications of LMs remain well-behaved even if LM scores do not actually cor- respond to probability distributions. For example, if a machine translation decoder uses output from a pre-trained LM as a feature inside a larger model, it suffices to have all output scores on approximately the same scale, even if these do not sum to one for every LM context. There has thus been considerable research interest around training procedures capa- ble of ensuring that unnormalized outputs for every context are “close” to a probability distribution. We are aware of at least two such techniques: noise- contrastive estimation (NCE) (Vaswani et al., 2013; Gutmann and Hyv¨arinen, 2010) and explicit penal- ization of the log-normalizer (Devlin et al., 2014). Both approaches have advantages and disadvantages. NCE allows fast training by dispensing with the need to ever compute a normalizer. Explicit penalization requires full normalizers to be computed during train- ing but parameterizes the relative importance of the likelihood and the “sum-to-one” constraint, allowing system designers to tune the objective for optimal performance. While both NCE and explicit penalization are ob- served …

Content truncated to 500 words