Teorema del representante

Para la ciencia de la computación , en la teoría del aprendizaje estadístico , un teorema de representación es cualquiera de varios resultados relacionados que establecen que un minimizador de una función de riesgo empírica regularizada definida sobre un espacio de Hilbert de kernel de reproducción se puede representar como una combinación lineal finita de productos de kernel evaluados en los puntos de entrada en los datos del conjunto de entrenamiento. ${\estilo de visualización f^{*}}$

El siguiente Teorema del Representante y su demostración se deben a Schölkopf , Herbrich y Smola: ^[1]

Teorema: Considérese un núcleo de valor real definido positivo en un conjunto no vacío con un espacio de Hilbert de núcleo reproductor correspondiente . Sea ${\displaystyle k:{\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$${\displaystyle {\mathcal {X}}}$$Estilo de visualización {\displaystyle H_{k}}$

• una muestra de entrenamiento ,${\displaystyle (x_{1},y_{1}),\dotsc ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R} }$
• una función de valor real estrictamente creciente , y${\displaystyle g\colon [0,\infty )\to \mathbb {R} }$
• una función de error arbitraria ,${\displaystyle E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{n}\to \mathbb {R} \cup \lbrace \infty \rbrace }$

que en conjunto definen la siguiente función de riesgo empírica regularizada en : ${\displaystyle H_{k}}$

${\displaystyle f\mapsto E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right).}$

Entonces, cualquier minimizador del riesgo empírico

${\displaystyle f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right)\right\rbrace ,\quad (*)}$

admite una representación de la forma:

${\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),}$

donde para todos . ${\displaystyle \alpha _{i}\in \mathbb {R} }$${\displaystyle 1\leq i\leq n}$

Prueba: Definir una asignación

${\displaystyle {\begin{aligned}\varphi \colon {\mathcal {X}}&\to H_{k}\\\varphi (x)&=k(\cdot ,x)\end{aligned}}}$

(por lo que es en sí mismo un mapa ). Dado que es un núcleo reproductor, entonces ${\displaystyle \varphi (x)=k(\cdot ,x)}$${\displaystyle {\mathcal {X}}\to \mathbb {R} }$${\displaystyle k}$

${\displaystyle \varphi (x)(x')=k(x',x)=\langle \varphi (x'),\varphi (x)\rangle ,}$

¿Dónde está el producto interno en ? ${\displaystyle \langle \cdot ,\cdot \rangle }$${\displaystyle H_{k}}$

Dado cualquier , se puede utilizar la proyección ortogonal para descomponer cualquier en una suma de dos funciones, una que se encuentra en , y la otra que se encuentra en el complemento ortogonal: ${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle f\in H_{k}}$${\displaystyle \operatorname {span} \left\lbrace \varphi (x_{1}),\ldots ,\varphi (x_{n})\right\rbrace }$

${\displaystyle f=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,}$

donde para todos . ${\displaystyle \langle v,\varphi (x_{i})\rangle =0}$${\displaystyle i}$

La descomposición ortogonal anterior y la propiedad de reproducción juntas muestran que la aplicación a cualquier punto de entrenamiento produce ${\displaystyle f}$${\displaystyle x_{j}}$

${\displaystyle f(x_{j})=\left\langle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,\varphi (x_{j})\right\rangle =\sum _{i=1}^{n}\alpha _{i}\langle \varphi (x_{i}),\varphi (x_{j})\rangle ,}$

que observamos es independiente de . En consecuencia, el valor de la función de error en (*) es igualmente independiente de . Para el segundo término (el término de regularización), ya que es ortogonal a y es estrictamente monótono, tenemos ${\displaystyle v}$${\displaystyle E}$${\displaystyle v}$${\displaystyle v}$${\displaystyle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})}$${\displaystyle g}$

${\displaystyle {\begin{aligned}g\left(\lVert f\rVert \right)&=g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v\rVert \right)\\&=g\left({\sqrt {\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert ^{2}+\lVert v\rVert ^{2}}}\right)\\&\geq g\left(\lVert \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})\rVert \right).\end{aligned}}}$

Por lo tanto, la configuración no afecta al primer término de (*), mientras que disminuye estrictamente el segundo término. En consecuencia, cualquier minimizador en (*) debe tener , es decir, debe tener la forma ${\displaystyle v=0}$${\displaystyle f^{*}}$${\displaystyle v=0}$

${\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),}$

Cuál es el resultado deseado.

El teorema enunciado anteriormente es un ejemplo particular de una familia de resultados que se denominan colectivamente "teoremas del representante"; aquí describimos varios de ellos.

El primer enunciado de un teorema de representación se debió a Kimeldorf y Wahba para el caso especial en el que

${\displaystyle {\begin{aligned}E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)&={\frac {1}{n}}\sum _{i=1}^{n}(f(x_{i})-y_{i})^{2},\\g(\lVert f\rVert )&=\lambda \lVert f\rVert ^{2}\end{aligned}}}$

Schölkopf, Herbrich y Smola generalizaron este resultado relajando el supuesto del costo de pérdida al cuadrado y permitiendo que el regularizador sea cualquier función estrictamente monótonamente creciente de la norma del espacio de Hilbert. ${\displaystyle \lambda >0}$${\displaystyle g(\cdot )}$

Es posible generalizar aún más aumentando el riesgo empírico regularizado funcional mediante la adición de términos de compensación no penalizados. Por ejemplo, Schölkopf, Herbrich y Smola también consideran la minimización

${\displaystyle {\tilde {f}}^{*}=\operatorname {argmin} \left\lbrace E\left((x_{1},y_{1},{\tilde {f}}(x_{1})),\ldots ,(x_{n},y_{n},{\tilde {f}}(x_{n}))\right)+g\left(\lVert f\rVert \right)\mid {\tilde {f}}=f+h\in H_{k}\oplus \operatorname {span} \lbrace \psi _{p}\mid 1\leq p\leq M\rbrace \right\rbrace ,\quad (\dagger )}$

es decir, consideramos funciones de la forma , donde y es una función no penalizada que se encuentra en el espacio comprendido entre un conjunto finito de funciones de valor real . Suponiendo que la matriz tiene rango , demuestran que el minimizador en admite una representación de la forma ${\displaystyle {\tilde {f}}=f+h}$${\displaystyle f\in H_{k}}$${\displaystyle h}$${\displaystyle \lbrace \psi _{p}\colon {\mathcal {X}}\to \mathbb {R} \mid 1\leq p\leq M\rbrace }$${\displaystyle n\times M}$${\displaystyle \left(\psi _{p}(x_{i})\right)_{ip}}$${\displaystyle M}$${\displaystyle {\tilde {f}}^{*}}$${\displaystyle (\dagger )}$

${\displaystyle {\tilde {f}}^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i})+\sum _{p=1}^{M}\beta _{p}\psi _{p}(\cdot )}$

Dónde y el están todos determinados de forma única. ${\displaystyle \alpha _{i},\beta _{p}\in \mathbb {R} }$${\displaystyle \beta _{p}}$

Las condiciones bajo las cuales existe un teorema del representador fueron investigadas por Argyriou, Micchelli y Pontil, quienes demostraron lo siguiente:

Teorema: Sea un conjunto no vacío, un núcleo de valor real definido positivo en con un espacio de Hilbert de núcleo reproductor correspondiente y sea una función de regularización diferenciable. Entonces, dada una muestra de entrenamiento y una función de error arbitraria , un minimizador ${\displaystyle {\mathcal {X}}}$${\displaystyle k}$${\displaystyle {\mathcal {X}}\times {\mathcal {X}}}$${\displaystyle H_{k}}$${\displaystyle R\colon H_{k}\to \mathbb {R} }$${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R} }$${\displaystyle E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{m}\to \mathbb {R} \cup \lbrace \infty \rbrace }$

${\displaystyle f^{*}={\underset {f\in H_{k}}{\operatorname {argmin} }}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),\ldots ,(x_{n},y_{n},f(x_{n}))\right)+R(f)\right\rbrace \quad (\ddagger )}$

del riesgo empírico regularizado admite una representación de la forma

${\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\alpha _{i}k(\cdot ,x_{i}),}$

donde para todo , si y sólo si existe una función no decreciente para la cual ${\displaystyle \alpha _{i}\in \mathbb {R} }$${\displaystyle 1\leq i\leq n}$${\displaystyle h\colon [0,\infty )\to \mathbb {R} }$

${\displaystyle R(f)=h(\lVert f\rVert ).}$

En efecto, este resultado proporciona una condición necesaria y suficiente para un regularizador diferenciable bajo la cual la minimización del riesgo empírico regularizado correspondiente tendrá un teorema de representante. En particular, esto muestra que una amplia clase de minimizaciones del riesgo regularizado (mucho más amplias que las consideradas originalmente por Kimeldorf y Wahba) tienen teoremas de representante. ${\displaystyle R(\cdot )}$${\displaystyle (\ddagger )}$

Los teoremas de representación son útiles desde un punto de vista práctico porque simplifican drásticamente el problema de minimización de riesgo empírico regularizado . En la mayoría de las aplicaciones interesantes, el dominio de búsqueda para la minimización será un subespacio de dimensión infinita de , y por lo tanto la búsqueda (tal como está escrita) no admite implementación en computadoras de memoria finita y precisión finita. En contraste, la representación de proporcionada por un teorema de representación reduce el problema de minimización original (de dimensión infinita) a una búsqueda del vector de dimensión óptima de coeficientes ; luego se puede obtener aplicando cualquier algoritmo de minimización de funciones estándar. En consecuencia, los teoremas de representación proporcionan la base teórica para la reducción del problema general de aprendizaje automático a algoritmos que realmente se pueden implementar en computadoras en la práctica. ${\displaystyle (\ddagger )}$${\displaystyle H_{k}}$${\displaystyle L^{2}({\mathcal {X}})}$${\displaystyle f^{*}(\cdot )}$${\displaystyle n}$${\displaystyle \alpha =(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {R} ^{n}}$${\displaystyle \alpha }$

A continuación se ofrece un ejemplo de cómo resolver el minimizador cuya existencia está garantizada por el teorema del representador. Este método funciona para cualquier núcleo definido positivo y nos permite transformar un problema de optimización complicado (posiblemente de dimensión infinita) en un sistema lineal simple que se puede resolver numéricamente. ${\displaystyle K}$

Supongamos que estamos utilizando una función de error de mínimos cuadrados

${\displaystyle E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]:=\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}$

y una función de regularización para algún . Por el teorema del representador, el minimizador ${\displaystyle g(x)=\lambda x^{2}}$${\displaystyle \lambda >0}$

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}{\Big \{}E[(x_{1},y_{1},f(x_{1})),\dots ,(x_{n},y_{n},f(x_{n}))]+g(\|f\|_{\mathcal {H}}){\Big \}}={\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}}$

tiene la forma

${\displaystyle f^{*}(x)=\sum _{i=1}^{n}\alpha _{i}^{*}k(x,x_{i})}$

Para algunos . Observando que ${\displaystyle \alpha ^{*}=(\alpha _{1}^{*},\dots ,\alpha _{n}^{*})\in \mathbb {R} ^{n}}$

${\displaystyle \|f\|_{\mathcal {H}}^{2}={\Big \langle }\sum _{i=1}^{n}\alpha _{i}^{*}k(\cdot ,x_{i}),\sum _{j=1}^{n}\alpha _{j}^{*}k(\cdot ,x_{j}){\Big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}{\big \langle }k(\cdot ,x_{i}),k(\cdot ,x_{j}){\big \rangle }_{\mathcal {H}}=\sum _{i=1}^{n}\sum _{j=1}^{n}\alpha _{i}^{*}\alpha _{j}^{*}k(x_{i},x_{j}),}$

vemos que tiene la forma ${\displaystyle \alpha ^{*}}$

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\sum _{i=1}^{n}\left(y_{i}-\sum _{j=1}^{n}\alpha _{j}k(x_{i},x_{j})\right)^{2}+\lambda \|f\|_{\mathcal {H}}^{2}\right\}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\|y-A\alpha \|^{2}+\lambda \alpha ^{\intercal }A\alpha \right\}.}$

donde y . Esto se puede factorizar y simplificar a ${\displaystyle A_{ij}=k(x_{i},x_{j})}$${\displaystyle y=(y_{1},\dots ,y_{n})}$

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbb {R} ^{n}}{\operatorname {argmin} }}\left\{\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }A^{\intercal }y\right\}.}$

Como es definida positiva, de hecho hay un único mínimo global para esta expresión. Sea y observe que es convexa. Entonces , el mínimo global, se puede resolver haciendo . Recordando que todas las matrices definidas positivas son invertibles, vemos que ${\displaystyle A^{\intercal }A+\lambda A}$${\displaystyle F(\alpha )=\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }A^{\intercal }y}$${\displaystyle F}$${\displaystyle \alpha ^{*}}$${\displaystyle \nabla _{\alpha }F=0}$

${\displaystyle \nabla _{\alpha }F=2(A^{\intercal }A+\lambda A)\alpha ^{*}-2A^{\intercal }y=0\Longrightarrow \alpha ^{*}=(A^{\intercal }A+\lambda A)^{-1}A^{\intercal }y,}$

Por lo tanto, el minimizador se puede encontrar mediante una solución lineal.

• Teorema de Mercer
• Métodos del núcleo

• Argyriou, Andreas; Micchelli, Charles A.; Pontil, Massimiliano (2009). "¿Cuándo existe un teorema de representación? Regularizadores vectoriales frente a regularizadores matriciales". Journal of Machine Learning Research . 10 (diciembre): 2507– 2529.
• Cucker, Felipe; Smale, Steve (2002). "Sobre los fundamentos matemáticos del aprendizaje". Boletín de la American Mathematical Society . 39 (1): 1– 49. doi : 10.1090/S0273-0979-01-00923-5 . MR  1864085.
• Kimeldorf, George S.; Wahba, Grace (1970). "Una correspondencia entre la estimación bayesiana en procesos estocásticos y el suavizado por splines". Anales de estadística matemática . 41 (2): 495– 502. doi : 10.1214/aoms/1177697089 .
• Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). "Un teorema de representante generalizado". Computational Learning Theory . Lecture Notes in Computer Science. Vol. 2111. págs.  416– 426. CiteSeerX  10.1.1.42.8617 . doi :10.1007/3-540-44581-1_27. ISBN . 978-3-540-42343-0.