機器學習_學習筆記系列(78)：t-隨機鄰近嵌入法(t-distributed stochastic neighbor embedding)
OK今天我們就繼續延續非監督式學習中的非線性降維，而我們今天要介紹的是「t-distributed stochastic neighbor embedding」。
t-distributed stochastic neighbor embedding
關於t_SNE演算法，其是由Laurens van der Maaten和Geoffrey Hinton所提出的，其論文名稱為
Visualizing Data using t-SNE
大家看到了嗎，又是Geoffrey Hinton，我們的深度學習之父。
而對當我們在做非監督式學習的時候，很多時候會選用t-SNE來做，最主要是他的結構和效能的表現相當的好。
對於t-SNE的概念，就是把原本資料點和點之間的歐幾里得距離，改成以機率的形式來表示，所以假使我們有一筆資料集X，總共有N筆數據，M個特徵，當高斯分布的中心為x_i時，挑選到x_j為我們neighbor的機率為
其中σ_i代表以x_i為中心的高斯分布變異數。
相對的我們一樣以降維後的資料Y以機率分布的形式表示
其中以y_i為中心的高斯分布變異數我們設為1/sqrt(2)。
接下來，我們希望能夠做到的事情就是高維度空間的機率能接近我們低維度空間的機率，所以我們SNE要最佳化的是所有資料間的Kullback-Leib Divergence總和
其中P_i為當我們選x_i，其他資料點的條件機率分布，Q_i為選y_i其他資料點的條件機率分布。
但是因為我們的資料分布通常是非常多變的，所以說我們不太可能找到一個σ_i滿足所有資料點。因為在dense region使用較小的一個σ_i，一定比sparse region選用較小的σ_i來得好。
所以說對於每個特定的一個σ_i，當σ_i增加，我們的分布的entropy也會跟著上升。而對於SNE演算法，其是以Binary Search的方式找尋P_i，且P_i要符合我們自己所設定的Perplexity，其可以寫為
其中H(P_i)為P_i的Shannon entropy，其等於
而通常我們會把Perplexity設成2~50這個區間。
接著針對我們上面提到的最佳化問題，我們就可以用梯度下降的方法來解我們想要的y_i，所以我們對C以y_i做微分可以得到
不過在這邊作者有提到，為了避免梯度下降的local minima問題，我們會在梯度下降的更新項多加入一個momentum項
其中η代表learning rate，α(t) 為momentum。最後迭代數次後，我們就可以得到我們的降維後的資料Y
但是實際上原本的SNE演算法，高維度資料的距離，其實很難完整的保存到低維度空間，所以面對這樣的問題，這篇paper也提出了相對應的解決方法，就是使用symmetric SNE以及t-distribution
symmetric SNE
關於這個改進方法，我們會把原本高維度空間的機率寫成
所以做梯度下降的時候，我們的微分方程式就會變成
t-distribution
對於使用t-distribution來取代gaussian distribution的好處就是，他能夠避免降維過後產生的crowding problem，也就是說當我們的資料點屬於離中心點比較近的時候，在降維過後能得到較大的距離。
所以在這裡我們會把低維度空間的機率改寫為
所以我們可以把我們梯度下降的微分方程式再改寫成
Note
我們可以看到在上面用到了梯度下降，所以我們必須給定初始值Y，但是顯然直接把Y一開始全部設成0會讓我們的梯度下降收斂速度很慢，所以在這裡我們會先用Principal Component Analysis先初始化我們的Y。
Example
接下來我們一樣以MNIST手顯辨識資料集當作例子
我們可以看到運用t-SNE的效果明顯筆我們之前介紹的各種流型學習演算法效能來得好，所以這也是為什麼t-SNE很常被運用在降維上。
Python Sample Code:
Github:
Reference:
[1] Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of machine learning research, 9(11).
[2] Scikit-learn: Machine Learning in Python, Pedregosa et al., JMLR 12, pp. 2825–2830, 2011.
