Le théorème du déjeuner gratuit et la cohérence K-NN

Dans l'apprentissage informatique, le théorème de la NFL déclare qu'il n'y a pas d'apprenant universel. Pour chaque algorithme d'apprentissage, il existe une distribution qui amène l'apprenant à émettre une hypotesis avec une grande erreur, avec une probabilité élevée (bien qu'il y ait une hypotesis à faible erreur). La conclusion est que pour apprendre, la classe d'hypotesis ou les distributions doivent être restreintes. Dans leur livre "Une théorie probabiliste de la reconnaissance des formes", Devroye et al prouvent le thème suivant pour l'apprenant K-plus proche: Où

Assume μ has a density. if k \to \infty and k / n \to 0 then for every ϵ > 0, there's N, s.t. for all n > N : P (R_{n} - R^{*} > ϵ) < 2 e x p (- C_{d} n ϵ^{2})

$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \\ \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.} \text{ for all } n>N : \\ P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2})$

R^{*}

$R^*$ est l'erreur de la règle optimale , est la véritable erreur de la sortie K-NN (la probabilité est supérieure à l'ensemble d'apprentissage de taille ), est la mesure de probabilité sur l'espace d'instance

est une constante ne dépend que de la dimension euclidienne. Par conséquent, nous pouvons nous rapprocher autant que nous le souhaitons de la meilleure hypothèse qui existe (pas la meilleure dans une classe restreinte), sans faire aucune hypothèse sur la distribution. J'essaie donc de comprendre comment ce résultat ne contredit pas le theroem de la NFL? Merci!

R_{n}

$R_n$

n

$n$

μ

$\mu$

R^{d}

$\mathbb{R}^d$

C_{d}

$C_d$

k-nearest-neighbour consistency michael J
la source

Réponses:

La façon dont je comprends le théorème de la NFL est qu'il n'y a pas d'algorithme d'apprentissage qui soit meilleur que le reste dans chaque tâche. Ce n'est cependant pas un théorème au sens mathématique clair qu'il a une preuve, plutôt une observation empirique.

Semblable à ce que vous avez dit pour le kNN, il y a aussi le théorème d'approximation universel pour les réseaux de neurones, qui stipule que, étant donné un réseau de neurones à 2 couches, nous pouvons approximer n'importe quelle fonction avec n'importe quelle erreur arbitraire.

Maintenant, comment cela ne brise-t-il pas la NFL? Il indique essentiellement que vous pouvez résoudre tout problème imaginable avec un simple NN à 2 couches. La raison en est que même si, théoriquement, les NN peuvent se rapprocher de tout, en pratique, il est très difficile de leur apprendre à se rapprocher de quoi que ce soit. C'est pourquoi pour certaines tâches, d'autres algorithmes sont préférables.

Une façon plus pratique d'interpréter la NFL est la suivante:

Il n'y a aucun moyen de déterminer a priori quel algorithme fera le mieux pour une tâche donnée.

CaucM
la source

Merci pour la réponse, mais il y a quelques inexactitudes. Premièrement, le théorème de la NFL a une preuve (par exemple, shalev-shwartz & ben-david, comprendre l'apprentissage automatique, chapitre 5). Pour le théorème d'approximation universelle - ce théorème traite de l'expressivité, tandis que le théorème de la NFL traite de la généralisation.

michael J