Résumé Technique : Adaptation, Rapide et Lente : Sur la Transportabilité en Few-Shot des Compositions

1. Énoncé du Problème

L'article aborde le défi de la généralisation à travers les domaines dans les tâches de prédiction séquentielle, en se concentrant spécifiquement sur l'adaptation de domaine (DA) où un apprenant dispose de grandes quantités de données sources ($N$) et d'une petite quantité de données cibles étiquetées ($n$).

Les garanties classiques de l'apprentissage automatique échouent souvent lorsque les distributions source et cible diffèrent (changement de distribution). Bien que la théorie de la transportabilité causale fournisse un cadre pour identifier quand les grandeurs cibles peuvent être récupérées à partir de données sources, les méthodes existantes supposent souvent que le prédicteur cible est une réutilisation directe d'un seul mécanisme source. Cet article investigate un cadre plus complexe : la transportabilité compositionnelle. Ici, le prédicteur cible n'est pas un mécanisme unique mais un circuit — une composition séquentielle de plusieurs mécanismes causaux. La question centrale est : Dans quelles conditions un prédicteur cible, construit en composant des mécanismes appris à partir de données sources, peut-il être appris avec peu d'échantillons cibles (adaptation rapide), et quand nécessite-t-il beaucoup d'échantillons (adaptation lente) ?

Le cadre implique :

• Données Séquentielles : Positions indexées $V_1, \dots, V_T$ sur un vocabulaire discret $\mathcal{V}$.
• Tâche Cible : Prédire une position cible désignée $Y = V_{T^*}$ étant donné un préfixe $X = V_{1:M}$.
• Objectif : Minimiser le risque excédentaire $R_{P^\dagger}(\mu) - R_{P^\dagger}(\mu^*)$ en utilisant les données sources $D_{src}$ et les données cibles limitées $D^\dagger$.

2. Méthodologie

Les auteurs proposent un cadre fondé sur les Modèles Causaux Structurels (SCM) et la théorie de la transportabilité causale, introduisant deux régimes distincts d'adaptation basés sur la disponibilité des connaissances structurelles.

2.1. Adaptation Informée par la Structure (Circuit-TR)

Ce régime suppose que l'apprenant a accès à :

1. Des diagrammes causaux pour les domaines source ($G_{src}$) et cible ($G^\dagger$).
2. Un oracle de discordance $\Delta$, qui identifie si le mécanisme causal (fonction $f$ ou distribution de bruit $P(u)$) à une position cible $i$ correspond à une position source $i'$.

Algorithme 2 (Circuit-TR) :

• Appariement des Mécanismes : Pour chaque position cible $i$, l'algorithme identifie les positions source $i'$ où $\Delta(i, i') = 0$ (les mécanismes correspondent).
• Regroupement des Données : Pour les positions correspondantes, les données des sources et des cibles sont regroupées (réordonnées pour aligner les parents) afin d'entraîner un prédicteur conditionnel.
• Composition : Le prédicteur cible est construit en composant ces conditionnels appris selon le graphe causal cible.
• Marginalisation : Les variables intermédiaires sont marginalisées pour obtenir la prédiction finale $P^\dagger(Y|X)$.

Insight Clé : Si un mécanisme cible correspond à un mécanisme source, le taux d'erreur décroît avec la grande taille source $N$ (zero-shot/rapide). Si aucune correspondance n'existe, l'erreur décroît avec la petite taille cible $n$ (lente). Le risque total est une somme de ces composantes.

2.2. Adaptation Agnostique à la Structure (Circuit-AD)

En pratique, les graphes causaux et les oracles de discordance sont rarement connus. L'article introduit Circuit-AD (Algorithme 3) pour gérer ce cadre few-shot sans priors structurels explicites.

Algorithme 3 (Circuit-AD) :

• Génération d'Hypothèses : L'algorithme énumère toutes les configurations structurelles possibles (partitions des positions source/cible en clusters supposant des mécanismes partagés, et graphes causaux candidats).
• Construction de Candidats : Pour chaque configuration, il construit un prédicteur candidat en utilisant uniquement les données sources (via la logique de Circuit-TR).
• Sélection : En utilisant une partie retenue du petit jeu de données cible ($D^\dagger_{te}$), l'algorithme sélectionne le candidat ayant le risque empirique le plus faible.
• Garantie Théorique : Le risque excédentaire de Circuit-AD est borné par le risque du Circuit-TR optimal informé par la structure, plus un terme dépendant de la taille de l'espace d'hypothèses ($O(\sqrt{T^{*3} \log T^* / n})$).

2.3. Relaxation Basée sur le Gradient

Reconnaissant que l'énumération symbolique dans Circuit-AD est combinatoire et intraitable pour de grands $T^*$, les auteurs proposent une architecture neuronale basée sur le gradient (Section 4).

• Pré-entraînement : Apprend un prédicteur universel $\Psi$, un indicateur de mécanisme $\Phi$ (regroupant les positions source par mécanisme) et une matrice de parents $A_{src}$ à partir des données sources.
• Affinage (Fine-tuning) : S'adapte au domaine cible en apprenant une matrice de parents cible $A^\dagger$, un indicateur de mécanisme cible $\Phi^\dagger$ et des indicateurs de transport $s_i$. Ces indicateurs $s_i \in [0,1]$ interpolent entre le mécanisme source transporté et un estimateur uniquement cible, apprenant efficacement quelles parties du circuit sont transportables.

3. Contributions Clés

1. Transportabilité de Module et de Circuit :

   • Module-TR : Le cas atomique où la cible est un mécanisme source unique (éventuellement avec des parents réordonnés).
   • Circuit-TR : Généralise cela aux prédicteurs cibles formés par la composition de plusieurs mécanismes sources. Cela permet une prédiction zero-shot même lorsqu'aucun mécanisme source ne prédit directement l'étiquette cible, à condition que la cible puisse être décomposée en modules apprenables depuis la source.

2. Taux d'Adaptation Few-Shot :

   • L'article établit que le taux d'erreur réalisable est gouverné par la taille $L$ du plus petit circuit cible composable à partir de modules apprenables depuis la source.
   • Adaptation Rapide : Si $L$ est constant (ou petit par rapport à $n$), l'algorithme atteint des taux dominés par la taille source $N$.
   • Adaptation Lente : Si la cible nécessite des mécanismes nouveaux non présents dans la source, le taux est dominé par la taille cible $n$.
   • Théorème 3.5 : Identifie un seuil $L = O(\sqrt[3]{n})$ séparant les régimes d'adaptation rapide et lente.

3. Adaptation Agnostique sans Structure Causale :

   • Démontre que les graphes causaux explicites ne sont pas strictement nécessaires pour une adaptation rapide. En recherchant parmi les structures candidates et en sélectionnant via des données de validation, Circuit-AD atteint des taux presque aussi bons que l'oracle informé par la structure, à condition que la taille du circuit cible soit petite.

4. Validation Empirique sur des Tâches Algorithmiques :

   • Des expériences sur des SCM synthétiques et une tâche de composition GCD Euclidien retenue montrent que le cadre délivre une précision proche de l'oracle.
   • La relaxation basée sur le gradient suit qualitativement les performances de l'algorithme symbolique à travers les régimes d'adaptation rapide (avec/sans supervision de processus) et lente.

4. Résultats

• Bornes Théoriques :

  • Circuit-TR (Théorème 2.7) : Le risque est $O\left(\frac{|I| \cdot |\mathcal{V}|^{c+1}}{\epsilon^2 N} + \frac{(T^* - M - |I|) \cdot |\mathcal{V}|^{c+1}}{\epsilon n}\right)$, où $|I|$ est le nombre de positions transportables.
  • Circuit-AD (Théorème 3.2) : Le risque est $O\left(R_{P^\dagger}(\mu_{TR}) + \sqrt{\frac{T^{*3} \log T^*}{n}}\right)$.
  • Rapide vs Lente (Théorème 3.5) : L'adaptation rapide se produit si la taille minimale du circuit $L$ est constante ; sinon, l'adaptation est lente.

• Résultats Expérimentaux :

  • Adaptation Rapide : Avec supervision de processus (étiquettes intermédiaires disponibles), le modèle atteint les performances de l'oracle avec très peu d'échantillons cibles ($n \approx 5$). Sans supervision de processus, il converge toujours rapidement ($n \approx 15$).
  • Adaptation Lente : Lorsque le mécanisme cible (par exemple, multiplication modulo $|\mathcal{V}|$) est absent du pool source, la méthode revient correctement aux performances ERM uniquement cible, évitant la dégradation observée dans les bases regroupées.
  • Expérience GCD : Sur une tâche algorithmique réelle (GCD Euclidien) où la cible est une composition de primitives sources (max, min, mod), Circuit-AD atteint une précision proche de l'oracle ($n \approx 20$), surpassant significativement l'ERM uniquement cible et les bases regroupées.
  • Relaxation Gradient : L'implémentation neuronale suit les performances de l'algorithme symbolique avec une surcharge résiduelle faible (0,1–0,3 nats), confirmant que la recherche basée sur le gradient peut découvrir des structures transportables sans énumération explicite.

5. Signification et Revendications

L'article revendique étendre la théorie de la transportabilité causale au domaine de la généralisation compositionnelle. Sa signification principale réside dans :

1. Relier Causalité et Composition : Il formalise comment les mécanismes causaux peuvent être "assemblés" pour résoudre de nouvelles tâches, allant au-delà du transfert de mécanisme unique.
2. Définir les Limites de l'Apprentissage Few-Shot : Il fournit une caractérisation théorique précise de quand l'apprentissage few-shot est possible (adaptation rapide) versus quand il est impossible (adaptation lente), reliant ces régimes à la complexité du circuit de la tâche cible par rapport à la bibliothèque source.
3. Robustesse à une Structure Inconnue : Il démontre que la connaissance causale explicite n'est pas une condition préalable à l'adaptation rapide ; une approche basée sur la recherche (Circuit-AD) peut récupérer les avantages de la connaissance structurelle en utilisant uniquement une petite quantité de données cibles.
4. Applicabilité Pratique : La relaxation basée sur le gradient offre une implémentation neuronale évolutive qui reproduit qualitativement les garanties théoriques, suggérant une voie vers des algorithmes pratiques pour l'adaptation de domaine compositionnelle.

Les auteurs restent modestes, reconnaissant que le cadre repose actuellement sur des variables discrètes, une positivité stricte et l'absence de confondants non observés. Ils notent que la relaxation basée sur le gradient est une approximation empirique de la théorie symbolique, et que combler le fossé formel entre les deux reste un problème théorique ouvert. Le travail est positionné comme une fondation théorique pour comprendre la transportabilité dans les cadres compositionnels, plutôt que comme une solution complète à tous les défis d'adaptation de domaine du monde réel (par exemple, le langage naturel).