Derivación de solución de lazo de forma cerrada

Para el problema del lazo $\min_\beta (Y-X\beta)^T(Y-X\beta)$ tal que $\|\beta\|_1 \leq t$ . A menudo veo el resultado de umbral 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 el caso

ortonormal

X

$X$ . Se afirma que la solución puede "mostrarse fácilmente" como tal, pero nunca he visto una solución que funcione. ¿Alguien ha visto uno o tal vez ha hecho la derivación?

lasso Gary
fuente

Esto parece un poco confundido. Al principio, asume una restricción

t

$t$ y en la solución introduce un parámetro

γ

$\gamma$ . Supongo que tiene la intención de que estos dos estén relacionados a través del problema dual, pero tal vez pueda aclarar lo que está buscando.

cardenal

Respondiendo parcialmente a @cardinal, encontrar la

β

$\beta$ que minimiza

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

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

‖ β ‖_{1} \leq t

$\|\beta\|_1 \leq t$ es equivalente a encontrar la

β

$\beta$ que minimiza

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

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ . Hay una relación 1-1 entre

t

$t$ y

γ

$\gamma$ . Para ver "fácilmente" por qué el resultado del umbral suave es así, recomendaría resolver la segunda expresión (en mi comentario).

Otra nota, al encontrar el

β

$\beta$ que minimiza

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

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ ,

el problema en los casos

β_{j} > 0

$\beta_j >0$ ,

β_{j} < 0

$\beta_j<0$ y

β = 0

$\beta=0$ .

@cardinal Ah sí, 1-1 es incorrecto. Corrección: para cada

t \geq 0

$t\geq0$ , puede encontrar un

γ \geq 0

$\gamma\geq 0$ .

Gracias por una gran discusión! Encontré este video en el curso: derivando la actualización de descenso de coordenadas del lazo , que es muy relevante para esta discusión, y analiza la solución con mucha elegancia. Puede ser útil para futuros visitantes :-)

zorbar

Respuestas:

Esto puede ser atacado de varias maneras, incluyendo enfoques bastante económicos a través de las condiciones de Karush-Kuhn-Tucker .

A continuación hay un argumento alternativo bastante elemental.

La solución de mínimos cuadrados para un diseño ortogonal

Supongamos que se compone de columnas ortogonales. Entonces, la solución de mínimos cuadrados es $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 \>.$

Algunos problemas equivalentes

A través de la forma lagrangiana, es sencillo ver que un problema equivalente al considerado en la pregunta es

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

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

Expandiendo el primer término obtenemos y dado que no contiene ninguno de las variables de interés, podemos descartarlo y considerar otro 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 \>.$

Teniendo en cuenta que , el problema anterior se puede volver a escribir 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| \> .$

Nuestra función objetivo es ahora una suma de objetivos, cada uno correspondiente a una variable separada , por lo que cada uno puede resolverse individualmente. $\beta_i$

El todo es igual a la suma de sus partes.

Arreglar un cierto . Entonces, 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| \> .$

Si , entonces debemos tener ya que de lo contrario podríamos voltear su signo y obtener un valor más bajo para la función objetivo. Del mismo modo, si , entonces debemos elegir . $\bls_i > 0$ $\beta_i \geq 0$ $\bls_i < 0$ $\beta_i \leq 0$

Caso 1 : . Desde , y diferenciando esto con respecto a y estableciendo un valor igual a cero , obtenemos y esto solo es factible si el lado derecho no es negativo, por lo que en este caso la solución real es $\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 : . Esto implica que debemos tener y entonces Al diferenciar con respecto a y establecer un valor igual a cero, obtenemos . Pero, una vez más, para garantizar que esto sea factible, necesitamos , que se logra tomando $\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)^+ \>.$

En ambos casos, obtenemos la forma deseada, y así terminamos.

Observaciones finales

cardenal
fuente

Gran crítica @cardinal!

Gary

+1 La segunda mitad completa se puede reemplazar por la simple observación de que la función objetivo es Una unión de partes de dos parábolas convexas con vértices en , donde el signo negativo se toma para y el positivo en caso contrario. La fórmula es solo una forma elegante de elegir el 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

Si es posible, me gustaría ver las derivaciones utilizando las condiciones de optimización de KKT. ¿Qué otras formas hay para derivar este resultado?

user1137731

@ Cardenal: gracias por una buena derivación. Una observación Si recuerdo, la matriz con columnas ortogonales no es lo mismo que una matriz ortogonal (también conocida como ortonormal). Entonces para alguna matriz diagonal (no necesariamente matriz de identidad). Con el supuesto de la matriz ortogonal (como está en la pregunta original), tenemos y todo se ve muy bien :)

X^{'} X = D

$X'X=D$

D

$D$

X^{'} X = I

$X'X=I$

Oleg Melnikov

@cardinal No entiendo por qué dices "ya que de lo contrario podríamos voltear su signo y obtener un valor más bajo para la función objetivo". Estamos tomando la derivada de la función objetivo. Entonces, ¿qué pasa si la función objetivo es mayor o menor, a quién le importa? Todo lo que nos importa es que la derivada se establezca en cero, nos preocupamos por los extremos. Si es más alto o más bajo por una constante, no afecta al argmin.

user13985

Suponemos que el covariables , las columnas de , también están estandarizados para que . Esto es solo por conveniencia más adelante: sin él, la notación se vuelve más pesada ya que es solo diagonal. Además suponga que . Esta es una suposición necesaria para que el resultado se mantenga. Defina el estimador de mínimos cuadrados . Luego, el estimador de lazo (forma lagrangiana del) $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 *} donde es el operador proximal de una función y umbrales suaves por la cantidad

{p r o x}_{f}

$\mathrm{prox}_f$

f

$f$

S_{α}

$S_{\alpha}$

α

$\alpha$ .

Esta es una derivación que omite la derivación detallada del operador proximal que Cardinal calcula, pero, espero, aclara los pasos principales que hacen posible una forma cerrada.

usuario795305
fuente