Pourquoi ma dérivation d'une solution de lasso de forme fermée est-elle incorrecte?

28

Le problème du lasso a la solution de forme fermée: \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS }} | - \ alpha) ^ + si X a des colonnes orthonormées. Cela a été montré dans ce fil: Dérivation de la solution de lasso de forme fermée .

βlasso=argminβyXβ22+αβ1
βjlasso=sgn(βjLS)(|βjLS|α)+
X

Cependant, je ne comprends pas pourquoi il n'y a pas de solution sous forme fermée en général. En utilisant des sous-différentiels, j'ai obtenu ce qui suit.

( X est une matrice n×p )

f(β)=yXβ22+αβ1
=i=1n(yiXiβ)2+αj=1p|βj|
( Xi est la i-ème ligne de X )
=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|
fβj=2i=1nyiXij+2i=1nXij2βj+βj(α|βj|)
={2i=1nyiXij+2i=1nXij2βj+α for βj>02i=1nyiXij+2i=1nXij2βjα for βj<0[2i=1nyiXijα,2i=1nyiXij+α] for βj=0
Avec fβj=0 nous obtenons

βj={(2(i=1nyiXij)α)/2i=1nXij2for i=1nyiXij>α(2(i=1nyiXij)+α)/2i=1nXij2for i=1nyiXij<α0 for i=1nyiXij[α,α]

Est-ce que quelqu'un voit où je me suis trompé?

Répondre:

Si nous écrivons le problème en termes de matrices, nous pouvons voir très facilement pourquoi une solution de forme fermée n'existe que dans le cas orthonormé avec XTX=I :

f(β)=yXβ22+αβ1
=yTy2βTXTy+βTXTXβ+αβ1
f(β)=2XTy+2XTXβ+(α|β1)
(J'ai pris plusieurs mesures à la fois ici. Cependant, jusqu'à présent, ceci est complètement analogue à la dérivation de la solution des moindres carrés. Vous devriez donc pouvoir y trouver les étapes manquantes.)
fβj=2XjTy+2(XTX)jβ+βj(α|βj|)

Avec fβj=0 nous obtenons

2(XTX)jβ=2XjTyβj(α|βj|)
2(XTX)jjβj=2XjTyβj(α|βj|)2i=1,ijp(XTX)jiβi

Nous pouvons voir maintenant que notre solution pour l'un dépend de tous les autres donc il n'est pas clair comment procéder à partir d'ici. Si est orthonormé, nous avons donc il existe certainement une solution de forme fermée dans ce cas.βjβijX2(XTX)jβ=2(I)jβ=2βj

Merci à Guðmundur Einarsson pour sa réponse, sur laquelle j'ai développé ici. J'espère que cette fois c'est correct :-)

Norbert
la source
3
Bienvenue sur CrossValidated, et félicitations pour un très joli premier post!
S.Kolassa - Reinstate Monica

Réponses:

16

Cela se fait normalement avec le moins de régression angulaire, vous pouvez trouver l' article ici .

Désolé de ma confusion au début, je vais essayer à nouveau.

Donc, après l'extension de votre fonction vous obtenezf(β)

f(β)=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|

Ensuite, vous calculez la dérivée partielle par rapport à . Ma préoccupation est dans votre calcul de la dérivée partielle du dernier terme avant la norme 1, c'est-à-dire le terme quadratique. Examinons-le plus en détail. Nous avons cela:βj

Xiβ=βTXiT=(β1Xi1+β2Xi2++βpXip)
Vous pouvez donc essentiellement réécrire votre terme quadratique comme: Nous pouvons maintenant utiliser la règle de chaîne pour calculer la dérivée de ce wrt :
i=1nβTXiTXiβ=i=1n(Xiβ)2
βj
βji=1n(Xiβ)2=i=1nβj(Xiβ)2=i=1n2(Xiβ)Xij

Alors maintenant, votre problème ne se simplifie pas aussi facilement, car vous avez tous les coefficients présents dans chaque équation.β

Cela ne répond pas à votre question de savoir pourquoi il n'y a pas de solution de forme fermée du Lasso, je pourrais ajouter quelque chose plus tard.

Gumeo
la source
1
Merci beaucoup. En fait, je peux voir maintenant pourquoi il n'y a pas de solution de formulaire fermé (voir ma modification).
Norbert
Doux! Excellent travail :)
Gumeo