Learning with Cascade for Classification of Non-Convex Manifolds

Images of a visual object, such as human face, reside in a complicated manifold in the high dimensional image space, when the object is subject to variations in pose, illumination, and other factors. Viola and Jones have successfully tackled difficult nonlinear classification problem for face detection using AdaBoost learning. Moreover, their simple-to-complex cascade of classifiers structure makes the learning and classification even more effective. While training with cascade has been used effectively in many works [4, 5, 6, 7, 2, 3, 8, 9, 10], an understanding of the role of the cascade strategy is still lacking. In this paper, we analyze the problem of classifying non-convex manifolds using AdaBoost learning with and without using cascade. We explain that the divide-and-conquer strategy in cascade learning has a great contribution on learning a complex classifier for non-convex manifolds. We prove that AdaBoost learning with cascade is effective when a complete or over-complete set of features (or weak classifiers) is available. Experiments with both synthesized and real data demonstrate that AdaBoost learning with cascade leads to improved convergence and accuracy.