03 - Model selection by bootstrap penalization for classification.pdf

Mach Learn (2007) 66:165–207
DOI -006-7679-y
Model selection by bootstrap penalization
for classification
Magalie Fromont
Received: 2 April 2005 / Revised: 16 December 2005 / Accepted: 22 December 2005 / Published online:
3 May 2006
Springer Science + Business Media, LLC 2007
Abstract We consider the binary classification problem. Given an . sample drawn from
the distribution of an X ×{0, 1}−valued random pair, we propose to estimate the so-called
Bayes classifier by minimizing the sum of the empirical classification error and a penalty
term based on Efron’s or . weighted bootstrap samples of the data. We obtain exponential
inequalities for such bootstrap type penalties, which allow us to derive non-asymptotic proper-
ties for the corresponding estimators. In particular, we prove that these estimators achieve the
global minimax risk over sets of functions built from Vapnik-Chervonenkis classes. The ob-
tained results generalize Koltchinskii (2001) and Bartlett et al.’s (2002) ones for Rademacher
penalties that can thus be seen as special examples of bootstrap type penalties. To illustrate
this, we carry out an experimental study in which pare the different methods for an
intervals model selection problem.
Keywords Model selection . Classification . Bootstrap penalty . Exponential inequality .
Oracle inequality . Minimax risk
1 Introduction
Let (X, Y ) be a random pair with values in a measurable space  = X ×{0, 1}, and with
unknown distribution denoted by independent copies (X1, Y1),... ,(Xn, Yn)of
(X, Y ), we aim at constructing a classification rule that is a function which would give the
value of Y from the observation of X. More precisely, in statistical terms, we are interested
in the estimation of the function s minimizing the classification error P[t(X) = Y ]overall
the measurable functions t : X →{0, 1}. The function s is called the Bayes classifier and it
is also defined by s(x) = IP[Y =1|X=x]>1/2.
Edit