Complejidad de Rademacher

Medida de complejidad de funciones de valor real.

En la teoría del aprendizaje computacional ( aprendizaje automático y teoría de la computación ), la complejidad de Rademacher , que lleva el nombre de Hans Rademacher , mide la riqueza de una clase de conjuntos con respecto a una distribución de probabilidad . El concepto también puede extenderse a funciones de valor real.

Definiciones

Complejidad de Rademacher de un conjunto.

Dado un conjunto , la complejidad de Rademacher de A se define de la siguiente manera: ^{[1] [2] : 326} ${\displaystyle A\subseteq \mathbb {R} ^{m}}$

${\displaystyle \operatorname {Rad} (A):={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{a\in A}\sum _{i=1}^{m}\sigma _{i}a_{i}\right]}$

donde son variables aleatorias independientes extraídas de la distribución de Rademacher , es decir, para , y . Algunos autores toman el valor absoluto de la suma antes de tomar el supremo, pero si es simétrico esto no hace diferencia. ${\displaystyle \sigma _{1},\sigma _{2},\dots ,\sigma _{m}}$ ${\displaystyle \Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1)=1/2}$ ${\displaystyle i=1,2,\dots ,m}$ ${\displaystyle a=(a_{1},\ldots ,a_{m})}$ ${\displaystyle A}$

Complejidad de Rademacher de una clase de función

Sea una muestra de puntos y considere una clase de función de funciones de valor real sobre . Entonces, la complejidad empírica de Rademacher dada se define como: ${\displaystyle S=\{z_{1},z_{2},\dots ,z_{m}\}\subset Z}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle Z}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle S}$

${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}})={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{f\in {\mathcal {F}}}\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right]}$

Esto también se puede escribir usando la definición anterior: ^{[2] : 326}

${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}})=\operatorname {Rad} ({\mathcal {F}}\circ S)}$

donde denota composición de funciones , es decir: ${\displaystyle {\mathcal {F}}\circ S}$

${\displaystyle {\mathcal {F}}\circ S:=\{(f(z_{1}),\ldots ,f(z_{m}))\mid f\in {\mathcal {F}}\}}$

Sea una distribución de probabilidad sobre . La complejidad de Rademacher de la clase de función con respecto al tamaño de la muestra es: ${\displaystyle P}$ ${\displaystyle Z}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P}$ ${\displaystyle m}$

${\displaystyle \operatorname {Rad} _{P,m}({\mathcal {F}}):=\mathbb {E} _{S\sim P^{m}}\left[\operatorname {Rad} _{S}({\mathcal {F}})\right]}$

donde la expectativa anterior se toma sobre una muestra idénticamente distribuida independientemente (iid) generada de acuerdo con . ${\displaystyle S=(z_{1},z_{2},\dots ,z_{m})}$ ${\displaystyle P}$

Intuición

La complejidad de Rademacher se aplica normalmente a una clase de función de modelos que se utilizan para la clasificación, con el objetivo de medir su capacidad para clasificar puntos extraídos de un espacio de probabilidad bajo etiquetas arbitrarias. Cuando la clase de función es lo suficientemente rica, contiene funciones que pueden adaptarse adecuadamente a cada disposición de etiquetas, simuladas mediante el sorteo aleatorio bajo la expectativa, de modo que esta cantidad en la suma se maximice. ${\displaystyle \sigma _{i}}$

Ejemplos

1. contiene un único vector, por ejemplo, . Entonces: ${\displaystyle A}$ ${\displaystyle A=\{(a,b)\}\subset \mathbb {R} ^{2}}$

${\displaystyle \operatorname {Rad} (A)={1 \over 2}\cdot \left({1 \over 4}\cdot (a+b)+{1 \over 4}\cdot (a-b)+{1 \over 4}\cdot (-a+b)+{1 \over 4}\cdot (-a-b)\right)=0}$

Lo mismo ocurre con cada clase de hipótesis singleton. ^{[3] : 56}

2. contiene dos vectores, por ejemplo, . Entonces: ${\displaystyle A}$ ${\displaystyle A=\{(1,1),(1,2)\}\subset \mathbb {R} ^{2}}$

${\displaystyle {\begin{aligned}\operatorname {Rad} (A)&={1 \over 2}\cdot \left({1 \over 4}\cdot \max(1+1,1+2)+{1 \over 4}\cdot \max(1-1,1-2)+{1 \over 4}\cdot \max(-1+1,-1+2)+{1 \over 4}\cdot \max(-1-1,-1-2)\right)\\[5pt]&={1 \over 8}(3+0+1-2)={1 \over 4}\end{aligned}}}$

Usando la complejidad de Rademacher

La complejidad de Rademacher se puede utilizar para derivar límites superiores dependientes de los datos sobre la capacidad de aprendizaje de las clases de funciones. Intuitivamente, una clase de función con menor complejidad Rademacher es más fácil de aprender.

Limitando la representatividad

En el aprendizaje automático , se desea tener un conjunto de entrenamiento que represente la distribución real de algunos datos de muestra . Esto puede cuantificarse utilizando la noción de representatividad . Denota por la distribución de probabilidad de la que se extraen las muestras. Denote por el conjunto de hipótesis (clasificadores potenciales) y denote por el conjunto correspondiente de funciones de error, es decir, para cada hipótesis , hay una función que asigna cada muestra de entrenamiento (características, etiqueta) al error del clasificador (nota en En este caso, la hipótesis y el clasificador se utilizan indistintamente). Por ejemplo, en el caso que representa un clasificador binario, la función de error es una función de pérdida 0-1, es decir, la función de error devuelve 0 si clasifica correctamente una muestra y 1 en caso contrario. Omitimos el índice y escribimos en lugar de cuando la hipótesis subyacente es irrelevante. Definir: ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle h\in H}$ ${\displaystyle f_{h}\in F}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle f_{h}}$ ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle f_{h}}$

${\displaystyle L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]}$– el error esperado de alguna función de error en la distribución real ; ${\displaystyle f\in F}$ ${\displaystyle P}$

${\displaystyle L_{S}(f):={1 \over m}\sum _{i=1}^{m}f(z_{i})}$– el error estimado de alguna función de error en la muestra . ${\displaystyle f\in F}$ ${\displaystyle S}$

La representatividad de la muestra , respecto de y , se define como: ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle F}$

${\displaystyle \operatorname {Rep} _{P}(F,S):=\sup _{f\in F}(L_{P}(f)-L_{S}(f))}$

Una representatividad más pequeña es mejor, ya que proporciona una manera de evitar el sobreajuste : significa que el error verdadero de un clasificador no es mucho mayor que su error estimado, por lo que seleccionar un clasificador que tenga un error estimado bajo garantizará que el error verdadero también lo sea. bajo. Sin embargo, tenga en cuenta que el concepto de representatividad es relativo y, por lo tanto, no se puede comparar entre muestras distintas.

La representatividad esperada de una muestra puede estar limitada por la complejidad de Rademacher de la clase de función: ^{[2] : 326}

$${\displaystyle \mathbb {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}(F,S)]\leq 2\cdot \mathbb {E} _{S\sim P^{m}}[\operatorname {Rad} (F\circ S)]}$$

Limitando el error de generalización

Cuando la complejidad de Rademacher es pequeña, es posible aprender la clase de hipótesis H utilizando la minimización empírica del riesgo .

Por ejemplo, (con función de error binario), ^{[2] : 328} para cada , con probabilidad al menos , para cada hipótesis : ${\displaystyle \delta >0}$ ${\displaystyle 1-\delta }$ ${\displaystyle h\in H}$

${\displaystyle L_{P}(h)-L_{S}(h)\leq 2\operatorname {Rad} (F\circ S)+4{\sqrt {2\ln(4/\delta ) \over m}}}$

Limitando la complejidad de Rademacher

Dado que una menor complejidad de Rademacher es mejor, es útil tener límites superiores en la complejidad de Rademacher de varios conjuntos de funciones. Las siguientes reglas se pueden utilizar para limitar la complejidad de Rademacher de un conjunto . ^{[2] : 329–330} ${\displaystyle A\subset \mathbb {R} ^{m}}$

1. Si todos los vectores en se traducen por un vector constante , entonces Rad( A ) no cambia. ${\displaystyle A}$ ${\displaystyle a_{0}\in \mathbb {R} ^{m}}$

2. Si todos los vectores se multiplican por un escalar , entonces Rad( A ) se multiplica por . ${\displaystyle A}$ ${\displaystyle c\in \mathbb {R} }$ ${\displaystyle |c|}$

3. . ^{[3] : 56} ${\displaystyle \operatorname {Rad} (A+B)=\operatorname {Rad} (A)+\operatorname {Rad} (B)}$

4. (Kakade y Tewari Lemma) Si todos los vectores son operados por una función de Lipschitz , entonces Rad( A ) se multiplica (como máximo) por la constante de Lipschitz de la función. En particular, si todos los vectores son operados mediante un mapeo de contracción , entonces Rad( A ) disminuye estrictamente. ${\displaystyle A}$ ${\displaystyle A}$

5. La complejidad de Rademacher del casco convexo de igual Rad( A ). ${\displaystyle A}$

6. (Massart Lemma) La complejidad de Rademacher de un conjunto finito crece logarítmicamente con el tamaño del conjunto. Formalmente, sea un conjunto de vectores en , y sea la media de los vectores en . Entonces: ${\displaystyle A}$ ${\displaystyle N}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle {\bar {a}}}$ ${\displaystyle A}$

${\displaystyle \operatorname {Rad} (A)\leq \max _{a\in A}\|a-{\bar {a}}\|\cdot {{\sqrt {2\log N}} \over m}}$

En particular, si es un conjunto de vectores binarios, la norma es como máximo , entonces: ${\displaystyle A}$ ${\displaystyle {\sqrt {m}}}$

${\displaystyle \operatorname {Rad} (A)\leq {\sqrt {2\log N \over m}}}$

Límites relacionados con la dimensión VC

Sea una familia de conjuntos cuya dimensión VC es . Se sabe que la función de crecimiento de está acotada como: ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle H}$

para todos : ${\displaystyle m>d+1}$ ${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}}$

Esto significa que, por cada conjunto con como máximo elementos, . La familia de conjuntos se puede considerar como un conjunto de vectores binarios sobre . Sustituyendo esto en el lema de Massart se obtiene: ${\displaystyle h}$ ${\displaystyle m}$ ${\displaystyle |H\cap h|\leq (em/d)^{d}}$ ${\displaystyle H\cap h}$ ${\displaystyle \mathbb {R} ^{m}}$

${\displaystyle \operatorname {Rad} (H\cap h)\leq {\sqrt {2d\log(em/d) \over m}}}$

Con técnicas más avanzadas ( límite de entropía de Dudley y límite superior de Haussler ^[4] ) se puede demostrar, por ejemplo, que existe una constante , de modo que cualquier clase de funciones indicadoras con dimensión de Vapnik-Chervonenkis tiene una complejidad de Rademacher limitada por . ${\displaystyle C}$ ${\displaystyle \{0,1\}}$ ${\displaystyle d}$ ${\displaystyle C{\sqrt {\frac {d}{m}}}}$

Límites relacionados con clases lineales.

Los siguientes límites están relacionados con operaciones lineales en – un conjunto constante de vectores en . ^{[2] : 332–333} ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle \mathbb {R} ^{n}}$

1. Defina el conjunto de productos escalares de los vectores con vectores en la bola unitaria . Entonces: ${\displaystyle A_{2}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{2}\leq 1\}=}$ ${\displaystyle S}$

${\displaystyle \operatorname {Rad} (A_{2})\leq {\max _{i}\|x_{i}\|_{2} \over {\sqrt {m}}}}$

2. Defina el conjunto de productos escalares de los vectores con vectores en la bola unitaria de la norma 1. Entonces: ${\displaystyle A_{1}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{1}\leq 1\}=}$ ${\displaystyle S}$

${\displaystyle \operatorname {Rad} (A_{1})\leq \max _{i}\|x_{i}\|_{\infty }\cdot {\sqrt {2\log(2n) \over m}}}$

Límites relacionados con los números de cobertura

El siguiente límite relaciona la complejidad de Rademacher de un conjunto con su número de cobertura externa : el número de bolas de un radio dado cuya unión contiene . El límite se atribuye a Dudley. ^{[2] : 338} ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle A}$

Supongamos que es un conjunto de vectores cuya longitud (norma) es como máximo . Entonces, para cada número entero : ${\displaystyle A\subset \mathbb {R} ^{m}}$ ${\displaystyle c}$ ${\displaystyle M>0}$

${\displaystyle \operatorname {Rad} (A)\leq {c\cdot 2^{-M} \over {\sqrt {m}}}+{6c \over m}\cdot \sum _{i=1}^{M}2^{-i}{\sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\right)}}}$

En particular, si se encuentra en un subespacio d -dimensional de , entonces: ${\displaystyle A}$ ${\displaystyle \mathbb {R} ^{m}}$

${\displaystyle \forall r>0:N_{r}^{\text{ext}}(A)\leq (2c{\sqrt {d}}/r)^{d}}$

Sustituyendo esto en el límite anterior se obtiene el siguiente límite en la complejidad de Rademacher:

${\displaystyle \operatorname {Rad} (A)\leq {6c \over m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (}{c{\sqrt {d\log(d)}} \over m}{\bigg )}}$

Complejidad gaussiana

La complejidad gaussiana es una complejidad similar con significados físicos similares, y se puede obtener a partir de la complejidad de Rademacher usando variables aleatorias en lugar de , donde están las variables aleatorias gaussianas i.id con media cero y varianza 1, es decir . Se sabe que las complejidades gaussianas y de Rademacher son equivalentes hasta factores logarítmicos. ${\displaystyle g_{i}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle g_{i}}$ ${\displaystyle g_{i}\sim {\mathcal {N}}(0,1)}$

Equivalencia de Rademacher y complejidad gaussiana

Dado un conjunto, entonces se cumple que ^[5] : ¿Dónde está la complejidad gaussiana de A? Como ejemplo, considere las complejidades rademacher y gaussiana de la bola L1. La complejidad de Rademacher está dada por exactamente 1, mientras que la complejidad gaussiana es del orden de (lo que puede demostrarse aplicando propiedades conocidas de suprema de un conjunto de variables aleatorias subgaussianas ). ^[5] ${\displaystyle A\subseteq \mathbb {R} ^{n}}$
${\displaystyle {\frac {G(A)}{2{\sqrt {\log {n}}}}}\leq {\text{Rad}}(A)\leq {\sqrt {\frac {\pi }{2}}}G(A)}$
${\displaystyle G(A)}$ ${\displaystyle {\sqrt {\log d}}}$

Referencias

1. Balcan, Maria-Florina (15 al 17 de noviembre de 2011). "Teoría del aprendizaje automático: complejidad de Rademacher" (PDF) . Consultado el 10 de diciembre de 2016 .
2. Capítulo 26 en Shalev-Shwartz, Shai; Ben-David, Shai (2014). Comprender el aprendizaje automático: de la teoría a los algoritmos . Prensa de la Universidad de Cambridge. ISBN 9781107057135.
3. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
4. Bousquet, O. (2004). Introducción a la teoría del aprendizaje estadístico. Cibernética biológica , 3176 (1), 169–207. doi :10.1007/978-3-540-28650-9_8
5. Wainwright, Martín (2019). Estadísticas de alta dimensión: un punto de vista no asintótico. Cambridge, Reino Unido. págs. Ejercicio 5.5. ISBN 978-1-108-62777-1. OCLC  1089254580.{{cite book}}: CS1 maint: location missing publisher (link)

• Peter L. Bartlett, Shahar Mendelson (2002) Rademacher y las complejidades gaussianas: límites de riesgo y resultados estructurales . Revista de investigación sobre aprendizaje automático 3 463–482
• Giorgio Gnecco, Marcello Sanguineti (2008) Límites de error de aproximación mediante la complejidad de Rademacher . Ciencias Matemáticas Aplicadas, vol. 2, 2008, núm. 4, 153-176