View source for 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 ==

[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. 


== 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>

== Experimental Result ==

The authors tested this method on [[UsesDataset::MUC]]-7 and the oncology part of [[UsesDataset::PennBioIE]] corpus. The base learner used for the experiment is a linear-chain [[UsesMethod::Conditional Random Fields]]. Features used are orthographical features (regexp patterns), lexical and morphological features (prefix, suffix, lemmatized tokens), and contextual features (features of neighbor tokens). In terms of the number of tokens that had to be labled to reach the maximal F-score, SeSAL could save about 60% over FuSAL, and 80% over random sampling. Having high confidence was also important because it could save the model from making errors in the early stages.

== Related papers ==

* [[RelatedPaper::Muslea, Minton and Knoblock, ICML 2002]]
* [[RelatedPaper::McCallum and Ngiam, ICML 98]]


== Comment ==

If you're further interested in active learning for NLP, you might want to see Burr Settles' review of active learning: http://active-learning.net/  --[[User:Brendan|Brendan]] 22:51, 13 October 2011 (UTC)