Comment dériver la solution de régression de crête?

41

J'ai des problèmes avec la dérivation de la solution pour la régression de crête.

Je connais la solution de régression sans le terme de régularisation:

β=(XTX)1XTy.

Mais après avoir ajouté le terme L2 à la fonction de coût, comment se fait-il que la solution devienneλβ22

β=(XTX+λI)1XTy.
utilisateur34790
la source

Réponses:

24

Il suffit de modifier la fonction de perte en ajoutant la pénalité. En termes de matrice, la fonction de perte quadratique initiale devient

(YXβ)T(YXβ)+λβTβ.
Dériver par rapport à β conduit à l'équation normale
XTY=(XTX+λI)β
qui mène à l'estimateur de Ridge.
johnny
la source
1
Comment se fait-il que la dérivée de λβTβ soit égale à λIβ
user34790 le
4
@ user34790 Ce n'est pas. C'est égal à 2λβ . Mais le 2 annule avec 2 similaires sur les autres termes. Bien sûr, le facteur I est comme un facteur de 1 en algèbre "normale", vous pouvez le multiplier où bon vous semble sans rien changer.
Bill
4
@bill: ici vous avez besoin du pour obtenir une matrice de la dimension correcte, de sorte que l'addition fonctionne avec : est juste un scalaireX T X λIXTXλ
Henry
48

Construisons sur ce que nous savons, à savoir que chaque fois que la matrice de modèle est , la réponse -vector est et le paramètre -vector est , la fonction objectifX nn×pXnp βypβ

f(β)=(yXβ)(yXβ)

(qui est la somme des carrés des résidus) est minimisé quand résout les équations normalesβ

(XX)β=Xy.

La régression de crête ajoute un autre terme à la fonction objectif (généralement après normalisation de toutes les variables afin de les rendre communes), demandant de minimiser

(yXβ)(yXβ)+λββ

pour une constante non-négative . C'est la somme des carrés des résidus plus un multiple de la somme des carrés des coefficients eux-mêmes (ce qui rend évident qu'il a un minimum global). Parce que , il a une racine carrée positive .λ 0λλ0ν2=λ

Considérons la matrice augmentée de lignes correspondant à fois la matrice d'identité :νXνIp×pI

X=(XνI)

Lorsque le vecteur est étendu de manière similaire avec zéros à la fin de , le produit matriciel de la fonction objectif ajoute termes supplémentaires de la forme à l'objectif initial. Par conséquentp y p ( 0 - ν β i ) 2 = λ βypyp(0νβi)2=λβi2

(yXβ)(yXβ)=(yXβ)(yXβ)+λββ.

A partir de la forme de l’expression de gauche, il est immédiat que les équations de Normal soient

(XX)β=Xy.

Comme nous avons joint des zéros à la fin de , le côté droit est identique à . Du côté gauche est ajouté à l'original . Par conséquent, les nouvelles équations normales simplifientX y ν 2 I = λyXyX ' Xν2I=λIXX

(XX+λI)β=Xy.

En plus d'être conceptuellement économique - aucune nouvelle manipulation n'est nécessaire pour obtenir ce résultat - il est également économique en calcul: votre logiciel de calcul des moindres carrés ordinaires effectuera également une régression de crête sans aucune modification. (Il peut néanmoins être utile dans les gros problèmes d’utiliser un logiciel conçu à cet effet, car il exploitera la structure particulière de pour obtenir des résultats efficaces pour un intervalle de très espacé , ce qui vous permettra d’explorer comment les réponses varient. avec .)Xλλλ

Une autre beauté de cette façon de voir les choses est de savoir comment cela peut nous aider à comprendre la régression de crête. Quand on veut vraiment comprendre la régression, il est presque toujours utile d’y penser géométriquement: les colonnes de constituent des vecteurs dans un espace vectoriel réel de dimension . En joignant à , en les prolongeant ainsi de vecteurs à vecteurs, nous intégrons dans un espace plus grand en incluant "imaginaire", directions orthogonales. La première colonne dep n ν I X n n + p R n R n + p p X ν p p th ν ν p ν 0XpnνIXnn+pRnRn+ppXreçoit un petit composant imaginaire de taille , l’allongeant ainsi et le déplaçant hors de l’espace généré par les colonnes originales . Le deuxième, troisième, ..., colonnes sont également rallongé et déplacé hors de l'espace d' origine du même montant - mais dans différentes directions nouvelles. Par conséquent, toute colinéarité présente dans les colonnes d'origine sera immédiatement résolue. De plus, plus devient grand, plus ces nouveaux vecteurs se rapprochent deνppthννpdirections imaginaires: elles deviennent de plus en plus orthonormées. En conséquence, la solution des équations de Normal deviendra immédiatement possible et deviendra rapidement numériquement stable à mesure que augmente à partir de .ν0

Cette description du processus suggère certaines approches novatrices et créatives pour résoudre les problèmes que Ridge Regression a été conçu pour traiter. Par exemple, en utilisant quelque moyen que ce soit (comme la décomposition de la variance décrite par Belsley, Kuh et Welsch dans leur livre de 1980 sur Regression Diagnostics , chapitre 3), vous pourrez peut-être identifier des sous-groupes de colonnes presque colinéaires de , où chaque sous-groupe est presque orthogonal à un autre. Il vous suffit d'adjoindre autant de lignes à (et de zéros à ) qu'il y a d'éléments dans le groupe le plus grand, en dédiant une nouvelle dimension "imaginaire" pour déplacer chaque élément d'un groupe loin de ses frères et soeurs: vous n'avez pas besoin de imaginaire dimensions pour le faire.X y pXXyp

whuber
la source
2
Le dernier auteur du livre est Welsch, pas gallois.
Mark L. Stone
1
Whoa, cela m'a juste frappé l'esprit. Y a-t-il une discussion sur ce qui se passe quand ceci est généralisé en dehors des modèles linéaires, c'est-à-dire aux GLM? La pénalité ne devrait pas être identique à la régression de crête ... mais cette interprétation implique que ce serait toujours un estimateur potentiellement utile!
Cliff AB
2
@ Cliff C'est une suggestion très intéressante. Cependant, étant donné que les estimations GLM dépendent de manière plus compliquée de et que leurs estimateurs ne peuvent généralement pas être factorisés sous la forme comme ils le sont pour MCO (où et ), il peut être difficile d'établir une relation utile entre l' imposition d' une fonction de pénalité et de modifier les colonnes de . En particulier, il est difficile de savoir comment les valeurs de devraient être augmentées pour que cela fonctionne. β = g ( X ) h ( y ) g ( X ) = ( X ' X ) - 1 X « h ( y ) = y X yX
β^=g(X)h(y)
g(X)=(XX)1Xh(y)=yXy
whuber
1
Oui, il faudrait un peu de réflexion pour essayer de déterminer quelle est la peine, mais cela ne me préoccupe pas tellement. L'idée de ce qui à utiliser est généralement pas facile non plus ... sauf peut - être dans le cas de la régression logistique, où nous pourrions ajouter deux y * s »; un des 0 et un des 1. Cette augmentation serait alors une version plus générale de "l'estimateur binomial +2" (le nom de cet estimateur est plus approprié, ce qui correspond essentiellement à l'estimation de p à partir d'une distribution binomiale en utilisant la moyenne postérieure). l'estimation avec un préalable uniforme sur p ). y ypp
Cliff AB
@ Mark Merci pour la correction. Vous pouvez dire que je partais de mémoire ... :-).
whuber
20

minβ(YβTX)T(YβTX)+λβTβ

Notez maintenant que et Ensemble nous arrivons à la condition du premier ordre Isoler donne la solution:

(YβTX)T(YβTX)β=2XT(YβTX)
λβTββ=2λβ.
XTY=XTXβ+λβ.
β
β=(XTX+λI)1XTY.
Pthesling
la source
9

Je suis récemment tombé sur la même question dans le contexte de P-Splines et, comme le concept est le même, je souhaite donner une réponse plus détaillée sur la dérivation de l'estimateur de crête.

Nous commençons par une fonction de critère pénalisée qui diffère de la fonction de critère classique MCO par son terme de pénalisation dans le dernier sommand:

CriterionRidge=i=1n(yixiTβ)2+λj=1pβj2

  • la quantité de covariables utilisées dans le modèlep=
  • votre prédicteur linéaire standardxiTβ=
  • le premier sommet représente la MSE (divergence au carré de la prédiction par rapport à la valeur réelle) que nous voulons minimiser comme d'habitude
  • le deuxième sommet représente la pénalisation que nous appliquons sur les coefficients. Nous sommes ici dans le contexte Ridge qui implique une mesure de distance euclidienne et donc le degré 2 dans le terme de pénalisation. Dans le cas d'une pénalisation de lasso, nous appliquerions un degré de 1 et produirions un estimateur totalement différent.

Nous pouvons réécrire ce critère en notation matricielle et le décomposer:

CriterionRidge=(yXβ)T(yXβ)+λβTβ

=yTyβTXTyyTXβ+βTxTXβ+λβTβ

avec I étant la matrice d'identité=yTyβTXTyβTXTy+βTXTXβ+βTλIβI

=yTy2βTXTy+βT(XTX+λI)β

Maintenant, nous cherchons le qui minimise notre critère. Nous utilisons entre autres la règle de différenciation matricielle x T A xβqueon peut appliquer ici(XTX+λI)Rn×n: xTAxx=(A+AT)x=A symmetric2Ax(XTX+λI)Rn×n

CriterionRidgeβ=2XTy+2(XTX+λI)β=!0

(XTX+λI)β=XTy

et voilàβ^=(XTX+λI)1XTy

Jann Goschenhofer
la source
@Jahn, pouvez-vous s'il vous plaît expliquer comment est devenu β T X T y ? Je pense que vous venez d'appliquer la transposition, d'accord. Cependant, vous ne pouvez pas appliquer la transposition à un terme sans l'appliquer à toutes les équations. Qu'est-ce que j'oublie ici?
yTXβ
βTXTy
theateist
1
@theateist Un scalaire transposé est le même scalaire.
Konstantin
2

Il manque quelques éléments importants dans les réponses fournies.

  1. La solution pour est dérivé du premier ordre condition nécessaire: f r i d g e ( β , λ )βqui donnedes =(XTX+λI)-1XTY. Mais est-ce suffisant? Autrement dit, la solution est un minimum global que sifridge(β,λ)est strictement convexe. Cela peut être montré pour être vrai.fridge(β,λ)β=0β=(XTX+λI)1XTYfridge(β,λ)

  2. Une autre façon de considérer le problème est de voir l'équivalence entre et f O L S ( β ) = ( Y - β T X ) T ( Y - β T X ) contraint de | | β | | 2 2t . OLS signifie «moindres carrés ordinaires». De ce point de vue f r ifridge(β,λ)fOLS(β)=(YβTX)T(YβTX)||β||22tn'est que la fonction lagrangienne utilisée pour trouver les minima globaux de la fonction objectif convexe f O L S (β)contrainte de la fonction convexe | | β | | 2 2 .fridge(β,λ)fOLS(β)||β||22

Une bonne explication de ces points et de la dérivation de peut être trouvée dans ces notes de cours: http://math.bu.edu/people/cgineste/classes/ma575/p/w14_1.pdfβ

Davor Josipovic
la source