Soit une distribution sur des paires chaîne de bits / étiquette et soit une collection de fonctions booléennes . Pour chaque fonction , soit: et soit: OPT (C, D) = \ min_ {f \ in C} \ err (f, D) Disons qu'un algorithme A apprend agnostiquement C sur n'importe quelle distribution, si pour n'importe quel D il peut avec probabilité 2/3 trouver une fonction f telle que err (f, D) \ leq OPT (C, D) + \ epsilon , compte tenu du temps et d'un certain nombre d'échantillons de D
Question: Quelles classes de fonctions sont connues pour être apprises de manière agnostique sur des distributions arbitraires?
Aucune classe n'est trop simple! Je sais que même les conjonctions monotones ne sont pas connues pour être apprises de manière agnostique sur des distributions arbitraires, donc je cherche juste des classes de fonctions non triviales.
la source
Réponses:
Si aucune classe n'est trop simple, voici quelques classes apprenables par PAC agnostiquement. En réponse aux commentaires, les classes avec de nombreuses hypothèses polynomiales sont barrées:
arbres de décision à profondeur constante (et autres classes ayant seulement plusieurs hypothèses)hyperplans dans (seulement les hypothèses produisant des étiquetages distincts)R2 O(n2) d'autres classes d'hypothèses dans des environnements de faible dimension.Presque tout le reste est NP-difficile à apprendre (au moins correctement) de manière agnostatique par PAC.
Le tutoriel d' Adam Kalai sur l'apprentissage agnostique peut également vous intéresser.
la source