Hypercuts: Boosted Dyadic Kernel Discriminants
We present a novel machine learning (ML) algorithm for training complex binary classifiers by superposition of simpler hyper plane discriminants formed by projection of a test point onto a "dyad" (an oppositely labeled pair of training points). The learning is based on a real-valued variant of AdaBoost and the constituent hyperplane discriminants use kernels of the type used by Support Vector Machines (SVM). The resulting kernel classifier has an accuracy / complexity tradeoff which is more flexible than that of a SVM, is amenable to on-line adaptive learning (unlike SVMs) and has a classification performance which is as good (if not better) than comparable SVMs.
Background & Objective: Consider a collection of linear discriminants, each formed by means of a hyperplane orthogonal to the vector connecting a "dyad" (ie. a pair of data points with opposite class labels). By applying the method of linear hypercuts to a nonlinearly transformed feature space (using Mercer kernels) we obtain nonlinear discriminants similar to SVMs. Using AdaBoost, the search for each new candidate hypercut explores the space of all possible dyadic classifiers. For both linear and nonlinear classification problems, boosted dyadic hypercuts form an efficient search strategy for exploring the space of all classifier hypotheses.
Technical Discussion: The ensemble of dyadic hypercuts is learned incrementally by means of a real-valued or confidence-rated version of AdaBoost, which provides a sound strategy for searching through the finite (but possibly large) set of hypercut hypotheses. In experiments with real-world datasets from the UCI ML repository, the generalization performance of the hypercut classifiers was found to be comparable to that of SVMs and k-NN classifiers. Furthermore, the computational cost of classification (at run time) was found to be similar to, or better than, a comparable SVM. In contrast to SVMs we offer an on-line and incremental learning machine for building kernel discriminants whose complexity (number of kernel evaluations) can be directly controlled (traded off for accuracy).
Outside Collaborations: This project was joint work with Gregory Shakhnarovich (MIT).
Contact: Joseph Katz
| Technical Reports: | |
| Boosted Dyadic Kernel Discriminants | |
Technology Areas:
Artificial Intelligence
Computer Vision
Modification Date: September 12, 2007
