理解TSNE算法

結合

t-SNE 是一種數據可視化工具,它可以將高維數據降維到2-3維以用於畫圖,局部相似性被這種embedding所保留。

t-SNE把原空間的數據點之間的距離轉換為高斯分佈概率,如果兩點在高維空間距離越近,那麼這個概率值越大。注意到高斯分佈的這個標準差$sigma_i$ 對每個點都是不同的,這也是算法的創新點之一,因為理論上空間不同位置的點的密度是不同的,條件概率如此計算,

$$p_{j|i} = frac{exp{(-d(boldsymbol{x}_i, boldsymbol{x}
Screen Shot 2018-01-30 at 15.18.45

圖中公式是理論方式,實際是先計算條件概率再用下面公式來產生聯合分佈,

$$p_{ij} = frac{p_{j|i} + p_{i|j}}{2N}.$$

其中$sigma_i$ 將自動確定。這個過程可以通過設置算法的困惑性來影響。

用一個長尾分佈(Student-t Distribution,簡稱為t分佈)來表示embed空間的相似性
$$q_{ij} = frac{(1 + ||boldsymbol{y}_i – boldsymbol{y}
Screen Shot 2018-01-30 at 15.28.56

損失函數是兩個分佈之間的Kullback-Leibler divergence(KL散度)

$$KL(P|Q) = sum_{i neq j} p_{ij} log frac{p_{ij}}{q_{ij}}$$

而為什麼說tsne保留的是局部相似性呢?我們從KL散度的公式出發來解釋,
Screen Shot 2018-01-30 at 15.33.19
可以看到,當$p_{ij}$很大而$q_{ij}$很小(高維空間距離近,低維空間距離遠)懲罰很大,反之懲罰小(高維空間距離遠,低維空間距離近)。

而為什麼高維空間用高斯分佈,低維空間用Student-t Distribution呢?

Screen Shot 2018-01-30 at 15.41.32Screen Shot 2018-01-30 at 15.41.43
原因就是因為降維是必然要帶來信息損失,我們要保存局部信息那麼必然要損失全局信息,比如我們要把上面的這個2維空間的三個成直角邊的點降維到1維,那麼把它們放平就保存了局部信息(左中和中右之間的距離保持不變),但是犧牲了全局信息(左右之間的距離變大了)。而Student-t Distribution就能放大這種密度,如下圖(tsne默認t分佈自由度為1),t分佈相比高斯分佈更加長尾。
Screen Shot 2018-01-30 at 15.48.47
梯度計算時有優化技巧,如果按下圖中的原公式計算,複雜度為$O(N^2)$ Barnes-Hut 樹方法就可以優化到$ O(NlogN)$
Screen Shot 2018-01-30 at 15.59.02
Screen Shot 2018-01-30 at 16.01.17
原理類似於用上圖中ABC三點中心的距離乘以三來代替計算三者各自的距離。
那麼把用barnes樹結構來進行深度優先搜索,分別判斷其距離是否大於閾值,分塊計算距離,這樣複雜度就降低了。
Screen Shot 2018-01-30 at 16.01.38

以下是計算損失KL散度的公式,

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 def
skip_num_points=
"""t-SNE objective function: gradient of the KL divergence
of p_ijs and q_ijs and the absolute error."""
X_embedded = params.reshape(n_samples, n_components)

# Q is a heavy-tailed distribution: Student's t-distribution
n = pdist(X_embedded,
n +=
n /= degrees_of_freedom
n **= (degrees_of_freedom +
Q = np.maximum(n / (

# Optimization trick below: np.dot(x, y) is faster than
# np.sum(x * y) because it calls BLAS

# Objective: C (Kullback-Leibler divergence of P and Q)
kl_divergence =

# Gradient: dC/dY
grad = np.ndarray((n_samples, n_components))
PQd = squareform((P - Q) * n)
for
np.dot(_ravel(PQd[i]), X_embedded[i] - X_embedded, out=grad[i])
grad = grad.ravel()
c =
grad *= c

用梯度下降(和一些tricks)優化,值得注意的是損失函數非對稱,並且不同的訓練會導致結果的不同。

sklearn裡對於binary search計算聯合分佈下面的(

 1
2
3
4
5
6
7
8
9
10
11
12
 def
"""Compute joint probabilities p_ij from distances."""
# Compute conditional probabilities such that they approximately match
# the desired perplexity
distances = astype(distances, np.float32, copy=

conditional_P = _utils._binary_search_perplexity(
distances,
P = conditional_P + conditional_P.T
sum_P = np.maximum(np.
P = np.maximum(squareform(P) / sum_P, MACHINE_EPSILON)
return
 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def
n_components, angle=
verbose=
"""t-SNE objective function: KL divergence of p_ijs and q_ijs."""
params = astype(params, np.float32, copy=
X_embedded = params.reshape(n_samples, n_components)
neighbors = astype(neighbors, np.int64, copy=
if
sP = squareform(P).astype(np.float32)
else
sP = P.astype(np.float32)

grad = np.zeros(X_embedded.shape, dtype=np.float32)
error = _barnes_hut_tsne.gradient(sP, X_embedded, neighbors,
grad, angle, n_components, verbose,
dof=degrees_of_freedom)
c =
grad = grad.ravel()
grad *= c

return

t-SNE – Laurens van der Maaten

Facebook
Twitter
LinkedIn
Pinterest
Tumblr