Derivação da solução de laço de forma fechada

52

Para o problema do laço minβ(YXβ)T(YXβ) tal que β1t . Muitas vezes, vejo o resultado do limiar suave

βjlasso=sgn(βjLS)(|βjLS|γ)+
para o caso X ortonormal X. Alega-se que a solução pode ser "facilmente mostrada", mas nunca vi uma solução funcionada. Alguém viu um ou talvez tenha feito a derivação?
Gary
fonte
Isso parece um pouco confuso. No início, você assume uma restrição t na solução, introduz um parâmetro γ . Suponho que você pretende que esses dois sejam relacionados pelo problema duplo, mas talvez você possa deixar claro o que está procurando.
cardeal
2
Respondendo parcialmente a @cardinal, encontrar o β que minimiza (YXβ)(YXβ) sujeito a β1t é equivalente a encontrar o β que minimiza (YXβ)(YXβ)+γj|βj|. Existe uma relação de 01/01 entre t e γ . Para 'facilmente' ver por que é o resultado do limiar suave, recomendo resolver a segunda expressão (no meu comentário).
2
Outra observação, ao encontrar o β que minimiza (YXβ)(YXβ)+γj|βj|, divida o problema nos casos βj>0 , βj<0 e β=0 .
2
@ cardinal Ah sim, 1-1 está incorreto. Correção: para cada t0 , você pode encontrar um γ0 .
3
Obrigado por uma ótima discussão! Me deparei com este vídeo no coursera - Derivando a atualização de descida das coordenadas do laço , que é muito relevante para esta discussão, e percorre a solução com muita elegância. Pode ser útil para os futuros visitantes :-)
zorbar

Respostas:

64

Isso pode ser atacado de várias maneiras, incluindo abordagens bastante econômicas através das condições de Karush – Kuhn – Tucker .

Abaixo está um argumento alternativo bastante elementar.

A solução de mínimos quadrados para um desenho ortogonal

Suponha que seja composto de colunas ortogonais. Então, a solução dos mínimos quadrados é X

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

Alguns problemas equivalentes

Através da forma lagrangiana, é fácil ver que um problema equivalente ao considerado na questão é

minβ12yXβ22+γβ1.

Expandindo o primeiro termo, obtemos e, como não contém nenhum das variáveis ​​de interesse, podemos descartá-lo e considerar outro problema equivalente, 12yTyyTXβ+12βTβyTy

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

Observando que , o problema anterior pode ser reescrito como β^LS=XTy

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

Nossa função objetivo é agora uma soma de objetivos, cada um correspondente a uma variável separada , para que cada um possa ser resolvido individualmente.βi

O todo é igual à soma de suas partes

Corrija um certo . Então, queremos minimizar i

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

Se , então devemos ter pois caso contrário poderíamos inverter o sinal e obter um valor mais baixo para a função objetivo. Da mesma forma, se , devemos escolher .β^iLS>0βi0β^iLS<0βi0

Caso 1 : . Desde , diferenciando-o em relação a e definindo igual a zero , obtemos e isso só é possível se o lado direito não for negativo, portanto, nesse caso, a solução real é β^iLS>0βi0

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

Caso 2 : . Isso implica que devemos ter e, portanto, Diferenciando em relação a e definindo igual a zero, obtemos . Mas, novamente, para garantir que isso seja possível, precisamos de , o que é obtido usando β^iLS0βi0

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

Nos dois casos, obtemos a forma desejada e, assim, terminamos.

Considerações finais

Observe que, à medida que aumenta, cada um dosnecessariamente diminui e, portanto, . Quando , recuperamos as soluções OLS e, para, obtemos para todos os .γ|β^ilasso|β^lasso1γ=0γ>maxi|β^iLS|β^ilasso=0i

cardeal
fonte
2
Grande writeup @cardinal!
Gary
9
+1 A segunda metade inteira pode ser substituída pela simples observação de que a função objetivo é uma união de partes de duas parábolas convexas com vértices em , onde o sinal negativo é obtido para e o positivo em contrário. A fórmula é apenas uma maneira elegante de escolher o vértice inferior. β12β2+(±γβ^)β±γβ^β<0
whuber
Se possível, gostaria de ver as derivações usando as condições de otimização KKT. Que outras maneiras existem para obter esse resultado?
user1137731
5
@ Cardinal: obrigado por uma boa derivação. Uma observação Se bem me lembro, a matriz com colunas ortogonais não é a mesma que uma matriz ortogonal (também conhecida como ortogonal). Então para alguma matriz diagonal (não necessariamente matriz de identidade). Com suposição matriz ortogonal (como está na pergunta original), nós temos e todos os olhares grandes :)XX=DDXX=I
Oleg Melnikov
@ cardinal Não entendo por que você diz ", pois caso contrário, poderíamos virar o sinal e obter um valor menor para a função objetivo". Estamos tomando a derivada da função objetivo. E daí que a função objetivo é maior ou menor, quem se importa. Tudo o que nos importa é que a derivada esteja definida como zero, nos preocupamos com os extremos. Se é mais alto ou mais baixo por uma constante, não afeta o argmin.
precisa saber é o seguinte
7

Assume-se que a co-variáveis , as colunas de , são também uniformizadas, de modo que . Isso é apenas para conveniência mais tarde: sem ela, a notação fica mais pesada, pois é apenas diagonal. Além disso, assuma que . Essa é uma suposição necessária para que o resultado seja mantido. Defina o estimador de mínimos quadrados . Então, o (forma Lagrangiana do) estimador de laço 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 *} onde é o operador proximal de uma função e os limites flexíveis pela quantidadeproxffSαα.

Essa é uma derivação que ignora a derivação detalhada do operador proximal que o Cardinal realiza, mas, espero, esclarece os principais passos que tornam possível um formulário fechado.

user795305
fonte