\documentclass[pdf,colorBG,slideColor,accumulate,asi]{prosper}
%\documentclass{prosper}
\usepackage{amsmath}
\usepackage{pstricks,pst-node,pst-text,pst-3d}
\usepackage[all]{xy}
\usepackage[T1]{fontenc}
\usepackage{inputenc}
\usepackage[francais]{babel}
\usepackage{graphicx}
% =================================================================================
% à insérer dans le préambule.
% définit la commande \figgauche
%\figgauche{LargeurImage}{FichierImage.eps}{TexteADroite}
%
\newlength\jataille
\newcommand{\figgauche}[3]%
{\jataille=1\linewidth\advance\jataille by -#1
      \advance\jataille by -.5cm
      \begin{minipage}[c]{#1}
      \includegraphics[scale = 0.5, width=#1]{#2}
      \end{minipage}\hfill
      \begin{minipage}[c]{\jataille} #3
      \end{minipage}
		~\newline{}
}

% définit la commande \moncadre
%\moncadre{TexteAencahjhjhjdrer}
%
\newcommand{\moncadre}[1]%
{\fbox{
    \begin{minipage}{\linewidth} #1
    \end{minipage}
}}

\def\Ind{{\cal J}}
\def\hdots{{.\;.\;.}}
\def\balpha{{\mathbf{\alpha}}}
\def\bbeta{{\mathbf{\beta}}}
\def\u{{\mathbf{u}}}
\def\v{{\mathbf{v}}}
\def\m{{\mathbf{m}}}
\def\r{{\mathbf{r}}}
\def\u{{\mathbf{u}}}
\def\w{{\mathbf{w}}}
\def\x{{\mathbf{x}}}
\def\y{{\mathbf{y}}}
\def\a{{\mathbf{a}}}
\def\b{{\mathbf{b}}}
\def\c{{\mathbf{c}}}
\def\dbR{{\mathrm{I\hskip-2.2pt R}}}
\def\dbN{{\mathrm{I\hskip-2.2pt N}}}
\def\esp{{\mathrm{I\hskip-1.5pt E}}}
\def\pr{{\mathrm{I\hskip-2.2pt P}}}
%\def\pr{{p}}  % proba
\def\De{{d}}  % regle de decision
\def\hapr{{\widehat{p}}}
\def\hag{{\widehat{g}}}
\def\hah{{\widehat{h}}}
\def\har{{\widehat{r}}}
\def\haD{{\widehat{d}}}
\def\hatheta{{\widehat{\theta}}}
\def\clF{{\cal{F}}}
\def\clH{{\cal{H}}}
\def\clA{{\cal{A}}}
\def\clG{{C}}
\def\clL{{\cal{L}}}
\def\clN{{\cal{N}}}
%\def\De{{d}}
\def\sign{{\mbox{signe}}}
\def\uneqDelta{\buildrel \Delta \over =}
\def\Un{{\mathrm{{1\hskip-2.6pt I}}}}


% =================================================================================
\title{SVM \\~\\Machines à vecteur support}
\author{Stéphane Canu}
\email {stephane.canu@insa-rouen.fr}
\institution{INSA Rouen -Département ASI - Laboratoire PSI}
\NoFrenchBabelItemize
\DefaultTransition{Replace}
% =================================================================================
\begin{document}
\maketitle

%---------------------------------------------------------------------- SLIDE -
\begin{slide}{A la recherche d'une règle de décision {\em universelle}}

\figgauche{200pt}{pb2Complex.eps}{\scriptsize on cherche un algorithme $\clA$ \\
capable de résoudre \\
$\qquad \qquad$ tous les problèmes \\

l'échantillon $\left(x_i,y_i\right)_{i=1,n} $ 

\vspace{-.2cm}
$$
\underbrace{\pr(err(\clA,x_i,y_i))}_{\mbox{erreur de } \clA}
 \underset{n \rightarrow \infty}{\longrightarrow} \underbrace{\pr_{\mbox{b}}(err)}_{\mbox{erreur de bayes}} $$ 

}
\normalsize
~\newline{}
Tracer la frontière de décision entre ces deux classes~?

\end{slide}

%---------------------------------------------------------------------- SLIDE -
\begin{slide}{Introduction}

\figgauche{200pt}{pb2Complex2.eps}{c'est plus facile... \\ ...avec un peu plus de points}
~\newline{}~\newline{}~\newline{}
Tracez la frontière de décision entre ces deux classes~?

\end{slide}

%---------------------------------------------------------------------- SLIDE -
\overlays{4}{
\begin{slide}{Introduction : le plan}

\figgauche{240pt}{SolSVMGauss.eps}{Une solution \\ $~\quad \Rightarrow$ Quels critères~? \\
%\includegraphics[scale = 0.5, width=200pt]{SolSVMGauss.eps}
\hspace{5cm}
\begin{itemstep}
\item (1) Fidélité%~\newline{} 
\item (2) Régularité
    ~\newline{} 
\item (3) Décision locale%~\newline{} 
\item(4) Points frontière
    ~\newline{}
\end{itemstep}
}

\end{slide}
}
%---------------------------------------------------------------------- SLIDE -
\overlays{4}{
\begin{slide}{Fidélité}

\figgauche{100pt}{SolSVMGauss.eps}{
l'échantillon $\left(x_i,y_i\right)_{i=1,n} \\
y_i \in \{-1,1\}$ (codage -1/1) \\
la fonction de décision : $\mbox{signe}(f(x_i))$  \\
($f$ fonction de discrimination) \\
$\clF=\left\{x \; |\; f(x) = 0   \right\}$ : frontière de décision.
}

%Notations : 

Bien classer tout le monde~: 

\begin{center}
\vspace{.15cm}
$\mbox{signe}(f(x_i)) = y_i \qquad i=1,n \qquad $ \fromSlide*{2}{{\tiny
 critère non dérivable}
}


\vspace{.25cm}
\fromSlide*{2}{
$f(x_i)  y_i \geq 0  \qquad \qquad \; \; \; i=1,n  \qquad $ \fromSlide*{3}{{\tiny solution triviale $f=0$}}
}
\end{center}

\vspace{.25cm}
\fromSlide*{3}{
\moncadre{
$\qquad \qquad \qquad \qquad f(x_i)  y_i \geq \rnode{K}{k}  \qquad k>0, \; i=1,n$
}
}
%~\newline{}
\onlySlide*{4}{~~\hspace{10cm} \rnode{KA}{{\red Marge}}
{\nccurve[linecolor=red,angleA=90,angleB=270]{->}{KA}{K}} }

\onlySlide*{1}{\vspace{2cm}}
\onlySlide*{2}{\vspace{1.5cm}}
\onlySlide*{3}{\vspace{.5cm}}
\onlySlide*{4}{\vspace{.25cm}}
\begin{flushright}
%\item 
\scriptsize
\fbox{\bf (1) Fidélité} - (3) Décision <<~locale~>> \\
%
%\item 
(2) Régularité - (4) Points <<~frontière~>>
\end{flushright}


\end{slide}
}
%---------------------------------------------------------------------- SLIDE -
\overlays{2}{
\begin{slide}{Fidélité et marge}

\figgauche{125pt}{marge.eps}{$f(x_i)  y_i > k  \qquad k>0, \; i=1,n$ \\
$\clF=\left\{x \; |\; f(x) = 0   \right\}$ : frontière \\
Marge : $$\displaystyle \min_{i=1,n} d(\clF,x_i) = \min_{i=1,n} f(x_i)y_i $$
}

\moncadre{
Bien classer tout le monde $(k=1)$~: 
$$f(x_i)  y_i > 1 
\qquad  \; i=1,n$$
}

\onlySlide{2}{ 
1 est la marge minimale
}


\vspace{.25cm}
\begin{flushright}
%\item 
\scriptsize
\fbox{\bf (1) Fidélité} - (3) Décision <<~locale~>> \\
%
%\item 
(2) Régularité - (4) Points <<~frontière~>>
\end{flushright}


\end{slide}
}

%---------------------------------------------------------------------- SLIDE -
\overlays{3}{
\begin{slide}{Fidélité et droit à l'erreur}

\figgauche{100pt}{svmRejet.eps}{ $f(x_i)  y_i > 1 \fromSlide*{2}{-\xi_i} \qquad \fromSlide*{2}{\xi_i>0,}\; i=1,n$ \\
\vspace{.25cm}
%
Introduisons  une variable d'écart $\xi_i$ \\
\onlySlide*{3}{\vspace{-.65cm}  $$\min_{\xi_i} \sum_{i=1}^{n} \xi_i $$  }
}

%Notations : 

\moncadre{
Bien classer {\bf \red a peu près} tout le monde~: 
$$f(x_i)  y_i > 1 
\onlySlide*{1}{\rnode{XI}{\pscirclebox[linecolor=red,linestyle=none]{- \xi_i}  }}
\fromSlide*{2}{\rnode{XI}{\pscirclebox[linecolor=red]{- \xi_i}  } }
\qquad  \xi_i > 0\;, \; i=1,n
$$
}

où \rnode{XIA}{$\xi_i$} est une variable d'écart
\fromSlide*{2}{ {\nccurve[linecolor=red,angleA=90,angleB=270]{->}{XIA}{XI}} }
\onlySlide*{3}{$ \xi_i = 0;  \; \; \; \underbrace{\xi_i \geq 1 }_{\mbox{mal classé}} ; \; \;0<\xi_i<1$}

\vspace{.25cm}
\onlySlide*{1}{\vspace{.5cm}}
\onlySlide*{2}{\vspace{.5cm}}
\begin{flushright}
%\item 
\scriptsize
\fbox{\bf (1) Fidélité} - (3) Décision <<~locale~>> \\
%
%\item 
(2) Régularité - {(4) Points <<~frontière~>>}
\end{flushright}


\end{slide}
}


%---------------------------------------------------------------------- REGULARITE -
%----------------------------------------------------------------------  -
\overlays{4}{
\begin{slide}{Régularité}

\figgauche{125pt}{regulier.eps}{ $f(x_i)  y_i > 1 - \xi_i \qquad \xi_i>0, \; i=1,n$ \\
$ \displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i $ \\
\onlySlide*{1}{les deux solutions vérifient $\displaystyle  \xi_i =0, \; i=1,n$}  
\onlySlide*{2}{les deux solutions vérifient $\displaystyle  \xi_i =0, \; i=1,n$}  
\onlySlide*{3}{les deux solutions vérifient $\displaystyle  \xi_i =0, \; i=1,n$}  
\onlySlide{4}{$\displaystyle \min_f \; \|f\|_\clH$}  
}

par exemple 
\begin{itemstep}
\item <<~l'énergie~>> de $f$ : la norme de sa dérivée ({\it cf} les splines)
\item la longueur de $f$ - la taille du code calculant $f$
\item une norme de $f$ au sens de $\clH$ (défini a priori): $\|f\|_\clH$
\item un terme de régularisation : une fonctionelle positive assurant l'unicité de la solution
\end{itemstep}

%\vspace{.5cm}
\begin{flushright}
\scriptsize
(1) Fidélité - (3) Décision <<~locale~>> \\
\fbox{\bf (2) Régularité} - (4) Points <<~frontière~>>
\end{flushright}

\end{slide}
}

%---------------------------------------------------------------------- REGULARITE -
%----------------------------------------------------------------------  -
\overlays{4}{
\begin{slide}{Régularité et marge}
\vspace{-.25cm}
\onlySlide*{1}{ \figgauche{100pt}{marge.eps}{$f(x_i)  y_i > 1 - \xi_i  \qquad \xi_i>0, \; i=1,n$ \\
$\displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i $ \\
$\displaystyle \min_f \; \|f\|_\clH$
}
}

\onlySlide*{2}{ \figgauche{130pt}{margelin.eps}{$f(x_i)  y_i > 1 - \xi_i  \qquad \xi_i>0, \; i=1,n$ \\
$\displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i $ \\
$\displaystyle \min_f \; \|f\|_\clH$
}
}

\onlySlide*{3}{ \figgauche{130pt}{margelinSol.eps}{$f(x_i)  y_i > 1 - \xi_i  \qquad \xi_i>0, \; i=1,n$ \\
$\displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i $\\
$\displaystyle \min_f \; \|f\|_\clH$
}
}

\onlySlide*{4}{ \figgauche{115pt}{margeW.eps}{$f(x_i)  y_i > 1 - \xi_i  \qquad \xi_i>0, \; i=1,n$ \\
$\displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i $ \\
$\displaystyle \min_f \; \|f\|_\clH \quad \Leftrightarrow \quad\displaystyle \min_{\w} \sum_{j=1}^{\infty} w_j^2 $
}
}

\vspace{-.2cm}

\begin{itemstep}
\item $\underbrace{\displaystyle \sum_{i=1}^{n} \Un_{\left\{\mbox{signe}\left(f(x_i)\right)  
\neq y_i\right\} }}_{\mbox{\blue erreur empirique}} 
+ \pr(err) < \phi\left(\frac{1}{\mbox{marge}}\right)$
\item {\bf minimiser} $\pr(err) \Leftrightarrow$ {\bf maximiser} la marge
\item maximiser la robustesse $\Leftrightarrow$ maximiser la marge
\item maximiser la marge $\Leftrightarrow$ minimiser $\|\w\|^2$
\end{itemstep}

\vspace{.2cm}
\onlySlide*{1}{\vspace{.4cm} }
\onlySlide*{2}{\vspace{-.4cm} }
\onlySlide*{3}{\vspace{-.4cm} }
\begin{flushright}
\scriptsize
(1) Fidélité - (3) Décision <<~locale~>> \\
\fbox{\bf (2) Régularité} -{ (4) Points <<~frontière~>>}
\end{flushright}

\end{slide}
}
%---------------------------------------------------------------------- CONCLUSION CRITERES -
%----------------------------------------------------------------------  -
\overlays{1}{
\begin{slide}{Normes...}
\figgauche{100pt}{SolSVMGauss.eps}{
$\qquad \displaystyle \min_f \; \|f\|_\clH \quad \Leftrightarrow \quad\displaystyle \min_{\w} \sum_{j=1}^{\infty} w_j^2 $
}
\scriptsize soit $\left(\phi_j\right)_{j\in J}$ une base orthonormé de fonctions (polynômes, fourier, ondelettes...)
%\moncadre{
\vspace{-.25cm}
$$f(x) = \sum_{j=1}^{\infty} w_j \phi_j(x)$$
%}
\vspace{-.35cm}

l'ensemble des hypothèses est alors de la forme

\vspace{-.15cm}
$$
\clH = \left\{f \; \bigl| \bigr. \; f(x) = \sum_{j=1}^{\infty} w_j \phi_j(x)\right\}
$$
\begin{center}
\moncadre{\normalsize
$\qquad \qquad  f$ est <<~linéaire~>> en $\phi$ et non linéaire en $x$
}
\end{center}

\end{slide}
}

%---------------------------------------------------------------------- CONCLUSION CRITERES -
%----------------------------------------------------------------------  -
\overlays{1}{
\begin{slide}{Quel critère minimiser~?}
\figgauche{100pt}{SolSVMGauss.eps}{
$$
\left. 
\begin{array}{l}
f(x_i)  y_i > 1 - \xi_i  \qquad \xi_i  > 0, \; i=1,n \\
\displaystyle \min_{\xi_i} \sum_{i=1}^{n} \xi_i 
\end{array} \right\}  \mbox{Fidélité} $$ \\
$\; \qquad \displaystyle \qquad \min_{\w} \sum_{j=1}^{\infty} w_j^2 $ \dotfill\ \hspace{4.5cm}  Régularité
}
\moncadre{
Comment choisir la fonction de discrimination~? $$f(x) = \sum_{j=1}^{\infty} w_j \phi_j(x)$$
}
%\vspace{.5cm}
\begin{flushright}
\scriptsize
(1) Fidélité - (3) Décision <<~locale~>> \\
 (2) Régularité - (4) Points <<~frontière~>>
\end{flushright}

\end{slide}
}

%---------------------------------------------------------------------- Noyaux -
%----------------------------------------------------------------------  -
\overlays{2}{
\begin{slide}{Comment choisir la fonction de discrimination~?}
\figgauche{100pt}{parzen.eps}{
$$f(x) = \sum_{j=1}^{\infty} w_j \phi_j(x)$$
}

Influence locale $\Rightarrow$ Noyaux. Influence fixe (Parzen + MAP)
\vspace{-.25cm}

$$
f(x) = \sum_{i=1}^{n} y_i K_b(x,x_i)
$$
\vspace{-.25cm}
Influence ajustée
\vspace{-.25cm}
$$
f(x) = \sum_{i=1}^{n} a_i K_{\rnode{B}{b}}(x,x_i)
$$
\fromSlide*{2}{ 
\scriptsize {\red \rnode{BA}{$b$}} : taille de la zone d'influence 
 {\nccurve[linecolor=red,angleA=90,angleB=270]{->}{BA}{B}} }

\vspace{-.15cm}
\begin{flushright}
\scriptsize
(1) Fidélité - \fbox{\bf (3) Décision <<~locale~>>} \\
 (2) Régularité - (4) Points <<~frontière~>>
\end{flushright}

\end{slide}
}
%---------------------------------------------------------------------- Noyaux -
\overlays{1}{
\begin{slide}{Malédiction de la dimensionnaleté}
\figgauche{150pt}{noyaux.eps}{
\scriptsize
noyaux défini positifs

noyau multidimensionnel produit~:
$$
 K_b(\u,\v)=\prod_{\ell=1}^{L} K_b(u_\ell,v_\ell)
$$
}

noyaux <<~radiaux~>> $\rho = \|\u-\v\|^2$ (distance entre les deux variables) \\
noyaux <<~projectifs~>> $\u^{\top}\v = \displaystyle \sum_{\ell=1}^{L}u_\ell v_\ell$   \\
formule de <<~passage~>>
$$
\|\u-\v\|^2=\|\u\|^2+\|\v\|^2-2\u^{\top}\v
$$
\end{slide}
}
%---------------------------------------------------------------------- Noyaux -
\overlays{1}{
\begin{slide}{Quelques exemples de noyaux}
\begin{tabular}{ll}
le noyau gaussien & le noyau de Laplace \\
 $
\quad \displaystyle K_b(u,v) = \quad \frac{1}{Z} \exp^{-{\rho\over
 b}}
$ & $ \quad  \displaystyle K_b(u,v) = \quad \frac{1}{Z}
\exp^{-{|u-v|\over
 b}}
$
\\
le noyau de Cauchy & le noyau d'Hermite \\
$ \quad  \displaystyle K_b(u,v) = \frac{1}{Z}\quad
\frac{1}{1+{\rho\over
 b}}
$
&
$ %\label{eq:hermitr}
\quad  \displaystyle K_b(u,v) = \frac{1}{Z}\left(b - \rho\right)
\; \exp^{-{\rho\over b}} $
\\

le noyau uniforme & le noyau d'Epanechnikov \\
$%\label{eq:unif}
\quad \displaystyle K_b(u,v) = \frac{1}{Z} \Un_{\{\rho\leq b\}} $
&
$%\label{eq:epanech}
\quad \displaystyle K_b(u,v) = \frac{1}{Z} \left(b - \rho\right)
\;  \Un_{\{\rho\leq b\}} $
\\le noyau de Fourier régularisé & le noyau sigmo\"{\i}de \\
$ \quad \displaystyle K_b(u,v) = \frac{1}{Z}
\cosh \left(\pi -\frac{|u-v|}{b}\right) % vapnik pp 400 et des brouettes A VERIFIER !!!
$ & $ \quad \displaystyle K_b(\u,\v) = \frac{1}{Z} \tanh\left(b
(\u^\top \v)+ b_0 \right) $
\\
le noyau scalaire & le noyau de Hardy \\
$%\label{eq:squalaires}
\quad \displaystyle K_b(\u,\v) = (\u^\top \v+1)^b $
& $%\label{eq:squalaires}
\quad \displaystyle K_b(u,v) = {1\over (\u^\top \v+1)^b} $
\\
\end{tabular}

%Quelques exemples de noyaux, avec $Z$  une constante de normalisation
%             et $b$ la largeur de bande.
\end{slide}
}
%---------------------------------------------------------------------- Noyaux -
\overlays{2}{
\begin{slide}{L'astuce du noyau}

Théorème de Mercer : Si $K$ est un noyau défini positif,
il existe une famille $\left(\phi_j\right)_{j\in \Ind}$  orthonormée telle que~:

\vspace{-.25cm}
\begin{equation}\label{eq:kerneltrick}
K_b(\x,\y) = \displaystyle  \sum_{j\in J} \phi_j\left(\x\right) \phi_j\left(\y\right)
\end{equation}
%
toute fonction $f \in \clH$ s'écrit alors~: 

\vspace{-.25cm}
$$f(\x) = \sum_{j\in J} w_j \phi_j\left(\x\right) = \sum_{i=1}^n a_i K_b\left(\x,\x_i\right)$$

\vspace{-.25cm}
$$
\onlySlide*{1}
{\quad \|f\|_\clH^2 = \rnode{b}{\pscirclebox[linecolor=red,linestyle=none]{\w^\top \w}} = \pscirclebox[linecolor=blue,linestyle=none]{\a^\top K \a}
}
\fromSlide*{2}
{\quad \|f\|_\clH^2 = \rnode{b}{\pscirclebox[linecolor=red]{\w^\top \w}} = \rnode{c}{\pscirclebox[linecolor=blue]{\a^\top K \a}}
}
$$
\vspace{-.1cm}
{\scriptsize où $K$ est la matrice d'influence.}  $ \qquad $
\fromSlide{2}{\rnode{bA}{\red dim $\infty$} $\quad$ \rnode{cA}{\blue dim $n$}}

\scriptsize
$K_{ij}=K_b\left(\x_i,\x_j\right)$
%

\vspace{-.25cm}
\begin{flushright}
\scriptsize
(1) Fidélité - \fbox{\bf (3) Décision <<~locale~>>} \\
 (2) Régularité - (4) Points <<~frontière~>>
\end{flushright}

\end{slide}
}

%---------------------------------------------------------------------- S V M -
\overlays{2}{
\begin{slide}{Ensemble d'hypothèses + Critère  = Le problème {\it SVM}}

\vspace{-.5cm}
$$
\clH = \left\{f : \dbR^L\rightarrow \dbR \Bigl| \Bigr. \; \exists
\a,\c \; ; \; f(\x)=\sum _{j=1}^{m}c_{j}\varphi _{j}(\x)+
\onlySlide*{1}{
%\rnode{bA}{\pscirclebox[linecolor=red,linestyle=none]{\displaystyle \sum_{\ell =1}^{n_{\mbox {\tiny sup}}}a_{\ell }K_b(\x,\x_{\ell })}}
\rnode{bA}{{\displaystyle \sum_{\ell =1}^{n_{\mbox {\tiny sup}}}a_{\ell }K_b(\x,\x_{\ell })}}
}
\onlySlide*{2}{
%\rnode{bA}{\pscirclebox[linecolor=red]{\displaystyle \sum_{\ell =1}^{n_{\mbox {\tiny sup}}}a_{\ell }K_b(\x,\x_{\ell })}}
\rnode{bA}{{\displaystyle \sum_{\ell =1}^{n_{\mbox {\tiny sup}}}a_{\ell }K_b(\x,\x_{\ell })}}
}
\right\}
$$%

\vspace{-.25cm}

 où \( n_{\mbox {\tiny sup}} \) est le nombre de vecteurs supports \\
probl\`{e}me de minimisation sous contraintes~:

\vspace{-.15cm}
\begin{equation}\label{eq:minsvm}
 \left\{ \begin{array}{lll}
\displaystyle  & \displaystyle \min _{\w } & \frac{1}{2}\w^{\top }\w + C \displaystyle \sum_{i=1}^n \xi_i\\
\mbox {avec} &  & y_{i}f(\x_{i})>1-\xi_i\qquad i=1,n \\
\mbox {et} &  & \xi_{i}>0\qquad \qquad \qquad i=1,n 
\end{array}\right.
\end{equation}
\vspace{-.25cm}
 où~: $f(\x)=\displaystyle \sum _{k=1}^{\infty }w_{k}\phi _{k}(\x)+\rnode{b}{\displaystyle \sum_{j=1}^{m}c_{j}\varphi _{j}(\x)}$

\fromSlide*{2}{ {\nccurve[linecolor=red,angleA=90,angleB=270]{<->}{b}{bA}} }

%\vspace{.5cm}
\begin{flushright}
\scriptsize
(1) Fidélité - \fbox{\bf (3) Décision <<~locale~>>} \\
 (2) Régularité - (4) Points <<~frontière~>>
\end{flushright}

\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{3}{
\begin{slide}{Minimisation sous contraintes (cas séparable)}
\figgauche{150pt}{optimCont.eps}{
$$ \left\{ \begin{array}{lll}
\displaystyle  & \displaystyle \min _{\w } & \frac{1}{2}\w^{\top }\w \\
\mbox {avec} &  & y_{i}f(\x_{i})>1\qquad i=1,n \\
\end{array}\right.
$$
\fromSlide{2}{
$\qquad \qquad \qquad \Leftrightarrow$
$$ \displaystyle \min_{\w,\c} \max_\lambda \clL(\w,\c,\lambda) \qquad \mbox{\tiny Lagrangien}$$
}
}
\fromSlide{2}{
$$
 \clL(\w,\c,\lambda)=\frac{1}{2} \|\w\|^2 - \underbrace{\sum_{i=1}^{n}}_{\mbox{\tiny les exemples}}
\onlySlide*{2}{
\rnode{bA}{\pscirclebox[linecolor=red,linestyle=none]{\lambda_{i}}}
}
\onlySlide*{3}{
\rnode{bA}{\pscirclebox[linecolor=red]{\lambda_{i}}}
}
\bigl(y_{i}f(\x_{i}) -1\bigr)
$$
}
\onlySlide{3}{
\scriptsize
Multiplicateur de Lagrange $\lambda_i$ = {\red influence de l'exemple $i$ dans la solution} \\
interprètation : $\lambda_i = 0 \rightarrow$ pas d'influence  $\qquad \lambda_i >0 \rightarrow$ {exemple \em support}
}

\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{2}{
\begin{slide}{Reformulation dans l'espace des exemples}

%\vspace{-.25cm}
%Le Lagrangien du problème [\ref{eq:minsvm}]~:
\vspace{-.25cm}
$$
\clL(\w,\a,\lambda)=\frac{1}{2} \|\w\|^2 - \sum_{i=1}^{n}
\lambda_i \bigl(y_{i}f(\x_{i}) -1\bigr)
$$
\vspace{-.25cm}
dont on tire les conditions de Kuhn et Tucker~:
\vspace{-.15cm}
$$
\left\{
\begin{array}{lll}
\displaystyle \frac{\partial \clL(\w,\c,\lambda)}{\partial \w} &=& 0 \\
\displaystyle \frac{\partial \clL(\w,\c,\lambda)}{\partial \c} &=&
0
\end{array}\right.
%
\Leftrightarrow
%
\left\{
\begin{array}{lll}
\displaystyle  \w - \sum_{i=1}^{n} \lambda_i y_{i} \phi(\x_i) &=&0\\
\displaystyle  \sum_{i=1}^{n} \lambda_i y_{i} \varphi(\x_i)  &=&0
\end{array}
\right.
$$

\vspace{-.5cm}
conséquence pour $f$ : 
%Donc :  $\displaystyle \w = \sum_{i=1}^{n} \lambda_i y_{i} \phi(\x_i)$,
%
%\vspace{-.25cm}
$
\begin{array}{ll}
\displaystyle f(\x) = \sum _{k=1}^{\infty }w_{k}\phi _{k}(\x) &=
\displaystyle \sum _{k=1}^{\infty }
\left(\sum_{i=1}^{N} \lambda_i y_{i}\phi(\x_i) \right) \phi _{k}(\x) \\
\displaystyle &=  \displaystyle \sum_{i=1}^{N} \underbrace{\lambda_i y_{i}}_{a_i}
\underbrace{\sum _{k=1}^{\infty } \phi
_{k}(\x)\phi(\x_i)}_{K_b(\x,\x_i)}
\end{array}
$

\onlySlide{2}{\vspace{-2.75cm}
\begin{flushright}
\scriptsize
\blue \fbox{Stratégie}\\
calcul de $K$ \\
calcul des $\lambda$ \\
calcul des $\a$ \\
calcul de $f$
\end{flushright}
}

\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{1}{
\begin{slide}{calcul des $\lambda$ : problème Dual (2)}
\vspace{-.5cm}
\figgauche{150pt}{minCont.eps}{
%$\lambda_i$
$$
\left\{ \begin{array}{lll}
\displaystyle  & \displaystyle \min _{\lambda} & \frac{1}{2}\lambda^{\top } H \lambda + \c^{\top } \lambda\\
\mbox {avec} &  & \displaystyle\sum_{i=1}^{N} \lambda_i y_{i} \varphi_j(x_i) =  0 \quad j=1,m \\
\mbox {et} & &  0 \leq \lambda_{i}\leq C \qquad i=1,n
\end{array}\right.
$$
où $H$ est la matrice de terme général $H_{ij} =
y_iy_jK_b(\x_i,\x_j)$

et $\c$ un vecteur de 1. 
}

Reformulation de Girosi (97)
$$
\min_\a \|f(\x_i)-y_i\|_\clH^2 + \mu \sum_{i=1}^n |a_i|
$$

%\vspace{.1cm}
\begin{flushright}
\scriptsize
(1) Fidélité - (3) Décision <<~locale~>> \\
 (2) Régularité - \fbox{\bf (4) Points <<~frontière~>>}
\end{flushright}

\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{1}{
\begin{slide}{Solution pratique : Problème d'optimisation}

\begin{itemize}
\item Simplex
\item Contraintes actives
\item Points intérieurs
\item stochastiques : SMO
\end{itemize}


\end{slide}
}
%---------------------------------------------------------------------- S V M -
%\overlays{1}{
%\begin{slide}{Solution pratique : Choix du noyau}
%\begin{itemize}
%\item polynomial
%\item radial
%\item Kriging : noyau de Fisher
%\item Ondelettes
%\end{itemize}

%\end{slide}
%}
%---------------------------------------------------------------------- S V M -
\overlays{1}{
\begin{slide}{Solution pratique : Paramètres de régularisation}
\figgauche{200pt}{ErrsigC4.eps}{
\begin{itemize}
\item $b$
\item $C$
\item $\lambda$
\end{itemize}
}
SVMtoolbox : une démo ?

\vspace{.5cm}
\tiny %\begin{verbatim}
$[xsup,w,w0,tps,alpha] = \mbox{svmclass}(Xapp,yi,C,lambda,kernel,kerneloption,1,phi);  $\\
$ypred = \mbox{svmval}(Xtest,xsup,w,w0,kernel,kerneloption);$
%\end{verbatim}

\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{1}{
\begin{slide}{Extentions}
\begin{itemize}
\item Multiclasse
\item Regression : $\varepsilon$-insensible
$$
J(f(x),y) = \max(|f(x) - y|-\varepsilon ,0)  
$$
\item analyse de données : ACP à base de noyau 
\end{itemize}


\end{slide}
}
%---------------------------------------------------------------------- S V M -
\overlays{1}{
\begin{slide}{Conclusion}
\begin{itemize}
\item SVM les principes
\begin{itemize}
\item Noyaux : unversel
\item Marge : minimum global unique
\item Parcimonieux : l'influence de chaque exemple
\end{itemize}
\item SVM vs Réseaux de neurones (PMC) : optimisation
\item SVM vs Noyaux (FBR) : optimisation
\item SVM vs Parzen : parcimonie ($L^2 \; vs \; L^1$)
\item SVM : des résultats
\end{itemize}


\end{slide}
}
%%---------------------------------------------------------------------- S V M -
%\overlays{1}{
%\begin{slide}{Historique}
%
%\end{slide}
%}
%---------------------------------------------------------------------- SLIDE -
\begin{slide}{Références}
\begin{itemize}
  \item  SVM
\begin{itemize}
  \item  \scriptsize Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
  \item  \scriptsize  Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines. 
       Cambridge University Press, Cambridge, UK, 2000
\end{itemize}
\vspace{.4cm}
\item Reconnaissance des formes statistiques
\begin{itemize}
  \item  \scriptsize R. O. Duda, P. E. Hart and  D. G. Stork, Pattern Classification (2nd ed.), John Wiley and Sons, 2001.
  \item \scriptsize T. Hastie, R. Tibshirani, and J. Fridman, The Elements of Statistical Learning:Data Mining, Inference, and Prediction, Springer-Verlag, 2001
\end{itemize}
\vspace{.4cm}
\item et sur le réseau
\begin{itemize}
  \item  \scriptsize http://kernel-machines.org
  \item  \scriptsize http://www.ph.tn.tudelft.nl/PRInfo/
\item  \scriptsize http://citeseer.nj.nec.com/
  \item  \scriptsize http://asi.insa-rouen.fr/\char126scanu
\end{itemize}
\end{itemize}
\end{slide}

% =================================================================================
\end{document}