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

Jacob Andreas, Dan KleinNAACL 2015 · OpenReview

TL;DR

This paper investigates the theoretical underpinnings of "self-normalizing" log-linear models, which aim to make their output scores approximate true probabilities without explicit normalization. The authors provide theoretical guarantees for when this self-normalization works and introduce a novel training objective that significantly speeds up training while maintaining model quality.

What Problem Does This Paper Address?

Log-linear models are powerful tools in natural language processing (NLP) tasks like machine translation and speech recognition. However, a major computational bottleneck is the need to calculate a "normalizer" (or partition function) for each input context to ensure the model outputs a valid probability distribution. This calculation can be prohibitively expensive, especially for large vocabularies. "Self-normalizing" techniques aim to circumvent this by training models such that their unnormalized scores are already close to summing to one, effectively acting as probabilities. While these techniques show practical promise, their theoretical foundations and the conditions under which they succeed have been largely unexplored. This paper seeks to fill that gap by providing a theoretical understanding of self-normalization and proposing a more efficient training method.

Methods

The authors delve into the theoretical properties of self-normalizing log-linear models. They first characterize the types of data distributions (or "context distributions") for which exact or approximate self-normalization is possible. This involves analyzing the conditions under which a weight vector $\theta$ can make the partition function $Z(x; \theta)$ approximately equal to 1 for a given context $x$. They then prove generalization bounds for training procedures that minimize the variance of the empirical normalizer.

Motivated by these theoretical insights, they propose a novel training objective. This objective combines a standard likelihood term with a penalty on the normalizer's deviation from 1. Crucially, this penalty is applied only to a subset of training examples, controlled by a parameter $\gamma$. This allows the model to avoid computing the full normalizer for most examples, significantly reducing training time, while still retaining fine-grained control over the trade-off between model likelihood and normalization quality, similar to explicit penalization methods.

Datasets

The paper uses a small prefix of the Europarl corpus for language modeling experiments. This corpus is approximately 10M words. The authors note that the translation results from this limited data are not state-of-the-art. No new benchmarks are introduced.

Key Insights and Ideas

  • Geometric Interpretation of Normalizability: The set of contexts $x$ for which a log-linear model is exactly normalizable for a given $\theta$ forms a smooth surface, specifically the boundary of a convex region. This provides a concrete geometric understanding of when self-normalization is achievable.
  • "Good Enough" Normalization: Real-world data is unlikely to be perfectly normalizable. The paper introduces the concept of a context distribution being "D-close" to a normalizable set, showing that distributions close to exactly normalizable ones are themselves approximately normalizable.
  • Training Efficiency via Selective Normalization: The core idea behind their novel training objective is that you don't need to normalize every training example to achieve good self-normalizing behavior. By selectively penalizing the normalizer on a fraction of examples, significant speedups can be achieved without sacrificing model quality.
  • Tunable Trade-off: The proposed objective offers a tunable parameter ($\alpha$) to control the strength of the normalization penalty, allowing practitioners to balance the desire for normalization with the need for good likelihood performance.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees on when self-normalization is possible and offers generalization bounds for training procedures that minimize normalizer variance.
  • Significant Speedup: Their novel training objective, by normalizing only a fraction ($\gamma=0.1$) of training examples, achieved an order-of-magnitude reduction in training time compared to normalizing all examples ($\gamma=1$).
  • Preserved Model Quality: Despite the speedup and reduced normalization effort, the model quality, as measured by BLEU score on a downstream machine translation task, was largely preserved. For instance, with $\gamma=0.1$ and $\alpha=0.1$, they achieved a BLEU score of 20.0, very close to the $\gamma=1$ baseline of 20.0, while significantly reducing normalization risk.
  • Importance of Tunability: Experiments showed that both too weak ($\alpha$ too small) and too strong ($\alpha$ too large) normalization penalties can degrade performance, highlighting the importance of a tunable parameter for balancing objectives.

Limitations and Future Work

  • Limited Experimental Scope: The experiments were conducted on a small prefix of the Europarl corpus, and the resulting translation performance was not state-of-the-art. The authors suggest that their techniques are applicable to larger datasets and more complex models.
  • Focus on Normalization Error: The theoretical results primarily focus on normalization error and do not directly address the quality of the self-normalized model in terms of likelihood or downstream task performance. While their experiments suggest quality is preserved, a deeper theoretical treatment of this aspect is deferred.
  • Neural Networks: While the paper briefly touches upon the applicability of their techniques to neural networks, the core analysis and experiments are on log-linear models. Further work could explore the direct integration and theoretical analysis of self-normalization within deep neural architectures.

Summary updated

Abstract

Several techniques have recently been proposed for training “self-normalized” discriminative models. These attempt to find parameter settings for which unnormalized model scores approximate the true label probability. However, the theoretical properties of such techniques (and of self-normalization generally) have not been investigated. This paper examines the conditions under which we can expect self-normalization to work. We characterize a general class of distributions that admit self-normalization, and prove generalization bounds for procedures that minimize empirical normalizer variance. Motivated by these results, we describe a novel variant of an established 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.
BibTeX
@inproceedings{andreas2015when,
  author = {Jacob Andreas and Dan Klein},
  title = {{When and why are log-linear models self-normalizing?}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  url = {https://openreview.net/forum?id=ry-2dXZ_-B},
}
Figure