\chapter{Modèles discriminants}
\label{ch:discriminant}



La conception de modèles discriminants, dont le but est de trouver l'association entre les observations et leurs étiquettes de sortie sans faire d'hypothèse distributionnelle sur la génération des données, a été le précurseur dans le développement d'algorithmes de classification et de régression. 

Un modèle discriminant construit une fonction de prédiction\index{fonction!de prédiction} à partir d'un ensemble fini d'exemples, appelé base d'entraînement ou base d'apprentissage\index{base!d'entraînement}\index{training set|see{base d'entraînement}} \citep{fukunaga:1972, duda:2001, scholkopf:2001, boucheron:2005}. Suivant le cadre supervisé\index{apprentissage!supervisé}, chaque exemple est un couple constitué généralement du vecteur représentatif d'une observation et de sa réponse associée (aussi appelée sortie désirée\index{sortie désirée}\index{desired output|see{sortie désirée}}). Le but de l'apprentissage est d'induire une fonction qui prédise les réponses associées à de nouvelles observations en commettant une erreur de prédiction \index{erreur!de généralisation}  aussi faible possible. Cette réponse est généralement une valeur réelle ou une étiquette de classe, comme nous allons le voir dans la suite. L'hypothèse sous-jacente ici est que les données sont stationnaires, c'est-à-dire que les exemples de la base d'entraînement, sur laquelle la fonction de prédiction est apprise, sont en quelque sorte représentatifs du problème général que l'on souhaite résoudre. Nous allons revenir sur cette hypothèse dans la section suivante. 

En pratique, parmi une classe de fonctions \index{classe de fonctions}existante, le modèle d'apprentissage choisit celle qui réalise la plus faible erreur moyenne de prédiction (ou erreur empirique\index{erreur!empirique}) sur une base d'entraînement. La fonction d'erreur\index{fonction!d'erreur} quantifie le désaccord entre la prédiction de sortie donnée par la fonction que l'on souhaite apprendre pour une observation de la base d'entraînement et sa réponse associée. Le but de cette recherche n'est pas que le modèle d'apprentissage induise une fonction donnant exactement les sorties désirées des observations de la base d'entraînement (ou faire du surapprentissage\index{surapprentissage}), mais de trouver, comme nous venons de l'évoquer, la fonction qui aura de bonnes performances de généralisation. 


En logique, ce raisonnement ou procédé de recherche d'une règle générale à partir d'un ensemble d'observations fini est appelé induction\index{induction} \cite[chapitre~7, pp.161-176]{genesereth:1987}\footnote{Le raisonnement contraire, appelé  déduction\index{déduction}, se base, quant à lui, sur des axiomes et produit des règles spécifiques (qui sont toujours vraies) comme des conséquences de la loi.}. En apprentissage automatique, le cadre inductif a été mis en place suivant le principe de la minimisation du risque empirique (MRE), (ou \textit{Empirical Risk Minimisation})\index{minimisation du risque!empirique}\index{empirical risk minimization|see{minimisation du risque empirique}}   et ses propriétés statistiques ont été étudiées dans la théorie développée par \citet{vapnik:1999}. Le lecteur intéressé par ces concepts est renvoyé à l'ouvrage \citet{amini:2015} qui les explique de façon détaillée dans un contexte plus général de l'apprentissage inductif.

Dans ce chapitre, nous allons nous intéresser au cadre de la classification, dont le but est d'apprendre une fonction de prédiction pour affecter des étiquettes de classes aux observations suivant les paradigmes supervisé et semi-supervisé. Nous allons commencer notre exposé par présenter en détail quelques  modèles de classification bi-classes et multi-classes conventionnels  (section \ref{sec:sup}). Dans la section \ref{sec:semisup}, nous présentons ensuite le paradigme de l'apprentissage semi-supervisé\index{apprentissage!semi-supervisé} en décrivant les approches classiques développées suivant ce paradigme.

\section{Approches supervisées}
\label{sec:sup}
La conception d'algorithmes de classification binaires et multi-classes, dont le but est d'affecter des étiquettes de classes à des observations, a été le précurseur dans le développement d'algorithmes d'apprentissage plus complexes. L'étude des modèles développés dans ce contexte aide ainsi à mieux comprendre le fonctionnement général des algorithmes supervisés et à faire le lien avec la théorie développée par  \citet{vapnik:1999}, ce qui est le but de ce chapitre.

\subsection{Modèles binaires}

\subsubsection{Régression logistique}
\index{régression!logistique}\index{logistic regression|see{régression}}La discrimination (ou \emph{régression}) logistique\index{discrimination logistique|see{régression logistique}} a été introduite par les statisticiens vers la fin des années soixante \citep{truett:1967} et a été popularisée ensuite par \cite{anderson:1982}. Il s'agit d'une tentative pour s'affranchir des hypothèses restrictives souvent associées aux méthodes linéaires paramétriques\index{méthode!linéaire paramétrique} \citep{duda:2001}. La seule hypothèse qui soit faite dans ce cas est que le logarithme des rapports de probabilités conditionnelles des classes pour une entrée $\obs$ soit linéaire par rapport à $\obs$, ce qui, dans le cas d'un problème de classification à deux classes se traduit par\footnote{Dans la version originale, les sorties désirées sont binaires, $0$ ou $1$.}  :
\begin{equation}
\label{CondRegLog}
\ln\left(\frac{\mathbb{P}(X=\obs\mid Y=1)}{\mathbb{P}(X=\obs\mid Y=-1)}\right)=w_0+\left\langle \bar\w,\obs\right\rangle
\end{equation}
où $\bar\w=(w_1,\ldots,w_d)$. L'intérêt du modèle (\ref{CondRegLog}) est qu'il recouvre une grande variété de distributions, par exemple toutes celles de la famille exponentielle \citep{kupperman:1958}, et que les probabilités a posteriori s'expriment sous une forme logistique \index{forme logistique}simple :
\begin{eqnarray*}
\label{APosterioRegLog}
\mathbb{P}(Y=1\mid X=\obs)\!\! &\!\!\!\!=\!\!\!\!&\!\! \frac{\mathbb{P}(Y=1)\mathbb{P}(X=\obs\mid Y=1)}{\sum_{y\in\{-1,+1\}}\mathbb{P}(Y=y)\mathbb{P}(X=\obs\mid Y=y)}\\
\!\! &\!\!=\!\!&\!\! \frac{e^{(\tilde w_0+\left\langle \bar\w,\obs\right\rangle)}}{1+e^{(\tilde w_0+\left\langle\bar\w,\obs\right\rangle)}}=\frac{1}{1+e^{-(\tilde w_0+\left\langle\bar\w,\obs\right\rangle)}} \nonumber
\end{eqnarray*}
et $\mathbb{P}(Y=-1\mid X=\obs)=1-\mathbb{P}(Y=1\mid X=\obs)=\frac{1}{1+e^{(\tilde w_0+\left\langle\bar\w,\obs\right\rangle)}}$, avec $\tilde w_0~=~w_0+\ln\left(\frac{\mathbb{P}(Y=1)}{\mathbb{P}(Y=-1)}\right)~\in~\mathbb{R}$ qui est une constante. Les paramètres du modèle $\w=(\tilde w_0,\bar \w)$ sont alors estimés en maximisant le logarithme de la vraisemblance classifiante \index{vraisemblance!classifiante} sur une base d'entraînement\index{base!d'entraînement} $S=\left((\obs_i,y_i)\right)_{i=1}^m$ :
\begin{eqnarray}
\mathcal{V}(S, \w) &= &\displaystyle{\ln \prod_{i=1}^m \mathbb{P}(Y=y_i, X=\obs_i)}=\displaystyle{\ln \prod_{i=1}^m \mathbb{P}(Y=y_i\mid X=\obs_i)\mathbb{P}(X=\obs_i)} \nonumber \\
&=&\sum_{i=1}^m  \ln\left(\frac{1}{1+e^{-y_i(\tilde w_0+\left\langle\bar{\w},\obs\right\rangle)}}\right) + \sum_{i=1}^m  \ln \mathbb{P}(X=\obs_i) \label{LogLikliLR}
\end{eqnarray}
Comme on ne pose aucune hypothèse sur la génération des exemples, la maximisation de l'équation \ref{LogLikliLR} est équivalente à la maximisation de :
\begin{equation}
\label{LogLikliLR2}
\bar{\mathcal{V}}(S, \w)=\sum_{i=1}^m  \ln\left(\frac{1}{1+e^{-y_i(\tilde w_0+\left\langle\bar{\w},\obs\right\rangle)}}\right) 
\end{equation}

Une fois ces paramètres estimés, la règle de décision consiste à affecter un exemple $\obs$ à la classe d'étiquette $1$ si $\mathbb{P}(Y=1\mid X=\obs)>\frac{1}{2}$ (ou de façon équivalente si $h_{\w}(\obs)~=\tilde w_0+\left\langle\bar{\w},\obs\right\rangle>0$) et à la classe d'étiquette $-1$ sinon. 

\subsubsection{Adaboost}
\label{chbinary:Boosting}
Les méthodes d'ensemble\index{méthode!d'ensemble} constituent une famille générale d'algorithmes en apprentissage qui combinent plusieurs classifieurs de base afin de créer un classifieur plus performant. Parmi ces méthodes, l'algorithme de \textit{boosting}\index{boosting} \citep{freund:1995}, plus particulièrement Adaboost (\textit{Adaptive Boosting}) \citep{schapire:1999}, a connu une grande popularité due notamment à ses performances et ses justifications théoriques.  \index{adaptive boosting|see{algorithme Adaboost}}Il génère un ensemble de classifieurs de base (ou classifieurs \textit{faibles})\index{classifieur!faible} et les combine par une \index{méthode!à base de votes}méthode à base de votes\index{algorithme!Adaboost}, donnant ce qu'on appelle le classifieur de vote\index{classifieur!de vote}. Les classifieurs faibles sont entraînés séquentiellement; le $t^e$~classifieur généré prend en compte les erreurs du classifieur précédent déjà construit. Ceci est réalisé en affectant un poids $D(i)$ à chaque exemple $i$ de la base  d'apprentissage :  un  exemple  mal  classé  par  le $(t-1)^e$  classifieur  va être affecté  d'un poids plus élevé qu'un exemple bien classé. De cette façon, à l'étape $t$, le nouveau classifieur faible se focalisera sur la classification des exemples jugés difficiles par celui de l'étape $t-1$. L'algorithme \ref{algo:chap5:Boosting} décrit la première variante de l'algorithme Adaboost proposé par Freund et Schapire pour la classification en deux classes. 
\begin{algorithm}[h!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme d'Adaboost\index{algorithme!Adaboost}}
    \Entr{\begin{itemize}\item une base d'entraînement $\TrnSet=\left((\textbf{x}_1, y_1), ..., (\textbf{x}_m, y_m) \right)$  \end{itemize}}
       \textbf{Initialisation :}
\begin{itemize} \item nombre d'itérations maximal $T$\item initialiser la distribution des poids $\forall i\in \{1,\ldots,m\}, D_1(i)=\frac{1}{m}$\end{itemize}
    \Pour{$t=1,\ldots,T$}{
      \begin{itemize}
        \item apprendre un classifieur $f_t:\mathbb{R}^d\rightarrow \{-1,+1\}$ avec la distribution $D_t$
        \item poser $\epsilon_t=\sum_{i:f_t(\obs_i)\neq y_i} D_t(i)$
        \item choisir $a_t=\frac{1}{2}\ln \frac{1-\epsilon_t}{\epsilon_t}$
        \item mettre à jour la distribution des poids sur les exemples (Eq. \ref{eq:ch5:Regle})
\[
\forall i\in\{1,\ldots,m\}, D_{t+1}(i)=\frac{D_t(i)e^{-a_t y_i f_t(\obs_i)}}{Z_t}
\]
où $Z_t=\sum_{i=1}^m D_t(i)e^{-a_t y_i f_t(\obs_i)}$ est un facteur de normalisation pour que $D_{t+1}$ reste une distribution.
\end{itemize}    
    }
    \Sort{le classifieur de vote\index{classifieur!de vote} $\forall \obs, \displaystyle{F(\obs)=\text{sign} \left(\sum_{t=1}^T a_t f_t(\obs) \right)}$}
\label{algo:chap5:Boosting}
\end{algorithm} 

\smallskip


\begin{figure}[h!]
\centering
\input{Figs/chapter-Discriminant/Boosting}
\caption{Illustration du fonctionnement de l'algorithme d'Adaboost sur un problème jouet où la combinaison finale des classifieurs linéaires\index{classifieur!de base}\index{classifieur!linéaire} de base (ou faibles) conduit à un classifieur non linéaire. Le vecteur normal de chaque classifieur faible pointe vers le demi-espace des exemples positifs (cercles pleins et les exemples mal classés sont encerclés). À une itération donnée, le classifieur courant tente de bien classer les exemples mal classés par celui de l'itération précédente et les poids $w$ de ces classifieurs, intervenant dans le vote majoritaire final, sont inversement proportionnels à leurs erreurs de classification. }
\label{chap5:fig:Boosting}
\end{figure}
\`A l'initialisation, la distribution des poids sur les exemples est uniforme ($\forall i\in \{1,\ldots,m\}, D_1(i)=\frac{1}{m}$) et on choisit le nombre $T$ de classifieurs intervenant dans le vote final. \`A chaque itération $t$, un classifieur binaire\index{classifieur!binaire}, appartenant à la classe $\mathcal F=\{f:\mathbb{R}^d\rightarrow \{-1,+1\}\}$, est appris en minimisant l'erreur empirique de classification et en considérant les poids $D_t$ sur les exemples $(f_t=\displaystyle{\mathop{\text{argmin}}_{f\in \mathcal F} \sum_{i:f(\obs_i)\neq y_i} D_t(i)})$. D'après l'erreur empirique $\epsilon_t$ du classifieur appris sur la base d'apprentissage $(\epsilon_t=\sum_{i:f_t(\obs_i)\neq y_i} D_t(i))$, on affecte au classifieur appris un poids $a_t$ d'autant plus grand que l'erreur $\epsilon_t$ est grande. La distribution des poids est alors mise à jour d'après la règle suivante :
\begin{equation}
\label{eq:ch5:Regle}
\forall i\in\{1,\ldots,m\}, D_{t+1}(i)=\frac{D_t(i)e^{-a_t y_i f_t(\obs_i)}}{Z_t}
\end{equation}
où $Z_t=\sum_{i=1}^m D_t(i)e^{-a_t y_i f_t(\obs_i)}$ est un facteur de normalisation pour que $D_{t+1}$ reste une distribution. Si le classifieur courant $f_t$ donne une mauvaise prédiction de classe sur un exemple d'apprentissage $(\obs_i,y_i)$ (i.e. $y_i f_t(\obs_i)=-1$), le poids associé à cet exemple, $D_{t+1}(i)$, sera plus élevé que son poids précédent, $D_t(i)$. Le classifieur final $F$ est alors une combinaison linéaire des classifieurs $(f_t)_{t=1}^T$ avec leurs poids associés $(a_t)_{t=1}^T$ et la prédiction de classe pour un nouvel exemple $\obs$ se fait sur la base d'un vote majoritaire de ces classifieurs  avec leurs poids respectifs. La figure \ref{chap5:fig:Boosting} illustre le fonctionnement de l'algorithme \ref{algo:chap5:Boosting} sur un exemple jouet.



\subsubsection{Séparateurs à vaste marge}
Dans cette section\index{separateurs à vaste marge@séparateurs à vaste marge}, nous présentons le modèle des séparateurs à vaste marge \index{support vector|see{vecteur de support}}(SVM, appelé aussi machine à vecteurs de support ou \textit{support vector machine})\index{support vector machine|see{séparateurs à vaste marge}}  qui, grâce à ses justifications théoriques, est sans aucun doute l'algorithme de classification le plus populaire aujourd'hui. Pour sa présentation, le choix s'est porté à exposer ses fondements théoriques, qui ont conduit aux développements de différentes techniques d'optimisation proposées dans la littérature ces dernières années. 


\paragraph{Marge dure}
L'algorithme des SVM est conçu autour de la notion de \textit{marge}\index{marge} définie ci-après. Considérons tout d'abord le cas des fonctions linéaires pour un problème de classification linéairement séparable\index{linéairement séparable}, c'est-à-dire que nous supposons qu'il existe $(\w, w_0)$ tel que :
\begin{eqnarray*}
\label{eq:chap5:SVM:separability}
\forall \obs_i\in S_+,  & \langle \bar{\w}, \obs_i\rangle+w_0 \geq 0 & \mbox{~~et~~} \\ 
\forall \obs_i\in S_-, &  \langle \bar{\w}, \obs_i\rangle+w_0 \leq 0 & \nonumber
\end{eqnarray*}
où $S_+$ (resp. $S_-$) est l'ensemble des exemples positifs (resp. négatifs) de la base d'entraînement\index{base!d'entraînement}. Moyennant une normalisation des paramètres, on peut réécrire ces équations sous la forme suivante, qui sera utilisée par la suite :
\begin{eqnarray}
\label{eq:chap5:SVM21}
\forall \obs_i\in S_+,  &  \langle\bar{\w}, \obs_i\rangle+w_0 \geq +1 & \mbox{~~et~~} \\ 
\forall \obs_i\in S_-, &  \langle\bar{\w}, \obs_i\rangle+w_0 \leq -1 & \label{eq:chap5:SVM22}
\end{eqnarray}
Ces deux conditions peuvent se combiner en un seul ensemble d'inéquations:
\begin{equation}
\label{eq:chap5:SVM:CONDS}
\forall (\obs,y)\in S, y(\langle\bar{\w}, \obs\rangle+w_0) -1 \geq 0
\end{equation}

S'il existe des points vérifiant l'égalité dans l'inéquation (\ref{eq:chap5:SVM21}), ils appartiendront à l'hyperplan d'équation $\langle\bar{\w}, \obs_i\rangle+w_0 = 1$ et $d_+=\frac{1}{||\bar{\w}||}$ sera la distance entre le point le plus proche de la classe des exemples positifs et l'hyperplan séparateur\index{hyperplan!séparateur}. De même, les points vérifiant l'égalité dans l'inéquation (\ref{eq:chap5:SVM22}) appartiendront à l'hyperplan d'équation $\langle\bar{\w}, \obs_i\rangle+w_0 = -1$ et $d_-=\frac{1}{||\bar{\w}||}$ sera la distance entre le point le plus proche de la classe des exemples négatifs et l'hyperplan. Dans ces conditions, la marge\index{marge} est définie comme $\rho=d_+ = d_-=\frac{1}{||\bar{\w}||}$. 

De plus, parmi les points de la base d'entraînement\index{base!d'entraînement}, ceux qui vérifient l'égalité dans l'inéquation (\ref{eq:chap5:SVM:CONDS}) sont appelés les \textit{vecteurs de support}\index{vecteur!de support}. La figure~\ref{chap5:fig:SVM1} illustre ces faits dans le cas d'un problème à deux dimensions. L'idée \index{marge!dure}\index{hard margin|see{marge dure}}principale sous-jacente aux SVM est alors que plus la marge associée à une frontière de décision\index{frontière de décision} est grande, plus la fonction de prédiction associée est susceptible de bien généraliser sur de nouvelles données. Cette idée se traduit par la recherche d'un hyperplan de plus grande marge tout en respectant les contraintes de l'équation (\ref{eq:chap5:SVM:CONDS}), ce qui mène à la résolution du problème d'optimisation suivant\footnote{Ce type de SVM est appelé \textit{SVM à marge dure} (ou \textit{hard margin} en anglais).} :
\begin{equation}
\label{eq:SVM:Primal}
\begin{split}
 & \min_{\bar{\w}\in \mathbb{R}^d, w_0 \in \mathbb{R}} \frac{1}{2} ||\bar{\w}||^2\\
& \mbox{sous~les~contraintes~~} \forall i, y_i(\langle\bar{\w}, \obs_i\rangle+w_0) -1 \geq 0	
\end{split}
\end{equation}


Le problème (\ref{eq:SVM:Primal}) est dit problème d'optimisation sous contraintes prenant la forme d'inéquations. Posons $\w^*$ la solution de ce problème; deux situations sont envisageables pour chaque contrainte $i~\in~\{1,\ldots,m\}$ :
\begin{itemize}
\item $y_i(\langle\bar{\w^*}, \obs_i\rangle+w^*_0) -1 = 0$, la contrainte $i$ est dite saturée à l'optimum,\index{contrainte!saturée}
\item $y_i(\langle\bar{\w^*}, \obs_i\rangle+w^*_0) -1 > 0$, la contrainte $i$ est dite non saturée à l'optimum,\index{contrainte!non saturée}
\end{itemize}
La formulation de ce problème d'optimisation sous contraintes\index{optimisation!sous contraintes} en utilisant les variables de Lagrange $\boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_m); \alpha_i\geq0, \forall i\in\{1,\ldots,m\}$ associées aux $m$ contraintes du problème s'écrit\index{lagrangien} :
\begin{equation}
\label{eq:Lagrange}
L_p(\bar{\w},w_0,\boldsymbol{\alpha})=\frac{1}{2} ||\bar{\w}||^2-\sum_{i=1}^m \alpha_i\left[ y_i(\left\langle\bar{\w},\obs_i\right\rangle+w_0)-1\right]
\end{equation}
Pour pouvoir utiliser le Lagrangien dans la résolution de ce problème, il suffit que l'une des conditions suivantes soit vérifiée ; on dit alors que les conditions sont qualifiées\index{qualification de contraintes} :
\begin{itemize}
\item La matrice des dérivées partielles des contraintes, ou la matrice jacobienne\index{matrice!jacobienne} des $n$ contraintes saturées, est de rang $n$ lorsqu'elle est évaluée à l'optimum.
\item Les fonctions contraintes sont toutes affines, ce qui est le cas du problème \ref{eq:SVM:Primal}.
\end{itemize} 
La fonction de coût $\CnxEmpLoss:\bar{\w}\mapsto \frac{1}{2} ||\bar{\w}||^2$ est deux fois dérivable. Son vecteur gradient et sa matrice hessienne\index{hessienne} au point $\bar{\w}$ sont $\nabla\CnxEmpLoss(\bar{\w})=\bar{\w}$ et $\mathbf{H}(\bar{\w})~=~\mathbf{I}$, la matrice identité. La hessienne   $\mathbf{H}(\bar{\w})$ admet ainsi $d$ valeurs propres strictement positives, la fonction de coût $\CnxEmpLoss$ est strictement convexe et les contraintes d'inégalité $c_i: (\bar{\w}, w_0)\mapsto 1-y_i(\left\langle\bar{\w},\obs_i\right\rangle+w_0)$ sont des fonctions affines et donc des contraintes qualifiées. Le problème d'optimisation (\ref{eq:SVM:Primal}) admet ainsi une solution unique.  De plus, comme la fonction-objectif\index{fonction!objectif} est convexe et que les points qui satisfont les contraintes forment aussi un ensemble convexe, la résolution relève d'un problème de programmation quadratique,\index{programmation quadratique} qui constitue une famille de techniques largement étudiée en optimisation.

Les conditions que doit vérifier la solution $\w^*$ du problème (\ref{eq:SVM:Primal}) sont celles de Karush-Kuhn-Tucker \index{condition!Karush-Kuhn-Tucker} et elles sont obtenues en annulant le gradient\index{lagrangien} du Lagrangien par rapport aux variables primales\index{variables!primales} $\bar{\w^*}$ et $w^*_0$ et en écrivant les conditions complémentaires :
\begin{eqnarray}
\!\!\!\nabla L_p(\bar{\w^*}) = \bar{\w^*} - \sum_{i=1}^m \alpha_iy_i\obs_i=0 , \!\!\!\!& \!\!\!\text{ soit }&\!\!\!\! \bar{\w^*} = \sum_{i=1}^m \alpha_i y_i \obs_i \label{wgt} \\
\nabla L_p(w^*_0) = - \sum_{i=1}^m \alpha_iy_i=0 , \!\!\!\!& \text{ soit } &\!\!\!\!\sum_{i=1}^m \alpha_i y_i = 0\label{w0} \\
\!\!\!\!\!\!\forall i, \alpha_i\left[ y_i(\left\langle\bar{\w^*},\obs_i\right\rangle+w^*_0)-1\right]=0, \!\!\!\!& \text{ soit } &\!\!\!\!\begin{cases}\alpha_i=0 \text{, ou } \!\!\!&\!\!\! \\ y_i(\left\langle\bar{\w^*},\obs_i\right\rangle+w^*_0)=1 & \end{cases}\label{compl}
\end{eqnarray}



\begin{figure}[t!]
\begin{minipage}[c]{.8\textwidth}
\begin{center}
\includegraphics[width=.85\textwidth]{./Figs/chapter-Discriminant/SVM-MargeDure.png}
%\input{./Figs/Chapter3/SVM-MargeDure}
\end{center}
\end{minipage}

\bigskip

\caption{Hyperplans pour un problème de classification linéairement séparable\index{linéairement séparable} en dimension 2. Les vecteurs de support\index{vecteur!de support} appartenant aux hyperplans\index{hyperplan!marginal} marginaux d'équations $\langle\bar{\w},\obs \rangle+w_0=\pm 1$ sont encerclés.}
\label{chap5:fig:SVM1}
\end{figure}



Avec l'équation \ref{wgt}, nous voyons bien que le vecteur des poids $\bar{\w^*}$ solution du problème d'optimisation est une combinaison linéaire des exemples d'entraînement. Les exemples~$\obs_i$ qui apparaissent dans cette solution sont ceux pour lesquels les coefficients $\alpha_i>0$. Ces exemples sont appelés  des vecteurs de support \index{vecteur!de support} qui, par les conditions complémentaires (eq. \ref{compl}), vérifient $y_i(\left\langle\bar{\w^*},\obs_i\right\rangle+w^*_0)=1$. Les vecteurs de support reposent ainsi sur les hyperplans d'équations\index{hyperplan!marginal} $\left\langle\bar{\w^*},\obs_i\right\rangle+w^*_0=\pm 1$ et les autres exemples pour lesquels $\alpha_i=0$ n'influent pas sur la solution. 

En substituant les égalités (\ref{wgt}) et (\ref{w0}) dans le primal (\ref{eq:Lagrange}), on obtient :

\begin{equation}
\label{eq:ResuLP}
\begin{split}
L_p &= \frac{1}{2}\left\| \sum_{i=1}^m \alpha_iy_i\obs_i\right\|^2 - \sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j \langle\obs_i, \obs_j\rangle-w^*_0\underbrace{\sum_{i=1}^m \alpha_iy_i}_{=0}  +\sum_{i=1}^m \alpha_i\\
&= - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \langle\obs_i, \obs_j \rangle+ \sum_{i=1}^m \alpha_i
\end{split}
\end{equation}
soit le problème d'optimisation dual\index{optimisation!duale} suivant  appelé  dual de \textit{Wolfe} \index{dual de Wolfe} :
\begin{eqnarray}
 & \displaystyle{\max_{(\alpha_1, ..., \alpha_m) \in \mathbb{R}^m} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \langle\obs_i, \obs_j\rangle} \label{dualWolfe} \\
& \mbox{sous~les~contraintes~~} \displaystyle{\sum_{i=1}^m y_i \alpha_i=0} \mbox{~et~} \forall i, \alpha_i \geq 0 \label{ContraintesSVM}
\end{eqnarray}
 
 La fonction-objectif\index{fonction!objectif} $\mathfrak{D}:\boldsymbol{\alpha} \mapsto \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \langle\obs_i, \obs_j\rangle$ est deux fois dérivable et l'opposé de sa hessienne\index{hessienne} $-\mathbf{H}_\mathfrak{D}=(\langle y_i\obs_i,y_j\obs_j\rangle)_{1\leq i, j\leq m}$ est la matrice de Gram\index{matrice!de Gram}\index{hessienne!symétrique positive définie} de la famille de vecteurs $(y_1\obs_1,\ldots,y_m\obs_m)$,  qui est positive, semi-définie. $\mathfrak{D}$  est ainsi une fonction concave et, comme les contraintes (\ref{ContraintesSVM}) sont affines, les deux problèmes primal et dual sont équivalents.   
 
 
Nous\index{decision boundary|see{frontière de décision}} remarquons \index{outlier|see{point aberrant}}que la solution du problème dual $\boldsymbol \alpha$ pourrait\index{feature space|see{espace de redescription}} être directement employée pour déterminer  la fonction de décision\index{fonction!de décision} $f$ associée au modèle pour prédire la classe d'un nouvel exemple $\obs'$ en utilisant l'équation \eqref{wgt} :

\begin{equation}
\label{SVM:decision}
f(\obs')=\mbox{sgn} \left({\sum_{i=1}^m y_i \alpha_i \langle\obs_i, \obs'\rangle + w^*_0}\right)
\end{equation}
De plus, comme les vecteurs de support\index{vecteur!de support} appartiennent aux hyperplans marginaux\index{hyperplan!marginal} d'équations $\langle\bar{\w^*},\obs\rangle+w^*_0=\pm 1$ \index{hyperplan!marginal} dans l'espace des caractéristiques, nous pouvons déduire l'expression de l'ordonnée à l'origine en prenant n'importe quel vecteur de support $(\obs_i,y_i)$ :
\begin{equation}
\label{SVM:ordoalorigine}
\langle\bar{\w^*},\obs_i\rangle+w^*_0=y_i \Rightarrow w^*_0=y_i-\sum_{j=1}^m \alpha_jy_j\langle\obs_i,\obs_j\rangle
\end{equation}
Avec l'égalité précédente, nous pouvons obtenir une expression simple de la marge. En effet, comme l'équation \ref{SVM:ordoalorigine} est valable pour tous les vecteurs de support\index{vecteur!de support} avec $\alpha_i\neq 0$, en  multipliant les deux côtés de  cette égalité par $\alpha_iy_i$ et en prenant la somme sur tous les exemples de la base d'entraînement,\index{base!d'entraînement} il vient :
\[
\sum_{i=1}^m \alpha_iy_ib=\sum_{i=1}^m \alpha_iy_i^2-\sum_{i=1}^m \sum_{j=1}^m \alpha_i\alpha_jy_iy_j\langle\obs_i,\obs_j\rangle
\]
D'après les équations \eqref{w0} et \eqref{wgt} et en considérant le fait que $\forall i, y_i^2=1$ et $\alpha_i\geq 0$ nous avons :
 \[
 \sum_{i=1}^m \alpha_i -\|\bar{\w^*}\|_2^2=\|\boldsymbol{\alpha}\|_1-\|\bar{\w^*}\|_2^2=0
 \] 
 soit la marge qui est égale à \index{marge} :
 \[
 \rho=\frac{1}{\|\bar{\w^*}\|_2}=\frac{1}{\sqrt{\|\boldsymbol{\alpha}\|_1}}
 \] 
L'intérêt essentiel de passer par le problème dual est que la dimension de l'espace d'entrée n'intervient pas dans la résolution du problème d'optimisation, qui ne dépend plus que des produits scalaires entre les couples d'exemples de la base d'entraînement\index{base!d'entraînement}. 

Ce constat a motivé l'utilisation de \textit{noyaux} pour les SVM, qui permettent d'apprendre des classifieurs non linéaires\index{classifieur!non-linéaire}. Cette utilisation suit les travaux qui ont montré que, dans certains cas, il est possible de rendre un problème non linéairement séparable\index{linéairement séparable} en un problème linéairement séparable en plongeant les données initiales dans un  espace de Hilbert\index{espace!de Hilbert}~$\mathbb{H}$ de plus grande dimension que l'espace de départ, appelé espace de redescription\index{espace!de redescription} (ou \textit{feature space}\index{feature space|see{espace de redescription}}). Ainsi, si on pose $\phi:\InpSpc\rightarrow\mathbb{H}$ la fonction de projection\index{fonction!de projection}, le noyau correspond au produit scalaire dans l'espace de plongement\index{espace!de plongement}:
\begin{eqnarray*}
 \kappa:\InpSpc\times\InpSpc& \rightarrow & \mathbb{R} \\
 (\obs, \obs') & \mapsto &  \langle\phi(\obs), \phi(\obs')\rangle
\end{eqnarray*}
Les deux principaux noyaux \index{noyau!polynomial}\index{noyau!gaussien} utilisés dans la littérature sont:
\begin{eqnarray*}
\kappa(\textbf{x}, \textbf{x}')&=&(\langle\textbf{x}, \textbf{x}'\rangle+1)^r \mbox{ pour }r \in \mathbb{N} ~~(\mbox{noyau polynomial}) \\
 \kappa(\textbf{x}, \textbf{x}')&=&e^{-\frac{||\textbf{x}-\textbf{x}'||^2}{2\sigma^2}}, \sigma\neq 0 ~~(\mbox{noyau Gaussien RBF})
\end{eqnarray*}


Les noyaux s'utilisent dans les SVM en lieu et place du produit scalaire. Avec ces notations, l'algorithme des SVM à marge dure est :

\begin{algorithm}[h!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{SVM à marge dure}
 
    \Entr{\begin{itemize}\item une base d'entraînement\index{base!d'entraînement} $S=\left((\textbf{x}_1, y_1), ..., (\textbf{x}_m, y_m) \right)$ \end{itemize}}
    
    \begin{tabular}{|l}

{\color{black!70}$\bullet$} trouver, $\boldsymbol \alpha^*$, la solution du problème d'optimisation \\
\hspace{2cm}$\displaystyle{\max_{\boldsymbol \alpha \in \mathbb{R}^m} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \kappa(\obs_i, \obs_j)} $ \\
\hspace{2cm}sous les contraintes $\displaystyle{\sum_{i=1}^m y_i \alpha_i=0 \mbox{~et~} \forall i, \alpha_i \geq 0}$\\

{\color{black!70}$\bullet$}  choisir $i\in\{1,\ldots,m\}$ tel que $\alpha_i^*>0$ \\
    \hspace{5mm} Poser $w^*_0=y_i-\displaystyle{\sum_{j=1}^m \alpha^*_jy_j\kappa(\obs_j,\obs_i)}$ {\color{black!70}// $\rhd$ (eq. \ref{SVM:ordoalorigine})}\\
{\color{black!70}$\bullet$} $\displaystyle{\bar{\w^*}=\displaystyle{\sum_{i=1}^m y_i\alpha_i^* \phi(\obs_i)}}$  {\color{black!70}// $\rhd$ (eq. \ref{wgt})}
    \end{tabular}
    
    \Sort{fonction de décision $\forall \obs, f(\obs)=\text{sgn}\left(\displaystyle{\sum_{i=1}^m y_i \alpha_i^* \kappa(\obs_i,\obs)+w^*_0}\right)$ \index{separateurs à vaste marge@séparateurs à vaste marge!algorithme (marge dure)} }
\label{algo:chap5:SVMmargedure}


\end{algorithm} 

\smallskip

Il existe une multitude de programmes implémentant les SVM de façon efficace, dont les plus populaires sont sans doute ceux de \citep{joachims:1999a}\footnote{\url{http://svmlight.joachims.org/}} et de \citep{fan:2008}\footnote{\url{http://www.csie.ntu.edu.tw/~cjlin/liblinear/}}.

\paragraph{Marge souple}

Un inconvénient\index{marge!souple}\index{soft margin|see{marge souple}} majeur de ce problème d'optimisation est que, lorsque les données sont complexes ou bruitées, ce qui est généralement le cas, la condition de séparabilité n'est plus respectée. Une solution à ce problème est de relâcher les contraintes sur la marge en introduisant de nouvelles variables $\xi_i$, appelées variables d'écart ; cela\index{variables!d'écart}\index{slack variables|see{variables d'écart}} assouplit les contraintes dans les inéquations (\ref{eq:chap5:SVM21}) et (\ref{eq:chap5:SVM22}) qui, dans l'espace de redescription,\index{espace!de redescription} s'écrivent:
\begin{eqnarray}
\label{eq:chap5:SVM:nonseparability}
\forall i, & \xi_i \geq 0 & \\
\forall \obs_i\in S_+,  & \langle\bar{\w}, \phi(\obs_i)\rangle+w_0 \geq 1-\xi_i &  \label{eq:chap5:SVM3}\\ 
\forall \obs_i\in S_-, & \langle\bar{\w}, \phi(\obs_i)\rangle+w_0 \leq -1+\xi_i  & \label{eq:chap5:SVM4}
\end{eqnarray}
D'après ces inéquations, lorsqu'un exemple $\textbf{x}_i$ de la base d'entraînement\index{base!d'entraînement} est mal classé, la variable $\xi_i$ correspondante doit être plus grande que l'unité, puisque dans ce cas $1-\xi_i$ ou $-1+\xi_i$ change de signe. De ce fait, la somme $\sum_i \xi_i$ détermine une borne supérieure du nombre d'erreurs de classification sur la base d'entraînement\index{base!d'entraînement} (figure~\ref{chap5:fig:SVM2}).

\begin{figure}[h!]
\begin{minipage}[c]{.8\textwidth}
\centering
\begin{center}
%\input{./Figs/Chapter3/SVM-MargeSouple}
\includegraphics[width=.85\textwidth]{./Figs/chapter-Discriminant/SVM-MargeSouple.png}
\end{center}
\end{minipage}
\medskip

\caption{Hyperplans linéaires pour un problème de classification non linéairement séparable\index{linéairement séparable}. Les vecteurs de support\index{vecteur!de support} sont encerclés. Soit ces vecteurs reposent  sur un des hyperplans marginaux, soit ce sont des points aberrants. La distance d'un point aberrant $\obs$ à l'hyperplan marginal associé à sa classe est $\frac{\xi}{||\bar{\w}||}$. }
\label{chap5:fig:SVM2}
\end{figure}

On cherche alors à minimiser les erreurs de classification tout en maximisant la marge, ce qui revient à changer la fonction-objectif\index{fonction!objectif} du problème primal de $\frac{||\bar{\w}||^2}{2}$ en $\frac{||\bar{\w}||^2}{2}~+~C \sum_{i=1}^m \xi_i$, où $C$ est un paramètre fixé à l'avance (plus $C$ est grand, plus les erreurs sont pénalisées). Le problème d'optimisation prend alors la forme:
\begin{equation}
\label{SVM2sscontraintes}
\begin{split}
 & \min_{\bar{\w} \in \mathbb{H}, w_0 \in \mathbb{R}, \xi \in \mathbb{R}^m} \frac{1}{2} ||\bar{\w}||^2 + C \sum_{i=1}^m \xi_i\\
 & \mbox{sous~les~contraintes~~} \forall i, \xi_i \geq 0 \mbox{~~et~~}y_i (\langle\bar{\w}, \phi(\textbf{x}_i)\rangle+w_0) \geq 1 - \xi_i
\end{split}
\end{equation}
C'est ce qu'on appelle \textit{SVM à marge souple} (ou \textit{soft margin}), puisque les contraintes sur la marge sont assouplies pour certains exemples. 

Comme pour le cas séparable, les contraintes sont affines et qualifiées ; la fonction-objectif étant aussi convexe, les conditions de Karush-Kuhn-Tucker\index{condition!Karush-Kuhn-Tucker} s'appliquent à l'optimum. Soit $\beta_i\geq 0, \forall i$\index{variables!de Lagrange} les variables de Lagrange\index{variables!de Lagrange} associées aux contraintes de non négativité des variables d'écart et $\alpha_i\geq 0, i\in\{1,\ldots,m\}$ les variables associées à l'ensemble des $m$ contraintes suivantes. Nous notons par $\boldsymbol \xi$\index{variables!d'écart} le vecteur $(\xi_1,\ldots,\xi_m)^\top$ par $\boldsymbol \alpha$ le vecteur $(\alpha_1,\ldots,\alpha_m)^\top$ et par $\boldsymbol \beta$ le vecteur $(\beta_1,\ldots,\beta_m)^\top$. Le Lagrangien\index{lagrangien} peut alors être défini pour tout $\bar{\w}\in \mathbb{H}$, $w_0\in\mathbb{R}$, $\boldsymbol \xi\in\mathbb{R}_+^m$, $\boldsymbol \alpha\in\mathbb{R}_+^m$ et  $\boldsymbol \beta\in\mathbb{R}_+^m$ par :
\begin{equation*}
%\label{SVMLagDual}
L_p(\bar{\w},w_0,\boldsymbol \xi, \boldsymbol \alpha, \boldsymbol \beta)\!\!=\!\!\frac{1}{2}\|\bar{\w}\|^2+C\sum_{i=1}^m\xi_i-\sum_{i=1}^m \alpha_i[y_i(\langle \phi(\obs_i),\bar{\w}\rangle+w_0)-1+\xi_i]-\sum_{i=1}^m \beta_i\xi_i
\end{equation*}
Les conditions de KKT sont obtenues en annulant les dérivées partielles du Lagrangien par rapport aux variables  $\bar{\w},w_0,\boldsymbol \xi, \boldsymbol \alpha$ et $\boldsymbol \beta$ et en écrivant les conditions complémentaires :
\begin{eqnarray}
\nabla L_p(\bar{\w}) = \bar{\w} - \sum_{i=1}^m \alpha_iy_i\phi(\obs_i)=0 , \!\!\!\!& \text{ soit }&\!\!\!\! \bar{\w} = \sum_{i=1}^m \alpha_i y_i \phi(\obs_i) \label{wgt2} \\
\nabla L_p(w_0) = - \sum_{i=1}^m \alpha_iy_i=0 , \!\!\!\!& \text{ soit } &\!\!\!\!\sum_{i=1}^m \alpha_i y_i = 0\label{w02} \\
\nabla L_p(\boldsymbol \xi) = C\times \mathbf{1}_m - \boldsymbol \alpha- \boldsymbol \beta=0 , \!\!\!\!& \text{ soit } &\!\!\!\!\forall i, C = \alpha_i-  \beta_i\label{C} \\
\forall i, \alpha_i\left[ y_i h_{\w}(\obs_i)-1+\xi_i\right]=0, & \text{ soit } &\alpha_i=0 \text{ ou } y_i h_{\w}(\obs_i)=1-\xi_i\label{complalpha2}\\
 \forall i, \beta_i\xi_i=0, & \text{ soit } & \beta_i=0\text{~ou~}\xi_i=0 \label{complbeta2}
\end{eqnarray}
où $\mathbf{1}_m$ est le vecteur de dimension $m$ ayant toutes ses composantes égales à~$1$ et $ h_{\w}(\obs)=\langle\phi(\obs), \bar{\w}\rangle+w_0$. Comme dans le cas séparable, le vecteur de poids $\bar{\w}$ solution du problème est une combinaison linéaire des exemples de la base d'entraînement\index{base!d'entraînement} (eq. \ref{wgt2}). D'après l'équation (\ref{complalpha2}), nous voyons qu'il y a cependant deux types de vecteurs de support\index{vecteur!de support}. En effet, un exemple $\obs_i\in\TrnSet$ est un vecteur support si son coefficient~$\alpha_i$ associé est non nul. Dans ce cas, d'après l'équation $y_i(\left\langle\bar{\w},\obs_i\right\rangle+w_0)=1-\xi_i$, si $\xi_i=0$ alors l'exemple~$\obs_i$ est sur l'un des hyperplans marginaux\index{hyperplan!marginal} et, si $\xi_i \neq 0$, le vecteur support est un point aberrant (ou un \textit{outlier}) (voir figure \ref{chap5:fig:SVM2}). Pour un point aberrant\index{point aberrant}~$\obs_i$, nous avons d'après l'équation (\ref{complbeta2}) $\beta_i=0$, ce qui d'après l'équation (\ref{C}) implique que $\alpha_i=C$. Ainsi, les vecteurs de support\index{vecteur!de support} sont soit des points aberrants dont les coefficients~$\alpha$ sont tous égaux à $C$, soit des points reposant sur un des  hyperplans marginaux.  La forme duale du problème d'optimisation sous contraintes\index{optimisation!sous contraintes} \eqref{SVM2sscontraintes} s'obtient en remplaçant l'expression du vecteur poids (eq. \ref{wgt2}) dans le Lagrangien et en utilisant les équations (\ref{C}) et (\ref{w02}). 

D'après l'équation (\ref{C}), nous avons :
\[
C\sum_{i=1}^m \xi_i-\sum_{i=1}^m \alpha_i\xi_i-\sum_{i=1}^m \beta_i\xi_i=\sum_{i=1}^m\xi_i\underbrace{(C-\alpha_i-\beta_i)}_{=0}=0
\] 
soit
\begin{equation}
\label{eq:ResuLP2}
\begin{split}
L_p &= \frac{1}{2}\left\| \sum_{i=1}^m \alpha_iy_i\phi(\obs_i)\right\|^2 - \sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j \kappa(\obs_i, \obs_j)-w_0\underbrace{\sum_{i=1}^m \alpha_iy_i}_{=0}  +\sum_{i=1}^m \alpha_i\\
&= - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \kappa(\obs_i, \obs_j)+ \sum_{i=1}^m \alpha_i
\end{split}
\end{equation}




C'est exactement la forme de la fonction-objectif\index{fonction!objectif} obtenue dans le cas séparable (eq. \ref{eq:ResuLP}) avec, comme seule différence, les contraintes sur les variables de Lagrange\index{variables!de Lagrange} $\beta_i\geq0$, ce qui d'après l'équation (\ref{C}) impose une borne supérieure sur les contraintes $\alpha_i\leq C$. L'optimisation duale\index{optimisation!duale} des SVM dans le cas non séparable est ainsi la même que celle des SVM dans le cas  séparable avec cette borne supérieure sur les contraintes $(\alpha_i)_{i=1}^m$, soit :


\begin{eqnarray}
 & \displaystyle{\max_{(\alpha_1, ..., \alpha_m) \in \mathbb{R}^m} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \kappa(\obs_i, \obs_j)} \label{dualWolfe2} \\
& \mbox{sous~les~contraintes~~} \displaystyle{\sum_{i=1}^m y_i \alpha_i=0} \mbox{~et~} \forall i, 0\leq \alpha_i \leq C \label{ContraintesSVM2}
\end{eqnarray}

\begin{algorithm}[!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{SVM à marge souple}

  
    \Entr{\begin{itemize}\item une base d'entraînement\index{base!d'entraînement} $S=\left((\textbf{x}_1, y_1), ..., (\textbf{x}_m, y_m) \right)$ \end{itemize}}
    
    \begin{tabular}{|l}

{\color{black!70}$\bullet$} trouver, $\boldsymbol \alpha^*$, la solution du problème d'optimisation \\
\hspace{2cm}$\displaystyle{\max_{\boldsymbol \alpha \in \mathbb{R}^m} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j \kappa(\obs_i, \obs_j)} $ \\
\hspace{2cm}sous les contraintes $\displaystyle{\sum_{i=1}^m y_i \alpha_i=0 \mbox{~et~} \forall i, 0\leq \alpha_i \leq C}$\\

{\color{black!70}$\bullet$}  choisir $i\in\{1,\ldots,m\}$ tel que $0<\alpha_i^*<C$ \\
    \hspace{5mm} poser $w^*_0=y_i-\displaystyle{\sum_{j=1}^m \alpha^*_jy_j \kappa(\obs_j,\obs_i)}$ \\
{\color{black!70}$\bullet$} $\displaystyle{\bar{\w^*}=\displaystyle{\sum_{i=1}^m y_i\alpha_i^* \phi(\obs_i)}}$  {\color{black!70}// $\rhd$ (eq. \ref{wgt2})}
    \end{tabular}
    
    \Sort{fonction de décision $\forall \obs, f(\obs)=\text{sgn}\left(\displaystyle{\sum_{i=1}^m y_i \alpha_i^* \kappa(\obs_i,\obs)+w^*_0}\right)$ \index{separateurs à vaste marge@séparateurs à vaste marge!algorithme (marge souple)} }
\label{algo:chap5:SVMmargesouple}
\end{algorithm}  

\smallskip

Comme dans le cas linéairement séparable\index{linéairement séparable}, nous obtenons la valeur de l'ordonnée à l'origine~$w^*_0$ en prenant un vecteur support $(\obs_i,y_i)$ qui n'est pas un point aberrant (i.e. $\xi_i=0$ et $\alpha_i<C$). Pour ce vecteur support, nous avons alors $\sum_{j=1}^m \alpha_j y_j \kappa(\obs_i,\obs_j)+w^*_0=y_i$, soit $w^*_0=y_i-\sum_{j=1}^m \alpha_j y_j \kappa(\obs_i,\obs_j)$.

L'algorithme des SVM à marge souple est ainsi identique à l'algorithme~(\ref{algo:chap5:SVMmargedure}) avec, comme seule différence, le problème d'optimisation (\ref{ContraintesSVM2}) et la borne supérieure $C$ sur les variables $(\alpha_i)_{i=1}^m$. 

\subsection{Modèles multi-classes} 

Dans les problèmes multi-classes, les deux cas d'étude sont le mono-label, où chaque exemple n'appartient qu'à une seule classe,\index{classification!multi-classe!mono-label} et le cas contraire dénommé souvent multi-label \index{classification!multi-classe!multi-label}.  Dans le cas mono-label\index{classification!multi-classe!mono-label}, l'espace de sortie est un ensemble d'étiquettes de classe $\OutputSpace=\{1,\ldots,K\}$ et les deux manières usuelles de représenter la sortie d'un exemple $\obs\in\InputSpace$ est soit de lui affecter son étiquette de classe $y\in\OutputSpace$, soit de lui associer un vecteur indicateur de classe\index{vecteur!indicateur!de classe} $\mathbf{y}\in\{0,1\}^K$ qui est  binaire avec toutes ses composantes égales à $0$ sauf la composante correspondant à la classe de l'exemple, qui vaut $1$ :
\begin{equation}
\label{VecIndClasse}
\forall (\obs, y)\in\InputSpace\times\OutputSpace, y=k \Leftrightarrow\mathbf{y}^\top = \left(\underbrace{y_1,\ldots,y_{k-1}}_{\small \text{tous égaux à 0}}, \underbrace{y_k}_{=1}, \underbrace{y_{k+1},\ldots,y_K}_{\small \text{tous égaux à 0}}\right)
\end{equation}
Dans le cas multi-label\index{classification!multi-classe!multi-label}, l'espace de sortie est $\OutputSpace=\{-1,+1\}^K$ et chaque exemple $\obs\in\InputSpace$ peut appartenir à plusieurs classes, auquel cas la sortie associée à l'exemple est un vecteur $\mathbf{y}\in\OutputSpace$ dont les composantes correspondant  aux classes de l'exemple sont égales à $+1$ et les autres valent $-1$.

\subsubsection{Erreurs de classification}
Comme dans le cas binaire, nous supposons que les paires d'exemples $(\obs,y)\in \InputSpace\times \OutputSpace$ sont  i.i.d.\index{i.i.d.}\index{identiquement et indépendamment distribué|see{i.i.d.}} suivant une distribution de probabilités fixe mais inconnue $\DistLbl$. Le but de l'apprentissage est de trouver la fonction de classification dans un espace de fonctions $\mathcal F=\{ f:\InputSpace\rightarrow \OutputSpace\}$ donné qui a la plus faible erreur de généralisation :
\begin{equation}
\label{MultiErrGen}
\Loss(f)=\E_{(\obs,y)\sim \DistLbl} [\InstLoss(f(\obs),y)]
\end{equation}
où $f(\obs)=(f_1(\obs),\ldots,f_K(\obs))\in\OutputSpace$ est le vecteur de sortie prédit pour l'exemple $\obs$ dans le cas multi-label\index{classification!multi-classe!multi-label} ou l'indice de classe dans le cas mono-label\index{classification!multi-classe!mono-label} et $\InstLoss:\OutputSpace\times \OutputSpace\rightarrow\R_+$ est une erreur de classification instantanée. Dans le cas multi-label,\index{classification!multi-classe!multi-label} cette erreur est souvent basée sur la distance de \cite{hamming:1950}\index{distance de Hamming}, comptant le nombre de composantes différentes entre les vecteurs de classe prédits $f(\obs)$ et réels $y$ pour un exemple $\obs$.  
\begin{equation}
\label{HammingDist}
\InstLoss(f(\obs),y)= \frac{1}{2}\sum_{k=1}^K (1-\text{sgn}(y_k f_k(\obs))) 
\end{equation}
où sgn désigne la fonction signe. Dans le cas mono-label\index{classification!multi-classe!mono-label}, l'erreur instantanée est définie simplement comme :
\begin{equation}
\label{ErrClassif}
\InstLoss(f(\obs),y)=  \Predi{f(\obs)\neq y}
\end{equation}

Comme dans le cas binaire, la fonction de classification est trouvée  suivant le principe de la minimisation du risque empirique\index{minimisation du risque!empirique} ERM, en utilisant une base d'entraînement\index{base!d'entraînement} $\TrnSet~=~\{(\obs_1,y_1),\ldots,(\obs_m,y_m)\}\in(\InputSpace\times \OutputSpace)^m$.
\begin{equation}
\label{MultiErrEmp}
f^*=\mathop{\text{argmin}}_{f\in \mathcal{F}} \LossEmp(f,\TrnSet)=\mathop{\text{argmin}}_{f\in \mathcal{F}} \frac{1}{m}\sum_{i=1}^m \InstLoss(f(\obs_i),y_i)
\end{equation}


En pratique, on apprend une fonction $\boldsymbol{h}$ définie comme :
\begin{align*}
\boldsymbol{h}:\R^d &\rightarrow\R^K\\
\obs&\mapsto (h(\obs,1),\ldots,h(\obs,K))
\end{align*}
où $h\in\R^{\InputSpace\times \OutputSpace}$, en minimisant une borne convexe dérivable de l'erreur empirique. La fonction de prédiction $f$ pour un exemple $\obs$ est alors obtenue en seuillant les sorties de $h(\obs,k), k\in\{1,\ldots,K\}$ pour le cas multi-label\index{classification!multi-classe!multi-label} ou en prenant l'indice de classe donnant la plus grande valeur de sortie prédite suivant $h$ pour le cas mono-label\index{classification!multi-classe!mono-label} :

\begin{equation}
 \label{eq:PredMonoClasse}
 \forall \obs, f_{\boldsymbol{h}}(\obs) = \mathop{\text{argmax}}_{k\in\{1,\ldots,K\}} h(\obs,k)
\end{equation}


\subsubsection{Différentes approches} 
Pour apprendre les fonctions $h\in\R^{\InputSpace\times \OutputSpace}$, il existe deux approches classiques appelées \textit{approches pures} et \textit{approches combinées}. Les premières consistent à apprendre un seul modèle qui prédit les classes des exemples, par exemple les SVM multi-classes ou les perceptrons multi-couches que nous verrons dans le chapitre suivant. Les approches combinées sont quant à elles basées sur une réduction du problème multi-classe à la classification binaire et elles dérivent du modèle  des codes correcteurs d'erreur, ou \textit{error correction codes}  (ECOC), proposée par  \cite{dietterich:1995}. 

Cette technique est composée de deux étapes. Dans la première, chaque classe $k$ est d'abord codée (ou représentée) par une séquence de bits de longueur fixe $n$, $\mathbf{\mathfrak{D}}_k$, appelée mot de code\index{mot de code},  qui traduit les caractéristiques intrinsèques de la classe. Avec la matrice de code résultante $\mathbf{\mathfrak{D}}\in\{-1,+1\}^{K\times n}$, $n$ classifieurs binaires sont appris en créant $n$ bases d'entraînement $\tilde{\TrnSet}_j$ avec la base initiale $\TrnSet$. Chacune des bases $\tilde{\TrnSet}_j$ est créée en considérant la colonne $j$ correspondante de la matrice $\mathbf{\mathfrak{D}}$ et en ré-étiquetant les exemples avec leurs étiquettes d'entrée correspondantes dans cette colonne. 
\begin{equation}
\label{eq:codage}
\forall (\obs,y)\in\InputSpace\times \OutputSpace, \forall j\in\{1,\ldots,n\}, \text{~le codage associé à l'observation est~}(\obs,\mathfrak{D}_y(j))
\end{equation}
Ce procédé est illustré dans l'algorithme (\ref{algo:chap6:ECOC}).

\begin{algorithm}[!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Stratégie des codes correcteurs d'erreur pour la classification multi-classe}

    \Entr{\begin{itemize}\item une base d'entraînement\index{base!d'entraînement} $S=\{(\textbf{x}_1, \mathbf{y}_1), ..., (\textbf{x}_m, \mathbf{y}_m) \}\in (\InputSpace\times \OutputSpace)^m$; \item la matrice de codage des classes $\mathbf{\mathfrak{D}}\in\{-1,+1\}^{K\times n}$\end{itemize}}
       \Pour{$j=1\ldots n$}
       {
             $\tilde{\TrnSet}_j\leftarrow \emptyset$
            \Pour{$i=1 \ldots m$}
            {
                 $\tilde{\TrnSet}_j\leftarrow (\obs_i, \mathfrak{D}_{y_i}(j))$; {\color{black!70}// $\rhd$~(eq. \ref{eq:codage})}
            }
            apprendre un classifieur $h_{j}:\InputSpace\rightarrow\R$ sur $\tilde \TrnSet_j$
            %Définir $f_j:\InpSp\rightarrow\{-1,+1\}, \forall \obs, f_j(\obs)=\text{sgn}(h_j(\obs))$;\;
       }
    
    \Sort{$\forall \obs\in\InputSpace, \mathbf{h}(\obs)=(h_1(\obs),\ldots,h_n(\obs))^\top$}
\label{algo:chap6:ECOC}
\end{algorithm} 

\smallskip

La deuxième étape, dite de prédiction, consiste alors à affecter chaque exemple à la classe dont le code associé $\mathfrak{D}_.$ est le plus proche des sorties des classifieurs binaires appris d'après la distance de \cite{hamming:1950}\index{distance de Hamming} :
\begin{equation}
\label{eq:distHammECOC}
\forall \obs\in\InputSpace, f(\obs)=\mathop{\text{argmin}}_{k\in\{1,\ldots,K\}} \frac{1}{2}\sum_{j=1}^n (1-\text{sgn}(\mathfrak{D}_{k}(j)h_j(\obs)))
\end{equation}

\cite{allwin:2000} ont étendu le codage de la matrice aux codes ternaires $\mathbf{\mathfrak{D}}~\in\{-1,0,+1\}^{K\times n}$ pour ne pas tenir compte des exemples ayant une sortie de classe $0$ après codage, dans l'apprentissage des fonctions binaires. Avec ce codage, les stratégies un contre tous et un contre un deviennent des cas particuliers des codes correcteurs. En effet, la matrice de code pour le cas un contre tous est une matrice carrée $K\times K$ ayant  ses éléments diagonaux égaux à $+1$ et tous les autres éléments égaux à $-1$. La matrice de code pour le cas un contre un est quant à elle, une matrice $K\times n$, avec $n=\frac{K(K-1)}{2}$, où chaque colonne est associée à une paire de classes $(k,\ell), k<\ell$ avec tous ses éléments égaux à $0$ sauf ceux correspondant à la ligne $k$, qui est égal à $+1$, et à la ligne $\ell$, qui vaut $-1$.

\section{Approches semi-supervisées}
\label{sec:semisup}
L'apprentissage semi-supervisé,\index{apprentissage!semi-supervisé} aussi appelé apprentissage avec des données partiellement étiquetées, est un apprentissage supervisé\index{apprentissage!supervisé} où l'on dispose à la fois d'exemples étiquetés et d'exemples non étiquetés. Les exemples étiquetés sont en général supposés trop peu nombreux pour que l'on puisse obtenir une bonne estimation des dépendances recherchées et l'on veut s'aider des exemples non étiquetés pour obtenir une meilleure estimation. Pour cela, nous supposerons disponibles un ensemble d'exemples étiquetés $\TrnSet = \{(\obs_i, y_i) \mid i = 1, \ldots, m\}$ issus de la distribution jointe $\mathbb{P}(\obs,y)$  (notée aussi par $\Dist$)  et un ensemble d'exemples non étiquetés $\ulda = \{\obs_i \mid i = m+1, \ldots, m+u\}$ supposés issus de la distribution marginale $\mathbb{P}(\obs)$.  Si $\ulda$ est vide, on retombe sur le problème de l'apprentissage supervisé\index{apprentissage!supervisé}. Si $\TrnSet$ est vide, on est en présence d'un problème d'apprentissage non supervisé.  Au cours de l'apprentissage, les algorithmes semi-supervisés estiment des étiquettes pour les exemples non étiquetés. On pose $\tilde y$ et $\tilde{\mathbf{z}}$ respectivement l'étiquette et le vecteur indicateur de classe\index{vecteur!indicateur!de classe} de l'exemple non étiqueté $\obs\in\ulda$ estimés par ces algorithmes. L'intérêt de l'apprentissage semi-supervisé\index{apprentissage!semi-supervisé} survient lorsque $u = |\ulda| >>  m = |\TrnSet|$ et le but est que la connaissance que l'on gagne sur la distribution marginale, $\mathbb{P}(\obs)$, à travers les exemples non étiquetés puisse apporter de l'information utile dans l'inférence de  $\mathbb{P}(y\mid \obs)$. Si ce but n'est pas atteint, l'apprentissage semi-supervisé\index{apprentissage!semi-supervisé} sera moins performant que le supervisé et il peut même arriver que l'utilisation des données non étiquetées dégradent la performance de la fonction de prédiction apprise \citep{zhang:2000, cozman:2002}. Il est alors nécessaire de formuler des hypothèses de travail pour la prise en compte des données non étiquetées dans l'apprentissage supervisé\index{apprentissage!supervisé} d'une fonction de prédiction\index{fonction!de prédiction}.

\subsection{Modèles graphiques}
Les modèles graphiques\index{apprentissage!semi-supervisé!modèles graphiques} utilisent un graphe empirique $G=(V,E)$ construit sur les exemples étiquetés et non étiquetés pour exprimer leur géométrie. Les n\oe{}uds $V={1,\ldots,m+u}$ de ce graphe représentent les exemples d'apprentissage et les arêtes $E$ traduisent les similarités entre eux. Ces similarités sont généralement données par une matrice symétrique positive $\boldsymbol W=[W_{ij}]_{i,j}$, où $\forall (i,j)\in\{1,\ldots,m+u\}^2$ le poids $W_{ij}$ est non nul si et seulement si les exemples d'indices $i$ et $j$ sont connectés, ou si $(i,j)\in E\times E$ est une arête du graphe $G$. Les deux exemples de matrices de similarité communément utilisées dans la littérature sont :
\begin{itemize}
\item la matrice binaire des $k$-plus proches voisins : 
\begin{align*}
\begin{split}
\forall (i,j)\in \{1,\ldots,m+u\}^2 ; W_{ij}=1  & \text{~si et seulement si l'exemple $\obs_i$ est parmi les} \\
& \text{$k$-plus proches voisins de l'exemple~}\obs_j 
\end{split}
\end{align*}
\item la matrice de similarité gaussienne de paramètre $\sigma$ :
\begin{equation}
\label{MatGauss}
\forall (i,j)\in \{1,\ldots,m+u\}^2 ; W_{ij}=e^{-\frac{\| \obs_i-\obs_j\|^2}{2\sigma^2}}
\end{equation}
\end{itemize}
Par convention, $W_{ii}=0$. Dans la suite de cette section, nous allons exposer un ensemble de techniques semi-supervisées basées sur la propagation des étiquettes dans les graphes. 

\subsubsection{Propagation des étiquettes}
Une idée simple pour tirer parti de $G$ construit sur les exemples est de propager les étiquettes des exemples à travers le graphe. Aux n\oe{}uds $1,\ldots, m$ associés aux exemples étiquetés sont attribués des étiquettes de classe,  $+1$ ou $-1$, de ces exemples ; et aux n\oe{}uds associés aux exemples non étiquetés $m+1, \ldots, m+u$ est affectée l'étiquette~$0$. Les algorithmes proposés suivant ce cadre, appelés algorithmes de propagation des étiquettes (ou \textit{label spreading})\index{propagation!des étiquettes}\index{label spreading|see{propagation des étiquettes}}, sont assez similaires; ils propagent l'étiquette de chaque n\oe{}ud du graphe à ses voisins \citep{zhu:2002, zhu:2003, zhou:2004}. Leur objectif est que les étiquettes trouvées, $\tilde{Y}=(\tilde{Y}_m,\tilde{Y}_u)$, soient cohérentes avec les étiquettes de classes des exemples étiquetés, $Y_m=(y_1,\ldots,y_m)$, mais aussi avec la géométrie des données induite par la structure du graphe $G$ et exprimée par la matrice $\boldsymbol{W}$. 

La consistance entre les étiquettes initiales des exemples étiquetés, $Y_m$, et les étiquettes estimées pour ces exemples, $\tilde{Y}_m$, est mesurée par :
\begin{eqnarray}
\sum_{i=1}^m (\tilde{y}_i - y_i)^2 &=&\|\tilde{Y}_m-Y_m\|^2 \nonumber \\
                                                  &=&\|\boldsymbol{S}\tilde{Y}-\boldsymbol{S} Y\|^2 \label{ConsistanceLabel}
\end{eqnarray}
où $\boldsymbol{S}$ est la matrice par blocs diagonale\index{matrice!par blocs} avec ses $m$ premiers éléments diagonaux égaux à~$1$ et ses autres éléments tous nuls.

La cohérence avec la géométrie des exemples, quant à elle, suit l'hypothèse de continuité (ou de variété)\index{hypothèse!de continuité}\index{hypothèse!de variété}. Elle consiste à pénaliser les changements rapides dans $\tilde{Y}$ entre les exemples proches, étant donnée la matrice~$\boldsymbol{W}$. Cette dernière est ainsi mesurée par :
\begin{eqnarray}
\frac{1}{2}\sum_{i=1}^{m+u} \sum_{j=1}^{m+u} W_{ij}(\tilde{y}_i-\tilde{y}_j)^2 & =&  \frac{1}{2}\left(2\sum_{i=1}^{m+u}\tilde{y}_i^2\sum_{j=1}^{m+u}W_{ij}-2\sum_{i,j=1}^{m+u}W_{ij}\tilde{y}_i\tilde{y}_j\right) \nonumber\\
&=& \tilde{Y}(\boldsymbol{D}\ominus\boldsymbol{W})\tilde{Y} \label{ConsistanceGeom}
\end{eqnarray}
où $\boldsymbol{D}=[D_{ij}]$ est la matrice diagonale définie par $D_{ii}=\displaystyle{\sum_{j=1}^{m+u} W_{ij}}$, $\ominus$ représente la soustraction matricielle terme à terme et $(\boldsymbol{D}\ominus\boldsymbol{W})$ est appelée la matrice laplacienne non normalisée\index{matrice!laplacienne}. 


La fonction-objectif considérée exprime ainsi un compromis entre ces deux termes (eq.~\ref{ConsistanceLabel} et \ref{ConsistanceGeom}) :
\begin{equation}
\label{criterepropage1}
\Delta(\tilde{Y})=\|\boldsymbol{S}\tilde{Y}-\boldsymbol{S} Y\|^2 + \lambda \tilde{Y}(\boldsymbol{D}\ominus\boldsymbol{W})\tilde{Y}
\end{equation}
où $\lambda\in(0,1)$ module ce compromis. La dérivée de la fonction-objectif est ainsi :
\begin{eqnarray*}
\frac{\partial \Delta(\tilde{Y})}{\partial \tilde{Y}}&=2\left[\boldsymbol{S}(\tilde{Y}-Y)+\lambda (\boldsymbol{D}\ominus\boldsymbol{W}) \tilde{Y} \right] \\
&=2\left[\left(\boldsymbol{S} \oplus \lambda (\boldsymbol{D}\ominus\boldsymbol{W}) \right) \tilde{Y} - \boldsymbol{S} Y \right]
\end{eqnarray*}
où $\oplus$ est l'addition matricielle terme à terme. De plus, la matrice hessienne\index{hessienne} de la fonction-objectif :
\[
\frac{\partial^2 \Delta(\tilde{Y})}{\partial \tilde{Y}\partial \tilde{Y}^{\top}} = 2\left(\boldsymbol{S} \oplus\lambda (\boldsymbol{D}\ominus\boldsymbol{W}) \right)
\]
est positive définie, ce qui assure que le minimum de  $\Delta(\tilde{Y})$ est atteint lorsque sa dérivée s'annule, soit :
\begin{equation}
\label{SolutionGraph}
\tilde{Y}^*=(\boldsymbol{S}\oplus\lambda (\boldsymbol{D}\ominus\boldsymbol{W}))^{-1}\boldsymbol{S} Y
\end{equation}

\medskip

\begin{algorithm}[h!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Init}{Initialisation}
    \SetKwInOut{Sort}{Sortie}
\caption{Propagation des étiquettes pour l'apprentissage semi-supervisé\index{apprentissage!semi-supervisé}}% \citep{Zhou04}

\Entr{des bases d'entraînement étiquetée $\TrnSet$ et non étiquetée $\ulda$} \textbf{Initialisation}: $t
\leftarrow 0$ \\ 
estimer la matrice de similarité $\boldsymbol{W}$ (eq.~\ref{MatGauss}) (pour $i\neq j, W_{ii}\leftarrow 0$) \\
construire la matrice $\boldsymbol{N}\leftarrow \boldsymbol{D}^{-1/2}\boldsymbol{W}\boldsymbol{D}^{-1/2}$ où $\boldsymbol{D}$ est la matrice diagonale définie par $D_{ii}\leftarrow \sum_{j} W_{ij}$\\
poser $\tilde Y^{(0)}\leftarrow (y_1,\ldots,y_m,0,0,\ldots,0)$\\
choisir le paramètre $\alpha\in(0,1)$ \\
\Repeter{convergence}{
  $\tilde Y^{(t+1)}\leftarrow \alpha\boldsymbol{N}\tilde Y^{(t)}+(1-\alpha)\tilde Y^{(0)}$
  $t\leftarrow t+1$
}

\Sort{soit $\tilde{Y}^*=(y^*_1,\ldots,y^*_{m+u})$ le vecteur après convergence. Attribuer des étiquettes de classes aux exemples $\obs_i\in\ulda$ suivant le signe de  $y^*_i$}
\label{labelpropagation}
\end{algorithm}

\smallskip

Nous remarquons que les pseudo-étiquettes des exemples non étiquetés sont ainsi obtenues par une simple inversion matricielle et que cette matrice ne dépend que de la matrice laplacienne non normalisée. Les autres techniques basées sur la propagation des étiquettes sont une variante de la formulation précédente. Nous pouvons notamment citer celle proposée par \citep{zhou:2004} qui est une approche itérative (algorithme \ref{labelpropagation}) où, à chaque itération, un n\oe{}ud $i$ du graphe reçoit une contribution de son voisin $j$  (sous forme d'une pondération normalisée du poids de l'arête $(i,j)$), avec en plus une faible contribution  de son étiquette initiale. Soit la règle de mise à jour :
\begin{equation}
\label{updaterulepropage}
\tilde Y^{(t+1)}= \alpha\boldsymbol{N}\tilde Y^{(t)}+(1-\alpha)\tilde Y^{(0)}
\end{equation}
où $\tilde{Y}^{(0)}=(\underbrace{y_1,\ldots,y_m}_{=Y_m},\underbrace{0,0,\ldots,0}_{=Y_u})$ est le vecteur des étiquettes initiales, $\boldsymbol{D}$ est la matrice diagonale définie par $D_{ii}= \sum_{j} W_{ij}$, $\boldsymbol{N}= \boldsymbol{D}^{-1/2}\boldsymbol{W}\boldsymbol{D}^{-1/2}$ est la matrice des poids normalisée et $\alpha$ est une valeur réelle dans $(0,1)$. La preuve de convergence de l'algorithme~(\ref{labelpropagation}) suit la règle de mise à jour (eq.~\ref{updaterulepropage}). En effet, après $t$ itérations, nous avons :
\begin{equation}
\label{updaterulepropage2}
\tilde Y^{(t+1)}= (\alpha\boldsymbol{N})^t\tilde Y^{(0)}+(1-\alpha)\sum_{l=0}^t (\alpha\boldsymbol{N})^l\tilde Y^{(0)}
\end{equation}
Par définition de la matrice diagonale $\boldsymbol{D}$, la matrice carrée $\boldsymbol{N}$ est la matrice laplacienne normalisée dont les éléments sont des réels positifs compris entre $0$ et $1$ et la somme des éléments de chacune de ses lignes vaut~$1$. La matrice $\boldsymbol{N}$ est ainsi par définition une matrice stochastique (ou une matrice de Markov) et ses valeurs propres sont  inférieures ou égales à $1$\index{matrice!stochastique} \citep[ch. 2]{latouche:1999}. Comme $\alpha$ est un réel positif strictement inférieur à 1, les valeurs propres de la matrice $\alpha \boldsymbol{N}$ sont toutes strictement inférieures à~1 et nous avons $\displaystyle{\lim_{t\rightarrow \infty} (\alpha \boldsymbol{N})^t=0}$. De même, $(\alpha \boldsymbol{N})^l; l\in \mathbb{N}$ est une suite géométrique matricielle de raison $\alpha \boldsymbol{N}$ et donc $\displaystyle{\lim_{t\rightarrow \infty} \sum_{l=0}^t (\alpha\boldsymbol{N})^l=(\boldsymbol{I}\ominus\alpha\boldsymbol{N})^{-1}}$, où $\boldsymbol{I}$ est la matrice identité. D'après ces résultats, le vecteur des pseudo-étiquettes des exemples $\tilde Y^{(t)}$ converge alors vers :
\begin{equation}
\label{updaterulepropage3}
\lim_{t\rightarrow \infty} \tilde Y^{(t+1)} = \tilde Y^*=(1-\alpha)(\boldsymbol{I}\ominus\alpha\boldsymbol{N})^{-1} \tilde Y^{(0)}
\end{equation}
La fonction-objectif correspondant à ce problème est la suivante :
\begin{eqnarray}
\Delta_n(\tilde{Y})&=&\| \tilde{Y}-\boldsymbol{S}Y\|^2 + \frac{\lambda}{2}\sum_{i=1}^{m+u}\sum_{j=1}^{m+u} W_{ij}\left(\frac{\tilde{y}_i}{\sqrt{D_{ii}}}-\frac{\tilde{y}_j}{\sqrt{D_{jj}}}\right)^2 \label{eq:objectiflabelspreading} \\
&=& \| \tilde{Y}_m-Y_m\|^2+\| \tilde{Y}_u\|^2+\lambda \tilde{Y}^\top (\boldsymbol{I}\ominus\boldsymbol{N}) \tilde{Y} \nonumber \\
&=& \| \tilde{Y}_m-Y_m\|^2+\| \tilde{Y}_u\|^2+ \lambda \left(\boldsymbol{D}^{-1/2}\tilde{Y}\right)^{\top} (\boldsymbol{D}\ominus\boldsymbol{W})  \left(\boldsymbol{D}^{-1/2}\tilde{Y}\right) \nonumber
\end{eqnarray}
En effet, la dérivée de cette fonction par rapport aux pseudo-étiquettes $\tilde Y$ est :
\[
\frac{\partial \Delta_n(\tilde{Y})}{\partial \tilde{Y}}=2\left[ \tilde{Y}-\boldsymbol{S}Y + \lambda\left(\tilde{Y}-\boldsymbol{N}\tilde{Y}\right)\right]
\]
et elle s'annule pour :
\[
\tilde{Y}=\left((1+\lambda)\boldsymbol{I}\ominus\lambda\boldsymbol{N}\right)^{-1}\boldsymbol{S}Y
\]
qui pour $\lambda=\alpha / (1-\alpha)$ est la même  solution que celle trouvée par l'algorithme (\ref{labelpropagation}) après convergence (eq.~\ref{updaterulepropage3}). Par rapport au critère (eq.~\ref{criterepropage1}), les deux différences majeures sont $(a)$ la matrice laplacienne normalisée et $(b)$ le terme $\| \tilde{Y}_m-Y_m\|^2+\| \tilde{Y}_u\|^2$ qui contraint, non seulement les pseudo-étiquettes à s'accorder aux étiquettes des exemples étiquetés, mais aussi  les pseudo-étiquettes des exemples non étiquetés à ne pas atteindre de grandes  valeurs.
\subsubsection{Marche aléatoire markovienne}
Une variante à l'algorithme de la propagation des étiquettes  (algorithme~\ref{labelpropagation}) introduite par \citep{szummer:2002}  considère une marche aléatoire markovienne\footnote{Une marche aléatoire modélise les systèmes avec une dynamique discrète composée d'une succession de pas aléatoires \citep{montroll:1956}. Le caractère markovien du processus traduit la décorrélation complète entre les pas aléatoires.} sur le graphe~$G$\index{marche aléatoire}\index{random walk|see{marche aléatoire}}, définie avec des probabilités de transition entre les n\oe{}uds $i$ et $j$ estimées sur la matrice de similarité par  :
\begin{equation}
\label{probatransition}
\forall (i,j), p_{ij}=\frac{W_{ij}}{\sum_{l} W_{il}}
\end{equation}
La similarité $W_{ij}$ est définie avec un noyau gaussien (eq. \ref{MatGauss}) pour les voisins des n\oe{}uds $i$ et $j$ et elle est fixée à 0 partout ailleurs. L'algorithme proposé initialise d'abord les probabilités d'appartenance à la classe $+1$ pour tous les n\oe{}uds du graphe, $\mathbb{P}(y=1\mid i), i\in V$ en utilisant l'algorithme~EM et estime, pour chaque exemple $\obs_j$, la probabilité $\mathbb{P}^{(t)}(y_s=1\mid j)$ à partir d'un exemple de classe $y_s=1$ pour arriver à l'exemple~$\obs_j$  après $t$ marches aléatoires, définie comme : 
\begin{equation}
\label{eq:ProbaRandomWalk}
\mathbb{P}^{(t)}(y_s=1\mid j)=\sum_{i=1}^{m+u} \mathbb{P}(y=1\mid i)\mathbb{P}_{1\rightarrow t}(i\mid j)
\end{equation}
où $\mathbb{P}_{1\rightarrow t}(i\mid j)$ est la probabilité de partir du n\oe{}ud $i$ pour arriver au n\oe{}ud $j$ après $t$~marches aléatoires. Au n\oe{}ud $j$ est alors attribuée la pseudo-étiquette de classe $+1$, dans le cas où $\mathbb{P}^{(t)}(y_s=1\mid j)>\frac{1}{2}$, et $-1$ sinon. En pratique, le choix de la valeur de $t$ a un grand impact sur les performances de l'algorithme de la marche aléatoire et il n'est pas facile à faire. Une alternative, proposée dans \citep{zhu:2002, zhu:2003}, est d'attribuer une pseudo-étiquette de classe au n\oe{}ud $i$ suivant la probabilité d'arriver à un n\oe{}ud d'étiquette $+1$ en partant de ce n\oe{}ud $i$ pour arriver au n\oe{}ud étiqueté, $\mathbb{P}(y_e=1\mid i)$, en effectuant une marche aléatoire. Dans le cas où l'exemple $\obs_i$ est étiqueté, nous avons :
\[
\mathbb{P}(y_e=1\mid i) =
\begin{cases}
1& \text{~si~} y_i=1,\\
0& \text{~sinon.}
\end{cases}
\]
Si $\obs_i$ est non étiqueté, nous avons la relation suivante :
\begin{equation}
\label{eq:ProbaNonEtiq}
\mathbb{P}(y_e=1\mid i) =\sum_{j=1}^{m+u} \mathbb{P}(y_e=1\mid j)p_{ij}
\end{equation}
où $p_{ij}$ est la probabilité de transition définie dans l'équation \ref{probatransition}. En posant $\forall~i,~\tilde z_i~=~\mathbb{P}(y_e~=~1\mid i)$ et $\tilde Z=(\tilde Z_m~~\tilde Z_u)$ le vecteur correspondant divisé en deux parties étiquetée et non étiquetée, puis en subdivisant aussi les matrices~$\boldsymbol{D}$ et $\boldsymbol{W}$ en quatre parties :
\[
\boldsymbol{D}=\begin{pmatrix}
\boldsymbol{D}_{mm} & 0 \\
0 & \boldsymbol{D}_{uu}
\end{pmatrix}, ~~~~~~~~~~~~
\boldsymbol{W}=\begin{pmatrix}
\boldsymbol{W}_{mm} & \boldsymbol{W}_{mu} \\
\boldsymbol{W}_{um} & \boldsymbol{W}_{uu}
\end{pmatrix}
\]
l'équation (\ref{eq:ProbaNonEtiq}) peut s'écrire :
\begin{eqnarray}
\tilde Z_u&=& \left( \boldsymbol{D}^{-1}_{uu} \boldsymbol{W}_{um}~~\boldsymbol{D}^{-1}_{uu} \boldsymbol{W}_{uu}\right)\left(\begin{array}{c} \tilde Z_m \\ \tilde Z_u\end{array}\right) \nonumber \\
&=&\boldsymbol{D}^{-1}_{uu} \left( \boldsymbol{W}_{um}\tilde Z_m + \boldsymbol{W}_{uu}\tilde Z_u\right) \label{EqAA}
\end{eqnarray}
L'équation (\ref{EqAA}) mène au système linéaire suivant : 
\begin{equation}
\label{eq:SysLin}
(\boldsymbol{D}\ominus \boldsymbol{W})_{uu}\tilde{Z}_u=\boldsymbol{W}_{um}\tilde{Z}_m
\end{equation}
Nous remarquons que si $(\tilde Z_m \tilde Z_u)$ est solution de l'équation précédente, alors $(\tilde Y_m \tilde Y_u)$ définie comme :
\begin{eqnarray*}
\tilde Y_m&=&2\tilde{Z}_m- \boldsymbol{1}_m=Y_m\\
\tilde Y_u&=&2\tilde{Z}_u- \boldsymbol{1}_u
\end{eqnarray*} 
où $\boldsymbol{1}_m$ et $\boldsymbol{1}_u$ sont respectivement des vecteurs de dimension $m$ et $u$ dont tous les éléments sont égaux à $1$, en est aussi une solution. Cette dernière égalité permet d'exprimer le système linéaire par rapport aux vecteurs des étiquettes et des pseudo-étiquettes des exemples, soit :
\[
\tilde Y_u=(\boldsymbol{D}\ominus \boldsymbol{W})^{-1}_{uu} \boldsymbol{W}_{um} Y_m
\]



\subsection{Modèles de mélange}
La prédiction semi-supervisée avec des modèles génératifs implique l'estimation de la densité conditionnelle $\mathbb{P}(\obs \mid y, \Theta)$ en utilisant, comme dans le cas non supervisé, l'algorithme EM\index{apprentissage!semi-supervisé!modèles de mélange} pour\index{algorithme!EM} estimer les paramètres $\Theta$ du modèle. Toutefois, la différence majeure avec le partitionnement non supervisé est que les variables cachées associées aux exemples étiquetés sont connues à l'avance et correspondent aux étiquettes de classes de ces exemples. L'hypothèse de base de ces modèles est ainsi l'hypothèse de partition qui stipule que, si deux exemples $\obs_1$ et $\obs_2$ sont dans le même groupe, ils sont alors susceptibles d'appartenir à  la même classe $y$. Cette hypothèse pourrait se comprendre de la façon suivante : s'il existe un groupe formé par un ensemble d'exemples dense, il est alors improbable qu'ils puissent appartenir à différentes classes. Ceci n'est pas équivalent à dire qu'une classe est formée par un seul groupe  d'exemples, mais qu'il est improbable de trouver deux exemples appartenant à différentes classes dans le même groupe.  Nous pouvons ainsi interpréter l'apprentissage semi-supervisé\index{apprentissage!semi-supervisé} avec des modèles génératifs  $(a)$~comme une classification supervisée où l'on dispose de l'information additionnelle sur la densité de probabilité $\mathbb{P}(\obs)$ \index{densité de probabilité} des données, ou $(b)$~comme un partitionnement avec de l'information additionnelle sur les étiquettes de classes d'un sous-ensemble d'exemples \citep{basu:2002}. Dans le cas où l'hypothèse générant les données est connue, les modèles génératifs peuvent devenir très performants.

\subsection{Modèles discriminants}
      L'inconvénient des modèles génératifs\index{apprentissage!semi-supervisé!modèles discriminants} est que, dans le cas où les hypothèses distributionnelles ne sont plus valides, leur utilisation tendra à détériorer leurs performances par rapport au cas où seuls les exemples étiquetés sont utilisés pour apprendre un modèle \citep{cohen:2004}. Ce constat a motivé de nombreux travaux pour s'affranchir de ces hypothèses. Les premiers travaux proposés suivant ce cadre ont utilisé des modèles discriminants estimant des probabilités a posteriori de classes pour les exemples en entrée, par exemple la régression logistique, et ils ont montré que la maximisation de la vraisemblance classifiante semi-supervisée\index{vraisemblance!classifiante} est équivalente à la minimisation du risque empirique sur les exemples étiquetés et pseudo-étiquetés. L'extension de l'algorithme CEM\index{algorithme!CEM}\index{classification!EM|see{algotithme CEM}} semi-supervisé au cas discriminant serait dans ce cas  équivalente à la technique dite de décision dirigée (ou l'algorithme auto-apprenant ou encore \textit{self-training}) proposée dans le cadre du traitement adaptatif du signal  et qui consiste à utiliser les sorties prédites par le système pour des exemples non étiquetés afin de construire des sorties désirées \citep{fralick:1967,patrick:1970}. Ce processus de pseudo-étiquetage et d'apprentissage de modèle est répété jusqu'à ce qu'il n'y ait plus de changement sur l'étiquetage des exemples. Dans le cas où les pseudo-étiquettes de classe sont attribuées aux exemples non étiquetés, en seuillant les sorties du classifieur correspondant à ces exemples, on peut montrer que l'algorithme auto-apprenant fonctionne suivant l'hypothèse de partition\index{hypothèse!de partition}. 
      
      \section{Exercices}
\begin{itemize}[itemindent=20mm]
\Quest{8.1} Dans cet exercice, nous allons nous intéresser à la convergence de l'algorithme \index{algorithme!Adaboost} Adaboost (algorithme \ref{algo:chap5:Boosting}). \`A l'itération $t$, le coefficient~$\alpha_t$ est choisi de façon à ce que le facteur de normalisation $Z_t~=~\sum_{i=1}^m D_t(i) e^{-a_t y_i f_t(\obs_i)} $ soit minimal.
\begin{itemize}
\item[a)] En considérant le fait que les prédictions du \index{classifieur!faible}classifieur faible, $f_t$, sont dans $\{-1,+1\}$, montrer que ce facteur de normalisation peut s'écrire sous la forme suivante:
\[
 Z_t=\sum_{i:y_i\neq f_t(\obs_i)} D_t(i) e^{a_t} + \sum_{i:y_i= f_t(\obs_i)} D_t(i) e^{-a_t}
 \]
\item[b)] En déduire que~:
\[
a_t=\frac{1}{2}\ln \frac{1-\epsilon_t}{\epsilon_t}
\]
avec $\epsilon_t=\sum_{i:f_t(\obs_i)\neq y_i} D_t(i)$.
\item[c)] Avec la valeur de $a_t$ trouvée à la question précédente, montrer que:
\[
Z_t=2\sqrt{\epsilon_t (1-\epsilon_t)}
\]
\item[d)] En posant $\gamma_t=\frac{1}{2}-\epsilon_t$, montrer que si $\epsilon_t < \frac{1}{2}$ nous avons:
\[
Z_t \leq e^{-2\gamma_l^2}
\]
\item[e)] Montrer alors que l'erreur empirique du classifieur final est bornée par:
\[
\frac{1}{m} \sum_{i=1}^m \Predi{y_i \neq F(\obs_i)} \leq \frac{1}{m} \sum_{i=1}^m e^{-y_i H(\obs_i)}
\]
où $H(\obs)=\sum_{t=1}^T \alpha_t f_t(\obs)$ et $F(\obs)=\text{sign} \left(H(\obs)\right)$.
\item[f)] Montrer que: 
\[
\frac{1}{m} \sum_{i=1}^m e^{-y_i H(\obs_i)} = \sum_{i=1}^m D_2(i) Z_1 \prod_{t>1} e^{-y_i \alpha_t f_t(\obs_i)}
\]
\item[g)] Par récursion, en déduire que: 
\[
\frac{1}{m} \sum_{i=1}^m e^{-y_i H(\obs_i)} = \prod_{t=1}^T Z_t
\]
\item[h)] En déduire que, si les classifieurs faibles donnent des prédictions meilleures que la prédiction aléatoire ($\forall t, \epsilon_t<\frac{1}{2}$), la borne supérieure de l'erreur empirique du classifieur final $F$ décroît alors de façon exponentielle en fonction du nombre d'itérations.
\end{itemize}
\Quest{8.2} Dans cet exercice, nous allons nous intéresser à la règle de mise à jour de l'algorithme d'apprentissage du modèle logistique (eq. \ref{CondRegLog}). 
Pour un ensemble de poids $\boldsymbol \lambda$ donné, le but de la règle de mise à jour est de trouver de nouveaux poids $\boldsymbol \lambda+\boldsymbol \delta$ qui conduisent à un nouveau modèle de plus faible erreur empirique. La différence des erreurs empiriques après et avant la phase de mise à jour est~:
\[
\hat R^e_m(\boldsymbol \lambda+\boldsymbol \delta, S)-\hat R^e_m(\boldsymbol \lambda, S)=\underbrace{\frac{1}{m} \left(\sum_{i=1}^m e^{-y_i h_{\boldsymbol \lambda}(\obs_i)} (e^{-y_i h_{\boldsymbol \delta}(\obs_i)} -1) \right)}_{\bar R(\boldsymbol \lambda, \boldsymbol \delta)}
\]
\begin{itemize}
\item[a)] En utilisant l'inégalité de Jensen, montrer que~:
\[
\bar R(\boldsymbol \lambda, \boldsymbol \delta) \leq \underbrace{\!\frac{1}{m}\! \left(\sum_{i=1}^m e^{-y_i h_{\boldsymbol \lambda}(\obs_i)} (\sum_{j=1}^d w_{ij} e^{-y_i \delta_j} -1) \right)}_{\mathcal E(\boldsymbol \lambda,\boldsymbol \delta)}
\]

\item[b)] Montrer que la fonction $\delta \mapsto \mathcal E(\boldsymbol \lambda,\boldsymbol \delta)$ admet un minimum unique négatif.


\item[c)] Montrer que ce minimum est atteint, pour cette valeur de $\delta$~:
\[
\forall j, \frac{\partial \mathcal E}{\partial \delta_j}=0 \Leftrightarrow \delta_j=\frac{1}{2}\ln \frac{\sum_{i: y_i=1} w_{ij}e^{-\left\langle \obs_i,\boldsymbol \lambda \right\rangle}}{\sum_{i: y_i=-1} w_{ij}e^{\left\langle \obs_i,\boldsymbol \lambda \right\rangle}}
\]

\end{itemize}

\Quest{8.3}
Différents algorithmes ont été proposés pour la résolution du problème primal des séparateurs à vaste marge (eq. \ref{eq:SVM:Primal}) dont l'algorithme PEGASOS (\textit{Primal Estimated sub-Gradient SOlver for SVM}) \cite{shalev:2011} qui est sans doute l'un des plus connus, résumé ci-après~:

\begin{algorithm}[h!]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme PEGASOS \cite{shalev:2011}\index{algorithme!PESGASOS}}
    \Entr{\begin{itemize}\item Ensemble d'apprentissage $S=\left(\obs_i,y_i\right)_{1\leq i \leq m}$ \item  constant $\lambda>0$ \item un nombre maximum d'itérations $T$\end{itemize}}
       \textbf{Initialisation :}
\begin{itemize} \item  $\w^{(1)} \leftarrow 0$\end{itemize}
    \Pour{$t=1,\ldots,T$}{
      \begin{itemize}
        \item Poser $S^+_t=\{(\obs,y)\in S; y\langle\w^{(t)},\obs\rangle<1\}$
        \item Poser  $\eta_t=\frac{1}{\lambda\times t}$
        \item Mettre à jour $\w^{(t+1)}\leftarrow (1-\lambda \eta_t)\w^{(t)}+\frac{\eta_t}{m}\sum_{(\obs,y)\in S^+_t} y\obs$
\end{itemize}    
    }
    \Sort{$\w^{(T+1)}$}
\label{algo:pegasos}
\end{algorithm} 

En commençant avec un vecteur poids nul, l'algorithme met à jour itérativement les poids du modèle sur le sous-ensemble des exemples mal classés $S^+_t$ en appliquant la règle suivante:
\begin{equation}
\label{eq:Update}
\forall t, \w^{(t+1)}\leftarrow (1-\lambda \eta_t)\w^{(t)}+\frac{\eta_t}{m}\sum_{(\obs,y)\in S^+_t} y\obs
\end{equation}
où, $\eta_t=\frac{1}{\lambda\times t}$ est le pas d'apprentissage. Dans cet exercice, nous allons étudier les propriétés de convergence de cet algorithme.
\begin{itemize}
\item[a)] Pour une observation donnée $(\obs,y)$ et un classifieur $h\in\mathcal H$, dire pourquoi le signe du produit $yh(\obs)=y\langle\w,\obs\rangle$ est un indicateur de bonne ou de mauvaise classification.
\item[b)] Dessiner l'erreur de classification\index{erreur!de classification} $\ell_b: (h(\obs),y)\mapsto \mathbbm{1}_{yh(\obs)<0}$ et l'erreur de Hinge.\index{erreur!de Hinge} 
\begin{equation}
\label{eq:instloss}
\ell(h(\obs),y)=\max(0,1-y h(\obs))
\end{equation}
par rapport au produit $yh(\obs)$, i.e. L'erreur en ordonnée et le produit $yh(\obs)$ en abscisse. 
\item[c)] Pour un exemple donné $(\obs,y)$, que représente $\frac{|h(\obs)|}{\|\w\|}$ ?
\item[d)] Pourquoi la fonction-objectif  (eq. \ref{eq:SVM:Primal}) admet-elle un seul minimiseur $\w^\star\in\mathbb{R}^d$?
\item[e)] Expliquer pourquoi, à la première itération, $S_1$ est tout l'ensemble d'apprentissage~: $S_1=S$.
\item[f)] Montrer que la règle de mise à jour \eqref{eq:Update} suit la règle de la descente du gradient:
\[
\forall t, \w^{(t+1)}\leftarrow \w^{(t)}-\eta_t \nabla_t 
\]
où $\nabla_t =\nabla_t \hat{\mathcal{L}}_m(S,\w^{(t)})$ est le gradient de la fonction-objectif (eq. \ref{eq:SVM:Primal}) au point $\w^{(t)}$.
\item[g)] Pour deux poids consécutifs $\w^{(t)}$ et $\w^{(t+1)}$, montrer que~:
\[
\|\w^{(t)}-\w^\star\|^2-\|\w^{(t+1)}-\w^\star\|^2 = 2\eta_t\langle\w^{(t)}-\w^\star,\nabla_t\rangle-\eta_t^2\|\nabla_t\|^2 
\]
\item[h)] La fonction objectif est dite $\lambda$-fortement convexe\index{fortement convexe} si elle vérifie~:
\[
\forall u\in\mathbb{R}^d, \langle\w^{(t)}-u, \nabla_t\rangle\geq \hat{\mathcal L}(\w^{(t)})-\hat{\mathcal L}(u)+\frac{\lambda}{2}\|\w^{(t)}-u\|^2
\]
De cette propriété et de la question précédente, en déduire que~:
\begin{align*}
\sum_{t=1}^T \left(\hat{\mathcal L}(\w^{(t)})-\hat{\mathcal L}(\w^\star)\right) \leq & \sum_{t=1}^T\left(\frac{\|\w^{(t)}-\w^\star\|^2-\|\w^{(t+1)}-\w^\star\|^2}{2\eta_t}-\frac{\lambda}{2}\|\w^{(t)}-\w^\star\|^2\right)\\ 
& +\frac{1}{2}\sum_{t=1}^T\eta_t\|\nabla_t\|^2
\end{align*}

\item[i)] Montrer que, pour deux itérations consécutives $t$ et $t+1$, nous avons~:
\begin{align*}
\sum_{j=t}^{t+1}\left(\frac{\|\w^{(j)}-\w^\star\|^2-\|\w^{(j+1)}-\w^\star\|^2}{2\eta_j}-\frac{\lambda}{2}\|\w^{(j)}-\w^\star\|^2\right) = \\
\frac{\lambda(t-1)}{2}\|\w^{(t)}-\w^\star\|^2 - \frac{\lambda(t+1)}{2}\|\w^{(t+2)}-\w^\star\|^2
\end{align*}

\item[j)] Déduire des deux questions précédentes que~:
\begin{align*}
\sum_{t=1}^T \left(\hat{\mathcal L}(\w^{(t)})-\hat{\mathcal L}(\w^\star)\right) &\leq\frac{ -\lambda T}{2}\|\w^{(T+1)}-\w^\star\|^2+\frac{1}{2}\sum_{t=1}^T\eta_t\|\nabla_t\|^2\\
&\leq \frac{1}{2}\sum_{t=1}^T\eta_t\|\nabla_t\|^2
\end{align*}
\item[k)] Supposons que le pas d'apprentissage $\eta_t=\frac{1}{\lambda t}, \forall t$ et que les exemples de la base d'entraînement sont contenus dans un hypersphère\index{hypersphère} de rayon~$R$, si, à chaque itération, les poids $\w^{(t)}$ sont normalisés de façon à ce que $\|\w^{(t)}\|\leq \frac{1}{\sqrt{\lambda}}$ montrer que~:
\[
\|\nabla_t\|\leq \sqrt{\lambda}+R
\]
En déduire que, pour $T\geq 3$, nous avons~:
\[
\frac{1}{T}\sum_{t=1}^T \hat{\mathcal L}(\w^{(t)}) \leq \frac{1}{T}\sum_{t=1}^T \hat{\mathcal L}(\w^\star)+\frac{c(1+\ln(T))}{2\lambda T}
\]
où $c=(\sqrt{\lambda}+R)^2$
\item[l)] D'après l'inégalité de Jensen et la convexité de la fonction-objectif, nous avons:
\[
\hat{\mathcal L}\left(\frac{1}{T}\sum_{t=1}^T\w^{(t)}\right)\leq \frac{1}{T}\sum_{t=1}^T \hat{\mathcal L}(\w^{(t)})
\]
En utilisant cette inégalité et la question précédente, montrer que~:
\[
\hat{\mathcal L}(\w^\star)\leq \hat{\mathcal L}(\tilde{\w}) \leq \hat{\mathcal L}(\w^\star)+\frac{c(1+\ln(T))}{2\lambda T}
\]
où $\tilde{\w}=\frac{1}{T}\sum_{t=1}^T \w^{(t)}$ et en déduire finalement que~:
\[
\mathop{\lim}_{t\to \infty}\frac{1}{T}\sum_{t=1}^T \w^{(t)}=\w^\star
\]


\end{itemize}


\end{itemize}

