Résumé

La réduction de la dimensionnalité se produit naturellement dans de très nombreuses applications d’apprentissage machine. Même si le phénomène demeure en grande partie un mystère conceptuel, les chercheurs croient que plus la réduction du nombre de dimensions est importante, plus la perte d’information est forte. Il est cependant ardu de confirmer le taux de cette perte d’information et de formuler le problème (même pour de très simples distributions de données et mappages de réductions non linéaires).

Dans cet article, nous tentons de quantifier de façon rigoureuse ces observations empiriques, du point de vue de la recherche d’information, en appliquant des techniques fondées sur la géométrie. Nous commençons par formuler le problème en adaptant deux indicateurs fondamentaux de la recherche d’information – la précision et le rappel – au cadre d’analyse de fonction (continue). Ce changement de perspective nous permet d’emprunter des outils de topologie quantitative pour établir le premier taux démontrable de perte d’information attribuable à la réduction de la dimensionnalité.

Nous avons été surpris de découvrir que la précision diminuait de façon exponentielle à mesure que nous supprimions des dimensions. Cette découverte devrait alerter les praticiens et les chercheurs expérimentaux qui tentent d’interpréter des mappages de réduction de la dimensionnalité. Par exemple, il pourrait être impossible de concevoir des systèmes de recherche d’information qui offrent à la fois des niveaux élevés de précision et de rappel. Cette constatation doit nous rappeler les limites des algorithmes de réductions de dimensions, y compris des plus performants tel t-SNE.

Si la précision et le rappel sont des indicateurs naturels de recherche d’information, ils ne tirent pas directement parti de l’information relative à la distance séparant les données (p. ex., dans le cas de la visualisation des données). Nous proposons donc un indicateur de remplacement pour la réduction des dimensions, fondé sur les distances de Wasserstein, qui tient compte de façon démontrable de l’effet de réduction de la dimensionnalité. Pour obtenir cette garantie théorique, nous résolvons le problème d’optimisation itérative suivant :

\[
\inf_{W:\,\text{Vol}_n(W) = M} W_{2}(\mathbb{P}_{B_r}, \mathbb{P}_{W})
=
\inf_{W:\,\text{Vol}_n(W) = M} \inf_{\gamma \in \Gamma (\mathbb{P}_{B_r} , \mathbb{P}_{W})} \mathbb{E}_{(a, b) \sim \gamma} [ \| a - b \|^{2}_{2} ]^{1/2} ,
\]

en exploitant les publications récentes relatives au transport partiel optimal.

Précision et rappel en apprentissage supervisé, discrets

Même si la précision et le rappel sont des concepts familiers dans les problèmes d’apprentissage supervisé, procédons à une brève récapitulation de ces concepts avant de les adapter au contexte de la réduction de la dimensionnalité.

Dans un cadre d’apprentissage supervisé, par exemple la classification des chats et des chiens, nous sélectionnons d’abord le facteur de classification favori pour le réseau neuronal $f_{W}$, puis rassemblons 1 000 images d’essai.

\[
Precision = 1/2 \frac{\text{How many are cats}}{\text{Among the ones predicted as cats}} + 1/2 \frac{\text{How many are dogs}} {\text{Among the ones predicted as dogs}}
\]

\[
Recall = 1/2 \frac{ \text{How many are predicted as cats}}{\text{Among the cats}} + 1/2 \frac{\text{How many are predicted as dogs}}{\text{Among the dogs}}
\]

Règle générale, nous pouvons établir des valeurs moyennes pour la précision et le rappel dans $n$ classes.

Précision et rappel en apprentissage non supervisé, continus

Les formules que nous avons utilisées pour la prévision et le rappel sont inspirées du contexte de l’apprentissage supervisé. Comme la réduction de la dimensionnalité peut, dans les faits, se produire dans un contexte non supervisé, nous avons dû changer quelques paramètres. Dans un mappage type de réduction de la dimensionnalité $f: X \rightarrow Y$, nous veillons souvent à préserver la structure locale après la réduction.

Comme un contexte non supervisé signifie l’absence d’étiquettes, notre première démarche a consisté à remplacer l’expression « étiquette pour une entrée x » par « points avoisinants pour une entrée x avec un nombre élevé de dimensions ». Nous ne disposions pas non plus de prédictions, mais nous étions d’avis qu’il était logique de remplacer l’expression « prédiction pour une entrée x » par « points avoisinants pour une entrée y = f(x) en faible nombre de dimensions ».

Lors du calcul de la précision et du rappel dans les cas d’apprentissage supervisés, nous établissons des moyennes pour les diverses étiquettes. Par conséquent, notre deuxième étape a consisté à calculer des moyennes pour chaque point de données.

\[Precision = \frac{1}{n} \sum_{x \in X_n} {\text{How many are neighbors of} ~x~ \text{in high dimension} / \text{Among the low dimensional neighbors of}~ y = f(x)}
\]

\[Recall = \frac{1}{n} \sum_{x \in X_n} {\text{How many are neighbors of} ~y = f(x)~ \text{in low dimension} / \text{Among the high dimensional neighbors of} ~x}
\]

Précision et rappel équivalent approximativement à l’injectivité et à la continuité

Par contre, il était encore difficile de prouver quoi que ce soit, même dans le contexte exposé ci-dessus. L’un des problèmes était que « f » est un mappage entre des espaces continus, alors que les points de données constituent des échantillons finis. Ceci nous a amenés à rechercher des équivalents continus des exemples ci-dessous :

 

 

Nous en sommes finalement arrivés à l’une des observations clés de cet article : la précision équivaut approximativement à l’injectivité, et le rappel équivaut approximativement à la continuité.

Pourquoi la perte d’information est-elle inévitable lors de la réduction de la dimensionnalité?

Élaborons certaines notions intuitives à l’aide du mappage linéaire. L’algèbre linéaire nous apprend qu’un mappage linéaire de $\mathbb{R}^n$ sur $\mathbb{R}^m$ doit comporter un espace nul comptant au moins $n - m$ dimensions. On pourrait interpréter ceci comme le « comment » et le « pourquoi » de la perte d’information dans les mappages linéaires : des points distants dans le modèle à nombre élevé de dimensions sont confondus en un seul point dans le modèle à faible nombre de dimensions. Ce processus produit une très faible précision. 

En pratique, les mappages de réduction de la dimensionnalité peuvent être beaucoup plus adaptables que les mappages linéaires. Cette expressivité permet-elle de contourner le problème d’écart du nombre de dimensions issu de l’algèbre linéaire? Pour étudier la réduction du nombre de dimensions dans des mappages en continu, nous avons eu recours à l’étude correspondante des dimensions topologiques : l’inégalité isopérimétrique de la topologie quantitative. En définitive, un mappage continu d’un nombre élevé de dimensions à un nombre restreint de dimensions ne parvient pas à contourner le problème qui affecte les mappages linéaires, soit que de nombreux mappages en continu condensent plusieurs points en un seul. Pour la plupart des éléments $x$, nous avons l’égalité $y = f(x): \text{Vol}_{n-m} f^{-1}(y) \ge C(x) \text{Vol}_{n-m} B^{n-m}$.

En gros, le voisinage pertinent de $U$ de $x$ est généralement petit, dans l’ensemble des $n$ directions, alors que le voisinage de récupération $f^{-1}(V)$ est grand dans n-m directions. En raison de cet écart quantitatif, il est très difficile d’atteindre un niveau de précision élevé pour un mappage continu de la réduction de la dimensionnalité. C’est cet écart qui est à l’origine de la diminution exponentielle de la précision :

\[
    Précision^{f}(U, V)
\leq
D(n, m)\,\left(\frac{r_U}{R}\right)^{n-m}\,\frac{ r_U^{^{m}} }{p^{m}(r_V/L)}
\]

Mesure des imperfections

Le compromis et le phénomène de perte d’information exposés ci-dessus ont été largement observés par les chercheurs expérimentaux. Bien entendu, les praticiens ont mis au point différents outils pour mesurer les imperfections. Le mécanisme ayant mené à ce compromis est toutefois moins clair. Comme nous avons quelque peu éclairci cet aspect, nous sommes maintenant en mesure de concevoir des outils de mesure plus efficaces.

Soit un calcul naïf de la précision et du rappel :

\[
Precision =
\frac{\mathrm{~How~many~points~are~high~dimensional~neighbors~of}~x }{\mathrm{Among~the~low~dimensional~neighbors~of}~y}
\]

\[
Recall =
\frac{\mathrm{~How~many~points~are~low~dimensional~neighbors~of}~y }{\mathrm{Among~the~high~dimensional~neighbors~of}~x}
\]

Ces deux quantités sont égales si l’on fixe le nombre de points avoisinants. (En effet, le numérateur des deux expressions est le même; si l’on fixe le nombre de points avoisinants, les dénominateurs deviennent eux aussi identiques.) L’adoption d’une valeur fixe pour le nombre de points avoisinants est l’une des raisons expliquant le succès de l’algorithme t-SNE, car certains points de données sont relativement éloignés des autres. Si on ne les fixait pas, certains points périphériques ne comporteraient aucun point avoisinant.

Changeons maintenant le calcul en établissant des valeurs discrètes pour la précision et le rappel continus présentés ci-dessus.

\[
Précision =
\frac{\#(\mathrm{points~within~r_U~from}~x~\mathrm{and~within~r_V~from}~y)}{\#(\mathrm{points~within~r_V~from}~y)}
\]

\[
Rappel = \frac{\#(\mathrm{points~within~r_U~from}~x~\mathrm{and~within~r_V~from}~y)}{\#(\mathrm{points~within~r_U~from}~x)}
\]

Cette formule crée non seulement un nombre inégal de points avoisinants, mais a aussi pour conséquence de réduire considérablement le nombre de points avoisinants de plusieurs points de données. Ceci est partiellement causé par la géométrie à nombre élevé de dimensions. D’une manière ou d’une autre, il peut sembler que la précision et le rappel sont des quantités difficiles à gérer dans des situations pratiques.

Revoyons le problème sous un autre angle. Le taux de réduction du nombre de dimensions fourni par la preuve de précision indique clairement que l’écart provient de $f^{-1}(V)$ et de $U$, ce qui correspond à l’imperfection d’injectivité. Du point de vue heuristique, les quantités parallèles pour l’imperfection de continuité sont f(U) et V.

Nous proposons par conséquent les mesures de Wasserstein suivantes :

\[
    W_{2}(\mathbb{P}_U, \mathbb{P}_{f^{-1}(V)})
\]

\[
W_{2}(\mathbb{P}_{f(U)}, \mathbb{P}_V)
\]

Comme dans le cas de la précision et du rappel, nous avons associé les deux mesures de Wasserstein pour chaque point du mappage de visualisation de réduction de la dimensionnalité.

Mesure de l’imperfection de la réduction de la dimensionnalité : conclusions pratiques

i) Sur le plan théorique, nos travaux éclairent les compromis inhérents à tout modèle de mappage de réduction de la dimensionnalité (p. ex., intégration de la visualisation).

ii) Sur le plan pratique, nos travaux fournissent un outil de mesure qui permettra d’améliorer les méthodes d’exploration des données. Jusqu’à maintenant, les praticiens se sont trop appuyés sur les visualisations avec un faible nombre de dimensions. Or, dans le meilleur des cas, les visualisations avec un faible nombre de dimensions ne rendent pas correctement compte des structures de données comptant un nombre élevé de dimensions. Et dans le pire des cas, elles peuvent générer des représentations incorrectes susceptibles d’entacher toute analyse subséquente fondée sur ces représentations. Nous recommandons fortement aux praticiens d’améliorer leur pratique en y intégrant une mesure de fiabilité pour chaque point de données dans toutes leurs visualisations de données.