Fourier Analysis on the Boolean Hypercube via Hoeffding Functional Decomposition

Each language version is independently generated for its own context, not a direct translation.

Le Titre : "Décomposer la recette du gâteau quand les ingrédients ne sont pas indépendants"

Imaginez que vous êtes un chef cuisinier (ou un data scientist) qui essaie de comprendre pourquoi un gâteau a un certain goût. Vous avez une liste d'ingrédients (les variables) : farine, sucre, œufs, chocolat, etc.

1. Le problème de départ : La recette "parfaite" mais irréaliste

Dans le monde idéal des mathématiques (ce qu'on appelle l'analyse de Fourier sur l'hypercube booléen), on suppose que tous les ingrédients sont indépendants et qu'on les utilise tous avec la même probabilité. C'est comme si, dans une usine de gâteaux géante, on mélangeait au hasard de la farine, du sucre et du chocolat, sans aucune règle.

L'outil classique : On utilise une "recette magique" (la base de Walsh-Hadamard) pour dire : "Ah, le goût vient à 30% du sucre, 20% du chocolat, et 10% de l'interaction entre le sucre et le chocolat".
Le souci : Dans la vraie vie (les données réelles), les ingrédients ne sont pas indépendants !
- Si vous mettez du chocolat, vous mettez rarement du sel (corrélation négative).
- Si vous faites un gâteau "one-hot" (une catégorie unique parmi plusieurs, comme "Rouge", "Vert" ou "Bleu"), vous ne pouvez pas avoir "Rouge" et "Vert" en même temps. C'est une contrainte stricte.
- Résultat : La recette magique classique se trompe. Elle ne comprend pas que certains ingrédients sont liés.

2. La solution du papier : La "Décomposition Hoeffding" (HFD)

Les auteurs (Baptiste Ferrere et son équipe) disent : "Arrêtons de forcer la recette classique. Utilisons plutôt une méthode plus flexible appelée Décomposition Fonctionnelle de Hoeffding (HFD)."

Imaginez que la HFD est un détective très rigoureux. Son but est de décomposer le goût du gâteau en expliquant exactement ce qui vient de chaque ingrédient, sans se tromper à cause des liens entre eux.

L'idée clé : Si le sucre et le chocolat sont souvent achetés ensemble, le détective ne dira pas "c'est le sucre" OU "c'est le chocolat". Il dira : "C'est le sucre seul, plus le chocolat seul, plus l'effet spécial qu'ils ont quand ils sont ensemble".

3. L'innovation : Adapter la recette à n'importe quelle cuisine

Le génie de ce papier, c'est qu'ils ont créé une nouvelle "recette mathématique" (une base de fonctions) qui s'adapte à n'importe quelle situation, même si les ingrédients sont liés ou si certains ingrédients n'apparaissent jamais dans votre cuisine (ce qu'on appelle le "support non complet").

L'analogie de la balance :
Imaginez que vous pesez les ingrédients.
- Dans la méthode classique, la balance est calibrée pour des ingrédients égaux.
- Dans la méthode de ce papier, la balance est intelligente. Elle sait que si vous avez très peu de "chocolat" dans vos données, elle va augmenter le poids de ce que vous avez pour ne pas le sous-estimer. C'est ce qu'ils appellent un "poids inverse de la probabilité".
- Le résultat : Vous obtenez une décomposition exacte, même si vos données sont déséquilibrées ou liées.

4. Le défi de la complexité (La malédiction de la dimension)

Il y a un gros problème : si vous avez 20 ingrédients, le nombre de combinaisons possibles (sucre+chocolat, sucre+œufs+chocolat, etc.) explose. C'est comme essayer de lire tous les livres d'une bibliothèque infinie. C'est impossible à calculer.

La solution des auteurs : Ils disent : "On va faire une approximation intelligente."
Ils utilisent une technique de régularisation (comme un filtre). Ils disent : "On va supposer que les interactions entre 10 ingrédients en même temps sont très rares et peu importantes. On va se concentrer seulement sur les ingrédients seuls et les paires d'ingrédients."
- C'est comme dire : "Le goût du gâteau dépend surtout de la farine, du sucre, et du mélange sucre-œufs. On va ignorer les combinaisons bizarres de 15 ingrédients."
- Cela rend le calcul rapide et possible, même sur de gros jeux de données.

5. Pourquoi c'est utile ? (L'IA Explicable)

Aujourd'hui, l'Intelligence Artificielle (IA) est souvent une "boîte noire". On lui donne des données, elle sort une prédiction, mais on ne sait pas pourquoi.

SHAP (l'outil actuel) : C'est comme demander à un ami de deviner pourquoi le gâteau est bon. C'est bien, mais parfois l'ami se trompe si les ingrédients sont liés.
La méthode de ce papier : C'est comme avoir le plan d'architecte exact du gâteau.
Les auteurs montrent que leur méthode donne des résultats très proches de SHAP (la référence actuelle), mais avec une base mathématique plus solide quand les données sont liées. De plus, une fois le calcul fait, on peut expliquer n'importe quelle prédiction instantanément.

En résumé, avec une métaphore finale

Imaginez que vous essayez de comprendre pourquoi un orchestre joue une belle musique.

L'ancienne méthode suppose que chaque musicien joue seul, au hasard. Elle dit : "Le violon est important".
La réalité : Le violoniste joue toujours en harmonie avec le violoncelle. Si on les sépare, la musique est fausse.
Ce papier propose un nouveau système d'écoute qui comprend que le violon et le violoncelle sont liés. Il crée une partition mathématique qui dit exactement : "Voici la part du violon seul, la part du violoncelle seul, et la part de leur duo magique". Et il le fait même si l'orchestre est petit ou si certains musiciens ne jouent que rarement.

Le but final ? Rendre l'Intelligence Artificielle plus transparente et plus fiable, surtout quand on travaille avec des données du monde réel où tout est connecté.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique et Contexte

L'analyse de Fourier sur l'hypercube booléen est un outil fondamental en informatique théorique pour décomposer les fonctions pseudo-booléennes $f : \{0, 1\}^d \to \mathbb{R}$ . Traditionnellement, cette analyse repose sur une mesure de probabilité uniforme sur l'hypercube. La base utilisée est celle des fonctions de parité (ou base de Walsh-Hadamard), qui sont orthogonales uniquement sous cette hypothèse d'indépendance et d'uniformité des variables d'entrée.

Cependant, dans les applications réelles d'apprentissage automatique (ML), cette hypothèse est souvent violée :

Les données binaires réelles présentent des corrélations (ex: modèles d'Ising, données génomiques).
L'encodage One-Hot de variables catégorielles crée des dépendances déterministes (une seule variable active à la fois).
Les espaces de configuration sont souvent rares (non pleine support), car le nombre d'échantillons $n$ est bien inférieur au nombre total de configurations $2^d$ .

Le problème central est donc : Comment généraliser l'analyse de Fourier pour des mesures de probabilité arbitraires (non uniformes, dépendantes) sur l'hypercube booléen, tout en conservant une interprétation structurelle (ANOVA) et une tractabilité computationnelle ?

2. Méthodologie

Les auteurs établissent un lien formel entre l'analyse de Fourier classique et la Décomposition Fonctionnelle de Hoeffding (HFD), également connue sous le nom de décomposition ANOVA fonctionnelle.

A. Fondements Théoriques

La HFD décompose une fonction $f$ en une somme de termes $f_S$ dépendant de sous-ensembles de variables $S$ , sous la contrainte d'orthogonalité hiérarchique : chaque terme $f_S$ capture les interactions spécifiques à $S$ , orthogonales à toute information expliquée par les marginales d'ordre inférieur.

Sous une mesure uniforme (produit), la HFD coïncide exactement avec l'analyse de Fourier standard.
Sous une mesure arbitraire $P$ , la base de Walsh-Hadamard n'est plus orthogonale.

B. Construction de la Nouvelle Base

Les auteurs proposent une base de fonctions adaptée à la mesure $\{\psi_S\}_{S \subseteq [d]}$ définie comme suit :
$\psi_S(x) := \frac{\chi_S(x)}{2^{|S|} \cdot p_S(x_S)}$
Où :

$\chi_S(x)$ est la fonction de parité standard.
$p_S(x_S)$ est la fonction de masse de probabilité marginale du sous-vecteur $x_S$ .
Le terme $1/p_S$ agit comme un repondage par l'inverse de la probabilité (inverse probability weighting) pour compenser la non-uniformité de la mesure.

Théorème Principal : Sous l'hypothèse de support plein (toutes les configurations ont une probabilité non nulle), cette base $\{\psi_S\}$ forme une base unique qui satisfait la décomposition HFD et l'orthogonalité hiérarchique. La décomposition de $f$ est la solution unique d'un problème de moindres carrés pondérés (WLS).

C. Gestion du Support Non Plein et de la Malédiction de la Dimension

Dans les cas pratiques (ML), le support est souvent incomplet ( $n \ll 2^d$ ) et la matrice de Gram n'est pas inversible de manière unique.

Approche : Les auteurs formulent le problème comme une régression pénalisée (Elastic Net : combinaison de pénalités L1 et L2).
Approximation d'ordre faible : Pour éviter la complexité exponentielle, ils restreignent la décomposition aux interactions d'ordre $k$ (généralement $k=1$ ou $2$), exploitant l'hypothèse de parcimonie des effets (seuls les effets principaux et les interactions paires sont significatifs).
Cela transforme le problème non paramétrique en un problème linéaire tractable.

3. Contributions Clés

Généralisation de l'Analyse de Fourier : Introduction d'une base explicite $\{\psi_S\}$ qui généralise les fonctions de parité à n'importe quelle mesure de probabilité sur l'hypercube booléen.
Lien avec la HFD : Démonstration que l'analyse de Fourier est un cas particulier de la HFD et fourniture d'une solution analytique/numérique pour le cas dépendant.
Formulation par Moindres Carrés : Reformulation de la décomposition fonctionnelle comme un problème de régression linéaire (WLS), rendant le calcul accessible via des méthodes d'optimisation standards.
Stratégie de Régularisation : Proposition d'une méthode robuste (Elastic Net + troncature d'ordre) pour traiter les données réelles à support partiel et haute dimension.
Connexion à l'IA Explicable (XAI) : Établissement d'un pont théorique entre cette décomposition et les méthodes d'attribution de caractéristiques comme SHAP.

4. Résultats Expérimentaux

Les auteurs ont évalué leur méthode sur six jeux de données réels (classification et régression) avec des modèles boîtes noires (Random Forest, XGBoost, MLP).

Fidélité de Reconstruction : Une expansion d'ordre faible ( $k=1$ ou $2$) permet de reconstruire les prédictions des modèles avec une très haute fidélité ( $R^2_{Fourier} > 0.9$ dans la plupart des cas), confirmant que les interactions d'ordre élevé sont souvent négligeables.
Comparaison avec SHAP :
- Sur les modèles arborescents, les importances de caractéristiques globales obtenues par la méthode proposée sont très fortement corrélées avec TreeSHAP et TreeHFD.
- Sur les réseaux de neurones (MLP), les attributions locales correspondent bien à DeepSHAP et KernelSHAP.
- Cela suggère que les méthodes SHAP, bien que basées sur la théorie des jeux, se comportent empiriquement comme des approximations de cette décomposition fonctionnelle dépendante de la mesure.
Efficacité Computationnelle : La méthode est rapide une fois la base construite, permettant des explications globales et locales instantanées sur l'ensemble des données.

5. Signification et Impact

Théorique : Ce travail unifie l'analyse de Fourier (dominante en théorie des fonctions booléennes) et l'analyse de sensibilité globale (ANOVA/HFD, dominante en statistiques et ingénierie de fiabilité). Il résout le problème de la définition de la décomposition sous des mesures dépendantes.
Pratique pour le ML :
- Permet d'analyser des modèles sur des données binaires réelles (avec corrélations ou encodage One-Hot) sans faire l'hypothèse erronée d'indépendance.
- Offre une alternative interprétable et mathématiquement fondée aux méthodes d'attribution de type SHAP, en fournissant une décomposition fonctionnelle explicite plutôt qu'une moyenne de marginales.
- La capacité à traiter les espaces de configuration non pleins (rares) est cruciale pour les applications réelles où les données sont limitées.

En conclusion, cet article propose un cadre généralisé, robuste et computationnellement efficace pour l'analyse de fonctions sur l'hypercube booléen, rendant l'analyse de Fourier applicable aux défis modernes de l'apprentissage automatique sur des données structurées et corrélées.