Complejidad de Rademacher

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

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

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

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

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

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

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

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

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

La complejidad empírica de Rademacher en el peor de los casos es$${\displaystyle {\overline {\operatorname {Rad} }}_{m}({\mathcal {F}})=\sup _{S=\{z_{1},\dots ,z_{m}\}}\operatorname {Rad} _{S}({\mathcal {F}})}$$Dejar${\displaystyle P}$sea ​​una distribución de probabilidad sobre${\displaystyle Z}$. La complejidad de Rademacher de la clase de función${\displaystyle {\mathcal {F}}}$con respecto a${\displaystyle P}$para el tamaño de la muestra${\displaystyle m}$es:

${\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 de forma independiente (iid)${\displaystyle S=(z_{1},z_{2},\dots,z_{m})}$generado según${\displaystyle P}$.

En el aprendizaje automático , se desea tener un conjunto de entrenamiento que represente la distribución real de algunos datos de muestra.${\displaystyle S}$Esto puede cuantificarse utilizando la noción de representatividad . Denotemos por${\displaystyle P}$la distribución de probabilidad de la cual se extraen las muestras. Denotemos por${\displaystyle H}$el conjunto de hipótesis (clasificadores potenciales) y denotamos por${\displaystyle {\mathcal {F}}}$el conjunto correspondiente de funciones de error, es decir, para cada hipótesis${\displaystyle h\in H}$, hay una función${\displaystyle f_{h}\in F}$que asigna a cada muestra de entrenamiento (características, etiqueta) el error del clasificador${\displaystyle h}$(tenga en cuenta que en este caso, hipótesis y clasificador se usan indistintamente). Por ejemplo, en el caso de que${\displaystyle h}$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${\displaystyle f_{h}}$devuelve 0 si${\displaystyle h}$clasifica correctamente una muestra y 1 en caso contrario. Omitimos el índice y escribimos${\displaystyle f}$en lugar de${\displaystyle f_{h}}$cuando la hipótesis subyacente es irrelevante. Definir:

${\displaystyle L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]}$– el error esperado de alguna función de error${\displaystyle f\in {\mathcal {F}}}$sobre la distribución real${\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${\displaystyle f\in {\mathcal {F}}}$en la muestra${\displaystyle S}$.

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

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

Una menor representatividad es preferible, ya que permite evitar el sobreajuste : esto significa que el error real de un clasificador no es mucho mayor que su error estimado, por lo que seleccionar un clasificador con un error estimado bajo garantiza que el error real también sea bajo. Sin embargo, cabe señalar 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 superiormente por la complejidad de Rademacher de la clase de función: Si${\displaystyle {\mathcal {F}}}$es un conjunto de funciones con rango dentro${\displaystyle [0,1]}$, entonces ^{[ 2 ] : 326 [ 4 ]}

$${\displaystyle \operatorname {Rad} _{P,m}({\mathcal {F}})-{\sqrt {\frac {\ln 2}{2m}}}\leq \mathbb {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}({\mathcal {F}},S)]\leq 2\operatorname {Rad} _{P,m}({\mathcal {F}})}$$

Además, la representatividad se concentra en torno a su expectativa: ^{[ 4 ]} Para cualquier${\displaystyle \epsilon }$, con probabilidad${\displaystyle \geq 1-2e^{-2\epsilon ^{2}m}}$,$${\displaystyle \operatorname {Rep} _{P}({\mathcal {F}},S)\in \mathbb {E} _{S\sim P^{m}}[\operatorname {Rep} _{P}({\mathcal {F}},S)]\pm \epsilon }$$

La complejidad de Rademacher es una justificación teórica para la minimización empírica del riesgo .

Cuando la función de error es binaria (pérdida 0-1), para cada${\displaystyle \delta >0}$,

${\displaystyle \sup _{f\in {\mathcal {F}}}(L_{P}(f)-L_{S}(f))\leq 2\operatorname {Rad} _{S}({\mathcal {F}})+4{\sqrt {2\ln(4/\delta ) \over m}}}$

con probabilidad al menos${\displaystyle 1-\delta }$. ^{[ 2 ] : 328}

Existe una constante${\displaystyle c>0}$, de tal manera que cuando la función de error se eleva al cuadrado${\displaystyle \ell ({\hat {y}},y):=({\hat {y}}-y)^{2}}$y la clase de función${\displaystyle {\mathcal {F}}}$consta de funciones con rango dentro${\displaystyle [-1,+1]}$, entonces para cualquier${\displaystyle \delta >0}$$${\displaystyle L_{P}(f)-L_{S}(f)\leq c\left[L_{S}(f)+(\ln m)^{4}{\overline {\operatorname {Rad} }}_{m}({\mathcal {F}})^{2}+{\frac {\ln(1/\delta )}{m}}\right],\quad \forall f\in {\mathcal {F}}}$$con probabilidad al menos${\displaystyle 1-\delta }$. ^{[ 4 ] : Teorema 2.2}

Dejemos que el riesgo bayesiano${\displaystyle L^{*}=\inf _{f}L_{P}(f)}$, dónde${\displaystyle f}$puede ser cualquier función medible .

Dejemos la clase de función${\displaystyle {\mathcal {F}}}$dividirse en "clases de complejidad"${\displaystyle {\mathcal {F}}_{r}}$, dónde${\displaystyle r\in \mathbb {R} }$son niveles de complejidad. Deje${\displaystyle p_{r}}$sean números reales. Sea la función de medida de complejidad.${\displaystyle p}$ser definido de tal manera que${\displaystyle p(f):=\min\{p_{r}:f\in {\mathcal {F}}_{r}\}}$.

Para cualquier conjunto de datos${\displaystyle S}$, dejar${\displaystyle {\hat {f}}}$ser un minimizador de${\displaystyle L_{S}(f)+p(f)}$. Si$${\displaystyle \sup _{f\in {\mathcal {F}}_{r}}|L_{P}(f)-L_{S}(f)|\leq p_{r},\quad \forall r}$$Entonces tenemos la desigualdad del oráculo.$${\displaystyle L({\hat {f}})-L^{*}\leq \inf _{r}\left(\inf _{f\in {\mathcal {F}}_{r}}L(f)-L^{*}+2p_{r}\right)}$$Definir${\displaystyle f_{r}^{*}\in \arg \min _{f\in {\mathcal {F}}_{r}}L(f)}$Si además asumimos$${\displaystyle r\leq s{\text{ implies }}{\mathcal {F}}_{r}\subseteq {\mathcal {F}}_{s}{\text{ and }}p_{r}\leq p_{s}}$$y$${\displaystyle {\begin{aligned}\forall r,\sup _{f\in {\mathcal {F}}_{r}}\left(L_{P}(f)-L_{P}\left(f_{r}^{*}\right)-2\left(L_{S}(f)-L_{S}\left(f_{r}^{*}\right)\right)\right)&\leq 2p_{r}/7\\\sup _{f\in {\mathcal {F}}_{r}}\left(L_{S}(f)-L_{S}\left(f_{r}^{*}\right)-2\left(L_{P}(f)-L_{P}\left(f_{r}^{*}\right)\right)\right)&\leq 2p_{r}/7\end{aligned}}}$$Entonces tenemos la desigualdad del oráculo.$${\displaystyle L_{P}({\widehat {f}})-L^{*}\leq \inf _{r}\left(\inf _{f\in {\mathcal {F}}_{r}}L_{P}(f)-L^{*}+3p_{r}\right)}$$

^{[ 4 ] : Teorema 2.3}

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

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

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

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

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

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

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

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

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

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

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

Suponer${\displaystyle A\subset \mathbb {R} ^{m}}$es un conjunto de vectores cuya longitud (norma) es como máximo${\displaystyle c}$. Entonces, para cada entero${\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${\displaystyle A}$se encuentra en un subespacio d- dimensional de${\displaystyle \mathbb {R} ^{m}}$, entonces:

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

Sustituyendo esto en la cota anterior se obtiene la siguiente cota para 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 )}}$

Dado un conjunto${\displaystyle A\subseteq \mathbb {R} ^{n}}$entonces sostiene que ^{[ 6 ]} : ${\displaystyle {\frac {G(A)}{2{\sqrt {\log {n}}}}}\leq {\text{Rad}}(A)\leq {\sqrt {\frac {\pi }{2}}}G(A)}$ Dónde${\displaystyle G(A)}$es la complejidad gaussiana de A. Como ejemplo, consideremos las complejidades de Rademacher y gaussiana de la bola L1. La complejidad de Rademacher viene dada por exactamente 1, mientras que la complejidad gaussiana es del orden de${\displaystyle {\sqrt {\log d}}}$(lo cual puede demostrarse aplicando propiedades conocidas de los supremos de un conjunto de variables aleatorias subgaussianas ). ^{[ 6 ]}