[非監督]t-SNE降維

2019-01-23 本文已影响69人 RJ阿杰

Manifold learning

Manifold的概念是低維空間的數據被塞在高維空間中，我們的目的就是將X（高維數據）與Z（低維度的數據）做轉換。

LLE(locally linear embedding)

$x^i$ 表示自己， $x^j$ 表示鄰居，{自己}減去{自己的所有鄰居}與{w的線性組合}，然後我們對每一筆數據都做一次求它們的MSE，然後要越小越好。

高維空間的x可以轉成低維空間的z，它們的w是不變的。
每一個點與點(鄰居)間的euclidean distance(歐式距離)必須要很小，結果才成立，所以我們選不同數量的K(他們的鄰居)，會有不同的結果。

t-SNE(t-distributed stochastic neighbor embedding)

前面的LLE確實會把同的類別放在一起，但它不會把不同的類別分開，而t-SNE將不同類別區別開來，主要用於可視化。

SNE

先來講講SNE，給定一個N個高維的數據 $x_1,...,x_N$ (多個特徵)，SNE的式子如下圖，||?||是求歐式距離， $\sigma$ 是標準差，SNE將數據點之間高維的歐氏距離轉換為條件概率(表示相似度)，即用條件概率P(j|i)表示點 $x^{j}$ 到點 $x^{i}$ 的相似度。令p(i|i)为0，因為我們關注的是點兩兩之間的相似度。參數 $σ_i$ ，對於不同的點xi取值不一樣，後續會討論如何設置。
$\frac{ e^{ {自己與鄰居的歐式距離}^{2} /2 \sigma^{2} } }{ e^{ {自己與所有鄰居的歐式距離}^{2} /2 \sigma^{2} } } ，有normization的效果。$

這邊假定轉換後的低維下 $y_i$ (對應高維 $x_i$ ) 和 $y_j$ (對應高維 $x_j$ )的條件概率為q(j∣i)，而我們可以指定標準差 $\sigma = \frac{1}{ \sqrt{2} }$ ，令q(i∣i)=0。

我們的總體目標是選擇 Y 中的一個數據點，然後其令條件概率分佈 q 近似於 p。這一步可以通過最小化兩個分佈之間的 KL 散度（損失函數）而實現，這一過程可以定義為：

我們希望能最小化該損失函數，所以我們可以使用梯度下降進行迭代更新。

常態分怖的關係
上面可以看做是常態分怖， $x^{i}為 \mu$ ，對於鄰近的點P(j|i)機率較高， $\sigma$ 決定由中心 $\mu$ 向外遠離的點機率下降的速度。
$σ^{i}$ 是以 $x^{i}$ 為中心的高斯分佈的方差。因為數據點的稠密程度不同，因此這個方差選用單個固定值是不合理的，例如在密度高的區域適合選用較小的方差值。

如何求σ
我們定義一個constant叫"困惑度(perplexity)"，將前面的機率代入這個式子，用來二分搜索來找這個合適的σ，困惑度通常設於5到50之間， $H( P_{i} )$ 是 $P_{i}$ 的熵(entropy)。
想了解不同perplexity的變化可以參考這篇:
https://cloud.tencent.com/developer/article/1143644

SNE的問題
由於KL散度並不具有對稱性，所以數據點對距離之間的不同類型的錯誤在權重上是不均勻的。簡單來說，從P到Q的度量通常並不等於從Q到P的度量。

t-SNE

t-SNE通常只用在降維做可視化。
t-SNE重點解決了兩個問題，一個是SNE的不對稱問題（用聯合概率分佈替代條件概率分佈），另一個是不同類別之間簇的Crowding(擁擠)問題（引入t分佈）。

不對稱問題
首先使用聯合概率分佈來替代條件概率分佈，使得 $∀i,j，p_{ij}=p_{ji}，q_{ij}=q_{ji}$ 。
但會有另一個問題，如果數據點 $x_i$ 離群簇非常遠，則 $∥ x_{i} − x_{j} ∥^2$ 的值會很大，而 $p_{ij}$ 會相應變得非常小，也就是說 $x_i$ 的位置很遠這件事情對損失函數影響很小（沒有足夠的懲罰）。