Pac L'apprentissage vs apprentissage sur la distribution uniforme

Question

La classe de fonction $ \ mathcal {f} $ est pac-apprenable s'il existe un algorithme $ a $ tel que pour tout distribution $ d $ , toute fonction inconnue $ f $ et tout $ \ epsilon, \ delta $ il existe qu'il existe $ M $ telle que sur une entrée de $ M $ des échantillons iid $ (x, f (x)) $ où < span classe="math-conteneur"> $ x \ sim d $ , $ A $ A $ retours, avec une probabilité plus grande que $ 1- \ delta $ , une fonction $ \ epsilon $ -Close to $ f $ (par rapport à $ d $ ). La classe $ \ MATHCAL {F} $ est efficacement accentuellement apprenable si c'est PAC apprenant et $ A $ > exécute dans le temps $ \ texte {poly} (1 / \ epsilon, 1 / \ delta, n) $ (où $ | x |= n $ ) et la description de $ f $ .

y a-t-il un cas où une classe $ \ mathcal {f} $ n'est pas efficace PAC apprenable, mais elle est efficace efficacement sur la distribution uniforme?

Answer 1

y a-t-il un cas où une classe $ \ mathcal {f} $ n'est pas efficace PAC apprenable, mais elle est efficace efficacement sur la distribution uniforme?

Ceci a été demandé sur Tcs.se . On dirait que la réponse courte est oui - Aaron Roth donne l'exemple de largeur - $ k $ conjonction pour $ k \ gg \ journal n $ . Et dans les commentaires, Avrim Blum est cité comme donnant la réponse de $ 2 $ -term dnf.

Je ne comprends pas totalement les exemples là-bas - il doit prendre un peu plus de travail pour dériver vraiment le résultat (je vais mettre à jour cette réponse si je trouve une preuve autonome). Mais le problème général ici avec la distribution uniforme est que si la fonction cible $ f $ est "clairsemé", ce qui signifie qu'il étiquette au plus un $ \ delta $ fraction de la distribution d'entrée avec $ 1 $ , il est facile d'apprendre en devinant simplement $ 0 $ .

---

Au-delà de l'apprentissage efficace (polynomial) de PAC, il existe d'autres exemples où la distribution uniforme semble aider. Par exemple, un problème difficile classique pour l'apprentissage du PAC est du DNF, un problème qui est conjecturé pour ne pas être approuvé et assez dur. D'autre part, le DNF sur la distribution uniforme est presque accessible: nous avons un algorithme de temps polynomial qausi Voir Ces notes et ces notes .

En résumé, il semble y avoir beaucoup de travail sur l'apprentissage sous la distribution uniforme (recherche "Apprentissage du PAC sous une distribution uniforme" pour des références supplémentaires). Et il semble que ce problème soit plus facile que d'étudier l'apprentissage du PAC, où nous ne sommes pas en mesure de prouver beaucoup. Citant les notes de Ryan O'Donnell ci-dessus:

General Pac-apprenant insiste sur le fait qu'un algorithme fonctionne simultanément pour toutes les distributions. En fait, la communauté d'apprentissage de la machine intéressée par les applications du monde réel trouve le cadre uniforme discutable: «Ils vous frapperont dans le nez si vous essayez de leur dire des algorithmes dans cette Cadre. "- Anryan. Mais, dans un cadre plus général, personne ne peut vraiment prouver rien.