t-SNE(t-distributed stochastic neighbor embedding)

t-SNE(t-distributed stochastic neighbor embedding)是用于降維的一種機器學習算法，是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出來。此外，t-SNE 是一種非線性降維算法，非常适用于高維資料降維到2維或者3維，進行可視化。

t-SNE是由SNE(Stochastic Neighbor Embedding, SNE; Hinton and Roweis, 2002)發展而來。我們先介紹SNE的基本原理，之後再擴充到t-SNE。最後再看一下t-SNE的實作以及一些優化。

1.SNE

1.1基本原理

SNE是通過仿射(affinitie)變換将資料點映射到機率分布上，主要包括兩個步驟：

我們看到t-SNE模型是非監督的降維，他跟kmeans等不同，他不能通過訓練得到一些東西之後再用于其它資料（比如kmeans可以通過訓練得到k個點，再用于其它資料集，而t-SNE隻能單獨的對資料做操作，也就是說他隻有fit_transform，而沒有fit操作）

1.2 SNE原理推導

SNE是先将歐幾裡得距離轉換為條件機率來表達點與點之間的相似度。具體來說，給定一個N個高維的資料 x1,...,xN

（注意N不是次元）, t-SNE首先是計算機率pij，正比于xi和xj

之間的相似度（這種機率是我們自主建構的），即：

pj∣i=exp(−∣∣xi−xj∣∣2/(2σ2i))∑k≠iexp(−∣∣xi−xk∣∣2/(2σ2i))

這裡的有一個參數是σi

，對于不同的點xi取值不一樣，後續會讨論如何設定。此外設定px∣x=0

,因為我們關注的是兩兩之間的相似度。

那對于低次元下的yi

，我們可以指定高斯分布為方差為12√

，是以它們之間的相似度如下:

qj∣i=exp(−∣∣xi−xj∣∣2)∑k≠iexp(−∣∣xi−xk∣∣2)

同樣，設定qi∣i=0

.

如果降維的效果比較好，局部特征保留完整，那麼 pi∣j=qi∣j

, 是以我們優化兩個分布之間的距離-KL散度(Kullback-Leibler divergences)，那麼目标函數(cost function)如下:

C=∑iKL(Pi∣∣Qi)=∑i∑jpj∣ilogpj∣iqj∣i

這裡的Pi

表示了給定點xi下，其他所有資料點的條件機率分布。需要注意的是KL散度具有不對稱性，在低維映射中不同的距離對應的懲罰權重是不同的，具體來說：距離較遠的兩個點來表達距離較近的兩個點會産生更大的cost，相反，用較近的兩個點來表達較遠的兩個點産生的cost相對較小(注意：類似于回歸容易受異常值影響，但效果相反)。即用較小的 qj∣i=0.2 來模組化較大的 pj∣i=0.8, cost=plog(pq)=1.11,同樣用較大的qj∣i=0.8來模組化較大的pj∣i=0.2

, cost=-0.277, 是以，SNE會傾向于保留資料中的局部特征。

思考:了解了基本思路之後，你會怎麼選擇σ

，固定初始化?

下面我們開始正式的推導SNE。首先不同的點具有不同的σi

，Pi的熵(entropy)會随着σi的增加而增加。SNE使用困惑度(perplexity)的概念，用二分搜尋的方式來尋找一個最佳的σ

。其中困惑度指:

Perp(Pi)=2H(Pi)

這裡的H(Pi)

是Pi

的熵，即:

H(Pi)=−∑jpj∣ilog2pj∣i

困惑度可以解釋為一個點附近的有效近鄰點個數。SNE對困惑度的調整比較有魯棒性，通常選擇5-50之間，給定之後，使用二分搜尋的方式尋找合适的σ

那麼核心問題是如何求解梯度了,目标函數等價于∑∑−plog(q)

這個式子與softmax非常的類似，我們知道softmax的目标函數是∑−ylogp，對應的梯度是y−p(注：這裡的softmax中y表示label，p表示預估值)。 同樣我們可以推導SNE的目标函數中的i在j下的條件機率情況的梯度是2(pi∣j−qi∣j)(yi−yj)， 同樣j在i下的條件機率的梯度是2(pj∣i−qj∣i)(yi−yj)

, 最後得到完整的梯度公式如下:

δCδyi=2∑j(pj∣i−qj∣i+pi∣j−qi∣j)(yi−yj)

在初始化中，可以用較小的σ

下的高斯分布來進行初始化。為了加速優化過程和避免陷入局部最優解，梯度中需要使用一個相對較大的動量(momentum)。即參數更新中除了目前的梯度，還要引入之前的梯度累加的指數衰減項，如下:

Y(t)=Y(t−1)+ηδCδY+α(t)(Y(t−1)−Y(t−2))

這裡的Y(t)

表示疊代t次的解，η表示學習速率,α(t)

表示疊代t次的動量。

此外，在初始優化的階段，每次疊代中可以引入一些高斯噪聲，之後像模拟退火一樣逐漸減小該噪聲，可以用來避免陷入局部最優解。是以，SNE在選擇高斯噪聲，以及學習速率，什麼時候開始衰減，動量選擇等等超參數上，需要跑多次優化才可以。

思考:SNE有哪些不足？ 面對SNE的不足，你會做什麼改進？

2.t-SNE

盡管SNE提供了很好的可視化方法，但是他很難優化，而且存在”crowding problem”(擁擠問題)。後續中，Hinton等人又提出了t-SNE的方法。與SNE不同，主要如下:

• 使用對稱版的SNE，簡化梯度公式
• 低維空間下，使用t分布替代高斯分布表達兩點之間的相似度

t-SNE在低維空間下使用更重長尾分布的t分布來避免crowding問題和優化問題。在這裡，首先介紹一下對稱版的SNE，之後介紹crowding問題，之後再介紹t-SNE。

2.1 Symmetric SNE

優化pi∣j

和qi∣j

的KL散度的一種替換思路是，使用聯合機率分布來替換條件機率分布，即P是高維空間裡各個點的聯合機率分布，Q是低維空間下的，目标函數為:

C=KL(P∣∣Q)=∑i∑jpi,jlogpijqij

這裡的pii

,qii為0，我們将這種SNE稱之為symmetric SNE(對稱SNE)，因為他假設了對于任意i,pij=pji,qij=qji

，是以機率分布可以改寫為:

pij=exp(−∣∣xi−xj∣∣2/2σ2)∑k≠lexp(−∣∣xk−xl∣∣2/2σ2)    qij=exp(−∣∣yi−yj∣∣2)∑k≠lexp(−∣∣yk−yl∣∣2)

這種表達方式，使得整體簡潔了很多。但是會引入異常值的問題。比如xi

是異常值，那麼∣∣xi−xj∣∣2會很大，對應的所有的j, pij都會很小(之前是僅在xi下很小)，導緻低維映射下的yi

對cost影響很小。

思考: 對于異常值，你會做什麼改進？pi

表示什麼？

為了解決這個問題，我們将聯合機率分布定義修正為: pij=pi∣j+pj∣i2

, 這保證了∑jpij>12n

, 使得每個點對于cost都會有一定的貢獻。對稱SNE的最大優點是梯度計算變得簡單了，如下:

δCδyi=4∑j(pij−qij)(yi−yj)

實驗中，發現對稱SNE能夠産生和SNE一樣好的結果，有時甚至略好一點。

2.2 Crowding問題

擁擠問題就是說各個簇聚集在一起，無法區分。比如有一種情況，高次元資料在降維到10維下，可以有很好的表達，但是降維到兩維後無法得到可信映射，比如降維如10維中有11個點之間兩兩等距離的，在二維下就無法得到可信的映射結果(最多3個點)。 進一步的說明，假設一個以資料點xi

為中心，半徑為r的m維球(三維空間就是球)，其體積是按rm增長的，假設資料點是在m維球中均勻分布的，我們來看看其他資料點與xi

的距離随次元增大而産生的變化。

從上圖可以看到，随着次元的增大，大部分資料點都聚集在m維球的表面附近，與點xi

的距離分布極不均衡。如果直接将這種距離關系保留到低維，就會出現擁擠問題。

怎麼解決crowding問題呢？

Cook et al.(2007) 提出一種slight repulsion的方式，在基線機率分布(uniform background)中引入一個較小的混合因子ρ

,這樣qij就永遠不會小于2ρn(n−1) (因為一共了n(n-1)個pairs)，這樣在高維空間中比較遠的兩個點之間的qij總是會比pij大一點。這種稱之為UNI-SNE，效果通常比标準的SNE要好。優化UNI-SNE的方法是先讓ρ為0，使用标準的SNE優化，之後用模拟退火的方法的時候，再慢慢增加ρ. 直接優化UNI-SNE是不行的(即一開始ρ不為0)，因為距離較遠的兩個點基本是一樣的qij(等于基線分布), 即使pij很大，一些距離變化很難在qij中産生作用。也就是說優化中剛開始距離較遠的兩個聚類點，後續就無法再把他們拉近了。

2.3 t-SNE

對稱SNE實際上在高次元下 另外一種減輕”擁擠問題”的方法：在高維空間下，在高維空間下我們使用高斯分布将距離轉換為機率分布，在低維空間下，我們使用更加偏重長尾分布的方式來将距離轉換為機率分布，使得高次元下中低等的距離在映射後能夠有一個較大的距離。

我們對比一下高斯分布和t分布(如上圖,code見probability/distribution.md), t分布受異常值影響更小，拟合結果更為合理，較好的捕獲了資料的整體特征。

使用了t分布之後的q變化，如下:

qij=(1+∣∣yi−yj∣∣2)−1∑k≠l(1+∣∣yi−yj∣∣2)−1

此外，t分布是無限多個高斯分布的疊加，計算上不是指數的，會友善很多。優化的梯度如下:

δCδyi=4∑j(pij−qij)(yi−yj)(1+∣∣yi−yj∣∣2)−1

t-sne的有效性，也可以從上圖中看到：橫軸表示距離，縱軸表示相似度, 可以看到，對于較大相似度的點，t分布在低維空間中的距離需要稍小一點；而對于低相似度的點，t分布在低維空間中的距離需要更遠。這恰好滿足了我們的需求，即同一簇内的點(距離較近)聚合的更緊密，不同簇之間的點(距離較遠)更加疏遠。

總結一下，t-SNE的梯度更新有兩大優勢：

• 對于不相似的點，用一個較小的距離會産生較大的梯度來讓這些點排斥開來。
• 這種排斥又不會無限大(梯度中分母)，避免不相似的點距離太遠。

2.4 算法過程

算法詳細過程如下：

• Data: X=x1,...,xn

• 計算cost function的參數：困惑度Perp
• 優化參數: 設定疊代次數T， 學習速率η
• , 動量α(t)
• 目标結果是低維資料表示 YT=y1,...,yn
• 開始優化
  • 計算在給定Perp下的條件機率pj∣i
• (參見上面公式)
• 令 pij=pj∣i+pi∣j2n
• 用 N(0,10−4I)
• 随機初始化 Y
• 疊代，從 t = 1 到 T， 做如下操作:
  • 計算低次元下的 qij
• (參見上面的公式)
• 計算梯度（參見上面的公式）
• 更新 Yt=Yt−1+ηdCdY+α(t)(Yt−1−Yt−2)

• • 結束
• 結束

優化過程中可以嘗試的兩個trick:

• 提前壓縮(early compression):開始初始化的時候，各個點要離得近一點。這樣小的距離，友善各個聚類中心的移動。可以通過引入L2正則項(距離的平方和)來實作。
• 提前誇大(early exaggeration)：在開始優化階段，pij

乘以一個大于1的數進行擴大，來避免因為qij太小導緻優化太慢的問題。比如前50次疊代，pij

• 乘以4

優化的過程動态圖如下：

2.5 不足

主要不足有四個:

• 主要用于可視化，很難用于其他目的。比如測試集合降維，因為他沒有顯式的預估部分，不能在測試集合直接降維；比如降維到10維，因為t分布偏重長尾，1個自由度的t分布很難儲存好局部特征，可能需要設定成更高的自由度。
• t-SNE傾向于儲存局部特征，對于本征維數(intrinsic dimensionality)本身就很高的資料集，是不可能完整的映射到2-3維的空間
• t-SNE沒有唯一最優解，且沒有預估部分。如果想要做預估，可以考慮降維之後，再建構一個回歸方程之類的模型去做。但是要注意，t-sne中距離本身是沒有意義，都是機率分布問題。
• 訓練太慢。有很多基于樹的算法在t-sne上做一些改進

3.變種

• multiple maps of t-SNE
• parametric t-SNE
• Visualizing Large-scale and High-dimensional Data