FoCM 2014 conference
Workshop B1 - Approximation Theory
December 16, 15:30 ~ 15:55 - Room B21
Tree Algorithms for Classification
Peter Binev
University of South Carolina , USA - binev@math.sc.edu
The solution of the problem of binary classification is often presented as a set of points at which one predicts a positive outcome assuming that a negative outcome is expected at the points of the complement set. Given a family of sets the goal is to find an element for which the risk of misclassification is as small as possible. We want to find an effective algorithm that based on a collection of query points identifies with high probability a good approximation in terms of minimizing the risk. As usual, no prior knowledge is assumed about the underlying probability measure related to the classification. We consider families of sets defined via tree structures and propose a convergence analysis based on nonlinear approximation theory, which allows us to significantly weaken the usual assumptions that are made to establish a given convergence rate. Algorithms using occupancy trees and decorated trees are presented to show one possible efficient realization of the general theory.