EML Trees Are Universal Approximators

Résumé technique : Les arbres EML sont des approximateurs universels

Énoncé du problème
L'article traite de la question de savoir si les compositions structurées en arbres de la fonction Exp-Minus-Log (EML) récemment introduite possèdent un pouvoir expressif suffisant pour servir d'approximateurs universels pour les fonctions lisses. Bien que des travaux antérieurs [22] aient démontré que les compositions EML peuvent représenter exactement toute fonction élémentaire (y compris les fonctions trigonométriques et exponentielles) via une construction symbolique explicite, il restait une question théorique ouverte de savoir si ces structures pouvaient approximer des fonctions arbitraires dans les espaces de Sobolev $W^{k,\infty}$ avec des bornes d'erreur quantifiables. De plus, l'article examine si la fonction EML généralisée, dotée de paramètres apprenables, peut être optimisée efficacement dans un espace de paramètres continu, se distinguant ainsi de la récupération symbolique discrète explorée dans la littérature antérieure.

Méthodologie
Les auteurs développent une théorie d'approximation rigoureuse pour les arbres EML à travers une stratégie de preuve constructive qui combine l'approximation polynomiale locale avec des représentations algébriques explicites.

1. Fonction EML généralisée : L'étude introduit un atome EML généralisé, $EML_{\theta_i}(x,y) = a_i e^{b_i x + c_i} + d_i \ln(e_i y + f_i)$, incorporant six paramètres apprenables par unité. Cette généralisation permet le codage direct des coefficients, évitant ainsi la nécessité de construire récursivement des constantes à partir du chiffre 1, ce qui entraînerait autrement une mauvaise mise à l'échelle de la taille de l'arbre.
2. Cadre d'approximation constructive : La preuve du théorème d'approximation universelle repose sur un processus en trois étapes :
   • Localisation : Le domaine $(0,1]^d$ est partitionné en petits cubes. En utilisant le lemme de Bramble–Hilbert, des approximants polynomiaux locaux sont construits pour la fonction cible sur des cubes chevauchants.
   • Lissage : Pour éviter les discontinuités inhérentes au raccordement de polynômes locaux avec des fonctions indicatrices, les auteurs construisent une « partition de l'unité approximative » lisse en utilisant des fonctions tangente hyperbolique ($\tanh$) décalées et mises à l'échelle.
   • Construction explicite : Les auteurs démontrent que les opérations algébriques requises (addition, soustraction, multiplication, division, exponentiation) ainsi que la fonction $\tanh$ elle-même peuvent être représentées exactement par des arbres EML. En composant ces « blocs », ils construisent un arbre EML qui représente exactement l'approximation polynomiale lissée globale.
3. Gestion des singularités : Puisque le logarithme naturel n'est pas défini pour des arguments non positifs, les résultats théoriques sont initialement établis sur le domaine semi-ouvert $(0,1]^d$. Les auteurs étendent ces résultats au domaine fermé $[0,1]^d$ en composant les approximants avec une application de contraction affine qui pousse le domaine vers l'intérieur, contrôlant ainsi les effets de bord.
4. Validation empirique : Les auteurs implémentent un algorithme d'apprentissage pour les arbres de type EML en utilisant l'optimisation basée sur le gradient (Adam suivi de L-BFGS). Ils testent le modèle sur cinq fonctions de référence unidimensionnelles, comparant les paramétrages à valeurs réelles et complexes.

Contributions clés

• Théorème d'approximation universelle : L'article prouve que les arbres EML sont des approximateurs universels pour les fonctions dans l'espace de Sobolev $W^{k,\infty}((0,1]^d)$. Le théorème fournit des bornes supérieures explicites sur la taille (nombre d'atomes) et la profondeur de l'arbre EML requis pour atteindre une erreur d'approximation spécifique, évoluant de manière polynomiale avec l'inverse de l'erreur et la dimension.
• Extension aux domaines fermés : Un corollaire étend les garanties d'approximation au cube fermé $[0,1]^d en utilisant une contraction affine pour éviter la singularité logarithmique en zéro.
• Paramétrage généralisé : L'introduction d'une fonction EML généralisée à six paramètres facilite les représentations plus compactes d'opérateurs et permet le codage direct des coefficients, ce qui est crucial pour la preuve constructive et l'optimisation pratique.
• Construction explicite d'opérateurs : Le travail fournit des constructions détaillées pour représenter les opérations élémentaires (addition, multiplication, etc.) et la fonction $\tanh$ en utilisant des arbres EML, établissant les blocs de composition nécessaires à la théorie de l'approximation.

Résultats

• Théoriques : L'article établit que pour toute fonction $f \in W^{s,\infty}([0,1]^d)$, il existe un arbre EML $\tilde{p}_N^\theta$ tel que l'erreur d'approximation dans la norme $W^{k,\infty}$ décroît comme $O(N^{-(s-k)})$, où $N$ est lié à la résolution de la partition du domaine. La taille et la profondeur de l'arbre sont bornées par des fonctions de la dimension $d$, de la régularité $s$ et de la résolution cible.
• Empiriques : Dans les expériences sur des cibles unidimensionnelles (polynômes, $\tanh$, $\sin$, Gaussienne et sinus modulé), les arbres EML généralisés ont atteint une RMSE relative inférieure à un pour cent sur la plupart des cibles à une profondeur de 4, avec un budget de calcul fixe.
  • Les paramétrages à valeurs réelles étaient suffisants pour les cibles polynomiales et de tangente hyperbolique.
  • Les paramétrages à valeurs complexes ont fourni un avantage mesurable pour les cibles hautement oscillatoires (ex: $\sin(3x)e^{-x^2/2}$), probablement en raison de la capacité à représenter exactement les fonctions trigonométriques via l'identité d'Euler.
  • Limite d'interprétabilité : Une analyse de « capture gloutonne » (greedy snap) a révélé que les paramètres continus appris ne convergeaient pas vers les configurations symboliques discrètes (ex: $\{0, \pm 1\}$) prédites par la preuve constructive. Seule une petite fraction des paramètres s'est fixée sur des valeurs discrètes, et aucun atome n'est devenu entièrement discret. Cela suggère que, bien que les arbres approchent avec précision les valeurs de la fonction, ils ne récupèrent pas nécessairement la structure symbolique spécifique dérivée de la preuve théorique.

Signification et affirmations
L'article affirme établir les arbres EML comme un « cadre théoriquement fondé pour l'approximation de fonctions ». En comblant le fossé entre l'exactitude symbolique de la représentation des fonctions élémentaires et l'apprentissage statistique de paramètres continus, ce travail fournit une justification rigoureuse de la capacité d'expression des architectures basées sur l'EML.

Les auteurs restent modestes quant aux implications pratiques de leurs résultats empiriques. Ils déclarent explicitement que l'étude sert de « test de cohérence » (sanity check) pour la capacité pratique des arbres EML plutôt qu'une validation complète des taux de convergence du théorème d'approximation. Ils reconnaissent que les modèles appris fonctionnent comme des approximateurs continus plutôt que comme des reconstructions symboliques, notant que la récupération de la structure symbolique discrète nécessiterait une régularisation structurelle supplémentaire ou des biais inductifs, ce qui est laissé à de futures investigations. Ce travail relie les arbres EML à la littérature plus large sur l'approximation universelle dans les réseaux de neurones, les réseaux de neurones informés par la physique et la régression symbolique, les positionnant comme une alternative viable pour une approximation de fonctions interprétable et expressive.