Connaissez-vous UMAP? je connais

Si vous en avez entendu parler mais que vous ne le savez pas, cet article vous aidera à le comprendre.

Qu'est-ce que UMAP

** C'est une méthode pour réduire et visualiser les dimensions plus rapidement et avec des performances plus élevées que le t-SNE **. Comparons-le avec le t-SNE couramment utilisé. La figure ci-dessous est une visualisation de Fashion MNIST.

(De [Comprendre UMAP] [Comprendre UMAP])

Par rapport au t-SNE, l'UMAP montre que les clusters sont clairement séparés. En outre, des catégories similaires sont situées à proximité les unes des autres et des catégories différentes sont éloignées les unes des autres. (Il y a beaucoup d'exemples de visualisation dans l'explication de [Comprendre UMAP] et [Comprendre UMAP], donc s'il vous plaît voir cela pour plus de détails. Vous pouvez voir la figure 3D ci-dessus en faisant le tour)

** UMAP a un temps d'exécution presque constant quel que soit le nombre de dimensions intégrées **. Contrairement à t-SNE, le temps d'exécution n'augmente pas de façon exponentielle même si la dimension incorporée augmente, il peut donc être utilisé non seulement pour la visualisation mais aussi pour la réduction de dimension. De plus, UMAP écrit en Python est plus rapide que FIt-SNE, une implémentation rapide de t-SNE en C ++.

Et ** prend en charge l'intégration de nouveaux échantillons **. Dans le cas du t-SNE, il était difficile d'ajouter de nouvelles données à l'espace de faible dimension, et l'ensemble a dû être exécuté à nouveau. Par contre, avec UMAP, il vous suffit de calculer la différence, et vous pouvez l'intégrer naturellement.

** Si vous souhaitez simplement l'utiliser comme un outil, c'est très simple. ** (Le code provient du [document officiel] howToUseUMAP)

!pip install umap-learn

import numpy as np
from sklearn.datasets import load_digits
import matplotlib.pyplot as plt
import umap

#Essayez avec des chiffres
digits = load_digits()

#Réduit à 2 dimensions avec umap
reducer = umap.UMAP(random_state=42)
reducer.fit(digits.data)
embedding = reducer.transform(digits.data)

# plot
plt.scatter(embedding[:, 0], embedding[:, 1], c=digits.target, cmap='Spectral', s=5)
plt.gca().set_aspect('equal', 'datalim')
plt.colorbar(boundaries=np.arange(11)-0.5).set_ticks(np.arange(10))
plt.title('UMAP projection of the Digits dataset', fontsize=24);

De plus, il peut être exécuté dans un temps réaliste même pour une très grande quantité de données dimensionnelles. La figure ci-dessous est une visualisation de 30 millions d'entiers en entrée, qui est un vecteur binaire factorisé premier. (Je ne sais pas si c'est une visualisation significative, mais c'est cool)

Si vous en êtes satisfait, c'est la fin. Veuillez l'utiliser comme un outil pratique.

Méthode existante

Avant d'entrer dans l'explication d'UMAP, jetons un coup d'œil rapide aux méthodes existantes.

Jusqu'à présent, de nombreuses méthodes de réduction de dimension ont été proposées. Il est nécessaire pour pouvoir conserver la structure globale et la structure locale des données. Et récemment, une certaine vitesse de calcul est également nécessaire.

Méthode linéaire (PCA, etc.)

Fonctionne bien pour les données artificielles, mais a de mauvaises performances pour les données réelles de haute dimension. Swiss-roll ne fonctionne pas.

Méthode non linéaire

UMAP appartient ici.

Isomap
LLE
Laplacian Eignmap
t-SNE
LargeVis

Parmi eux, ** t-SNE est souvent utilisé comme une méthode ** qui permet de bien maintenir à la fois la structure globale et la structure locale. Cependant, il y avait un problème avec le temps d'exécution, et LargeVis et d'autres ont été proposés pour le résoudre. Dans cet article, je vais essayer d'expliquer UMAP de manière technique, mais je pense que ce sera plus facile à comprendre si vous avez une certaine connaissance d'Isomap et de t-SNE. Les articles répertoriés dans les méthodes existantes sont résumés dans Références.

Définition de caractère

Voici quelques définitions pour le futur.

--Nombre de données $ N $

$ n $ Ensemble de données de dimension haute dimension $ X $
- X = \\{x_1, x_2, ..., x_N\\}, \; x_i \in \mathbb{R}^n
$ m $ Ensemble de données de dimensions réduites $ Y $ ($ m << n $)
- Y = \\{y_1, y_2, ..., y_N\\}, \; y_i \in \mathbb{R}^m

Ci-après, ces caractères seront utilisés sans préavis.

Compréhension technique de l'UMAP

Tout d'abord, reconfirmons le but de l'UMAP.

** Conversion de données de haute dimension $ X $ en données de faible dimension $ Y $. Cependant, la structure locale et la structure globale de $ X $ sont conservées et converties. ** **

Les articles UMAP ne peuvent pas être vraiment compris sans connaissance des mathématiques. Cependant, l'article contient des explications pour ceux qui n'ont pas de connaissances en mathématiques. UMAP est basé sur des mathématiques avancées, mais en fait ** UMAP peut être considéré comme une création et une opération de graphe sur le graphe **. En effet, UMAP est basé sur une idée très similaire à Isomap, t-SNE, Large Vis, etc.

Le déroulement de la méthode est les deux étapes suivantes.

Créez un graphique de k-voisinage pondéré
Placez le graphique dans une dimension inférieure

La figure est tirée de [Large Vis Paper] [Large Vis Paper]

L'étape 1 se concentre sur la structure locale des données. Ensuite, le graphe construit à partir de la structure locale est agencé de manière à représenter la structure globale à l'étape 2 (image). Puisque la distance de la station peut être considérée localement comme la distance euclidienne dans une variété, l'image d'un bluff proche utilisant la distance euclidienne est suffisante. (En fait, cela ne se limite pas à la distance, mais il peut également être utilisé pour des choses comme la dissemblance.)

Regardons-les dans l'ordre.

1. Créez un graphique de k-voisinage pondéré

① Faire un graphique près de k

Tout d'abord, faisons un graphe de voisinage sans pondération. Définissez des distances (métriques) $ d $ pour trouver le voisinage (Imaginez une distance euclidienne, etc.).

Ensuite, les k voisinages dans la métrique $ d $ de $ x_i $ sont écrits comme suit. \\{x_{i_1}, ..., x_{i_k}\\}

La recherche de voisinage peut utiliser la méthode normale k-near, mais UMAP utilise une méthode d'approximation. La méthode normale de k-voisinage coûte $ O (N ^ 2) $, mais la méthode d'approximation accélère jusqu'à $ O (N ^ {1.14}) $. Pour plus de détails, reportez-vous à la référence [Avant-plan de la recherche approximative du voisin le plus proche] [Knn approx.

Une fois la recherche de quartier terminée, créez un graphique de k-voisinage en regroupant les quartiers. Autrement dit, l'ensemble de côtés $ E $ et l'ensemble de sommets $ V $ sont définis comme suit.

E = \\{(x_i, x_{i_j}) \; | \; 0\leq i \leq N, \, 0\leq j \leq k \\} $ V $ correspond à chaque point des données.

De cette façon, un graphe à k-voisins dirigés $ G_1 $ a été créé sans pondération. $ G_1 = (V, E) $

Pour résumer un peu ** Dans "(1) Création d'un graphe de k-voisinage", k voisinages ont été recherchés pour chaque $ x_i $ de données de grande dimension $ X $, et un graphe de k-voisinage dirigé non pondéré $ G_1 $ a été créé. ** **

➁ Créez un graphe de k-voisinage pondéré

Pour ajouter du poids, définissez d'abord la fonction de pondération $ w $. Le côté droit est normalisé par $ \ rho_i $ et $ \ sigma_i $.

w((x_i, x_{i_j})) = \exp(\dfrac{-\max(0, \, d(x_i, x_{i_j})-\rho_i)}{\sigma_i})

Où $ \ rho_i $ est la distance au voisin le plus proche. \rho_i = \min\\{d(x_i, x_{i_j}) \; |\; 1\leq j \leq k \\}

De plus, $ \ sigma_i $ est obtenu par une recherche en deux parties afin de satisfaire l'équation suivante. \Sigma_j w((x_i, x_{i_j})) = \log_2 (k) $ \ Log_2 (k) $ sur le côté droit est obtenu empiriquement.

(Ce $ log_2 {k} $ est quelque chose que je ne sais pas, mais je pense qu'il a une signification perplexe de t-SNE parce que la distribution est calculée par une recherche en deux parties.)

Créez un graphique pondéré dirigé $ G_2 $ en utilisant la fonction de pondération ci-dessus. G_2 = (V, E, w)

Cependant, ce $ G_2 $ n'est pas utilisé tel quel. Créez un graphique non orienté $ G $ par la conversion suivante. $ A $: matrice adjacente de $ G_2 $ $ B = A + A ^ T-A \ circ A ^ T, \ circ: Produit Adamal $

Si vous regardez les éléments de $ B $, vous pouvez voir qu'ils ciblent. B_{i,l} = w((x_i, x_l)) + w((x_l, x_i)) - w((x_i, x_l))*w((x_l, x_i)) \\ = B_{l. i}

(Je pense que cela fonctionne de la même manière que t-SNE symétrisant la probabilité conditionnelle de SNE. La fonction de coût devient plus facile à gérer.)

Le graphe $ G $ est créé en utilisant le $ B $ ainsi créé comme matrice adjacente. Placez ce graphique $ G $ à l'étape ➂ dans une dimension inférieure.

Pour résumer un peu ** Dans "➁ Créer un graphe de k-voisinage pondéré", un graphe de k-voisinage pondéré et non orienté $ G $ a été créé **.

2. Placer dans une dimension inférieure

Maintenant que nous avons une matrice adjacente, nous voulons la placer dans un espace de faible dimension. Cependant, la méthode de dessin d'un graphique à partir d'une matrice adjacente n'est pas unique. Regardez les deux figures ci-dessous.

Les deux sont des visualisations du même graphique (les images proviennent [ici] [explication du modèle mécanique]). Utilisez le ** modèle dynamique ** pour un placement soigné. Comme l'explication sera longue, j'ai écrit l'explication du modèle dynamique dans [article séparé de Qiita (algorithme de dessin de graphe et verso de Networkx)] [modèle dynamique de Qiita]. Dans le modèle dynamique, les sommets sont bien agencés avec l'algorithme suivant.

Calculez la force attractive / répulsive agissant entre chaque sommet
Déplacez les sommets en fonction de la force calculée en 1. L'amplitude du déplacement mobile est inférieure ou égale au paramètre de température $ t $
Abaissez le paramètre de température
Répétez les étapes 1 à 3 un certain nombre de fois

Puisqu'il est nécessaire de définir la force d'attraction et la force de répulsion dans le modèle mécanique, elle est définie comme suit. J'expliquerai pourquoi cette formule est un peu plus tardive, alors je l'accepterai et continuerai.

f_a(y_i, y_j) = \dfrac{-2ab\|y_i - y_j\|^{2(b-1)}} {1+\|y_i - y_j\|^2} w((x_i, x_j))(y_i - y_j)

f_r(y_i, y_j) = \dfrac{b} {(\epsilon + \|y_i - y_j\|^2)(1 + \|y_i - y_j\|^2)} (1 - w((x_i, x_j))) (y_i - y_j)

$ a, b $: Hyper paramètres $ \ Epsilon $: Petite valeur pour éviter la division zéro

Cependant, l'UMAP a rationalisé le calcul de la force répulsive. Considérant un sommet $ x_i $

La force d'attraction fonctionne sur k à proximité
La force de répulsion fonctionne sur N-k pièces autres que le voisinage

Généralement, $ k << N $, donc le calcul de la force répulsive devient un goulot d'étranglement. UMAP utilise ** l'échantillonnage négatif ** pour réduire la quantité de calcul. Les sommets qui ne sont pas connectés par des côtés sont considérés comme connectés par une arête négative.

Ensuite, échantillonnez correctement ce bord négatif et mettez-le à jour provisoirement. UMAP utilise la distribution d'échantillonnage de vertex suivante $ P $. Cela peut être approximé à une distribution uniforme dans un ensemble de données suffisamment grand. (Je ne sais pas à ce sujet, alors dites-moi s'il vous plaît.)

P(x_i) = \dfrac{ \sum_{\{a \in A | d_0(a) = x_i\}}{1 - \mu(a)} }{ \sum_{\{b\in A | d_0(b) \neq x_i \}}{1 - \mu(b)} }

$ \ mu $: Fonction d'appartenance (degré d'appartenance à $ \ mu: A \ rightarrow [0, 1] $, $ A $) $ A $: expression topologique floue (probable)

Lors de la mise à jour de l'emplacement, au lieu d'utiliser tous les bords négatifs, échantillonnez et mettez à jour certains. En d'autres termes, l'algorithme est le suivant.

Calculez la force d'attraction agissant entre chaque sommet. ** La force répulsive est calculée par échantillonnage avec une distribution $ P $ **.
Déplacez les sommets en fonction de la force calculée en 1. L'amplitude du déplacement mobile est inférieure ou égale au paramètre de température $ t $
Abaissez le paramètre de température
Répétez les étapes 1 à 3 un certain nombre de fois

Je ne sais pas si la convergence est garantie, mais empiriquement, elle semble converger correctement.

Cette compréhension est-elle complètement différente du flux original? ??

"L'article de l'UMAP est à l'origine incroyablement mathématique, mais y a-t-il une explication maintenant?"

"Comment vous reliez-vous à la topologie floue et à la variété Lehman?"

Pour ceux qui réfléchissent, écrivez la pertinence par rapport au flux d'origine. Pour ce faire, nous devons d'abord connaître le flux mathématique d'origine ...

Flux UMAP d'origine

Ceux qui ont des connaissances en mathématiques devraient comprendre ce flux.

Formulation
Dérivation de la fonction de coût
Minimisez la fonction de coût et intégrez-la dans une dimension inférieure

Jetons un coup d'œil à chacun d'eux.

1. Formulation

Pour avoir un aperçu, je citerai une partie de [Qiita lisant les articles UMAP] et [Qiita lisant les articles UMAP].

Les concepts suivants sont introduits dans UMAP. (Hey)

fuzzy set --Ensemble flou

simplicial set --Composé

fuzzy simplicial set --Combinaison de 1 et 2

FinReal --Convertir une seule unité en EPMet

FinSing --Convertir EPMet en ensemble simplicial flou

Et définissez l'opération pour transformer la séquence de points en une expression topologique floue.

Tout d'abord, le chapitre 1 a décrit comment estimer la variété Lehman à partir d'une séquence de points de données. Cependant, je n'ai pas vraiment estimé la forme de la diversité elle-même, mais estimé la distance sur l'espace fini (FinEPMet).

Dans le chapitre 3, nous avons défini un ensemble simplicial flou qui ressemble à un composé flou, et défini une opération appelée FinSing pour convertir un FinEPMet en un ensemble simplicial flou.

Je ne sais pas si je viens de le citer, mais je pense que c'est probablement parce que le mathématicien le dit (compréhension abandonnée). Si vous souhaitez en savoir plus sur ce domaine, l'article suivant vous sera utile. Si vous êtes à l'aise avec l'anglais, la lecture de l'article est précise.

Lire l'article Qiita UMAP Lire l'article Qiita UMAP
[Article de commentaire UMAP] [Article suivant la formule UMAP]

2. Dérivation de la fonction de coût

L'entropie croisée des deux expressions topologiques floues est définie comme suit.

C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}

$ \ mu, \ nu $: Fonction d'appartenance (degré d'appartenance à $ \ mu: A \ rightarrow [0, 1] $, $ A $) A：Fuzzy topological expression

La raison pour laquelle ce n'est pas un nombre égal est que le côté droit est la formule après avoir omis la partie qui n'est pas liée à la minimisation. (Voir l'article pour plus de détails.)

3. Minimisez la fonction de coût et intégrez-la dans une dimension inférieure

--Convertir des données de haute dimension en expression topologique floue $ X $ --Convertissez également les données de faible dimension (destination d'incorporation) en expression topologique floue $ Y $

Les données de faible dimension $ Y $ sont modifiées selon la méthode du gradient afin que l'entropie croisée entre les expressions topologiques floues soit minimisée. Le $ Y $ ainsi créé est le résultat de la visualisation ou le résultat de la réduction de dimension.

Pour résumer si grossièrement,

** Il existe une fonction de coût dérivée par un mathématicien. ** ** ** Minimisez cela pour l'incorporation de faible dimension basée sur les mathématiques. ** **

Connexion avec la compréhension de l'ingénierie jusqu'à présent

"Quelle était l'explication du graphe de k-voisinage et du modèle dynamique plus tôt!?" Je suis désolé de vous avoir fait attendre. ** La définition de la force attractive / répulsive dans le modèle dynamique est liée à la fonction de coût **.

La fonction de coût pourrait être écrite comme suit.

C((A, \mu), (A, \nu)) \rightarrow \sum_{a \in A}{( \mu(a)\log(\nu(a)) + (1 - \mu(a)) \log(1-\nu(a)) )}

$ \ mu, \ nu $: Fonction d'appartenance (degré d'appartenance à $ \ mu: A \ rightarrow [0, 1] $, $ A $) A：Fuzzy topological expression

Si vous examinez attentivement l'équation, vous pouvez voir la relation avec le modèle dynamique. Puisque $ \ mu $ est une fonction d'appartenance pour des données de dimensions supérieures, $ \ mu (a) $ appartient à $ A $ et $ (1- \ mu (a)) $ appartient à $ A $. Degré non. Autrement dit, le premier terme de $ \ sum $ peut être considéré comme un terme qui agit sur le voisinage, et le second terme peut être considéré comme un terme qui agit sur autre que le voisinage.

La ** force d'attraction et la force de répulsion mentionnées précédemment sont calculées à partir de la fonction de coût ** (bien que non spécifiée dans l'article, après avoir dérivé la fonction de coût même avec la méthode existante LargeVis, le terme correspondant à la force de répulsion est efficacement échantillonné par échantillonnage négatif. Est calculé).

Après tout, la connaissance des mathématiques est nécessaire pour aller au fond de la définition de l'attraction / répulsion. Cependant, j'estime que la compréhension de «créer un graphe et de l'intégrer en fonction de la force» est une longueur d'avance sur celle de «minimiser la fonction de coût qui n'est pas bien comprise».

finalement

Il est intéressant de noter que l'UMAP, qui est mathématiquement difficile, peut être formulé avec un modèle mécanique simple (bien que ce soit un peu technique). C'est la compréhension maximale pour quelqu'un (moi) qui n'a aucune formation en mathématiques. Je ne sais pas si je peux l'expliquer, il serait donc utile que vous puissiez signaler les erreurs en frappant le papier sans prendre cet article comme une hirondelle.

Les références

[UMAP: UniformManifold ApproximationandProjectionfor DimensionReduction, arXiv] [UMAP Paper] : Voici tout

Lire l'article Qiita UMAP Lire l'article Qiita UMAP
[Article de commentaire UMAP] [Article suivant la formule UMAP] : Ces deux articles tentent de comprendre les formules mathématiques

Understanding UMAP : Il y a des chiffres abondants et c'est facile à comprendre. C'est intéressant juste de le regarder, alors jetez un œil.

[document UMAP] [document UMAP]
HowToUseUMAP : Si vous souhaitez l'utiliser comme outil, regardez ici

[Réduction de dimensionnalité avec t-SNE (Rtsne) et UMAP (uwot) à l'aide des packages R.] De tSNE à UMAP (système testé) : Obtenez un aperçu de t-SNE et UMAP. Pratique> Théorie

[Algorithme de dessin graphique et dans les coulisses de Networkx] Modèle dynamique Qiita : Explication des algorithmes typiques de modèle dynamique. (Mon article)

[Avant-plan de la recherche approximative du voisin le plus proche] [Knn approx. : Division spatiale par arbre, hachage, faire l'hypothèse que "à proximité est aussi proche" est intéressant

Vous pouvez approfondir votre compréhension en lisant les articles suivants.

[Barns-Hut-SNE] [Papier Barns-Hut-SNE]
[(t-SNE) Visualisation des données à l'aide de t-SNE] [papier t-SNE]
[(LargeVis) Visualisation de données à grande échelle et à haute dimension] LargeVis Paper
(fruchterman-reingold algorithm) Graph drawing by force‐directed placement

Je veux comprendre (l'ingénierie) UMAP plus fort que t-SNE