Sequential supervised learning and conditional random fields

Abstract

Supervised learning is concerned with discovering the relationship between example sets of features and their corresponding classes. The traditional supervised learning formulation assumes that all examples are independent from one another. The order of the examples contains no information. Nonetheless, many problems have a sequential nature. Classifiers for these problems must use the sequence of the examples, as well as the regular features, when generating a prediction. Sequential supervised learning (SSL) algorithms are able to capture both types of information. A variety of sequential supervised learning methods have already exist. The conditional random field is a particularly robust SSL algorithm that overcomes some limitations of other SSL methods, such as hidden Markov models and recurrent sliding windows. However, the original implementation of the conditional random field explicitly represents a weight for every feature combination. For sequential problems using a window of input features, this means a combinatorial explosion. A better way to represent the conditional random field, using regression trees, is introduced. The regression tree conditional random field provides an efficient method for learning feature weights and supports the selection and combination of features. The ability to select feature combinations benefits classification performance.