標(biāo)題：大規(guī)模高維數(shù)據(jù)可視化
作者來自MSRA
代碼開源好用:https://github.com/lferry007/LargeVis
編者的總結(jié)
- 類似t-SNE，本文以KNN圖捕捉原始數(shù)據(jù)分布妹笆，但目標(biāo)函數(shù)沒有采用KL散度西饵，但含義是類似地柴墩，只是更好地幫助訓(xùn)練惦辛，達(dá)成更快的速度和更穩(wěn)定的參數(shù)俗孝。
- 對于相似度的度量主要是L2距離条舔，無論在高維或者低維叙赚，不清楚在其他度量空間上是否有效。
- 相比于t-SNE拭荤，降維速度和參數(shù)穩(wěn)定性有很大提升茵臭，但是仍然比較慢，測試1M舅世，8線程要2-3個(gè)小時(shí)左右旦委。
ABSTRACT
- 本文是t-SNE的進(jìn)階版本，有兩個(gè)主要貢獻(xiàn)雏亚，一個(gè)是原始數(shù)據(jù)的KNN圖構(gòu)建加速缨硝，另一個(gè)是KNN圖投影到低維空間時(shí)的優(yōu)化目標(biāo)和訓(xùn)練方法更好更快了。
- 而且超參數(shù)更少更穩(wěn)定罢低，也是一個(gè)主要優(yōu)點(diǎn)查辩。
1. INTRODUCTION
- 降維/可視化的目的是在低維空間保持?jǐn)?shù)據(jù)點(diǎn)之間的近鄰性，原來近的降維之后也近网持，原來遠(yuǎn)的降維之后也遠(yuǎn)宜岛。
- 主要方法有線性（PCA，multi-dimension scaling）功舀，和非線性的（local linear embedding, laplacian eigenmaps）萍倡，按照t-SNE作者的說法，高維數(shù)據(jù)通常躺在低維空間的非線性流形上日杈，所以線性方法有效性有限遣铝。
- 非線性方法也沒有在保持局部和全局結(jié)構(gòu)。
- 目前最有效的就是t-SNE莉擒，基本策略是用一個(gè)KNN圖來代表原始數(shù)據(jù)的分布特征酿炸，然后將KNN圖投影到二維或低維空間。
image.png
3. LARGEVIS
3.1 Efficient KNN Graph Construction
這一部分沒什么好說的涨冀，KNN-graph用最新的技術(shù)去做就可以了填硕。
本文采用的是用樹來初始化knn-graph，用nn-descent來refine的過程鹿鳖，和effana比較像扁眯。樹的分裂是隨機(jī)選兩個(gè)點(diǎn)，取中間平面進(jìn)行分割翅帜。
3.2 A Probabilistic Model for Graph Visualization
首先KNN圖邊的權(quán)重和t-SNE的設(shè)計(jì)一樣：
image.png
- 含義是當(dāng)前i,j邊的長度和i所有的出邊的長度和的比值姻檀，相當(dāng)于一種歸一化。
- 然后準(zhǔn)備投影到低維空間涝滴，基本思路是首先隨機(jī)初始化每個(gè)點(diǎn)的坐標(biāo)绣版，然后根據(jù)一個(gè)目標(biāo)函數(shù)，每次sample一條邊對它的起點(diǎn)進(jìn)行refine歼疮，refine是一個(gè)梯度下降的訓(xùn)練過程杂抽。
- 目標(biāo)函數(shù)：對于在KNN圖中的邊，在二維空間上越近越好韩脏；反之亦然缩麸。KNN圖上的邊的權(quán)重在目標(biāo)函數(shù)上也是一個(gè)權(quán)重項(xiàng)。
-
表示的是在二維空間上的兩點(diǎn)之間相似度赡矢，可以用歐氏距離的一些變種來替代杭朱。
image.png - 實(shí)際情況1：因?yàn)樨?fù)邊實(shí)在太多，不可能全用吹散，所以可以采用一些負(fù)采樣技術(shù)痕檬，按照一個(gè)噪聲分布和一個(gè)正負(fù)邊的比例去采樣一些邊來訓(xùn)練。
- 實(shí)際情況2：權(quán)重
有時(shí)不好控制范圍送浊，可以通過權(quán)重大的邊多采樣幾次梦谜，權(quán)重小的邊少采樣的方式，將權(quán)重抹除袭景。
- 優(yōu)化器：異步隨機(jī)梯度下降唁桩，簡單點(diǎn)來說，如果圖很稀疏耸棒，邊很少（比如KNN圖K/N的稀疏度）荒澡，所以并行訓(xùn)練隨機(jī)采樣邊幾乎不會(huì)發(fā)生沖突，所以就可以不加鎖与殃，同步訓(xùn)練单山。
