Regularización de escasez estructurada

Consideremos el problema de minimización del riesgo empírico regularizado con núcleo lineal y una función de pérdida.${\displaystyle V(y_{i},f(x))}$ y el${\displaystyle \ell _{0}}$"norma" como penalización de regularización:

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

dónde${\displaystyle x,w\in \mathbb {R^{d}} }$, y${\displaystyle \|w\|_{0}}$denota el${\displaystyle \ell _{0}}$"norma", definida como el número de entradas no nulas del vector${\displaystyle w}$.${\displaystyle f(x)=\langle w,x_{i}\rangle }$ Se dice que es escaso si${\displaystyle \|w\|_{0}=s<d}$. Lo que significa que la salida${\displaystyle Y}$puede describirse mediante un pequeño subconjunto de variables de entrada.

En términos más generales, supongamos que hay un diccionario.${\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }$con${\displaystyle j=1,...,p}$ se da, de tal manera que la función objetivo${\displaystyle f(x)}$Un problema de aprendizaje se puede escribir como:

${\displaystyle f(x)=\sum _ {j=1}^{p}\phi _ {j}(x)w_ {j}}$,${\displaystyle \forall x\in X}$

El${\displaystyle \ell _{0}}$norma${\displaystyle \|f\|_{0}=\|w\|_{0}}$ como el número de componentes no nulos de${\displaystyle w}$se define como

${\displaystyle \|w\|_{0}=|\{j|w_{j}\neq 0,j\in \{1,...,p\}\}|}$, dónde${\displaystyle |A|}$es la cardinalidad del conjunto${\displaystyle A}$.

${\displaystyle f}$Se dice que es escaso si${\displaystyle \|f\|_{0}=\|w\|_{0}=s<d}$.

Sin embargo, al usar el${\displaystyle \ell _{0}}$La norma para la regularización favorece las soluciones más dispersas, es computacionalmente difícil de usar y además no es convexa. Una norma computacionalmente más factible que favorece las soluciones más dispersas es la${\displaystyle \ell _{1}}$norma; se ha demostrado que esto aún favorece las soluciones más dispersas y además es convexo. ^{[ 4 ]}

La regularización de escasez estructurada extiende y generaliza el problema de selección de variables que caracteriza la regularización de escasez. ^{[ 2 ] [ 3 ]} Considere el problema de minimización de riesgo empírico regularizado anterior con un núcleo general y un mapa de características asociado.${\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }$con${\displaystyle j=1,...,p}$.

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

El término de regularización${\displaystyle \lambda \|w\|_{0}}$penaliza cada${\displaystyle w_{j}}$componente de forma independiente, lo que significa que el algoritmo suprimirá las variables de entrada de forma independiente entre sí.

En ciertas situaciones, podemos querer imponer mayor estructura al proceso de regularización, de modo que, por ejemplo, las variables de entrada se supriman según grupos predefinidos. Los métodos de regularización de escasez estructurada permiten imponer dicha estructura añadiendo una estructura a las normas que definen el término de regularización.

El caso de grupos no superpuestos es la instancia más básica de escasez estructurada. En él, una partición a priori del vector de coeficientes${\displaystyle w}$en${\displaystyle G}$Se asume que los grupos no se superponen.${\displaystyle w_{g}}$sea ​​el vector de coeficientes en el grupo${\displaystyle g}$, podemos definir un término de regularización y su norma de grupo como

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

dónde${\displaystyle \|w_{g}\|_{g}}$es el grupo${\displaystyle \ell _{2}}$norma${\displaystyle \|w_{g}\|_{g}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}$, ${\displaystyle G_{g}}$es grupo${\displaystyle g}$, y${\displaystyle w_{g}^{j}}$es el j-ésimo componente del grupo${\displaystyle G_{g}}$.

La norma anterior también se conoce como Lasso de grupo . ^{[ 2 ]} Este regularizador fuerza grupos de coeficientes completos a tender a cero, en lugar de coeficientes individuales. Dado que los grupos no se superponen, el conjunto de coeficientes distintos de cero se obtiene como la unión de los grupos que no se establecieron en cero, y viceversa para el conjunto de coeficientes cero.

Los grupos superpuestos son el caso de escasez de estructura donde una variable puede pertenecer a más de un grupo.${\displaystyle g}$Este caso suele ser de interés, ya que puede representar una clase de relaciones entre variables más general que la que pueden representar los grupos no superpuestos, como las estructuras de árbol u otro tipo de grafos. ^{[ 3 ] [ 8 ]}

Existen dos tipos de enfoques de regularización de escasez de grupos superpuestos, que se utilizan para modelar diferentes tipos de relaciones entre variables de entrada:

La función objetivo que utiliza el lasso de grupo consiste en una función de error , que generalmente debe ser convexa pero no necesariamente fuertemente convexa, y un grupo${\displaystyle \ell _{1}}$término de regularización. Un problema con esta función objetivo es que es convexa pero no necesariamente fuertemente convexa, y por lo tanto, generalmente no conduce a soluciones únicas. ^{[ 9 ]}

Un ejemplo de cómo solucionar esto es introducir el cuadrado${\displaystyle \ell _{2}}$norma del vector de peso como un término de regularización adicional mientras se mantiene la${\displaystyle \ell _{1}}$término de regularización del enfoque lasso de grupo. ^{[ 9 ]} Si el coeficiente del cuadrado ${\displaystyle \ell _{2}}$El término de norma es mayor que${\displaystyle 0}$, entonces porque el cuadrado ${\displaystyle \ell _{2}}$Si el término de norma es fuertemente convexo, la función objetivo resultante también será fuertemente convexa. ^{[ 9 ]} Siempre que la ${\displaystyle \ell _{2}}$Si el coeficiente es suficientemente pequeño pero aún positivo, el vector de pesos que minimiza la función objetivo resultante es generalmente muy cercano a un vector de pesos que minimiza la función objetivo que resultaría de eliminar el grupo. ${\displaystyle \ell _{2}}$término de regularización completamente de la función objetivo original; este último escenario corresponde al enfoque Lasso de grupo. ^{[ 9 ]} Por lo tanto, este enfoque permite una optimización más simple manteniendo la escasez. ^{[ 9 ]}

Ver: Función de conjunto submodular

Además de las normas mencionadas anteriormente, en los métodos de escasez estructurada se utilizan otras normas, como las normas jerárquicas y las definidas en cuadrículas. Estas normas surgen de funciones submodulares y permiten incorporar supuestos previos sobre la estructura de las variables de entrada. En el contexto de las normas jerárquicas, esta estructura puede representarse como un grafo dirigido acíclico sobre las variables, mientras que en el contexto de las normas basadas en cuadrículas, la estructura puede representarse mediante una cuadrícula. ^{[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]}

El problema de elegir el mejor subconjunto de variables de entrada se puede formular naturalmente bajo un marco de penalización como: ^{[ 4 ]}

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

Dónde${\displaystyle \|w\|_{0}}$denota el${\displaystyle \ell _{0}}$"norma", definida como el número de entradas no nulas del vector${\displaystyle w}$.

Aunque esta formulación tiene sentido desde una perspectiva de modelado, es computacionalmente inviable, ya que equivale a una búsqueda exhaustiva que evalúa todos los subconjuntos posibles de variables. ^{[ 4 ]}

Existen dos enfoques principales para resolver el problema de optimización: 1) métodos voraces, como la regresión por pasos en estadística o la búsqueda de coincidencias en el procesamiento de señales ; y 2) enfoques de formulación de relajación convexa y métodos de optimización de gradiente proximal .

Una aproximación natural para el problema de selección del mejor subconjunto es la${\displaystyle \ell _{1}}$regularización de la norma: ^{[ 4 ]}

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

Dicho esquema se llama búsqueda de base o Lasso , que sustituye la${\displaystyle \ell _{0}}$"norma" para la convexa, no diferenciable${\displaystyle \ell _{1}}$norma.

Los métodos de gradiente proximal , también llamados división hacia adelante-hacia atrás, son métodos de optimización útiles para minimizar funciones con un componente convexo y diferenciable , y un componente convexo potencialmente no diferenciable.

Por lo tanto, los métodos de gradiente proximal son útiles para resolver problemas de regularización de escasez y escasez estructurada ^{[ 9 ]} de la siguiente forma:

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

Dónde${\displaystyle V(y_{i},w,x_{i})}$es una función de pérdida convexa y diferenciable como la pérdida cuadrática , y${\displaystyle R(w)}$es un regularizador convexo potencialmente no diferenciable como el${\displaystyle \ell _{1}}$norma.

La regularización de escasez estructurada se puede aplicar en el contexto del aprendizaje de múltiples núcleos . ^{[ 16 ]} El aprendizaje de múltiples núcleos se refiere a un conjunto de métodos de aprendizaje automático que utilizan un conjunto predefinido de núcleos y aprenden una combinación lineal o no lineal óptima de núcleos como parte del algoritmo.

En los algoritmos mencionados anteriormente, se consideró un espacio completo de una sola vez y se dividió en grupos, es decir, subespacios. Un punto de vista complementario es considerar el caso en el que se combinan espacios distintos para obtener uno nuevo. Es útil discutir esta idea considerando diccionarios finitos. Los diccionarios finitos con elementos linealmente independientes —estos elementos también se conocen como átomos— se refieren a conjuntos finitos de funciones base linealmente independientes, cuyas combinaciones lineales definen espacios de hipótesis. Los diccionarios finitos se pueden usar para definir núcleos específicos, como se mostrará. ^{[ 16 ]} Supongamos para este ejemplo que, en lugar de un solo diccionario, se consideran varios diccionarios finitos.

Para simplificar, consideremos el caso en el que solo hay dos diccionarios.${\displaystyle A=\{a_{j}:X\rightarrow \mathbb {R} ,j=1,...,p\}}$y${\displaystyle B=\{b_{t}:X\rightarrow \mathbb {R} ,t=1,...,q\}}$dónde${\displaystyle q}$y${\displaystyle p}$son enteros, serán considerados. Los átomos en${\displaystyle A}$así como los átomos en${\displaystyle B}$Se supone que son linealmente independientes.${\displaystyle D=\{d_{k}:X\rightarrow \mathbb {R} ,k=1,...,p+q\}=A\cup B}$Sea la unión de los dos diccionarios. Consideremos el espacio lineal de funciones.${\displaystyle H}$dadas por combinaciones lineales de la forma

${\displaystyle f(x)=\sum _{i=1}^{p+q}{w^{j}d_{j}(x)}=\sum _{j=1}^{p}{w_{A}^{j}a_{j}(x)}+\sum _{t=1}^{q}{w_{B}^{t}b_{t}(x)},x\in X}$

para algunos vectores de coeficientes${\displaystyle w_{A}\in \mathbb {R} ^{p},w_{B}\in \mathbb {R} ^{q}}$, dónde${\displaystyle w=(w_{A},w_{B})}$. Supongamos que los átomos en${\displaystyle D}$seguir siendo linealmente independientes, o equivalentemente, que el mapa${\displaystyle w=(w_{A},w_{B})\mapsto f}$es uno a uno. Las funciones en el espacio${\displaystyle H}$puede verse como la suma de dos componentes, uno en el espacio${\displaystyle H_{A}}$, las combinaciones lineales de átomos en ${\displaystyle A}$y uno en${\displaystyle H_{B}}$, las combinaciones lineales de los átomos en${\displaystyle B}$.

Una opción de norma en este espacio es${\displaystyle ||f||=||w_{A}||+||w_{B}||}$. Tenga en cuenta que ahora podemos ver${\displaystyle H}$como un espacio de funciones en el que ${\displaystyle H_{A}}$, ${\displaystyle H_{B}}$son subespacios. En vista del supuesto de independencia lineal,${\displaystyle H}$puede identificarse con${\displaystyle \mathbb {R} ^{p+q}}$y${\displaystyle H_{A},H_{B}}$con${\displaystyle \mathbb {R} ^{p},\mathbb {R} ^{q}}$respectivamente. La norma mencionada anteriormente puede considerarse como la norma del grupo en ${\displaystyle H}$asociados a los subespacios ${\displaystyle H_{A}}$, ${\displaystyle H_{B}}$, proporcionando una conexión con la regularización de escasez estructurada.

Aquí,${\displaystyle H_{A}}$, ${\displaystyle H_{B}}$y${\displaystyle H}$Se puede observar que son los espacios de Hilbert del núcleo reproductor con mapas de características correspondientes.${\displaystyle \Phi _{A}:X\rightarrow \mathbb {R} ^{p}}$, dado por${\displaystyle \Phi _{A}(x)=(a_{1}(x),...,a_{p}(x))}$,${\displaystyle \Phi _{B}:X\rightarrow \mathbb {R} ^{q}}$, dado por${\displaystyle \Phi _{B}(x)=(b_{1}(x),...,b_{q}(x))}$, y${\displaystyle \Phi :X\rightarrow \mathbb {R} ^{p+q}}$, dado por la concatenación de${\displaystyle \Phi _{A},\Phi _{B}}$, respectivamente.

En el enfoque de regularización de escasez estructurada para este escenario, los grupos relevantes de variables que consideran las normas de grupo corresponden a los subespacios${\displaystyle H_{A}}$y${\displaystyle H_{B}}$Este enfoque promueve establecer a cero los grupos de coeficientes correspondientes a estos subespacios en lugar de solo los coeficientes individuales, lo que promueve el aprendizaje de múltiples núcleos dispersos.

El razonamiento anterior se generaliza directamente a cualquier número finito de diccionarios o mapas de características. Puede extenderse a mapas de características que inducen hipótesis de dimensión infinita.

espacios. ^{[ 16 ]}