Tolerancia a errores (aprendizaje PAC)
En el aprendizaje de PAC , la tolerancia a errores se refiere a la capacidad de un algoritmo para aprender cuando los ejemplos recibidos se han corrompido 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 sin ruido. El ruido puede interferir con el proceso de aprendizaje en diferentes niveles: el algoritmo puede recibir datos que ocasionalmente se han etiquetado incorrectamente, o las entradas pueden tener información falsa, o la clasificación de los ejemplos puede haber sido adulterada maliciosamente.
Notación y el modelo de aprendizaje Valiant
A continuación, dejemos ser nuestro -espacio de entrada dimensional. Dejar ser una clase de funciones que deseamos usar para aprender un -función objetivo valorada definido sobre . Dejar ser la distribución de los insumos sobre . El objetivo de un algoritmo de aprendizaje es elegir la mejor función tal que minimiza . Supongamos que tenemos una función que puede medir la complejidad de . Dejar ser un oráculo que, siempre que se llame, devuelva un ejemplo y su etiqueta correcta .
Cuando ningún ruido corrompe los datos, podemos definir el aprendizaje en la configuración de Valiant : [1] [2]
Definición: Decimos que se aprende de manera eficiente usando en la configuración de Valiant si existe un algoritmo de aprendizaje que tiene acceso a y un polinomio tal que para cualquier y genera, en una serie de llamadas al oráculo delimitadas por , Una función que satisfaga con probabilidad al menos la condición .
A continuación, definiremos la capacidad de aprendizaje de cuando los datos hayan sufrido alguna modificación. [3] [4] [5]
Ruido de clasificación
En el modelo de clasificación de ruido [6] una tasa de ruido es presentado. Entonces, en lugar de que devuelve siempre la etiqueta correcta de ejemplo , algoritmo solo puedo llamar a un oráculo defectuoso que volteará la etiqueta de con probabilidad . Como en el caso Valiant, el objetivo de un algoritmo de aprendizaje es elegir la mejor función tal que minimiza . En las aplicaciones, es difícil tener acceso al valor real de, pero asumimos 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 objetivo.
Definición: Decimos que se aprende de manera eficiente usando en el modelo de clasificación de ruido si existe un algoritmo de aprendizaje que tiene acceso a y un polinomio tal que para cualquier , y genera, en una serie de llamadas al oráculo delimitadas por , Una función que satisfaga con probabilidad al menos la condición .
Aprendizaje de consultas estadísticas
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 solicitar información sobre la probabilidad que una función ejemplo de etiquetas correctamente , y recibe una respuesta precisa dentro de una tolerancia . Formalmente, siempre que el algoritmo de aprendizaje llama al oráculo , recibe como probabilidad de retroalimentación , tal que .
Definición: Decimos que se aprende de manera eficiente usando en el modelo de aprendizaje de consultas estadísticas si existe un algoritmo de aprendizaje que tiene acceso a y polinomios , , y tal que para cualquier la siguiente retención:
- puede evaluar a tiempo ;
- está delimitado por
- genera un modelo tal que , en una serie de llamadas al oráculo delimitadas por .
Tenga en cuenta que el parámetro de confianza no aparece en la definición de aprendizaje. Esto se debe a que el propósito principal dees permitir que el algoritmo de aprendizaje tenga una pequeña probabilidad de falla debido a una muestra no representativa. Desde ahora siempre garantiza cumplir con el criterio de aproximación , la probabilidad de falla ya no es necesaria.
El modelo de consulta estadística es estrictamente más débil que el modelo PAC: cualquier clase que se pueda aprender con SQ de manera eficiente se puede aprender con PAC de manera eficiente en presencia de ruido de clasificación, pero existen problemas de aprendizaje con PAC eficientes, como la paridad, que no se pueden aprender con SQ de manera eficiente. [8]
Clasificación maliciosa
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 falla repetidamente. Formalmente, algoritmo llama a un oráculo que devuelve un ejemplo correctamente etiquetado extraído, como de costumbre, de la distribución sobre el espacio de entrada con probabilidad , pero vuelve 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 el progreso actual del algoritmo de aprendizaje.
Definición: dado un límite por , Nosotros decimos eso se aprende de manera eficiente usando en 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 una serie de llamadas al oráculo delimitadas por , Una función que satisfaga con probabilidad al menos la condición .
Errores en las entradas: ruido de atributo aleatorio no uniforme
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 voltear cada uno -th bit de ejemplo independientemente con probabilidad .
Este tipo de error puede frustrar irreparablemente 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 sólo si .
Ver también
Referencias
- ^ Valiant, LG (agosto de 1985). Aprendizaje de la disyunción de conjunciones . En IJCAI (págs. 560–566).
- ^ Valiente, Leslie G. "Una teoría de lo que se puede aprender". Comunicaciones del ACM 27.11 (1984): 1134-1142.
- ^ Laird, PD (1988). Aprendiendo de datos buenos y malos . Editores académicos de Kluwer.
- ^ Kearns, Michael. " Aprendizaje eficiente y tolerante al ruido a partir de consultas estadísticas ". Journal of the ACM 45.6 (1998): 983–1006.
- ^ Brunk, Clifford A. y Michael J. Pazzani. " Una investigación de algoritmos de aprendizaje de conceptos relacionales tolerantes al ruido ". Actas del VIII Taller Internacional de Aprendizaje Automático. 1991.
- ^ Kearns, MJ y Vazirani, UV (1994). Introducción a la teoría del aprendizaje computacional , capítulo 5. Prensa del MIT.
- ^ Angluin, D. y Laird, P. (1988). Aprendiendo de ejemplos ruidosos . Aprendizaje automático, 2 (4), 343–370.
- ↑ a b Kearns, M. (1998). [www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf Aprendizaje eficiente y tolerante al ruido a partir de consultas estadísticas] . Revista de la ACM, 45 (6), 983–1006.
- ^ Kearns, M. y Li, M. (1993). [www.cis.upenn.edu/~mkearns/papers/malicious.pdf Aprendizaje en presencia de errores maliciosos] . SIAM Journal on Computing, 22 (4), 807–837.
- ^ Goldman, SA y Robert, H. (1991). Sloan. La dificultad del ruido de atributos aleatorios. Informe técnico WUCS 91 29, Universidad de Washington, Departamento de Ciencias de la Computación.
- ^ Sloan, RH (1989). Teoría del aprendizaje computacional: Nuevos modelos y algoritmos (Tesis doctoral, Instituto de Tecnología de Massachusetts).