Résumé Technique : Apprentissage de la Permutation à partir de la Structure sans Supervision

Énoncé du Problème

De nombreuses tâches d'apprentissage impliquent des données qui sont naturellement désordonnées au moment de l'observation, nécessitant la récupération d'une permutation cachée pour révéler une structure sous-jacente. Les exemples incluent le tri (récupération de la monotonie), la reconstruction de puzzle (récupération de la continuité spatiale) et des problèmes de routage comme le problème du voyageur de commerce (TSP). Dans ces contextes, les permutations de vérité terrain sont souvent indisponibles, ce qui nécessite un apprentissage non supervisé piloté par des propriétés structurelles spécifiques à la tâche (par exemple, la régularité, la monotonie ou la cohérence géométrique) plutôt que par une supervision directe par étiquettes.

Les récents progrès dans l'apprentissage de permutations différentiables, en particulier la méthode Gumbel–Sinkhorn, permettent de traiter les permutations comme des opérateurs latents optimisés via des relaxations continues. Ces méthodes approximent des matrices de permutation discrètes en utilisant des matrices doublement stochastiques au sein du polytope de Birkhoff, contrôlées par un paramètre de température global $\tau$ (ou inverse de température $\beta$). Cependant, une limitation critique émerge à mesure que la taille du problème et l'ambiguïté augmentent : différentes parties de la matrice d'affectation se résolvent à des rythmes différents. Certaines lignes/colonnes deviennent déterministes tôt dans l'entraînement, tandis que d'autres restent ambiguës en raison de la symétrie ou de signaux structurels faibles. Une température globale unique force toutes les affectations à se durcir ou à se diffuser simultanément, créant un compromis inévitable entre stabilité et discrétisation. Un recuit agressif fige les erreurs précoces, tandis qu'un recuit conservateur empêche les grandes permutations ambiguës de converger.

Méthodologie

Les auteurs proposent une formulation adaptative à l'entropie de Gumbel–Sinkhorn qui remplace la température globale unique par un champ d'inverse de température localement variable, dépendant des lignes et des colonnes. Cette approche module la température en fonction de l'incertitude de l'affectation douce actuelle.

Mécanisme Central

1. Estimation de l'Entropie : À chaque étape d'entraînement, une affectation douce déterministe $Q$ est calculée en utilisant un inverse de température de base $\beta_0(t)$ :
   $$Q = \text{Sinkhorn}(\beta_0(t) \cdot \text{stopgrad}(S))$$
   où $S$ représente les scores de compatibilité. Le stop-gradient garantit que le contrôleur d'entropie ne rétropropage pas à travers l'estimation de la température elle-même.
2. Calcul de l'Incertitude : Les entropies normalisées des lignes et des colonnes ($H^{\text{row}}_i$ et $H^{\text{col}}_j$) sont calculées à partir de $Q$. Des valeurs proches de zéro indiquent des affectations confiantes, tandis que des valeurs proches de un indiquent une forte incertitude.
3. Champ de Température Adaptatif : Un champ d'inverse de température élément par élément $\beta \in \mathbb{R}^{n \times n}$ est construit. Pour les lignes ou colonnes à haute entropie, l'inverse de température est réduit (augmentant la température effective) pour préserver l'exploration. Pour les régions à faible entropie, l'inverse de température reste au niveau de base pour encourager la discrétisation.
   $$\beta^{\text{row}}_i = \frac{\beta_0(t)}{1 + b(H^{\text{row}}_i)}, \quad \beta^{\text{col}}_j = \frac{\beta_0(t)}{1 + b(H^{\text{col}}_j)}$$
   où $b(\cdot)$ est une fonction bornée et monotone qui s'active uniquement lorsque l'entropie dépasse un seuil $H_0$. Le champ final élément par élément est la moyenne : $\beta_{ij} = \frac{1}{2}(\beta^{\text{row}}_i + \beta^{\text{col}}_j)$.
4. Échantillonnage : La permutation douce finale $P$ est échantillonnée en utilisant ce champ adaptatif :
   $$P = \text{Sinkhorn}(\beta \odot (S + g))$$
   où $g$ est un bruit de Gumbel et $\odot$ désigne la multiplication élément par élément.

Interprétation Théorique

L'article établit que l'application de la normalisation Sinkhorn avec un champ d'inverse de température élément par élément est équivalente à la résolution d'un problème d'affectation régularisé par l'entropie avec des coûts localement redimensionnés. Cela fournit une interprétation du transport optimal où le contrôle adaptatif de la température retarde la rupture de symétrie dans les régions ambiguës tout en permettant aux régions confiantes de se concentrer, tout en maintenant les contraintes globales de double stochasticité.

Contributions Clés

1. Cadre Unifié : Un cadre pour apprendre les permutations comme opérateurs latents directement à partir de pertes structurelles spécifiques à la tâche sur des données réordonnées, permettant un apprentissage non supervisé sans permutations de vérité terrain.
2. Gumbel–Sinkhorn Adaptatif à l'Entropie : Une variante novatrice qui remplace la température globale par un champ localement variable dérivé de l'entropie d'affectation. Cela permet aux affectations confiantes de se discrétiser tôt tout en préservant l'exploration dans les régions ambiguës.
3. Interprétation du Transport Optimal : Une preuve que le contrôle adaptatif de la température est équivalent au redimensionnement local des coûts sur le polytope de Birkhoff, offrant une fondation théorique pour le comportement de la méthode.
4. Validation Empirique : Démonstration sur le tri, la reconstruction de puzzle et le TSP non supervisé que le contrôle adaptatif à l'entropie produit une convergence plus fiable et des permutations de meilleure qualité que les bases à température fixe ou à recuit global, en particulier à mesure que la taille du problème ($n$) et l'ambiguïté d'affectation augmentent.

Résultats Expérimentaux

La méthode a été évaluée sur trois tâches principales :

• Tri de Listes : Sur des ensembles de données à haute ambiguïté (valeurs dans $[10, 11]$), la température adaptative à l'entropie a constamment surpassé le recuit global et NeuralSort. À mesure que $n$ augmentait jusqu'à 300, l'écart de performance s'est élargi, la méthode adaptative maintenant des scores de Kendall $\tau$ significativement plus élevés.
• Reconstruction de Puzzle : Sur des images CelebA-Test partitionnées en grilles (jusqu'à $7 \times 7$), la méthode adaptative a atteint un Kendall $\tau$ plus élevé et une convergence plus stable à travers différentes graines aléatoires par rapport au recuit global. Les améliorations étaient les plus prononcées pour les puzzles plus grands où les indices de cohérence des frontières sont ambigus.
• TSP Non Supervisé : Appliqué au protocole UTSP, la méthode (utilisant une variante d'adaptation basée sur la violation de degré) a réduit les longueurs de tournée et les écarts d'optimalité par rapport aux bases Gumbel–Sinkhorn et UTSP standard, en particulier pour des nombres de nœuds plus élevés ($n=500, 1000$).

Dans tous les cas, la méthode adaptative a démontré une robustesse aux choix d'hyperparamètres (seuil d'entropie $H_0$ et boost maximal $b_{\text{max}}$) et a évité l'instabilité associée aux calendriers de température globale dans les régimes à haute ambiguïté.

Signification et Revendications

L'article revendique que l'apprentissage efficace de permutations à partir de la structure dépend de manière critique de la gestion de l'endroit et du moment où l'entropie s'effondre pendant l'optimisation. En reconnaissant que l'incertitude d'affectation est hétérogène, la méthode proposée résout le compromis stabilité-discrétisation inhérent aux calendriers de température globale.

Les auteurs positionnent ce travail comme une extension légère de la famille Gumbel–Sinkhorn qui améliore l'évolutivité et la stabilité sans altérer la géométrie de relaxation sous-jacente ni les propriétés de convergence. Ils notent que si la méthode améliore la stabilité de l'optimisation, elle ne résout pas les ambiguïtés fondamentales dans les objectifs hautement symétriques ou faiblement informatifs, et qu'une forme de rupture de symétrie (par exemple, des tuiles ancrées dans les puzzles) peut toujours être requise.

Les directions futures suggérées incluent l'apprentissage du contrôle adaptatif à l'entropie de bout en bout et l'extension de la discrétisation consciente de l'incertitude à des structures combinatoires plus complexes et à des problèmes d'appariement multimodaux.