Empirical Risk Minimization

This is a method proposed by Bahl et al. 1988 A new algorithm for the estimation of hidden Markov model parameters.

In graphical models, the true distribution is always unknown. Instead of maximizing the likelihood on training data when estimating the model parameter $\theta$ , we can alternatively minimize the Empirical Risk Minimization (ERM) by averaging the loss $l$ . ERM was widely used in Speech Recognition (Bahl et al., 1988) and Machine Translation (Och, 2003). The ERM estimation method has the following advantages:

Maximum likelihood might overfit to the training distribution. ERM can prevent overfitting the training data.
Log likelihood does not equal to the accuracy on the test set, but ERM directly optimizes on the test performance.
Summing up and averaging the local conditional likelihood might be more resilient to errors than calculating the product of conditional likelihoods.

Motivation

A standard training method for probablistic graphical models often involves using Expectation Maximization (EM) for Maximum a Posteriori (MAP) training, approaximate inference and approximate decoding. However, when using the approximate inference with the same equations as in the exact case, it might lead to the divergence of the learner (Kulesza and Pereira, 2008). Secondly, the structure of the model itself might be too simple, and cannot characterize by a model parameter $\theta$ . Moreover, even if the model structure is correct, MAP training using the training data might not give us the correct $\theta$ .

ERM argues that minimizing the risk is the most proper way of training, since the ultimate goal of the task is to directly optimize the performance on true evaluation. In addition, studies (Smith and Eisner, 2006) have shown that maximizing log likelihood using EM does not guarantee consistently high accuracy for evaluations in NLP tasks. As a result, minimizing local empirical risks (the observed errors on the training data) might be an alternative method for training graphical models.

Problem Formulation

Assume we use $\theta$ to represent the model parameter. The task of training is to set the most appropriate $\theta$ that represents the true distribution of the data. For graphical models, given the training data ${(X_{i},Y_{i})}$ pairs, the standard method is to maximize the following log likelihood

\theta ^{*}={\underset {\theta }{\operatorname {argmax} }}LogL(\theta )={\underset {\theta }{\operatorname {argmax} }}\sum _{i}logp_{\theta }(x_{i},y_{i})

where $p_{\theta }(x_{i},y_{i})$ always represent the conditional log-likelihood of $p_{\theta }(y_{i}|x_{i})$ .