Beyond identifiability: Learning causal representations with few environments and finite samples

Ce papier établit des garanties théoriques à échantillons finis prouvant qu'il est possible d'apprendre des représentations causales, y compris le graphe latent, la matrice de mélange et les cibles d'intervention inconnues, à partir d'un nombre sublinéaire d'environnements et d'interventions non conçues à l'avance.

L'essentiel

Imaginez que vous êtes un détective privé qui essaie de comprendre comment fonctionne une machine complexe, mais vous ne pouvez voir que l'extérieur de la machine. À l'intérieur, il y a des engrenages invisibles (les représentations causales) qui tournent et s'entraînent les uns les autres pour produire ce que vous voyez (les données).

Le problème ? La machine est très complexe, et si vous ne regardez que dans un seul état (par exemple, la machine en marche normale), vous ne pouvez pas savoir quel engrenage fait tourner quel autre. C'est comme essayer de deviner la recette d'un gâteau en ne goûtant qu'une seule bouchée : vous ne savez pas si le sucre vient du chocolat ou de la vanille.

Voici comment les auteurs de cet article, Inbeom Lee, Tongtong Jin et Bryon Aragam, résolvent ce casse-tête, expliqué simplement :

1. Le problème : Trop de bruit, pas assez de pistes

Dans le monde de l'intelligence artificielle, on essaie souvent de trouver des "causes" cachées derrière des données. Mais sans hypothèses supplémentaires, c'est impossible. C'est comme essayer de démêler un nœud de cordes sans savoir où elles commencent et où elles finissent.

Les chercheurs savent théoriquement que si on peut perturber la machine (changer un engrenage ici, enlever un ressort là), on peut enfin comprendre la structure. Mais jusqu'à présent, il fallait faire des milliers de perturbations différentes pour y arriver, ce qui est trop long et trop cher.

2. La solution magique : Le "Cadeau de Noël"

L'idée géniale de cet article, c'est qu'on n'a pas besoin de milliers de perturbations. On a besoin de très peu, mais intelligentes.

Imaginez que vous avez un coffre-fort avec un code à 100 chiffres.

• L'ancienne méthode : Vous essayez chaque chiffre un par un. Il vous faut 100 essais (ou plus).
• La méthode de cet article : Vous utilisez une technique de "binarité" (comme un jeu de devinettes). Vous demandez : "Le code est-il pair ou impair ?", "Est-il supérieur à 50 ?". Avec seulement quelques questions bien posées (logarithmiques, donc très peu par rapport à la taille du code), vous pouvez trouver le code exact.

Dans le papier, ils montrent qu'avec seulement un nombre logarithmique d'environnements (par exemple, si vous avez 1000 variables cachées, vous n'avez besoin que d'une douzaine d'environnements différents, pas de 1000), vous pouvez tout reconstruire.

3. Comment ça marche ? (L'analogie du "Filtre à Café")

Voici les trois étapes de leur méthode, expliquées avec des images :

Étape A : Trouver les "coupables" (Les cibles d'intervention)

Imaginez que vous avez plusieurs photos d'une scène de crime prises à différents moments. Sur chaque photo, certains objets ont bougé ou ont été déplacés, mais vous ne savez pas lesquels.
Les chercheurs utilisent une astuce mathématique : ils regardent ce qui reste commun entre toutes les photos.

• Si un objet est présent dans toutes les photos, il n'a pas été touché.
• Si un objet manque dans une photo mais pas dans les autres, c'est lui qui a été touché.
  En comparant les "ombres" (les statistiques) de ces différentes photos, ils peuvent identifier exactement quels engrenages ont été perturbés, même sans les avoir vus directement.

Étape B : Démêler les cordes (Le "Décodeur")

Une fois qu'ils savent quels engrenages ont été touchés, ils peuvent isoler chaque pièce.
Imaginez que vous avez un mélange de jus de fruits (les données observées). Si vous savez que dans un verre, on a ajouté uniquement du jus de pomme, et dans un autre, uniquement du jus d'orange, vous pouvez déduire à quoi ressemble le jus pur de pomme et le jus pur d'orange.
Ils font la même chose mathématiquement pour séparer les "ingrédients" cachés (les représentations) du mélange final.

Étape C : Voir la carte du trésor (Le graphe causal)

Maintenant qu'ils ont les ingrédients séparés, ils peuvent enfin voir comment ils interagissent.
C'est comme si, après avoir séparé les ingrédients, vous voyiez enfin le schéma de la recette : "La farine va dans le bol, puis on ajoute les œufs". Ils reconstruisent la carte complète des relations de cause à effet entre les variables cachées.

4. Pourquoi c'est important ?

Jusqu'à présent, les théoriciens disaient : "C'est possible en théorie, mais on ne sait pas le faire avec de vraies données limitées."
Cet article dit : "Voici comment le faire, et voici combien de données il faut exactement."

• Avant : Il fallait des montagnes de données et des hypothèses très strictes (comme supposer que tout est parfaitement lisse ou gaussien).
• Maintenant : Ils montrent que même avec peu de données, même si le bruit est bizarre (pas de distribution normale), et même si on ne sait pas exactement quelles parties de la machine on a touchées, on peut tout retrouver.

En résumé

C'est comme si on vous donnait un puzzle de 10 000 pièces, mais au lieu de devoir essayer chaque pièce, on vous dit : "Regarde juste ces 15 pièces clés, et tu pourras reconstruire tout le puzzle, même si certaines pièces sont manquantes ou abîmées."

C'est une avancée majeure pour rendre l'intelligence artificielle plus compréhensible et fiable, en lui permettant de comprendre le "pourquoi" des choses, pas juste le "quoi".

Résumé technique

1. Problématique et Contexte

L'apprentissage de représentations causales (Causal Representation Learning - CRL) vise à apprendre des représentations latentes interprétables avec des propriétés causales à partir de données non structurées. Bien que la théorie de l'identifiabilité (la capacité théorique à retrouver les paramètres uniques) ait beaucoup progressé, les garanties finies d'échantillonnage (estimation pratique avec un nombre limité de données) restent mal comprises, en particulier dans des modèles linéaires à haute dimension.

Les défis principaux :

• Combinaison de difficultés : Le problème combine les défis des modèles à facteurs latents (où la matrice de mélange n'est pas identifiable sans hypothèses fortes) et des modèles causaux (où la structure du graphe est difficile à estimer).
• Nombre d'environnements : Les résultats existants sur l'identifiabilité suggèrent souvent qu'un nombre linéaire d'environnements ($K = \Omega(d)$, où $d$ est la dimension latente) est nécessaire, ou reposent sur des interventions à cible unique.
• Interventions inconnues : Dans la pratique, les cibles des interventions (quels facteurs latents sont perturbés) sont souvent inconnues.
• Absence de distribution : La plupart des méthodes d'estimation supposent des distributions spécifiques (ex: Gaussienne) ou utilisent des fonctions de vraisemblance, ce qui n'est pas applicable ici où le bruit peut être non-Gaussien et inconnu.

Objectif de l'article : Fournir des garanties non asymptotiques (finies) pour apprendre la structure causale latente, la matrice de mélange et les cibles d'intervention inconnues, en utilisant un nombre sous-linéaire (logarithmique) d'environnements.

---

2. Modèle et Hypothèses

Le modèle suppose des données observées $X \in \mathbb{R}^p$ générées à partir de facteurs latents causaux $Z \in \mathbb{R}^d$ (avec $p \gg d$) via une équation structurelle linéaire :

1. Modèle latent : $Z = A^T Z + \nu$, où $A$ définit un graphe acyclique dirigé (DAG) $G$ inconnu et $\nu$ est un bruit indépendant.
2. Modèle d'observation : $X = BZ$, où $B$ est une matrice de mélange (décodeur) de rang plein.
3. Environnements d'intervention : Les données proviennent de $K$ environnements différents. Chaque environnement $k$ correspond à une intervention inconnue sur un sous-ensemble de nœuds $I^{(k)} \subset [d]$. L'intervention "annule" les colonnes correspondantes dans $A$ et modifie la variance du bruit.

Hypothèses clés :

• (A1) Conception des interventions : Le nombre d'environnements $K$ est de l'ordre de $O(\log d)$. Il existe un environnement observationnel ($k=0$) et un système de séparation fort : pour toute paire de nœuds, il existe des environnements où l'un est intervenu et l'autre non (et vice-versa).
• (A2) Interventions sur le bruit : Les rapports de variances du bruit entre deux sous-environnements doivent être distincts pour chaque nœud (condition d'identifiabilité classique).
• (A3) Condition de régularité : La matrice de mélange $B$ peut être mal conditionnée, mais pas excessivement (le rapport entre la plus petite et la plus grande valeur propre de $B^T B$ est contrôlé).

---

3. Méthodologie Proposée

Les auteurs proposent un estimateur en trois étapes, basé uniquement sur les statistiques du second ordre (matrices de covariance), évitant ainsi toute hypothèse sur la distribution du bruit (Gaussien ou non).

Étape 1 : Reconstruction des cibles d'intervention inconnues

L'idée centrale est d'exploiter les intersections des espaces colonnes des matrices de covariance spécifiques à chaque environnement.

• Pour un ensemble d'environnements $T$, on définit $g(T)$ comme la dimension de l'espace colonne commun : $g(T) = \dim(\bigcap_{k \in T} \text{col}(\Sigma_X^{(k)}))$.
• Lemme clé : La connaissance de $g(T)$ pour tous les sous-ensembles $T$ permet de reconstruire les ensembles de cibles d'intervention $I^{(k)}$.
• Algorithme : On utilise une estimation par seuillage des valeurs propres d'une matrice de projection construite à partir des covariances empiriques pour estimer $g(T)$ et déduire $I^{(k)}$.

Étape 2 : Estimation de la matrice de mélange $B$

Une fois les cibles $I^{(k)}$ identifiées, on peut isoler les colonnes de $B$.

• Pour chaque nœud latent $j$, on définit l'ensemble d'environnements $\kappa_j$ où ce nœud n'est pas intervenu.
• La colonne $B_{\cdot j}$ correspond à l'intersection des espaces colonnes des covariances dans ces environnements : $\text{col}(B_{\cdot j}) = \bigcap_{k \in \kappa_j} \text{col}(\Sigma_X^{(k)})$.
• Cela permet de retrouver $B$ (à une permutation et un facteur d'échelle près) sans hypothèses de parcimonie sur $B$.

Étape 3 : Apprentissage du graphe causal latent $G$

Avec $B$ estimé, on peut "dé-mélanger" les données pour obtenir les covariances latentes $\Sigma_Z$.

• On résout un problème de valeur propre généralisée entre deux covariances latentes (issues de deux sous-environnements avec des variances de bruit différentes) : $\Sigma_Z^{(1)} t = \lambda \Sigma_Z^{(2)} t$.
• Les vecteurs propres généralisés $T_Z$ encodent la structure du graphe causal via leurs zéros. En seuillant les coefficients de $T_Z$, on récupère le graphe $G$.

---

4. Résultats Principaux et Garanties Statistiques

L'article établit des bornes d'erreur non asymptotiques pour chaque étape, avec une probabilité de succès élevée ($1 - 1/pn$).

1. Estimation des cibles d'intervention :

   • Les ensembles d'intervention $\hat{I}^{(k)}$ sont retrouvés exactement avec une probabilité élevée, à condition que le nombre d'échantillons $n$ soit suffisant par rapport à $d$ et $p$.

2. Estimation de la matrice de mélange $B$ :

   • L'erreur de Frobenius normalisée satisfait :
     $$\inf_{D} \| \hat{B} - B D \|_F \lesssim \sqrt{\frac{r \log(pn)}{n}}$$
     où $D$ est une matrice diagonale positive (compensant l'échelle et la permutation) et $r$ est la taille maximale du support non-intervenu.

3. Estimation du graphe causal $G$ :

   • Le graphe estimé $\hat{G}$ est égal au vrai graphe $G$ avec une probabilité élevée, à condition que le seuil de détection $\alpha$ soit choisi correctement et que les coefficients non nuls du graphe soient suffisamment grands par rapport au bruit d'estimation.

Optimalité :
Le résultat le plus frappant est que le nombre d'environnements nécessaire est logarithmique ($K \asymp \log d$). Cela correspond à la borne inférieure informationnelle connue pour l'identification de modèles causaux avec des interventions multi-cibles, même lorsque les cibles sont inconnues et les variables latentes non observées.

---

5. Contributions Clés et Signification

• Combler le fossé Identifiabilité/Estimation : L'article passe de la simple preuve que les paramètres sont identifiables (théorie) à la construction d'un estimateur explicite avec des garanties de convergence finie.
• Efficacité des environnements : Démontrer qu'un nombre logarithmique d'environnements suffit, même avec des cibles d'intervention inconnues et des données à haute dimension. C'est un progrès majeur par rapport aux méthodes nécessitant $O(d)$ environnements.
• Robustesse distributionnelle : La méthode ne nécessite aucune hypothèse sur la distribution du bruit (pas de Gaussien, pas de LiNGAM), reposant uniquement sur les moments du second ordre.
• Nouvelle technique d'analyse : Introduction d'une méthode de "comptage de valeurs propres par projection" (projection-based eigen-counting) pour gérer les intersections d'espaces colonnes bruités, une technique technique novatrice pour l'analyse de perturbation dans ce contexte.
• Pas d'hypothèses de parcimonie : Contrairement à de nombreux travaux en analyse factorielle, la méthode ne suppose pas que la matrice de mélange $B$ est parcimonieuse ou que les facteurs sont non corrélés.

Conclusion :
Ce travail représente une avancée fondamentale pour l'apprentissage de représentations causales. Il fournit un cadre théorique rigoureux pour l'estimation pratique dans des scénarios réalistes (peu d'environnements, cibles inconnues, bruit non-Gaussien), ouvrant la voie à des applications plus robustes en généralisation hors-distribution et en analyse de données biologiques ou de vision par ordinateur.