Multi-Class Semi-Supervised and Online Boosting

Inffeldgasse 16a/2nd floor, A-8010 Graz, Austria

In this thesis, we develop multi-class boosting algorithms for supervised, semi-supervised, and online learning problems. First, we present our supervised algorithm which is based on maximizing the true multi-class classification margin. This algorithm is versatile enough to use many different loss functions. As a result, the proposed multi-class boosting algorithm can be used in many different applications and circumstances where the desirable behavior can be tuned by choosing the proper loss function.

Based on the concept of learning from prior knowledge, we build a multi-class semi-supervised boosting algorithm which is able to use unlabeled data to improve its performance. We show that our algorithm can be applied to large-scale problems with many unlabeled samples. This algorithm is flexible enough to operate on a wide-range of semi-supervised learning problems by incorporating both the cluster and manifold assumptions. We take the proposed semi-supervised boosting algorithm further and show that it can be used for learning from multiple views of the data. In this approach, different views combine their beliefs regarding the output label of an unlabeled sample into a set of prior knowledge and train each other using the same principles introduced for the semi-supervised boosting model.

We proceed to develop an online multi-class learning algorithm which uses online convex programming tools to solve linear programs in the context of the boosting. The resulting algorithm can use any other online learner as its base functions and compared to other online learning algorithms, its performance is considerably higher.

We apply the proposed methods to a wide range of applications, such as pattern recognition, object category recognition, and visual object tracking. Our extensive set of evaluations demonstrates the competitiveness of the proposed algorithms with respect to the state-of-the-art methods.

PDF