Cas 1 : Linéairement Séparable
1. Problème Primal
On cherche à trouver un hyperplan w · x + b = 0 qui sépare parfaitement les deux classes
y ∈ {−1, +1} tout en maximisant la marge.
1
∥w∥2
min
w,b 2
sous les contraintes yi (w · xi + b) ≥ 1, ∀i = 1, . . . , N
2. Lagrangien
Le Lagrangien associé est donné par :
N
1 X
L(w, b, α) = ∥w∥2 −
αi yi (w · xi + b) − 1
2 i=1
où αi ≥ 0 sont les multiplicateurs de Lagrange associés aux contraintes.
3. Conditions d’Optimalité (KKT)
Les conditions nécessaires d’optimalité sont :
• ∂L
PN
∂w
=0 ⇒ w= i=1 αi yi xi
• ∂L
PN
∂b
=0 ⇒ i=1αi y i = 0
• αi yi (w · xi + b) − 1 = 0, ∀i
• αi ≥ 0, ∀i
• yi (w · xi + b) ≥ 1, ∀i
4. Problème Dual
Le problème dual se formule comme suit :
N N N
X 1 XX
max αi − αi αj yi yj (xi · xj )
α
i=1
2 i=1 j=1
N
X
sous les contraintes αi y i = 0
i=1
αi ≥ 0, ∀i
1
5. Calcul de b
Si on a accès à un seul vecteur support : Vous pouvez calculer b directement avec :
b = yi − ⟨w, xi ⟩
Cela suppose que vous savez déjà identifier un vecteur support xi (un point pour lequel ξi = 0).
Si on a plusieurs vecteurs supports : Vous devrez calculer b pour chaque vecteur support xi en
utilisant la même formule :
bi = yi − ⟨w, xi ⟩
Ensuite, vous prenez la moyenne des bi obtenus :
1 X
b= bi
|S| i∈S
Cas 2 : Non Linéairement Séparable
1. Problème Primal
Dans le cas non linéairement séparable, on introduit des variables de relâchement ξi ≥ 0 et un
paramètre C pour pénaliser les erreurs. Le problème primal devient :
N
1 X
min ∥w∥2 + C ξi
w,b,ξ 2 i=1
sous les contraintes yi (w · xi + b) ≥ 1 − ξi , ∀i
ξi ≥ 0, ∀i
2. Lagrangien
Le Lagrangien est donné par :
N N N
1 X X X
L(w, b, ξ, α, µ) = ∥w∥2 + C ξi − αi yi (w · xi + b) − 1 + ξi − µi ξi
2 i=1 i=1 i=1
où αi , µi ≥ 0.
2
3. Conditions d’Optimalité (KKT)
Les conditions nécessaires d’optimalité sont :
• ∂L
PN
∂w
=0 ⇒ w= i=1 αi yi xi
• ∂L
PN
∂b
=0 ⇒ i=1 αi y i = 0
• ∂L
∂ξi
=0 ⇒ αi + µi = C
• αi yi (w · xi + b) − 1 + ξi = 0, ∀i
• µi ξi = 0, ∀i
• ξi ≥ 0, αi ≥ 0, µi ≥ 0, ∀i
• yi (w · xi + b) ≥ 1 − ξi , ∀i
4. Problème Dual
En introduisant un noyau K(xi , xj ) = ϕ(xi ) · ϕ(xj ), le problème dual devient :
N N N
X 1 XX
max αi − αi αj yi yj K(xi , xj )
α
i=1
2 i=1 j=1
N
X
sous les contraintes αi y i = 0
i=1
0 ≤ αi ≤ C, ∀i
5. Calcul de b
Dans le cas non linéairement séparable, vous devez tenir compte des variables d’écart ξi , et la
contrainte devient :
yi (⟨w, xi ⟩ + b) ≥ 1 − ξi
En utilisant un seul vecteur support xi , vous pouvez calculer b avec la formule suivante :
b = yi − ⟨w, xi ⟩ + ξi
Pour plusieurs vecteurs supports, vous calculez chaque bi de la même manière et prenez la
moyenne :
1 X
b= (yi − ⟨w, xi ⟩ + ξi )
|S| i∈S