Théorème d'approximation universelle

Le résultat de Cybenko est assez intuitif, comme j'espère le transmettre ci-dessous; ce qui rend les choses plus difficiles, c'est qu'il visait à la fois la généralité et un nombre minimal de couches cachées. Le résultat de Kolmogorov (mentionné par vzn) obtient en fait une garantie plus forte, mais est un peu moins pertinent pour l'apprentissage automatique (en particulier, il ne construit pas un réseau neuronal standard, car les nœuds sont hétérogènes); ce résultat est à son tour décourageant car en surface, il ne s'agit que de 3 pages enregistrant des limites et des fonctions continues, mais en réalité, il construit un ensemble de fractales. Bien que le résultat de Cybenko soit inhabituel et très intéressant en raison des techniques exactes qu'il utilise, les résultats de cette saveur sont très largement utilisés dans l'apprentissage automatique (et je peux vous en indiquer d'autres).

Voici un résumé de haut niveau des raisons pour lesquelles le résultat de Cybenko devrait tenir.

Une fonction continue sur un ensemble compact peut être approximée par une fonction constante par morceaux.
Une fonction constante par morceaux peut être représentée comme un réseau neuronal comme suit. Pour chaque région où la fonction est constante, utilisez un réseau neuronal comme fonction d'indicateur pour cette région. Construisez ensuite une couche finale avec un seul nœud, dont la combinaison linéaire d'entrée est la somme de tous les indicateurs, avec un poids égal à la valeur constante de la région correspondante dans la fonction constante par morceaux d'origine.

En ce qui concerne le premier point ci-dessus, cela peut être considéré comme l'énoncé "une fonction continue sur un ensemble compact est uniformément continue". Ce que cela signifie pour nous, c'est que vous pouvez prendre votre fonction continue sur , et une erreur cible , puis vous pouvez mailler à l'échelle (pour finir avec environ cubes) de sorte qu'une fonction constante sur chaque sous-cube se trouve à moins de de la fonction cible. $[0,1]^d$ $\epsilon>0$ $[0,1]^d$ $\tau>0$ $(1/\tau)^d$ $\epsilon$

Maintenant, un réseau neuronal ne peut pas représenter précisément un indicateur, mais vous pouvez vous en approcher très près. Supposons que la "fonction de transfert" soit un sigmoïde. (La fonction de transfert est la fonction continue que vous appliquez à une combinaison linéaire d'entrées afin d'obtenir la valeur du nœud de réseau neuronal.) Ensuite, en rendant les poids énormes, vous produisez quelque chose près de 0 ou près de 1 pour plus d'entrées. Cela est cohérent avec le développement de Cybenko: notez qu'il a besoin que les fonctions impliquées soient égales à 0 ou 1 dans la limite: par définition de limite, vous obtenez exactement ce que je dis, ce qui signifie que vous poussez les choses arbitrairement près de 0 ou 1.

(J'ai ignoré la fonction de transfert dans la couche finale; si elle est là, et qu'elle est continue, alors nous pouvons adapter tout mappage à en remplaçant les poids constants par quelque chose dans l'image inverse de cette constante en fonction du transfert une fonction.) $[0,1]$

Notez que ce qui précède peut sembler prendre quelques couches: disons, 2 pour construire les indicateurs sur des cubes, puis une couche de sortie finale. Cybenko cherchait deux points de généralité: un nombre minimal de couches cachées et une flexibilité dans le choix de la fonction de transfert. J'ai déjà décrit comment il travaille la flexibilité dans la fonction de transfert.

Pour obtenir le nombre minimum de couches, il évite la construction ci-dessus, et utilise plutôt l'analyse fonctionnelle pour développer une contradiction. Voici un croquis de l'argument.

Le nœud final calcule une combinaison linéaire des éléments de la couche située en dessous et lui applique une fonction de transfert. Cette combinaison linéaire est une combinaison linéaire de fonctions, et en tant que telle, elle-même est une fonction, une fonction dans un sous-espace de fonctions, recouvert par les nœuds possibles dans la couche cachée.
Un sous-espace de fonctions est exactement comme un sous-espace de dimension finie ordinaire, avec la principale différence qu'il n'est potentiellement pas un ensemble fermé; c'est pourquoi les arguments de cybenko prennent tous la fermeture de ce sous-espace. Nous essayons de prouver que cette fermeture contient toutes les fonctions continues; cela signifie que nous sommes arbitrairement proches de toutes les fonctions continues.
Si l'espace de fonction était simple (un espace de Hilbert), nous pourrions argumenter comme suit. Choisissez une fonction continue cible qui est supposée contradictoirement ne pas se trouver dans le sous-espace et projetez-la sur le complément orthogonal du sous-espace. Ce résidu doit être différent de zéro. Mais comme notre sous-espace peut représenter des choses comme ces petits cubes ci-dessus, nous pouvons trouver une région de ce résidu, y ajuster un petit cube (comme ci-dessus), et ainsi nous rapprocher de notre fonction cible. C'est une contradiction puisque les projections choisissent des éléments minimaux. (Remarque, je laisse quelque chose ici: l'argument de Cybenko ne construit pas de petits cubes, il le gère également en général; c'est là qu'il utilise une forme du théorème de représentation de Riesz et les propriétés des fonctions de transfert (si je me souviens bien correctement, il existe un lemme distinct pour cette étape,
Nous ne sommes pas dans un espace de Hilbert, mais nous pouvons utiliser le théorème de Hahn-Banach pour remplacer l'étape de projection ci-dessus (note, prouver que Hahn-Banach utilise l'axiome de choix).

J'aimerais maintenant dire quelques mots sur le résultat de Kolmogorov. Bien que ce résultat n'ait apparemment pas besoin du type de contexte de Cybenko, je pense personnellement qu'il est beaucoup plus intimidant.

$\mathcal O(d^2)$

D'accord, alors avec tout ça, comment cette chose peut-elle fonctionner?!

$\epsilon>0$ $\tau >0$

$[0,1]$ $[0,1]^d$ $\mathcal O(d^2)$ $\mathbb{R}^d$ $\mathbb R$ $\mathcal O(d^2)$

Notez que le résultat de Cybenko, en raison de l'utilisation d'un seul type de fonction de transfert, est plus pertinent pour l'apprentissage automatique. Les théorèmes de ce type sont très courants dans l'apprentissage automatique (vzn l'a suggéré dans sa réponse, mais il a fait référence au résultat de Kolmogorov, qui est moins applicable en raison des fonctions de transfert personnalisées; cela est affaibli dans certaines versions plus fantaisistes du résultat de Kolmogorov (produit par autres auteurs), mais celles-ci impliquent encore des fractales, et au moins deux fonctions de transfert).

J'ai quelques diapositives sur ces sujets, que je pourrais publier si vous êtes intéressé (avec moins de chance, je l'espère, et j'ai quelques photos; je les ai écrites avant d'être adepte de Hahn-Banach, cependant). Je pense que les deux preuves sont très, très belles. (Aussi, j'ai une autre réponse ici sur ces sujets, mais je l'ai écrite avant d'avoir grokké le résultat de Kolmogorov.)

matus
la source

A

$A$

B

$B$

ϕ

$\phi$

\forall f \in A : ϕ (f) \leq 1

$\forall f \in A: \phi(f) \leq 1$

\forall g \in B : ϕ (g) > 1

$\forall g \in B: \phi(g) > 1$

Sasho Nikolov

S

$S$

f \notin S

$f\not\in S$

L

$L$

L (g) = 0

$L(g) = 0$

g \in S

$g \in S$

L (f) = ‖ f ‖

$L(f) = \|f\|$

L (f)

$L(f)$ comme partie intégrante d'une mesure signée. Mais cela termine la preuve en raison des conditions de Cybenko sur les fonctions de transfert (suite dans le commentaire suivant).

matus

@SashoNikolov, la condition de Cybenko est que, compte tenu de toute mesure signée qui n'est pas exactement zéro, il existe une fonction affine de sorte que l'intégration de la fonction de transfert composée avec cette fonction affine, sur cette mesure, n'est pas égale à zéro. Il doit ensuite prouver le lemme selon lequel les sigmoïdes généralisés (comme je l'ai dit ci-dessus: limites à 0 et 1 à gauche et à droite) conviennent. (suite dans le commentaire suivant.)

matus

@SashoNikolov. Ci-dessus, j'ai dit "laisser tomber un cube le long du résidu". Cela rendrait notre travail un peu plus facile, puisque la mesure signée n'est pas exactement zéro, nous choisirions simplement un petit morceau et y placerions un indicateur. Dans son cas, il doit travailler un peu, mais de la même manière, cela se résume à se déplacer dans le sigmoïde avec la fonction affine afin qu'il trouve une région facile, obtenant ainsi une intégrale non nulle, contredisant Hahn-Banach (qui est zéro sur notre sous-espace) ; au sens de Hilbert, nous avons réduit notre résidu, une contradiction.

matus

Wow, c'est une réponse extrêmement agréable. Naturellement, j'ai quelques questions si cela ne vous dérange pas d'y répondre. Le résultat de Cybenko (comme vous le dites) semble le plus utile pour les applications, mais je m'égare un peu avec le sous-espace des fonctions. Comment projeter une fonction continue arbitraire sur le complément orthogonal du sous-espace de combinaisons linéaires de nœuds possibles. D'ailleurs, comment conceptualiser le complément orthogonal de ce sous-espace? Les fonctions plus proches dans l'espace se rapprochent-elles plus étroitement? (A continué).

Matt Munson

Il existe un résultat avancé, clé de l'apprentissage automatique, connu sous le nom de théorème de Kolmogorov [1]; Je n'ai jamais vu d'esquisse intuitive de pourquoi cela fonctionne. Cela peut avoir à voir avec les différentes cultures qui l'approchent. La foule d'apprentissage appliqué considère le théorème de Kolmogorov comme un théorème d'existence qui indique simplement que des NN peuvent exister, donc au moins la structure n'est pas trop limitative, mais le théorème ne garantit pas que ces NN peuvent être trouvés. Les mathématiciens ne se préoccupent pas autant des applications de bas niveau du théorème.

Le théorème a également été historiquement utilisé pour invoquer / défendre la sophistication inhérente des NN multicouches pour contrer une critique de Perceptrons (Minsky / Papert) selon laquelle il y avait des fonctions de base [c.-à-d. Non linéaires] qu'ils ne pouvaient pas apprendre.

Les informaticiens théoriques préfèrent ne pas considérer les NN comme des "approximations" , car ce terme a une signification spéciale / différente. Il y a probablement une analogie approximative avec une interpolation linéaire par morceaux, mais encore une fois, je ne l'ai pas vue présentée.

[1] Kolmogorov, AN (1957). Sur la représentation des fonctions continues de nombreuses variables par superposition de fonctions continues d'une variable et addition. Doklady Akademii Nauk SSSR, 144, 679-681; Traduction de l'American Mathematical Society, 28, 55-59 [1963]

[2] 2.3 Capacités d'approximation des réseaux de neurones à action directe pour les fonctions continues

[3] Théorème de Kolmogorov et réseaux de neurones multicouches Kurkova

vzn
la source

voir aussi les algorithmes d'approximation des techniques d'apprentissage automatique? , stats.se

vzn

"ce résultat avancé [...] n'a pas vu une esquisse intuitive de pourquoi cela fonctionne." Une telle esquisse serait-elle une entreprise considérable pour quelqu'un dans le monde avancé des mathématiques? Les mathématiciens avancés comprennent-ils même intuitivement pourquoi cela fonctionne? Il semble qu'une compréhension intuitive de ce théorème soit quelque chose que la foule d'apprentissage appliqué devrait fortement désirer, si elle veut concevoir des topologies et des algorithmes d'apprentissage supérieurs pour les ANN.

Matt Munson

Modifié pour la grammaire, l'orthographe, la ponctuation et la capitalisation.

Jeffε

Théorème d'approximation universelle - Réseaux de neurones

Réponses: