Support Vector Machine (SVM)

Intermediaire 45 min 13 sections

Maitrisez les SVM, un algorithme puissant pour la classification qui trouve la frontiere optimale entre les classes.

Telecharger CSV Telecharger Script Python

Objectifs d'apprentissage

Comprendre le concept de marge maximale et hyperplan separateur
Maitriser le kernel trick pour les donnees non lineaires
Implementer SVM avec scikit-learn
Choisir le bon kernel selon les donnees

Prerequis

Module Regression Logistique recommande

Theorie

Qu'est-ce qu'un SVM?

Un Support Vector Machine (SVM) est un algorithme de classification qui cherche l'hyperplan separant les classes avec la marge maximale.

Concepts cles:

Hyperplan: Frontiere de decision (droite en 2D, plan en 3D)
Marge: Distance entre l'hyperplan et les points les plus proches
Support Vectors: Points qui definissent la marge (les plus proches de l'hyperplan)

Pourquoi maximiser la marge?

Une marge plus grande = meilleure generalisation sur de nouvelles donnees.

Avantages:

Efficace en haute dimension
Fonctionne bien meme si nb_features > nb_samples
Robuste a l'overfitting (grace a la regularisation)

Inconvenients:

Lent sur tres grands datasets (>10K samples)
Sensible a l'echelle des features (normalisation requise)
Choix du kernel peut etre difficile

Theorie

Schema: Marge maximale et Support Vectors

Trouver l'hyperplan optimal:

flowchart LR subgraph Data ["Donnees 2D"] direction TB C1["Classe 0
(cercles)"] C2["Classe 1
(carres)"] end subgraph SVM ["SVM"] H["Hyperplan
(frontiere)"] M["Marge
(maximisee)"] SV["Support Vectors
(points cles)"] end Data --> SVM style H fill:#F7E64D,color:#1A1A1A style SV fill:#9B7AC4,color:#FFFFFF

Plusieurs hyperplans possibles, lequel choisir?

flowchart TD H1["Hyperplan A
Marge: 0.5"] H2["Hyperplan B
Marge: 1.2"] H3["Hyperplan C
Marge: 2.0"] BEST["SVM choisit C
(marge maximale)"] H1 --> BEST H2 --> BEST H3 --> BEST style H3 fill:#F7E64D,color:#1A1A1A style BEST fill:#F7E64D,color:#1A1A1A

Le probleme des donnees non lineaires:

flowchart LR L["Donnees
Non Lineaires"] K["Kernel Trick
(transformation)"] H["Hyperplan
dans nouvel espace"] L -->|"Impossible en 2D"| K -->|"Separable en 3D+"| H style K fill:#C09CF0,color:#1A1A1A style H fill:#F7E64D,color:#1A1A1A

Exemple concret - Classification d'un nouveau point:

Nouveau point: $\textcolor{#3498db}{x_1 = 2.5}$, $\textcolor{#e67e22}{x_2 = 1.8}$

Le SVM a appris l'hyperplan: $\textcolor{#9B7AC4}{w_1} \cdot x_1 + \textcolor{#9B7AC4}{w_2} \cdot x_2 + \textcolor{#9B7AC4}{b} = 0$

Avec $\textcolor{#9B7AC4}{w_1 = 0.8}$, $\textcolor{#9B7AC4}{w_2 = 0.6}$, $\textcolor{#9B7AC4}{b = -2.0}$

Calcul de la decision:

$$f(x) = \textcolor{#9B7AC4}{0.8} \times \textcolor{#3498db}{2.5} + \textcolor{#9B7AC4}{0.6} \times \textcolor{#e67e22}{1.8} + \textcolor{#9B7AC4}{(-2.0)}$$

$$f(x) = \textcolor{#3498db}{2.0} + \textcolor{#e67e22}{1.08} - 2.0 = \textcolor{#27ae60}{\mathbf{+1.08}}$$

Decision:

Si $f(x) > 0$ → $\textcolor{#27ae60}{\text{Classe 1}}$
Si $f(x) < 0$ → Classe 0

Ici $\textcolor{#27ae60}{+1.08 > 0}$ → Classe 1

Legende des couleurs:

$\textcolor{#3498db}{Bleu}$ : feature 1 et sa contribution ($\textcolor{#3498db}{2.5 \times 0.8 = 2.0}$)
$\textcolor{#e67e22}{Orange}$ : feature 2 et sa contribution ($\textcolor{#e67e22}{1.8 \times 0.6 = 1.08}$)
$\textcolor{#9B7AC4}{Violet}$ : poids appris par le SVM
$\textcolor{#27ae60}{Vert}$ : score final positif → Classe 1

Avance Exercice manuel: A vous de calculer!

Objectif: Comprendre les SVM a la main (marge, vecteurs supports).

CONTEXTE

Vous avez 4 points en 2D a separer (classification binaire) :

Point	x1	x2	Classe
A	1	2	+1
B	2	3	+1
C	4	1	-1
D	5	2	-1

L'hyperplan separateur est : $w_1 x_1 + w_2 x_2 + b = 0$

Avec $w_1 = 1$, $w_2 = 0$, $b = -3$

Soit : $x_1 - 3 = 0$ (ligne verticale a $x_1 = 3$)

PARTIE 1 : Classification

1.1) Calculez $f(x) = w_1 x_1 + w_2 x_2 + b$ pour chaque point

1.2) Verifiez que le signe de $f(x)$ correspond a la classe

PARTIE 2 : Calcul des marges

Distance d'un point a l'hyperplan : $\frac{|f(x)|}{||w||}$

2.1) Calculez $||w|| = \sqrt{w_1^2 + w_2^2}$

2.2) Calculez la distance de chaque point a l'hyperplan

2.3) Quels sont les vecteurs supports (points les plus proches) ?

PARTIE 3 : Marge du classifieur

3.1) Quelle est la marge (distance au plus proche) ?

3.2) Pourquoi SVM maximise-t-il cette marge ?

Avance Solution de l'exercice manuel

SOLUTION DETAILLEE

PARTIE 1 : Classification

1.1) Calcul de $f(x) = x_1 - 3$ :

$f(A) = 1 - 3 = \textcolor{#3498db}{-2}$ → signe negatif
$f(B) = 2 - 3 = \textcolor{#3498db}{-1}$ → signe negatif
$f(C) = 4 - 3 = \textcolor{#e67e22}{+1}$ → signe positif
$f(D) = 5 - 3 = \textcolor{#e67e22}{+2}$ → signe positif

1.2) Verification :

A, B : $f(x) < 0$ mais classe +1 → Incoherent !

Correction : L'hyperplan devrait etre $-x_1 + 3 = 0$ ou les classes inversees. Supposons que les classes sont inversees (A,B = -1 et C,D = +1) pour la suite.

PARTIE 2 : Calcul des marges

2.1) Norme :

$$||w|| = \sqrt{1^2 + 0^2} = \textcolor{#9B7AC4}{1}$$

2.2) Distances :

$d(A) = \frac{|-2|}{1} = \textcolor{#27ae60}{2}$
$d(B) = \frac{|-1|}{1} = \textcolor{#F7E64D}{1}$
$d(C) = \frac{|+1|}{1} = \textcolor{#F7E64D}{1}$
$d(D) = \frac{|+2|}{1} = \textcolor{#27ae60}{2}$

2.3) Vecteurs supports :

$\boxed{\text{B et C (distance = 1)}}$

PARTIE 3 : Marge du classifieur

3.1) Marge = distance minimale = $\textcolor{#e74c3c}{\mathbf{1}}$

3.2) SVM maximise la marge pour :

Meilleure generalisation
Plus robuste au bruit
Frontiere la plus "sure" entre les classes

Legende : $\textcolor{#3498db}{Bleu}$: classe -1, $\textcolor{#e67e22}{Orange}$: classe +1, $\textcolor{#F7E64D}{Jaune}$: vecteurs supports

Code

Explorer les donnees

Cliquez sur "Executer" pour voir le resultat