Take It or Leave It: Intent-Controlled Partial Optimal Transport

Ce papier présente le Transport Optimal Partiel Contrôlé par l'Intention (IC-POT), un cadre novateur qui généralise le transport optimal partiel en remplaçant le rejet global de masse par des coûts de rejet ponctuels et pilotés par l'intention, fondés sur des informations secondaires, permettant ainsi un appariement plus structuré et fiable dans des applications telles que l'apprentissage positif-non étiqueté et l'analyse de données satellitaires multimodales.

L'essentiel

Imaginez que vous essayez de faire correspondre deux groupes différents de personnes pour une danse. Un groupe est la « Source » (disons, des danseurs de New York) et l'autre est la « Cible » (des danseurs de Londres).

L'Ancienne Méthode (Transport Optimal Standard) :
Traditionnellement, la règle était stricte : Chaque danseur doit trouver un partenaire. Même si un danseur de New York porte un nez de clown et qu'un danseur de Londres porte un tutu, l'algorithme les force à s'apparier simplement pour que les nombres correspondent. Cela conduit souvent à des appariements absurdes et forcés qui n'ont aucun sens.

La Méthode « Partielle » (Solutions Précédentes) :
Plus tard, les chercheurs ont dit : « D'accord, nous pouvons laisser certaines personnes sans partenaire. » Mais ils l'ont fait avec un budget global. Imaginez un manager qui dit : « Nous pouvons laisser 10 % des danseurs sur le côté. » Le manager ne se soucie pas de qui est laissé de côté ; il a juste besoin que le nombre total soit de 10 %. Si les 10 % laissés de côté sont par hasard les meilleurs danseurs, l'appariement est ruiné. Le système manque de nuance.

La Nouvelle Méthode (IC-POT - « Prends-le ou Laisse-le ») :
Ce papier introduit le Transport Optimal Partiel Contrôlé par l'Intention (IC-POT). Au lieu d'un budget global, il donne à chaque danseur un « prix de rejet » personnel.

Pensez-y comme à un videur dans une boîte de nuit, mais où le videur est différent pour chaque personne :

• La Règle « Prends-le » : Si un danseur est fiable, bien habillé et correspond à l'ambiance, son « prix de rejet » est élevé. L'algorithme pense : « Cela coûte trop cher de virer cette personne, donc nous devons essayer de lui trouver un partenaire. »
• La Règle « Laisse-le » : Si un danseur est clairement déplacé (peut-être un clown dans un bal formel, ou ses données sont bruyantes), son « prix de rejet » est faible. L'algorithme pense : « C'est peu coûteux de laisser cette personne sur le côté, donc nous le ferons. »

Comment cela fonctionne dans la vraie vie (Les exemples du papier)

Les auteurs montrent que cela fonctionne dans trois scénarios spécifiques :

1. Le « Jeu de Devinettes » (Apprentissage Positif-Non-Étiqueté)
Imaginez que vous essayez de trouver tous les chats dans une photo, mais que vous n'avez que quelques photos de chats étiquetés et un énorme tas de photos non étiquetées (certains chats, certains chiens).

• Le Problème : Certains chats sont cachés dans les ombres (difficiles à voir), tandis que d'autres sont lumineux et clairs. Une méthode « partielle » standard pourrait jeter les chats dans l'ombre parce qu'elle essaie d'être efficace.
• La Correction IC-POT : Le système sait que les zones « ombragées » sont simplement difficiles à voir, et pas nécessairement « pas des chats ». Il met un prix élevé sur le rejet des chats dans l'ombre. Il les garde dans l'appariement. Il met un prix faible sur les chiens évidents. Le résultat ? Il trouve plus de chats sans se confondre avec des chiens.

2. La « Barrière Linguistique » (Adaptation de Domaine Ouverte-Partielle)
Imaginez enseigner à un ordinateur à reconnaître des objets dans des photos d'un nouveau pays. Certains objets existent dans les deux pays (voitures, arbres), mais certains n'existent que dans le nouveau pays (animaux locaux uniques).

• Le Problème : L'ordinateur pourrait essayer de forcer un appariement entre un animal local et une voiture parce qu'il est désespéré d'apparier tout le monde.
• La Correction IC-POT : Le système examine la « confiance » de l'appariement. Si un animal local est très confiant dans sa propre identité mais n'a pas de correspondant dans l'ancien pays, le système lui donne un faible prix de rejet. Il dit : « Laissez cet animal sans partenaire ; il n'appartient pas à l'ancienne liste. » Mais si une voiture est clairement une voiture, le prix pour la rejeter est élevé, donc elle est appariée.

3. La « Vue sur l'Océan » (Données Géophysiques)
C'est l'exemple le plus visuel. Les auteurs ont comparé deux caméras satellites différentes regardant les vagues de l'océan.

• Le Problème : Une caméra (SWIM) voit les vagues clairement mais reçoit du « bruit statique » dans certaines directions. L'autre caméra (SAR) voit bien les vagues mais devient « floue » dans d'autres directions en raison de la physique.
• La Correction IC-POT : Le système utilise la connaissance physique comme prix de rejet.
  • Si une vague est floue dans la Caméra A mais claire dans la Caméra B, le système dit : « C'est une vraie vague, mais la Caméra A passe juste une mauvaise journée. Ne la rejetez pas. » (Prix élevé pour rejeter).
  • Si une vague est claire dans la Caméra A mais ressemble à du « bruit statique » dans la Caméra B, le système dit : « La Caméra B voit simplement du bruit. Rejetez cet appariement. » (Prix faible pour rejeter).
  • Résultat : Ils obtiennent une carte parfaite des vagues en ignorant les « bugs » spécifiques de chaque caméra, plutôt que d'essayer de forcer un appariement entre une vraie vague et un bug.

La Grande Conclusion

Le papier soutient que toutes les incompatibilités ne sont pas créées égales.

• Ancienne Méthode : « Rejetons 10 % des données au hasard ou selon une règle simple. »
• IC-POT : « Examinons chaque élément de données individuellement. S'il est fiable, nous le gardons. S'il est peu fiable ou bruyant, nous le laissons de côté. Nous décidons cela en fonction d'indices spécifiques (comme les ombres, les scores de confiance ou la physique des capteurs) disponibles pour cet élément de données précis. »

Cela transforme la décision de « quoi jeter » d'un instrument brut en un outil précis et intelligent.

Résumé technique

Résumé Technique : Transport Optimal Partiel Contrôlé par l'Intention (IC-POT)

Énoncé du Problème

Le Transport Optimal (OT) classique impose une contrainte rigide où toute la masse source doit être transportée et toute la masse cible doit être expliquée. Cette hypothèse de « participation totale » conduit souvent à des correspondances artificielles ou à un transfert négatif lors de la comparaison de distributions où seule une sous-ensemble de la masse est pertinent ou fiable.

Bien que le Transport Optimal Partiel (POT) assouplisse cela en permettant à la masse de rester non appariée, les formulations existantes reposent généralement sur des mécanismes de contrôle globaux. Ceux-ci incluent un budget de masse transportée scalaire, une remise scalaire uniforme ou des pénalités marginales globales. Ces mécanismes contrôlent combien de masse est rejetée, mais pas quels points spécifiques doivent être protégés ou écartés. Par conséquent, ils échouent à répondre aux applications où la décision de laisser une masse non appariée dépend de la fiabilité spécifique à chaque côté, de la géométrie du support ou d'informations externes (par exemple, le biais d'échantillonnage dans l'apprentissage Positif-Non-Étiqueté, la confiance dans l'Adaptation de Domaine, ou les artefacts spécifiques aux capteurs en géophysique).

Méthodologie : IC-POT

Les auteurs introduisent le Transport Optimal Partiel Contrôlé par l'Intention (IC-POT), une généralisation ciblée du POT qui remplace le paradigme de rejet global par des coûts de rejet ponctuels sur les mesures source et cible.

Formulation

Étant donnés des supports discrets $X = \{x_i\}$ et $Y = \{y_j\}$ avec des masses $\mu$ et $\nu$, et une matrice de coût de transport $C$, l'IC-POT introduit des variables de relâchement $u$ (masse source non appariée) et $v$ (masse cible non appariée). Le problème d'optimisation est :

$$\min_{P, u, v} \langle C, P \rangle + \langle c_s, u \rangle + \langle c_t, v \rangle$$
sous contraintes :
$$P\mathbf{1} + u = \mu, \quad P^\top\mathbf{1} + v = \nu, \quad P, u, v \geq 0$$

Ici, $c_s \in \mathbb{R}^n_+$ et $c_t \in \mathbb{R}^m_+$ sont des coûts de non-appariement ponctuels. Contrairement aux remises globales, ces coûts évaluent l'alternative locale de laisser une masse spécifique non appariée directement sur les supports originaux.

Propriétés Structurelles

L'article établit plusieurs propriétés théoriques clés :

1. Forme Lagrangienne Réduite : Le problème est équivalent à la minimisation de $\sum_{i,j} (C_{ij} - c_s(i) - c_t(j))P_{ij}$ sur des sous-couplages, remplaçant efficacement la remise scalaire du POT classique par une remise séparable et ponctuelle.
2. Interprétation Duale : La formulation duale révèle que $c_s(i)$ et $c_t(j)$ agissent comme des seuils d'acceptation locaux (plafonds) pour les variables duales. Un point est rejeté si sa variable duale atteint ce plafond.
3. Admissibilité et Sparsité : Une arête $(i, j)$ ne peut être active dans un plan de transport optimal que si $C_{ij} \leq c_s(i) + c_t(j)$. Cela fournit une règle exacte, pré-calculable, pour élaguer le graphe de transport, garantissant une sparsité basée sur les coûts de rejet spécifiques.
4. Équivalence de Support Augmenté : L'IC-POT peut être reformulé comme un problème OT de Kantorovich équilibré standard sur un support augmenté (ajoutant un point factice à chaque marge), prouvant sa bonne définition dans le cadre de l'OT discret.

Contributions Clés

L'article revendique trois contributions principales :

1. Modélisation Explicite du Comportement Non Apparié : Il rend la politique de non-appariement un objet explicite dans la formulation via des variables de relâchement sur les supports originaux, plutôt qu'un résultat implicite de contraintes globales.
2. Caractérisation Théorique : Il caractérise le problème comme une généralisation séparable à remise ponctuelle du transport partiel lagrangien, établissant des plafonds duaux, des règles d'admissibilité éparses et une séparation stricte du POT partiel à coût constant (démontrée via des contre-exemples où les coûts ponctuels brisent les symétries préservées par les règles uniformes).
3. Validation Empirique : Il démontre que l'intégration de règles de rejet ponctuelles pilotées par des informations latérales améliore les performances dans des tâches où le rejet est structuré, spécifiquement dans l'apprentissage Positif-Non-Étiqueté (PU), l'Adaptation de Domaine Ouverte-Partielle (OPDA) et la comparaison de signaux géophysiques.

Résultats Expérimentaux

1. Apprentissage Positif-Non-Étiqueté (PU)

Dans l'apprentissage PU, l'objectif est d'apparier les positifs étiquetés à un pool non étiqueté contenant à la fois des positifs latents et des négatifs.

• Configuration : Les auteurs simulent des scénarios « Sélectionnés au Hasard » (SAR) où les échantillons positifs sont sous-observés dans certaines régions (franges) en raison d'un biais de sélection dépendant des covariables.
• Résultat : Une base de référence OT partiel à coût constant (rejet uniforme) échoue à protéger ces régions de franges sous-observées, les traitant comme des négatifs. L'IC-POT, utilisant un profil de coût côté source qui encode le biais de sélection (rendant le rejet coûteux dans les franges à faible observation), surpasse significativement la base de référence.
• Métriques : Dans des régimes hétérogènes, l'IC-POT a obtenu un score F1 de 0,86 contre 0,52 pour la base de référence à coût constant.

2. Adaptation de Domaine Ouverte-Partielle (OPDA)

Dans l'OPDA, le domaine cible contient des classes inconnues qui doivent être rejetées.

• Configuration : En utilisant un backbone de distillation CLIP fixe, les auteurs ont modifié uniquement la couche de rejet finale. Ils ont comparé une base de référence partielle-W uniforme à deux variantes IC-POT : l'une utilisant l'entropie postérieure (protégeant les échantillons à faible entropie) et l'autre utilisant le support de prototype (protégeant les échantillons avec un accord cohérent du voisinage local).
• Résultat : Les deux variantes IC-POT ont amélioré la base de référence uniforme sur plusieurs jeux de données (Office-31, Office-Home, VisDA, DomainNet). La variante support de prototype a obtenu les gains les plus élevés sur des jeux de données localement cohérents (par exemple, 95,12 H-score sur Office-31 contre 94,08 pour le partiel-W).
• Constat : Les résultats suggèrent que, une fois la représentation fixée, les gains de performance dépendent de la modélisation du rejet comme une politique dépendante de la structure plutôt que d'une règle scalaire uniforme.

3. Étude de Cas Géophysique : Spectres de Vagues Océaniques SWIM/SAR

Cette expérience traite de la comparaison de spectres de vagues océaniques récupérés à partir de deux capteurs différents (SWIM et SAR) présentant des artefacts distincts.

• Contexte : Les spectres SAR souffrent d'une « coupure azimutale » (déplacement de l'énergie), tandis que les spectres SWIM souffrent de « scintillement » (secteurs directionnels peu fiables). L'objectif est de comparer uniquement les systèmes de vagues physiquement cohérents.
• Méthode : L'IC-POT utilise des coûts spécifiques à chaque côté dérivés de priors physiques : protéger la masse SAR déplacée par la coupure (si soutenue par SWIM) tout en exposant la masse dominée par le scintillement ou non soutenue au rejet.
• Résultat : L'IC-POT a récupéré une énergie de vague comparable (0,993) à une base de référence globale à prix élevé, mais a réduit le transport spurious d'un facteur 7 (0,031 contre 0,236).
• Signification : Contrairement à une règle scalaire qui force un compromis entre la récupération de systèmes communs et le rejet d'artefacts, l'IC-POT permet que la politique de rejet soit définie par la nature physique des données elles-mêmes.

Signification et Limites

L'article soutient que l'IC-POT est significatif car il déplace le paradigme du transport partiel de « combien rejeter » vers « quoi rejeter ». En rendant la politique de non-appariement une variable explicite et ponctuelle, il permet aux connaissances spécifiques au domaine (biais d'échantillonnage, confiance, priors physiques) d'informer directement le plan de transport.

Limites reconnues par les auteurs :

• Spécification : Les fonctions de non-appariement ($c_s, c_t$) doivent être spécifiées par l'utilisateur en fonction des informations latérales disponibles ou des diagnostics. L'article ne propose pas de méthode pour apprendre automatiquement ces fonctions à partir des données, bien qu'il suggère cela comme une direction future (par exemple, via une optimisation bi-niveau).
• Évolutivité : Bien que le solveur épars soit exact, les applications à grande échelle peuvent nécessiter des approximations supplémentaires.
• Régularisation : Les auteurs notent que la régularisation entropique standard (Sinkhorn) ne s'applique pas directement à la formulation de support augmenté sans altérer l'objectif (introduisant un biais sur la masse totale transportée) ou créer des déséquilibres d'échelle entre les points factices et réels. Ainsi, l'IC-POT n'est pas un remplacement direct pour les solveurs OT entropiques standards.

En conclusion, l'IC-POT fournit un cadre flexible pour le rejet structuré dans le transport optimal, démontrant que l'encodage d'informations latérales dans des coûts de rejet ponctuels produit des performances supérieures dans les tâches où la décision de « non-appariement » est intrinsèquement non uniforme.