2019年6月4日 星期二

資料降維與視覺化: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





沒有留言:

張貼留言

技術提供:Blogger.