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

Para o problema do laço $\min_\beta (Y-X\beta)^T(Y-X\beta)$ tal que $\|\beta\|_1 \leq t$ . Muitas vezes, vejo o resultado do limiar suave

β_{j}^{lasso} = s g n (β_{j}^{LS}) (| β_{j}^{LS} | - γ)^{+}

$\beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+$ para o caso

ortonormal

X

$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?

lasso Gary
fonte

Isso parece um pouco confuso. No início, você assume uma restrição

t

$t$ na solução, introduz um parâmetro

γ

$\gamma$ . Suponho que você pretende que esses dois sejam relacionados pelo problema duplo, mas talvez você possa deixar claro o que está procurando.

cardeal

Respondendo parcialmente a @cardinal, encontrar o

β

$\beta$ que minimiza

(Y - X β)^{'} (Y - X β)

$(Y-X\beta )'(Y-X\beta )$ sujeito a

‖ β ‖_{1} \leq t

$\|\beta\|_1 \leq t$ é equivalente a encontrar o

β

$\beta$ que minimiza

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ . Existe uma relação de 01/01 entre

t

$t$ e

γ

$\gamma$ . Para 'facilmente' ver por que é o resultado do limiar suave, recomendo resolver a segunda expressão (no meu comentário).

Outra observação, ao encontrar o

β

$\beta$ que minimiza

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ , divida o problema nos casos

β_{j} > 0

$\beta_j >0$ ,

β_{j} < 0

$\beta_j<0$ e

β = 0

$\beta=0$ .

@ cardinal Ah sim, 1-1 está incorreto. Correção: para cada

t \geq 0

$t\geq0$ , você pode encontrar um

γ \geq 0

$\gamma\geq 0$ .

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:

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$

{\hat{β}}^{LS} = (X^{T} X)^{- 1} X^{T} y = X^{T} y .

$\newcommand{\bls}{\hat{\beta}^{{\small \text{LS}}}}\newcommand{\blasso}{\hat{\beta}^{{\text{lasso}}}} \bls = (X^T X)^{-1} X^T y = X^T y \>.$

Alguns problemas equivalentes

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

min_{β} \frac{1}{2} ‖ y - X β ‖_{2}^{2} + γ ‖ β ‖_{1} .

$\min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_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, $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ $y^T y$

min_{β} (- y^{T} X β + \frac{1}{2} ‖ β ‖^{2}) + γ ‖ β ‖_{1} .

$\min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>.$

Observando que , o problema anterior pode ser reescrito como $\bls = X^T y$

min_{β} \sum_{i = 1}^{p} - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma |\beta_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. $\beta_i$

O todo é igual à soma de suas partes

Corrija um certo . Então, queremos minimizar $i$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma |\beta_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 . $\bls_i > 0$ $\beta_i \geq 0$ $\bls_i < 0$ $\beta_i \leq 0$

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 é $\bls_i > 0$ $\beta_i \geq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ β_{i},

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> ,$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} - γ

$\beta_i = \bls_i - \gamma$

{\hat{β}}_{i}^{lasso} = ({\hat{β}}_{i}^{LS} - γ)^{+} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

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 $\bls_i \leq 0$ $\beta_i \leq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} - γ β_{i} .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> .$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} + γ = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)

$\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$

β_{i} \leq 0

$\beta_i \leq 0$

{\hat{β}}_{i}^{lasso} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

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

Considerações finais

cardeal
fonte

Grande writeup @cardinal!

Gary

+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.

β \to \frac{1}{2} β^{2} + (\pm γ - \hat{β}) β

$\beta\to\frac{1}{2}\beta^2+(\pm\gamma-\hat{\beta})\beta$

\pm γ - \hat{β}

$\pm\gamma-\hat{\beta}$

β < 0

$\beta\lt 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

@ 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 :)

X^{'} X = D

$X'X=D$

D

$D$

X^{'} X = I

$X'X=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

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 $x_j$ $X \in \mathbb{R}^{n \times p}$ $X^T X = I$ $X^T X$ $n \geq p$ $\hat\beta_{OLS} = \arg\min_\beta \|y - X \beta\|_2^2$

\begin{aligned} (defn.) & {\hat{β}}_{λ} & = \arg min_{β} \frac{1}{2 n} ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (OLS is projection) & = \arg min_{β} \frac{1}{2 n} ‖ X {\hat{β}}_{O L S} - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (X^{T} X = I) & = \arg min_{β} \frac{1}{2 n} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (algebra) & = \arg min_{β} \frac{1}{2} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + n λ ‖ β ‖_{1} \\ (defn.) & = {p r o x}_{n λ ‖ \cdot ‖_{1}} ({\hat{β}}_{O L S}) \\ (takes some work) & = S_{n λ} ({\hat{β}}_{O L S}), \end{aligned}

$\begin{align*} \hat\beta_\lambda & = \arg\min_{\beta} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{defn.} \\ & = \arg\min_\beta \frac{1}{2n} \|X \hat\beta_{OLS} - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{OLS is projection} \\ & = \arg\min_\beta \frac{1}{2n} \|\hat\beta_{OLS} - \beta\|_2^2 + \lambda \|\beta\|_1 \tag{$X^TX=I$} \\ & = \arg\min_\beta \frac{1}{2} \|\hat\beta_{OLS} - \beta\|_2^2 + n \lambda \|\beta\|_1 \tag{algebra} \\ & = \mathrm{prox}_{n \lambda \|\cdot\|_1} \left( \hat\beta_{OLS} \right) \tag{defn.} \\ & = S_{n \lambda} \left( \hat\beta_{OLS} \right) \tag{takes some work}, \end{align*}$ \ end {align *} onde é o operador proximal de uma função e os limites flexíveis pela quantidade

{p r o x}_{f}

$\mathrm{prox}_f$

f

$f$

S_{α}

$S_{\alpha}$

α

$\alpha$ .

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