Le SVM classique & Forme duale et astuce du noyau

Le SVM classique

L’idée en une phrase

Le SVM (Support Vector Machine) cherche l’hyperplan séparateur de marge maximale entre deux classes : la frontière qui s’éloigne le plus possible des points les plus proches de chaque côté. Dans la boucle variationnelle hybride, le SVM ne joue pas le rôle du QPU mais celui de l’optimiseur classique — c’est la moitié classique du calcul, un programme quadratique convexe sur lequel un noyau quantique viendra se brancher, les données n’entrant dans le problème que par leurs produits scalaires.

Analogie : Tracer la plus large avenue possible entre deux quartiers. Pour séparer les maisons rouges des maisons bleues, on ne choisit pas une rue au hasard : on prend celle qui laisse le plus d’espace de part et d’autre. Seules les maisons bordant directement l’avenue — les vecteurs de support — décident de son tracé. Déplacer une maison enfouie au cœur d’un quartier ne change rien.

Points clés

• L’hyperplan optimal minimise ‖w‖²/2 sous la contrainte y_i(w·x_i + b) ≥ 1 pour chaque point. C’est un programme quadratique convexe : la solution est un optimum global, contrairement à l’entraînement d’un réseau de neurones ou d’un circuit variationnel.
• Les vecteurs de support sont les seuls points situés exactement sur la marge (y_i(w·x_i + b) = 1). Ils déterminent entièrement la frontière ; tous les autres points sont inactifs.
• La marge vaut 2/‖w‖. La maximiser revient à minimiser ‖w‖ — d’où la forme du problème d’optimisation.
• Marge dure (données linéairement séparables) contre marge souple : on introduit des variables de relâchement ξ_i ≥ 0 et un paramètre C qui arbitre entre largeur de marge et tolérance aux erreurs. Un C grand pénalise fortement les erreurs (variance ↑) ; un C petit élargit la marge (biais ↑) — le compromis biais-variance vu au chapitre 3-4.
• Le SVM est déterministe et parcimonieux : la décision sign(w·x + b) ne dépend que des vecteurs de support, pas du volume total des données.

Exemple concret

Deux points en 2D : un positif en (3, 3), un négatif en (1, 1). L’hyperplan de marge maximale est la médiatrice du segment qui les joint, de vecteur normal dirigé selon (1, 1). En imposant la marge fonctionnelle unité aux deux points — w·(3,3) + b = +1 et w·(1,1) + b = −1 — on résout w = (0.5, 0.5) et b = −2. La norme ‖w‖ = √0.5 ≈ 0.707 donne une marge 2/‖w‖ ≈ 2.83. Les deux points sont vecteurs de support : ils sont les seuls, et ils suffisent à fixer la frontière.

Marge dure contre marge souple

Code Python — entraîner un SVM linéaire et lire ses vecteurs de support

# scikit-learn fournit le solveur du programme quadratique ;
# on lit ensuite directement w, b, la marge et les vecteurs de support.
import numpy as np
from sklearn.svm import SVC

# Jeu minimal, linéairement séparable
X = np.array([[3.0, 3.0], [1.0, 1.0]])
y = np.array([1, -1])

# Un C très grand approche la marge dure (aucune erreur tolérée)
clf = SVC(kernel="linear", C=1e6)
clf.fit(X, y)

w = clf.coef_[0]                 # vecteur normal à l'hyperplan
b = clf.intercept_[0]            # biais
marge = 2.0 / np.linalg.norm(w)

print("w =", np.round(w, 3))                  # ≈ [0.5 0.5]
print("b =", round(b, 3))                     # ≈ -2.0
print("marge = 2/||w|| =", round(marge, 3))   # ≈ 2.828
print("vecteurs de support :", clf.support_vectors_.tolist())

Piège courant : « Le SVM exploite l’ensemble des données d’entraînement pour tracer sa frontière » est inexact. Seuls les vecteurs de support — les points sur la marge — interviennent. Retirer n’importe quel autre point laisse l’hyperplan strictement identique. Cette parcimonie est une propriété centrale : la frontière se résume à une poignée de points critiques.

Forme duale et astuce du noyau

L’idée en une phrase

La forme duale du SVM, obtenue par les multiplicateurs de Lagrange, n’exprime le problème qu’à travers les produits scalaires x_i·x_j entre points. L’astuce du noyau (kernel trick) y substitue un noyau K(x_i, x_j) = ⟨φ(x_i), φ(x_j)⟩, produit scalaire dans un espace de redescription de très grande dimension jamais construit explicitement — exactement le produit scalaire que le noyau quantique remplacera par une fidélité entre états encodés (chapitre 17-18).

Analogie : Un sommelier comparant deux vins. Plutôt que de dresser la liste exhaustive de tous les composés chimiques de chaque vin — le vecteur de redescription φ, potentiellement immense —, l’expert énonce directement un score de ressemblance entre les deux. Le noyau procède ainsi : il livre la similarité sans jamais énumérer les caractéristiques. Construire φ serait coûteux, parfois impossible ; mesurer la ressemblance reste simple.

Points clés

• La forme duale maximise Σ α_i − ½ ΣΣ α_i α_j y_i y_j (x_i·x_j) sous les contraintes Σ α_i y_i = 0 et 0 ≤ α_i ≤ C. Les inconnues sont les multiplicateurs α_i, un par point.
• Les données n’apparaissent que via les produits scalaires x_i·x_j. C’est la porte d’entrée du noyau : il suffit de remplacer ce produit pour changer d’espace de représentation.
• L’astuce du noyau substitue K(x_i, x_j) = ⟨φ(x_i), φ(x_j)⟩ au produit scalaire. La projection φ peut être de dimension énorme — infinie pour le noyau RBF — mais seul K est calculé, jamais φ.
• Théorème de Mercer : une fonction K est un noyau valide si et seulement si sa matrice de Gram (toutes les valeurs K(x_i, x_j)) est semi-définie positive. Cette condition garantit que le problème dual reste convexe.
• La décision duale s’écrit sign(Σ α_i y_i K(x_i, x) + b) : seuls les vecteurs de support (α_i > 0) y contribuent. Le coût dépend de leur nombre, pas de la dimension de φ.

Exemple concret

Le noyau polynomial de degré 2 illustre l’astuce. Pour x = (1, 2) et y = (3, 1), le produit scalaire vaut x·y = 1·3 + 2·1 = 5, et le noyau K(x, y) = (x·y)² = 25. La redescription implicite associée est φ(v) = (v₁², √2·v₁v₂, v₂²), soit φ(x) = (1, 2√2, 4) et φ(y) = (9, 3√2, 1). Leur produit scalaire explicite vaut 1·9 + 2√2·3√2 + 4·1 = 9 + 12 + 4 = 25. Identique au noyau, mais obtenu sans jamais former φ : c’est tout l’intérêt.

Trois noyaux classiques

Code Python — vérifier l’astuce du noyau (degré 2)

# Le noyau polynomial (x·y)² égale le produit scalaire dans l'espace
# de redescription φ — sans jamais former φ pour calculer le noyau.
import numpy as np

x = np.array([1.0, 2.0])
y = np.array([3.0, 1.0])

# Noyau calculé directement (astuce du noyau)
K_direct = (x @ y) ** 2

# Produit scalaire explicite dans l'espace de redescription de dimension 3
phi = lambda v: np.array([v[0] ** 2, np.sqrt(2) * v[0] * v[1], v[1] ** 2])
K_explicite = phi(x) @ phi(y)

print("K direct      =", round(K_direct, 6))      # 25.0
print("<phi(x),phi(y)> =", round(K_explicite, 6)) # 25.0 — identiques

Code Python (Qiskit) — un noyau quantique comme fidélité

# Aperçu du chapitre 17-18 : le noyau quantique calcule une entrée de la
# matrice de Gram comme fidélité |⟨φ(x)|φ(y)⟩|² entre deux états encodés.
# La redescription φ est ici réalisée par un circuit, non par une formule.
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def feature_map(x):
    """Encoder un vecteur 2D dans un état à 2 qubits (angle + corrélation ZZ)."""
    qc = QuantumCircuit(2)
    qc.h([0, 1])
    qc.rz(x[0], 0)
    qc.rz(x[1], 1)
    qc.cx(0, 1)
    qc.rz(x[0] * x[1], 1)   # terme d'intrication : corrélation entre features
    qc.cx(0, 1)
    return qc

def noyau_quantique(x, y):
    """K(x, y) = |⟨φ(x)|φ(y)⟩|² — produit scalaire dans l'espace de Hilbert."""
    etat_x = Statevector(feature_map(x))
    etat_y = Statevector(feature_map(y))
    return abs(etat_x.inner(etat_y)) ** 2

x = np.array([0.3, 0.7])
y = np.array([0.5, 0.1])
print("K(x, x) =", round(noyau_quantique(x, x), 6))   # 1.0 — fidélité maximale
print("K(x, y) =", round(noyau_quantique(x, y), 6))   # une valeur dans [0, 1]

Piège courant : « L’astuce du noyau projette d’abord les données dans l’espace de grande dimension, puis y calcule le produit scalaire » est inexact. La projection φ n’est jamais effectuée : le noyau K(x, y) est évalué directement. C’est précisément ce qui rend exploitable un espace de redescription de dimension infinie (RBF) — l’énumérer point par point serait impossible, le noyau le contourne.

Fil rouge — la frontière quantique/classique

Ce chapitre pose la moitié classique d’un schéma hybride distinct de la boucle variationnelle. La forme duale isole les données dans des produits scalaires x_i·x_j ; la méthode à noyau quantique (chapitre 17-18) délègue au QPU le calcul de ces produits sous forme de fidélité K(x_i, x_j) = |⟨φ(x_i)|φ(x_j)⟩|² entre états préparés par un circuit, tandis que l’optimisation duale — un programme quadratique convexe — reste entièrement classique. Contrairement à la boucle variationnelle, le QPU n’est pas réentraîné à chaque pas : il est interrogé une seule fois pour remplir la matrice de noyau (O(N²) estimations de fidélité), puis l’optimiseur classique prend le relais. Le compromis expressivité ↔ entraînabilité se déplace alors : faute de paramètres θ à entraîner, il n’y a pas de plateaus de Barren, mais une autre pathologie guette — la concentration exponentielle du noyau, dont les entrées tendent vers une constante à mesure que le nombre de qubits croît, rendant la matrice de Gram quasi singulière et le SVM aveugle.

Kata Qiskit — la matrice de noyau quantique

Objectif : construire la matrice de Gram d’un noyau quantique (fidélité entre états encodés) pour un petit jeu de données, et vérifier qu’elle satisfait les propriétés d’un noyau valide au sens de Mercer.

Squelette :

# kata_day_15_16.py
import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def feature_map(x):
    """Encoder un vecteur 2D dans un état à 2 qubits (angle + corrélation ZZ)."""
    qc = QuantumCircuit(2)
    qc.h([0, 1])
    qc.rz(x[0], 0)
    qc.rz(x[1], 1)
    # TODO 1 : ajouter l'intrication ZZ — cx(0,1), puis rz(x[0]*x[1], 1), puis cx(0,1)
    return qc

def noyau_quantique(x, y):
    """K(x, y) = |⟨φ(x)|φ(y)⟩|² : fidélité entre deux états encodés."""
    # TODO 2 : construire les deux Statevector et renvoyer |⟨φ(x)|φ(y)⟩|²
    #          (indice : Statevector(...).inner(...) donne le produit scalaire)
    return 0.0

def matrice_noyau(X):
    """Matrice de Gram NxN : K[i, j] = noyau_quantique(X[i], X[j])."""
    n = len(X)
    K = np.zeros((n, n))
    # TODO 3 : remplir K[i, j] pour tous les couples (i, j)
    return K

Auto-correction :

# test_kata_day_15_16.py
import numpy as np
from kata_day_15_16 import feature_map, noyau_quantique, matrice_noyau

X = np.array([[0.1, 0.2], [1.0, 0.5], [-0.3, 0.8], [0.6, -0.4]])

# Test 1 : la feature map encode bien l'intrication ZZ (2 portes CNOT)
qc = feature_map(X[0])
assert qc.num_qubits == 2, "Le circuit doit avoir 2 qubits"
n_cx = sum(1 for instr in qc.data if instr.operation.name == "cx")
assert n_cx == 2, f"2 portes CNOT attendues pour l'intrication ZZ, trouvé {n_cx}"

# Test 2 : la fidélité d'un point avec lui-même vaut 1
assert abs(noyau_quantique(X[0], X[0]) - 1.0) < 1e-9, "K(x, x) doit valoir 1"

# Test 3 : matrice symétrique, diagonale unité, entrées dans [0, 1]
K = matrice_noyau(X)
assert K.shape == (4, 4), "La matrice doit être 4x4"
assert np.allclose(K, K.T, atol=1e-9), "La matrice de noyau doit être symétrique"
assert np.allclose(np.diag(K), 1.0, atol=1e-9), "La diagonale doit valoir 1"
assert K.min() >= -1e-9 and K.max() <= 1 + 1e-9, "Les entrées doivent être dans [0, 1]"

# Test 4 : matrice semi-définie positive (condition de Mercer)
vp_min = np.linalg.eigvalsh(K).min()
assert vp_min >= -1e-8, f"La matrice doit être SDP (Mercer), valeur propre min = {vp_min}"

print("Kata validé !")

import numpy as np
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

def feature_map(x):
    qc = QuantumCircuit(2)
    qc.h([0, 1])
    qc.rz(x[0], 0)
    qc.rz(x[1], 1)
    qc.cx(0, 1)               # TODO 1 : intrication
    qc.rz(x[0] * x[1], 1)     # corrélation entre les deux features
    qc.cx(0, 1)
    return qc

def noyau_quantique(x, y):
    etat_x = Statevector(feature_map(x))   # TODO 2
    etat_y = Statevector(feature_map(y))
    return abs(etat_x.inner(etat_y)) ** 2

def matrice_noyau(X):
    n = len(X)
    K = np.zeros((n, n))
    for i in range(n):                     # TODO 3
        for j in range(n):
            K[i, j] = noyau_quantique(X[i], X[j])
    return K