El lasso problema $\min_\beta (Y-X\beta)^T(Y-X\beta)$ tal que $\|\beta\|_1 \leq t$. A menudo veo el umbral suave resultado $$ \beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+ $ $ para el caso de orthonormal $X$. Se afirma que la solución puede ser "fácilmente se muestra" para ser tal, pero nunca he visto una solución trabajada. ¿Alguien ha visto uno o tal vez ha hecho la derivación?
Respuesta
¿Demasiados anuncios?
giulio
Puntos
166
Esto puede ser atacado en un número de maneras, incluyendo bastante económico enfoques a través de la Karush–Kuhn–Tucker condiciones.
A continuación es bastante elemental argumento alternativo.
La solución de mínimos cuadrados para un diseño ortogonal
Supongamos $X$ se compone de columnas ortogonales. A continuación, el de mínimos cuadrados es la solución $$ \newcommand{\bls}{\hat{\beta}^{{\small \text{LS}}}}\newcommand{\blasso}{\hat{\beta}^{{\text{lazo}}}} \bls = (X^T X)^{-1} X^T y = X^T y \>. $$
Algunos problemas equivalentes
A través de la forma de Lagrange, es sencillo ver que un problema equivalente al considerado en la pregunta es $$ \min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_1 \>. $$
La expansión de la primer término obtenemos $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ y desde $y^T y$ no contiene ninguna de las variables de interés, podemos descartarlo y considerar otro problema equivalente, $$ \min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>. $$
Tomando nota de que $\bls = X^T y$, el anterior problema puede escribirse como $$ \min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma\beta_i| \> . $$
Nuestra función objetivo ahora es una suma de objetivos, cada uno correspondiente a una variable separada $\beta_i$, por lo que cada uno puede ser solucionado de forma individual.
El todo es igual a la suma de sus partes
Fijar un determinado $i$. A continuación, queremos minimizar $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma\beta_i| \> . $$
Si $\bls_i > 0$, entonces tenemos que tener en $\beta_i \geq 0$ ya que de lo contrario podríamos voltear su signo y consigue un menor valor de la función objetivo. Del mismo modo, si $\bls_i < 0$, entonces debemos optar $\beta_i \leq 0$.
Caso 1: $\bls_i > 0$. Desde $\beta_i \geq 0$, $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> , $$ y de diferenciación de este con respecto a $\beta_i$ y ajuste igual a cero, obtenemos $\beta_i = \bls_i - \gamma$ y esto sólo es posible si el lado derecho es no negativo, por lo que en este caso la solución real es $$ \blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>. $$
Caso 2: $\bls_i \leq 0$. Esto implica que debemos tener $\beta_i \leq 0$, por lo que $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> . $$ Diferenciando con respecto a $\beta_i$ y ajuste igual a cero, obtenemos $\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$. Pero, de nuevo, para asegurarse de que esto es factible, necesitamos $\beta_i \leq 0$, lo cual se logra mediante la adopción de $$ \blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>. $$
En ambos casos, se obtiene la forma deseada, y así hemos terminado.
Comentarios finales
Tenga en cuenta que como $\gamma$ aumenta, entonces cada una de las $|\blasso_i|$ necesariamente disminuye, por lo tanto lo hace $\|\blasso\|_1$. Al $\gamma = 0$, recuperamos el OLS soluciones, y, por $\gamma > \max_i |\bls_i|$, obtenemos $\blasso_i = 0$ todos los $i$.
