t-SNEシミュレータ

## はじめに
非常に強力だが、計算が遅く未知の入力に対して役立たずな次元圧縮のアルゴリズムであるt-SNEをカーネル法でシミュレートして弱点を克服する。

## t-SNE
t-SNEは次元圧縮のアルゴリズムです。次元圧縮というのは高次元（10次元とか1000次元とか、あるいはそれ以上）のデータから必要な情報だけを抜き出してより低次元な空間に写像することを言います。普通は人間が目視確認しやすいように2次元とか3次元の空間に写像します。

ざっくり解説すると、次元圧縮に際していつもはデータ入力をベクトルとみなしてノルムを比較したりそれはまぁ涙ぐましい様々な操作を施すことがいろいろなアルゴリズムの基本となっているのですが、t-SNEではデータ入力を確率分布とみなし、確率分布が近いものどうしが近くに来るように写像します。

案の定、t-SNEについては素晴らしい記事がたくさん存在しているので詳しい解説はそちらにお任せいたします（[参考1](https://blog.albert2005.co.jp/2015/12/02/tsne/),[参考2](https://deepage.net/machine_learning/2017/03/08/tsne.html),[参考3](https://qiita.com/stfate/items/8988d01aad9596f9d586)）。百聞は一見にしかずなのでとりあえずt-SNEがどうスゴいのかを見てみましょう。

今回用いるデータセットはsklearnに付属しているDigitsという手書き文字認識用のデータセットです。Digitsは$8 \times 8$の大きさを持つ数字の画像に、対応する0〜9までのラベルが割り振ってあります。今回はこの$8\times 8 = 64$次元のデータを$2$次元に圧縮して可視化します。

これから用いるいろいろなライブラリをインポートしつつDigitsデータセットを読み込んでみましょう。

```py3
# 必要なライブラリのインポート
%matplotlib inline
## 行列演算やグラフ描画
import numpy as np
from matplotlib import pyplot as plt
import seaborn as sns
## 次元圧縮のアルゴリズム
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis as LDA
from sklearn.manifold import TSNE
## データセットとデータの操作
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_digits

# Digits データセットのロード
digits = load_digits(n_class=10)

# 入力Xと出力Yの抜き出し
X = digits['data']
Y = digits['target']

# 教師データとテストデータを分割
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.33, random_state=42)
```

あと今後使うので、いい感じに結果をプロットしてくれる関数を定義しておきます。

```py3
def number_plot(X, Y, shade=None):
    markers = ["$0$", "$1$", "$2$", "$3$", "$4$", "$5$", "$6$", "$7$", "$8$", "$9$"]
    plt.figure(figsize=(10,10))
    if shade is not None:
        plt.scatter(shade[:, 0], shade[:, 1])
    for i in range(10):
        X_paint = X[Y == i]
        plt.scatter(X_paint[:, 0], X_paint[:, 1], marker=markers[i])
    plt.show()
```

まずは「データ入力をベクトルとみなしてノルムを比較したりそれはまぁ涙ぐましい様々な操作を施す」アルゴリズムの代表格である線形判別分析（LDA:Linear Discriminant Analysis）を使って次元圧縮をしてみたらどうなるかを見てみます。LDAは同じグループどうしをなるべく近くに、異なるグループどうしをなるべく遠くに配置するような線形写像を行う教師ありの写像です。ぶっちゃけ、これで0〜9までの手書き文字がうまい具合にばらけてくれればt-SNEとかでぃーぷらーにんぐとか難しいことをしなくていいわけです。

```py3
# 線形判別分析で2次元に圧縮
lda = LDA(n_components=2)
X_lda = lda.fit_transform(X_train, Y_train)

# 次元圧縮の結果を描画
number_plot(X_lda, Y_train)
```

![lda_qiita.png](https://qiita-image-store.s3.amazonaws.com/0/47653/3a6a3ba1-51cc-cb02-ed95-6412d86cf6cb.png)

ありゃ。けっこういい感じ……？ 0,2,3,4,6あたりは割と綺麗に分離してますが、1,7,8と5,9という似通った形状の数字がごちゃまぜになっているので次元圧縮は失敗したというべきでしょう。

ではt-SNEを用いてみます。

```py3
# t-SNEで2次元に圧縮
tsne = TSNE(n_components=2)
X_tsne = tsne.fit_transform(X_train)

# 次元圧縮の結果を表示
number_plot(X_tsne, Y_train)
```

![tsne_qiita.png](https://qiita-image-store.s3.amazonaws.com/0/47653/2e1e7017-20be-3248-db36-227ff369cdfa.png)


うおっ。ヤベェ。ほぼ完璧に各数字が分離しています。

これほどの結果を教師なしで出してしまうt-SNE、最強のアルゴリズムに思えますが実は以下のような欠点があります。

* 計算が遅い
    * 解析的に解けないため非常に時間がかかります。
* 新しい入力に対して無力
    * 新しく手書き文字をもう1枚用意してそれを写像して、と言ってもt-SNEにはできません。新しい手書き文字を加えたすべてのデータに対してもう一度計算をかけ直す必要があります。また、その場合は一般に実行結果が毎回変わってしまいます。

つまり新しいデータがポンポンと何度も入ってきて、それを毎回写像せねばならないような問題に対してt-SNEを用いることはできません。t-SNEは入力の個数が有限ですべて既知である場合にのみ効果を発揮します。

## t-SNEシミュレータ
とは言うものの、この強力なアルゴリズムは捨てがたいものです。そう簡単には諦められません。そこでたとえばt-SNEの結果をうまく再現するような非線形写像を作ってしまえばどうでしょう。

私たちには任意の非線形写像を近似するためのカーネル法という武器があります。教科書通りの素直な近似を行うので、以下のコードで何をしているか分からない人は[以前の投稿](https://qiita.com/wsuzume/items/09a59036c8944fd563ff)をご覧くらださい。

```py3
from itertools import combinations_with_replacement

# ガウスカーネル用のハイパーパラメータ
beta = 1e-3

# グラム行列を計算
n_samples, n_features = X_train.shape
K = np.zeros((n_samples, n_samples))
for i, j in combinations_with_replacement(range(n_samples), 2):
    K[i][j] = np.exp(- beta * np.sum((X_train[j] - X_train[i])**2))
    K[j][i] = K[i][j]

# 重みBを求めて近似
lam = 1e-6
B = np.linalg.inv(K + lam * np.eye(n_samples)).dot(X_tsne)
X_emurated = K.dot(B)

# 近似した結果を表示
number_plot(X_emurated, Y_train)
```

![emurated_qiita.png](https://qiita-image-store.s3.amazonaws.com/0/47653/76f36ebb-5eac-264c-ddc5-b0423e3e005e.png)

ふっふっふ。上のt-SNEの結果とほとんど見分けがつきません。そう言ってほんとはt-SNEの結果を貼り付けてごまかしているだけじゃないのか？過学習してるんじゃないのか？という疑念を振り払うためにテスト用のデータをあらかじめ分けておいたわけです。この写像をテストデータに施してみましょう。

```py3
# テストデータをガウスカーネルによるヒルベルト空間に写像
n_tests, n_test_features = X_test.shape
K_predict = np.zeros((n_tests, n_samples))
for i in range(n_tests):
    for j in range(n_samples):
        K_predict[i][j] = np.exp(- beta * np.sum((X_train[j] - X_test[i])**2))

# さらに求めた重みで線形写像
X_predict = K_predict.dot(B)

# 近似した結果を表示
number_plot(X_predict, Y_test)
```
![predict_qiita.png](https://qiita-image-store.s3.amazonaws.com/0/47653/ef6b5deb-4f7b-9fa8-9260-ee88cc6858ff.png)

若干バラけてますがテストデータに対してもうまく写像できており、過学習はしていないことがわかります。ちなみに教師データを影として表示すると次の図のようになります。

```py3
number_plot(X_predict, Y_test, X_tsne)
```

![shaded_qiita.png](https://qiita-image-store.s3.amazonaws.com/0/47653/24ebd09d-e1c1-1343-6e73-f8443e159064.png)

ハイパーパラメータを適当に設定してこんな感じなのでうまくチューニングすればもっといい感じになるかもしれませんが、今回はこれくらいで十分でしょう。

## まとめ
t-SNEの結果を再現するような非線形写像を求めてやることで、未知の入力に対しても使える次元圧縮を得ることができました。ニューラルネットとかカーネル法のような万能の近似アルゴリズムを使って、既存の低速だけど強力なアルゴリズムのシミュレータを作ってしまうのはけっこうありかもしれません。