Dérivation d'une solution de lasso sous forme fermée

52

Pour le problème de lasso tels que \ | \ beta \ | _1 \ leq t . Je vois souvent le résultat de seuillage souple \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS}} | - \ gamma) ^ + pour le cas X orthonormé . On prétend que la solution peut être "facilement démontrée", mais je n'ai jamais vu de solution efficace. Quelqu'un en a-t-il déjà vu une ou a-t-il déjà fait la dérivation?minβ(YXβ)T(YXβ)β1t

βjlasso=sgn(βjLS)(|βjLS|γ)+
X
Gary
la source
Cela semble un peu confus. Au début, vous assumez une contrainte t et dans la solution, vous introduisez un paramètre γ . J'imagine que vous avez l'intention de relier ces deux problèmes via le double problème, mais vous pouvez peut-être préciser ce que vous recherchez.
Cardinal
2
Répondre partiellement à @cardinal, trouver le β qui minimise (YXβ)(YXβ) soumis à β1t équivaut à trouver le β qui minimise (YXβ)(YXβ)+γj|βj|. Il existe une relation 1-1 entre t et γ . Pour "facilement" comprendre pourquoi le résultat du seuillage souple est vrai, je vous recommande de résoudre la deuxième expression (dans mon commentaire).
2
Une autre remarque, lors de la recherche de la β minimisant (YXβ)(YXβ)+γj|βj|, divisez le problème dans les cas \ beta_j> 0βj>0 , βj<0 et β=0 .
2
@ cardinal Ah oui, 1-1 est incorrect. Correction: pour chaque t0 , vous pouvez trouver un γ0 .
3
Merci pour une bonne discussion! Je suis tombé sur cette vidéo sur coursera - Dériver de la mise à jour de la descente de coordonnées au lasso , qui est très pertinente pour cette discussion, et présente la solution de manière très élégante.
Cela

Réponses:

64

Cela peut être attaqué de différentes manières, y compris par des approches relativement économiques via les conditions de Karush – Kuhn – Tucker .

Ci-dessous, un argument alternatif assez élémentaire.

La solution des moindres carrés pour un dessin orthogonal

Supposons que soit composé de colonnes orthogonales. La solution des moindres carrés est alors X

β^LS=(XTX)1XTy=XTy.

Quelques problèmes équivalents

Via la forme lagrangienne, il est évident qu'un problème équivalent à celui considéré dans la question est

minβ12yXβ22+γβ1.

En élargissant le premier terme, on obtient et depuis ne contient pas des variables d’intérêt, nous pouvons l’écarter et envisager un autre problème équivalent, 12yTyyTXβ+12βTβyTy

minβ(yTXβ+12β2)+γβ1.

En notant que , le problème précédent peut être réécrit sous la forme β^LS=XTy

minβi=1pβ^iLSβi+12βi2+γ|βi|.

Notre fonction d'objectif est maintenant une somme d'objectifs, chacun correspondant à une variable distincte , afin qu'ils puissent être résolus individuellement.βi

Le tout est égal à la somme de ses parties

Fixer un certain . Ensuite, nous voulons minimiser i

Li=β^iLSβi+12βi2+γ|βi|.

Si , alors nous devons avoir sinon nous pourrions retourner son signe et obtenir une valeur inférieure pour la fonction objectif. De même si , alors nous devons choisir .β^iLS>0βi0β^iLS<0βi0

Cas 1 : . Depuis , différenciant par rapport à et en le fixant à zéro , nous obtenons et ceci n’est réalisable que si le droite n’est pas négatif, donc dans ce cas la solution actuelle est β^iLS>0βi0

Li=β^iLSβi+12βi2+γβi,
βiβi=β^iLSγ
β^ilasso=(β^iLSγ)+=sgn(β^iLS)(|β^iLS|γ)+.

Cas 2 : . Cela implique que nous devons avoir et donc En différenciant par rapport à et en fixant la valeur à zéro, nous obtenons . Mais, encore une fois, pour que cela soit réalisable, nous avons besoin de , qui est obtenu en prenant β^iLS0βi0

Li=β^iLSβi+12βi2γβi.
βiβi=β^iLS+γ=sgn(β^iLS)(|β^iLS|γ)βi0
β^ilasso=sgn(β^iLS)(|β^iLS|γ)+.

Dans les deux cas, nous obtenons le formulaire souhaité et nous avons donc terminé.

Remarques finales

Notez que lorsque augmente, alors chacun desdécroît nécessairement, donc aussi . Lorsque , nous récupérons les solutions OLS et, pour, on obtient pour tout .γ|β^ilasso|β^lasso1γ=0γ>maxi|β^iLS|β^ilasso=0i

cardinal
la source
2
Grande écriture @ cardinal!
Gary
9
+1 Toute la seconde moitié peut être remplacée par la simple observation que la fonction objectif est une union de parties de deux paraboles convexes avec des sommets à , où le signe négatif est pris pour et le positif sinon. La formule est juste une manière élégante de choisir le sommet inférieur. β12β2+(±γβ^)β±γβ^β<0
whuber
Si possible, j'aimerais voir les dérivations en utilisant les conditions d'optimalité KKT. Quels sont les autres moyens d'obtenir ce résultat?
user1137731
5
@ Cardinal: merci pour cette belle dérivation. Une observation. Si je me souviens bien, une matrice à colonnes orthogonales n’est pas identique à une matrice orthogonale (ou orthonormée). Alors pour une matrice diagonale (pas nécessairement une matrice d'identité). Avec l'hypothèse de matrice orthogonale (comme dans la question initiale), nous avons et tout est superbe :)XX=DDXX=I
Oleg Melnikov
@ cardinal Je ne comprends pas pourquoi vous dites "sinon nous pourrions retourner son signe et obtenir une valeur inférieure pour la fonction objectif". Nous prenons la dérivée de la fonction objectif. Alors que se passe-t-il si la fonction objectif est supérieure ou inférieure, qui s'en soucie. Tout ce qui nous importe, c’est que le dérivé est réglé à zéro, nous nous soucions des extrema. Qu'il soit supérieur ou inférieur d'une constante n'affecte pas l'argmin.
utilisateur13985
7

On suppose que la covariables , les colonnes de , sont également normalisées de sorte que . C’est pour plus de commodité par la suite: sans cela, la notation n’est que plus lourde puisque n’est que diagonale. Supposons en outre que . Ceci est une hypothèse nécessaire pour que le résultat soit valide. Définissez l’estimateur des moindres carrés . Ensuite, la forme (lagrangienne) de l’estimateur de lasso xjXRn×pXTX=IXTXnpβ^OLS=argminβyXβ22

(defn.)β^λ=argminβ12nyXβ22+λβ1(OLS is projection)=argminβ12nXβ^OLSXβ22+λβ1(XTX=I)=argminβ12nβ^OLSβ22+λβ1(algebra)=argminβ12β^OLSβ22+nλβ1(defn.)=proxnλ1(β^OLS)(takes some work)=Snλ(β^OLS),
\ end {align *} où est l'opérateur proximal d'une fonction et seuils variables de la quantitéproxffSαα.

C’est une dérivation qui ignore la dérivation détaillée de l’opérateur proximal élaborée par Cardinal, mais, j’espère, clarifie les principales étapes permettant de créer une forme fermée.

utilisateur795305
la source