20 Régression ridge à noyau (KRR)
La régression ridge est une méthode de régularisation basée sur la méthode des moindres carrés pour la régression linéaire.
La régression ridge à noyau (kernel ridge regression, KRR) étend cette méthode à la régression non linéaire et non paramétrique, c’est-à-dire que la structure même du modèle est déterminée à partir des données et non fixée à l’avance, grâce aux noyaux.
Le modèle créée s’exprime ainsi : \hat{f}(\boldsymbol{x}) = \sum_{i=1}^m \beta_i K(\boldsymbol{x}_i, \boldsymbol{x}) avec l’apprentissage des paramètres \beta_i réalisé simplement par \boldsymbol{\beta }= (\boldsymbol{K} + \lambda\boldsymbol{I})^{-1} \boldsymbol{y} (voir ci-dessous pour les détails).
20.1 Formulation dans le RKHS
Apprendre un modèle de régression non linéaire peut être formulé comme l’apprentissage d’une fonction f dans un certain espace de fonctions. La méthode KRR se place dans un espace de Hilbert à noyau reproduisant (RKHS) \mathcal{H} engendré par un noyau K et cherche la fonction qui minimise à la fois l’erreur quadratique moyenne et un terme de régularisation donné par la norme de cette fonction au carré : \hat{f} = \arg\min_{f\in\mathcal{H}} \sum_{i=1}^m (y_i - f(\boldsymbol{x}_i))^2 + \lambda \|f\|^2 où l’hyperparamètre \lambda>0 règle le compromis entre l’attache aux données et la régularisation.
20.2 Formulation duale
Le problème d’apprentissage KRR peut être résolu efficacement grâce au théorème de représentation qui s’applique dans le RKHS. Celui-ci garantit que la solution est de la forme \hat{f} = \sum_{j=1}^m \beta_j K(\boldsymbol{x}_j, \cdot) avec les m exemples \boldsymbol{x}_j de la base d’apprentissage. Cela nous permet de reformuler la norme de f comme \begin{align*} \|f\|^2 &= \left\langle \sum_{i=1}^m \beta_i K(\boldsymbol{x}_i, \cdot), \sum_{j=1}^m \beta_j K(\boldsymbol{x}_j, \cdot) \right\rangle \\&=\sum_{i=1}^m \beta_i\sum_{j=1}^m \beta_j \left\langle K(\boldsymbol{x}_i, \cdot), K(\boldsymbol{x}_j, \cdot) \right\rangle =\sum_{i=1}^m\sum_{j=1}^m \beta_i \beta_j K(\boldsymbol{x}_i , \boldsymbol{x}_j) \end{align*} où la dernière étape vient de la propriété de reproduction du noyau.
En réinjectant cette forme dans le problème, nous obtenons la forme duale exprimée par rapport aux m variables réelles \beta_i : \min_{\beta_1,\dots,\beta_m} \sum_{i=1}^m \left(y_i - \sum_{j=1}^m \beta_j K(\boldsymbol{x}_j, \boldsymbol{x}_i)\right)^2 + \ \lambda \sum_{i=1}^m\sum_{j=1}^m \beta_i \beta_j K(\boldsymbol{x}_i , \boldsymbol{x}_j) ou, sous forme matricielle avec \boldsymbol{\beta}\in\mathbb{R}^m concaténant tous les \beta_i : \min_{\boldsymbol{\beta}\in\mathbb{R}^m} \|\boldsymbol{y} - \boldsymbol{K} \boldsymbol{\beta}\|^2 + \ \lambda \boldsymbol{\beta}^T \boldsymbol{K}\boldsymbol{\beta} avec la matrice de noyau \boldsymbol{K} = \begin{bmatrix} K(\boldsymbol{x}_1,\boldsymbol{x}_1) & \dots & K(\boldsymbol{x}_1,\boldsymbol{x}_m)\\ \vdots & & \\ K(\boldsymbol{x}_m,\boldsymbol{x}_1) & \dots & K(\boldsymbol{x}_m,\boldsymbol{x}_m) \end{bmatrix}
20.3 Solution
La solution de la forme duale peut êter calculée simplement en cherchant le vecteur \boldsymbol{\beta} qui annule le gradient de l’objectif J(\boldsymbol{\beta}) = \|\boldsymbol{y} - \boldsymbol{K} \boldsymbol{\beta}\|^2 + \ \lambda \boldsymbol{\beta}^T \boldsymbol{K}\boldsymbol{\beta} à minimiser, comme pour la régression ridge classique :
\begin{align*} \frac{\text{d} J(\boldsymbol{\beta})}{\text{d} \boldsymbol{\beta}} &= -2 \boldsymbol{K}^T (\boldsymbol{y} - \boldsymbol{K} \boldsymbol{\beta}) + 2\lambda \boldsymbol{K}\boldsymbol{\beta }\\& = -2\boldsymbol{K}^T\boldsymbol{y} + 2 (\boldsymbol{K}^T\boldsymbol{K} + \lambda\boldsymbol{K})\boldsymbol{\beta }\\ &= -2\boldsymbol{K}\boldsymbol{y} + 2 (\boldsymbol{K}\boldsymbol{K} + \lambda\boldsymbol{K})\boldsymbol{\beta } \end{align*} où la dernière étape utilise la symétrie de la matrice de noyau (elle-même induite par la symétrie de la fonction noyau K).
Cela donne une solution caractérisée par \boldsymbol{\beta }= (\boldsymbol{K}\boldsymbol{K} + \lambda\boldsymbol{K})^{-1} \boldsymbol{K}\boldsymbol{y} = [\boldsymbol{K}(\boldsymbol{K} + \lambda\boldsymbol{I})]^{-1} \boldsymbol{K}\boldsymbol{y} =(\boldsymbol{K} + \lambda\boldsymbol{I})^{-1} \boldsymbol{K}^{-1} \boldsymbol{K}\boldsymbol{y} et donc un vecteur de paramètres obtenu simplement par \boldsymbol{\beta }= (\boldsymbol{K} + \lambda\boldsymbol{I})^{-1} \boldsymbol{y}
def kernel(X1,X2,sigma):
K = np.zeros((len(X1),len(X2)))
for i in range(len(X1)):
for j in range(len(X2)):
K[i,j] = np.exp(-np.sum((X1[i] - X2[j])**2)/(2*sigma**2))
return K
def krr(X,y, sigma, Lambda):
K = kernel(X,X,sigma)
beta = np.linalg.inv(K + Lambda * np.eye(len(y))) @ y
return beta
def krrpred(X,Xt,beta,sigma):
K = kernel(Xt,X,sigma)
return K@beta
x = 6*np.random.rand(30)-3
y = np.sinc(x) + np.random.randn(30)*0.15
Lambda = 0.5
xt = np.arange(-3,3,0.05)
for sigma in [0.2, 0.5, 1]:
beta = krr(x,y, Lambda, sigma)
plt.figure()
plt.plot(x,y, "ok")
plt.plot(xt,np.sinc(xt),"--g")
plt.plot(xt, krrpred(x, xt,beta, sigma), "-b")
plt.legend(["Données", "sinc(x)", "f(x)"])
plt.xlabel("x")
plt.ylabel("y")
t=plt.title("Kernel ridge regression pour lambda=0.2")
