Journal of Machine Learning Research 7 (2006) 2087-2123
Submitted 2/05; Revised 6/06; Published 10/06
A Hierarchy of Support Vector Machines for Pattern Detection
Machine Intelligence Laboratory
Department of Engineering
University of Cambridge
Cambridge, CB2 1PZ, UK
Center for Imaging Science
302 Clark Hall
Johns Hopkins University
3400 N. Charles Street
Baltimore, MD 21218, USA
Editor: Pietro Perona
We introduce a computational design for pattern detection based on a tree-structured network of
support vector machines (SVMs). An SVM is associated with each cell in a recursive partitioning
of the space of patterns (hypotheses) into increasingly finer subsets. The hierarchy is traversed
coarse-to-fine and each chain of positive responses from the root to a leaf constitutes a detection.
Our objective is to design and build a network which balances overall error and computation.
Initially, SVMs are constructed for each cell with no constraints. This “free network” is then
perturbed, cell by cell, into another network, which is “graded” in two ways: first, the number
of support vectors of each SVM is reduced (by clustering) in order to adjust to a pre-determined,
increasing function of cell depth; second, the decision boundaries are shifted to preserve all positive
responses from the original set of training data. The limits on the numbers of clusters (virtual
support vectors) result from minimizing the mean computational cost of collecting all detections
subject to a bound on the expected number of false positives.
When applied to detecting faces in cluttered scenes, the patterns correspond to poses and the
free network is already faster and more accurate than applying a single pose-specific SVM many
times. The graded network promotes very rapid processing of background regions while maintain-
ing the discriminatory power of the free network.
Keywords: statistical learning, hierarchy of classifiers, coarse-to-fine computation, suppor