球面上的雙隨機(jī)鄰居嵌入筆記（Doubly Stochastic Neighbor Embedding on Spheres ）
introduction：SNE存在比較嚴(yán)重的擁擠問題，這種擁擠問題的產(chǎn)生主要是由于SNE傾向于把高階的數(shù)據(jù)點放在中心，而把低階的數(shù)據(jù)點放在外圍這就造成了數(shù)據(jù)的擁擠問題，為了解決這個問題在2003年Laurens van der Maaten和Geoffrey Hinton提出了t-SNE來解決這個問題。本文作者做出的技術(shù)改進(jìn)是：首先引入了快速歸一化的方法，把相似矩陣歸一化為雙隨機(jī)，那么所有的數(shù)據(jù)點就具有相等的相似度。用球面的替代平面的嵌入空間從而實現(xiàn)去中心化而且當(dāng)輸入的矩陣是雙隨機(jī)矩陣的時候，低維空間的數(shù)據(jù)點將會嵌入到球體的周圍（通過下面的圖形可以發(fā)現(xiàn)），這有助于不同鏃數(shù)據(jù)之間的相似性，如果輸入領(lǐng)域圖（neighborhoodgraph）是非對稱的可以將其轉(zhuǎn)化為雙隨機(jī)矩陣。其次，如果輸入的矩陣是雙隨機(jī)的那么數(shù)據(jù)點通常會分布在球上，?根據(jù)這種現(xiàn)象本文將二維歐氏嵌入空間替換為三維空間中的球體，從而實現(xiàn)去中心化來避免出現(xiàn)“擁擠問題”。
通過上面左邊t-SNE數(shù)據(jù)可視化和右面DSNES可視化可以直觀的發(fā)現(xiàn)DSNES的效果明顯要優(yōu)于t-SNE可視化的效果，有效的解決了擁擠問題。
method:輸入矩陣P是個非負(fù)對稱矩陣（nonnegative and symmetric matrix ），如果節(jié)點的度（即P的行和或列和）分布高度不均勻，高階節(jié)點的吸引力更大而低階節(jié)點的吸引力更?。ㄔ趖-SNE的KL散度梯度下降過程中，將下降的結(jié)果視為引力和斥力作用的結(jié)果）。所以這就會造成擁擠問題的出現(xiàn)。為了解決這個問題，對圖親和力進(jìn)行規(guī)范化使圖的節(jié)點具有相同的度。使得矩陣的和約束同樣對于雙隨機(jī)也有同樣的定義。
? ? 如果給定的矩陣是一個非規(guī)范化矩陣（non-normalized matrix），我們可以應(yīng)用Sinkhorn-Knopp的方法將其投影到最近的雙隨機(jī)矩陣P，通過這種方式來保證矩陣的稀疏性。這種方法的原理是：初始化P=S并迭代以下更新規(guī)則，直到P收斂，對于所有的i都有,對于所有的i、j也有。
通過以下方法也可以構(gòu)造雙隨機(jī)矩陣：假設(shè)反對稱矩陣,
