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

From Cohen Courses

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

You do not have permission to edit this page, for the following reason:

---

You can view and copy the source of this page.

== 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 == [http://www.cs.ubc.ca/~murphyk/Papers/icml06_camera.pdf Link] == Summary == In this [[Category::paper]], the authors apply [[UsesMethod::Stochastic Meta Descent]] (SMD) to accelerate the training process of a [[UsesMethod::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. == Brief description of the method == === Stochastic Approximation of Gradients === As in [[UsesMethod::Stochastic Gradient Descent]], the log-likelihood is approximated by subsampling small batches of <math>b \ll m</math> <math> \mathcal{L}(\boldsymbol{\theta}) = \sum_{t=0}^{\frac{m}{b}-1} {\mathcal{L}_{b}(\boldsymbol{\theta},t)} </math> where <math> \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]} </math> For an optimization step, we use <math>\mathcal{L}_{b}\left(\boldsymbol{\theta},t\right)</math> for the gradient <math> \mathbf{g}_{t} = \frac{\partial}{\partial\boldsymbol\theta}\mathcal{L}_{b}\left(\boldsymbol{\theta},t\right) </math> 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: <math> \boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_{t} - \boldsymbol\eta_{t}\cdot\mathbf{g}_{t} </math> The gain vector <math>\boldsymbol{\eta}_{t}\in\mathbb{R}_{+}^{n}</math> is updated by a multiplicative update with meta-gain <math>\mu</math> <math> \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) </math> The vector <math>\mathbf{v}</math> indicates the long-term 2nd-order dependence of the system parameters with memory (decay factor <math>\lambda</math>). <math> \mathbf{v}_{t+1} = \lambda\mathbf{v}_{t} - \boldsymbol{\eta}_{t}\cdot\left(\mathbf{g}_{t}+\lambda\mathbf{H}_{t}\mathbf{v}_{t}\right) </math> The hessian-vector product is calculated efficiently using the following technique: <math> d\mathbf{g}\left(\boldsymbol\theta\right)=\mathbf{H}(\boldsymbol\theta)d\boldsymbol\theta </math> <math> \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 </math> <math> \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} </math> == Experimental Result == === Experiments on 1D chain CRFs === The authors tested convergence rate of a 1D chain CRF model used against [[UsesDataset::CoNLL'00]] and [[UsesDataset::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. [[File:Vishwanathan et al ICML2006 1.png|800px]] === 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 <math>\eta_{t}=\eta_{0}/t</math> 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. [[File:Vishwanathan et al ICML2006 2.png|400px]][[File:Vishwanathan et al ICML2006 3.png|400px]] 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 == * [[RelatedPaper::Lafferty_2001_Conditional_Random_Fields]] * [[RelatedPaper::Sha_2003_shallow_parsing_with_conditional_random_fields]]

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