Différence entre la régression primitive, double et Kernel Ridge

18

Quelle est la différence entre la régression primitive , double et Kernel Ridge? Les gens utilisent les trois, et à cause de la notation différente que tout le monde utilise à différentes sources, il m'est difficile de suivre.

Alors, quelqu'un peut-il me dire en termes simples quelle est la différence entre ces trois? De plus, quels pourraient être certains avantages ou inconvénients de chacun, et quelle peut être leur complexité?

Jim Blum
la source

Réponses:

39

Réponse courte: aucune différence entre Primal et Dual - il s'agit uniquement de la manière d'arriver à la solution. La régression de crête du noyau est essentiellement la même que la régression de crête habituelle, mais utilise l'astuce du noyau pour devenir non linéaire.

Régression linéaire

Tout d'abord, une régression linéaire habituelle des moindres carrés essaie d'ajuster une ligne droite à l'ensemble des points de données de telle sorte que la somme des erreurs au carré soit minimale.

entrez la description de l'image ici

Nous paramétrons la ligne la mieux ajustée avec et pour chaque point de données nous voulons . Soit l'erreur - la distance entre les valeurs prédites et vraies. Notre objectif est donc de minimiser la somme des erreurs quadratiques où - une matrice de données avec chaque étant une ligne, et un vecteur avec tous les .ww ( x i , y i ) (xi,yi)w T x iy i wTxiyie i = y i - w T x iei=yiwTxie 2 i = e 2 = X w - y 2e2i=e2=Xwy2 X = [ - x 1- - x 2- - x n- ]X=x1x2xnxixiy=(y1,...,Yn)  y=(y1, ... ,yn)yiyi

Ainsi, l'objectif est , et la solution est (connue sous le nom d '"équation normale").min wX w - y 2 minwXwy2w =( X T X ) - 1 X T yw=(XTX)1XTy

Pour un nouveau point de données invisible nous prédisons sa valeur cible comme .x xy y^y = w T xy^=wTx

Régression de crête

Lorsqu'il existe de nombreuses variables corrélées dans les modèles de régression linéaire, les coefficients peuvent devenir mal déterminés et avoir beaucoup de variance. L' une des solutions à ce problème est de limiter le poids afin qu'ils ne dépassent pas un certain budget . Cela équivaut à utiliser la régularisation , également connue sous le nom de "décroissance du poids": cela diminuera la variance au prix de manquer parfois les bons résultats (c'est-à-dire en introduisant un biais).w www C CL 2L2

L'objectif devient maintenant , avec comme paramètre de régularisation. En parcourant les mathématiques, nous obtenons la solution suivante: . C'est très similaire à la régression linéaire habituelle, mais ici nous ajoutons à chaque élément diagonal de .min wX w -y2 +λW 2minwXwy2+λw2 λ λw = ( X T X + λI ) - 1 X T yw=(XTX+λI)1XTy λ λX T XXTX

Notez que nous pouvons réécrire comme (voir ici pour plus de détails). Pour un nouveau point de données invisible nous prédisons sa valeur cible comme . Soit . Alors .w ww = X T( X X T + λI ) - 1 y w=XT(XXT+λI)1yx y y = x T w = x T X Txy^( X X T + λI ) - 1 yy^=xTw=xTXT(XXT+λI)1y α = ( X X T + λI ) - 1 y α=(XXT+λI)1yy = x T X T α = n Σ i = 1 α ix T x iy^=xTXTα=i=1nαixTxi

Formule double de régression de crête

Nous pouvons avoir un regard différent sur notre objectif - et définir le problème de programme quadratique suivant:

min e , w n i = 1 e 2 imine,wi=1ne2i st pour et . e i = y i - w T x iei=yiwTxi i=1. .n i=1..nw 2Cw2C

C'est le même objectif, mais exprimé quelque peu différemment, et ici la contrainte sur la taille de est explicite. Pour le résoudre, nous définissons le lagrangien - c'est la forme primitive qui contient les variables primaires et . Ensuite, nous l'optimisons par et . Pour obtenir la double formulation, nous trouvé et dans .w wL p ( w , e ; C ) Lp(w,e;C)w we ee ew we ew wL p ( w , e ; C )Lp(w,e;C)

Donc, . En prenant les dérivés wrt et , nous obtenons et . En laissant , et en remettant et dans , nous obtenons double lagrangienL p ( w , e ;C)= e 2 + β T ( y -X w - e )-λ( W 2 - C ) Lp(w,e;C)=e2+βT(yXwe)λ(w2C)w we ee =12 βe=12βw=12 λ XTβw=12λXTβα=12 λ βα=12λβeewwLp(w,e;C)Lp(w,e;C)Ld(α,λ;C)=-λ2α2+2λα T y - λ X T α - λ CLd(α,λ;C)=λ2α2+2λαTyλXTαλC . Si nous prenons un dérivé wrt , nous obtenons - la même réponse que pour la régression habituelle de Kernel Ridge. Il n'est pas nécessaire de prendre un dérivé wrt - cela dépend de , qui est un paramètre de régularisation - et il crée également paramètre de régularisation .α αα = ( X X T - λ I ) - 1 yα=(XXTλI)1y λ λC Cλλ

Ensuite, mettez à la solution de forme primitive pour , et obtenez . Ainsi, la forme double donne la même solution que la régression Ridge habituelle, et c'est juste une façon différente d'arriver à la même solution.α αw ww =12 λ XTβ=XTαw=12λXTβ=XTα

Régression de Kernel Ridge

Les noyaux sont utilisés pour calculer le produit interne de deux vecteurs dans un espace de fonctionnalité sans même le visiter. Nous pouvons voir un noyau comme , bien que nous ne sachions pas ce qu'est - nous savons seulement qu'il existe. Il existe de nombreux noyaux, par exemple RBF, Polynonial, etc.k kk ( x 1 , x 2 ) = ϕ ( x 1 ) T ϕ ( x 2 ) k(x1,x2)=ϕ(x1)Tϕ(x2)ϕ ( )ϕ()

Nous pouvons utiliser des noyaux pour rendre notre régression de crête non linéaire. Supposons que nous ayons un noyau . Soit une matrice où chaque ligne est , c'est-à-direk(x1,x2)=ϕ(x1)Tϕ(x2)k(x1,x2)=ϕ(x1)Tϕ(x2)Φ(X)Φ(X)ϕ(xi)ϕ(xi)Φ(X)=[ϕ(x1)ϕ(x2)ϕ(xn)]Φ(X)=ϕ(x1)ϕ(x2)ϕ(xn)

Maintenant, nous pouvons simplement prendre la solution pour la régression de crête et remplacer chaque par : . Pour un nouveau point de données invisible nous prédisons sa valeur cible comme .XXΦ(X)Φ(X)w=Φ(X)T(Φ(X)Φ(X)T+λI)1yw=Φ(X)T(Φ(X)Φ(X)T+λI)1yxxˆyy^ˆy=ϕ(x)TΦ(X)T(Φ(X)Φ(X)T+λI)1yy^=ϕ(x)TΦ(X)T(Φ(X)Φ(X)T+λI)1y

Tout d'abord, nous pouvons remplacer par une matrice , calculée comme . Alors, est . Nous avons donc réussi à exprimer chaque produit scalaire du problème en termes de noyaux.Φ(X)Φ(X)TΦ(X)Φ(X)TKK(K)ij=k(xi,xj)(K)ij=k(xi,xj)ϕ(x)TΦ(X)Tϕ(x)TΦ(X)Tni=1ϕ(x)Tϕ(xi)=ni=1k(x,xj)i=1nϕ(x)Tϕ(xi)=i=1nk(x,xj)

Enfin, en laissant (comme précédemment), on obtientα=(K+λI)1yα=(K+λI)1yˆy=ni=1αik(x,xj)y^=i=1nαik(x,xj)

Les références

Alexey Grigorev
la source
1
Je suis impressionné par la discussion bien organisée. Cependant, votre première référence aux «valeurs aberrantes» m'a confondu. Il semble que les poids appliquer aux des variables plutôt que les cas, alors comment la régression serait exactement la crête de l' aide rendre la solution robuste aux périphériques cas , comme le suggère l'illustration? w
whuber
Excellente réponse, Alexey (même si je n'appellerais pas cela des "mots simples")! +1 sans poser de questions. Vous aimez écrire en LaTeX, n'est-ce pas?
Aleksandr Blekh
2
Je soupçonne que vous pourriez confondre certaines choses fondamentales ici. AFAIK, la régression des crêtes n'est ni une réponse ni un moyen de faire face aux «observations bruyantes». OLS le fait déjà. La régression de crête est un outil utilisé pour faire face à la quasi-colinéarité entre les régresseurs. Ces phénomènes sont complètement différents du bruit dans la variable dépendante.
whuber
1
+1 whuber. Alexey, vous avez raison, il est trop adapté - il y a trop de paramètres pour les données disponibles - pas vraiment de bruit. [et ajoutez suffisamment de dimensions pour une taille d'échantillon fixe et «tout» ensemble de données devient colinéaire]. Ainsi, une meilleure image 2D pour RR serait tous les points regroupés autour de (0,1) avec un seul point à (1,0) [«justifiant» le paramètre de pente]. Voir ESL fig 3.9, page 67 web.stanford.edu/~hastie/local.ftp/Springer/OLD/… . regardez également la fonction de coût primaire: pour augmenter le poids de 1 unité, l'erreur doit diminuer de unité1/λ
seanv507
1
Je pense que vous vouliez ajouter aux éléments diagonaux de non pas soustraire (?) Dans la section de régression des crêtes. J'ai appliqué la modification. λXTX
Heteroskedastic Jim