Supervised Learning Using Truth Tables: Convergence Results and Algorithms.

International audienceA novel method for combining weak classifiers in supervised learning is described, which fully characterizes the set of weak classifiers by a truth table.Convexification of the risk function (risk of false decision for any combination of the chosen weak classifiers) with any calibrated C2 classification function ϕ, yields a minimization problem in ℝ^M , whose unique solution is easily studied using a classical minimization algorithm that amounts to iteratively solving equations in ℝ with a Newton method.The complexity of this method depends only linearly on the number M of weak classifiers and does not depend on the number of examples in the training set or on the dimension of the underlying space where the examples are considered.In the case of two well-known ϕ's, the Boosting function (for all M) or the Logistic function (in the case M=3), the algorithm even leads to an explicit formula for the sequence of points of the sequence that converges to the minimum point.This framework is then used to study the quality of the training set, i.e., how the results are modified if some examples are added or removed from the training set, thus setting criteria for the stability of the results under such operations. This leads to criteria for quasi-separability of two sets (two-class classifiers) or margin analysis.Linear separation of a mixture of 2 Gaussian distributions is used as an illustration of our work and results