Théorème d'approximation universelle

Dans la théorie mathématique des réseaux de neurones artificiels, le théorème d'approximation universelle indique qu'un réseau à propagation avant d'une seule couche cachée contenant un nombre fini de neurones (c'est-à-dire, un perceptron multicouche) peut approximer des fonctions continues sur des sous-ensembles compacts de Rⁿ.

Histoire

Une des premières versions du cas avec largeur arbitraire a été prouvé par George Cybenko (en) en 1989 pour des fonctions d'activation sigmoïdes^[1]. Kurt Hornik a montré en 1991^[2] que ce n'est pas le choix spécifique de la fonction d'activation, mais plutôt l'architecture multi-couches à propagation avant elle-même qui donne aux réseaux de neurones le potentiel d'être des approximateurs universels. Moshe Leshno et al en 1993^[3] et plus tard Allan Pinkus en 1999^[4] ont montré que la propriété d'approximation universelle est équivalente à l'utilisation d'une fonction d'activation non-polynomiale.

Le cas avec profondeur arbitraire a aussi été étudié par nombre d'auteurs, comme Zhou Lu et al en 2017^[5], Boris Hanin et Mark Sellke en 2018^[6], et Patrick Kidger et Terry Lyons en 2020^[7]. Le résultat sur la largeur minimale par couche a été raffiné en 2020^[8],[9] pour les réseaux résiduels.

Plusieurs extensions du théorème existent, comme celle à des fonctions d'activation discontinues^[3], à des domaines non compacts^[7], à des réseaux certifiables^[10], et à des architectures de réseaux et des topologies alternatives^[7],[11].

Cas avec largeur arbitraire

On note ${\displaystyle C(X,Y)}$ l'ensemble des fonctions continues d'un ensemble ${\displaystyle X}$ vers un ensemble ${\displaystyle Y}$. La forme classique du théorème d'approximation universelle pour une largeur arbitraire et une profondeur bornée est la suivante^{[1],[2],[12],[13]}. Elle étend^[4] les résultats classiques de George Cybenko (en) and Kurt Hornik (en).

Théorème d'approximation universelle. Soit ${\displaystyle \sigma \in C(\mathbb {R} ,\mathbb {R} )}$. Notons que ${\displaystyle (\sigma \circ x)_{i}=\sigma (x_{i})}$, c'est-à-dire que ${\displaystyle \sigma \circ x}$ représente l'application de ${\displaystyle \sigma }$ à chacune des composantes de ${\displaystyle x}$^[pas clair].

Alors ${\displaystyle \sigma }$ n'est pas polynomiale si et seulement si pour tout ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle m\in \mathbb {N} }$, pour tout sous-espace compact ${\displaystyle K\subseteq \mathbb {R} ^{n}}$, pour tout ${\displaystyle f\in C(K,\mathbb {R} ^{m})}$ et pour tout ${\displaystyle \varepsilon >0}$, il existe ${\displaystyle k\in \mathbb {N} }$, ${\displaystyle A\in \mathbb {R} ^{k\times n}}$, ${\displaystyle b\in \mathbb {R} ^{k}}$ et ${\displaystyle C\in \mathbb {R} ^{m\times k}}$, tels que :$${\displaystyle \sup _{x\in K}\|f(x)-g(x)\|<\varepsilon }$$ où $${\displaystyle g(x)=C\cdot (\sigma \circ (A\cdot x+b))}$$

Une telle fonction ${\displaystyle f}$ peut également être approximée par un réseau de plus grande profondeur en utilisant la même construction pour les deux premières couches ${\displaystyle A}$ et ${\displaystyle C}$ et en utilisant la fonction identité pour les couches ultérieures.

Cas avec profondeur arbitraire

Les versions 'duales' du théorème considèrent des réseaux de largeur bornée et de profondeur arbitraire. Une variante du théorème d'approximation universelle a été prouvée pour le cas de la profondeur arbitraire par Zhou Lu et al. en 2017^[5]. Ils ont montré que les réseaux de largeur n+4 avec fonction d'activation ReLU peuvent approximer n'importe quelle fonction intégrable au sens de Lebesgue sur un espace d'entrée de dimension n muni de la distance ${\displaystyle L^{1}}$ à condition d'autoriser la profondeur du réseau à croître. Il a aussi été montré que si la largeur était inférieure ou égal à n, cette possibilité générale d'approximer toute fonction intégrable au sens de Lebesgue était perdue. Dans le même article ^[5] il est montré que les réseaux ReLU de largeur n+1 sont suffisants pour approximer n'importe quelle fonction continue à variables d'entrée de dimension n^[14]. Le raffinement suivant précise la largeur minimale optimale pour laquelle une telle approximation est possible et est dû à Sejun Park et al.^[15]

Théorème d'approximation universelle (distance L1, activation ReLU, profondeur arbitraire, largeur minimale). Pour toute fonction Bochner–Lebesgue p-integrable ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}$ et tout ${\displaystyle \epsilon >0}$, il existe un réseau ReLU entièrement connecté (en) ${\displaystyle F}$ de largeur exactement ${\displaystyle d_{m}=\max\{{n+1},m\}}$, satisfaisant:

${\displaystyle \int _{\mathbb {R} ^{n}}\left\|f(x)-F_{}(x)\right\|^{p}\mathrm {d} x<\epsilon }$.

En outre, il existe une fonction ${\displaystyle f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})}$ et un certain ${\displaystyle \epsilon >0}$, pour lesquels il n'existe pas de réseau ReLU entièrement connecté de largeur inférieure à ${\displaystyle d_{m}=\max\{{n+1},m\}}$ satisfaisant la borne d'approximation ci-dessus.

Par ailleurs, le résultat central de ^[7] fournit le théorème d'approximation universelle suivant pour les réseaux à largeur bornée:

Théorème d'approximation universelle (activation non-affine, profondeur arbitraire, largeur constrainte). Soit ${\displaystyle {\mathcal {X}}}$ un sous-ensemble compact de ${\displaystyle \mathbb {R} ^{d}}$. Soit ${\displaystyle \sigma$ :\mathbb {R} \to \mathbb {R} } une transformation non-affine continue qui soit continûment différentiable en au moins un point, avec des dérivées non nulles en ce point. Soit ${\displaystyle {\mathcal {N}}_{d,D:d+D+2}^{\sigma }}$ l'espace des réseaux de neurones à propagation avant ayant ${\displaystyle d}$ neurones d'entrée, ${\displaystyle D}$ neurones de sortie, et un nombre arbitraire de couches cachées, chacune ayant ${\displaystyle d+D+2}$ neurones, et telles que tout neurone caché ait ${\displaystyle \sigma }$ comme fonction d'activation et que tout neurone de sortie ait l'identité comme fonction d'activation.

Alors pour tout ${\displaystyle \varepsilon >0}$ et tout ${\displaystyle f\in C({\mathcal {X}},\mathbb {R} ^{D})}$, il existe ${\displaystyle {\hat {f}}\in {\mathcal {N}}_{d,D:d+D+2}^{\sigma }}$ telle que:

${\displaystyle \sup _{x\in {\mathcal {X}}}\,\left\|{\hat {f}}(x)-f(x)\right\|<\varepsilon .}$

En d'autres termes, ${\displaystyle {\mathcal {N}}}$ est dense dans ${\displaystyle C({\mathcal {X}};\mathbb {R} ^{D})}$ muni de la topologie de la convergence uniforme.

Certaines conditions nécessaires pour le cas largeur bornée, profondeur arbitraire ont été établies, mais il y a encore un écart entre les conditions nécessaires et les conditions suffisantes connues^[5],[6],[16].

Informatique quantique

Les réseaux de neurones quantiques peuvent être exprimés par différents outils mathématiques pour les circuits ordinateurs quantiques, allant du perceptron quantique aux circuits quantiques variationnels, tous deux basés sur des combinaisons de portes logiques quantiques. Les circuits quantiques variationnels sont basés sur un circuit paramétrique, n'impliquant pas de réseaux de neurones. Au lieu de cela, le perceptron quantique permet la conception d'un réseau de neurones quantiques avec la même structure que les réseaux de neurones à réaction, à condition que le comportement de seuil de chaque nœud n'implique pas l'effondrement de l'état quantique, c'est-à-dire aucun processus de mesure. En 2022, un tel bloc de construction sans mesure fournissant le comportement de la fonction d'activation pour les réseaux de neurones quantiques a été conçu ^[17]. Le circuit quantique renvoie une approximation arbitraire des fonctions d'écrasement dans l'intervalle de -1 à +1, ce qui est pertinent pour les qubits. Une telle méthode pour concevoir des fonctions d'activation quantiques arbitraires permet des multi-perceptrons quantiques et des réseaux de neurones à réaction quantique en général.

Notes et références

1. G. Cybenko, « Approximation by superpositions of a sigmoidal function », Mathematics of Control, Signals, and Systems, vol. 2, n^o 4,‎ 1989, p. 303–314 (DOI 10.1007/BF02551274, S2CID 3958369, CiteSeer^x 10.1.1.441.7873)
2. Kurt Hornik, « Approximation capabilities of multilayer feedforward networks », Neural Networks, vol. 4, n^o 2,‎ 1991, p. 251–257 (DOI 10.1016/0893-6080(91)90009-T)
3. Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus et Shimon Schocken, « Multilayer feedforward networks with a nonpolynomial activation function can approximate any function », Neural Networks, vol. 6, n^o 6,‎ janvier 1993, p. 861–867 (DOI 10.1016/S0893-6080(05)80131-5, S2CID 206089312)
4. Allan Pinkus, « Approximation theory of the MLP model in neural networks », Acta Numerica, vol. 8,‎ janvier 1999, p. 143–195 (DOI 10.1017/S0962492900002919, Bibcode 1999AcNum...8..143P)
5. Zhou Lu, Homgming Pu, Feicheng Wang, Zhiqiang Hu et Liwei Wang, « The Expressive Power of Neural Networks: A View from the Width », Curran Associates, vol. 30,‎ 2017, p. 6231–6239 (arXiv 1709.02540, lire en ligne)
6. Boris Hanin et Mark Sellke, « Approximating Continuous Functions by ReLU Nets of Minimal Width », MDPI, vol. 7, n^o 10,‎ mars 2019, p. 992 (DOI 10.3390/math7100992 , arXiv 1710.11278)
7. Patrick Kidger et Terry Lyons « Universal Approximation with Deep Narrow Networks » (Juillet 2020) (arXiv 1905.08539)
   —Conference on Learning Theory
8. Sejun Park, Chulhee Yun, Jaeho Lee et Jinwoo Shin « Minimum Width for Universal Approximation » (Octobre 2020) (arXiv 1905.08539)
   —Conference on Learning Theory
9. Paulo Tabuada et Bahman Gharesifard « Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theory » (2020) (arXiv 2007.06007)
   —ICLR
10. Maximilian Baader, Matthew Mirman et Martin Vechev « Universal Approximation with Certified Networks » (2020) (lire en ligne)
    —ICLR
11. Hongzhou Lin et Stefanie Jegelka « ResNet with one-neuron hidden layers is a Universal Approximator » (2018) (lire en ligne)
    — « (ibid.) », Advances in Neural Information Processing Systems, Curran Associates, vol. 30,‎ 2018, p. 6169–6178
12. Haykin, Simon (1998). Neural Networks: A Comprehensive Foundation, Volume 2, Prentice Hall. (ISBN 0-13-273350-1).
13. Hassoun, M. (1995) Fundamentals of Artificial Neural Networks MIT Press, p. 48
14. Hanin, B. (2018). Approximating Continuous Functions by ReLU Nets of Minimal Width. arXiv preprint arXiv:1710.11278.
15. (en) Sejun, Chulhee, Jaeho, Jinwoo Park, Yun, Lee, Shin, « Minimum Width for Universal Approximation », ICLR,‎ 28 septembre 2020 (arXiv 2006.08859, lire en ligne)
16. Jesse Johnson « Deep, Skinny Neural Networks are not Universal Approximators » (2019) (lire en ligne)
    —International Conference on Learning Representations
17. Marco Maronese, Claudio Destri et Enrico Prati, « Quantum activation functions for quantum neural networks », Springer, vol. 21, n^o 4,‎ 2022, p. 1-24 (DOI 10.1007/s11128-022-03466-0, arXiv 2201.03700, lire en ligne)

• Portail des mathématiques
• Portail de l'informatique théorique