Contrastive Identification and Generation in the Limit

Résumé Technique : Identification et Génération Contrastives à la Limite

Définition du Problème
Cet article initie l'étude théorique de l'apprentissage de l'identification et de la génération contrastives à la limite. Les auteurs comblent un vide dans les modèles classiques d'apprentissage à la limite (Gold, 1967 ; Angluin, 1980) et les modèles de génération récents (Kleinberg et Mullainathan, 2024), qui reposent sur des flux d'exemples positifs (texte) ou de données entièrement étiquetées (informateur). Dans de nombreux contextes naturels — tels que les tests A/B, les expériences comparatives et les annotations de similarité-dissimilarité — les données arrivent sous forme de paires non ordonnées $\{x, y\}$ où l'apprenant sait que les exemples divergent selon l'hypothèse cible $h$ (c'est-à-dire $h(x) \neq h(y)$), mais ne sait pas quel élément est positif ($h(x)=1$) et quel élément est négatif ($h(x)=0$).

L'apprenant observe un flux de telles paires contrastives qui finit par couvrir chaque exemple positif (couverture du côté positif) mais n'étiquette jamais explicitement un seul point. L'objectif est de déterminer les conditions selon lesquelles un apprenant peut :

1. Identifier l'hypothèse cible $h$ à partir d'une classe connue $\mathcal{H}$ (se stabiliser sur l'hypothèse correcte).
2. Générer de nouveaux exemples positifs de $h$ (sortir des éléments de $\text{supp}(h)$ non encore vus dans le flux).

Méthodologie et Cadre Technique
La contribution technique centrale est l'introduction du graphe de croisement commun, noté $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$, où $\Delta(h)$ est l'ensemble de toutes les paires traversant la coupure définie par $h$. Ce graphe encode l'ambiguïté paire à paire entre les hypothèses : une arête existe dans $\Gamma(h, g)$ si la paire est une observation valide pour $h$ et pour $g$.

Les auteurs appliquent cet objet géométrique à trois échelles :

• Paires : Pour analyser l'éliminabilité entre deux hypothèses.
• Familles Finies : Pour analyser les obstructions à la génération via des présentations partagées.
• Ensembles de Défaut Infinités : Pour analyser la robustesse face à une corruption adversariale.

L'article utilise une traduction théorique des graphes où l'ambiguïté contrastive paire à paire se réduit à une question de couverture : une hypothèse $g$ n'est pas éliminable de $h$ si et seulement si le support de $h$ est couvert par les sommets incidents aux arêtes de $\Gamma(h, g)$.

Contributions et Résultats Clés

1. Caractérisation Exacte de l'Identification Contrastive (CtrId)
L'article fournit une condition nécessaire et suffisante pour qu'une classe $\mathcal{H}$ soit identifiable à partir de données contrastives. Une classe appartient à CtrId si et seulement si :

• Elle est identifiable par texte (satisfait la condition des indices révélateurs d'Angluin).
• Condition de Couverture Recouvrante : Chaque paire d'hypothèses incomparables dans $\mathcal{H}$ doit former une « couverture recouvrante ». Cela signifie que leurs supports doivent s'intersecter ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) et que leur union doit couvrir l'ensemble entier des exemples ($\text{supp}(h) \cup \text{supp}(g) = X$).
• Implication : Les données contrastives introduisent une nouvelle obstruction : si deux hypothèses sont incomparables, disjointes, ou s'intersectant mais ne couvrant pas l'espace, elles ne peuvent être distinguées.

2. Génération Contrastive et Dimension de Clôture
Les auteurs introduisent la dimension de clôture contrastive ($C^\Delta$), une dimension combinatoire analogue à la dimension de clôture pour les données positives (Raman et al., 2025).

• Définition : $C^\Delta(\mathcal{H})$ est le supremum de la taille des ensembles d'arêtes « creux » finis (ensembles de paires qui n'imposent aucun nouvel élément positif en dehors des sommets observés).
• Résultat : Une classe admet un générateur contrastif uniforme si et seulement si $C^\Delta(\mathcal{H}) < \infty$. La complexité d'échantillonnage optimale est $C^\Delta(\mathcal{H}) + 1$.
• Génération Non Uniforme : Une classe est générable de manière non uniforme si elle peut être décomposée en une chaîne de sous-classes ayant des dimensions de clôture contrastive finies.
• Obstructions : L'article identifie des « obstructions de familles finies » où un ensemble d'hypothèses admet une présentation contrastive partagée avec une intersection finie de supports, empêchant la génération d'éléments nouveaux.

3. La Hiérarchie en Diamant
Sur les classes dénombrables à support uniformément non borné (UUS), les quatre familles d'apprentissage forment une hiérarchie en diamant stricte plutôt qu'une chaîne linéaire :

• Inclusions Strictes : $\text{CtrId} \subsetneq \text{CtrGen}$ et $\text{CtrId} \subsetneq \text{TxtId}$. À la fois $\text{CtrGen}$ et $\text{TxtId}$ sont strictement contenus dans $\text{TxtGen}$.
• Incomparabilité : $\text{CtrGen}$ et $\text{TxtId}$ sont mutuellement incomparables.
  • TxtId $\not\subseteq$ CtrGen : Les classes à supports disjoints sont identifiables par texte mais bloquées pour la génération contrastive par des obstructions d'intersection finie.
  • CtrGen $\not\subseteq$ TxtId : Les classes à « supports percés » (retirant un élément d'un ensemble infini) sont générables de manière contrastive via des cœurs éventuels mais manquent d'ensembles d'indices révélateurs finis pour l'identification par texte.

4. Inversion de la Robustesse sous Corruption Adversariale
L'article prouve une inversion nette de la relation entre les modes d'identification sous corruption adversariale finie :

• Fragilité du Texte : Un seul exemple positif corrompu peut rendre une classe non identifiable dans le cadre textuel.
• Robustesse Contrastive : Les auteurs définissent un nombre de défaut $\kappa(h \to g)$, comptant le nombre minimum de violations forcées d'une hypothèse $g$ dans toute présentation valide de $h$. Si $\kappa(h \to g) = \infty$, aucune corruption finie ne peut masquer les violations.
• Classe Co-Singleton : La classe où chaque hypothèse étiquette tous les exemples positifs sauf un « trou » est identifiable sous n'importe quel budget de corruption finie dans le cadre contrastif (en utilisant un algorithme de « comptage d'absence ») mais est non identifiable même sous une seule corruption dans le cadre textuel.
• Résultat : Pour tout $k \ge 1$, l'identification contrastive corrompue à $k$ et l'identification textuelle corrompue à $k$ sont mutuellement incomparables.

Signification et Revendications
L'article revendique que le graphe de croisement commun sert d'objet technique unificateur qui encode l'ambiguïté paire à paire, les obstructions de génération au niveau des familles et les défauts de corruption dans un langage unique. Les auteurs soutiennent que si l'absence de direction dans les données contrastives est une faiblesse dans des contextes propres (introduisant de nouvelles obstructions par rapport au texte), elle devient une force sous corruption adversariale, car les paires corrompues créent des « non-arêtes » structurellement détectables qui violent la contrainte XOR.

Ce travail suggère que les paradigmes classiques d'apprentissage à la limite admettent des raffinements fructueux lorsque les observations ne sont pas des singletons, révélant une structure théorique des graphes à double face : coûteuse par rapport aux données étiquetées lorsqu'elle est propre, mais protectrice lorsqu'elle est perturbée de manière adversariale. L'article note explicitement que ses constructions pour l'identification et la génération non uniforme sont informationnelles (reposant sur l'existence de familles d'indices révélateurs ou de chaînes de dimensions) et laisse la question des procédures effectives et constructives pour des classes plus larges comme un problème ouvert.