Greedy ensemble learning of structured predictors for sequence tagging

We tackle the sequence tagging problem where the multiple output labels to be predicted are correlated with one another in a complex manner. Due to the ability of capturing statistical dependency in the output variables, the structured models like conditional random fields (CRFs) have received significant attention recently. For computational issues, however, the CRF typically assumes rather simple restricted dependency structures like chains, which can limit its prediction performance considerably when the true data generation processes do not match with the model assumption. In this paper we propose novel algorithms to learn an ensemble of predictor models to boost the overall prediction accuracy. By looking at the frame-wise predictor inferred from a structured CRF model as a weak classifier, the ensemble learning can be formulated within the (functional gradient) boosting framework. Similar to the conventional single-output boosting algorithms, our methods produce the frame-wise importance weights on training data at each stage that gives crucial guidance of which output variables to focus on more (and which less) in learning the next-stage CRF model. The stage-wise learning reduces to the weighted frame-wise conditional likelihood maximization, which can be done as fast as the conventional CRF learning. Our approaches differ from the ordinary single-output boosting in that the base predictors are not learned independently across different frames, yet they are derived from the same structural CRF model, hence tightly clamped with each other to impose overall smoothness and consistency constraints. We demonstrate the improved prediction accuracy on several sequence tagging problems.