OCVX2 : Tout ce que vous avez toujours voulu savoir sur les SVMS

Lien de la note Hackmd

On a un probleme de classification binaire:

Probleme: donnees d’apprentissage

\[\{(x_i,y_i)\}_{i=1}^n\quad x_i\in\mathbb R^p\quad 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\Leftrightarrow w^Tx+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^Tx_i+b\ge0$ $y_i=+1$
• negatif: $w^Tx_i+b\le0$ $y_i=-1$

Dans tous les cas:

\[\boxed{\forall x_i\in\mathbb R^p, y_i(w^Tx_i+b)\ge 0}\]

Marge

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

\(\begin{aligned} M_H=\min_{i=1,\dots,n}\{d(x_i,H)\} &= \min_{i=1,\dots,n}\{d(x_i,x),x\in\mathbb R^n,w^Tx+b=0\}\\ &= d(x_s,H)\quad\text{avec } x_s \text{ vecteur de support} \end{aligned}\)

On va chercher l’hyperplan qui maximise la marge

\[H^*=\text{arg}\max_{(w,b)\in\mathbb R^p\times\mathbb R}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\}\] \[y\in(L),\exists t\in\mathbb R, y=x_0+tw\\ \begin{aligned} &y\in(H)w^Ty+b=0\\ &w^T(x_0+tw)+b=0\\ &w^Tx_0+\underbrace{tw^Tw}_{\Vert w\Vert^2}+b=0\\ \end{aligned}\\ t=-\frac{1}{\Vert w\vert^2}(w^Tx_0+b)\] \[\begin{aligned} d(x_0,H)=\Vert y-x_0\Vert&=\Vert x_0+tw-x_0\Vert\\ &=\Vert tw\Vert\\ &=\vert t\vert\cdot\Vert w\Vert\\ &=\biggr\vert-\frac{1}{\Vert w\Vert^2}(w^Tx_0+b)\biggr\vert\times\Vert w\Vert \end{aligned}\\ \boxed{d(x_0, H)=\frac{\vert w^Tx_0+b}{\Vert w\Vert}}\] \[\begin{aligned} M_H&=\min_i\{d(x_i,H)\}\\ &=\min_i\biggr\{\frac{\vert w^Tx_i+b\vert}{\Vert w\Vert}\biggr\}\\ &= \frac{1}{\Vert w\Vert}\min_i\{\vert w^Tx_i+b\vert\}\\ &= \frac{\vert w^Tx_s+b\vert}{\Vert w\Vert}\quad x_s\text{ vecteur de support} \end{aligned}\]

On cherche

\[\text{arg}\max_{(w,b)}M_H=\text{arg}\max_{(w,b)}\frac{\vert w^T x_s+b\vert}{\Vert w\Vert}\]

Si $(w,b)$ est une solution, $(kw,kb)$ $k\gt0$ est aussi solution.

On va choisir $(w,b)$ tels que $\vert w^T x_s+b\vert =1$

Marge normalisee: $\frac{1}{\Vert w\Vert}$

SVM

On cherche a:

\[\begin{aligned} \text{maximiser}&\frac{1}{\Vert w\Vert}\\ \text{maximiser}&\frac{2}{\Vert w\Vert}\\ \text{minimiser}&\frac{1}{2}\Vert w\Vert^2\\ \end{aligned}\]

SVM:

\[\boxed{\text{arg}\min_{(w,b)\in\mathbb R^d\times\mathbb R}\frac{1}{2}\Vert w\Vert^2\\ \begin{aligned} \text{tel que } &y_i(w^Tx_i+b)\ge1\\ &\forall i=1,\dots,n \end{aligned}}\]

\[\frac{1}{2}\Vert w\Vert^2=\frac{1}{2}w^Tw\\ y_i(w^Tx_i+b)\ge1\Leftrightarrow 1 - y_i(w^Tx_i+b)\le 0\quad\forall i\]

Le Lagrangien de (SVM) est:

\[\begin{aligned} \mathscr L(w,b,\lambda)&=\frac{1}{2}w^Tw+\sum_{i=1}^n\lambda_i(1-y_i(w^Tx_i+b))\quad w\in\mathbb R^p, b\in\mathbb R,\lambda\in\mathbb R^n\\ &=\frac{1}{2}w^Tw-\sum_{i=1}^n\lambda_i(y_i(w^Tx_i+b)-1) \end{aligned}\]

Conditions KKT

Stationnarite du Lagrangien

\[\begin{aligned}\nabla_w\mathscr L(w,b,\lambda)&=0 \\ &=\underbrace{\frac{\partial}{\partial w} (\frac{1}{2}w^Tw)}_{w} - \sum_{i=1}^n\frac{\partial}{\partial w}(\lambda_i\underbrace{(y_i(w^T}_{\lambda_i y_i x_i}x_i+b)-1))\\ 0&= w-\sum_{i=1}^n\lambda_iy_ix_i\\ w&=\sum_{i=1}^n\lambda_iy_ix_i\quad w \text{ est une combinaison lineaire des } x_i \end{aligned}\\ \nabla_b\mathscr L(w,b,\lambda)=\boxed{0=\sum_{i=1}^n\lambda_iy_i}\]

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_iy_i=0\to$ l’hyperplan est a l’equilibre

Complementarite

\[\forall i=1,\dots,n\quad\lambda_i(1-y_i(w^Tx_i+b))=0\quad(\alpha_i^*g_i(x^*)=0\quad\forall i)\]

Soit $\lambda_i=0$:

\[1-y_i(w^Tx_i+b)\lt 0\Leftrightarrow y_i(\underbrace{w^Tx_i+b}_{x_i \text{ n'est pas} \\ \text{un vecteur}\\ \text{de support}})\gt 1\\ \lambda_i=0\begin{cases} x_i\text{ ne repousse pas l'hyperbole}\\ \text{ne contribue pas a la solution } w=\sum_{i=1}^n\lambda_iy_ix_i\\ \text{la solution ne change pas si on enleve } x_i\text{ du jeu de donnees} \end{cases}\]

Soit $\lambda_i\gt 0$:

\[1-y_i(w^Tx_i+b)=0\Leftrightarrow y_i(\underbrace{w^Tx_i+b}_{x_i \text{ est un vecteur} \\ \text{de support}})=1\\ \lambda_i\gt 0\begin{cases} \text{la solution change si on enleve } x_i \text{ du jeu de donnees} \end{cases}\]

Recap

\[w=\sum_{i=1}^n\lambda_iy_ix_i\\ o=\sum_{i=1}^n\lambda_iy_i\\ \mathscr L(w,b,\lambda)=\frac{1}{2}w^Tw-\sum_{i=1}^n\lambda_i(y_i(w^Tx_i+b)-1)\\ \begin{aligned} w^Tw&= (\sum_{i=1}^n\lambda_iy_ix_i)^T(\sum_{j=1}^n\lambda_jy_jx_j)\\ &= \sum_{i=1}^n\lambda_iy_i(x_i)^T\sum_{j=1}^n\lambda_jy_jx_j\\ &= \sum_i\sum_j\lambda_i\lambda_jy_iy_jx_i^Tx_j \end{aligned}\] \[\begin{aligned} \sum_{i=1}^n\lambda_i(y_i(w^Tx_i+b)-1)=\sum_{i=1}^n\underbrace{\lambda_iy_iw^Tx_i}&+\underbrace{b\sum_{i=1}^n\lambda_iy_i}-\sum_{i=1}^n\lambda_i\\ \sum_{i}\lambda_iy_i(\sum_{j=1}^n\lambda_jy_jx_j)^Tx_i&=\sum_i\sum_j\lambda_i\lambda_jy_iy_jx_i^Tx_j \end{aligned}\]

Probleme dual du SVM

\[\boxed{ \max_{\lambda_i\ge 0 \\ \sum_{i=1}^n\lambda_iy_i}\mathscr L=-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^n\lambda_i }\]

Sous reserve qu’on puisse resoudre le dual:

• On trouve $\lambda_i^{*}$
• On trouve $w^{*}=\sum_{i=1}^n\lambda_i^{*}y_ix_i$
• On trouve $b^{*}$ grace aux vecteurs de support $y_i(w^{*t}x_i+b^{*})=1$

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