|
Apprentissage
non-supervisé
dans le cadre de la
théorie du
transport optimal
Collaborations :
Y. Bennani, C. Laclau,
Y. Redko
La théorie
du transport optimal a
été
introduite pour la
première fois par
Monge pour
étudier le
problème de
l’allocation
des ressources. En
supposant que nous ayons
un ensemble d’usines et
un ensemble de mines,
l’objectif du transport
optimal est de
déplacer le
minerai des mines vers
les usines de
manière optimale,
c’est-à-dire en
minimisant le coût
global
du transport.
La formalisation du
problème
d’optimisation de Monge
a été
donné par
Kantorovich. Ce
problème admet
une solution unique γ∗
, appelée
distance de Wasserstein,
qui est une
métrique sur
l’espace des mesures
de probabilité.
La distance de
Wasserstein a
été
utilisée avec
succès dans
diverses applications,
par exemple : vision par
ordinateur, analyse de
texture, reconstruction
tomographique,
adaptation de domaine,
apprentissage
métrique et
clustering. Cette
dernière
application est d’un
intérêt
particulier car la
distance de Wasserstein
est connue pour
être une
métrique
très efficace en
raison de sa
capacité à
prendre en compte la
géométrie
des données
à travers les
distances
par paires entre les
échantillons.
En collaboration
avec Y. Bennani, C.
Laclau et I. Redko nous
avons abordé les
problèmes
existants des
méthodes
de co-clustering
décrites
ci-dessus en proposant
une approche
principalement nouvelle
qui résout
efficacement le
problème
de co-clustering d’un
point de vue qualitatif
et informatique et
permet la
détection
automatique du nombre de
co-clusters.
Nous posons le
problème de
co-clustering comme la
tâche de
transporter la mesure
empirique définie
sur les observations
vers la mesure empirique
définie sur les
caractéristiques
des données.
L’intuition
derrière ce
processus est
très naturelle au
co-clustering et
consiste à
capturer les
associations entre les
instances et les
caractéristiques
de la matrice de
données. La
solution du
problème de
transport optimal est
donnée par une
matrice de couplage
doublement stochastique
qui peut être
considérée
comme la distribution de
probabilité
conjointe
approchée des
données
d’origine. De plus, nous
montrons que la
matrice de couplage peut
être
factorisée en
trois termes où
l’un d’eux
reflète la
distribution a
posteriori des
co-clusters de
données tandis
que les deux autres
représentent les
distributions
approchées des
observations et des
caractéristiques.
Nous
utilisons ces
distributions
approchées pour
obtenir les partitions
finales. Nous
dérivons
également une
version à noyau
de
notre méthode
qui, contrairement au
cas original, est
basée sur une
métrique de
transport optimal
définie sur
l’espace des
fonctions de
dissimilarité.
D’un point de vue
théorique, nous
avons justifié
notre approche en
démontrant que la
matrice de couplage peut
être
vue comme la solution
d’un problème
d’inférence
variationnelle. Cette
approche présente
plusieurs avantages :
l’algorithme
de Sinkhorn-Knopp
utilisé pour
résoudre le
problème du
transport optimal
régularisé
a une complexité
logarithmique ;
le nombre de classes des
objets et des variables
est
détecté
automatiquement
grâce à
l’adaptation d’un
algorithme de
détection
multi-échelle.
|
