OREGON STATE UNIVERSITY

You are here

Gradient Tree Boosting for Training Conditional Random Fields

TitleGradient Tree Boosting for Training Conditional Random Fields
Publication TypeJournal Article
Year of Publication2008
AuthorsDietterich, T. G., G. Hao, and A. Ashenfelter
JournalJournal of Machine Learning Research
Volume9
Pagination2113-2139
Date Published10/2008
Keywordsconditional random fields, functional gradient, gradient tree boosting, missing values, sequential supervised learning
Abstract

Conditional random fields (CRFs) provide a flexible and powerful model for sequence labeling problems. However, existing learning algorithms are slow, particularly in problems with large numbers of potential input features and feature combinations. This paper describes a new algorithm for training CRFs via gradient tree boosting. In tree boosting, the CRF potential functions are represented as weighted sums of regression trees, which provide compact representations of feature interactions. So the algorithm does not explicitly consider the potentially large parameter space. As a result, gradient tree boosting scales linearly in the order of the Markov model and in the order of the feature interactions, rather than exponentially as in previous algorithms based on iterative scaling and gradient descent. Gradient tree boosting also makes it possible to use instance weighting (as in C4.5) and surrogate splitting (as in CART) to handle missing values. Experimental studies of the effectiveness of these two methods (as well as standard imputation and indicator feature methods) show that instance weighting is the best method in most cases when feature values are missing at random.