Regularización y el vector de proyecciones están conectados a través de la idea de optimización restringida y la Karush-Kuhn (sin relación)-Tucker condiciones.
¿Cuáles son las condiciones KKT?
Brevemente, estos estado que, si x es una solución para el problema de "minimizar f(x)g(x) \le 0", x es una solución para el problema de \nabla f(x) = \lambda \nabla g(x) para algunos escalares \lambda. Pero esto es equivalente a decir \nabla f(x) - \lambda \nabla g(x) = 0, lo que significa que x minimiza las restricciones problema de optimización "minimizar f(x) - \lambda g(x)".
La intuición es que:
g(x) < 0. En este caso, x es un "interior de la solución", por lo que el gradiente de f debe ser cero en ese punto. (Si no fuera cero, podríamos mover un poco en esa dirección de x, mientras que el mantenimiento de g(x) < 0, y tienen un mayor valor de f(x). A continuación, establecemos \lambda = 0 y hemos terminado.
O, g(x) = 0. En este caso, x está en el borde de la posible solución de espacio. Localmente, esta ventaja se ve como un hyperplane ortogonal a la gradiente \nabla g(x), debido a que la forma de mantener el g(x) = 0 restricción es que no se mueva arriba o abajo del gradiente. Pero eso significa que la única dirección en la que el gradiente \nabla f podría, posiblemente, el punto es exactamente la misma dirección como \nabla g--si tenía algún componente ortogonal de a \nabla g, podríamos mover x un poco en esa dirección, la estancia en el ortogonal hyperplane g(x) = 0, y aumentar el f(x).
Cómo las condiciones KKT de explicar la relación entre restringida de la minimización y la regularización de
Si g(x) = |x| - c por alguna norma y algunas constantes c, entonces la restricción g(x) \le 0 significa que x se encuentra en una esfera de radio c en virtud de dicha norma. Y en el sin restricciones de la formulación, restando \lambda g(x) a partir de la función que se quiere maximizar es lo que termina de aplicar la penalización de regularización: realmente estás restando \lambda |x| + \lambda c (y el constante \lambda c no importa para la optimización).
La gente suele tomar ventaja de esta "dualidad" entre restricciones y optimización restringida. Para obtener un ejemplo que he podido encontrar rápidamente por Google ver En el LAZO y su doble.
¿Por qué son proyecciones importante aquí?
OK, así que ¿por qué alguien escribiendo un artículo sobre rápido proyecciones, aunque?
Básicamente, una forma de hacer general limitada de optimización--"maximizar f(x) x \in X" -- es hacer lo siguiente:
- Tomar cualquier algoritmo iterativo para sin restricciones de la maximización de f(x)
- Comience con una conjetura x_0
- Tome un paso del algoritmo: x_0^\prime \leftarrow step(x_0)
- A continuación, el proyecto de nuevo en el conjunto de X: x_1 \leftarrow P_X(x_0^\prime).
- Y repetir hasta la convergencia.
Por ejemplo, esta es la forma proyectada de gradiente de la pendiente se deriva de ordinario gradiente de la pendiente. Por supuesto, la optimización de la función de proyección de P_X es de vital importancia aquí.
Poniendo todo junto
Así, supongamos que queremos resolver el LAZO: \arg\min_\beta (\mathbf{y} - \beta^\prime \mathbf{X})^2 + \lambda ||\beta||_1
Ese es el sin restricciones de la versión. Por las condiciones KKT, la adición de la regularización término es equivalente a la restricción de la solución a mentir en ||\beta||_1 \le c para algunas constantes c. Pero eso es sólo el \ell_1-ball con el radio de c!
Así que usted podría imaginar la solución de este con proyectada (sub)gradiente de la pendiente.* Si no, su P_X función sería una proyección sobre la unidad de la pelota, y usted quiere hacer que rápido.
*No creo que la gente realmente hacer esto, porque hay maneras más eficientes. Pero los podría utilizar las proyecciones también. EDIT: como @Dougal señala, una más sofisticada variante de proyección de subgradiente descenso era lo suficientemente bueno como para escribir un artículo sobre en 2008.
