New classification algorithms based on the notion of 'margin'
(e.g. Support Vector Machines, Boosting) have recently been developed.
The goal of this thesis is to better understand how they work, via a
study of their theoretical performance.
In order to do this, a general framework for real-valued
classification is proposed. In this framework, it appears that the
natural tools to use are Concentration Inequalities and Empirical
Thanks to an adaptation of these tools, a new measure of the size of a
class of functions is introduced, which can be computed from the data.
This allows, on the one hand, to better understand the role of
eigenvalues of the kernel matrix in Support Vector Machines, and on
the other hand, to obtain empirical model selection criteria.