Dietterich 2008 gradient tree boosting for training conditional random fields

Citation

Gradient Tree Boosting for Training Conditional Random Fields. By T. G Dietterich, G. Hao, A. Ashenfelter. In Journal of Machine Learning Research, vol. 9 ({{{issue}}}), 2008.

Online Version

This Paper is available online [1].

Summary

The paper addresses the problem of combinatorial explosion of parameters of CRFs when new features are introduced. It represents the potential functions as sums of regression trees. The authors claim that adding a regression tree is a big step in the feature space and hence it reduces the number of iterations. This leads to a significant performance improvement.

Method

In a traditional gradient descent method, a function $\Psi$ is represented by linear function of parameters. Thus, the parameter values after $m$ steps would be

$\Theta _{m}=\Theta _{0}+\delta _{1}+\cdots +\delta _{m}$.

Instead of parameterizing, functional gradient ascent assumes that $\Psi$ is a weighted sum of functions;

$\Psi _{m}=\Psi _{0}+\Delta _{1}+\cdots +\Delta _{m}$, where

$\Delta _{m}=E_{{\vec {x}},y}\left[\nabla _{\Psi }\log P(y|{\vec {x}};\Psi )\vert _{\Psi _{m-1}}\right]$

Since the joint distribution ${\vec {x}},y$ is not known, $\Delta _{m}$ is empirically calculated from the training samples (which are assumed to be from the joint distribution. Now, a regression tree $h_{m}$ is trained to minimize the squared error loss. Overfitting is prevented by using a shrinkage parameter instead of bounding the number of leaf nodes of the tree.

The authors define a "desirability" quotient for a particular label $y_{t}$ as

$F^{y_{t}}(y_{t-1},X)=\Psi (y_{t},X)+\Psi (y_{t},y_{t-1},X)$

given $y_{t-1}$ and $X$. The authors then calculate the functional gradient of $F^{y_{t}}(y_{t-1},X)$.

Evaluation

The authors evaluated the performance of their trained CRF's with Mallet.

Datasets

• Protein Secondary Structure Benchmark (Qian and Sejnowski, 1988)

• NETtalk Data Set

• Hyphenation Data Set

• Usenet FAQs Data Sets.

Summarized Results

The prediction accuracy of the current method and Mallet is not statistically significant for all datasets other than FAQ ai-general data set (current method is more accurate than Mallet) and NETtalk data set (Mallet has better accuracy).

In terms of speed; the authors compared how CPU times scale over the number of features and sequence length. The method performs poorly for large sequences; equally good for small sequences and small features, and outperforms for large number of features.