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