---
title: "OCVX2 : Tout ce que vous avez toujours voulu savoir sur les SVMS"
date: 2021-10-27 11:00
categories: [Image S9, OCVX2]
tags: [Image, SCIA, S9, OCVX2]
math: true
---

Lien de la [note Hackmd](https://hackmd.io/@lemasymasa/H15lscIIY)

On a un probleme de classification binaire:


:::warning
**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

:::info
**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

:::success
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$


:::danger
Dans tous les cas:

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

:::

## Marge

:::info
**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}
$$
:::

:::success
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}
$$

:::success

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}
$$

:::danger

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
$$

:::info

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}
$$

:::danger

**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](https://cs229.stanford.edu/materials/smo.pdf)