Skip to content
Retour aux résultats

Achèvement de matrice

Introduite par
Emmanuel Candès & Benjamin Recht
Année
2009
Type
Convex low-rank recovery
Famille
Missing data

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

L'achèvement de matrice est une technique permettant de retrouver une matrice de rang faible à partir d'un sous-ensemble petit, éventuellement aléatoire, de ses entrées.

Introduit par Emmanuel Candès et Benjamin Recht en 2009, il reformule le problème en minimisation de la norme nucléaire — un substitut convexe à la minimisation du rang — et fournit des garanties théoriques selon lesquelles une récupération exacte est réalisable lorsque les entrées sont observées uniformément au hasard et que la matrice satisfait une condition d'incohérence.

L’intuition derrière la méthode

Imaginez une feuille de calcul partiellement remplie de notes d'utilisateurs sur des films, où la plupart des cellules sont vides. Si les données sous-jacentes ont une structure simple — disons, que les goûts sont expliqués par seulement quelques facteurs latents comme la préférence pour le genre et l'époque — alors connaître même une petite fraction des notes suffit à remplir le reste avec confiance. L'achèvement de matrice exploite cette structure cachée de faible dimension, un peu comme compléter un puzzle dont on sait que l'image ne présente que quelques formes distinctes.

Histoire

L'achèvement de matrice est né de la littérature sur la détection comprimée. Candès et Recht (2009) ont établi le premier théorème de récupération exacte via la minimisation de la norme nucléaire, suivi de près par les travaux de Candès et Tao sur le pouvoir de l'incohérence. La méthode a gagné une large attention publique grâce au concours Netflix Prize, où les méthodes de filtrage collaboratif de rang faible ont atteint une précision de recommandation de pointe. Les travaux ultérieurs de Recht, Fazel et Parrilo ont lié la minimisation de la norme nucléaire à la régularisation par norme de trace en apprentissage automatique.

Quand l’utiliser

Utilisez l'achèvement de matrice lorsque les données peuvent être organisées sous forme de matrice avec des entrées systématiquement manquantes et qu'il y a une raison de croire que le signal réel est de rang faible — par exemple, dans les systèmes de recommandation, la génomique, l'analyse des réseaux sociaux et la récupération d'images. Les hypothèses clés sont que les entrées sont manquantes au hasard et que la matrice satisfait une condition d'incohérence. Elle n'est pas appropriée pour les matrices avec des données manquantes structurées ou non aléatoires, une structure de rang très élevé, ou lorsque l'hypothèse de rang faible est injustifiée. Les alternatives incluent l'imputation MICE pour les données manquantes générales et NMF lorsque la non-négativité est requise.

Limites et points d’attention

  • Le coût de calcul de la programmation semi-définie évolue mal avec les dimensions de la matrice
  • L'hypothèse d'incohérence peut échouer sur des jeux de données réels avec des données manquantes structurées ou des valeurs aberrantes
  • Les performances se dégradent lorsque le rang réel n'est pas beaucoup plus petit que les dimensions de la matrice
  • La minimisation de la norme nucléaire peut être sensible au bruit ; les variantes robustes ajoutent une complexité supplémentaire

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Récupération exacte prouvable dans des conditions douces avec un programme convexe en temps polynomial
  • Gère des taux très élevés de données manquantes lorsque la matrice est réellement de rang faible
  • Aucune connaissance préalable du rang n'est requise ; la minimisation de la norme nucléaire le trouve implicitement
  • Garanties théoriques solides ancrées dans la théorie des matrices aléatoires et l'analyse convexe

Applications

  • Filtrage collaboratif et systèmes de recommandation (prédiction des notes utilisateur-article)
  • Génomique et bioinformatique (récupération de matrices d'expression génique avec des mesures manquantes)
  • Vision par ordinateur (inpainting d'images et soustraction de fond vidéo)
  • Localisation de réseaux de capteurs (récupération de matrices de position à partir de mesures de distance partielles)
  • Neurosciences (achèvement de matrices de connectivité fonctionnelle à partir d'observations IRMf partielles)

Comment ça marche

Comment ça marche

1

L'algorithme commence avec une matrice M dont les entrées ne sont observées que sur un ensemble d'indices Omega. Ces valeurs observées forment les contraintes du problème de récupération. Le schéma de sparsité est supposé être échantillonné uniformément au hasard, ce qui constitue le cadre théorique dans lequel les garanties de récupération exacte sont établies.

Formule
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

Parce que minimiser directement le rang d'une matrice est NP-difficile, Candès et Recht proposent de minimiser la norme nucléaire — la somme des valeurs singulières — comme une relaxation convexe. La norme nucléaire joue le même rôle pour les matrices que la norme L1 pour les vecteurs en détection comprimée : elle favorise les solutions de rang faible tout en gardant le problème traitable par programmation semi-définie.

Formule
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

Pour que la récupération soit possible, les vecteurs singuliers de la vraie matrice ne doivent pas être trop alignés avec la base standard, quantifié par le paramètre d'incohérence mu. Les matrices qui concentrent leur énergie dans seulement quelques lignes ou colonnes sont incohérentes ; les matrices hautement localisées violent cette condition et ne peuvent pas être récupérées à partir d'un échantillon aléatoire, car trop d'informations sont encodées dans les entrées non observées.

Formule
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}
4

Lorsque le nombre d'entrées observées dépasse un seuil proportionnel à mu fois le rang r fois n log n, le minimiseur du problème de norme nucléaire récupère la vraie matrice exactement avec une haute probabilité. Ce résultat montre que la taille de l'échantillon requise n'est que logarithmiquement plus grande que les degrés de liberté intrinsèques d'une matrice de rang-r, rendant l'approche quasi-optimale du point de vue de la théorie de l'information.

Formule
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}

Pièges courants

  • Supposer des données manquantes aléatoires uniformes alors que les observations réelles sont sélectionnées par l'utilisateur ou biaisées (par exemple, seuls les articles très bien notés sont notés), ce qui viole le modèle d'échantillonnage théorique
  • Négliger de vérifier la condition d'incohérence, conduisant à une mauvaise récupération même avec des observations suffisantes
  • Utiliser la minimisation de la norme nucléaire sans mise à l'échelle ou régularisation dans un cadre bruité, où la formulation de récupération exacte est inappropriée
  • Confondre l'achèvement de matrice avec des heuristiques de factorisation de matrice : les moindres carrés alternés peuvent converger vers des minima locaux et manquent des garanties de récupération de la minimisation de la norme nucléaire

Questions fréquentes

La minimisation de la norme nucléaire est-elle la seule façon de résoudre l'achèvement de matrice ?

Non. Les moindres carrés alternés (ALS) et la descente de gradient sur des formes factorisées (par exemple, SGD sur U et V tels que M ≈ UV^T) sont largement utilisés en pratique pour la scalabilité. Cependant, ces approches non convexes manquent des garanties de récupération exacte de la minimisation de la norme nucléaire et peuvent converger vers des minima locaux sans initialisation soignée.

Quelle quantité de données est nécessaire pour une récupération exacte ?

Candès et Recht ont montré qu'environ C·mu·r·n·log(n) entrées observées suffisent pour une matrice n×n de rang r avec un paramètre d'incohérence mu. En pratique, cela signifie qu'une matrice de rang faible peut souvent être récupérée à partir d'un échantillon qui n'est qu'un petit multiple de ses degrés de liberté intrinsèques, qui sont égaux à r(2n−r) pour une matrice n×n.

Qu'est-ce que la condition d'incohérence et pourquoi est-elle importante ?

L'incohérence mesure à quel point les vecteurs singuliers sont répartis sur la base coordonnée. Une matrice avec des vecteurs singuliers concentrés — comme une matrice de rang 1 qui n'est non nulle que dans une seule ligne — stocke la majeure partie de son information dans un petit ensemble d'entrées. Si ces entrées se trouvent être non observées, la récupération est impossible quelle que soit le nombre d'autres entrées connues.

Méthodes associées

Sources

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    Ouvrir la référence DOI
    Copié.