¿Qué significa la teoría de aprendizaje PAC?

15

Soy nuevo en aprendizaje automático. Estoy estudiando un curso de aprendizaje automático (Universidad de Stanford) y no entendí qué significa esta teoría y cuál es su utilidad. Me pregunto si alguien podría detallar esta teoría para mí.

Esta teoría se basa en esta ecuación. ingrese la descripción de la imagen aquí

Mejor inglés
fuente
2
PAC significa Probablemente Aproximadamente Correcto.
Marc Claesen
@MarcClaesen, ¿podría explicarlo así: "Significa que los enfoques de aprendizaje automático ofrecen una solución de probabilidad para un problema dado y esta solución tiende a ser aproximadamente correcta"
BetterEnglish
1
aquí hay un enlace divertido: autonlab.org/tutorials/pac.html o esto: autonlab.org/_media/tutorials/pac05.pdf
EngrStudent - Reinstale Monica el

Respuestas:

16

Probablemente, la teoría de aprendizaje aproximadamente correcta (PAC) ayuda a analizar si y bajo qué condiciones un alumno probablemente generará un clasificador aproximadamente correcto. (Verá que algunas fuentes usan A en lugar de L ).LAL

Primero, definamos "aproximado". Una hipótesis es aproximadamente correcta si su error sobre la distribución de entradas está limitado por algún ϵ , 0 ϵ 1hHEs decir,errorD(h)<ϵ, dondeDϵ,0ϵ12.errorD(h)<ϵD es la distribución sobre las entradas.

A continuación, "probablemente". Si generará dicho clasificador con probabilidad 1 - δ , con 0 δ 1L1δ , llamamos a ese clasificadorprobablementeaproximadamente correcto.0δ12

Saber que un concepto objetivo puede aprenderse con PAC le permite vincular el tamaño de muestra necesario para probablemente aprender un clasificador aproximadamente correcto, que es lo que se muestra en la fórmula que ha reproducido:

m1ϵ(ln|H|+ln1δ)

Para tener alguna intuición al respecto, tenga en cuenta los efectos en cuando modifique las variables en el lado derecho. A medida que disminuye el error permitido , crece el tamaño de muestra necesario. Asimismo, se crece con la probabilidad de que un alumno aproximadamente correcto, y con el tamaño del espacio de hipótesis H . (En términos generales, un espacio de hipótesis es el conjunto de clasificadores que su algoritmo considera). Más claramente, a medida que considera más clasificadores posibles, o desea un menor error o una mayor probabilidad de corrección, necesita más datos para distinguirlos.mH

Para más información, este y otros videos relacionados pueden ser útiles, como podría ser esta larga introducción o uno de los muchos textos de aprendizaje automático , por ejemplo, Mitchell .

Sean Easter
fuente
Este es el tipo de respuesta que estaba buscando durante mucho tiempo; ambos simples pero con sonido. Aunque muchas fuentes proporcionarían una respuesta extensa, no es tan preferible para una referencia rápida.
Ébe Isaac
3


(xi,yi)xiyix~y~
Realmente uno no está interesado en la precisión de la hipótesis sobre los datos (de capacitación) dados, excepto que es difícil creer que un modelo creado con algunos datos no refleje con precisión ese conjunto de datos, pero será preciso en cualquier futuro conjuntos de datos Las dos advertencias importantes son que uno no puede predecir datos nuevos con una precisión del 100% y también existe la posibilidad de que los ejemplos de datos que uno ha visto pierdan algo importante. Un ejemplo de juguete sería que si le diera los 'datos' 1,2,3,4, uno 'predeciría' que 5 sería el siguiente número. Si probaste esto preguntando a la gente cuál era el siguiente número en la secuencia, la mayoría de la gente diría 5. Alguien podría

xi,1imyifθfΘp>1δfΘϵ(δ,ϵ)(δ,ϵ) y cuán compleja es la clase de hipótesis dada.

Hfθ(ϵ,δ)0<ϵ,δ,<.5FΘX~,y~mirr(FΘ(X~),y~)<ϵ con probabilidad pag>1-δ si el modelo fue seleccionado (entrenado) con al menos m=m(δ,ϵ,H) training examples. Here Err is the chosen loss function which is usually (fΘ(x~)y~)2.

The diagram you have gives a formula for how much data one needs to train on for a given class of hypotheses to satisfy a given pair (δ,ϵ). I could be wrong, but I believe that this definition was given by Valiant in a paper called "A Theory of the Learnable" and was in part responsible for Valiant winning the Turing prize.

meh
fuente