Comprendre t-SNE et améliorer la visualisation

introduction

Cette fois, j'ai résumé l'algorithme de réduction de dimension ** t-SNE ** (t-Distributed Stochastic Neighbor Embedding). t-SNE est un ** algorithme de réduction de dimension ** pour la conversion et la visualisation de données haute dimension en 2 ou 3 dimensions, et a été développé par le professeur Hinton, également connu comme le père de l'apprentissage profond. (Le professeur Hinton est incroyable) Cette fois, je vais comprendre ce t-SNE et améliorer la puissance de visualisation.

référence

Pour comprendre t-SNE, je me suis référé à ce qui suit.

Vue d'ensemble du t-SNE

L'origine du t-SNE

** t-SNE ** est un algorithme de réduction de dimension permettant de déposer des données de grande dimension en 2 ou 3 dimensions. L'ACP et le MDS sont les classiques de la réduction de dimension, mais il y avait quelques problèmes avec ces réductions de dimension linéaires.

  1. ** Un algorithme qui se concentre sur le fait de garder différentes données éloignées dans les dimensions inférieures **, il est donc vulnérable à la conservation de données similaires proches dans les dimensions inférieures
  2. En particulier pour les données non linéaires de dimensions supérieures, il est presque impossible de "conserver des données similaires à proximité même dans les dimensions inférieures" **

Afin de résoudre ces problèmes, diverses technologies de réduction de dimension non linéaire ** ont été créées pour maintenir la structure locale des données (en gardant des données similaires proches même dans les dimensions inférieures). J'ai fait. t-SNE est un algorithme qui suit cette tendance.

Ci-dessous, une image de données non linéaires.

figure_10_original.png

Caractéristiques du t-SNE

Les points de t-SNE sont décrits. Je voudrais décrire en détail le contenu spécifique du processus et les raisons des avantages et des inconvénients dans l'explication de l'algorithme ci-dessous.

** Points de traitement **

--Convertir pour que la distribution de distance dans la dimension supérieure corresponde autant que possible à la distribution de distance dans la dimension inférieure.

mérite

Démérite

--Si vous modifiez la Perplexité (paramètre interne), un cluster complètement différent apparaîtra.

Algorithme t-SNE

Pour comprendre l'algorithme t-SNE, nous commençons par comprendre son prédécesseur, l'algorithme SNE. Après cela, nous allons régler les problèmes de SNE et résumer le t-SNE créé en résolvant les problèmes.

Comment fonctionne SNE

1. Convertir la distance entre les points de données en probabilité conditionnelle

SNE commence par convertir la distance entre les points de données en probabilité conditionnelle. Sélectionnez $ x_ {j} $ comme voisinage pour la similitude entre les points de données $ x_ {i} $ et $ x_ {j} $, étant donné $ x_ {i} $ ** Probabilité conditionnelle $ p_ { Exprimé sous la forme j | i} $. ** De plus ici, on suppose que $ x_j $ est sélectionné de manière probabiliste sur la base d'une ** distribution normale centrée sur $ x_ {i} $ **.

Alors $ p_ {j | i} $ peut être exprimé par la formule suivante.


p_{j|i} = \frac{\exp(-||x_{i} - x_{j}||^2/2\sigma_{i}^2)}{\sum_{k\neq i}\exp(-||x_{i} - x_{k}||^2/2\sigma_{i}^2)}

Ce qui précède est obtenu à partir de la fonction de densité de probabilité de la distribution normale. $ \ Frac {1} {\ sqrt {2πσ ^ 2}} $ est une constante et est annulée par le dénominateur.


\frac{1}{\sqrt{2πσ^2}}\exp{(-(x-μ)^2/2σ^2)}

Nous supposons une distribution normale avec une moyenne $ x_ {i} $ et une variance $ \ sigma_ {i} ^ 2 $, mais la valeur de la variance $ \ sigma_ {i} ^ 2 $ sera ajustée par les paramètres décrits ci-dessous. .. Puisque la distribution $ \ sigma_ {i} ^ 2 $ change le type de distribution supposé, la sortie après la réduction de dimension finale changera également de manière significative.

Aussi, puisque cette fois le but est d'exprimer la distance entre différentes données avec une probabilité conditionnelle, nous la placerons comme suit.


p_{i|i} = 0

2. La distance entre les points de données après réduction de dimension est également exprimée par la probabilité conditionnelle.

La similitude entre les points de données à dimension réduite $ y_ {i} $ et $ y_ {j} $ est également exprimée en ** probabilité conditionnelle $ q_ {j | i} $ comme précédemment. ** Supposons également que $ y_j $ soit sélectionné de manière probabiliste sur la base d'une distribution normale centrée sur $ y_ {i} $, mais contrairement à avant ** la variance est $ \ frac {1} { Corrigé avec \ sqrt {2}} $ **. En le fixant, vous pouvez annuler la dispersion de la formule précédente et la simplifier.

$ q_ {j | i} $ peut être exprimé par la formule suivante.


q_{j|i} = \frac{\exp(-||y_{i} - y_{j}||^2)}{\sum_{k\neq i}\exp(-||y_{i} - y_{k}||^2)}

Placez-le comme suit comme avant.


q_{i|i} = 0

3. Conception de la fonction de perte avec divergence KL

Étant donné que la relation de distance entre les points de données dans la dimension supérieure et la relation de distance dans la dimension inférieure après la réduction de dimension doit correspondre autant que possible,p_{i|j} = q_{i|j}Je vise à être. Cette foisp_{i|j}Quandq_{i|j}の距離を測る指標QuandしてKLダイバージェンス(Pas une définition stricte de la distance)を使用します。KLダイバージェンスQuand損失関数Quandしてその最小化を目指します。

La fonction de perte $ C $ cette fois est exprimée par la formule suivante.


C = \sum_{i}KL(P_{i}||Q_{i}) = \sum_{i} \sum_{j} p_{j|i}\log\frac{p_{j|i}}{q_{j|i}}

$ P_ {i} $ représente toutes les probabilités conditionnelles données $ x_ {i} $, $ Q_ {i} $ représente toutes les conditions données $ y_ {i} $ Représente une probabilité.

iciLa divergence KL est un indicateur asymétriqueAlorsKL(P_{i}||Q_{i}) \neq KL(Q_{i}||P_{i})Le but est d'être. grosp_{j|i}Petitq_{j|i}Si vous modélisez avec, la fonction de perte sera grande, petitp_{j|i}Le grandq_{j|i}Lors de la modélisation avec, la fonction de perte ne devient pas si grande. c'est**Si la position du point de données après la réduction de dimension est placée loin lors de l'expression d'un point de données proche sur une dimension plus élevée, la fonction de perte devient très grande.**Cela signifie que. C'est pourquoi SNE est censé se concentrer sur la préservation de la structure locale des données.

4.Perplexity Il y avait $ \ sigma_ {i} ^ 2 $ comme paramètre restant. Il s'agit de la distribution d'une distribution normale centrée sur le point de données de grande dimension $ x_ {i} $. C'est un paramètre très important car le type de distribution supposé dépend de la distribution $ \ sigma_ {i} ^ 2 $.

Si les données sont denses, il convient de supposer $ \ sigma_ {i} ^ 2 $ small, et si les données sont rares, il convient de supposer $ \ sigma_ {i} ^ 2 $ large. Un paramètre appelé Perplexité est utilisé pour savoir comment assumer les données.

Le SNE coupe $ \ sigma_ {i} ^ 2 $ qui générera $ P_ {i} $ avec une Perplexité fixe spécifiée par son utilisateur. La perplexité est définie comme suit.


Perp(P_{i}) = 2^{H(P_{i})}

De plus, $ H (P_ {i}) $ est l'entropie de $ P_ {i} $ et est défini comme suit.


H(P_{i}) = -\sum_{j}p_{j|i}\log_{2}p_{j|i}

Par exemple, corrigez Perplexité avec une valeur telle que $ 40 $ et recherchez $ \ sigma_ {i} ^ 2 $ qui correspond à l'équation. Si la Perplexité est grande, $ \ sigma_ {i} ^ 2 $ sera naturellement grande, et on suppose que les données sont clairsemées. De plus, si la Perplexité est petite, $ \ sigma_ {i} ^ 2 $ l'est également, en supposant que les données sont denses.

La perplexité peut également être reformulée comme ** le nombre qui détermine combien de voisins sont considérés à partir du point de données $ x_ {i} $ **.

5. Minimisez la fonction de perte avec la méthode de descente de gradient probabiliste

Minimisez la fonction de perte en utilisant la méthode de descente de gradient probabiliste. Le gradient utilise ce qui suit, qui est la valeur obtenue en différenciant la fonction de perte par $ y_ {i} $.


\frac{\delta C}{\delta y_{i}} = 2\sum_{j}(p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})(y_{i}-y_{j})

Nous déplacerons progressivement $ y_ {i} $ en utilisant ce dégradé, et la formule de mise à jour est la suivante.


Y^{(t)} = Y^{(t-1)} + \eta \frac{\delta C}{\delta Y} + \alpha(t)(Y^{(t-1)} - Y^{(t-2)})

Est une image de déplacement $ Y ^ {(t-1)} $ du taux d'apprentissage $ \ eta $ uniquement dans le sens du gradient $ \ frac {\ delta C} {\ delta Y} . ( T $ représente le nombre d'itérations.) Finalement, il y a un $ \ alpha (t) (Y ^ {(t-1)} --Y ^ {(t-2)}) $ appelé terme de moment, qui est un peu d'optimisation du gradient. Il y a un sens à changer. L'optimisation est contrôlée de manière à ne pas tomber dans la valeur minimale locale et à rester dans la valeur minimale autant que possible.

C'est le flux de SNE.

Problèmes avec SNE

Ce qui précède est le flux de SNE, mais SNE a les deux problèmes suivants.

Parce que la fonction de perte utilise la divergence KLp_{j|i}Quandq_{j|i}Ne peut pas être manipuléFormule de fonction de perte compliquéeFaire.((p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j})Partie de)

Problème d'encombrement Lorsqu'un objet multidimensionnel est déposé dans une dimension inférieure, le nombre de points de données qui peuvent être équidistants les uns des autres diminue, donc ** lorsque la dimension est supprimée, il devient encombré pour tenter de maintenir l'équidistance **. C'est un problème.

Par exemple, dans le cas de 3 dimensions, 4 points de données avec le nombre de dimensions + 1 peuvent exister à égale distance les uns des autres, mais lorsqu'ils sont déposés en 2 dimensions, seuls 3 points de données avec le nombre de dimensions + 1 peuvent exister à des distances égales. Il y a une possibilité d'écraser l'espace qui aurait dû se produire lorsque le nombre de dimensions est réduit. C'est le problème du surpeuplement.

T-SNE a essayé de résoudre ces problèmes.

Comment fonctionne t-SNE

Afin de résoudre les problèmes de SNE, les fonctionnalités suivantes ont été ajoutées à t-SNE.

--Synchroniser la fonction de perte

Symétrie de la fonction de perte

La proximité du point $ x_ {i} $ et du point $ x_ {j} $ est exprimée par la distribution de probabilité simultanée $ p_ {ij} $ comme traitement de symétrie de la fonction de perte. (Notez que la symétrie est une probabilité simultanée plutôt qu'une probabilité conditionnelle)


p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}


p_{j|i} = \frac{\exp(-||x_{i} - x_{j}||^2/2\sigma_{i}^2)}{\sum_{k\neq i}\exp(-||x_{i} - x_{k}||^2/2\sigma_{i}^2)}

p_{j|i}Il n'y a pas de changement, mais un traitement qui prend une moyennep_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}Il est symétrique avec.

En supposant la distribution t des élèves

De plus, la proximité du point $ y_ {i} $ et du point $ y_ {j} $ sur la dimension inférieure est exprimée par la distribution de probabilité simultanée $ q_ {ij} $ comme suit.


q_{ij} = \frac{(1+||y_{i} - y_{j}||^2)^{-1}}{\sum_{k\neq i}(1+||y_{i} - y_{j}||^2)^{-1}}

Ici, en considérant la distance des points sur la dimension inférieure, nous supposons une distribution de Student t avec un degré de liberté de $ 1 $. ** La distribution t est caractérisée par une base plus élevée que la distribution normale **. En utilisant une distribution de base t élevée, les points de données à moyenne portée peuvent être modélisés comme des points de données à moyenne portée dans un espace de grande dimension et des distances plus longues dans un espace de faible dimension, et ** les problèmes d'encombrement peuvent être évités pour les points de données à moyenne portée. Je peux le faire. ** **

download.png

Minimiser la fonction de perte

t-SNE utilise ces $ p_ {ij} $ et $ q_ {ij} $ pour minimiser la fonction de perte. La fonction de perte est exprimée comme suit.


C = \sum_{i}KL(P ||Q) = \sum_{i} \sum_{j} p_{ji}\log\frac{p_{ji}}{q_{ji}}

Ceci est également optimisé en utilisant la méthode de descente de gradient stochastique comme dans SNE.


\frac{\delta C}{\delta y_{i}} = 4\sum_{j}(p_{ji}-q_{ji})(y_{i}-y_{j})(1+||y_{i} - y_{j}||^2)^{-1}

La formule de mise à jour est la même que SNE.

Exemple de visualisation de t-SNE

Cette fois, j'aimerais visualiser la situation de distribution à l'aide de données textuelles. Les données textuelles ont tendance à être de grande dimension lorsqu'elles sont vectorisées, de sorte que l'algorithme de réduction de dimension est très efficace.

Bibliothèque utilisée

scikit-learn 0.21.3

base de données

Cette fois, je pense que le jeu de données sera utilisé pour visualiser l'état de la distribution des données à l'aide du "corpus de news liveoor". Pour plus de détails sur l'ensemble de données et la méthode d'analyse morphologique, veuillez consulter Publié dans l'article précédemment publié. Je vais.

Dans le cas du japonais, un prétraitement qui décompose les phrases en éléments morphologiques est nécessaire à l'avance, donc après avoir décomposé toutes les phrases en éléments morphologiques, elles sont déposées dans la trame de données suivante.

スクリーンショット 2020-01-13 21.07.38.png

Visualisation de la distribution des données

Après avoir vectorisé les données textuelles avec TF-IDF, elles sont réduites à deux dimensions en utilisant t-SNE.

import pickle
import matplotlib.pyplot as plt
from sklearn.feature_extraction.text import TfidfVectorizer
import pandas as pd

#On suppose que la trame de données après décomposition morphologique a déjà été décapée.
with open('df_wakati.pickle', 'rb') as f:
    df = pickle.load(f)

#tf-Vectorisation utilisant idf
vectorizer = TfidfVectorizer()
X = vectorizer.fit_transform(df[3])

#t-Réduction de dimension avec SNE
from sklearn.manifold import TSNE
tsne = TSNE(n_components=2, random_state = 0, perplexity = 30, n_iter = 1000)
X_embedded = tsne.fit_transform(X)

ddf = pd.concat([df, pd.DataFrame(X_embedded, columns = ['col1', 'col2'])], axis = 1)

article_list = ddf[1].unique()

colors =  ["r", "g", "b", "c", "m", "y", "k", "orange","pink"]
plt.figure(figsize = (30, 30))
for i , v in enumerate(article_list):
    tmp_df = ddf[ddf[1] == v]
    plt.scatter(tmp_df['col1'],  
                tmp_df['col2'],
                label = v,
                color = colors[i])
    
plt.legend(fontsize = 30)

Le résultat est là. Il est possible de visualiser l'existence de clusters pour chaque support d'article.

download2.png

Next Je pense que ce serait bien de résumer d'autres algorithmes de réduction de dimension. Merci d'avoir lu jusqu'au bout.

Recommended Posts

Comprendre t-SNE et améliorer la visualisation
[Remarque] PCA et t-SNE
Comprendre le DataSet et le DataLoader de PyTorch (2)
Comprendre le DataSet et le DataLoader de PyTorch (1)
Apprenez à connaître les packages et les modules Python
Visualisation interactive avec ipywidgets et Bokeh
[Python / matplotlib] Comprendre et utiliser FuncAnimation
Clustering et visualisation à l'aide de Python et CytoScape
Comprendre les rouages et les extensions dans discord.py
Comprendre les règles et les fonctions convexes d'Armijo
Agrégation et visualisation des nombres accumulés