Métodos de gradiente proximal para el aprendizaje

Los métodos de aprendizaje de gradiente proximal (división hacia adelante y hacia atrás) son un área de investigación en la teoría de optimización y aprendizaje estadístico que estudia algoritmos para una clase general de problemas de regularización convexa donde la penalización de regularización puede no ser diferenciable . Un ejemplo de ello es la regularización (también conocida como Lasso) de la forma ${\displaystyle \ell _{1}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},\quad {\text{ where }}x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$

Los métodos de gradiente proximal ofrecen un marco general para resolver problemas de regularización a partir de la teoría del aprendizaje estadístico con penalizaciones que se adaptan a una aplicación de problema específica. ^{[1] [2]} Estas penalizaciones personalizadas pueden ayudar a inducir cierta estructura en las soluciones de problemas, como la escasez (en el caso de lasso ) o la estructura de grupo (en el caso de lasso de grupo ).

Antecedentes relevantes

Los métodos de gradiente proximal son aplicables en una amplia variedad de escenarios para resolver problemas de optimización convexa de la forma

${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x),}$

donde es convexa y diferenciable con gradiente continuo de Lipschitz , es una función convexa , semicontinua inferior que posiblemente no sea diferenciable, y es un conjunto, típicamente un espacio de Hilbert . El criterio habitual de minimiza si y solo si en el entorno convexo y diferenciable ahora se reemplaza por ${\displaystyle F}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle x}$ ${\displaystyle F(x)+R(x)}$ ${\displaystyle \nabla (F+R)(x)=0}$

${\displaystyle 0\in \partial (F+R)(x),}$

donde denota el subdiferencial de una función convexa de valor real . ${\displaystyle \partial \varphi }$ ${\displaystyle \varphi }$

Dada una función convexa, un operador importante a considerar es su operador proximal definido por ${\displaystyle \varphi :{\mathcal {H}}\to \mathbb {R} }$ ${\displaystyle \operatorname {prox} _{\varphi }:{\mathcal {H}}\to {\mathcal {H}}}$

${\displaystyle \operatorname {prox} _{\varphi }(u)=\operatorname {arg} \min _{x\in {\mathcal {H}}}\varphi (x)+{\frac {1}{2}}\|u-x\|_{2}^{2},}$

que está bien definido debido a la estricta convexidad de la norma. El operador proximal puede verse como una generalización de una proyección . ^{[1] [3] [4]} Vemos que el operador de proximidad es importante porque es un minimizador del problema si y solo si ${\displaystyle \ell _{2}}$ ${\displaystyle x^{*}}$ ${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x)}$

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right),}$donde es cualquier número real positivo. ^[1] ${\displaystyle \gamma >0}$

Descomposición de Moreau

Una técnica importante relacionada con los métodos de gradiente proximal es la descomposición de Moreau, que descompone el operador de identidad como la suma de dos operadores de proximidad. ^[1] Es decir, sea una función convexa semicontinua inferior en un espacio vectorial . Definimos su conjugado de Fenchel como la función ${\displaystyle \varphi :{\mathcal {X}}\to \mathbb {R} }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \varphi ^{*}:{\mathcal {X}}\to \mathbb {R} }$

${\displaystyle \varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).}$

La forma general de la descomposición de Moreau establece que para cualquier y cualquier que ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle \gamma >0}$

${\displaystyle x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),}$

lo que implica que . ^{[1] [3]} La descomposición de Moreau puede verse como una generalización de la descomposición ortogonal habitual de un espacio vectorial, análoga al hecho de que los operadores de proximidad son generalizaciones de proyecciones. ^[1] ${\displaystyle \gamma =1}$ ${\displaystyle x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)}$

En ciertas situaciones puede resultar más sencillo calcular el operador de proximidad para el conjugado en lugar de la función , y por lo tanto se puede aplicar la descomposición de Moreau. Este es el caso del grupo lasso . ${\displaystyle \varphi ^{*}}$ ${\displaystyle \varphi }$

Regularización de lazo

Consideremos el problema de minimización de riesgo empírico regularizado con pérdida cuadrada y con la norma como penalización de regularización: ${\displaystyle \ell _{1}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{1},}$

El problema de regularización a veces se denomina lasso ( operador de selección y contracción mínima absoluta ). ^[5] Estos problemas de regularización son interesantes porque inducen soluciones dispersas , es decir, las soluciones al problema de minimización tienen relativamente pocos componentes distintos de cero. Se puede considerar que Lasso es una relajación convexa del problema no convexo. ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle w}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \|w\|_{0},}$

donde denota la "norma", que es el número de entradas distintas de cero del vector . Las soluciones dispersas son de particular interés en la teoría del aprendizaje para la interpretabilidad de los resultados: una solución dispersa puede identificar una pequeña cantidad de factores importantes. ^[5] ${\displaystyle \|w\|_{0}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle w}$

Resolviendo para L1operador de proximidad

Para simplificar, limitamos nuestra atención al problema donde . Para resolver el problema ${\displaystyle \lambda =1}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\|w\|_{1},}$

Consideramos nuestra función objetivo en dos partes: un término convexo diferenciable y una función convexa . Nótese que no es estrictamente convexa. ${\displaystyle F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}}$ ${\displaystyle R(w)=\|w\|_{1}}$ ${\displaystyle R}$

Calculemos el operador de proximidad para . Primero, encontramos una caracterización alternativa del operador de proximidad de la siguiente manera: ${\displaystyle R(w)}$ ${\displaystyle \operatorname {prox} _{R}(x)}$

${\displaystyle {\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}}$

Porque es fácil de calcular : la entrada ésima de es precisamente ${\displaystyle R(w)=\|w\|_{1}}$ ${\displaystyle \partial R(w)}$ ${\displaystyle i}$ ${\displaystyle \partial R(w)}$

${\displaystyle \partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}}$

Utilizando la recaracterización del operador de proximidad dada anteriormente, para la elección de y tenemos que se define por entrada por ${\displaystyle R(w)=\|w\|_{1}}$ ${\displaystyle \gamma >0}$ ${\displaystyle \operatorname {prox} _{\gamma R}(x)}$

${\displaystyle \left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}}$

que se conoce como operador de umbral suave . ^{[1] [6]} ${\displaystyle S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)}$

Esquemas iterativos de punto fijo

Para resolver finalmente el problema del lazo, consideramos la ecuación de punto fijo mostrada anteriormente:

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).}$

Dado que hemos calculado la forma del operador de proximidad explícitamente, entonces podemos definir un procedimiento de iteración de punto fijo estándar. Es decir, fijar un valor inicial y para definir ${\displaystyle w^{0}\in \mathbb {R} ^{d}}$ ${\displaystyle k=1,2,\ldots }$

${\displaystyle w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).}$

Obsérvese aquí la compensación efectiva entre el término de error empírico y la penalización de regularización . Este método de punto fijo ha desacoplado el efecto de las dos funciones convexas diferentes que componen la función objetivo en un paso de descenso de gradiente ( ) y un paso de umbralización suave (a través de ). ${\displaystyle F(w)}$ ${\displaystyle R(w)}$ ${\displaystyle w^{k}-\gamma \nabla F\left(w^{k}\right)}$ ${\displaystyle S_{\gamma }}$

La convergencia de este esquema de punto fijo está bien estudiada en la literatura ^{[1] [6]} y está garantizada bajo la elección apropiada del tamaño del paso y la función de pérdida (como la pérdida cuadrada tomada aquí). Nesterov introdujo métodos acelerados en 1983 que mejoran la tasa de convergencia bajo ciertas suposiciones de regularidad en . ^[7] Dichos métodos han sido estudiados extensamente en años anteriores. ^[8] Para problemas de aprendizaje más generales donde el operador de proximidad no puede calcularse explícitamente para algún término de regularización , dichos esquemas de punto fijo aún pueden llevarse a cabo utilizando aproximaciones tanto al gradiente como al operador de proximidad. ^{[4] [9]} ${\displaystyle \gamma }$ ${\displaystyle F}$ ${\displaystyle R}$

Consideraciones prácticas

En la última década se han producido numerosos avances en las técnicas de optimización convexa que han influido en la aplicación de los métodos de gradiente proximal en la teoría del aprendizaje estadístico. En este artículo, analizamos algunos temas importantes que pueden mejorar en gran medida el rendimiento algorítmico práctico de estos métodos. ^{[2] [10]}

Tamaño de paso adaptable

En el esquema de iteración de punto fijo

${\displaystyle w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),}$

se puede permitir un tamaño de paso variable en lugar de uno constante . Se han propuesto numerosos esquemas de tamaño de paso adaptativo en toda la literatura. ^{[1] [4] [11] [12]} Las aplicaciones de estos esquemas ^{[2] [13]} sugieren que pueden ofrecer una mejora sustancial en el número de iteraciones necesarias para la convergencia de punto fijo. ${\displaystyle \gamma _{k}}$ ${\displaystyle \gamma }$

Red elástica (regularización de normas mixtas)

La regularización elástica de red ofrece una alternativa a la regularización pura. El problema de la regularización lasso() involucra el término de penalización , que no es estrictamente convexo. Por lo tanto, las soluciones para donde es alguna función de pérdida empírica, no necesitan ser únicas. Esto a menudo se evita mediante la inclusión de un término estrictamente convexo adicional, como una penalización de regularización de norma. Por ejemplo, se puede considerar el problema ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle R(w)=\|w\|_{1}}$ ${\displaystyle \min _{w}F(w)+R(w),}$ ${\displaystyle F}$ ${\displaystyle \ell _{2}}$

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}+\lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right),}$

donde Para el término de penalización ahora es estrictamente convexo y, por lo tanto, el problema de minimización ahora admite una solución única. Se ha observado que para suficientemente pequeño , el término de penalización adicional actúa como un precondicionador y puede mejorar sustancialmente la convergencia sin afectar negativamente la escasez de soluciones. ^{[2] [14]} ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ ${\displaystyle 0<\mu \leq 1}$ ${\displaystyle \lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)}$ ${\displaystyle \mu >0}$ ${\displaystyle \mu \|w\|_{2}^{2}}$

Explotación de la estructura de grupo

Los métodos de gradiente proximal proporcionan un marco general que se puede aplicar a una amplia variedad de problemas en la teoría del aprendizaje estadístico . Algunos problemas de aprendizaje a menudo pueden implicar datos que tienen una estructura adicional que se conoce a priori . En los últimos años, ha habido nuevos desarrollos que incorporan información sobre la estructura de grupos para proporcionar métodos que se adaptan a diferentes aplicaciones. Aquí examinamos algunos de estos métodos.

Lazo de grupo

El lazo de grupo es una generalización del método lazo cuando las características se agrupan en bloques disjuntos. ^[15] Supongamos que las características se agrupan en bloques . Aquí tomamos como penalización de regularización ${\displaystyle \{w_{1},\ldots ,w_{G}\}}$

${\displaystyle R(w)=\sum _{g=1}^{G}\|w_{g}\|_{2},}$

que es la suma de la norma en los vectores de características correspondientes para los diferentes grupos. Se puede utilizar un análisis de operador de proximidad similar al anterior para calcular el operador de proximidad para esta penalización. Donde la penalización del lazo tiene un operador de proximidad que es un umbral suave en cada componente individual, el operador de proximidad para el lazo de grupo es un umbral suave en cada grupo. Para el grupo tenemos que el operador de proximidad de está dado por ${\displaystyle \ell _{2}}$ ${\displaystyle w_{g}}$ ${\displaystyle \lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)}$

${\displaystyle {\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}}$

¿Dónde está el grupo th? ${\displaystyle w_{g}}$ ${\displaystyle g}$

A diferencia de lasso, la derivación del operador de proximidad para el grupo lasso se basa en la descomposición de Moreau. Aquí el operador de proximidad del conjugado de la penalización del grupo lasso se convierte en una proyección sobre la bola de una norma dual . ^[2]

Otras estructuras de grupo

A diferencia del problema del lazo de grupo, donde las características se agrupan en bloques disjuntos, puede darse el caso de que las características agrupadas se superpongan o tengan una estructura anidada. Tales generalizaciones del lazo de grupo se han considerado en una variedad de contextos. ^{[16] [17] [18] [19]} Para los grupos superpuestos, un enfoque común se conoce como lazo de grupo latente que introduce variables latentes para tener en cuenta la superposición. ^{[20] [21]} Las estructuras de grupo anidadas se estudian en la predicción de la estructura jerárquica y con gráficos acíclicos dirigidos . ^[18]

Véase también

• Análisis convexo
• Método del gradiente proximal
• Regularización
• Teoría del aprendizaje estadístico

Referencias

1. Combettes, Patrick L.; Wajs, Valérie R. (2005). "Recuperación de la señal mediante división proximal hacia delante y hacia atrás". Modelo multiescala. Simul . 4 (4): 1168–1200. doi :10.1137/050626090. S2CID  15064954.
2. Mosci, S.; Rosasco, L.; Matteo, S.; Verri, A.; Villa, S. (2010). "Resolución de regularización de escasez estructurada con métodos proximales". Aprendizaje automático y descubrimiento de conocimiento en bases de datos . Apuntes de clase en informática. Vol. 6322. págs. 418–433. doi : 10.1007/978-3-642-15883-4_27 . ISBN . 978-3-642-15882-7.
3. Moreau, J.-J. (1962). "Funciones convexas duales y puntos próximos en un espacio hilbertien". Cuentas Rendus de la Academia de Ciencias, Serie A. 255 : 2897–2899. SEÑOR  0144188. Zbl  0118.10502.
4. Bauschke, HH y Combettes, PL (2011). Análisis convexo y teoría de operadores monótonos en espacios de Hilbert . Springer.{{cite book}}: CS1 maint: multiple names: authors list (link)
5. Tibshirani, R. (1996). "Regresión contraída y selección mediante el lazo". JR Stat. Soc. Ser. B . 1. 58 (1): 267–288. doi :10.1111/j.2517-6161.1996.tb02080.x.
6. Daubechies, I.; Defrise, M.; De Mol, C. (2004). "Un algoritmo de umbralización iterativo para un problema inverso lineal con una restricción de escasez". Comm. Pure Appl. Math . 57 (11): 1413–1457. arXiv : math/0307152 . doi :10.1002/cpa.20042. S2CID  1438417.
7. Nesterov, Yurii (1983). "Un método para resolver un problema de programación convexa con tasa de convergencia ". Matemáticas soviéticas - Doklady . 27 (2): 372–376. ${\displaystyle O(1/k^{2})}$
8. Nesterov, Yurii (2004). Lecciones introductorias sobre optimización convexa . Editorial Kluwer Academic.
9. Villa, S.; Salzo, S.; Baldassarre, L.; Verri, A. (2013). "Algoritmos de avance-retroceso acelerados e inexactos". SIAM J. Optim . 23 (3): 1607–1633. CiteSeerX 10.1.1.416.3633 . doi :10.1137/110844805. S2CID  11379846. 
10. Bach, F.; Jenatton, R.; Mairal, J.; Obozinski, Gl. (2011). "Optimización con penalizaciones que inducen escasez". Fundamentos y tendencias en aprendizaje automático . 4 (1): 1–106. arXiv : 1108.0775 . Código Bibliográfico :2011arXiv1108.0775B. doi :10.1561/2200000015. S2CID  56356708.
11. Loris, I.; Bertero, M.; De Mol, C.; Zanella, R.; Zanni, L. (2009). "Métodos de proyección de gradiente acelerado para la recuperación de señal con restricciones de escala mediante reglas de selección de longitud de paso". Applied & Comp. Análisis armónico . 27 (2): 247–254. arXiv : 0902.4424 . doi :10.1016/j.acha.2009.02.003. S2CID  18093882. ${\displaystyle \ell _{1}}$
12. Wright, SJ; Nowak, RD; Figueiredo, MAT (2009). "Reconstrucción dispersa mediante aproximación separable". IEEE Trans. Image Process . 57 (7): 2479–2493. Bibcode :2009ITSP...57.2479W. CiteSeerX 10.1.1.115.9334 . doi :10.1109/TSP.2009.2016892. S2CID  7399917. 
13. Loris, Ignace (2009). "Sobre el rendimiento de algoritmos para la minimización de funcionales penalizados". Problemas inversos . 25 (3): 035008. arXiv : 0710.4082 . Código Bibliográfico :2009InvPr..25c5008L. doi :10.1088/0266-5611/25/3/035008. S2CID  14213443. ${\displaystyle \ell _{1}}$
14. De Mol, C.; De Vito, E.; Rosasco, L. (2009). "Regularización de red elástica en la teoría del aprendizaje". J. Complejidad . 25 (2): 201–230. arXiv : 0807.3423 . doi :10.1016/j.jco.2009.01.002. S2CID  7167292.
15. Yuan, M.; Lin, Y. (2006). "Selección de modelos y estimación en regresión con variables agrupadas". JR Stat. Soc. B . 68 (1): 49–67. doi : 10.1111/j.1467-9868.2005.00532.x . S2CID  6162124.
16. Chen, X.; Lin, Q.; Kim, S.; Carbonell, JG; Xing, EP (2012). "Método de suavizado de gradiente proximal para regresión dispersa estructurada general". Ann. Appl. Stat . 6 (2): 719–752. arXiv : 1005.4717 . doi :10.1214/11-AOAS514. S2CID  870800.
17. Mosci, S.; Villa, S.; Verri, A.; Rosasco, L. (2010). "Un algoritmo primal-dual para regularización dispersa de grupos con grupos superpuestos". NIPS . 23 : 2604–2612.
18. Jenatton, R.; Audibert, J.-Y.; Bach, F. (2011). "Selección de variables estructuradas con normas inductoras de escasez". J. Mach. Learn. Res . 12 : 2777–2824. arXiv : 0904.3523 . Código Bibliográfico :2009arXiv0904.3523J.
19. Zhao, P.; Rocha, G.; Yu, B. (2009). "La familia de penalizaciones absolutas compuestas para la selección de variables agrupadas y jerárquicas". Ann. Stat . 37 (6A): 3468–3497. arXiv : 0909.0411 . Código Bibliográfico :2009arXiv0909.0411Z. doi :10.1214/07-AOS584. S2CID  9319285.
20. Obozinski, Guillaume; Jacob, Laurent; Vert, Jean-Philippe (2011). "Lazo de grupo con superposiciones: el enfoque del lazo de grupo latente". arXiv : 1110.0413 [stat.ML].
21. Villa, Silvia; Rosasco, Lorenzo; Mosci, Sofia; Verri, Alessandro (2012). "Métodos proximales para la penalización del lazo de grupo latente". arXiv : 1209.0368 [math.OC].