Comprendre le théorème du déjeuner gratuit dans la classification des motifs de Duda et al

J'ai des questions sur les notations utilisées dans la section 9.2 Absence de supériorité inhérente de tout classificateur dans la classification des modèles de Duda, Hart et Stork . Permettez-moi d'abord de citer un texte pertinent du livre:

• Pour simplifier, considérons un problème à deux catégories, où l'ensemble d'apprentissage compose de motifs et d'étiquettes de catégorie associées pour générées par la fonction cible inconnue à apprendre, , où .$D$$x^i$$y_i = ± 1$$i = 1,..., n$$F(x)$$y_i = F(x^i)$
• Soit le jeu (discret) d'hypothèses ou les jeux de paramètres possibles à apprendre. Une hypothèse particulière pourrait être décrite par des poids quantifiés dans un réseau neuronal, ou des paramètres 0 dans un modèle fonctionnel, ou des ensembles de décisions dans un arbre, et ainsi de suite.$H$$h(x) \in H$
• De plus, est la probabilité antérieure que l'algorithme produise l'hypothèse après l'entraînement; notez que ce n'est pas la probabilité que soit correct.$P(h)$$h$$h$
• Ensuite, indique la probabilité que l'algorithme donnera l' hypothèse quand une formation sur les données . Dans les algorithmes d'apprentissage déterministes tels que le plus proche voisin et les arbres de décision, sera partout nul sauf pour une seule hypothèse . Pour les méthodes stochastiques (telles que les réseaux de neurones formés à partir de poids initiaux aléatoires), ou l'apprentissage Boltzmann stochastique, peut être une large distribution.$P(h|D)$$h$$D$$P(h|D)$$h$$P(h|D)$
• Soit l'erreur pour une fonction de perte nulle ou autre.$E$

L'erreur de classification attendue hors ensemble d'apprentissage lorsque la fonction vraie est et la probabilité pour le ème algorithme d'apprentissage candidat est est donnée park P k ( h ( x ) | D ) E k ( E $F(x)$$k$$P_k(h(x)|D)$

$$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D)$$

Théorème 9.1. (Pas de déjeuner gratuit) Pour deux algorithmes d'apprentissage et P_2 (h | D) , les éléments suivants sont vrais, indépendamment de la distribution d'échantillonnage P (x) et du nombre n de points d'apprentissage:P 2 ( h | D ) P ( x ) $P_1 (h |D)$$P_2(h|D)$$P(x)$$n$

1. Moyenne uniforme sur toutes les fonctions cibles ,$F$$\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. Pour tout ensemble d'entraînement fixe , moyenné uniformément sur , $D$$F$$\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

La partie 1 dit en fait

$$\sum_F \sum_D P(D|F) [\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n)] = 0$$

La partie 2 dit en fait

$$\sum_F [\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D)] = 0$$

Mes questions sont

1. Dans la formule de , c'est-à-dire puis-je remplacer par et le déplacer en dehors de la somme , parce que c'est vraiment une distribution de sur étant donné pour le ème algorithme d'apprentissage stochastique?$\mathcal{E}_k(E|F,n)$ $$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D),$$ $P_k(h(x)|D)$$P_k(h|D)$$\sum_{x \notin D}$$h$$H$$D$$k$
2. Étant donné que le ème algorithme d'apprentissage candidat est une méthode stochastique, pourquoi dans la formule de , il n'y a pas de somme sur , c'est-à-dire ?$k$$\mathcal{E}_k(E|F,n)$$h$$\sum_{h \in H}$

3. En quoi et différents l'un de l'autre?$\mathcal{E}_i (E|F, D)$$\mathcal{E}_i (E|F, n)$

   Est : le taux d'erreur hors formation étant donné un ensemble de formation ?$\mathcal{E}_i (E|F, D)$$D$

   Est signifie que le taux d'erreur hors formation, en moyenne sur l' ensemble de la formation donnée ensemble une taille de formation ? Si oui, pourquoi la partie 1 du théorème NFL fait-elle une moyenne sur les ensembles d'entraînement en écrivant à nouveau , et pourquoi dans la formule pour , il n'y a pas de moyenne sur tous les ensembles d'entraînement étant donné une taille d'entraînement ?$\mathcal{E}_i (E|F, n)$$n$$\mathcal{E}_i (E|F, n)$$\sum_D$$\mathcal{E}_k(E|F,n)$$n$

4. Dans la partie 1 du théorème de la NFL, signifie- -il la somme de tous les ensembles d'entraînement avec une taille d'entraînement fixe ?$\sum_D$$n$
5. Si l'on additionne davantage toutes les valeurs possibles dans de taille d'entraînement dans la partie 1, le résultat est toujours 0, non?$\mathbb{N}$$n$
6. Dans la formule de , si je change en , c'est-à-dire que n'est pas nécessairement limité à être en dehors de l'ensemble d'apprentissage, les deux parties de Le théorème de la NFL est-il toujours vrai?$\mathcal{E}_k(E|F,n)$$\sum_{x \notin D}$$\sum_x$$x$
7. Si la vraie relation entre et n'est pas supposée être une fonction déterministe comme , mais plutôt des distributions conditionnelles , ou une distribution conjointe qui est équivalente à connaissant et (voir aussi ma autre question ), alors je peux changer pour être (avec l'étrange indiqué dans les parties 1 et 2). Les deux parties du théorème de la NFL sont-elles toujours vraies?$x$$y$$F$$y=F(x)$$P(y|x)$$P(x,y)$$P(y|x)$$P(x)$$\mathcal{E}_k (E|F,n)$ $$\mathcal{E}_k(E|P(x,y),n) = \mathcal{E}_{x,y} [1-\delta(y, h(x))] P_k(h(x)|D)$$ $P_k(h(x)|D)$

Merci et salutations!

Je répondrai aux questions auxquelles je pense connaître les réponses.

1. Cette réponse est non parce que vous choisissez un qui ne faisait pas partie de l'ensemble d'ajustement et donc dépend de .$x$$D$$h$$x$
2. $h$ n'est évalué qu'aux valeurs de l'ensemble de test pour obtenir le taux d'erreur attendu, il n'est donc pas évalué sur l'ensemble mais uniquement sur l'ensemble discret de dans l'ensemble de test.$x$$H$$x$
3. $\mathcal{E}_i(E|F, D)$ est le taux prévu hors d'erreur de jeu de formation compte tenu de la fonction et l'ensemble de la formation . Mais je pense que c'est différent parce que vous ne conditionnez que le nombre de points d'entraînement et non les valeurs réelles . Mais c'est déroutant compte tenu des déclarations ultérieures.$F$$D$$\mathcal{E}_i(E|F, n)$$n$$x$
4. $D$ est l'ensemble des vecteurs d'apprentissage. Il existe vecteurs de formation en . Donc , vous sommant sur les fixes vecteurs formation en . Il n'y a qu'un seul jeu .$n$$D$$n$$D$$D$
5. Je pense que la réponse à 5 est non. La notation semble être un peu déroutante.

Je ne peux pas commenter 6 et 7.