Tolerancia a errores (aprendizaje PAC)

En el aprendizaje PAC , la tolerancia a errores se refiere a la capacidad de un algoritmo de aprender cuando los ejemplos recibidos han sido corrompidos de alguna manera. De hecho, este es un problema muy común e importante ya que en muchas aplicaciones no es posible acceder a datos libres de ruido. El ruido puede interferir con el proceso de aprendizaje en diferentes niveles: el algoritmo puede recibir datos que hayan sido etiquetados incorrectamente en ocasiones, o las entradas pueden tener alguna información falsa, o la clasificación de los ejemplos puede haber sido adulterada maliciosamente.

En lo que sigue, sea nuestro espacio de entrada de dimensión . Sea una clase de funciones que deseamos usar para aprender una función de destino con valor definido sobre . Sea la distribución de las entradas sobre . El objetivo de un algoritmo de aprendizaje es elegir la mejor función de manera que minimice . Supongamos que tenemos una función que puede medir la complejidad de . Sea un oráculo que, siempre que se lo llama, devuelve un ejemplo y su etiqueta correcta . ${\displaystyle X}$${\displaystyle n}$${\displaystyle {\mathcal {H}}}$${\displaystyle \{0,1\}}$${\displaystyle f}$${\displaystyle X}$${\displaystyle {\mathcal {D}}}$${\displaystyle X}$${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$${\displaystyle size(f)}$${\displaystyle f}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle x}$${\displaystyle f(x)}$

Cuando ningún ruido corrompe los datos, podemos definir el aprendizaje en la configuración de Valiant : ^{[1] [2]}

Definición: Decimos que es eficientemente aprendible usando en el entorno Valiant si existe un algoritmo de aprendizaje que tiene acceso a y un polinomio tal que para cualquier y genera, en un número de llamadas al oráculo acotado por , una función que satisface con probabilidad al menos la condición . ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$${\displaystyle 0<\delta \leq 1}$${\displaystyle p\left({\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,{\text{size}}(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle {\text{error}}(h)\leq \varepsilon }$

A continuación definiremos la capacidad de aprendizaje de cuando los datos han sufrido alguna modificación. ^{[3] [4] [5]}${\displaystyle f}$

En el modelo de ruido de clasificación ^[6] se introduce una tasa de ruido . Entonces, en lugar de que eso devuelva siempre la etiqueta correcta de ejemplo , el algoritmo solo puede llamar a un oráculo defectuoso que cambiará la etiqueta de con probabilidad . Como en el caso de Valiant, el objetivo de un algoritmo de aprendizaje es elegir la mejor función de modo que minimice . En las aplicaciones es difícil tener acceso al valor real de , pero suponemos que tenemos acceso a su límite superior . ^[7] Tenga en cuenta que si permitimos que la tasa de ruido sea , entonces el aprendizaje se vuelve imposible en cualquier cantidad de tiempo de cálculo, porque cada etiqueta no transmite información sobre la función de destino. ${\displaystyle 0\leq \eta <{\frac {1}{2}}}$${\displaystyle {\text{Oracle}}(x)}$${\displaystyle x}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\eta )}$${\displaystyle x}$${\displaystyle \eta }$${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$${\displaystyle \eta }$${\displaystyle \eta _{B}}$${\displaystyle 1/2}$

Definición: Decimos que es eficientemente aprendible usando en el modelo de ruido de clasificación si existe un algoritmo de aprendizaje que tiene acceso a y un polinomio tal que para cualquier , y genera, en un número de llamadas al oráculo acotado por , una función que satisface con probabilidad al menos la condición . ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\eta )}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0\leq \eta \leq {\frac {1}{2}}}$${\displaystyle 0\leq \varepsilon \leq 1}$${\displaystyle 0\leq \delta \leq 1}$${\displaystyle p\left({\frac {1}{1-2\eta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle error(h)\leq \varepsilon }$

El aprendizaje de consultas estadísticas ^[8] es un tipo de problema de aprendizaje activo en el que el algoritmo de aprendizaje puede decidir si solicita información sobre la probabilidad de que una función etiquete correctamente ejemplo y recibe una respuesta precisa dentro de una tolerancia . Formalmente, siempre que el algoritmo de aprendizaje llama al oráculo , recibe como retroalimentación probabilidad , tal que . ${\displaystyle {\mathcal {A}}}$${\displaystyle P_{f(x)}}$${\displaystyle f}$${\displaystyle x}$${\displaystyle \alpha }$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle Q_{f(x)}}$${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$

Definición: Decimos que es eficientemente aprendible usando el modelo de aprendizaje de consultas estadísticas si existe un algoritmo de aprendizaje que tiene acceso a y polinomios , , y tales que para cualquier se cumple lo siguiente: ${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle p(\cdot ,\cdot ,\cdot )}$${\displaystyle q(\cdot ,\cdot ,\cdot )}$${\displaystyle r(\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$

1. ${\displaystyle {\text{Oracle}}(x,\alpha )}$puede evaluar a tiempo ;${\displaystyle P_{f(x)}}$${\displaystyle q\left({\frac {1}{\varepsilon }},n,size(f)\right)}$
2. ${\displaystyle {\frac {1}{\alpha }}}$está delimitado por${\displaystyle r\left({\frac {1}{\varepsilon }},n,size(f)\right)}$
3. ${\displaystyle {\mathcal {A}}}$genera un modelo tal que , en un número de llamadas al oráculo limitado por .${\displaystyle h}$${\displaystyle err(h)<\varepsilon }$${\displaystyle p\left({\frac {1}{\varepsilon }},n,size(f)\right)}$

Tenga en cuenta que el parámetro de confianza no aparece en la definición de aprendizaje. Esto se debe a que el objetivo principal de es permitir que el algoritmo de aprendizaje tenga una pequeña probabilidad de falla debido a una muestra no representativa. Dado que ahora siempre garantiza el cumplimiento del criterio de aproximación , la probabilidad de falla ya no es necesaria. ${\displaystyle \delta }$${\displaystyle \delta }$${\displaystyle {\text{Oracle}}(x,\alpha )}$${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$

El modelo de consulta estadística es estrictamente más débil que el modelo PAC: cualquier clase que se pueda aprender SQ de manera eficiente se puede aprender PAC de manera eficiente en presencia de ruido de clasificación, pero existen problemas que se pueden aprender PAC de manera eficiente, como la paridad , que no se pueden aprender SQ de manera eficiente. ^[8]

En el modelo de clasificación maliciosa ^[9], un adversario genera errores para frustrar el algoritmo de aprendizaje. Esta configuración describe situaciones de ráfaga de errores , que pueden ocurrir cuando, durante un tiempo limitado, el equipo de transmisión funciona mal repetidamente. Formalmente, el algoritmo llama a un oráculo que devuelve un ejemplo correctamente etiquetado extraído, como es habitual, de una distribución sobre el espacio de entrada con probabilidad , pero devuelve con probabilidad un ejemplo extraído de una distribución que no está relacionada con . Además, este ejemplo elegido maliciosamente puede ser seleccionado estratégicamente por un adversario que tenga conocimiento de , , o del progreso actual del algoritmo de aprendizaje. ${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\beta )}$${\displaystyle x}$${\displaystyle {\mathcal {D}}}$${\displaystyle 1-\beta }$${\displaystyle \beta }$${\displaystyle {\mathcal {D}}}$${\displaystyle f}$${\displaystyle \beta }$${\displaystyle {\mathcal {D}}}$

Definición: Dado un límite para , decimos que se puede aprender de manera eficiente usando el modelo de clasificación maliciosa, si existe un algoritmo de aprendizaje que tiene acceso a y un polinomio tal que para cualquier , genera, en un número de llamadas al oráculo limitado por , una función que satisface con probabilidad al menos la condición . ${\displaystyle \beta _{B}<{\frac {1}{2}}}$${\displaystyle 0\leq \beta <{\frac {1}{2}}}$${\displaystyle f}$${\displaystyle {\mathcal {H}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\text{Oracle}}(x,\beta )}$${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot ,\cdot )}$${\displaystyle 0<\varepsilon \leq 1}$${\displaystyle 0<\delta \leq 1}$${\displaystyle p\left({\frac {1}{1/2-\beta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle 1-\delta }$${\displaystyle error(h)\leq \varepsilon }$

En el modelo de ruido de atributo aleatorio no uniforme ^{[10] [11]} , el algoritmo está aprendiendo una función booleana ; un oráculo malicioso puede invertir cada bit -ésimo del ejemplo de forma independiente con una probabilidad . ${\displaystyle {\text{Oracle}}(x,\nu )}$${\displaystyle i}$${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle \nu _{i}\leq \nu }$

Este tipo de error puede arruinar irremediablemente el algoritmo, de hecho se cumple el siguiente teorema:

En la configuración de ruido de atributo aleatorio no uniforme, un algoritmo puede generar una función tal que solo si . ${\displaystyle {\mathcal {A}}}$${\displaystyle h\in {\mathcal {H}}}$${\displaystyle error(h)<\varepsilon }$${\displaystyle \nu <2\varepsilon }$