Source-linked AI summary
Noise Contrastive Estimation and Negative Sampling for Conditional Models: Consistency and Statistical Efficiency
Zhuang Ma, Michael Collins
TL;DR
Conditional NCE lacks a rigorous theory despite avoiding expensive normalization over large label sets. This paper analyzes classification- and ranking-based estimators, finding that ranking is consistent under weaker assumptions and that both variants become Fisher-efficient as negative samples increase. Experiments compare their effectiveness and trade-offs in synthetic data and language modeling.
Problem
Conditional NCE lacks rigorous theoretical analysis, while maximum-likelihood estimation can require expensive summation over large label sets.
Method
The paper analyzes classification- and ranking-based NCE variants for conditional models and evaluates them on synthetic data and language modeling.
Results
Ranking-based NCE is consistent under weaker assumptions than classification-based NCE, and both variants achieve Fisher efficiency as K →∞ under their respective assumptions.
Takeaways & Limitations
Ranking-based NCE supports consistent estimation when Z(x; θ) varies with x, whereas classification-based consistency requires constant normalization or sufficient score flexibility.
Takeaways & Limitations
Perfect self-normalization can impose |X| constraints on only d + 1 free parameters, with exponentially many constraints in language modeling.
Abstract
from arXiv · showhide
Noise Contrastive Estimation (NCE) is a powerful parameter estimation method for log-linear models, which avoids calculation of the partition function or its derivatives at each training step, a computationally demanding step in many cases. It is closely related to negative sampling methods, now widely used in NLP. This paper considers NCE-based estimation of conditional models. Conditional models are frequently encountered in practice; however there has not been a rigorous theoretical analysis of NCE in this setting, and we will argue there are subtle but important questions when generalizing NCE to the conditional case. In particular, we analyze two variants of NCE for conditional models: one based on a classification objective, the other based on a ranking objective. We show that the ranking-based variant of NCE gives consistent parameter estimates under weaker assumptions than the classification-based method; we analyze the statistical efficiency of the ranking-based and classification-based variants of NCE; finally we describe experiments on synthetic data and language modeling showing the effectiveness and trade-offs of both methods.
1 Introduction
The paper studies NCE-based parameter estimation for conditional models, where large label sets make maximum-likelihood normalization expensive. It compares classification- and ranking-based variants, showing that ranking requires weaker consistency assumptions while both become Fisher-efficient as negative samples increase.
- Motivation: Conditional maximum likelihood can be computationally expensive because each training step may require summing over all labels in a large Y.Negative-sampling objectives avoid this per-example summation by drawing negative examples and optimizing classification or ranking objectives.
- Research gap: NCE has lacked rigorous theoretical analysis for conditional models, whose partition function Z(x; θ) varies by input rather than remaining globally shared.The paper identifies this input-dependent normalization as critical when generalizing NCE from joint to conditional models.
- Consistency: For any K ≥1, classification-based NCE is consistent only when Z(x; θ) is constant in x or the score can represent log Z(x; θ).This condition corresponds to a restricted self-normalization requirement or sufficient score flexibility.
- Consistency: For any K ≥1, ranking-based NCE is consistent when Z(x; θ) may vary with x, without requiring the score to represent log Z(x; θ).Thus ranking-based NCE applies under a weaker assumption than the classification-based variant.
- Efficiency: As K →∞, both NCE variants achieve Fisher efficiency under their respective assumptions.Fisher efficiency means matching the MLE’s asymptotic mean square error.
- Applications and evaluation: The paper unifies related negative-sampling methods and evaluates both NCE variants on synthetic data and language modeling.The experiments assess the effectiveness and trade-offs of classification- and ranking-based approaches.
2 Basic Assumptions
The analysis assumes finite input and label sets, IID training data, a parameterized scoring function, and a positive-support noise distribution. It distinguishes general normalization from perfect self-normalization, whose many constraints can make direct enforcement impractical in language modeling.
- General setup: The setup uses finite X and Y, IID training pairs, a scoring function s(x, y; θ), and a parameter space Θ contained in R^d.The score may be defined by a neural network, and the data arise from an unknown joint distribution with positive marginals.
- General setup: The noise distribution pN(y) must assign positive probability to every label y ∈Y.This ensures every possible label can be sampled as a negative example.
- Assumptions: The paper considers a parameter θ∗ whose score induces the conditional distribution through the input-specific partition function Z(x; θ∗).This is the basic model-correctness assumption for conditional estimation.
- Self-normalization: Perfect self-normalization requires log Z(x; θ∗) ≡γ∗ for every x, imposing |X| constraints on only d + 1 free parameters.When |X| ≫d, this is nontrivial; in language modeling, |X| = |V |^k and the number of constraints grows exponentially.
- Self-normalization: Adding one normalization parameter c_x for every history x can enforce self-normalization but introduces a large number of additional model parameters.This is the direct conditional extension used by Mnih and Teh (2012), with a separate c_x for each history.
3 Two Estimation Algorithms
The paper compares binary-classification and ranking-based NCE algorithms for conditional models, showing that ranking is consistent under weaker assumptions while both approaches become statistically efficient as K grows.
- Algorithms: The two algorithms take training examples, a negative-sampling distribution, K negative examples per example, and a scoring function as inputs.They differ in the objective optimized: binary classification versus ranking the true label above sampled negatives.
- Algorithms: Binary NCE constructs a classifier distinguishing positive from negative examples, whereas ranking NCE orders the true label above K negative examples for each input.The distinction is entirely in the choice between binary and ranking objectives.
- Consistency: For any K ≥1, binary classification NCE is consistent under the stronger assumption that Z(x; θ) is constant with respect to x, but may fail under the weaker assumption.The main theorem states this result for the binary algorithm in Figure 1.
- Consistency: For any K ≥1, ranking NCE is consistent when Z(x; θ) varies with x, without requiring the scoring function to absorb log Z(x; θ).Its consistency argument relates the limiting objective to negative cross-entropy and recovers the conditional distribution.
- Efficiency and applications: Both NCE variants achieve the same statistical efficiency as maximum likelihood as K →∞.The paper also analyzes their application to prior NLP methods and evaluates both variants on synthetic data and language modeling.
- Previous work: Applying binary NCE to language modeling can require a separate normalization parameter for each history, an approach whose practical justification was previously empirical.The discussed language-modeling formulation uses parameters c_x for history-specific normalization terms.
4 Theory
The theory establishes consistency for ranking-based NCE under input-varying partition functions, while binary NCE requires self-normalization; both become Fisher-efficient as the number of negative samples grows.
- Ranking: For fixed K, ranking-based NCE consistently estimates the conditional distribution under continuity, identifiability, and regularity assumptions.The ranking objective's population maximizers correspond to the correct conditional distribution, and identifiability makes the maximizer unique.
- Classification: Binary NCE is strongly consistent for fixed K under the stronger self-normalization assumption, with identifiability and regularity conditions.Self-normalization requires the partition function to be constant with respect to the input.
- Counterexample: Binary classification NCE can be inconsistent when the partition function depends on the input, even though the weaker conditional-model assumption holds.The paper provides a counterexample in which the binary objective does not consistently estimate the conditional distribution.
- Asymptotic Normality and Statistical Efficiency: As n →∞, both ranking and binary NCE estimators are asymptotically normal and √n-consistent under their respective assumptions.The efficiency analysis assumes identifiability and twice-continuous differentiability of the scoring function.
- Asymptotic Normality and Statistical Efficiency: As K →∞, both NCE variants approach Fisher efficiency, matching the MLE's asymptotic mean square error under their respective assumptions.Fisher efficiency is the statistical-optimality benchmark used in the paper's comparison with MLE.
5 Experiments
Experiments show that NCE estimators improve as the number of negative samples increases and can approach MLE performance, while binary NCE is sensitive to self-normalization and model-space size.
- Simulations: NCE estimators are consistent for any fixed K and become comparable to MLE as K increases in the synthetic experiments.The simulations measure KL divergence between estimated and true distributions across sample sizes and negative-sample counts.
- Simulations: Larger sample sizes reduce NCE sensitivity to K, so a very small K can suffice when the sample size is large.This pattern is reported for the synthetic conditional-model experiments.
- Simulations: With self-normalization bias correction, NCE-binary's KL divergence grows as |X| increases, whereas NCE-ranking and MLE are independent of |X|.Without the x-dependent bias term, binary NCE is inconsistent and reports KL divergences of 0.19, 0.21, 0.24, and 0.26 across the tested |X| values.
- Language Modeling: On Penn Treebank, NCE-ranking and NCE-binary improve as K increases and eventually outperform MLE on test-set perplexity.The comparison uses ranking and binary losses across different K values, with and without regularization.
- Language Modeling: Regularization that promotes Z(x; θ) ≈1 significantly improves ranking and MLE, while the unregularized binary approach outperforms both in the tested LSTM model.The authors interpret the unregularized binary result as evidence that the two-layer LSTM can approximately incorporate the input-dependent partition function.
6 Conclusions
The paper compares binary and ranking NCE for conditional models, finding broader consistency for ranking and MLE-level efficiency as negative samples increase.
- Ranking-based NCE is consistent for a broader class of conditional models than binary-based NCE.
- Both NCE variants achieve Fisher efficiency as the number of negative examples increases.
- Both algorithms outperform MLE on the reported language-modeling task.
- Ranking-based NCE outperforms binary-based NCE after introducing a regularizer that encourages self-normalization.
A.1 Similation Results for NCE-binary
This section includes a figure reporting KL divergence between true and estimated distributions, within a setup that assumes finite X and Y and uses separate ranking and binary-loss proofs.
- Figure 3 reports KL divergence between the true distribution and the estimated distribution.
- The setup assumes that X and Y are finite sets.
- The paper presents ranking-loss and binary-classification-loss proofs in separate subsections.
B.1 Proofs for Ranking Loss
The ranking-loss proof develops simplex-based lemmas and uses equalities of ranking probabilities to characterize parameter relationships.
- Under Assumption 2.1, Lemma B.2 establishes a supporting fact used in the ranking-loss proof.
- Equality of ranking probabilities implies that score differences between two parameters depend only on x.
B.1.1 Proof of Theorem 4.1
The proof characterizes ranking-objective maximizers through pointwise optimization and score differences that may depend only on the conditioning variable.
- The proof uses the fact that ranking probabilities sum to one over the candidate index.
- A ranking-objective maximizer must maximize the objective for every x and candidate-label vector.
- The proof shows that equivalent parameterizations differ through a function c(x) independent of y.
- When the relevant set R is a singleton, the identified parameter equals θ∗.
B.1.2 Proof of Theorem 4.2
The proof establishes consistency by combining uniform convergence, continuity, compactness, and large-sample arguments. It also derives identification and asymptotic matrix properties under the stated assumptions.
- Consistency: The proof combines uniform convergence, the strong law of large numbers, and strong consistency to control empirical objectives and estimators.These ingredients are applied over compact parameter sets and with probability one.
- Consistency: The mapping g(θ) from parameters to conditional functions is continuous, and compactness makes it uniformly continuous.This supports transferring parameter proximity into function-space proximity.
- Identification: Under Assumption 4.1, the limiting maximizer set Θ∗ is a singleton, Θ∗ = {θ∗}.The limiting objective therefore identifies a unique target parameter.
- Objective construction: The objective is represented as an average of IID random variables generated from one observed outcome and K noise outcomes.The corresponding expectation is taken under pX,Y(x,y0) together with the noise distribution for the remaining outcomes.
- Matrix properties: The proof establishes nonsingularity and positive definiteness of the relevant matrices for sufficiently large K.In particular, Lemma B.9 provides an integer K0 beyond which the required matrix bound holds.
- Classification formulation: The classification formulation is characterized through the function g(x,y;θ,γ), which combines the model probability with K times the noise probability.The proof uses equivalent exponential and probability representations of this quantity.
B.2.1 Proof of Theorem 4.3
The proof analyzes the classification objective through population maximization, augmented parameters, IID representations, and Fisher-information calculations. It establishes uniqueness under an additional assumption and studies nonsingularity and large-K behavior of the associated matrices.
- Identification: Under Assumption 4.4, the maximizer set Ω∗B is a singleton, so the population objective uniquely identifies (θ∗, γ∗).The proof explicitly concludes that (θ̄, γ̄) = (θ∗, γ∗).
- Objective representation: The classification objective is written as an average of n IID random variables over one data outcome and K independently sampled noise outcomes.The sampling law is pX,Y(x,y0) multiplied by the noise distribution for y1:K.
- Fisher information: Under Assumption 2.2, the Fisher information matrix admits a simplified representation involving pX(x) and exp(s(x,y;θ∗)).This simplification is stated in Lemma B.15.
- Variance analysis: The proof derives covariance and information expressions using permutation symmetry and repeated applications of total variance.Several auxiliary lemmas provide the required symmetric-function and variance identities.
- Matrix properties: Under the theorem assumptions, the matrices W and W̃ are nonsingular, and W̃K remains nonsingular for all sufficiently large K.The argument uses positive definiteness, block-matrix inversion, and perturbation bounds on the smallest singular value.