Complejidad de la muestra

La complejidad de muestreo de un algoritmo de aprendizaje automático representa la cantidad de muestras de entrenamiento que necesita para aprender con éxito una función objetivo.

Más precisamente, la complejidad de la muestra es la cantidad de muestras de entrenamiento que necesitamos proporcionar al algoritmo, de modo que la función devuelta por el algoritmo esté dentro de un margen de error arbitrariamente pequeño de la mejor función posible, con una probabilidad arbitrariamente cercana a 1.

Existen dos variantes de complejidad de la muestra:

• La variante débil fija una distribución de entrada-salida particular;
• La variante fuerte toma la complejidad de muestreo del peor caso sobre todas las distribuciones de entrada-salida.

El teorema de la imposibilidad de obtener algo gratis , que se analiza más adelante, demuestra que, en general, la complejidad de la muestra fuerte es infinita, es decir, que no existe ningún algoritmo que pueda aprender la función objetivo globalmente óptima utilizando un número finito de muestras de entrenamiento.

Sin embargo, si solo nos interesa una clase particular de funciones objetivo (por ejemplo, solo funciones lineales), entonces la complejidad de la muestra es finita y depende linealmente de la dimensión VC en la clase de funciones objetivo. ^{[ 1 ]}

Dejar${\displaystyle X}$sea ​​un espacio que llamamos espacio de entrada, y${\displaystyle Y}$Sea un espacio que llamamos espacio de salida, y dejemos que${\displaystyle Z}$denotan el producto${\displaystyle X\times Y}$. Por ejemplo, en el contexto de la clasificación binaria,${\displaystyle X}$es típicamente un espacio vectorial de dimensión finita y${\displaystyle Y}$es el conjunto${\displaystyle \{-1,1\}}$.

Fijar un espacio de hipótesis${\displaystyle {\mathcal {H}}}$de funciones${\displaystyle h\colon X\to Y}$. Un algoritmo de aprendizaje sobre${\displaystyle {\mathcal {H}}}$es un mapa computable de${\displaystyle Z}$a${\displaystyle {\mathcal {H}}}$En otras palabras, es un algoritmo que toma como entrada una secuencia finita de muestras de entrenamiento y produce como salida una función a partir de${\displaystyle X}$a${\displaystyle Y}$Los algoritmos de aprendizaje típicos incluyen la minimización del riesgo empírico , con o sin regularización de Tikhonov .

Corregir una función de pérdida${\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}$, por ejemplo, la pérdida cuadrática${\displaystyle {\mathcal {L}}(y,y')=(yy')^{2}}$, dónde${\displaystyle h(x)=y'}$Para una distribución dada${\displaystyle \rho }$en${\displaystyle X\times Y}$, el riesgo esperado de una hipótesis (una función)${\displaystyle h\in {\mathcal {H}}}$es

${\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}$

En nuestro entorno, tenemos${\displaystyle h={\mathcal {A}}(S_{n})}$, dónde${\displaystyle {\mathcal {A}}}$es un algoritmo de aprendizaje y${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$es una secuencia de vectores que se extraen todos independientemente de${\displaystyle \rho }$Definir el riesgo óptimo$${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).}$$Colocar${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$, para cada tamaño de muestra${\displaystyle n}$.${\displaystyle h_{n}}$es una variable aleatoria y depende de la variable aleatoria${\displaystyle S_{n}}$, que se extrae de la distribución${\displaystyle \rho ^{n}}$El algoritmo${\displaystyle {\mathcal {A}}}$se denomina consistente si${\displaystyle {\mathcal {E}}(h_{n})}$converge probabilísticamente a${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$. En otras palabras, para todos${\displaystyle \epsilon ,\delta >0}$Existe un número entero positivo.${\displaystyle N}$, de tal manera que, para todos los tamaños de muestra${\displaystyle n\geq N}$, tenemos

$${\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}$$La complejidad de la muestra de${\displaystyle {\mathcal {A}}}$es entonces el mínimo${\displaystyle N}$para lo cual esto es válido, en función de${\displaystyle \rho,\epsilon}$, y${\displaystyle \delta }$. Escribimos la complejidad de la muestra como${\displaystyle N(\rho ,\epsilon ,\delta )}$para enfatizar que este valor de${\displaystyle N}$depende de${\displaystyle \rho,\epsilon}$, y${\displaystyle \delta }$. Si${\displaystyle {\mathcal {A}}}$no es consistente , entonces establecemos${\displaystyle N(\rho ,\epsilon ,\delta )=\infty }$. Si existe un algoritmo para el cual${\displaystyle N(\rho ,\epsilon ,\delta )}$es finito, entonces decimos que el espacio de hipótesis${\displaystyle {\mathcal {H}}}$es aprendible .

En otras palabras, la complejidad de la muestra${\displaystyle N(\rho ,\epsilon ,\delta )}$define la tasa de consistencia del algoritmo: dada una precisión deseada${\displaystyle \epsilon }$y confianza${\displaystyle \delta }$, uno necesita hacer una muestra${\displaystyle N(\rho ,\epsilon ,\delta )}$puntos de datos para garantizar que el riesgo de la función de salida esté dentro${\displaystyle \epsilon }$de lo mejor posible, con probabilidad al menos${\displaystyle 1-\delta }$. ^{[ 2 ]}

En el aprendizaje probablemente aproximadamente correcto (PAC) , uno se preocupa por si la complejidad de la muestra es polinómica , es decir, si${\displaystyle N(\rho ,\epsilon ,\delta )}$está acotado por un polinomio en${\displaystyle 1/\epsilon }$y${\displaystyle 1/\delta }$. Si${\displaystyle N(\rho ,\epsilon ,\delta )}$es polinomial para algún algoritmo de aprendizaje, entonces se dice que el espacio de hipótesis ${\displaystyle {\mathcal {H}}}$es PAC-aprendible . Esta es una noción más fuerte que ser aprendible.

Se puede preguntar si existe un algoritmo de aprendizaje tal que la complejidad de la muestra sea finita en sentido estricto, es decir, existe un límite en el número de muestras necesarias para que el algoritmo pueda aprender cualquier distribución sobre el espacio de entrada-salida con un error objetivo especificado. De manera más formal, se pregunta si existe un algoritmo de aprendizaje${\displaystyle {\mathcal {A}}}$, de tal manera que, para todo${\displaystyle \epsilon ,\delta >0}$Existe un número entero positivo.${\displaystyle N}$de tal manera que para todos${\displaystyle n\geq N}$, tenemos

$${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}$$ dónde${\displaystyle h_{n}={\mathcal {A}}(S_{n})}$, con${\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}$como se indicó anteriormente. El teorema de que no hay almuerzo gratis dice que sin restricciones en el espacio de hipótesis${\displaystyle {\mathcal {H}}}$, este no es el caso, es decir, siempre existen distribuciones "malas" para las cuales la complejidad de la muestra es arbitrariamente grande. ^{[ 1 ]}

Por lo tanto, para poder hacer afirmaciones sobre la tasa de convergencia de la cantidad $${\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}$$ uno debe o

• restringir el espacio de distribuciones de probabilidad${\displaystyle \rho }$, por ejemplo, mediante un enfoque paramétrico, o
• restringir el espacio de hipótesis${\displaystyle {\mathcal {H}}}$, como en los enfoques no distributivos.

Este último enfoque conduce a conceptos como la dimensión VC y la complejidad de Rademacher , que controlan la complejidad del espacio.${\displaystyle {\mathcal {H}}}$. Un espacio de hipótesis más pequeño introduce más sesgo en el proceso de inferencia, lo que significa que${\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}$puede ser mayor que el mejor riesgo posible en un espacio más amplio. Sin embargo, al restringir la complejidad del espacio de hipótesis, un algoritmo puede producir funciones más uniformemente consistentes. Esta compensación da lugar al concepto de regularización . ^{[ 2 ]}

Es un teorema de la teoría VC que las siguientes tres afirmaciones son equivalentes para un espacio de hipótesis.${\displaystyle {\mathcal {H}}}$:

1. ${\displaystyle {\mathcal {H}}}$es PAC-aprendible.
2. La dimensión VC de${\displaystyle {\mathcal {H}}}$es finito.
3. ${\displaystyle {\mathcal {H}}}$es una clase uniforme Glivenko-Cantelli .

Esto ofrece una manera de demostrar que ciertos espacios de hipótesis son aprendibles mediante PAC y, por extensión, aprendibles.

Además del entorno de aprendizaje supervisado, la complejidad de la muestra es relevante para problemas de aprendizaje semisupervisado , incluido el aprendizaje activo , ^{[ 7 ]} donde el algoritmo puede solicitar etiquetas para entradas elegidas específicamente con el fin de reducir el costo de obtener muchas etiquetas. El concepto de complejidad de la muestra también aparece en el aprendizaje por refuerzo , ^{[ 8 ]} el aprendizaje en línea y los algoritmos no supervisados, por ejemplo, para el aprendizaje de diccionarios . ^{[ 9 ]}

Una alta complejidad de muestreo implica que se requieren muchos cálculos para ejecutar una búsqueda en árbol de Monte Carlo . ^{[ 10 ]} Esto equivale a una búsqueda por fuerza bruta sin modelo en el espacio de estados. Por el contrario, un algoritmo de alta eficiencia tiene una baja complejidad de muestreo. ^{[ 11 ]} Algunas técnicas posibles para reducir la complejidad de muestreo son el aprendizaje métrico ^{[ 12 ]} y el aprendizaje por refuerzo basado en modelos. ^{[ 13 ]}

• Aprendizaje activo (aprendizaje automático)