Por que minha derivação de uma solução de laço de forma fechada está incorreta?

28

O problema do laço possui a solução de formulário fechado: \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _j) (| \ beta_j ^ {\ text {LS }} | - \ alpha) ^ + se X tiver colunas ortonormais. Isso foi mostrado neste tópico: Derivação da solução de laço de forma fechada .

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

No entanto, eu não entendo por que não existe uma solução de formulário fechado em geral. Usando subdiferenciais, obtive o seguinte.

( X é uma matriz n×p )

f(β)=yXβ22+αβ1
=i=1n(yiXiβ)2+αj=1p|βj|
( Xi é a i-ésima linha 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
Com fβj=0 obtemos

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

Alguém vê onde eu errei?

Responda:

Se escrevermos o problema em termos de matrizes, podemos ver com muita facilidade por que uma solução de forma fechada só existe no caso ortonormal com XTX=I :

f(β)=yXβ22+αβ1
=yTy2βTXTy+βTXTXβ+αβ1
f(β)=2XTy+2XTXβ+(α|β1)
(Eu tomei várias etapas ao mesmo tempo aqui. No entanto, até esse ponto, isso é completamente análogo à derivação da solução dos mínimos quadrados. Portanto, você deve encontrar as etapas ausentes lá.)
fβj=2XjTy+2(XTX)jβ+βj(α|βj|)

Com fβj=0 obtemos

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

Agora podemos ver que nossa solução para um depende de todos os outros portanto não está claro como proceder a partir daqui. Se é ortonormal, temos portanto, certamente existe uma solução em forma fechada nesse caso.βjβijX2(XTX)jβ=2(I)jβ=2βj

Agradeço a Guðmundur Einarsson por sua resposta, sobre a qual elaborei aqui. Espero que desta vez esteja correto :-)

Norbert
fonte
3
Bem-vindo ao CrossValidated, e parabéns por um muito primeiro post bom!
S. Kolassa - Restabelece Monica

Respostas:

16

Isso normalmente é feito com regressão de menor ângulo, você pode encontrar o artigo aqui .

Desculpe pela minha confusão no começo, vou tentar outra vez.

Então, após a expansão de sua função você obtémf(β)

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

Então você calcula a derivada parcial em relação a . Minha preocupação está no seu cálculo da derivada parcial do último termo antes da norma 1, ou seja, o termo quadrático. Vamos examiná-lo mais. Nós temos que:βj

Xiβ=βTXiT=(β1Xi1+β2Xi2++βpXip)
Portanto, você pode essencialmente reescrever seu termo quadrático como: Agora podemos usar a regra da cadeia para calcular a derivada deste wrt :
i=1nβTXiTXiβ=i=1n(Xiβ)2
βj
βji=1n(Xiβ)2=i=1nβj(Xiβ)2=i=1n2(Xiβ)Xij

Portanto, agora seu problema não se simplifica tão facilmente, porque você tem todos os coeficientes presentes em cada equação.β

Isso não responde à sua pergunta de por que não existe uma solução de forma fechada do Lasso, devo acrescentar algo mais tarde.

Gumeo
fonte
1
Muito obrigado. Na verdade, agora posso ver por que não há uma solução de formulário fechado (veja minha edição).
Norbert
Doce!
Bom