Approximate constraint generation for efficient structured boosting

Abstract

We propose efficient training methods (SBoost) for totally-corrective boosting based structured learning. The optimization of boosting method for structured learning is more challenging than the structured support vector machine. Basically, we propose smooth and convex formulation for boosting based structured learning, and develop approximate constraint generation together with column generation to solve the optimization with large number of constraints and variables. Because of the convexity and smoothness, the optimization in each generation iteration can be solved efficiently. We demonstrate some structured learning applications in computer vision using SBoost, including invariance learning for digit recognition, object detection and hierarchical image classification.