Que signifie la théorie de l'apprentissage PAC?

15

Je suis nouveau dans l'apprentissage automatique. J'étudie un cours en machine learning (Stanford University) et je n'ai pas compris ce que l'on entend par cette théorie et quelle est son utilité. Je me demande si quelqu'un pourrait détailler cette théorie pour moi.

Cette théorie est basée sur cette équation. entrez la description de l'image ici

BetterEnglish
la source
2
PAC signifie Probablement approximativement correct.
Marc Claesen
@MarcClaesen, pourrais-je l'expliquer comme ceci: "Cela signifie que les approches d'apprentissage automatique offrent une solution probabiliste pour un problème donné et cette solution a tendance à être approximativement correcte"
BetterEnglish
1
voici un lien amusant: autonlab.org/tutorials/pac.html ou ceci: autonlab.org/_media/tutorials/pac05.pdf
EngrStudent - Reinstate Monica

Réponses:

16

La théorie de l'apprentissage probablement correct (PAC) permet d'analyser si et dans quelles conditions un apprenant produira probablement un classificateur approximativement correct. (Vous verrez que certaines sources utilisent A à la place de L. )LAL

Tout d'abord, définissons «approximatif». Une hypothèse est approximativement correcte si son erreur sur la distribution des entrées est bornée par quelques ϵ , 0 ϵ 1hHIe,errorD(h)<ϵ, oùDest la distribution sur les entrées.ϵ,0ϵ12.errorD(h)<ϵD

Ensuite, "probablement". Si sortira un tel classifieur avec une probabilité de 1 - δ , avec 0 δ 1L1δ , nous appelons ce classificateurprobablementapproximativement correct.0δ12

Le fait de savoir qu'un concept cible peut être appris par PAC vous permet de délimiter la taille d'échantillon nécessaire pour probablement apprendre un classificateur approximativement correct, ce qui est indiqué dans la formule que vous avez reproduite:

m1ϵ(ln|H|+ln1δ)

mH

Pour en savoir plus, cette vidéo et d'autres vidéos connexes peuvent être utiles, tout comme cette longue introduction ou l'un des nombreux textes d'apprentissage automatique , par exemple Mitchell .

Sean Easter
la source
C'est le type de réponse que je cherchais depuis longtemps; à la fois simple mais solide. Bien que de nombreuses sources fourniraient une réponse détaillée, il n'est pas préférable de la consulter rapidement.
Ébe Isaac
4


(xi,yi)xiyix~y~
disons 1 000 000 cependant. Si on vous donnait la séquence 1,2,3, ... 999,999, on serait plus sûr que le nombre suivant est 1 000 000. Cependant, le nombre suivant pourrait être 999 999,5, voire 5. Le fait est que plus on voit de données, plus on peut être sûr que l'on a produit un modèle précis, mais on ne peut jamais être absolument certain.

xi,1imyifθfΘp>1δfΘϵ(δ,ϵ)(δ,ϵ) et la complexité de la classe d'hypothèses donnée.

Hfθ(ϵ,δ)0<ϵ,δ,<.5fΘx~,y~Err(fΘ(x~),y~)<ϵp>1δm=m(δ,ϵ,H)(fΘ(x~)y~)2

(δ,ϵ)

meh
la source