\documentclass[XUPS,XML,SOM,Unicode,francais,NoFloatCountersInSection,ThmDefs]{cedram}
\OneNumberAllTheorems
\setcounter{tocdepth}{2}
\usepackage{xups13-02}
\graphicspath{{xups13-02_figures}}

\AtBeginDocument{%
\renewcommand{\appendixname}{Appendice}%
}

\let\subsection\Subsection

\hyphenation{mathé-ma-tique mathé-ma-tiques}
\begin{document}
\frontmatter

\title[Apprentissage statistique]{Fondements mathématiques de\nobreakspace l'apprentissage statistique}

\author[\initial{Ch.} \lastname{Giraud}]{\firstname{Christophe} \lastname{Giraud}}
\address{CMAP, UMR CNRS 7641, École Polytechnique,
91128 Palaiseau Cedex}
\email{christophe.giraud@math.u-psud.fr}

\thanks{Journées X-UPS 2013. Aléatoire. Éditions de l'École polytechnique, 2013}

\begin{abstract}
L'objectif d'un algorithme de classification est de prédire au mieux la classe d'un objet à partir d'observations de cet objet. Un exemple typique est le filtre à spam des messageries électroniques qui prédisent (plus ou moins bien) si un courriel est un spam ou non. Nous introduisons dans ces notes les principaux concepts fondamentaux de la théorie de la classification statistique supervisée et quelques uns des algorithmes de classification les plus populaires. Nous soulignons chemin faisant l'importance de certains concepts mathématiques, parmi lesquels la symétrisation, la convexification, les inégalités de concentration, le principe de contraction et les espaces de Hilbert à noyau reproduisant.
\end{abstract}
\maketitle
\vspace*{-\baselineskip}
\tableofcontents
\mainmatter

\section{Introduction}
En ce début de siècle, nous observons un accroissement phénoménal de l'utilisation des mathématiques, à la fois dans l'industrie et dans les laboratoires scientifiques. Cet essor de l'importance des mathématiques va de pair avec l'explosion des volumes de données collectées et l'accroissement de la puissance de calculs des ordinateurs. Dans l'industrie, la modélisation mathématique apparaît à tous les stades de la vie d'un produit. Depuis la conception technique, avec force de simulations numériques, via la production, avec l'optimisation des ressources et des flux, jusqu'au marketing et la distribution avec des prévisions basées sur l'analyse de grandes bases de données.
Dans les laboratoires scientifiques, la modélisation mathématique devient de plus en plus cruciale, en particulier en biologie et médecine où les scientifiques doivent extraire des informations pertinentes des données massives qu'ils produisent grâce aux récents développements biotechnologiques.

La classification automatique est peut-être l'un des usages quotidiens les plus invasifs des mathématiques. L'objectif de la classification automatique est de prédire au mieux la classe $y$ d'un objet $x$ à partir d'observations de ce dernier. Un exemple typique est le filtre à spam de notre messagerie électronique qui prédit (plus ou moins bien) si un courriel est un spam ou non. La classification automatique est omniprésente dans notre quotidien, filtrant nos courriels, lisant automatiquement les codes postaux sur nos lettres ou reconnaissant les visages sur les photos que nous publions sur les réseaux sociaux. Elle est aussi extrêmement importante en sciences, par exemple en médecine pour effectuer des diagnostics précoces à partir de données à hauts débits, ou pour la recherche \emph{in silico} de médicaments efficaces.

Nous introduisons dans ces notes les principaux concepts fondamentaux de l'apprentissage statistique (supervisé).
Nous décrivons dans la partie~\ref{sec:supervised1} la modélisation mathématique d'un problème générique de classification. Dans la partie~\ref{sec:erm}, nous analysons la précision prédictive d'un algorithme universel de classification et dans la partie~\ref{sec:cvxERM} nous dérivons de cet algorithme théorique des algorithmes numériquement implémentables et populaires.
Les appendices rassemblent des résultats techniques nécessaires pour la définition et l'analyse des algorithmes de classification.

\section{Modélisation mathématique}\label{sec:supervised1}
Par soucis de simplicité, nous allons nous restreindre au cas où il y a seulement deux classes (comme pour le filtre à spam). Le problème de la classification automatique peut alors être modélisé de la manière suivante. Soit $\mX$ un espace mesuré. On observe conjointement un
point $X\in\mX$ et une étiquette $Y\in\ac{-1,+1}$. Notre objectif est de construire une fonction
$h:\mX\to\ac{-1,+1}$, appelée \emph{classifieur}, telle que $h(X)$
prédit au mieux l'étiquette $Y$.

Supposons que le couple $(X,Y)\in \mX\times\ac{-1,+1}$ est issu d'un tirage selon une loi $\p$. Pour un classifieur $h:\mX\to\ac{-1,+1}$ donné,
la probabilité de mauvaise classification est
$$L(h)=\p(Y\neq h(X)).$$
Comme $|Y-h(X)|\in\ac{0,2}$, nous avons par le théorème de Pythagore
\begin{align*}
L(h)&={1\over 4}\, \E\cro{(Y-h(X))^2}\\
&={1\over 4}\, \E\cro{(Y-\E\cro{Y|X})^2}+{1\over 4}\, \E\cro{(\E\cro{Y|X}-h(X))^2}.
\end{align*}
En conséquence, $L(h)$ est minimal pour le classifieur de Bayes
$$h_{*}(X)=\sign(\E\cro{Y|X})\quad\textrm{où}\quad \textrm{sign(x)}=\1_{x>0}-\1_{x\leq 0}\quad \textrm{pour}\ x\in\R.$$
Lorsque la loi $\p$ est connue, il suffit donc d'utiliser le classifieur de Bayes $h_{*}$ pour avoir la plus petite probabilité possible de mauvaise classification.

Malheureusement, la loi $\p$ est en général inconnue et on ne peut donc pas calculer le classifieur de
Bayes $h_{*}$. En pratique, nous avons uniquement accès à des données dites d'apprentissage
$(X_{i},Y_{i})_{i=1,\ldots,n}$ i.i.d.\ de loi $\p$
et notre objectif est de construire à partir de ces données d'apprentissage un classifieur
$\hh:\mX\to\ac{-1,+1}$ tel que $L(\hh)-L(h_{*})$ est aussi petit que possible.

\section{Minimisation du risque empirique}\label{sec:erm}
Comme la loi $\p$ est inconnue, nous ne pouvons pas calculer la probabilité de mauvaise classification
$L(h)$.
On peut cependant calculer à la place la probabilité empirique de mauvaise classification
$$\hL_{n}(h):={1\over n}\sum_{i=1}^n\1_{Y_{i}\neq h(X_{i})}=\widehat \p_{n}(Y\neq h(X)),$$
où $\widehat \p_{n}={1\over n}\sum_{i=1}^n\delta_{(X_{i},Y_{i})}$. À  un ensemble $\cH$ de classifieurs, appelé \emph{dictionnaire},
on peut associer le classifieur de minimisation du risque empirique
\begin{equation}\label{erm}
\hh_{\cH}\in\argmin_{h\in\cH}\hL_{n}(h).
\end{equation}
La définition de ce classifieur est très naturelle, cependant deux questions fondamentales se posent immédiatement: quel dictionnaire $\cH$ choisir? et comment $\hh_{\cH}$ se comporte-t-il comparativement à $h_{*}$?
Ces deux questions sont bien évidemment fortement reliées. En décomposant la différence entre les probabilités de mauvaise classification $L(\hh_{\cH})$ et $L(h_{*})$, on obtient
$$0\ \leq\ L(\hh_{\cH})-L(h_{*})\ =\ \underbrace{\min_{h\in\cH}L(h)-L(h_{*})}_{\textrm{erreur d'approximation}}+\underbrace{L(\hh_{\cH})-\min_{h\in\cH}L(h)}_{\textrm{erreur stochastique}}.$$
Le premier terme mesure la qualité de l'approximation de $h_{*}$ par un classifieur $h\in\cH$. Cette erreur d'approximation
est purement déterministe et élargir le dictionnaire $\cH$ ne peut que la réduire.
Le second terme mesure l'erreur résultant de la minimisation sur $h\in\cH$
de la probabilité empirique de mauvaise classification $\hL_{n}(h)$
au lieu de la vraie probabilité de mauvaise classification $L(h)$. Ce terme est stochastique et il tend à augmenter lorsque $\cH$ grossit. Ce phénomène est illustré figure~\ref{fig:overfit}.
\begin{figure}
\begin{center}
\includegraphics[width=0.28\textwidth]{A}\hfill\includegraphics[width=0.28\textwidth]{B}\hfill\includegraphics[width=0.28\textwidth]{C}
\caption{\smaller \label{fig:overfit} Exemples de classifications produites par différents dictionnaires. Gauche: avec des classifieurs liné\-aires~$\cH_{\textsf{lin}}$. Centre: avec des classifieurs polygonaux $\cH_{\textsf{poly}}$. Droite: avec des classifieurs basés sur des formes quadratiques.}
\end{center}
\vspace*{-.5\baselineskip}
\end{figure}
Dans cette illustration dans $\mX=\R^2$, les classifieurs du dictionnaire $\cH_{\textsf{lin}}=\ac{h(x)=\sign(\langle w,x\rangle):\|w\|=1}$ ne sont pas suffisamment flexibles et ils produisent une classification de mauvaise qualité.
Dans ce cas, l'erreur d'approximation est grande. À l'opposé, les classifieurs du dictionnaire
\[
\cH_{\textsf{poly}}=\ac{h(x)=2\,\1_{A}(x)-1: A\ \textrm{polygone dans}\ \mX}
\]
sont très flexibles et ils peuvent toujours reproduire exactement la classification des données $(X_{i},Y_{i})_{i=1,\ldots,n}$. L'erreur empirique $\hL_{n}(\hh_{\cH_{\textsf{poly}}})$ est donc toujours nulle, mais $\hh_{\cH_{\textsf{poly}}}$
tend a mal classifier une nouvelle donnée $(X,Y)$ et l'erreur stochastique $L(\hh_{\cH})-\min_{h\in\cH}L(h)$ est grande.
Le~dernier exemple, basé sur un ensemble moins flexible de classifieurs quadratiques produit de meilleurs résultats.

Pour choisir un bon dictionnaire $\cH$,
il faut donc trouver un bon équilibre entre les propriétés d'approximation de $\cH$
et sa taille. La première étape pour développer un principe de sélection de dictionnaire $\cH$
est de quantifier la probabilité de mauvaise classification du minimiseur du risque empirique
$\hh_{\cH}$.\enlargethispage{1.5\baselineskip}%

\subsection{Probabilité de mauvaise classification avec \texorpdfstring{$\hh_{\cH}$}{H}}
Comme mentionné ci-dessus, augmenter la taille de $\cH$ tend
à augmenter l'erreur stochastique $L(\hh_{\cH})-\min_{h\in\cH}L(h)$.
En fait, ce~n'est pas exactement la taille du dictionnaire qui compte, mais plutôt sa flexibilité en terme de classification. Par exemple, nous ne pouvons pas classifier correctement les trois points étiquetés\vspace*{-3pt}
\[
\ac{\big((0,1),+1\big),\big((1,1),-1\big),\big((1,0),+1\big)}
\]
avec les classifieurs dans $\cH_{\textsf{lin}}$. A~l'inverse, pour tout ensemble $(x_{i},y_{i})_{i=1,\ldots,n}$ de points étiquetés,
il~existe $h\in\cH_{\textsf{poly}}$ tel que $h(x_{i})=y_{i}$.

Nous quantifions cette flexibilité de classification par le coefficient d'éclatement\vspace*{-3pt}
\begin{equation}\label{shatter}
\S_{n}(\cH)=\max_{(x_{1},\ldots,x_{n})\in\mX^n}\card\ac{(h(x_{1}),\ldots,h(x_{n})):h\in\cH}\,,
\end{equation}
qui donne le nombre maximum d'étiquetages différents de $n$ points qui peuvent être produits par les classifieurs dans
$\cH$.
Par exemple, comme on peut obtenir à partir de $\cH_{\textsf{poly}}$ tous les étiquetages possibles de $n$ points (distincts), nous avons $\S_{n}(\cH_{\textsf{poly}})=2^n$. À  l'inverse, le nombre d'étiquetages possibles de $n$ points avec les classifieurs dans~$\cH_{\textsf{lin}}$ est plus limité. En effet, la proposition~\ref{prop:sauer} partie~\ref{sec:VC} implique que $\S_{n}(\cH_{\textsf{lin}})\leq (n+1)^2$. Le prochain théorème nous fournit une borne supérieure de l'erreur stochastique et un intervalle de confiance pour la probabilité de mauvaise classification $L(\hh_{\cH})$ en terme du coefficient d'éclatement.

\begin{Thm}[Contrôle de l'erreur stochastique]\label{thm:stocherror}
Pour tout $t>0$, nous avons avec probabilité au moins $1-e^{-t}$\vspace*{-3pt}
\begin{equation}\label{borneL}
L(\hh_{\cH})-\min_{h\in\cH} L(h)\leq 4\,\sqrt{2\log(2\,\S_{\cH}(n))\over n}+\sqrt{2t\over n}
\end{equation}
et\vspace*{-5pt}
\begin{equation}\label{IC}
\big|L(\hh_{\cH})-\hL_{n}(\hh_{\cH})\big|\leq 2\,\sqrt{2\log(2\,\S_{\cH}(n))\over n}+\sqrt{t\over 2n}
\end{equation}
\end{Thm}

\begin{proof}
Nous segmentons la preuve en trois lemmes. Le premier lemme montre que les termes de gauche dans~\eref{borneL} et~\eref{IC}
peuvent être bornés à l'aide du maximum sur $\cH$ de la différence entre l'erreur empirique de mauvaise classification et la vraie erreur de mauvaise classification\vspace*{-3pt}
\begin{equation}\label{Delta}
\hD(\cH)=\sup_{h\in\cH}\big|\hL_{n}(h)-L(h)\big|.
\end{equation}

\begin{lem}\label{classif:lem1}
Pour tout dictionnaire $\cH$ et entier $n$, nous avons les bornes supérieures\vspace*{-3pt}
$$L(\hh_{\cH})-\min_{h\in\cH} L(h)\leq 2\,\hD(\cH)\quad\textrm{et}\quad \big|L(\hh_{\cH})-\hL_{n}(\hh_{\cH})\big|\leq\hD(\cH).$$
\end{lem}

\begin{proof}
Pour tout $h\in\cH$, nous avons $\hL_{n}(\hh_{\cH})\leq \hL_{n}(h)$ et donc\vspace*{-3pt}
\begin{align*}
L(\hh_{\cH})-L(h) &= L(\hh_{\cH})-\hL_{n}(\hh_{\cH})+\hL_{n}(\hh_{\cH})- L(h)\\
&\leq L(\hh_{\cH})-\hL_{n}(\hh_{\cH})+\hL_{n}(h)- L(h)\\
&\leq 2\,\hD(\cH).
\end{align*}
Comme cette inégalité est vraie pour tout $h\in\cH$, nous en déduisons directement la première borne du lemme~\ref{classif:lem1}. La seconde borne est évidente.
\end{proof}


Pour démontrer le théorème~\ref{thm:stocherror},
il reste à prouver qu'on a
$$\hD(\cH)\leq 2\sqrt{2\log(2\,\S_{\cH}(n))\over n}+\sqrt{t\over 2n}$$
avec probabilité au moins $1-e^{-t}$.
Nous segmentons la preuve de cette borne en deux lemmes.

\begin{lem}\label{lem2}
Avec probabilité $1-e^{-t}$, nous avons
$$\hD(\cH)\leq \E\cro{\hD(\cH)}+\sqrt{t\over 2n}.$$
\end{lem}

\begin{proof}
Nous avons $\hD(\cH)=F((X_{1},Y_{1}),\ldots,(X_{n},Y_{n}))$ avec
\begin{align*}
F: \quad(\mX\times \ac{-1,+1})^n \quad&\to\quad \R\\
((x_{1},y_{1}),\ldots,(x_{n},y_{n}))&\mto {1\over n}\sup_{h\in\cH}\Big|\sum_{i=1}^n\1_{y_{i}\neq h(x_{i})}-L(h)\Big|\,.
\end{align*}
Pour tout $(x_{1},y_{1}),\ldots,(x_{n},y_{n}),(x'_{i},y'_{i})\in \mX\times \ac{-1,+1}$, nous avons
\begin{multline*}
\big|F((x_{1},y_{1}),\ldots,(x'_{i},y'_{i}),\ldots,(x_{n},y_{n}))\\
-F((x_{1},y_{1}),\ldots,(x_{i},y_{i}),\ldots,(x_{n},y_{n}))\big|\leq {1\over n}\,.
\end{multline*}
En conséquence, l'inégalité de concentration de McDiarmid (voir théorème~\ref{McDiarmid} de l'appendice~\ref{App:concentration}),
nous assure qu'avec probabilité au moins $1-e^{-2ns^2}$, nous avons $\hD(\cH)\leq \E\cro{\hD(\cH)}+s$. Le lemme~\ref{lem2} en découle (avec le changement de variable $s=\sqrt{t/(2n)})$.
\end{proof}


Il reste à borner l'espérance de $\hD(\cH)$ à l'aide de $\S_{\cH}(n)$.

\begin{lem}\label{lem3}
Pour tout dictionnaire $\cH$, nous avons l'inégalité
$$\E\bcro{\hD(\cH)}\leq 2\, \sqrt{2\log(2\,\S_{\cH}(n))\over n}\,.$$
\end{lem}

\begin{proof}
La preuve du lemme~\ref{lem3} est basée sur un argument classique et élégant de symétrisation.

La première étape de la symétrisation est de représenter la probabilité de mauvaise classification $L(h)$
comme l'espérance de la probabilité empirique de mauvaise classification
$$L(h)=\p(Y\neq h(X))=\widetilde \E \bbcro{{1\over n}\sum_{i=1}^n\1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}},$$
où $(\widetilde X_{i},\widetilde Y_{i})_{i=1,\ldots,n}$ est indépendant de $(X_{i},Y_{i})_{i=1,\ldots,n}$ et est identiquement distribué. Dans la suite, nous noterons $\widetilde \E$ pour l'espérance par rapport aux variables $(\widetilde X_{i},\widetilde Y_{i})_{i=1,\ldots,n}$ et $\E$ pour l'espérance par rapport aux variables $(X_{i},Y_{i})_{i=1,\ldots,n}$.
Les inégalités de Jensen et Fatou nous donnent
\begin{align*}
\E\bcro{\hD(\cH)}&=\E\bbcro{\sup_{h\in\cH}\bigg|{1\over n}\sum_{i=1}^n\1_{Y_{i}\neq h(X_{i})} - \widetilde \E \bbcro{{1\over n}\sum_{i=1}^n\1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}} \bigg|}\\
&\leq \E\widetilde \E\bbcro{\sup_{h\in\cH}\Big|{1\over n}\sum_{i=1}^n\pa{\1_{Y_{i}\neq h(X_{i})} - \1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}} \Big|}.
\end{align*}
La seconde étape consiste à capitaliser sur la symétrie des varia\-bles $\1_{Y_{i}\neq h(X_{i})} - \1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}\,$. Nous introduisons $n$ variables aléatoires i.i.d.\ $(\sigma_{i})_{i=1,\ldots,n}$ indépendantes de $(X_{i},Y_{i},\widetilde X_{i},\widetilde Y_{i})_{i=1,\ldots,n}$ et de loi
\[
\p_{\sigma}(\sigma_{i}=1)=\p_{\sigma}(\sigma_{i}=-1)=1/2.
\]
Par symétrie, on remar\-que que $\bpa{\sigma_{i}\bpa{\1_{Y_{i}\neq h(X_{i}} - \1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}}}_{i=1,\ldots,n}$
a la même loi que $\bpa{\1_{Y_{i}\neq h(X_{i})} - \1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}}_{i=1,\ldots,n}$, donc nous obtenons
\begin{eqnarray*}
\E\bcro{\hD(\cH)}&\leq& \E\widetilde \E\E_{\sigma}\bbcro{\sup_{h\in\cH}\Big|{1\over n}\sum_{i=1}^n\sigma_{i}\pa{\1_{Y_{i}\neq h(X_{i})} - \1_{\widetilde Y_{i}\neq h(\widetilde X_{i})}} \Big|}\\
&\leq& 2\E\E_{\sigma}\bbcro{\sup_{h\in\cH}\Big|{1\over n}\sum_{i=1}^n\sigma_{i}\1_{Y_{i}\neq h(X_{i})} \Big|}\\
&\leq& 2\, \max_{y\in \ac{-1,+1}^n}\, \max_{x\in \mX^n}\,\E_{\sigma}\bbcro{\sup_{h\in\cH}\Big|{1\over n}\sum_{i=1}^n\sigma_{i}\1_{y_{i}\neq h(x_{i})} \Big|},
\end{eqnarray*}
où la seconde inégalité découle de l'inégalité triangulaire. Pour tout $(x,y)\in \mX^n\times \ac{-1,+1}^n$, nous introduisons l'ensemble
$$\mV_{\cH}(x,y)=\ac{(\1_{y_{1}\neq h(x_{1})},\ldots,\1_{y_{n}\neq h(x_{n})}):\ h\in\cH}.$$
La dernière majoration de $\E\cro{\hD(\cH)}$ peut s'écrire comme
$$\E\bcro{\hD(\cH)} \leq {2\over n}\times \max_{y\in \ac{-1,+1}^n}\, \max_{x\in \mX^n}\,\E_{\sigma}\Bcro{\sup_{v\in\mV_{\cH}(x,y)}|\langle \sigma,v\rangle|},$$
où $\langle x, y\rangle$ est le produit scalaire canonique sur $\R^n$. Remarquons au passage qu'entre le membre de gauche et le membre de droite nous avons remplacé l'espérance sous la probabilité inconnue $\p$ par une espérance sous la probabilité connue $\p_{\sigma}$.
Pour tout $y\in \ac{-1,+1}^n$ remarquons aussi qu'il y a une bijection entre $\mV_{\cH}(x,y)$ et l'ensemble $\ac{(h(x_{1}),\ldots,h(x_{n})):h\in\cH}$.
En conséquence, nous avons la majoration
$$\max_{y\in \ac{-1,+1}^n}\ \max_{x\in \mX^n}\card(\mV_{\cH}(x,y))\leq \S_{n}(\cH).$$
Au regard des deux dernières inégalités, il suffit de démontrer que
\begin{multline}\label{eq:clefVapnik}
\E_{\sigma}\cro{\sup_{v\in\mV}|\langle \sigma,v\rangle|}\leq \sqrt{2n\log\pa{2\,\card(\mV)}},\\ \textrm{pour tout ensemble}\quad \mV\subset \ac{-1,0,+1}^n
\end{multline}
pour conclure la preuve du lemme~\ref{lem3}. Démontrons~\eref{eq:clefVapnik}. Avec la notation $\mV^{\#}=\mV\cup-\mV$, l'inégalité de Jensen nous donne pour tout~\hbox{$s>0$}
\begin{eqnarray}
\E_{\sigma}\Bcro{\sup_{v\in\mV}|\langle \sigma,v\rangle|}&=&\E_{\sigma}\Bcro{\sup_{v\in\mV^{\#}}\langle \sigma,v\rangle}\ \leq\ {1\over s}\,\log\,\E_{\sigma}\Bcro{\sup_{v\in\mV^{\#}} e^{s\langle \sigma,v\rangle}}	\nonumber\\
&\leq&{1\over s}\,\log\Bpa{\sum_{v\in\mV^{\#}}\E_{\sigma}\cro{ e^{s\langle \sigma,v\rangle}}}\label{eq:logexp}.
\end{eqnarray}
En combinant le fait que les $\sigma_{i}$ sont indépendants, que $(e^{x}+e^{-x})\leq 2e^{x^2/2}$ pour tout $x\in\R$ et que
$v_{i}^2\in\{0,1\}$ pour tout $v\in\mV^{\#}$, nous obtenons
\begin{eqnarray*}
\E_{\sigma}\cro{ e^{s\langle \sigma,v\rangle}}&=&\prod_{i=1}^n\E_{\sigma}\cro{ e^{sv_{i}\sigma_{i}}}\ =\ \prod_{i=1}^n{1\over 2}(e^{sv_{i}}+e^{-sv_{i}})\\
&\leq & \prod_{i=1}^ne^{s^2v_{i}^2/2}\ \leq\ e^{ns^2/2}.
\end{eqnarray*}
En injectant cette majoration dans~\eref{eq:logexp}, nous obtenons
$$\E_{\sigma}\cro{\sup_{v\in\mV}|\langle \sigma,v\rangle|}\leq {\log(\card(\mV^{\#})\over s}+{ns\over 2}\quad \quad \textrm{pour tout}\ s>0.$$
Le terme de droite est minimal pour $s=\sqrt{2\log(\card(\mV^{\#}))/n}$, ce qui nous donne la majoration
$$\E_{\sigma}\cro{\sup_{v\in\mV}|\langle \sigma,v\rangle|}\leq \sqrt{2n\log(\card(\mV^{\#}))}.$$

Nous obtenons finalement la borne~\eref{eq:clefVapnik} en remarquant que $\card(\mV^{\#})\leq 2\, \card(\mV)$. La preuve du lemme~\ref{lem3} est complète.
\end{proof}


Les bornes \eref{borneL} et \eref{IC} s'obtiennent directement en combinant les trois lemmes.
\end{proof}

\subsection{Sélection de dictionnaire}
Soit $\ac{\cH_{1},\ldots,\cH_{M}}$ une collection de dictionnaires de classifieurs. Nous aimerions sélectionner parmi cette collection, le dictionnaire~$\cH_{*}$ avec la plus petite probabilité de mauvaise classification $L(\hh_{\cH_{*}})$. Ce~dictionnaire $\cH_{*}$, dit \emph{dictionnaire oracle}, dépend de la probabilité inconnue $\p$, il n'est donc malheureusement pas connu du statisticien. Dans cette partie, nous allons développer à partir du théorème~\ref{thm:stocherror} une procédure reposant sur les données pour sélectionner parmi la collection $\ac{\cH_{1},\ldots,\cH_{M}}$ un dictionnaire $\cH_{\hm}$ ayant des performances similaires à celles de~$\cH_{*}$.

Le dictionnaire oracle $\cH_{*}$ est obtenu en minimisant la probabilité de mauvaise classification
$L(\hh_{\cH})$ sur $\cH\in\ac{\cH_{1},\ldots,\cH_{M}}$. Une première idée est de sélectionner
$\cH_{\hm}$ en minimisant sur la collection $\ac{\cH_{1},\ldots,\cH_{M}}$ la probabilité empirique de mauvaise classification
$\hL_{n}(\hh_{\cH})$. Cette procédure de sélection ne donne pas de bons résul\-tats car pour tout
$\cH\subset \cH'$ on a toujours $\hL_{n}(\hh_{\cH'})\leq \hL_{n}(\hh_{\cH})$,
donc la procédure tend à sélectionner le dictionnaire le plus gros possible. Pour bâtir une bonne procédure de sélection, nous devons prendre en compte les fluctuations de $\hL_{n}(\hh_{\cH})$ autour de $L(\hh_{\cH})$. La borne~\eref{IC} du
théorème~\ref{thm:stocherror} nous offre un contrôle de ces fluctuations. En élaborant à partir de cette borne, nous obtenons le résultat suivant.

\begin{Thm}[Sélection de dictionnaire]
\label{thm:selectionD}
Considérons la procédure de sélection de dictionnaire
\begin{multline*}
\hm=\argmin_{m=1,\ldots,M}\ac{\hL_{n}(\hh_{\cH_{m}})+\pen(\cH_{m})},\\[-12pt]
\textrm{avec}\quad\pen(\cH)=2\,\sqrt{2\log(2\,\S_{n}(\cH))\over n}\,.
\end{multline*}
Alors, pour tout $t>0$, avec probabilité au moins $1-e^{-t}$ nous avons
\begin{multline}\label{eq:oracleD}
L(\hh_{\cH_{\hm}})\\[-8pt]
\leq \min_{m=1,\ldots,M} \ac{\inf_{h\in\cH_{m}}L(h)+2\,\pen(\cH_{m})}+\sqrt{2\log(M)+2t\over n}\,.
\end{multline}
\end{Thm}

Avant de prouver le théorème~\ref{thm:selectionD}, commentons la borne~\eref{eq:oracleD}.
Comme $\min_{h\in\cH}L(h)\leq L(\hh_{\cH})$, nous obtenons avec probabilité $1-e^{-t}$ que
$$L(\hh_{\cH_{\hm}})\leq L(\hh_{\cH_{*}})+
%4\,\sqrt{2\log(2\,\S_{n}(\cH_{*}))\over n}
2\,\pen(\cH_{*})
+\sqrt{2\log(M)+2t\over n}\,.$$
En particulier, cela nous permet de comparer la probabilité de mauvaise classification du classifieur sélectionné à celle du meilleur classifieur parmi la collection $\big\{\hh_{\cH_{1}},\ldots,\hh_{\cH_{M}}\big\}$.

Remarquons aussi que le second terme de la borne~\eref{eq:oracleD} augmente en $\sqrt{2\log(M)/n}$ avec le nombre $M$ de dictionnaires candidats.
Enfin, nous noterons que les résultats restent valides si on prend $\pen(\cH)$ plus grand que $2\,\sqrt{2\log(2\,\S_{n}(\cH))/n}$.

\skpt\begin{proof}[\proofname\ du théorème~\ref{thm:selectionD}]\par
\begin{small}
Rappelons la notation $\hD(\cH)=\sup_{h\in\cH}\big|\hL_{n}(h)-L(h)\big|$.
Les lemmes~\ref{lem2} et~\ref{lem3} nous assurent qu'avec probabilité au moins $1-e^{-t}$ nous avons
\begin{multline}\label{probaglobale}
\hD(\cH_{m})\leq \pen(\cH_{m})+\sqrt{\log(M)+t\over 2n},\\ \textrm{\emph{simultanément} pour tout}\ m=1,\ldots,M.
\end{multline}
En conséquence, le lemme~\ref{classif:lem1}
et la définition du critère de sélection nous donnent qu'avec probabilité au moins
$1-e^{-t}$
\begin{equation}\label{inegcrit}
\begin{split}
L(\hh_{\cH_{\hm}})&\leq \hL_{n}(\hh_{\cH_{\hm}})+ \pen(\cH_{\hm})+\sqrt{\log(M)+t\over 2n}\\
&\leq \min_{m=1,\ldots,M} \ac{\hL_{n}(\hh_{\cH_{m}})+ \pen(\cH_{m})}+\sqrt{\log(M)+t\over 2n}\,.
\end{split}
\end{equation}
Pour conclure, il suffit de contrôler $\hL_{n}(\hh_{\cH_{m}})$ en fonction de $\inf_{h\in\cH_{m}}L(h)$. Cela peut être fait directement en combinant les inégalités~\eref{borneL} et~\eref{IC},
mais la majoration résultante peut être améliorée par le raisonnement ci-dessous.


Pour comparer $\hL_{n}(\hh_{\cH_{m}})$ à $\inf_{h\in\cH_{m}}L(h)$,
commençons par remarquer que pour tout
$h\in\cH_{m}$ nous avons
$$\hL_{n}(\hh_{\cH_{m}})\leq \hL_{n}(h) \leq L(h)+\hD(\cH_{m}),$$
donc en prenant l'infimum sur $h\in\cH_{m}$ nous obtenons pour tout $m=1,\ldots,M$
$$\hL_{n}(\hh_{\cH_{m}})\leq \inf_{h\in\cH_{m}} L(h)+\hD(\cH_{m}).$$
En combinant cette majoration avec~\eref{probaglobale} et~\eref{inegcrit}, on trouve
$$L(\hh_{\cH_{\hm}})\leq \min_{m=1,\ldots,M} \ac{\inf_{h\in\cH_{m}}L(h)+ 2\,\pen(\cH_{m})}+2\,\sqrt{\log(M)+t\over 2n}\,.$$
La preuve du théorème~\ref{thm:selectionD} est complète.
\end{small}
\end{proof}


\begin{remarque*}
En combinant \eref{probaglobale} avec le lemme~\ref{classif:lem1},
on obtient un intervalle de confiance pour la probabilité de mauvaise classification
\begin{multline*}
{\p\pa{L(\hh_{\cH_{\hm}})\in \big[\hL_{n}(\hh_{\cH_{\hm}})-\delta(\hm,t),\hL_{n}(\hh_{\cH_{\hm}})+\delta(\hm,t)\big]}\geq 1-e^{-t}}\\
\textrm{avec}\quad \delta(\hm,t)=\pen(\cH_{\hm})+\sqrt{\log(M)+t\over 2n}\,.\quad
\end{multline*}
\end{remarque*}

\subsection{Dimension combinatoire de Vapnik-Chervonenkis}\label{sec:VC}
Le calcul des coefficients d'éclatement $\S_{n}(\cH)$ peut être complexe en pratique. Cependant, une propriété combinatoire remarquable de ces coefficients d'éclatement permet d'obtenir une majoration simple de
$\S_{n}(\cH)$, ne dépendant de $\cH$ qu'à travers une unique quantité, la~dimen\-sion
de Vapnik-Chervonenkis de $\cH$ définie ci-dessous.

Par convention on posera $\S_{0}(\cH)=1$. On appelle VC-dimension de~$\cH$ l'entier $d_{\cH}$ défini par
$$d_{\cH}=\sup\ac{d\in\N: \S_{d}(\cH)=2^d}\ \in \ \N\cup\ac{+\infty}.$$
Elle correspond au nombre maximum de points de
$\mX$ qui peuvent être classifiés de toutes les façons possibles par les classifieurs de $\cH$.
La proposition suivante donne une majoration du coefficient d'éclatement $\S_{n}(\cH)$ en fonction de la
VC-dimension $d_{\cH}$.

\begin{propo}[Lemme de Sauer]\label{prop:sauer}
Soit $\cH$ un ensemble de classifieurs de VC-dimension $d_{\cH}$ finie. Pour tout $n\in\N$, on a
$$\S_{n}(\cH)\leq \sum_{i=0}^{d_{\cH}} C_{n}^{i}\leq (n+1)^{d_{\cH}}\quad \textrm{avec}\quad C_{n}^{i}=\left\{\begin{array}{cl}
\dpl{n!\over i!\,(n-i)!}& \textrm{pour}\ n\geq i\\
0& \textrm{pour}\ n<i.
\end{array}\right.$$
\end{propo}

\begin{proof}
Nous commençons par prouver par récurrence sur $k$ l'inégalité
\begin{equation}\label{sauer0}
\S_{k}(\cH)\leq \sum_{i=0}^{d_{\cH}} C_{k}^{i}
\end{equation}
pour tout
$\cH$ de VC-dimension finie $d_{\cH}$.

Considérons dans un premier temps le cas $k=1$. Si $d_{\cH}=0$, aucun point ne peut être étiqueté de deux manières différentes, donc tous les points ne peuvent être étiquetés que d'une seule manière. Il en découle que
$\S_{1}(\cH)=1$, qui est égal à $C_{1}^0$. Si $d_{\cH}\geq 1$, nous avons $\S_{1}(\cH)=2$ qui est égal à $C_{1}^0+C_{1}^1$.


Supposons maintenant que \eref{sauer0} est vraie pour tout $k\leq n-1$. Considérons $\cH$ de VC-dimension $d_{\cH}$ finie. Comme on vient de le voir, lorsque $d_{\cH}=0$
tous les points peuvent être étiqueté d'une seule manière donc $\S_{k}(\cH)=1$ et~\eref{sauer0} est vraie pour tout $k$.
Considérons maintenant le cas $d_{\cH}\geq1$.
Soient $x_{1},\ldots,x_{n}\in\mX$ et définissons
$$\cH(x_{1},\ldots,x_{n})=\ac{(h(x_{1}),\ldots,h(x_{n})):h\in\cH}.$$
L'ensemble $\cH(x_{1},\ldots,x_{n})$ ne dépend que des valeurs de $h$ sur $\ac{x_{1},\ldots,x_{n}}$,
donc on peut remplacer $\cH$ par \hbox{$\F\!=\!\{h|_{\ac{x_{1},\ldots,x_{n}}}: h\!\in\!\cH\}$} dans la définition de $\cH(x_{1},\ldots,x_{n})$. Comme $d_{\F}$ est inférieur à $d_{\cH}$,
on peut supposer sans perte de généralité que $\mX=\ac{x_{1},\ldots,x_{n}}$ et $\cH=\F$, ce que nous faisons par la suite. Considérons l'ensemble
$$\cH'=\ac{h\in\cH:h(x_{n})=1\ \textrm{et}\ h'=h-2\times\1_{\ac{x_{n}}}\in\cH}.$$
Comme $\cH(x_{1},\ldots,x_{n})=\cH'(x_{1},\ldots,x_{n})\cup(\cH\setminus\cH')(x_{1},\ldots,x_{n})$ nous avons
\begin{multline}\label{sauer1}
\card\pa{\cH(x_{1},\ldots,x_{n})}\leq \card\pa{\cH'(x_{1},\ldots,x_{n})}\\
+\card\pa{(\cH\setminus\cH')(x_{1},\ldots,x_{n})}.
\end{multline}

Nous allons majorer séparément le cardinal de
${\cH'(x_{1},\ldots,x_{n})}$ et celui de ${(\cH\setminus\cH')(x_{1},\ldots,x_{n})}$.

\begin{enumerate}
\item Pour commencer, remarquons que
\[
\card\pa{\cH'(x_{1},\ldots,x_{n})}=\card\pa{\cH'(x_{1},\ldots,x_{n-1})}
\]
car on a $h(x_{n})=1$ pour tout $h\in\cH'$. Ensuite, on observe que la
VC-dimension $d_{\cH'}$ de $\cH'$ est au plus $d_{\cH}-1$. En effet, si $d$ points $x_{i_1},\ldots,x_{i_d}$ de $\mX=\ac{x_{1},\ldots,x_{n}}$ peuvent être étiquetés de toutes les manières possibles par $\cH'$, alors $x_{n}\notin \ac{x_{i_1},\ldots,x_{i_d}}$ vu que $h(x_{n})=1$ pour tout $h\in\cH'$. De plus, l'ensemble $\ac{x_{i_1},\ldots,x_{i_d},x_{n}}$ peut être étiqueté de toutes les manières possibles par $\cH$ par définition de $\cH'$, donc $d+1\leq d_{\cH}$, ce qui implique $d_{\cH'}\leq d_{\cH}-1$. En appliquant~\eref{sauer0} avec $k=n-1$
on obtient
\begin{equation}\label{sauer2}
\begin{split}
\card\pa{\cH'(x_{1},\ldots,x_{n})}&=\card\pa{\cH'(x_{1},\ldots,x_{n-1})}\\
&\leq \sum_{i=0}^{d_{\cH}-1} C_{n-1}^{i}.
\end{split}
\end{equation}
\item Si $h,h'\in\cH\setminus\cH'$ vérifient $h(x_{i})=h'(x_{i})$ pour $i=1,\ldots,n-\nobreak1$, alors ils vérifient aussi $h(x_{n})=h'(x_{n})$ par définition de $\cH'$. En conséquence, on a comme précédemment l'égalité
$$
\card\pa{(\cH\setminus\cH')(x_{1},\ldots,x_{n})}=\card\pa{(\cH\setminus\cH')(x_{1},\ldots,x_{n-1})}.
$$
De plus $d_{\cH\setminus\cH'}$ est inférieur à $d_{\cH}$ car $\cH\setminus\cH'\subset \cH$ donc l'équation~\eref{sauer0} avec $k=n-1$ donne
\begin{multline}\label{sauer3}
\card\pa{(\cH\setminus\cH')(x_{1},\ldots,x_{n})}\\[-8pt]
=\card\pa{(\cH\setminus\cH')(x_{1},\ldots,x_{n-1})}
\leq \sum_{i=0}^{d_{\cH}} C_{n-1}^{i}\,.
\end{multline}
\end{enumerate}

En combinant \eref{sauer1}, \eref{sauer2} et \eref{sauer3}, on obtient
$$\card\pa{\cH(x_{1},\ldots,x_{n})}\leq \sum_{i=1}^{d_{\cH}} C_{n-1}^{i-1}+\sum_{i=0}^{d_{\cH}} C_{n-1}^{i}=\sum_{i=0}^{d_{\cH}} C_{n}^{i}\,,$$
car $C_{n-1}^{i}+C_{n-1}^{i-1}=C_{n}^{i}$ pour $i\geq 1$.
Il en découle que \eref{sauer0} est vrai pour $k=n$ et la récurrence est établie.

La seconde borne de la proposition est obtenue par
$$\sum_{i=0}^dC_{n}^i \leq \sum_{i=0}^d {n^i\over i!} \leq \sum_{i=0}^dC_{d}^i\,n^i=(1+n)^d.$$
La preuve de la proposition~\ref{prop:sauer} est complète.
\end{proof}

Donnons quelques exemples de VC-dimension pour quelques dictionnaires simples de $\mX=\R^d$.
Les preuves sont laissées en exercice.

\begin{enonce*}[remark]{Exemple 1: classifieurs linéaires}
La VC-dimension de l'ensemble
\[
\cH=\ac{h(x)=\sign(\langle w,x\rangle):\|w\|=1}
\]
de classifieurs linéaires est $d$.
\end{enonce*}

\begin{enonce*}[remark]{Exemple 2: classifieurs affines}
La VC-dimension de l'ensemble
$$
\cH=\ac{h(x)=\sign(\langle w,x\rangle+b):\|w\|=1,\ b\in\R}
$$ de classifieurs affines est $d+1$.
\end{enonce*}

\begin{enonce*}[remark]{Exemple 3: classifieurs hyper-rectangulaires}
La VC-dimension de l'ensemble
$$
\cH=\ac{h(x)=2\,\1_{A}(x)-1:A\ \textrm{hyper-rectangle de}\ \R^d}
$$
de classifieurs hyper-rectangulaires est $2d$.
\end{enonce*}

\begin{enonce*}[remark]{Exemple 4: classifieurs à polygones convexes}
La VC-dimension de l'ensemble
$$
\cH=\ac{h(x)=2\,\1_{A}(x)-1:A\ \textrm{polygone convexe de}\ \R^d}
$$
de classifieurs par polygones convexes est $+\infty$ (prendre $n$ points sur la sphère unité : pour tout sous-ensemble de ces points, on peut prendre leur enveloppe convexe comme polygone convexe).
\end{enonce*}

\section{De la théorie vers la pratique}\label{sec:cvxERM}
\subsection{Convexification du risque empirique}
Les classifieurs par minimisation du risque empirique analysés précédemment possèdent de bonnes qualités statistiques, mais ils ne peuvent pas être mis en {\oe}uvre en pratique à cause de leur coût en temps de calcul. En effet, il n'existe pas de façon efficace de minimiser~\eref{erm} car ni $\cH$ ni $\hL_{n}$ ne sont convexes.
Un certain nombre des algorithmes de classification les plus populaires sont obtenus par une simple relaxation convexe du problème de minimisation~\eref{erm}.
La probabilité empirique de mauvaise classification $\hL_{n}$ est remplacée par un substitut convexe et l'ensemble des classifieurs $\cH$ est remplacé par un ensemble fonctionnel convexe $\F\subset \R^{\mX}$.


Considérons un ensemble convexe $\F$ de fonctions de $\mX$ dans $\R$. Une fonction $f\in\F$ n'est pas un classifieur, mais on peut l'utiliser pour classifier en étiquetant les points en fonction du signe de~$f$. En~d'autres mots, on peut associer à $f$ le classifieur $\sign(f)$. La probabilité empirique de mauvaise classification de ce classifieur peut être réécrite sous la forme
$$\hL_{n}(\sign(f))={1\over n}\sum_{i=1}^n\1_{\ac{Y_{i}\,\sign(f)(X_{i})<0}}={1\over n}\sum_{i=1}^n\1_{\ac{Y_{i}\,f(X_{i})<0}}.$$
Remplaçons maintenant la probabilité empirique de mauvaise classification $\hL_{n}$ par un substitut convexe se prêtant bien au calcul numérique. Un moyen simple et efficace d'obtenir un critère convexe est de remplacer la fonction de perte $z\to\1_{z<0}$ par une fonction convexe $z\to \ell(z)$.
Nous allons développer cette idée et considérer dans la suite les classifieurs obtenus par la procédure
\begin{multline}\label{classif:surrogate}
\hh_{\F}=\sign(\hf_{\F})\\[-5pt]
\textrm{où}\quad \hf_{\F}=\argmin_{f\in\F}\hL^{\ell}_{n}(f)\quad\textrm{avec}\quad
\hL^{\ell}_{n}(f)={1\over n}\sum_{i=1}^n\ell(Y_{i}\,f(X_{i})).
\end{multline}
Ce classifieur peut être calculé numériquement de façon efficace car à la fois $\F$ et $\hL^{\ell}_{n}$ sont convexes.
De nombreux classifieurs populaires sont obtenus en résolvant~\eref{classif:surrogate} pour des choix spécifiques de $\F$ et $\ell$, voir par exemple les parties~\ref{svm} et~\ref{boosting} pour quelques exemples.

\subsubsection*{Quelques fonctions de perte convexes $\ell$ classiques}
Il est naturel de considérer une fonction de perte $\ell$ qui est décroissante et positive. Habituellement, on demande aussi que $\ell(z)\geq \1_{z<0}$ pour tout $z\in\R$ car cela nous permet de donner une majoration de la probabilité de mauvaise classification, voir le théorème~\ref{thm:cvxIC}. Quelques fonctions de pertes classiques sont
\begin{itemize}
\item la perte exponentielle $\ell(z)=e^{-z}$
\item la perte logit $\ell(z)=\log_{2}(1+e^{-z})$
\item la perte hinge $\ell(z)=(1-z)_{+}$\quad (avec $(x)_{+}=\max(0,x)$)
\end{itemize}
voir la figure~\ref{fig:loss} pour un tracé de ces trois fonctions.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=8.5cm]{Loss}
\caption{\smaller \label{fig:loss} Tracé des pertes exponentielle, hinge et logit}
\end{center}
\end{figure}

\subsubsection*{Quelques exemples classiques d'ensembles fonctionnels $\F$}
Les principaux exemples classiques d'ensembles fonctionnels $\F$ peuvent être regroupés en deux classes.

Une première classe d'ensembles $\F$ est obtenue en prenant des combinaisons linéaires d'une famille finie
$\cH=\ac{h_{1},\ldots,h_{p}}$ de classifieurs
\begin{equation}\label{Fcvx}
\F=\bigg\{f:f(x)=\sum_{j=1}^p\beta_{j}h_{j}(x)\ \textrm{avec}\ \beta_{j}\in\mC\bigg\},
\end{equation}
où $\mC$ est un sous-ensemble convexe de $\R^p$. Des choix typiques pour~$\mC$ sont
\begin{itemize}
\item
le simplexe $\ac{\beta\in\R^p:\beta_{j}\geq 0,\ \sum_{j=1}^p\beta_{j}\leq 1}$,
\item
la boule
$\ac{\beta\in\R^p:|\beta|_{1}\leq R}$
\item
ou tout l'ensemble $\R^p$.
\end{itemize}
Ces choix apparaissent notamment dans les méthodes de \og boosting\fg, voir partie~\ref{boosting}. Les classifieurs de base $\ac{h_{1},\ldots,h_{p}}$ sont souvent appelés \emph{weak learners}.
Un choix populaire pour les weak learners est $h_{j}(x)=\sign(x_{j}-t_{j})$ avec $t_{j}\in\R$.


Un seconde classe classique d'ensembles $\F$
est obtenue en prenant une boule d'une espace de Hilbert à noyaux reproduisant (qu'on appelle RKHS, pour \emph{Reproducing Kernel Hilbert Space} en anglais). On renvoie à l'appendice~\ref{RKHS} pour une brève introduction aux RKHS. Plus précisément, considérons un RKHS $\F_{k}$ de noyau $k$ et notons par $\|f\|_{\F}$ la norme hilbertienne de $f\in\F_{k}$.
Pour alléger les notations, dans la suite on écrira simplement $\F$ pour $\F_{k}$.
Minimiser $\hL_{n}^{\ell}$ sur la boule
$\ac{f\in\F:\|f\|_{\F}\leq R}$
est équivalent à minimiser sur $\F$ le problème lagrangien dual
\begin{equation}\label{RKHS:lagrange}
\hf_{\F}=\argmin_{f\in\F}\widetilde L^{\ell}_{n}(f)\quad
\textrm{avec}\;\; \widetilde L_{n}^{\ell}(f)={1\over n}\sum_{i=1}^n\ell(Y_{i}\,f(X_{i}))+\lambda \|f\|_{\F}^2,
\end{equation}
pour un certain $\lambda>0$.
Ce type de classifieur apparaît notamment dans les algorithmes de type \emph{Support Vector Machine}, présentés partie~\ref{svm}.
Il s'avère que le minimiseur $\hf_{\F}$ de~\eref{RKHS:lagrange} est de la forme
\begin{equation}\label{ktrick}
\hf_{\F}=\sum_{i=1}^n\hbeta_{i}\,k(X_{i},.).
\end{equation}
En effet, notons $V$ l'espace linéaire engendré par $k(X_{1},.),\ldots,k(X_{n},.)$ et décomposons $f=f_{V}+f_{V^{\perp}}$ sur $V\oplus V^{\perp}$. Par la propriété de reproduction on a $f(X_{i})=\langle f,k(X_{i},.)\rangle_{\F}= \langle f_{V},k(X_{i},.)\rangle_{\F}=f_{V}(X_{i})$,
donc la formule de
Pythagore nous donne
$$\widetilde L_{n}^{\ell}(f_{V}+f_{V^{\perp}})={1\over n}\sum_{i=1}^n\ell\big(Y_{i}f_{V}(X_{i})\big)+\lambda \|f_{V}\|_{\F}^2+\lambda \|f_{V^{\perp}}\|_{\F}^2\,.$$
Comme $\lambda$ est strictement positif, tout minimiseur de $\hf$ de $\widetilde L_{n}^{\ell}$ doit satisfaire $\hf_{V^{\perp}}=0$,
donc il est de la forme~\eref{ktrick}. De plus, la propriété de reproduction nous assure de nouveau que $\langle k(X_{i},.),k(X_{j},.)\rangle_{\F}=k(X_{i},X_{j})$ donc
$$\bigg\|\sum_{j=1}^n\beta_{j}k(X_{j},.)\bigg\|^2_{\F}=\sum_{i,j=1}^n\beta_{i}\beta_{j}k(X_{i},X_{j}).$$
Le problème de minimisation~\eref{RKHS:lagrange} est donc équivalent à
\begin{multline}\label{RKHS:lagrange2}
\hf_{\F}=\sum_{j=1}^n\hbeta_{j}\,k(X_{j},.)\quad \textrm{avec}\\
\hbeta=\argmin_{\beta\in\R^n} \ac{{1\over n}\sum_{i=1}^n\ell\bigg(\sum_{j=1}^n\beta_{j}Y_{i}k(X_{j},X_{i})\bigg)+\lambda \sum_{i,j=1}^n\beta_{i}\beta_{j}k(X_{i},X_{j})}.
\end{multline}
Cette formulation est cruciale en pratique, car elle réduit le problème de minimisation infini-dimensionnel~\eref{RKHS:lagrange} à un problème de minimisation $n$-dimensionnel qui peut être résolu efficacement. Dans la partie~\ref{svm} sur les Support Vector Machines,
nous donnerons une description plus précise des solutions de ce problème lorsque $\ell$ est la perte Hinge.

\subsection{Propriétés statistiques}
Le classifieur $\hh_{\F}$ donné par~\eref{classif:surrogate} avec $\F$ et $\ell$ convexes
a l'avantage de se calculer facilement, mais a-t-il de bonnes propriétés statistiques?

\subsubsection*{Lien avec le classifieur de Bayes}
Le minimiseur du risque empirique~$\hh_{\cH}$ de la partie~\ref{sec:erm}
était un minimiseur de la version empirique de la probabilité de mauvaise classification $\p(Y\neq h(X))$ sur un ensemble $\cH$ de classifieurs.
La fonction $\hf_{\F}$ minimise à la place la version empirique de $\E\cro{\ell(Yf(X))}$ sur un ensemble fonctionnel $\F$. Le classifieur~$\hh_{\cH}$ peut donc être vu comme une version empirique du classifieur de Bayes $h_{*}$ qui minimise $\p(Y\neq h(X))$
sur l'ensemble des fonctions mesurables $h:\mX\to\ac{-1,+1}$, alors que la fonction $\hf_{\F}$ est une version empirique de la fonction $f_{*}^{\ell}$ qui minimise $\E\cro{\ell(Yf(X))}$ sur l'ensemble des fonctions mesurables $f:\mX\to\R$.
Une première étape est de comprendre le lien entre le classifieur de Bayes $h_{*}$ et le signe de la fonction~$f_{*}^{\ell}$.
Il s'avère que sous des hypothèses très faibles sur $\ell$, le signe de~$f_{*}^{\ell}$
coïncide exactement avec le classifieur de Bayes~$h_{*}$, donc $\sign(f_{*}^{\ell})$ minimise la probabilité de mauvaise classification $\p(Y\neq h(X))$. Démontrons maintenant ce résultat.


En conditionnant par $X$ on obtient
\begin{align*}
\E\bcro{\ell(Yf(X)}&=\E\bcro{\E\cro{\ell(Yf(X)|X}}\\
&=\E\Big[\ell(f(X))\p(Y\!=\!1|X)+\ell(-f(X))(1-\p(Y\!=\!1|X))\Big].
\end{align*}
Supposons que $\ell$ est décroissante, dérivable et strictement convexe (par exemple perte exponentielle ou logit).
En minimisant l'expression ci-dessus on obtient que $f_{*}^{\ell}(X)$ est solution de
$${\ell'(-f(X))\over\ell'(f(X))}={\p(Y=1|X)\over 1-\p(Y=1|X)}\,.$$
Comme $\ell$ est strictement convexe, on a $f(X)>0$ si et seulement si $\ell'(-f(X))/\ell'(f(X))>1$, donc
\begin{align*}
f_{*}^{\ell}(X)>0& \Longleftrightarrow \p(Y=1|X)>1/2 \\ &\Longleftrightarrow \E[Y|X]=2\p(Y=1|X)-1>0\,.
\end{align*}
Comme $h_{*}(X)\!=\!\sign(\E\cro{Y|X})$ (voir partie~\ref{sec:supervised1}), on obtient $\sign(f_{*}^{\ell}){=}\nobreak h_{*}$.
Cette égalité reste vraie pour la perte Hinge (exercice!).


Pour résumer la discussion ci-dessus, la fonction cible $f_{*}^{\ell}$ approchée par $\hf_{\F}$ est intéressante pour le problème de classification
car son signe coïncide avec le meilleur classifieur possible $h_{*}$.

\subsubsection*{Majoration de la probabilité de mauvaise classification}
Nous nous concentrons maintenant sur la probabilité de mauvaise classification
$L(\hh_{\F})$ du classifieur $\hh_{\F}=\sign(\hf_{\F})$ défini par~\eref{classif:surrogate}.
En pratique, il~est intéressant d'avoir une majoration de la probabilité de mauvaise classification $L(\hh_{\F})$
qui puisse être évaluée à partir des données. Le prochain théorème fournit une telle majoration pour des exemples typiques d'ensembles $\F$.

\begin{Thm}[Borne de confiance pour $L(\hh_{\F})$]\label{thm:cvxIC}
Pour tout $R>0$, on définit $\Delta\ell(R)=|\ell(R)-\ell(-R)|$.
On suppose que la fonction de perte $\ell$ est convexe, décroissante, positive, $\alpha$-Lipschitz sur $[-R,R]$ et vérifie $\ell(z)\geq \1_{z<0}$ pour tout $z$ dans $\R$. On s'intéresse au classifieur $\hh_{\F}$ défini par~\eref{classif:surrogate}.


{\bf (a)} Lorsque $\F$ est de la forme \eref{Fcvx} avec $\mC=\ac{\beta\in\R^p:|\beta|_{1}\leq R}$, nous avons avec probabilité au moins $1-e^{-t}$
\begin{equation}\label{IC:boosting}
L(\hh_{\F})\ \leq\ \hL^{\ell}_{n}(\hf_{\F})+2\alpha R\,\sqrt{2\log(2p)\over n}+\Delta\ell(R)\,\sqrt{t\over 2n} \,.
\end{equation}

{\bf (b)} Soit $\F$ une boule de rayon $R$ d'un RKHS de noyau $k$ vérifiant $k(x,x)\leq 1$ pour tout $x\in\mX$. Alors, avec probabilité au moins $1-e^{-t}$, on a
\begin{equation}\label{IC:svm}
L(\hh_{\F})\ \leq\ \hL^{\ell}_{n}(\hf_{\F})+{2\alpha R\over \sqrt{n}}+\Delta\ell(R)\,\sqrt{t\over 2n}\,.
\end{equation}
\end{Thm}

\begin{proof}
Commençons par prouver une majoration générale de $L(\hh_{\F})$ très similaire au théorème~\ref{thm:stocherror}.

\begin{lem}\label{lem31}
Supposons que $\sup_{f\in\F}|f(x)|\leq R<+\infty$. Alors pour toute fonction de perte $\ell$ vérifiant les hypothèses du théorème~\ref{thm:cvxIC}, on~a avec probabilité au moins $1-e^{-t}$
\begin{multline}\label{IC:radem}
L(\hh_{\F})\leq \hL^{\ell}_{n}(\hf_{\F})\\
+{2\alpha\over n}\ \max_{x\in\mX^n}\E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}f(x_{i})\bigg|}+\Delta\ell(R)\sqrt{t\over 2n}
\end{multline}
où $\sigma_{1},\ldots,\sigma_{n}$ sont des variables aléatoires i.i.d.\ de loi $\p_{\sigma}(\sigma_{i}=1)=\p_{\sigma}(\sigma_{i}=-1)=1/2$.
\end{lem}

\begin{proof}[\proofname\ du lemme \ref{lem31}]
La preuve de ce lemme repose sur exactement les mêmes arguments que la preuve du théorème~\ref{thm:stocherror}.
La première étape est de remarquer que l'inégalité $\ell(z)\geq \1_{z<0}$ pour tout réel $z$ nous donne
\begin{align*}
L(\hh_{\F})=\p(Y\hf_{\F}(X)<0)&\leq L^{\ell}(f)\ \quad\textrm{avec}\ L^{\ell}(f)=\E\cro{\ell(Yf(X))}\\
&\leq \hL^{\ell}_{n}(f)+\widehat \Delta_{n}^{\ell}(\F) \\
&\quad\quad\textrm{où}\ \widehat\Delta_{n}^{\ell}(\F)=\sup_{f\in\F}\big|\hL^{\ell}_{n}(f)-L^{\ell}(f)\big|.
\end{align*}
Comme dans le lemme~\ref{lem2}, l'inégalité de concentration de \hbox{McDiarmid} (théorème~\ref{McDiarmid} de l'appendice~\ref{App:concentration})
assure qu'avec probabilité au moins $1-e^{-t}$ on a
$$\widehat \Delta_{n}^{\ell}(\F)\leq \E\cro{\widehat \Delta_{n}^{\ell}(\F)}+\Delta\ell(R)\sqrt{t\over 2n}\,.$$
Pour conclure la preuve du lemme, il suffit de montrer que
\begin{equation}\label{eq:last}
\E\cro{\widehat \Delta_{n}^{\ell}(\F)}\leq {2\alpha\over n}\ \max_{x\in\mX^n}\E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}f(x_{i})\bigg|}.
\end{equation}
En suivant exactement les mêmes arguments que dans la preuve du lemme~\ref{lem3} (en remplaçant $\1_{Y_{i}\neq h(X_{i})}$ par $\ell(Y_{i}f(X_{i}))$) on obtient
$$\E\cro{\widehat \Delta_{n}^{\ell}(\F)}\leq {2\over n}\ \max_{y\in\ac{-1,+1}^n}\, \max_{x\in\mX^n}\,\E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}\ell(y_{i}f(x_{i}))\bigg|}.$$
Finalement, on utilise que $\ell$ est $\alpha$-Lipschitz pour conclure\,: le principe de Contraction (proposition~\ref{thm:contraction} de l'appendice~\ref{App:concentration}) nous donne
\begin{align*}
\E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}\ell(y_{i}f(x_{i}))\bigg|}&\leq \alpha\, \E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}y_{i}f(x_{i})\bigg|}\\
&=\alpha\, \E_{\sigma}\cro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}f(x_{i})\bigg|}.
\end{align*}
En combinant les deux dernières majorations on obtient~\eref{eq:last} et le lemme~\ref{lem31} est démontré.
\end{proof}


{\bf (a)} Prouvons maintenant la borne \eref{IC:boosting}. L'application $\beta\to \sum_{i=1}^n\sigma_{i}\sum_{j=1}^p\beta_{j}h_{j}(x_{i})$ est linéaire, donc elle atteint à l'un des sommets de $\mC$ son maximum et son minimum sur la boule $\mC$.
En conséquence, on a
$$\E_{\sigma}\bbcro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}f(x_{i})\bigg|}=R\,\E_{\sigma}\bbcro{\max_{j=1,\ldots,p}\bigg|\sum_{i=1}^n\sigma_{i}h_{j}(x_{i})\bigg|}.$$
En appliquant l'inégalité~\eref{eq:clefVapnik} avec
\[
\mV=\ac{(h_{j}(x_{1}),\ldots,h_{j}(x_{n})):j=1,\ldots,p},
\]
dont le cardinal est inférieur à $p$, on obtient
$$\E_{\sigma}\bbcro{\sup_{f\in\F}\bigg|\sum_{i=1}^n\sigma_{i}f(x_{i})\bigg|}\leq R\ \sqrt{2n\log(2p)}.$$
La borne~\eref{IC:boosting} découle du lemme~\ref{lem31}.

{\bf (b)} Démontrons maintenant la borne \eref{IC:svm}. On note $\|.\|_{\F}$ la norme dans le RKHS.
La formule de reproduction et l'inégalité de Cauchy-Schwarz nous donne
$$\Big|\sum_{i=1}^n\sigma_{i}f(x_{i})\Big|=\Big|\Big\langle f,\sum_{i=1}^n\sigma_{i}k(x_{i},.)\Big\rangle_{\F}\Big|\leq \|f\|_{\F}\Big\|\sum_{i=1}^n\sigma_{i}k(x_{i},.)\Big\|_{\F}\,.$$
En appliquant de nouveau l'inégalité de Cauchy-Schwarz, on obtient
\begin{eqnarray*}
\E_{\sigma}\Bcro{\sup_{\|f\|_{\F}\leq R}\Big|\textstyle\sum_{i=1}^n\sigma_{i}f(x_{i})\Big|}&\leq& R\ \E_{\sigma}\Bcro{\Big\|\textstyle\sum_{i=1}^n\sigma_{i}k(x_{i},.)\Big\|_{\F}}\\
&\leq& R\ \sqrt{\E_{\sigma}\Bcro{\Big\|\textstyle\sum_{i=1}^n\sigma_{i}k(x_{i},.)\Big\|_{\F}^2}}\\
&\leq& R\ \sqrt{\textstyle\sum_{i=1}^nk(x_{i},x_{i})\E_{\sigma}[\sigma_{i}^2]\,}\ \leq\ R\sqrt{n},
\end{eqnarray*}
où on a utilisé $k(x,x)\leq 1$ dans la dernière inégalité et \hbox{$\E\cro{\sigma_{i}\sigma_{j}}=0$} pour $i\neq j$ dans l'avant-dernière.
En combinant de nouveau la propriété de reproduction avec l'inégalité de Cauchy-Schwarz, on obtient
$$|f(x)|=|\langle f,k(x,.)\rangle_{\F}|\leq R \sqrt{k(x,x)}\leq R.$$
Le lemme~\ref{lem31} donne alors
$$L(\hh_{\F})\leq \hL^{\ell}_{n}(\hf_{\F})+{2\alpha R\over \sqrt{n}}+\Delta\ell(R)\sqrt{t\over 2n}\ ,$$
ce qui achève la preuve du théorème~\ref{thm:cvxIC}.
\end{proof}

Il est possible de démontrer des bornes de risque similaire à \eref{borneL} pour $L(\hh_{\cH})$, nous renvoyons à Bousquet, Boucheron et Lugosi~\cite{BBL} pour un panorama de tels résultats. Dans la dernière partie de ces notes, nous allons décrire deux algorithmes de classification très populaires: les Support Vector Machines et AdaBoost.

\subsection{Support Vector Machine}\label{svm}
Les Support Vector Machines (SVM) correspondent à l'estimateur~\eref{RKHS:lagrange} avec la perte Hinge $\ell(z)=(1-z)_{+}$.
La classification finale s'effectue avec $\hh_{\F}(x)=\sign(\hf_{\F}(x))$.
Nous allons donner une interprétation géométrique de la solution $\hf_{\F}$, interprétation qui est à l'origine du nom \og Support Vector Machine\fg.

\begin{propo}[Vecteurs supports]\label{prop:svm}
La solution de~\eref{RKHS:lagrange} avec $\ell(z)=(1-z)_{+}$ est de la forme $\hf_{\F}(x)=\sum_{i=1}^n\hbeta_{i}\,k(X_{i},x)$
avec
$$
\begin{cases}
\hbeta_{i}=0&\text{si }Y_{i}\hf_{\F}(X_{i})>1 \\
\hbeta_{i}=Y_{i}/(2\lambda n)&\text{si }Y_{i}\hf_{\F}(X_{i})<1\\
0\leq Y_{i}\hbeta_{i}\leq 1/(2\lambda n)&\text{si }Y_{i}\hf_{\F}(X_{i})=1\,.
\end{cases}$$
Les vecteurs $X_{i}$ d'indice $i$ tel que $\hbeta_{i}\neq 0$ sont appelés vecteurs supports.
\end{propo}

\begin{proof}
Notons $K$ la matrice $[k(X_{i},X_{j})]_{i,j=1,\ldots,n}$. Nous savons par~\eref{RKHS:lagrange2} que la solution de~\eref{RKHS:lagrange} est de la forme
\begin{align*}
\hf_{\F}&=\sum_{j=1}^n\hbeta_{j}\,k(X_{j},.)\\[-8pt]
\tag*{avec}
\hbeta&=\argmin_{\beta\in\R^n} \bigg\{{1\over n}\sum_{i=1}^n\big(1-Y_{i}[K\beta]_{i}\big)_{+}+\lambda \beta^TK\beta\bigg\}.
\end{align*}
Le problème de minimisation ci-dessus n'est pas régulier, donc on introduit des variables de relâchement $\widehat\xi_{i}=(1-Y_{i}[K\hbeta]_{i})_{+}$ et on reformule le problème de minimisation comme suit
\begin{equation}\label{slack:svm}
(\hbeta,\widehat \xi)=\argmin_{\substack{
\beta,\xi\in\R^n\ \textrm{tels que} \\
\xi_{i}\geq 1-Y_{i}[K\beta]_{i}\\
\xi_{i}\geq 0}}
\bigg\{{1\over n}\sum_{i=1}^n\xi_{i}+\lambda \beta^TK\beta\bigg\}.
\end{equation}
Ce problème est maintenant régulier et convexe et les conditions de Karush-Kuhn-Tucker pour le problème lagrangien dual
$$(\hbeta,\widehat \xi)=\argmin_{\beta,\xi\in\R^n}\bigg\{{1\over n}\sum_{i=1}^n\xi_{i}+\lambda \beta^TK\beta-\sum_{i=1}^n\big(
\alpha_{i}(\xi_{i}-1+Y_{i}[K\beta]_{i})+\gamma_{i}\xi_{i} \big)\bigg\}.$$
donnent les formules
\begin{align*}
\tag*{conditions de $1^{\textrm{er}}$ ordre:}& 2\lambda [K\hbeta]_{j}=\sum_{i=1}^nK_{ij}\alpha_{i}Y_{i}\quad\textrm{et}\quad\alpha_{j}+\gamma_{j}={1\over n},\\
\tag*{conditions de relâchement:}& \min(\alpha_{i},\widehat\xi_{i}-1+Y_{i}[K\hbeta]_{i})=0\quad\textrm{et}\quad \min(\gamma_{i},\widehat \xi_{i})=0.
\end{align*}
On déduit de la première condition de premier ordre que $\hbeta_{i}=\alpha_{i}Y_{i}/(2\lambda)$. Comme $\hf_{\F}(X_{i})=[K\hbeta]_{i}$,
la première condition de relâ\-chement donne $\hbeta_{i}=0$ si $Y_{i}\hf_{\F}(X_{i})>1$.
La seconde condition de relâ\-chement couplée à la seconde condition de premier ordre implique que $\hbeta_{i}=Y_{i}/(2\lambda n)$ si $\widehat\xi_{i}>0$ et $0\leq Y_{i}\hbeta_{i}\leq 1/(2\lambda n)$ sinon.
Pour conclure la preuve de la proposition, on remarque que lorsque que $\widehat\xi_{i}>0$ on a $\hbeta_{i}$ et $\alpha_{i}$ non nuls, et donc $Y_{i}\hf_{\F}(X_{i})=1-\widehat\xi_{i}<1$
vu la première condition de relâchement.
\end{proof}

Interprétons géométriquement la proposition~\ref{prop:svm}.

\subsubsection*{Interprétation géométrique\,: noyau linéaire}
\begin{figure}
\begin{center}
\includegraphics[width=4.5cm]{2}
\caption{\smaller \label{fig:svm} Classification par un SVM linéaire: l'hyperplan frontière $\ac{x\in\R^d: \langle \widehat w,x\rangle=0}$
est représenté en noir, les hyperplans de marge $\ac{x\in\R^d: \langle \widehat w,x\rangle=+1}$ et \hbox{$\ac{x\in\R^d: \langle \widehat w,x\rangle=-1}$}
sont représentés en pointillés bleus et rouges respectivement. Les vecteurs supports sont représentés par des carrés.}
\end{center}
\end{figure}
Considérons le noyau le plus simple $k(x,y)=\langle x,y\rangle$ pour tout $x,y\in\R^d$. Le RKHS associé est l'espace des formes linéaires $\F=\ac{\langle w,.\rangle:w\in\R^d}$.
Dans ce cas\vspace*{-3pt}
$$\hf_{\F}(x)=\sum_{i=1}^n\hbeta_{i}\langle X_{i},x\rangle=\langle \widehat w,x\rangle\quad\textrm{avec}\quad \widehat w=\sum_{i=1}^n\hbeta_{i} X_{i}\,,$$
donc le classifieur $\hh_{\F}(x)=\sign(\langle \widehat w,x\rangle)$
classe les points en fonction de leur position par rapport à l'hyperplan $\ac{x\in\R^d: \langle \widehat w,x\rangle=0}$.
La normale à l'hyperplan $\widehat w$ est une combinaison linéaire des vecteurs supports, qui sont les points $X_{i}$ tels que $Y_{i}\langle \widehat w,X_{i}\rangle\leq 1$. Ils sont représentés par des carrés sur la figure~\ref{fig:svm}.
Les hyperplans\vspace*{-3pt}\enlargethispage{.5\baselineskip}
\[
\ac{x\in\R^d: \langle \widehat w,x\rangle=+1}\quand\ac{x\in\R^d: \langle \widehat w,x\rangle=-1}
\]
sont habituellement appelés hyperplans de marge.
Pour finir, notons la propriété suivante des SVM. Si on ajoute à l'ensemble d'apprentissage $(X_{i},Y_{i})_{i=1,\ldots,n}$ un point $X_{n+1}$ vérifiant $Y_{n+1}\langle \widehat w,X_{n+1}\rangle> 1$,
alors le vecteur $\widehat w$ et le classifieur $\hh_{\F}$ ne changent pas. En d'autres mots, seules les données mal classifiées ou classifiées avec une marge insuffisante (i.e.\ $Y_{i}\langle \widehat w,X_{i}\rangle\leq 1$)
influencent l'hyperplan frontière \hbox{$\ac{x\in\R^d: \langle \widehat w,x\rangle=0}$}.

\subsubsection*{Interprétation géométrique\,: noyau défini positif quelconque}
Notons par $\phi:\mX\to\F$ l'application $\phi(x)=k(x,.)$.
La propriété de reproduction combinée à la proposition~\ref{prop:svm} nous donne\vspace*{-3pt}
$$\hf_{\F}(x)=\langle \hf_{\F},\phi(x)\rangle_{\F}=\bigg\langle \sum_{i=1}^n\hbeta_{i}\phi(X_{i}),\phi(x)\bigg\rangle_{\F}.$$
Un point $x\in\mX$ est classifié selon le signe du produit scalaire ci-dessus. En conséquence, les points $\phi(x)\in\F$
sont classifiés selon le classifieur linéaire sur $\F$\vspace*{-3pt}
$$f\mto\sign\left(\langle \widehat w_{\phi},f\rangle_{\F}\right)\quad\textrm{où}\ \widehat w_{\phi}=\sum_{i=1}^n\hbeta_{i}\phi(X_{i}).$$
La frontière $\big\{x\in\mX:\hf_{\F}(x)=0\big\}$ du classifieur $\hh_{\F}$
est donc l'image réciproque par $\phi$ de l'hyperplan $\ac{f\in\F:\langle \widehat w_{\phi},f\rangle_{\F}=0}$, comme repré\-senté figure~\ref{fig:ksvm}.
\begin{figure}
\begin{center}
\includegraphics[scale=.5]{3}
\caption{\smaller \label{fig:ksvm} Classification avec un noyau non linéaire: la classification linéaire dans $\F$ produit une classification non linéaire dans $\mX$ via l'image réciproque de $\phi$.}
\end{center}
\end{figure}
Nous observons que le noyau $k$ délinéarise le~SVM, dans le sens où il produit un classifieur non linéaire $\hh_{\F}$
pour le même coût numérique qu'un classifieur linéaire dans $\R^n$.


Vous pouvez observer les SVM à l'\oe uvre avec la petite démo:\\*
\url{http://svm.cs.rhul.ac.uk/pagesnew/GPat.shtml}

\subsubsection*{Pourquoi les RKHS sont-ils utiles ?}
Il y a principalement deux raisons pour utiliser un RKHS. La première raison est de permettre de délinéariser un algorithme en envoyant
$\mX$ dans $\F$ avec $\phi:x\to k(x,.)$,
comme représenté dans la figure~\ref{fig:ksvm}. Cela permet d'obtenir un algorithme non linéaire pour un coût similaire à celui d'un algorithme linéaire.

La seconde raison pour utiliser un RKHS est de pouvoir employer sur n'importe quel ensemble $\mX$ des algorithmes définis pour des vecteurs. Imaginons par exemple qu'on veuille classifier des protéines ou des molécules en fonction de leur propriétés thérapeutiques. Notons par $\mX$ notre ensemble de molécules. Pour tout $x,y\in\mX$, représentons par $k(x,y)$ leur similarité (selon des critères à définir).
Si le noyau résultant $k:\mX\times\mX\to\R$ est défini positif, on peut alors directement appliquer un SVM pour les classifier, comme illustré figure~\ref{fig:vectoralize}.
\begin{figure}
\begin{center}
\includegraphics[scale=.5]{4}
\caption{\smaller \label{fig:vectoralize} Classification de molécules à l'aide d'un SVM.}
\vspace*{-.7\baselineskip}
\end{center}
\end{figure}
Bien sûr, le point clef dans ce cas est de construire le noyau~$k$. En général, le noyau $k(x,y)$
est défini en fonction de certaines propriétés de $x,y$ qui sont connues pour avoir de l'importance pour le problème de classification. Par exemple, le nombre de courtes séquences communes est un indice utile pour quantifier la similarité entre deux protéines.
La~complexité du calcul de $k(x,y)$ est aussi un critère crucial pour les applications sur des données complexes. Nous renvoyons aux excellents slides de Jean-Philippe Vert pour la description d'applications prometteuses en biologie et médecine:\\*
\url{https://members.cbio.mines-paristech.fr/~jvert/talks/120302ensae/ensae.pdf}

\subsection{AdaBoost}\label{boosting}
AdaBoost est un algorithme qui tend à calculer une solution approximative de l'estimateur~\eref{classif:surrogate} avec la perte exponentielle $\ell(z)=\nobreak e^{-z}$ et l'espace fonctionnel $\F=\textrm{span}\ac{h_{1},\ldots,h_{p}}$ où $h_{1},\ldots,h_{p}$ sont $p$ classifieurs donnés.


Le principe de l'algorithme AdaBoost est de réaliser une minimisation dite agressive de~\eref{classif:surrogate}.
Plus précisément, AdaBoost produit une suite de fonctions $\hf_{m}$ pour $m=0,\ldots,M$ en partant de $\hf_{0}=0$ puis en résolvant récursivement
pour $m=1,\ldots,M$\vspace*{-3pt}
\begin{multline*}
\hf_{m} = \hf_{m-1}+\beta_{m}h_{j_{m}}\\[-7pt] \textrm{où}\quad (\beta_{m},{j_{m}})=\argmin_{\substack{j=1,\ldots,p\\ \beta\in\R}}{1\over n}\sum_{i=1}^n\exp\left(-Y_{i}\big(\hf_{m-1}(X_{i})+\beta h_{j}(X_{i})\big)\right).
\end{multline*}
La classification finale est effectuée à l'aide de $\hh_{M}(x)=\sign(\hf_{M}(x))$ qui est une approximation de $\hh_{\cH}$ défini par~\eref{classif:surrogate}.

La perte exponentielle permet de calculer $(\beta_{m},{j_{m}})$ très efficacement. En effet, en posant
$w_{i}^{(m)}=n^{-1}\exp(-Y_{i}\hf_{m-1}(X_{i}))$, on peut écrire\vspace*{-3pt}
\begin{multline*}
{1\over n}\sum_{i=1}^n\exp\left(-Y_{i}\big(\hf_{m-1}(X_{i})+\beta h_{j}(X_{i})\big)\right)\\[-7pt]
=(e^{\beta}-e^{-\beta})\sum_{i=1}^nw_{i}^{(m)}{\bf 1}_{h_{j}(X_{i})\neq Y_{i}}+e^{-\beta}\sum_{i=1}^nw_{i}^{(m)}.
\end{multline*}
Lorsque la condition suivante
$$ \textrm{err}_{m}(j)= {\sum_{i=1}^nw_{i}^{(m)}{\bf 1}_{h_{j}(X_{i})\neq Y_{i}} \over \sum_{i=1}^nw_{i}^{(m)}}\,\leq\, {1\over 2}\quad \textrm{pour tout}\ j=1,\ldots,p,$$
est satisfaite, les minimiseurs $(\beta_{m},{j_{m}})$ sont donnés par
$${j_{m}}=\argmin_{j=1,\ldots,p} \textrm{err}_{m}(j)\quad\textrm{et}\quad
\beta_{m}={1\over 2}\log\left({1-\textrm{err}_{m}({j_{m})}\over \textrm{err}_{m}({j_{m}})}\right).$$
En remarquant que $-Y_{i}h(X_{i})=2{\bf 1}_{Y_{i}\neq h(X_{i})}-1$
on obtient la formulation standard de l'algorithme AdaBoost.

\smallskip
\begin{center}
\begin{minipage}{0.8\textwidth}
\boxed{\textbf{\large AdaBoost}}
\vspace{-0.05cm}

\begin{tabular}{|p{\textwidth}|}\hline
{\bf Init:} $w_{i}^{(1)}=1/n$, for $i=1,\ldots,n$\\
{\bf Iterate:} For $m=1,\ldots,M$ do
\begin{eqnarray*}
{j_{m}}&=&\argmin_{j=1,\ldots,p} \textrm{err}_{m}(j)\\
2\beta_{m}&=&\log({1-\textrm{err}_{m}({j_{m})})-\log(\textrm{err}_{m}({j_{m}})})\\
w_{i}^{(m+1)}&=&w_{i}^{(m)}\exp(2\beta_{m}{{\bf 1}_{h_{j_{m}}(X_{i})\neq Y_{i}}}),\quad \textrm{for}\ i=1,\ldots,n\\
\textrm{STOP}&\textrm{if}& \min_{j=1,\ldots,p} \textrm{err}_{m+1}(j)>1/2
\end{eqnarray*}
{\bf Output:} $\hf_{M}(x)=\sum_{m=1}^M \beta_{m}h_{j_{m}}(x).$
\\\hline
\end{tabular}
\end{minipage}
\end{center}
\smallskip

On remarque que l'algorithme AdaBoost donne de plus en plus de poids dans $\textrm{err}_{m}(j)$ aux points $X_{i}$
qui sont mal classifiés à l'étape $m$.

Vous pouvez observer AdaBoost à l'\oe uvre (pour des classifieurs~$h_{j}$ par demi-espaces) avec l'application récréative:\\*
\url{http://cseweb.ucsd.edu/~yfreund/adaboost/}

\section{Pour aller au-delà de cette introduction}
Nous renvoyons
le lecteur intéressé à aller au-delà des concepts présentés dans ces notes à l'article de synthèse de Boucheron, Bousquet et Lugosi~\cite{BBL}. Cet article comprend notamment une bibliographie assez exhaustive. D'un point de vue plus pratique et appliqué, l'incontournable livre de
Hastie, Tibshirani et Friedman~\cite{ESL} décrit et discute de très nombreux algorithmes opérationnels. Enfin, nous soulignons que les concepts introduits ici apparaissent aussi pour le problème de \emph{ranking} (ordonner au mieux des données, l'exemple le plus célèbre étant les moteurs de recherche sur internet), voir Clémençon, Lugosi et Vayatis~\cite{ranking}.

%%%%%%%%%%%%%%
\appendix
\section{Espace de Hilbert à noyaux reproduisants (RKHS)}\label{RKHS}
Les espaces de Hilbert à noyaux reproduisants, dit \emph{Reproducing Kernel Hilbert Spaces} (RKHS) en anglais,
sont des espaces de \hbox{Hilbert} fonctionnels dont la norme décrit la régularité des fonctions.
Les RKHS vérifient aussi une propriété de reproduction particulière, qui s'avère cruciale en pratique car elle permet une mise \oe uvre numérique efficace.

Une fonction $k:\mX\times \mX\to \R$
est dite définie positive si elle est symétrique ($k(x,y)=k(y,x)$ pour tout $x,y\in\mX$) et si pour tout $N\in\N$, $x_{1},\ldots,x_{N}\in\mX$ et $a_{1},\ldots,a_{N}\in\R$ on a
\begin{equation}\label{eq:pd}
\sum_{i,j=1}^{N}a_{i}a_{j}k(x_{i},x_{j})\geq 0.
\end{equation}


\begin{enonce*}[remark]{Exemples de noyaux définis positifs:}\mbox{}
\begin{itemize}
\item noyau linéaire: $k(x,y)=\langle x,y\rangle$
\item noyau gaussien: $k(x,y)=e^{-\|x-y\|^2/2\sigma^2}$
\item noyau histogramme ($d=1$): $k(x,y)=\min(x,y)$
\item noyau exponentiel: $k(x,y)=e^{-\|x-y\|/\sigma}$
\end{itemize}
\end{enonce*}

On peut associer à un noyau défini positif $k$ un sous-espace de Hilbert $\F$ de $\R^{\mX}$ appelé espace de Hilbert de noyau reproduisant $k$.

\begin{propo}[Espace de Hilbert à noyau reproduisant (RKHS)]\label{prop:RKHS}
À tout noyau défini positif $k$ sur $\mX$, on peut associer un (unique) espace de Hilbert $\F\subset \R^\mX$ vérifiant
\begin{itemize}
\item $k(x,.)\in\F$ pour tout $x\in\mX$
\item \emph{propriété de reproduction:} $f(x)=\langle f,k(x,.)\rangle_{\F}$ pour tout $x\in\mX$ et $f\in\F$.
\end{itemize}
L'espace $\F$ est appelé espace de Hilbert de noyau reproduisant $k$.
\end{propo}

\begin{proof}
Considérons l'espace linéaire $\F_{0}$ engendré par la famille $\ac{k(x,.):x\in\mX}$
\begin{multline*}
\F_{0}=\bigg\{f:\mX\to \R: f(x)=\sum_{i=1}^Na_{i}k(x_{i},x),\ N\in\N,
\\[-8pt] x_{1},\ldots,x_{N}\in\mX,\ a_{1},\ldots,a_{N}\in \R\bigg\}.
\end{multline*}
À tout $f=\sum_{i=1}^{N}a_{i}k(x_{i},.)$ et $g=\sum_{j=1}^{M}b_{j}k(y_{j},.)$ on associe
$$\langle f,g \rangle_{\F_{0}}:= \sum_{i=1}^N\sum_{j=1}^Ma_{i}b_{j}k(x_{i},y_{j})=\sum_{i=1}^Na_{i}g(x_{i})=\sum_{j=1}
^Mb_{j}f(y_{j}).$$
Les deux dernières égalités indiquent que $\langle f,g \rangle_{\F_{0}}$
ne dépend pas du choix de la décomposition de $f$ et $g$, donc cette quantité est bien définie. De plus, l'application $(f,g)\to\langle f,g\rangle_{\F_{0}}$ est bilinéaire, symétrique, positive (vu~\eref{eq:pd}) et on a la propriété de reproduction
$$f(x)=\langle f,k(x,.)\rangle_{\F_{0}}\quad\textrm{pour tout}\ x\in\mX\quad \textrm{et}\ f\in\F_{0}.$$
L'inégalité de Cauchy-Schwarz $\langle f,g \rangle_{\F_{0}}\leq \|f\|_{\F_{0}} \|g\|_{\F_{0}}$ combinée à la formule de reproduction donne
\begin{equation}\label{eq:CS}
|f(x)|\leq \sqrt{k(x,x)}\ \|f\|_{\F_{0}}.
\end{equation}
En conséquence $\|f\|_{\F_{0}}=0$ implique $f=0$ donc $\langle f,g \rangle_{\F_{0}}$ est un produit scalaire. L'espace $\F_{0}$
est donc un espace pré-hilbertien et pour obtenir $\F$ il nous suffit de le compléter. Considérons deux suites $(x_{i})\in\mX^{\N}$ et $(a_{i})\in\R^{\N}$ vérifiant $\sum_{i,j\geq 1}a_{i}a_{j}k(x_{i},x_{j})<+\infty$. L'inégalité~\eref{eq:CS} nous assure que pour tout $M<N$ et $x\in\mX$ on a
$$\Big|\sum_{i=M+1}^Na_{i}k(x_{i},x)\Big|\leq \sqrt{k(x,x)}\ \sum_{i,j=M+1}^{N}a_{i}a_{j}k(x_{i},x_{j}).$$
Lorsque $\sum_{i,j\geq 1}a_{i}a_{j}k(x_{i},x_{j})$ est fini, le membre de droite tend vers 0 lorsque $M,N$ tendent vers l'infini, donc les séries partielles $\sum_{i=1}^Na_{i}k(x_{i},x)$ sont de Cauchy et convergent lorsque $N\to\infty$.
On~peut donc définir l'espace\vspace*{-3pt}
\begin{multline*}
\F=\Bigl\{f:\mX\to \R: f(x)=\sum_{i=1}^{\infty}a_{i}k(x_{i},x),\ (x_{i})\in\mX^{\N},\\[-8pt]
(a_{i})\in\R^{\N},\ \sum_{i,j\geq 1}a_{i}a_{j}k(x_{i},x_{j})<+\infty\Bigr\}
\end{multline*}
et la forme bilinéaire\vspace*{-3pt}
$$\langle f,g \rangle_{\F}:= \sum_{i,j=1}^{\infty}a_{i}b_{j}k(x_{i},y_{j})=\sum_{i=1}^{\infty}a_{i}g(x_{i})=\sum_{j=1}
^{\infty}b_{j}f(y_{j})$$
pour $f=\sum_{i=1}^{\infty}a_{i}k(x_{i},.)$ et $g=\sum_{j=1}^{\infty}b_{j}k(y_{j},.)$.
Exactement comme précédemment, l'application $(f,g)\to\langle f,g\rangle_{\F}$ est un produit scalaire vérifiant la propriété de reproduction\vspace*{-3pt}
$$f(x)=\langle f,k(x,.)\rangle_{\F}\quad\textrm{pour tout}\ x\in\mX\ \textrm{et}\ f\in\F.$$
Finalement, l'espace $\F$ muni du produit scalaire $\langle.,.\rangle_{\F}$ est la complétion dans $\R^{\mX}$ de $\F_{0}$ muni de $\langle.,.\rangle_{\F_{0}}$, donc c'est un espace de Hilbert à noyau reproduisant.
\end{proof}

La norme d'une fonction $f$ dans un RKHS $\F$ est fortement reliée à la régularité de $f$.
Cette propriété apparaît clairement dans l'inégalité\vspace*{-3pt}
$$|f(x)-f(x')| = |\langle f,k(x,.)-k(x',.)\rangle_{\F}|\leq \|f\|_{\F}\ \|k(x,.)-k(x',.)\|_{\F}.$$
Nous illustrons ce point en décrivant le RKHS associé aux noyaux histogrammes et gaussiens.

\begin{enonce*}[remark]{Exemple 1: RKHS associé au noyau histogramme}
L'espace de Sobolev\vspace*{-3pt}
\begin{multline*}
\F=\Big\{f\in C([0,1],\R): f\ \textrm{est p.p. différentiable}\\[-8pt]
\text{avec}\ f'\in L^2([0,1])\ \textrm{et}\ f(0)=0\Big\}
\end{multline*}
muni du produit scalaire $\langle f,g\rangle_{\F}=\int_{0}^1f'g'$
est un RKHS de noyau reproduisant $k(x,y)=\min(x,y)$ sur $[0,1]$. En effet, $k(x,.)\in\F$ pour tout $x\in[0,1]$ et
$$f(x)=\int_{0}^1f'(y){\bf 1}_{y\leq x}\,dy=\langle f,k(x,.)\rangle_{\F}\,,\ \textrm{pour tout}\ f\in\F\ \textrm{et}\ x\in[0,1].$$
Dans ce cas, la norme $\|f\|_{\F}$ correspond simplement à la norme $L^2$ de la dérivée de $f$.
Plus cette norme est petite, plus $f$ est régulière.
\end{enonce*}

\begin{enonce*}[remark]{Exemple 2: RKHS associé au noyau gaussien}
Notons par ${\bf F}[f]$ la transformée de Fourier dans $\R^d$ de normalisation
\begin{multline*}
{\bf F}[f](\omega)={1\over (2\pi)^{d/2}}\int_{\R^d}f(t)e^{-{\bf i}\langle \omega,t\rangle},\\[-8pt] \textrm{pour}\ f\in L^1(\R^d)\cap L^2(\R^d)\ \textrm{et}\ \omega\in\R^d.
\end{multline*}
Pour tout $\sigma>0$, l'espace fonctionnel
$$\F_{\sigma}=\bigg\{f\in C_{0}(\R^d)\cap L^1(\R^d)\ \textrm{tel que} \int_{\R^d}\big|{\bf F}[f](\omega)\big|^2e^{\sigma|\omega|^2/2}\,d\omega<+\infty\bigg\},$$
muni du produit scalaire
\[
\langle f,g\rangle_{\F_{\sigma}}=(2\pi\sigma^2)^{-d/2}\int_{\R^d}\overline{{\bf F}[f](\omega)}{\bf F}[g](\omega)e^{\sigma|\omega|^2/2}\,d\omega
\]
est un RKHS associé au noyau gaussien
\[
k(x,y)=\exp(-\|y-x\|^2/2\sigma^2).
\]
En effet, pour tout $x\in\R^d$ la fonction $k(x,.)$ appartient à $\F_{\sigma}$
et un calcul direct donne
$$\langle k(x,.),f\rangle_{\F_{\sigma}}={\bf F}^{-1}\big[{\bf F}[f]\big](x)=f(x)\quad\textrm{pour tout}\ f\in\F\ \textrm{et}\ x\in \R^d.$$
L'espace $\F_{\sigma}$ est composé de fonctions très régulières et la norme $\|f\|_{\F_{\sigma}}$
contrôle directement la régularité de $f$. Remarquons que lorsque
$\sigma$ augmente l'espace $\F_{\sigma}$ rétrécit pour ne contenir que des fonctions de plus en plus régulières.
\end{enonce*}

\section{Inégalités probabilistes}\label{App:concentration}
Les analyses non asymptotiques en apprentissage statistique reposent très souvent sur l'inégalité de concentration de McDiarmid~\cite{McDiarmid}.

\begin{Thm}[McDiarmid (1989)]\label{McDiarmid}
Soit $\mX$ un ensemble mesurable et considérons $F:\mX^n\to \R$ telle qu'il existe $\delta_{1},\ldots,\delta_{n}$ vérifiant
$$\big|F(x_{1},\ldots,x'_{i},\ldots,x_{n})-F(x_{1},\ldots,x_{i},\ldots,x_{n})\big|\leq \delta_{i},$$
pour tout $x_{1},\ldots,x_{n},x'_{i}\in\mX$, pour $i=1,\ldots,n$. Alors, pour tout $t>0$ et pour toutes variables indépendantes $X_{1},\ldots,X_{n}$, on a
$$\p\big(F(X_{1},\ldots,X_{n})>\E\cro{F(X_{1},\ldots,X_{n})}+t\big)\leq \exp\pa{-{2t^2\over \delta_{1}^2+\ldots+\delta_{n}^2}}.$$
\end{Thm}

Nous renvoyons le lecteur au Chapitre 9 du livre de Devroye, Györfi et Lugosi~\cite{bookPattern}
pour la preuve classique de ce résultat, preuve qui combine simplement l'inégalité de Markov avec un argument martingale (par conditionnements télescopiques). Une preuve plus conceptuelle basée sur la méthode d'entropie est donnée dans le livre de Boucheron, Lugosi et Massart~\cite{bookBLM}, Chapitre~6.

Un second concept important en apprentissage statistique est le principe de contraction.

\begin{Thm}[Principe de contraction]\label{thm:contraction}
Soit $\mathcal Z$ un sous-ensemble borné de $\R^n$ et $\varphi:\mathcal \R \to \R$ une fonction $\alpha$-Lipschitz vérifiant $\varphi(0)=0$. Pour des variables aléatoires $\sigma_{1},\ldots,\sigma_{n}$ i.i.d.\ de loi
\[
\p_{\sigma}(\sigma_{i}=1)=\p_{\sigma}(\sigma_{i}=-1)=1/2,
\]
nous avons
$$\E_{\sigma}\Bcro{\sup_{z\in\mathcal Z}\Big|\sum_{i=1}^n\sigma_{i}\varphi(z_{i})\Big|}\leq \alpha\, \E_{\sigma}\Bcro{\sup_{z\in\mathcal Z}\Big|\sum_{i=1}^n\sigma_{i}z_{i}\Big|}.$$
\end{Thm}

Un preuve concise est donnée dans le Chapitre 11 du livre de Boucheron, Lugosi et Massart~\cite{bookBLM}.

\backmatter
\bibliographystyle{jepplain+eid}
\bibliography{xups13-02}
\end{document}