La prueba de fórmulas equivalentes de regresión de crestas

15

He leído los libros más populares sobre aprendizaje estadístico.

1- Los elementos del aprendizaje estadístico.

2- Una introducción al aprendizaje estadístico .

Ambos mencionan que la regresión de crestas tiene dos fórmulas que son equivalentes. ¿Existe una prueba matemática comprensible de este resultado?

También pasé por Cross Validated , pero no puedo encontrar una prueba definitiva allí.

Además, ¿LASSO disfrutará del mismo tipo de prueba?

regression lasso regularization ridge-regression lagrange-multipliers jeza
fuente

2

en.wikipedia.org/wiki/…

Taylor

1

El lazo no es una forma de regresión de cresta.

Xi'an

@jeza, ¿podrías explicar lo que falta en mi respuesta? Realmente deriva todo lo que se puede derivar sobre la conexión.

Royi

@jeza, ¿podrías ser específico? A menos que conozca el concepto lagrangiano para problemas restringidos, es difícil dar una respuesta concisa.

Royi

1

@jeza, un problema de optimización restringido puede convertirse en optimización de la función lagrangiana / condiciones KKT (como se explica en las respuestas actuales). Este principio ya tiene muchas explicaciones simples diferentes en todo Internet. ¿En qué dirección es necesaria una mayor explicación de la prueba? ¿Explicación / prueba del multiplicador / función lagrangiana, explicación / prueba de cómo este problema es un caso de optimización relacionado con el método de Lagrange, la diferencia KKT / Lagrange, explicación del principio de regularización, etc.?

Sextus Empiricus

19

La clásica Regresión de cresta ( regularización de Tikhonov ) viene dada por:

\arg min_{x} \frac{1}{2} {‖ x - y ‖}_{2}^{2} + λ {‖ x ‖}_{2}^{2}

$\arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2}$

La afirmación anterior es que el siguiente problema es equivalente:

\begin{aligned} \arg min_{X} & \frac{1}{2} {‖ X - y ‖}_{2}^{2} \\ sujeto a & {‖ X ‖}_{2}^{2} \leq t \end{aligned}

$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$

Vamos a definir como la solución óptima del problema y la primera como la solución óptima del segundo problema. $\hat{x}$ $\tilde{x}$

El reclamo de equivalencia significa que $\forall t, \: \exists \lambda \geq 0 : \hat{x} = \tilde{x}$ .
Es decir, siempre se puede tener un par de $t$ y $\lambda \geq 0$ como la solución del problema es el mismo.

¿Cómo podemos encontrar un par?
Bueno, resolviendo los problemas y observando las propiedades de la solución.
Ambos problemas son convexos y suaves, por lo que debería simplificar las cosas.

La solución para el primer problema se da en el punto en que el gradiente desaparece, lo que significa:

\hat{x} - y + 2 λ \hat{x} = 0

$\hat{x} - y + 2 \lambda \hat{x} = 0$

Las condiciones de KKT del segundo problema establecen:

\tilde{x} - y + 2 μ \tilde{x} = 0

$\tilde{x} - y + 2 \mu \tilde{x} = 0$

y

μ ({‖ \tilde{x} ‖}_{2}^{2} - t) = 0

$\mu \left( {\left\| \tilde{x} \right\|}_{2}^{2} - t \right) = 0$

La última ecuación sugiere que $\mu = 0$ o ${\left\| \tilde{x} \right\|}_{2}^{2} = t$ .

Presta atención a que las 2 ecuaciones básicas son equivalentes.
Es decir, si y sostienen ambas ecuaciones. $\hat{x} = \tilde{x}$ $\mu = \lambda$

Por lo tanto, significa que en el caso de ${\left\| y \right\|}_{2}^{2} \leq t$ uno debe establecer $\mu = 0$ que significa que para $t$ suficientemente grande para que ambos sean equivalentes, uno debe establecer $\lambda = 0$ .

En el otro caso, uno debe encontrar $\mu$ donde:

y^{t} {(I + 2 μ I)}^{- 1} {(I + 2 μ I)}^{- 1} y = t

${y}^{t} \left( I + 2 \mu I \right)^{-1} \left( I + 2 \mu I \right)^{-1} y = t$

Esto es básicamente cuando ${\left\| \tilde{x} \right\|}_{2}^{2} = t$

Una vez que encuentre que $\mu$ las soluciones colisionarán.

Con respecto al caso ${L}_{1}$ (LASSO), bueno, funciona con la misma idea.
La única diferencia es que no tenemos solución cerrada, por lo tanto, derivar la conexión es más complicado.

Eche un vistazo a mi respuesta en StackExchange Cross Validated Q291962 y StackExchange Signal Processing Q21730 - Importancia de $\lambda$ en la búsqueda de bases .

Observación
¿Qué está pasando realmente?
En ambos problemas, $x$ intenta estar lo más cerca posible de $y$ .
En el primer caso, $x = y$ desaparecerá el primer término (The ${L}_{2}$ distancia ) y en el segundo caso hará que la función objetivo desaparezca.
La diferencia es que en el primer caso uno debe equilibrar la Norma ${L}_{2}$ de $x$ . A medida que $\lambda$ aumenta, el equilibrio significa que debe hacer $x$ más pequeño.
En el segundo caso hay una pared, acercas $x$ cada vez más a $y$ hasta que golpeas la pared, que es la restricción en su Norma (Por $t$ ).
Si la pared está lo suficientemente lejos (alto valor de $t$ ) y suficiente depende de la norma de $y$ entonces no tiene significado, al igual que $\lambda$ es relevante solo porque su valor multiplicado por la norma de $y$ comienza a ser significativo.
La conexión exacta es por el lagrangiano mencionado anteriormente.

Recursos

Encontré este documento hoy (03/04/2019):

Dureza de aproximación para una clase de problemas de optimización dispersos .

Royi
fuente

¿el equivalente significa que \ lambda y \ t deberían ser iguales? Porque no puedo ver eso en la prueba. gracias

jeza

@jeza, como escribí anteriormente, para cualquier

hay

t

$t$

λ \geq 0

$\lambda \geq 0$ (no necesariamente igual a

pero una función de

y los datos

) de modo que las soluciones de las dos formas son las mismas.

t

$t$

t

$t$

y

$y$

Royi

3

@jeza, tanto

&

son parámetros esencialmente libres aquí. Una vez que especifique, digamos,

, eso produce una solución óptima específica. Pero

sigue siendo un parámetro libre. Entonces, en este punto, la afirmación es que puede haber algún valor de

que produzca la misma solución óptima. Esencialmente no hay restricciones sobre lo que debe ser

; no es como si tuviera que ser alguna función fija de

, como

o algo así.

λ

$\lambda$

t

$t$

λ

$\lambda$

t

$t$

t

$t$

t

$t$

λ

$\lambda$

t = λ / 2

$t=\lambda/2$

gung - Restablece a Monica

@Royi, me gustaría saber 1- ¿por qué su fórmula tiene (1/2), mientras que las fórmulas en cuestión no? 2- ¿estás usando KKT para mostrar la equivalencia de las dos fórmulas? 3- si es así, todavía no puedo ver esa equivalencia. No estoy seguro, pero lo que espero ver es esa prueba para mostrar que la fórmula uno = fórmula dos.

jeza 01 de

1. Simplemente más fácil cuando diferencia el término LS. Puedes mover mi

al OP

por un factor de dos. 2. Usé KKT para el segundo caso. El primer caso no tiene restricciones, por lo tanto, solo puede resolverlo. 3. No existe una ecuación de forma cerrada entre ellos. Mostré la lógica y cómo puedes crear un gráfico conectándolos. Pero como escribí, cambiará para cada

(depende de los datos).

λ

$\lambda$

λ

$\lambda$

y

$y$

Royi

9

Un enfoque menos matemáticamente riguroso, pero posiblemente más intuitivo, para comprender lo que está sucediendo es comenzar con la versión de restricción (ecuación 3.42 en la pregunta) y resolverla utilizando los métodos del "Multiplicador de Lagrange" ( https: //en.wikipedia .org / wiki / Lagrange_multiplier o su texto de cálculo multivariable favorito). Solo recuerda que en el cálculo es el vector de variables, pero en nuestro caso es constante y es el vector variable. Una vez que aplica la técnica del multiplicador de Lagrange, termina con la primera ecuación (3.41) (después de tirar el extra que es constante en relación con la minimización y puede ignorarse). $x$ $x$ $\beta$ $-\lambda t$

Esto también muestra que esto funciona para el lazo y otras restricciones.

Greg Snow
fuente

8

Quizás valga la pena leer sobre la dualidad lagrangiana y una relación más amplia (a veces equivalencia) entre:

optimización sujeta a restricciones duras (es decir, inviolables)
optimización con penalizaciones por violar restricciones.

Introducción rápida a la dualidad débil y dualidad fuerte

Supongamos que tenemos alguna función de dos variables. Para cualquier $f(x,y)$ $\hat{x}$ , se tiene: $\hat{y}$

min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

Dado que es válido para cualquier e que también sostiene que: $\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$

Esto se conoce como dualidad débil . En ciertas circunstancias, también tiene una fuerte dualidad (también conocida como la propiedad del punto de silla de montar ):

max_{y} min_{x} f (x, y) = min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) = \min_x \max_y f(x, y)$

Cuando se mantiene una fuerte dualidad, resolver el problema dual también resuelve el problema primario. En cierto sentido, ¡son el mismo problema!

Lagrangiano para la regresión de cresta restringida

Permítanme definir la función como: $\mathcal{L}$

L (b, λ) = \sum_{i = 1}^{n} (y - x_{i} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t)

$\mathcal{L}(\mathbf{b}, \lambda) = \sum_{i=1}^n (y - \mathbf{x}_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right)$

La interpretación min-max del lagrangiano

El problema de regresión de Ridge sujeto a restricciones duras es:

min_{b} max_{λ \geq 0} L (b, λ)

$\min_\mathbf{b} \max_{\lambda \geq 0} \mathcal{L}(\mathbf{b}, \lambda)$

You pick $\mathbf{b}$ to minimize the objective, cognizant that after $\mathbf{b}$ is picked, your opponent will set $\lambda$ to infinity if you chose $\mathbf{b}$ such that $\sum_{j=1}^p b_j^2 > t$ .

If strong duality holds (which it does here because Slater's condition is satisfied for $t>0$ ), you then achieve the same result by reversing the order:

max_{λ \geq 0} min_{b} L (b, λ)

$\max_{\lambda \geq 0} \min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$

Here, your opponent chooses $\lambda$ first! You then choose $\mathbf{b}$ to minimize the objective, already knowing their choice of $\lambda$ . The $\min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ part (taken $\lambda$ as given) is equivalent to the 2nd form of your Ridge Regression problem.

As you can see, this isn't a result particular to Ridge regression. It is a broader concept.

References

(I started this post following an exposition I read from Rockafellar.)

Rockafellar, R.T., Convex Analysis

You might also examine lectures 7 and lecture 8 from Prof. Stephen Boyd's course on convex optimization.

Matthew Gunn
fuente

note that your answer can be extended to any convex function.

81235

6

They are not equivalent.

For a constrained minimization problem

\begin{matrix} (1) & min_{b} \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} s . t . \sum_{j = 1}^{p} b_{j}^{2} \leq t, b = (b_{1}, . . ., b_{p}) \end{matrix}

$\min_{\mathbf b} \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2\\ s.t. \sum_{j=1}^p b_j^2 \leq t,\;\;\; \mathbf b = (b_1,...,b_p) \tag{1}$

we solve by minimize over $\mathbf b$ the corresponding Lagrangean

\begin{matrix} (2) & Λ = \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t) \end{matrix}

$\Lambda = \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right) \tag{2}$

Here, $t$ is a bound given exogenously, $\lambda \geq 0$ is a Karush-Kuhn-Tucker non-negative multiplier, and both the beta vector and $\lambda$ are to be determined optimally through the minimization procedure given $t$ .

Comparing $(2)$ and eq $(3.41)$ in the OP's post, it appears that the Ridge estimator can be obtained as the solution to

\begin{matrix} (3) & min_{b} {Λ + λ t} \end{matrix}

$\min_{\mathbf b}\{\Lambda + \lambda t\} \tag{3}$

Since in $(3)$ the function to be minimized appears to be the Lagrangean of the constrained minimization problem plus a term that does not involve $\mathbf b$ , it would appear that indeed the two approaches are equivalent...

But this is not correct because in the Ridge regression we minimize over $\mathbf b$ given $\lambda >0$ . But, in the lens of the constrained minimization problem, assuming $\lambda >0$ imposes the condition that the constraint is binding, i.e that

\sum_{j = 1}^{p} (b_{j, r i d g e}^{*})^{2} = t

$\sum_{j=1}^p (b^*_{j,ridge})^2 = t$

The general constrained minimization problem allows for $\lambda = 0$ also, and essentially it is a formulation that includes as special cases the basic least-squares estimator ( $\lambda ^*=0$ ) and the Ridge estimator ( $\lambda^* >0$ ).

So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.

Alecos Papadopoulos
fuente

@MartijnWeterings Thanks for the comment, I have reworked my answer.

Alecos Papadopoulos

@MartijnWeterings I do not see what is confusing since the expression written in your comment is exactly the expression I wrote in my reworked post.

Alecos Papadopoulos

1

This was the duplicate question I had in mind were the equivalence is explained very intuitively to me math.stackexchange.com/a/336618/466748 the argument that you give for the two not being equivalent seems only secondary to me, and a matter of definition (the OP uses

λ \geq 0

$\lambda \geq 0$ instead of

λ > 0

$\lambda > 0$ and we could just as well add the constrain

t < ‖ β^{O L S} ‖_{2}^{2}

$t < \Vert \beta^{OLS} \Vert^2_2$ to exclude the cases where

λ = 0

$\lambda=0$ ) .

Sextus Empiricus

@MartijnWeterings When A is a special case of B, A cannot be equivalent to B. And ridge regression is a special case of the general constrained minimization problem, Namely a situation to which we arrive if we constrain further the general problem (like you do in your last comment).

Alecos Papadopoulos

Certainly you could define some constrained minimization problem that is more general then ridge regression (like you can also define some regularization problem that is more general than ridge regression, e.g. negative ridge regression), but then the non-equivalence is due to the way that you define the problem and not due to the transformation from the constrained representation to the Lagrangian representation. The two forms can be seen as equivalent within the constrained formulation/definition (non-general) that are useful for ridge regression.

Sextus Empiricus

La prueba de fórmulas equivalentes de regresión de crestas

Respuestas:

Recursos

Introducción rápida a la dualidad débil y dualidad fuerte

Lagrangiano para la regresión de cresta restringida

La interpretación min-max del lagrangiano

References