Accelerated Training of Conditional Random Fields with Stochastic Gradient Methods, Vishwanathan et al, ICML 2006

Citation

Vishwanathan et al, 2009. ccelerated Training of Conditional Random Fields with Stochastic Gradient Methods. In Proceedings of the 23rd International Conference on Machine Learning

Online version

Link

Summary

In this paper, the authors apply Stochastic Meta Descent (SMD) to accelerate the training process of a Conditional Random Fields model. By having an ability to adapt step sizes for each parameter, it helps the model converge faster in many cases, especially when exact inference is possible. In cases where exact inference is not possible, SMD seems to have advantages only in the beginning and later BFGS catches up and even does a better job.

Brief description of the method

Stochastic Approximation of Gradients

As in Stochastic Gradient Descent, the log-likelihood is approximated by subsampling small batches of $b\ll m$

${\mathcal {L}}({\boldsymbol {\theta }})=\sum _{t=0}^{{\frac {m}{b}}-1}{{\mathcal {L}}_{b}({\boldsymbol {\theta }},t)}$ where

${\mathcal {L}}_{b}({\boldsymbol {\theta }},t)={\frac {b\vert \vert {\boldsymbol {\theta }}_{t}\vert \vert ^{2}}{2m\sigma ^{2}}}-\sum _{i=1}^{b}{\left[\langle \phi \left(\mathbf {x} _{bt+i},\mathbf {y} _{bt+i}\right),{\boldsymbol {\theta }}_{t}\rangle -z\left({\boldsymbol {\theta }}_{t}\vert \mathbf {x} _{bt+i}\right)\right]}$

For an optimization step, we use ${\mathcal {L}}_{b}\left({\boldsymbol {\theta }},t\right)$ for the gradient

$\mathbf {g} _{t}={\frac {\partial }{\partial {\boldsymbol {\theta }}}}{\mathcal {L}}_{b}\left({\boldsymbol {\theta }},t\right)$

If we just use the stochastic gradient descent, it may not converge at all or may not converge fast enough. By using gain vector adaptation from SMD, the convergence speed can be improved. Each parameter has its own gain:

${\boldsymbol {\theta }}_{t+1}={\boldsymbol {\theta }}_{t}-{\boldsymbol {\eta }}_{t}\cdot \mathbf {g} _{t}$

The gain vector ${\boldsymbol {\eta }}_{t}\in \mathbb {R} _{+}^{n}$ is updated by a multiplicative update with meta-gain $\mu$

${\boldsymbol {\eta }}_{t+1}={\boldsymbol {\eta }}_{t}\cdot \max \left({\frac {1}{2}},1-\mu \mathbf {g} _{t+1}\cdot \mathbf {v} _{t+1}\right)$

The vector $\mathbf {v}$ indicates the long-term 2nd-order dependence of the system parameters with memory (decay factor $\lambda$).

$\mathbf {v} _{t+1}=\lambda \mathbf {v} _{t}-{\boldsymbol {\eta }}_{t}\cdot \left(\mathbf {g} _{t}+\lambda \mathbf {H} _{t}\mathbf {v} _{t}\right)$

The hessian-vector product is calculated efficiently using the following technique:

$d\mathbf {g} \left({\boldsymbol {\theta }}\right)=\mathbf {H} ({\boldsymbol {\theta }})d{\boldsymbol {\theta }}$

$\mathbf {g} \left({\boldsymbol {\theta }}+i\epsilon d{\boldsymbol {\theta }}\right)=\mathbf {g} ({\boldsymbol {\theta }})+O(\epsilon ^{2})+i\epsilon d\mathbf {g} ({\boldsymbol {\theta }})=\mathbf {g} ({\boldsymbol {\theta }})+O(\epsilon ^{2})+i\epsilon \mathbf {H} ({\boldsymbol {\theta }})d{\boldsymbol {\theta }}$

$\mathbf {g} \left({\boldsymbol {\theta }}+i\epsilon \mathbf {v} _{t}\right)=\mathbf {g} ({\boldsymbol {\theta }})+O(\epsilon ^{2})+i\epsilon \mathbf {H} ({\boldsymbol {\theta }})\mathbf {v} _{t}$

Experimental Result

Experiments on 1D chain CRFs

The authors tested convergence rate of a 1D chain CRF model used against CoNLL'00 and GENIA_dataset. The Stochastic Meta Descent (SMD) method described in the previous section is compared with the following methods:

• Simple stochastic gradient descent (SGD) with a fixed gain
• Batch-only limited-memory BFGS algorithm
• Collins' (2002) perceptron (CP), fully online update

As shown in the graphs, SMD converged much faster than any other methods, especially BFGS and CP. It is worthwhile to note that in both datasets, SGD and SMD achieved significant F-score even before it looked at all the examples in the dataset.

Experiments on 2D lattice CRFs

For 2D CRF four optimization methods are compared: SMD, SGD, BFGS and annealed stochastic gradient descent (ASG) where the gain $\eta _{t}=\eta _{0}/t$ decreases as time goes. These methods are used to optimize the conditional likelihood approximated by loopy belief propagation (LBP) or mean field (MF) and the pseudo likelihood (PL). The authors tested 2D CRFs for the binary image denoising task and the classification task recognizing patches including "manmade structures" in the image.

When exact inference is possible (PL), SMD and SGD converged faster. However, in other cases, SMD and SGD have a faster convergence in the beginning and then BFGS catches up and even does better in later passes.

Related papers

• Lafferty_2001_Conditional_Random_Fields
• Sha_2003_shallow_parsing_with_conditional_random_fields