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   -

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.

View abstract PDF