Limites de dimension VC d'apprentissage PAC appropriées

Il est bien connu que pour une classe de concept de dimension VC , il suffit d'obtenir exemples étiquetés pour PAC learn . Il n'est pas clair pour moi si l'algorithme d'apprentissage PAC (qui utilise ces nombreux échantillons) est approprié ou inapproprié? Dans les manuels de Kearns et Vazirani ainsi que d'Anthony et Biggs, il semble que l'algorithme d'apprentissage PAC soit incorrect (c'est-à-dire que l'hypothèse de sortie ne réside pas dans ) d O ( $\mathcal{C}$$d$C$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$\mathcal{C}$$\mathcal{C}$

1. Quelqu'un pourrait-il préciser si une limite supérieure similaire s'applique également au paramètre d'apprentissage PAC approprié? Si oui, pourriez-vous me donner une référence où cela est explicitement mentionné et contient également une preuve autonome?

2. Hanneke a récemment amélioré cette limite en se débarrassant du facteur . Quelqu'un pourrait-il préciser si le est connu pour être amovible pour le paramètre d'apprentissage PAC approprié? Ou est-ce encore une question ouverte?$\log(1/\varepsilon)$$\log(1/\varepsilon)$

Merci à Aryeh d' avoir porté cette question à mon attention.

Comme d'autres l'ont mentionné, la réponse à (1) est Oui , et la méthode simple de minimisation des risques empiriques dans atteint la complexité de l'échantillon ( voir Vapnik et Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler et Warmuth, 1989).$\mathcal{C}$$O((d/\varepsilon)\log(1/\varepsilon))$

Quant à (2), il est en fait connu qu'il existe des espaces où aucun algorithme d'apprentissage approprié n'atteint mieux que la complexité de l'échantillon, et par conséquent, un apprentissage correct ne peut pas atteindre la complexité optimale de l' échantillon . À ma connaissance, ce fait n'a jamais été publié, mais est enraciné dans un argument connexe de Daniely et Shalev-Shwartz (COLT 2014) (formulé à l'origine pour une question différente, mais liée, dans l'apprentissage multiclasse).$\mathcal{C}$ Ω ( ( d / ε ) log ( 1 / ε ) ) O ( d / ε )$\Omega((d/\varepsilon)\log(1/\varepsilon))$$O(d/\varepsilon)$

Considérez le cas simple , et mettez l'espace comme , et est singletons : c'est-à-dire que chaque classificateur dans classe exactement un point de comme et les autres comme . Pour la borne inférieure, prenez la fonction cible comme un singleton aléatoire , où , et , la distribution marginale de , est uniforme sur$d=1$$\mathcal{X}$$\{1,2,...,1/\varepsilon\}$$\mathcal{C}$$f_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$$\mathcal{C}$$\mathcal{X}$$1$$0$$f_{x^*}$$x^{*} \sim {\rm Uniform}(\mathcal{X})$$P$$X$$\mathcal{X}\setminus\{x^*\}$1 z 1 C z X ∖ { x * } 1 / 2 f z z ≠ x * 1 / 2 Ω ( ( 1 / ε ) log ( 1 / ε ) ) X ∖ { x * } Ω ( ( 1 / ε ) log ( 1 / ε ) ). Maintenant, l'apprenant ne voit jamais d'exemples étiquetés , mais il doit choisir un point pour deviner est étiqueté (surtout, la fonction `` tout zéro '' n'est pas dans , donc tout apprenant doit deviner quelques ), et jusqu'à ce qu'il ait vu chaque point dans il a au moins chance de deviner faux (c'est-à-dire la probabilité postérieure que son ait est au moins ). L'argument du collecteur de coupons implique qu'il faudrait$1$$z$$1$$\mathcal{C}$$z$$\mathcal{X}\setminus\{x^*\}$$1/2$$f_z$$z \neq x^*$$1/2$$\Omega((1/\varepsilon)\log(1/\varepsilon))$ pour voir chaque point dans . Cela prouve donc une limite inférieure de pour tous les apprenants appropriés.$\mathcal{X} \setminus \{x^*\}$$\Omega((1/\varepsilon)\log(1/\varepsilon))$

Pour le général , nous prenons comme , prenons comme classificateurs pour les ensembles de taille exactement , choisissez la fonction cible au hasard dans , et reprenez comme uniforme sur les seuls points que la fonction cible classe (de sorte que l'apprenant ne voit jamais un point nommé ). Ensuite, une généralisation de l'argument coupon-collecteur implique que nous avons besoin d' échantillons pour voir au moins$d>1$$\mathcal{X}$$\{1,2,...,d/(4\varepsilon)\}$$\mathcal{C}$$\mathbb{I}_{A}$$A \subset \mathcal{X}$$d$$\mathcal{C}$$P$$0$$1$$\Omega((d/\varepsilon)\log(1/\varepsilon))$$|\mathcal{X}| - 2d$points distincts de , et sans voir autant de points distincts, tout apprenant approprié a au moins chance d'obtenir plus de de sa supposition de points erronés dans son hypothèse choisie , ce qui signifie que son taux d'erreur est supérieur à . Donc, dans ce cas, il n'y a aucun apprenant approprié avec une complexité d'échantillon inférieure à , ce qui signifie qu'aucun apprenant approprié n'atteint la complexité optimale de l'échantillon .$\mathcal{X}$$1/3$$d/4$$A$$d$$h_{A}$$\varepsilon$$\Omega((d/\varepsilon)\log(1/\varepsilon))$$O(d/\varepsilon)$

Notez que le résultat est assez spécifique à l'espace construit. Il existe des espaces où les apprenants appropriés peuvent atteindre la complexité optimale de l'échantillon , et même l'expression exacte complète dans (Hanneke, 2016a). Certaines limites supérieures et inférieures pour les apprenants ERM généraux ont été développées dans (Hanneke, 2016b), quantifiées en termes de propriétés de l'espace , ainsi que des cas plus spécialisés où des apprenants appropriés spécifiques peuvent parfois atteindre l'optimum complexité de l'échantillon.$\mathcal{C}$$\mathcal{C}$$O(d/\varepsilon)$$O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$$\mathcal{C}$

Références:

Vapnik et Chervonenkis (1974). Théorie de la reconnaissance des formes. Nauka, Moscou, 1974.

Blumer, Ehrenfeucht, Haussler et Warmuth (1989). L'apprentissage et la dimension Vapnik-Chervonenkis. Journal de l'Association for Computing Machinery, 36 (4): 929–965.

Daniely et Shalev-Shwartz (2014). Apprenants optimaux pour les problèmes multiclasses. Dans les actes de la 27e conférence sur la théorie de l'apprentissage.

Hanneke (2016a). L'échantillon optimal de complexité de l'apprentissage PAC. Journal of Machine Learning Research, vol. 17 (38), p. 1-15.

Hanneke (2016b). Limites d'erreur raffinées pour plusieurs algorithmes d'apprentissage. Journal of Machine Learning Research, vol. 17 (135), p. 1-55.

Vos questions (1) et (2) sont liées. Tout d'abord, parlons d'un bon apprentissage PAC. Il est connu qu'il existe des apprenants PAC appropriés qui n'atteignent aucune erreur d'échantillon et nécessitent néanmoins des exemples . Pour une preuve simple de la dépendance , considérons la classe conceptuelle d'intervalles sous la distribution uniforme. Si nous choisissons le plus petit intervalle cohérent, nous obtenons en effet un échantillon de complexité de . Supposons, cependant, que nous choisissions le plus grand intervalle cohérent, et que le concept cible soit un intervalle ponctuel tel que$\Omega(\frac{d}{\epsilon}\log\frac1\epsilon)$$\epsilon$$[a,b]\subseteq[0,1]$$O(1/\epsilon)$$[0,0]$. Ensuite, un simple argument de collecteur de coupons montre qu'à moins que nous recevions à peu près des exemples , nous serons dupés par l'espacement entre les exemples négatifs (le seul type que nous verrons ) - qui a un comportement caractéristique de [taille de l'échantillon] sous la distribution uniforme. Des bornes inférieures plus générales de ce type sont données dans$\frac{1}{\epsilon}\log\frac1\epsilon$$1/$

P. Auer, R. Ortner. Un nouveau PAC à destination des classes de concept à intersection fermée. Machine Learning 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf

La chose à propos du PAC approprié est que pour des résultats positifs dans le cas abstrait, on ne peut pas spécifier un algorithme au-delà de l'ERM, qui dit "trouver un concept cohérent avec l'échantillon étiqueté". Lorsque vous avez une structure supplémentaire, comme des intervalles, vous pouvez examiner deux algorithmes ERM différents, comme ci-dessus: un segment cohérent minimal vs maximal cohérent. Et ceux-ci ont des complexités d'échantillons différentes!

Le pouvoir d'un PAC inapproprié est que vous pouvez concevoir différents schémas de vote (celui d'Hanneke est un tel résultat) - et cette structure supplémentaire vous permet de prouver des taux améliorés. (L'histoire est plus simple pour les PAC agnostiques, où l'ERM vous donne le meilleur taux de pire cas possible, jusqu'aux constantes.)

Éditer. Il me vient maintenant à l'esprit que la stratégie de prédiction du graphique à 1 inclusion de D. Haussler, N. Littlestone, Md K. Warmuth. Prédire {0,1} -fonctions sur des points tirés aléatoirement. Inf. Comput. 115 (2): 248-292 (1994) pourrait être un candidat naturel pour un apprenant PAC approprié universel .$O(d/\epsilon)$

Pour ajouter à la réponse actuellement acceptée:

1. Oui. La limite supérieure de la complexité de l'échantillon est également valable pour un apprentissage PAC correct (bien qu'il soit important de noter qu'il peut ne pas conduire à un algorithme d'apprentissage efficace sur le plan des calculs. Ce qui est normal, car à moins que soit connu que certaines classes ne sont pas efficacement apprises correctement par PAC. Cf. par exemple le théorème 1.3 dans le livre de Kearns — Vazirani vous mention). Ceci est en fait montré dans le livre de Kearns-Vazirani (Théorème 3.3), car il existe un chercheur d'hypothèses cohérent avec la classe d'hypothèses . Voir aussi [1].NP=RPLH=

   $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$ $\mathsf{NP}=\mathsf{RP}$$L$$\mathcal{H}=\mathcal{C}$

2. Inconnue. L'algorithme de Hanneke [2] est un algorithme d'apprentissage incorrect. La question de savoir si ce facteur supplémentaire dans la complexité de l'échantillon peut être supprimé pour un apprentissage PAC approprié (informations théoriquement, c'est-à-dire en mettant de côté toute exigence d'efficacité de calcul) reste une question ouverte. Cf. les questions ouvertes à la fin de [3]:$\log(1/\varepsilon)$

   Classiquement, il reste une question ouverte de savoir si le facteur dans la limite supérieure de [1] pour -un apprentissage PAC approprié est nécessaire.( ε , δ $\log(1/\varepsilon)$$(\varepsilon, \delta)$

   (La note de bas de page 1 du même document est également pertinente)

[1] A. Blumer, A. Ehrenfeucht, D. Haussler et MK Warmuth. L'apprentissage et la dimension Vapnik-Chervonenkis. Journal de l'ACM, 36 (4): 929–965, 1989.

[2] S. Hanneke. L'échantillon optimal de complexité de l'apprentissage PAC. J. Mach. Apprendre. Res. 17, 1, 1319-1333, 2016.

[3] S. Arunachalam et R. de Wolf. Complexité d'échantillonnage quantique optimale des algorithmes d'apprentissage. Dans les actes de la 32e Computational Complexity Conference (CCC), 2017.