Contrastive Estimation

This is a method proposed by Smith and Eisner 2005:Contrastive Estimation: Training Log-Linear Models on Unlabeled Data.

The proposed approach deals with the estimation of Log-linear Models (e.g. Conditional Random Fields) in an unsupervised fashion. The method focuses on the denominator $\sum _{x\prime ,y\prime }p(x\prime ,y\prime )$ of the log-linear models by exploiting the so called implicit negative evidence in the probability mass.

Motivation

In the Smith and Eisner (2005) paper, the authors have surveyed different estimation techniques (See the Figure above) for probabilistic graphic models. It is clear that for HMMs, people usually optimize the joint likelihood. For log-linear models, various methods were proposed to optimize the conditional probabilities. In addition to this, there are also methods to directly maximize the classification accuracy, the sum of conditional likelihoods, or expected local accuracy. However, none of the above estimation techniques have specifically focused on the implicit negative evidence in the denominator of the standard log-linear model in an unsupervised setting.

How it Works

Unlike the above methods, the contrastive estimation approach optimizes:

$\prod _{i}p(X_{i}=x_{i}|X_{i}\in Neighbor(x_{i}),\theta )$

here, the $Neighbor(x_{i})$ function means a set of implicit negative examples and the $x_{i}$ itself. The idea here is to move the probability mass from the neighborhood of $x_{i}$ to $x_{i}$ itself, so that a good denominator in log-linear models can not only improve the task accuracy, but also reduce the computation of the normalization part of the model.

Problem Formulation and the Detailed Algorithm

Assume we have a log-linear model that is paratermized by $\theta$, the input example is $x$, and the output label is $y$. A standard log-liner model takes the form

$p(x,y|\theta ){\overset {\underset {\mathrm {def} }{}}{=}}{\frac {1}{Z(\theta )}}\exp(\theta \cdot f(x,y))$

here, we can use $u$ to represent the unnormalized score $\exp(\theta \cdot f(x,y))$. $Z(\theta )$ is the partition function, and is hard to compute (much larger space). Then, we can represent the objective function as

$\prod _{i}{\frac {\sum _{(x,y)\in A_{i}}u(x,y|\theta )}{\sum _{(x,y)\in B_{i}}u(x,y|\theta )}}$

where $A_{i}\subset B_{i}$ for each $i$.

In the unsupervised setting, the contrastive estimation method maximizes

$\log \prod _{i}{\frac {\sum _{(y\in Y)}u(x,y|\theta )}{\sum _{(x,y)\in Neighbor(x_{i})\times Y}u(x,y|\theta )}}$

In order to optimize the neighborhood likelihood, the standard numerical optimization approach like L-BFGS can be applied. There are also many other neighborhood methods for sequential data, but it will not be discussed in this method page.

Some Reflections

(1) The hypothesis of this contrastive estimation approach is that each learning instance (the numerator of the log-linear model) is closely related to its neighbors (the denominator of the log-linear model), so that we can make the good instance more likely at the expense of bad instances nearby.

(2) The denominator of log-linear models not only has impacts on the system accuracy, but also influences the overall efficiency performance, as computing the partition function $\mathbf {Z}$ is not desirable.

(3) The proposed Contrastive Estimation method is closely related to the following methods: Expectation Maximization, Posterior Regularization for Expectation Maximization, Featurized HMM and Conditional Random Fields.

Related Papers

• Smith and Eisner 2005:Contrastive Estimation: Training Log-Linear Models on Unlabeled Data (This is the original paper that proposes the contrastive estimation method.)

• Berg-Kirkpatrick et al, ACL 2010: Painless Unsupervised Learning with Features (This paper talks about incorporating log-linear models as local classifiers in HMMs. The estimation method is the forward-backward algorithm.)

• Klein 2002 conditional structure versus conditional estimation in nlp models (This paper discusses various estimation methods for log-linear models, in particular, the sum of conditional likelihoods (SCL) and maximum conditional likelihoods(CL). They observe better performances derived from SCL estimation than CL, even though SCL objective function is non-convex.)

Comments

It would be cool if someone figured out what the relationship is between contrastive estimation (this) vs. constrastive divergence (Hinton). Something like, you only look at little pieces of the partition function... --Brendan 21:15, 13 October 2011 (UTC)