在介紹t-SNE之前，要從流形開始講起。
流形Manifold
将流形引入到機器學習領域主要有兩個用途：
- 改進原本歐式空間中的算法，使它能作用到流形上，直接或者間接地利用和流行的性質和構造。
- 将流形映射到歐式空間中，令歐式空間中的算法能對流形起作用。
eg. Isomap就是一個典型的将原本存在于歐式空間的算法進行改造，将流形映射到歐式空間的算法。
測地線 vs. 直線
歐式空間中用線段（直線）測量兩點之間的距離；流形中也一樣，不過這條“直線”就不是直的了，稱為測地線。
另一方面是改造現有算法使其适合流形結構甚至專門針對流形的特點來設計新的算法，比較典型的是 graph regularized semi-supervised learning 。當然，所有的這些都是基于同一個假設，那就是資料是分布在一個流形上的（部分算法可能會有稍微寬松一些的假設），然而 real world 的資料，究竟哪些是分别在流形上的呢？這個卻是很難說。不過，除了典型的 face 和 hand written digit 之外，大家也有把基于流形的算法直接用在諸如 text 看起來好像也流形沒有什麼關系的資料上，效果似乎也還不錯。
在實際應用中，擷取測地距離是比較困難的，一般通過構造kNN圖，在圖中尋找最短路徑距離作為真實的測地距離。
kNN圖
建構kNN圖的常見方法一般有三類：第一類是空間分割樹(space-partitioning trees)算法，第二類是局部敏感哈希(locality sensitive hashing)算法，第三類是鄰居搜尋(neighbor exploring techniques)算法。其中k-d(Random Projection Tree)樹和随機投影樹均屬于第一類算法。
SNE
核心思想很簡單，在高維空間中相似的資料點，在映射後的低維空間中也相似。正常做法是将歐式距離作為相似度度量。考慮高維空間中的兩個資料點xi和xj，xi以條件機率pj∣i選擇xj作為它的鄰近點。
77x))
假設高維資料點xi和xj在低維空間的映射點分别為yi和yj。類似的，低維空間中的條件機率用qj∣i表示
)
可推。若考慮xi與其他所有點之間的條件機率，則可構成一個條件機率分布Pi，同理在低維空間存在一個條件機率分布Qi且應該與Pi一緻。那麼，如何衡量兩個分布之間的相似性…？
KL距離!(Kullback-Leibler Divergence)。SNE算法的目的就是最小化這個目标函數。優化算法可以使用梯度下降法。
)
似乎到這裡問題就解決了，但是注意觀察目标函數，當pj∣i較小而qj∣i較大時，函數的代價居然也較小。為什麼說“居然”呢，剛才講了pj∣i較小表示兩個資料點在高維空間中距離較遠，qj∣i較大表示兩個資料點在映射的低維空間中距離較近，這個時候得到的代價居然偏小，這就有問題了。也就是說，SNE隻關注到全局資料，而忽略了局部資料。
對稱SNE
關鍵在于，它解決了SNE存在的不對稱問題。
在原始的SNE中，pi∣j與pj∣i是不相等的，低維空間中qi∣j與qj∣i也是不相等的。是以如果能得出一個更加通用的聯合機率分布更加合理，即分别在高維和低維空間構造聯合機率分布P和Q，使得對任意i,j，均有pij=pji,qij=qji。
相應地，将pij和qij定義為：
)
)
？是這樣嗎。
由于KL散度的不對稱性，這樣定義的分布又會遇到跟SNE一樣的問題。是以這裡采用一個更簡單直接的定義：
)
相應地，目标函數寫成：
)
相比剛才定義的公式，這個梯度更加簡化，計算效率更高。但是别高興的太早，雖然我們解決了SNE中的不對稱問題，得到了一個更為簡單的梯度公式，但是Maaten指出，對稱SNE的效果隻是略微優于原始SNE的效果，依然沒有從根本上解決問題。
擁擠問題 The Crowding Problem
由于我們生活在一個低維的世界中，我們對于資料可視化的接受程度最多不超過三維，超過這個次元的可視化我們便難以了解了。這也是為什麼在讨論流行的時候，總喜歡以“Swiss roll”為例，這不過是将二維流形嵌入到三維空間而已。實際上，流形的實際應用遠比它要複雜得多。舉個例子，在10維流形上可以存在11個點且兩兩之間距離相等。在二維空間中呢？我們最多隻能使三個點兩兩之間距離相等，想将高維空間中的距離關系完整保留到低維空間是不可能的。随着次元的不斷增大，定會存在資料點擁擠問題。
t分布
t分布是典型的長尾分布。在穩定分布中，除了正态分布，其他均為長尾分布。長尾分布在處理小樣本和異常點具有良好的效果。
使用自由度為1的t分布重新定義qij：
依然用KL距離衡量兩個分布之間的相似性，此時梯度變為:
這就是最終的t-SNE算法，它相比最初的SNE做了兩個改進：1）SNE改為對稱的SNE；2）t分布代替高斯分布。
t-SNE v.s. 其他降維算法
優點
除了t-SNE以外的大多數非線性降維方法，都沒辦法同時保留局部和全局的結構。尤其是對局部的隐藏結構更加敏感。對于處理存在多個流形的高維資料很有效果。
缺點
- 時間複雜度和空間複雜度均為O(n^2)，導緻其無法高效處理大型資料集；
- 更新版Barnes-Hut t-SNE可以讓複雜度降為O(nlogn)，但隻限于獲得二維和三維的嵌入；
- 由于代價函數非凸，多次執行算法的結果是随機的，需要多次運作選取最好的結果；
- 全局結構不能很清楚的保留。這個問題可以通過先用PCA降維到一個合理的次元（如50）後再用t-SNE來緩解，前置的PCA步驟也可以起到去除噪聲等功能。（sklearn中可以直接使用參數init=‘pca’）
回到Manifold
對于t-SNE在擷取資料在流形空間中相似性的方法，有很多中改進方法。以及對于測度度量的方法，也能有很多改進。
當然，本文隻是淺談流形，對于其測地線、距離度量方法都有很多值得我們深究探讨的地方。
參考：
[1]: https://bindog.github.io/blog/2016/06/04/from-sne-to-tsne-to-largevis/
[2]: https://blog.pluskid.org/archives/533
[3]: https://www.jianshu.com/p/a24a1cabb553