La regularización de Tikhonov (o la cresta de regresión) se agrega una restricción que $\|\beta\|^2$, $L^2$- norma del vector de parámetros, no es mayor que un valor dado (es decir $c$). Equivalentemente, se puede resolver un sin restricciones de la minimización de los mínimos cuadrados pena con $\alpha\|\beta\|^2$ añadido, donde $\alpha$ es una constante (esta es la forma de Lagrange de la limitación de problema).
El de arriba es de la Wikipedia. ¿Por qué es el LS sin restricciones con $\alpha\|\beta\|^2$ añadido al coste equivalente a la del LS problema con una restricción adicional de que el $\|\beta\|^2 \leq c$?
¿Cuál es la relación entre el$\alpha$$c$?
Gracias!
Respuestas
¿Demasiados anuncios?
Primero vamos a definir los dos problemas:
- Problema 1: \begin{equation} \min_{\beta} ~f_\alpha(\beta):=\frac{1}{2}\Vert y-X\beta\Vert^2 +\alpha\Vert \beta\Vert^2\end{equation}
- Problema 2: \begin{align} \min_{\beta} ~&\frac{1}{2}\Vert y-X\beta\Vert^2\\ s.t.~&\Vert \beta\Vert^2-c\leq 0\end{align}
El Lagrangiano para el Problema 2 se lee: \begin{equation} \mathcal{L}(\beta,\lambda)=\frac{1}{2}\Vert y-X\beta\Vert^2+\lambda (\Vert \beta\Vert^2-c) \end{equation} y probablemente usted ya ve el parecido con el Problema 1 (idénticos, excepto por el término constante $-\lambda c$).
Veamos ahora las condiciones necesarias de optimalidad. Para el Problema 1, estos leer: \begin{equation} \nabla_\beta f_\alpha(\beta^*(\alpha))=0 \end{equation} donde nos voluntariamente escribir $\beta^*(\alpha)$ a mostrar que esta es la solución óptima para un determinado $\alpha$.
Para el Problema 2, las condiciones KKT implica que tenemos: \begin{align*} \nabla_\beta \mathcal{L}(\beta^*,\lambda^*)&=\nabla_\beta f_\lambda(\beta^*)=0\\ \lambda^* (\Vert \beta^*\Vert^2-c)&=0 \end{align*} La primera línea dice que el gradiente de la Lagrangiano con respecto a $\beta$ debe ser nulo y el segundo es el complementario de la condición. (También tenemos $\lambda^* \geq 0$, pero esto es menos importante para nuestra discusión). También se observa que el gradiente de la Lagrangiana es igual a la pendiente de $f_\lambda$ (de la función objetivo del problema 1 pero con $\lambda$ en lugar de $\alpha$).
Ahora supongamos que resolver el Problema 1 para un determinado $\alpha$ y obtener su solución de $\beta^*(\alpha)$. Deje $c=\Vert \beta^*(\alpha)\Vert^2$, el cuadrado de la norma de la solución para el Problema 1. A continuación, $\lambda^*=\alpha$ $\beta^*=\beta^*(\alpha)$ satisfacer las condiciones KKT para el Problema 2, mostrando que ambos Problemas tienen la misma solución. Por el contrario, si usted solucionado el Problema 2, usted puede establecer el $\alpha=\lambda^*$ a recuperar la misma solución de problemas Problema 1.
En suma, ambos problemas son equivalentes al $c=\Vert \beta^*(\alpha)\Vert^2$.
jhclark
Puntos
121
La respuesta de Joe se ve bien, pero si usted está buscando para una cita, en este documento se cubre, así como en el Teorema 1: http://papers.nips.cc/paper/3675-efficient-and-accurate-lp-norm-multiple-kernel-learning (Nota: La carne de la prueba es, en realidad, en el material suplementario).
Kloft et al, "Eficiente y Precisa Lp-Norma Múltiples de Aprendizaje del Núcleo". NIPS de 2009.
XZS
Puntos
179
Usted puede hacer esto directamente si así lo desea. Para resolver el problema de optimización \begin{align} \min_{\beta} ~&\Vert y-X\beta\Vert^2\\ \mathrm{s.t.}~&\Vert \beta\Vert^2\le c\ , \end{align} como en el estándar de primal-dual procedimiento, primero vamos a \begin{align} g(\lambda)=&\inf_\beta\mathcal{L}(\beta,\lambda)\\ =&\inf_\beta\Vert y-X\beta\Vert^2+\lambda (\Vert \beta\Vert^2- c)\\ =& \Vert y-X(X^\mathrm{T}X+\lambda I)^{-1}X^\mathrm{T}y\Vert^2 + \lambda (\Vert(X^\mathrm{T}X+\lambda I)^{-1}X^\mathrm{T}y\Vert^2-c)\ , \end{align} luego resuelve $\max_{\lambda\ge 0} g(\lambda)$. Usted encontrará que $$ \frac{\partial g}{\parcial\lambda}=y^\mathrm{T}X(X^\mathrm{T}X+\lambda I)^{-2}X^\mathrm{T}y c=0\ffi c=\Vert\beta^*_{\mathrm{ridge}}(\lambda)\Vert^2\ . $$
La matriz de derivados \begin{align} \frac{\partial AU(x)B}{\partial x} = & A\frac{\partial U(x)}{\partial x}B\\ \frac{\partial U(x)^{-1}}{\partial x} = &-U(x)^{-1} \frac{\partial U(x)}{\partial x}U(x)^{-1} \end{align} será útil.
Actualización:
Por el camino se puede demostrar al $\lambda$ aumenta, $c$ no aumenta. Más en general, Vamos a $L(x;\lambda)=f(x)+\lambda g(x)$, e $x_i^*=\mathrm{arg\,min}_xL(x;\lambda_i)\,(i=1,2)$. Supongamos $\lambda_2>\lambda_1$$g(x_2^*)>g(x_1^*)$, tenemos \begin{align} &(\lambda_2-\lambda_1)(g(x_2^*)-g(x_1^*))>0\\ \Longrightarrow & \lambda_1g(x_1^*)+\lambda_2g(x_2^*)>\lambda_1g(x_2^*)+\lambda_2g(x_1^*)\\ \Longrightarrow & [f(x_1^*)+\lambda_1g(x_1^*)]+[f(x_2^*)+\lambda_2g(x_2^*)]>[f(x_2^*)+\lambda_1g(x_2^*)]+[f(x_1^*)+\lambda_2g(x_1^*)] \ge [f(x_1^*)+\lambda_1g(x_1^*)]+[f(x_2^*)+\lambda_2g(x_2^*)] \end{align} lo cual es una contradicción, por lo $g(x^*)$ no aumenta al $\lambda$ aumenta. En el contexto de la OP del problema, $c$ no aumenta al $\lambda$ aumenta.
