UC San Diego

Learning a sequence classifier means learning to predict a sequence of output tags based on a set of input data items. For example, recognizing that a handwritten word is "cat, '' based on three images of handwritten letters and on general knowledge of English letter combinations, is a sequence classification task. This thesis describes a new two-stage approach to learning a sequence classifier that is highly accurate, scalable, and easy to use in data mining applications. The two-stage approach combines support vector machines (SVMs) and conditional random fields (CRFs). It is highly accurate because it benefits from the maximum-margin nature of SVMs and also from the ability of CRFs to model correlations between neighboring output tags. It is scalable because the input to each SVM is a small training set, and the input to the CRF has a small number of features, namely the SVM outputs. It is easy to use because it combines existing published software in a straightforward way. In detailed experiments on the task of recognizing handwritten words, we show that the two-stage approach is more accurate, or faster and more scalable, or both, than the leading other methods for learning sequence classifiers, including max-margin Markov networks (M3Ns) and standard CRFs