資料降維與視覺化：t-SNE 理論與應用

一般來說，將資料視覺化或降維的方法第一個會想到的是經典的 PCA，但其實近年來的論文常常是以 t-SNE 這個方法做降維視覺化，效果相比其他方法好非常多，那就廢話不多說開始介紹吧！

一、t-SNE 簡介

t-SNE（t-distributed stochastic neighbor embedding，t-隨機鄰近嵌入法）是一種非線性的機器學習降維方法，由 Laurens van der Maaten 和 Geoffrey Hinton 於 2008 年提出，由於 t-SNE 降維時保持局部結構的能力十分傑出，因此成為近年來學術論文與模型比賽中資料視覺化的常客。

t-SNE 演算法有以下幾個特色：

應用上，t-SNE 常用來將資料投影到 2 維或 3 維的空間作定性的視覺化觀察，通過視覺化直觀的驗證某資料集或演算法的有效性。
SNE 使用條件機率和高斯分佈來定義高維和低維中樣本點之間的相似度，用 KL 散度來衡量兩條件機率分佈總和之間的相似度，並將其作為價值函數以梯度下降法求解。
t-SNE 使用 t 分佈定義低維時的機率分佈來減緩維數災難（curse of dimensionality）造成的擁擠問題（crowding problem）。
由於 t-SNE 的演算法優化是基於機率的方法，在判讀圖像時有許多要注意的地方。

圖：Visualizations of 6,000 handwritten digits from the MNIST dataset

二、SNE 演算法

以下簡單介紹 SNE 演算法步驟：

1. 將高維中樣本點之間的歐式距離（Euclidean distances）轉換為表示相似度的條件機率 $p_{j|i}$（當高斯分佈中心為 $x_i$ 時，$x_i$ 挑選 $x_j$ 為鄰居的機率）：
$$
{p_ {j \mid i} = \frac{\exp(- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i ))} {\sum_{k \neq i} \exp(- \mid \mid x_i - x_k \mid \mid ^2 / (2 \sigma^2_i))}}
$$
其中 $\sigma_i$ 為以 $x_i$ 為中心之高斯分佈的變異數，且 $p_{x∣x}=0$。

2. 同理，目標低維度一樣建構一個高斯分佈的條件機率 $q_{j|i}$（$x_i$ 和 $x_j$ 對應到 $y_i$ 和 $y_j$，方便計算標準差設為 $\frac{1}{\sqrt{2}}$）：
$$
{q_ {j \mid i} = \frac{\exp(- \mid \mid y_i -y_j \mid \mid ^2)} {\sum_{k \neq i} \exp(- \mid \mid y_i - y_k \mid \mid ^2)}}
$$
同理，其中 $q_{x∣x}=0$。

3. 在歐式距離轉條件機率建構高斯分佈時，需要選擇每一個 $x_i$ 對應的 $\sigma_i$，由於資料點的密度通常不平均，SNE 以二分搜尋法找尋 $P_i$ ，該 $P_i$ 要符合使用者預先設定的困惑度（Perplexity）：
$$
Perp(P_i) = 2^{H(P_i)}
$$
其中 $H(P_i)$ 是 $P_i$ 以 bit 度量的夏農熵（Shannon entropy）：
$$
H(P_i) = -\sum_j p_{j \mid i} \log_2 p_{j \mid i}
$$
一般將困惑度設為 5 至 50，可以將其視為平滑過後的有效鄰居數。

4. 我們的目標是在高維和低維中的條件機率分佈盡可能的相似 $p_{j∣i} \sim q_{j∣i}$ ，因此 SNE 要最佳化所有樣本點間的 KL 散度總和：
$$
C = \sum_i KL(P_i \mid \mid Q_i) = \sum_i \sum_j p_{j \mid i} \log \frac{p_{j \mid i}}{q_{j \mid i}}
$$

5. 以上式作為價值函數（Cost function），可以利用隨機梯度下降法（Stochastic gradient descent, SGD）求解：
$$
\frac{\delta C}{\delta y_i} = 2 \sum_j (p_{j \mid i} - q_{j \mid i} + p_{i \mid j} - q_{i \mid j})(y_i - y_j)
$$
KL 散度（Kullback–Leibler divergence, KLD）為兩個機率分布差別的非對稱性度量，當作 SNE 的價值函數時有保留局部特徵的特性，即在高維中近的兩樣本在低維中也要近（算出來的 cost 數值較大），但在高維中遠的樣本並不一定也要特別遠（算出來的 cost 數值較小）。

6. 為了避免陷入局部最佳解和加速最佳化過程，使用梯度下降法加入一個會衰減的動量項：
$$
\Upsilon^{(t)} = \Upsilon^{(t-1)} + \eta \frac{\delta C}{\delta \Upsilon} + \alpha(t)(\Upsilon^{(t-1)} - \Upsilon^{(t-2)})
$$
其中 $\Upsilon^{(t)}$ 為第 $t$ 次迭代時的解，$\eta$ 為學習率，$\alpha(t)$ 為第 $t$ 次迭代時的動量。

三、t-SNE 與擁擠問題

由於維數災難（curse of dimensionality）高維資料中的距離關係不能完整在低維空間中保留（詳見補記 2：維數災難），各個分群會有聚集在一起無法區分的擁擠問題（crowding problem），面對擁擠問題，t-SNE 做了兩項改進來達到更好的降維效果：

1. 使用 Symmetric SNE

將映射方式改成聯合概率分佈以簡化梯度公式，實驗表明 Symmetric SNE 和 SNE 有一樣好的結果。因此公式變為：
$$
{\displaystyle p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}},}
$$
$$
{\displaystyle p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}}
$$
優化時的梯度計算：
$$
\frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij} - q_{ij})(y_i - y_j)
$$

2. 低維空間時改用 t 分佈

為了解決擁擠問題，在 t-SNE 中低維空間改用 t 分佈而非原本的高斯分佈，以 t 分佈表達的好處是 t 分佈較高斯分佈偏重長尾，使得高維度下中近的距離的樣本點在映射後能夠有一個較大的距離，且 t 分佈受異常值影響更小，在樣本數較少時仍可以模擬分佈情形而不受雜訊影響。因此使用 t 分布時聯合機率分佈 $q_{ij}$ 公式變為：
$$
q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k\neq l}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}
$$
優化時的梯度計算：
$$
\frac{\delta C}{\delta y_i} = 4 \sum_j(p_{ij}-q_{ij})(y_i-y_j)(1+ \mid \mid y_i-y_j \mid \mid ^2)^{-1}
$$
下面是不同演算法的梯度比較圖，可以看到 t-SNE 相比其他方法有更好的梯度，對於不相似的點，用一個較小的距離會產生較大的梯度來讓點排斥開來，且該排斥不會太大，避免不相似點距離過遠。

圖：Gradients of three types of SNE

四、Barnes-Hut t-SNE：效率優化

Barnes-Hut t-SNE 是最流行的 t-SNE 方法，主要最佳化 t-SNE 的速度，Barnes-Hut t-SNE 有以下特點：

效率提升，Barnes-Hut approximation 使複雜度從 $O(n^2)$ 下降至 $O(nlogn)$，讓 t-SNE 可以處理 10 萬級規模的資料。
使用角度（angle）參數對近似結果進行控制。
僅在目標維度為 2 或 3 時有效，著重於資料視覺化。
稀疏矩陣只能用特定的方法嵌入或者用投影近似。

實務上建議使用 Barnes-Hut t-SNE，其詳細優化步驟可以查看論文 Accelerating t-SNE using Tree-Based Algorithms。

圖：Barnes-Hut optimization highlighted as points converge to their t-SNE positions

五、t-SNE 應用時的參數設置

在一般實務上使用 t-SNE 有以下參數可以設置：

困惑度（perplexity）
前期放大係數（early exaggeration factor）
學習率（learning rate）
最大迭代次數（maximum number of iterations）
角度（angle）

其中，最主要是設置困惑度（perplexity），論文中提出通常困惑度在 5 ~ 50 之間，有些狀況會設置到 100 以上，一般來說，大的資料集需要更大的困惑度。困惑度可以解釋成有效鄰近樣本點數量，困惑度越大，近鄰越多，對小區域的敏感度就越小，因此可以有以下結論：

困惑度低：只有少數鄰居有影響力，可能把同分群拆成多群。
困惑度高：全局結構較明顯，但可能群與群之間會無法區分。

不同的困惑度對產生的結果影響很大，因此判讀時可以考慮畫出多個圖比較。

圖：t-SNE plots for five different perplexity values

六、t-SNE 判讀注意事項

t-SNE 雖然有很強的捕捉局部特徵的能力，但也有許多要注意的地方：

1. t-SNE 的隨機性

t-SNE 演算法具有隨機性，多次實驗可以產生不同的結果，而一般常見 PCA 是確定性的（deterministic），每次計算後的結果相同。

2. t-SNE 的解釋性

由於演算法本身是基於機率的特性，解釋 t-SNE 的映射時要特別注意：

比較兩堆的大小沒有意義：t-SNE 會根據鄰居的擁擠程度來調整區塊的大小
比較兩堆間的距離沒有意義：並不是靠比較近的群集彼此就比較像，該嵌入空間中的距離並沒有直覺上的距離的性質。
t-SNE 不能用於尋找離群點：t-SNE 中的對稱項相當於把離群點拉進某群中。

因此，一般來說只可以用 t-SNE 做定性分析提出假設，不能用 t-SNE 得出結論。

3. 本徵維度（intrinsic dimensionality）

如果不能在 2D 中用 t-SNE 分群，並不一定這個資料就一定不能被模型良好區分，也有可能是 2 維不足夠表示這個資料的內部結構，也就是說原資料的本徵維度過高。

4. 一般 t-SNE 不適用於新資料

PCA 降維可以適用新資料，而一般的 t-SNE 則不行。在 python sklearn library 中的 t-SNE 演算法沒有 transform() 函式。如果真的需要 transform() 方法，需要使用另一種變體：parametric t-SNE，他不包含在 sklearn library 之中。

七、範例結果

1. 基礎的數字辨識：simple MNIST dataset (in 2D)

2. 行人辨識（re-id）：A small crop of the Barnes-Hut t-SNE of learned embeddings for the Market-1501 testset. The triplet loss learns semantically meaningful features.

3. 文字探勘：Clusters of similar words from Google News (preplexity=15, word embedding, NLP)

補記 1：流形學習 Manifold Learning

t-SNE 是一種流形學習 (Manifold Learning)，流形學習假設資料是均勻取樣於一個高維歐氏空間中的低維流形，因此可以從高維取樣資料中找到高維空間中的低維流形，並求出相應的嵌入對映。流形學習的代表方法有：

多尺度變換 (MDS, Multi-Dimensional Scaling)
等度量映射 (Isomap, Isometric Mapping）
局部線性嵌入 (LLE, Locally Linear Embedding)
拉普拉斯特徵映射 (LE, Laplacian Eigenmap)
隨機鄰近嵌入法 (SNE, Stochastic Neighbor Embedding)

圖：Comparison of Manifold Learning methods, from sklearn [link]

補記 2：維數災難

在機器學習中，維數災難（curse of dimensionality）通常用來說明給定固定數量的訓練樣本，模型預測能力隨著維度的增加而減小，造成這個現象的原因是當維數提高時，空間的體積提高太快，因而可用的資料點變得很稀疏。

1. 取樣

舉例來說，100 個平均分布的點能把一個單位區間以每個點距離不超過 0.01 採樣；而當維度增加到 10 後，如果以相鄰點距離不超過 0.01 小方格採樣一單位超正方體，則需要 $10^{20}$ 個採樣點:所以，這個 10 維的超正方體也可以說是比單位區間大 $10^{18}$ 倍。

圖：取樣之維數災難示意圖

2. 距離函數

另一個重要的例子是，當一個度量（如歐式距離）使用很多坐標來定義時，不同的樣本對之間的距離已經基本上沒有差別。一種用來描述高維歐幾里德空間的巨型性的方法是將超球體中半徑 ${\displaystyle r}$ 和維數 ${\displaystyle d}$ 的比例，和超立方體中邊長 ${\displaystyle 2r}$ 和等值維數的比例相比較。

一個球體的體積計算如下：${\displaystyle {\frac {2r^{d}\pi ^{d/2}}{d\Gamma (d/2)}}}$
立方體的體積計算如下： ${\displaystyle (2r)^{d}}$

隨著空間維度 ${\displaystyle d}$ 增加，相對於超立方體的體積來說，超球體的體積就變得微不足道了。這一點可以從當 ${\displaystyle d}$ 趨於無窮時比較前面的比例清楚地看出：
$$
{\displaystyle {\frac {\pi ^{d/2}}{d2^{d-1}\Gamma (d/2)}}\rightarrow 0}
$$
當 ${\displaystyle d\rightarrow \infty }$。因此在某種意義上，幾乎所有的高維空間都遠離其中心。或者從另一個角度來看，高維單元空間可以說是幾乎完全由超立方體的「邊角」所組成的，沒有「中部」，這對於理解卡方分布是很重要的直覺理解。給定一個單一分布，由於其最小值和最大值與最小值相比收斂於 0，因此，其最小值和最大值的距離變得不可辨別。
$$
{\displaystyle \lim _{d\to \infty }{\frac {\operatorname {dist} _{\max }-\operatorname {dist} _{\min }}{\operatorname {dist} _{\min }}}\to 0}
$$
這通常被引證為距離函數在高維環境下失去其意義的例子。

References

L.J.P. van der Maaten and G.E. Hinton. Visualizing High-Dimensional Data Using t-SNE. Journal of Machine Learning Research 9(Nov):2579-2605, 2008.

L.J.P. van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research 15(Oct):3221-3245, 2014.

L.J.P. van der Maaten. Learning a Parametric Embedding by Preserving Local Structure. In Proceedings of the Twelfth International Conference on Artificial Intelligence & Statistics (AI-STATS), JMLR W&CP 5:384-391, 2009.

Laurens van der Maaten (author) - t-SNE
https://lvdmaaten.github.io/tsne/

wiki - t-SNE
https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding

wiki - 維數災難
https://zh.wikipedia.org/wiki/%E7%BB%B4%E6%95%B0%E7%81%BE%E9%9A%BE

sklearn - Manifold learning
https://scikit-learn.org/stable/modules/manifold.html

t-SNE完整笔记
http://www.datakit.cn/blog/2017/02/05/t_sne_full.html

oreillymedia - t-SNE-tutorial
https://github.com/oreillymedia/t-SNE-tutorial

Distill - How to Use t-SNE Effectively
https://distill.pub/2016/misread-tsne/

hustqb - 數據降維與可視化——t-SNE
https://blog.csdn.net/hustqb/article/details/78144384#%E4%BC%98%E5%8C%96-t-sne

Microsoft Research Blog - Optimizing Barnes-Hut t-SNE
https://www.microsoft.com/en-us/research/blog/optimizing-barnes-hut-t-sne/

範葉亮 - 流形學習 (Manifold Learning)
https://leovan.me/cn/2018/03/manifold-learning/#fn:sklearn-manifold

Sergey Smetanin - Google News and Leo Tolstoy: Visualizing Word2Vec Word Embeddings using t-SNE
https://towardsdatascience.com/google-news-and-leo-tolstoy-visualizing-word2vec-word-embeddings-with-t-sne-11558d8bd4d

Pages

2019年6月4日星期二