Multi-class Boosting for Early Classification of Sequences

We propose a new boosting algorithm for sequence classification, in particular one that enables early classification of multiple classes. In many practical problems, we would like to classify a sequence into one of K classes as quickly as possible, without waiting for the end of the sequence. Recently, an early classification boosting algorithm was proposed for binary classification that employs a weight propagation technique. In this paper, we extend this model to a multi-class early classification. The derivation is based on the loss function approach, and the developed model is quite simple and effective. We validated the performance through experiments with real-world data, and confirmed the superiority of our approach over the previous method.