#はじめに
今回は次元削減のアルゴリズムt-SNE(t-Distributed Stochastic Neighbor Embedding)についてまとめました。t-SNEは高次元データを2次元又は3次元に変換して可視化するための次元削減アルゴリズムで、ディープラーニングの父とも呼ばれるヒントン教授が開発しました。今回はこのt-SNEを理解して可視化力を高めていきます。

##参考
t-SNEを理解するに当たって下記を参考にさせていただきました。

#t-SNEの概要
##t-SNEの源流
t-SNEは高次元データを2次元や3次元に落とし込むための次元削減アルゴリズムです。
次元削減といえば古典的なものとしてPCAやMDSがありますが、それら線形的な次元削減にはいくつかの問題点がありました。

異なるデータを低次元上でも遠くに保つことに焦点を当てたアルゴリズムのため、類似しているデータを低次元上でも近くに保つことには弱い
特に高次元上の非線形的なデータに対しては「類似しているデータを低次元上でも近くに保つこと」は不可能に近い

これらの問題点を解決するためにデータの局所的な構造(類似しているデータを低次元上でも近くに保つこと)の維持を目的とした非線形次元削減技術が色々と生み出されました。t-SNEはその流れを汲んだアルゴリズムになります。

下記が非線形的なデータのイメージです。

※こちらのサイトより引用

##t-SNEの特徴
t-SNEのポイントを記載しています。具体的な処理の中身やメリットデメリットの理由は後述のアルゴリズムの説明のところで詳細に記載したいと思います。

処理のポイント

高次元での距離分布が低次元での距離分布にもできるだけ合致するように変換する
距離の分布をスチューデンのt-分布に従うと仮定(SNEではガウス分布を仮定していたが、そこから改良された)

メリット

高次元の局所的な構造を非常によく捉える
大局的な構造も可能な限り捉える

デメリット

Perplexity(内部のパラメータ)を変えると全くことなるクラスターが出現してしまう

#t-SNEのアルゴリズム
t-SNEのアルゴリズムを理解するに当たって、まずその前身となるSNEのアルゴリズムについて理解するところから始めます。その後SNEの問題点について整理し、問題点を解消するものして生み出されたt-SNEついてまとめます。

##SNEの仕組み
###1.データポイント間の距離を条件付き確率に変換
SNEはデータポイント間の距離を条件付き確率に変換するところからスタートします。
データポイント$x_{i}$ と$x_{j}$の類似度を、$x_{i}$が与えられた時に近傍として$x_{j}$を選択する条件付き確率$p_{j|i}$として表現します。さらにここでは、$x_j$は$x_{i}$を中心とした正規分布に基づいて、確率的に選択されると仮定しています。

すると$p_{j|i}$は下記の数式で表現できます。


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)}

上記は正規分布の確率密度関数から求められたものです。$\frac{1}{\sqrt{2πσ^2}}$は定数のため分母分子で打ち消されています。


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

平均$x_{i}$、分散$\sigma_{i}^2$の正規分布を仮定している訳ですが、分散$\sigma_{i}^2$の値は後述のパラメータによって調整します。分散$\sigma_{i}^2$によってどういう分布を仮定するかが変わってくるため、最終的な次元削減後のアウトプットも大きく変わります。

また今回は異なるデータ間の距離を条件付き確率で表すことを目的としているため、下記のように置きます。


p_{i|i} = 0

###2.次元削減後のデータポイント間の距離も条件付き確率で表現

次元削減後のデータポイント$y_{i}$ と$y_{j}$の類似度も先ほどと同様に条件付き確率$q_{j|i}$として表現します。また同様に$y_j$は$y_{i}$を中心とした正規分布に基づいて確率的に選択されると仮定しますが、先ほどと異なり分散は$\frac{1}{\sqrt{2}}$で固定します。固定することで先ほどの式から分散を打ち消してシンプルにすることができます。

$q_{j|i}$は下記の数式で表現することができます。


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

先ほどと同様に下記のように置きます。


q_{i|i} = 0

###3.KLダイバージェンスで損失関数設計
高次元でのデータポイント間の距離関係と次元削減後の低次元での距離関係ができるだけ一致すればよいので、$p_{i|j} = q_{i|j}$となることを目指します。今回は$p_{i|j}$と$q_{i|j}$の距離を測る指標としてKLダイバージェンス(厳密な定義での距離ではない)を使用します。KLダイバージェンスと損失関数としてその最小化を目指します。

今回の損失関数$C$は下記数式で表されます。


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}$は$x_{i}$が与えられた時の全ての条件付き確率を表し、$Q_{i}$は$y_{i}$が与えられた時の全ての条件付き確率を表します。

ここでKLダイバージェンスは非対称な指標なので$KL(P_{i}||Q_{i}) \neq KL(Q_{i}||P_{i})$となることがポイントです。大きな$p_{j|i}$を小さな$q_{j|i}$でモデル化する場合は損失関数は大きくなりますが、
小さな$p_{j|i}$を大きな$q_{j|i}$でモデル化する場合はそこまで損失関数は大きくなりません。これは高次元上で近くにあるデータポイントを表現するに当たって次元削減後のデータポイントの位置を遠くに配置してしまうと、非常に損失関数が大きくなるということを意味します。
これがSNEがデータの局所構造を保持すること焦点を当てていると言われる所以です。

###4.Perplexity
残っているパラメータとして$\sigma_{i}^2$がありました。これは高次元のデータポイント$x_{i}$を中心とした正規分布の分散です。分散$\sigma_{i}^2$によってどういう分布を仮定するかが変わってくるため非常に重要なパラメータです。

データが密であれば$\sigma_{i}^2$を小さく仮定するのが適切だし、疎では$\sigma_{i}^2$を大きく仮定するのが適切です。データをどのように仮定するのか、というところでPerplexityというパラメータが用いられます。

SNEはその使用者が指定した固定のPerplexityを持つ$P_{i}$を生成するような$\sigma_{i}^2$を二分探索します。Perplexityは下記のように定義されています。


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

また、$H(P_{i})$は$P_{i}$のエントロピーで下記のように定義されています。


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

例えばPerplexityを$40$といった値で固定して等式に合致するような$\sigma_{i}^2$を探索します。
Perplexityが大きければ当然$\sigma_{i}^2$も大きくなり、データが疎であることを仮定することになります。また、Perplexityが小さければ$\sigma_{i}^2$も小さくなり、データが密であることを仮定します。

Perplexityはデータポイント$x_{i}$からどの程度の数の近傍点を考慮するか決める数であると言い換えることもできます。

###5.確率的勾配降下法で損失関数を最小化する
確率的勾配降下法を使用して損失関数を最小化していきます。その勾配は損失関数を$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})

この勾配を用いて$y_{i}$を徐々に動かしていくのですが、その更新式は下記のようになっています。


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

を$Y^{(t-1)}$を勾配$\frac{\delta C}{\delta Y}$の方向だけ学習率$\eta$の分だけ動かすといったイメージです。($t$は反復回数を表す。)
最後にモメンタム項と呼ばれる$\alpha(t)(Y^{(t-1)} - Y^{(t-2)})$がついているのですが、これは勾配にを最適化から少しずらす意味合いがあります。局所的な極小値にはまらないようにできるだけ全体の中での極小値におさまるように最適化をコントールしています。

これがSNEの流れになります。

##SNEの問題点
上記がSNEの流れになりますが、SNEには下記2点の問題があります。

損失関数の最小化が難しい
Crowding問題

損失関数はKLダイバージェンスを使用しているため、$p_{j|i}$と$q_{j|i}$を対象に扱えず損失関数の式が複雑化しています。(($p_{j|i}-q_{j|i}+p_{i|j}-q_{i|j}$)の部分)

Crowding問題多次元のものを低次元に落とし込んだ時に、お互いに等距離であれるデータポイントの数が減少するため、次元を落とす時に等距離性を保とうとして混雑化してしまうという問題です。

例えば3次元であれば次元数＋1の4つのデータポイントが互いに等距離で存在できますが、2次元に落とすと次元数＋1の3つしか等距離であれません。次元数を落とした時に本来発生するはずの隙間を潰してしまう可能性があります。それがCrowding問題です。

これらの解決を試みたのがt-SNEです。

##t-SNEの仕組み
SNEの問題点を解決するため、t-SNEでは下記のような特徴が加えられています。

損失関数を対称化
低次元のデータポイント間の距離を考えるに当たってスチューデントのt分布を仮定

###損失関数の対称化
損失関数の対称化処理として点$x_{i}$と点$x_{j}$の近さを同時確率分布$p_{ij}$で表します。(対称化するにあたって条件付き確率ではなく同時確率になっていることに注意)


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}$に変化はないですが、平均を取るような処理$p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}$で対称化しています。

###スチューデントのt分布を仮定
また低次元上の点$y_{i}$と点$y_{j}$の近さを同時確率分布$q_{ij}$で以下のように表します。


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

ここで低次元上の点の距離を考えるに当たって自由度$1$のスチューデントのt分布を仮定しています。t分布は正規分布に比べて裾野が高いのが特徴です。裾野が高いt分布を使用することで高次元空間では中距離のデータポイントを、低次元空間ではより長い距離としてモデル化することができ、中距離のデータポイントについてCrowding問題を避けることができます。

###損失関数の最小化
t-SNEはこの$p_{ij}$と$q_{ij}$を使って損失関数を最小化します。損失関数は下記のように表されます。


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

こちらも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}

更新式についてはSNEと同様です。

#t-SNEの可視化例
今回はテキストデータを用いてその分布状況を可視化したいと思います。テキストデータはベクトル化すると高次元になりがちなので次元削減アルゴリズムが非常に有効です。

##使用したライブラリ
scikit-learn 0.21.3
##データセット
今回データセットは「livedoor ニュースコーパス」を使用してそのデータ分布状況を可視化使用と思います。データセットの詳細やその形態素解析の方法は以前投稿した記事で投稿しているの気になる方そちらをご参照いただければと思います。

日本語の場合は事前に文章を形態素単位に分解する前処理が必要となるため、全ての文章を形態素に分解した後下記のようなデータフレームに落とし込んでいます。

##データ分布状況の可視化
テキストデータを一旦TF-IDFでベクトル化した後、t-SNEを使用して2次元に次元削減しています。

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

#形態素分解した後のデータフレームはすでにpickle化して持っている状態を想定
with open('df_wakati.pickle', 'rb') as f:
    df = pickle.load(f)

#tf-idfを用いてベクトル化
vectorizer = TfidfVectorizer()
X = vectorizer.fit_transform(df[3])

#t-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)

結果はこちらです。記事の媒体毎にクラスターが存在していることが可視化できています。

#Next
その他の次元削減アルゴリズムについてもまとめられたいいなと思っています。最後まで読んでいただきありがとうございました。