Lien de la note Hackmd

On a un probleme de classification binaire:

Probleme: donnees d'apprentissage

$$\{(x_i,y_i){\}}_{i=1}^n{x}_i\in {\mathbb{R}}^p{y}_i\in \{-1,+1\}$$

On cherche un hyperplan de

${\mathbb{R}}^p$ qui separe parfaitement les deux classes

Dans notre exemple, il n'y a pas qu'un seul hyperplan separant les 2 classes:

Hyperplan

Hyperplan: caracterise par un vecteur normal

$w\in {\mathbb{R}}^p$ et un offset

$b\in \mathbb{R}$

$$x\in H\iff w^{T}x+b=0$$

Lequel des hyperplans semble meilleur ?

Celui du milieu

On a une infinite de solutions possibles (meme risque empirique), mais toutes les solutions n'ont pas les memes performances en generalisation

Geometriquement, on veut celui qui est le plus loin des points (aka la marge de l'hyperplan)

On cherche

$(w,b)\in {\mathbb{R}}^p\times \mathbb{R}$ tel que tous les echantillons de la classe

$-1/+1$ soient dans le demi espace:

• positif:
  $w^T{x}_i+b\ge 0$
  $y_i=+1$
• negatif:
  $w^T{x}_i+b\le 0$
  $y_i=-1$

Dans tous les cas:

$$\boxed{{\displaystyle \mathrm{\forall }{x}_i\in {\mathbb{R}}^p,y_i(w^T{x}_i+b)\ge 0}}$$

Marge

Marge: distance de l'hyperplan aux echantillons les plus proches

$$\begin{array}{rl}{M}_H=\underset{i=1,\dots ,n}{min}\{d(x_i,H)\}& =\underset{i=1,\dots ,n}{min}\{d(x_i,x),x\in {\mathbb{R}}^n,w^{T}x+b=0\}\\ & =d(x_s,H)\text{avec }{x}_s\text{ vecteur de support}\end{array}$$

On va chercher l'hyperplan qui maximise la marge

$$H^{\ast }=\text{arg}\underset{(w,b)\in {\mathbb{R}}^p\times \mathbb{R}}{max}{M}_H=d(x_s,H)$$

Distance d'un point

$x_0$ a un hyperplan:

$$d(x_0,H)=\Vert y-x_0\Vert$$

$$(L)=\{x_0+tw,t\in \mathbb{R}\}$$

$$\begin{gathered} y\in (L),\mathrm{\exists }t\in \mathbb{R},y=x_0+tw \\ \begin{array}{rl}& y\in (H)w^{T}y+b=0\\ & w^T(x_0+tw)+b=0\\ & w^T{x}_0+\underset{\Vert w{\Vert }^2}{\underbrace{t{w}^{T}w}}+b=0\end{array} \\ t=-\frac{1}{\Vert w{|}^2}(w^T{x}_0+b) \end{gathered}$$

$$\begin{gathered} \begin{array}{rl}d(x_0,H)=\Vert y-x_0\Vert & =\Vert x_0+tw-x_0\Vert \\ & =\Vert tw\Vert \\ & =|t|\cdot \Vert w\Vert \\ & =|-\frac{1}{\Vert w{\Vert }^2}(w^T{x}_0+b)|\times \Vert w\Vert \end{array} \\ \boxed{{\displaystyle d(x_0,H)=\frac{|w^T{x}_0+b}{\Vert w\Vert }}} \end{gathered}$$

$$\begin{array}{rl}{M}_H& =\underset{i}{min}\{d(x_i,H)\}\\ & =\underset{i}{min}\{\frac{|w^T{x}_i+b|}{\Vert w\Vert }\}\\ & =\frac{1}{\Vert w\Vert }\underset{i}{min}\{|w^T{x}_i+b|\}\\ & =\frac{|w^T{x}_s+b|}{\Vert w\Vert }{x}_s\text{ vecteur de support}\end{array}$$

On cherche

$$\text{arg}\underset{(w,b)}{max}{M}_H=\text{arg}\underset{(w,b)}{max}\frac{|w^T{x}_s+b|}{\Vert w\Vert }$$

Si

$(w,b)$ est une solution,

$(kw,kb)$

$k>0$ est aussi solution.

On va choisir

$(w,b)$ tels que

$|w^T{x}_s+b|=1$

Marge normalisee:

$\frac{1}{\Vert w\Vert }$

SVM

On cherche a:

$$\begin{array}{rl}\text{maximiser}& \frac{1}{\Vert w\Vert }\\ \text{maximiser}& \frac{2}{\Vert w\Vert }\\ \text{minimiser}& \frac{1}{2}\Vert w{\Vert }^2\end{array}$$

SVM:

$$\begin{gathered} \boxed{{\displaystyle \text{arg}\underset{(w,b)\in {\mathbb{R}}^d\times \mathbb{R}}{min}\frac{1}{2}\Vert w{\Vert }^2 \\ \begin{array}{rl}\text{tel que }& y_i(w^T{x}_i+b)\ge 1\\ & \mathrm{\forall }i=1,\dots ,n\end{array}}} \end{gathered}$$

$$\begin{gathered} \frac{1}{2}\Vert w{\Vert }^2=\frac{1}{2}{w}^{T}w \\ {y}_i(w^T{x}_i+b)\ge 1\iff 1-y_i(w^T{x}_i+b)\le 0\mathrm{\forall }i \end{gathered}$$

Le Lagrangien de (SVM) est:

$$\begin{array}{rl}\mathcal{L}(w,b,\lambda )& =\frac{1}{2}{w}^{T}w+\sum _{i=1}^n{\lambda }_i(1-y_i(w^T{x}_i+b))w\in {\mathbb{R}}^p,b\in \mathbb{R},\lambda \in {\mathbb{R}}^n\\ & =\frac{1}{2}{w}^{T}w-\sum _{i=1}^n{\lambda }_i(y_i(w^T{x}_i+b)-1)\end{array}$$

Conditions KKT

Stationnarite du Lagrangien

$$\begin{gathered} \begin{array}{rl}{\mathrm{\nabla }}_w\mathcal{L}(w,b,\lambda )& =0\\ & =\underset{w}{\underbrace{\frac{\partial }{\partial w}(\frac{1}{2}{w}^{T}w)}}-\sum _{i=1}^n\frac{\partial }{\partial w}({\lambda }_i\underset{{\lambda }_i{y}_i{x}_i}{\underbrace{(y_i(w^T}}{x}_i+b)-1))\\ 0& =w-\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\\ w& =\sum _{i=1}^n{\lambda }_i{y}_i{x}_{i}w\text{ est une combinaison lineaire des }{x}_i\end{array} \\ {\mathrm{\nabla }}_b\mathcal{L}(w,b,\lambda )=\boxed{{\displaystyle 0=\sum _{i=1}^n{\lambda }_i{y}_i}} \end{gathered}$$

A chaque

$x_i$ correspond un

${\lambda }_i$

• ${\lambda }_i\ge 0\to {\lambda }_i$ est la "force" avec laquelle
  $x_i$ repousse l'hyperplan
• $\sum _{i=1}^n{\lambda }_i{y}_i=0\to$ l'hyperplan est a l'equilibre

Complementarite

$$\mathrm{\forall }i=1,\dots ,n{\lambda }_i(1-y_i(w^T{x}_i+b))=0({\alpha }_i^{\ast }{g}_i(x^{\ast })=0\mathrm{\forall }i)$$

Soit

${\lambda }_i=0$:

$$\begin{gathered} 1-y_i(w^T{x}_i+b)<0\iff y_i(\underset{x_i\text{ n'est pas} \\ \text{un vecteur} \\ \text{de support}}{\underbrace{w^T{x}_i+b}})>1 \\ {\lambda }_i=0\{\begin{array}{l}{x}_i\text{ ne repousse pas l'hyperbole}\\ \text{ne contribue pas a la solution }w=\sum _{i=1}^n{\lambda }_i{y}_i{x}_i\\ \text{la solution ne change pas si on enleve }{x}_i\text{ du jeu de donnees}\end{array} \end{gathered}$$

Soit

${\lambda }_i>0$:

$$\begin{gathered} 1-y_i(w^T{x}_i+b)=0\iff y_i(\underset{x_i\text{ est un vecteur} \\ \text{de support}}{\underbrace{w^T{x}_i+b}})=1 \\ {\lambda }_i>0\{\begin{array}{l}\text{la solution change si on enleve }{x}_i\text{ du jeu de donnees}\end{array} \end{gathered}$$

Recap

$$\begin{gathered} w=\sum _{i=1}^n{\lambda }_i{y}_i{x}_i \\ o=\sum _{i=1}^n{\lambda }_i{y}_i \\ \mathcal{L}(w,b,\lambda )=\frac{1}{2}{w}^{T}w-\sum _{i=1}^n{\lambda }_i(y_i(w^T{x}_i+b)-1) \\ \begin{array}{rl}{w}^{T}w& =(\sum _{i=1}^n{\lambda }_i{y}_i{x}_i{)}^T(\sum _{j=1}^n{\lambda }_j{y}_j{x}_j)\\ & =\sum _{i=1}^n{\lambda }_i{y}_i(x_i{)}^T\sum _{j=1}^n{\lambda }_j{y}_j{x}_j\\ & =\sum _i\sum _j{\lambda }_i{\lambda }_j{y}_i{y}_j{x}_i^T{x}_j\end{array} \end{gathered}$$

$$\begin{array}{rl}\sum _{i=1}^n{\lambda }_i(y_i(w^T{x}_i+b)-1)=\sum _{i=1}^n\underbrace{{\lambda }_i{y}_i{w}^T{x}_i}& +\underbrace{b\sum _{i=1}^n{\lambda }_i{y}_i}-\sum _{i=1}^n{\lambda }_i\\ \sum _i{\lambda }_i{y}_i(\sum _{j=1}^n{\lambda }_j{y}_j{x}_j{)}^T{x}_i& =\sum _i\sum _j{\lambda }_i{\lambda }_j{y}_i{y}_j{x}_i^T{x}_j\end{array}$$

Probleme dual du SVM

$$\begin{gathered} \boxed{{\displaystyle \underset{{\lambda }_i\ge 0 \\ \sum _{i=1}^n{\lambda }_i{y}_i}{max}\mathcal{L}=-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\lambda }_i{\lambda }_j{y}_i{y}_j{x}_i^T{x}_j+\sum _{i=1}^n{\lambda }_i}} \end{gathered}$$

Sous reserve qu'on puisse resoudre le dual:

• On trouve
  ${\lambda }_i^{\text{*}}$
• On trouve
  $w^{\text{*}}=\sum _{i=1}^n{\lambda }_i^{\text{*}}{y}_i{x}_i$
• On trouve
  $b^{\text{*}}$ grace aux vecteurs de support
  $y_i(w^{\text{*}t}{x}_i+b^{\text{*}})=1$

Probleme dual du SVM se resout par Sequential Minimal Optimization
Pour resoudre