我已经有两年 ML 经历，这系列课主要用来查缺补漏，会记录一些细节的、自己不知道的东西。

已经有人记了笔记（很用心，强烈推荐）：https://github.com/Sakura-gh/ML-notes

本节对应笔记：

• https://github.com/Sakura-gh/ML-notes/blob/master/ML-notes-md/21_Unsupervised%20Learning%20Neighbor%20Embedding.md

本节内容综述

1. t-SNE 中 NE 就是 Neighbor Embedding 。在高维空间中，直接算 distance 肯能不符合常理，因为数据所处得形状可能不是均匀得。
2. 第一个方法 Locally Linear Embedding (LLE)。
3. 另一个方法为 Laplacian Eigenmaps ，拉普拉斯特征映射。
4. 之前的方法假设了“相近的点是接近的”，但没有防止“不相近的点接近”。因此提出T-distributed Stochastic Neighbor Embedding (t-SNE)。

小细节

Locally Linear Embedding (LLE)

在高维空间中，找到各个数据见的关系，用$w_{ij}$wij​来描述。将 $w_{ij}$wij​ 值固定住。

此时，将 $x$x 降维成 $z$z 。然后我们的优化目标就是

$\sum\limits_i||z^i-\sum\limits_j w_{ij}z^j ||_2$i∑​∣∣zi−j∑​wij​zj∣∣2​

如上，规定 w 时，找几个邻居也很重要。

Laplacian Eigenmaps

之前将半监督学习时提到过 smoothness assumption ，两点间的“密度距离”也很重要。如果在很密的区域比较近，那才是真的近。

于是我们依据某个规则建立图，两点间距离即为通路边数。

复习一下半监督学习

$L=\sum\limits_{x^r} C(y^r,\hat y^r) + \lambda S$L=xr∑​C(yr,y^​r)+λS

$S=\frac{1}{2}\sum\limits_{i,j} w_{i,j}(y^i-y^j)^2=y^TLy$S=21​i,j∑​wi,j​(yi−yj)2=yTLy

其中，C是带有标签的项，而S表示平滑的正则。

于是我们把这个思维用在这里

于是，我们的目标就是最小化下式：
$S=\sum\limits_{i,j} w_{i,j} ||z^i-z^j||_2$S=i,j∑​wi,j​∣∣zi−zj∣∣2​

注意，上式中，$w$w表示相似度。

但是这样遇到问题，因为其最优解可以为$z^i=z^j=0$zi=zj=0。

在半监督学习中，因为还有标签数据$\sum\limits_{x^r} C(y^r,\hat y^r)$xr∑​C(yr,y^​r)的牵制，因此不好出现这种情况；在无监督学习中，我们只能照猫画虎地添加一些额外约束：

• 假设降维后z所处的空间为$M$M维，则$Span\{z^1,z^2,...,z^N\}=R^M$Span{z1,z2,...,zN}=RM，我们希望降维后的$z$z占据整个$M$M维的空间，而不希望它在一个比$M$M更低维的空间里。

其实，最终得到的$z$z就是拉普拉斯矩阵的特征向量。而谱聚类spectral clustering就是在这基础上做K-means。

拉普拉斯图矩阵的相关内容：【李宏毅2020 ML/DL】P24 Semi-supervised的smoothness。

T-distributed Stochastic Neighbor Embedding (t-SNE)

如上，没有让不同的类相互远离。

首先计算数据间的相似度：$S(x^i, x^j)$S(xi,xj)。

变成概率模型（归一化）：
$P(x^j|x^i)=\frac{S(x^i,x^j)}{\sum_{k\ne i}S(x^i,x^k)}$P(xj∣xi)=∑k​=i​S(xi,xk)S(xi,xj)​

对于 $z$z 也同理：$S(z^i, z^j)$S(zi,zj)。

变成概率模型（归一化）：
$Q(z^j|z^i)=\frac{S'(z^i,z^j)}{\sum_{k\ne i}S'(z^i,z^k)}$Q(zj∣zi)=∑k​=i​S′(zi,zk)S′(zi,zj)​

如何找 $z$z ？则让 $P$P 与 $Q$Q 的分布越近越好。

使用 KL散度（KL divergence）：
$L=\sum\limits_i KL(P(|x^i)||Q(|z^i))\ =\sum\limits_i \sum\limits_jP(x^j|x^i)log \frac{P(x^j|x^i)}{Q(z^j|z^i)}$L=i∑​KL(P(∣xi)∣∣Q(∣zi)) =i∑​j∑​P(xj∣xi)logQ(zj∣zi)P(xj∣xi)​

运算量有些大。可能需要先降维，再用 t-SNE 。

此外，t-SNE只能把一堆数据输入，不能对单个数据学习。因此，t-SNE不适合训练模型，而适于做固定数据的可视化。比如将高维数据可视化到二维平面上。

KL Divergence

感谢Sakura-gh的分享，这里补充一下 KL 散度的基本知识。

KL 散度是从信息论里演化而来的。首先介绍信息熵：$H=-\sum\limits_{i=1}^N p(x_i)\cdot log\ p(x_i)$H=−i=1∑N​p(xi​)⋅log p(xi​)

其用于翻译一个概率分布所需要的平均信息量。

在信息熵的基础上，我们定义 KL 散度为：
$\begin{aligned} & D_{KL}(p||q) & =\sum\limits_{i=1}^N p(x_i)\cdot (log\ p(x_i)-log\ q(x_i)) & \\ & & =\sum\limits_{i=1}^N p(x_i)\cdot log\frac{p(x_i)}{q(x_i)} & \\ \end{aligned}$​DKL​(p∣∣q)​=i=1∑N​p(xi​)⋅(log p(xi​)−log q(xi​))=i=1∑N​p(xi​)⋅logq(xi​)p(xi​)​​​

显然，$D_{KL}(p||q)$DKL​(p∣∣q)表示的就是概率$q$q与概率$p$p之间的差异。很显然KL散度越小，$q$q与$p$p的差异越小。

t-SNE Similarity Measure

之前的方法常常采用欧式距离，并且使用了RBF function ：$S(x^i,x^j)=e^{-||x^i-x^j||_2}$S(xi,xj)=e−∣∣xi−xj∣∣2​

这样欧式距离稍大一点，相似度将下降得很明显。

此外，SNE方法在降维后，也使用相同的相似度衡量公式：$S'(z^i,z^j)=e^{-||z^i-z^j||_2}$S′(zi,zj)=e−∣∣zi−zj∣∣2​。

但是，t-SNE方法在降维后，采用了不同得衡量方法，即t-distribution：$S'(z^i,z^j)=\frac{1}{1+||z^i-z^j||_2}$S′(zi,zj)=1+∣∣zi−zj∣∣2​1​

如上，这样得效果是：

• 如果原来的 $||x^i - x^j||_2$∣∣xi−xj∣∣2​ 足够小，那么降维后$||z^i - z^j||_2$∣∣zi−zj∣∣2​的值也不会太大；
• 但是如果原来的$||x^i - x^j||_2$∣∣xi−xj∣∣2​有些大，那么降维后$||z^i - z^j||_2$∣∣zi−zj∣∣2​将会进一步增加这个距离。

即，t-SNE让gap夸张化。

效果如上（当然不是直接做了像素，而是先降维，再t-SNE）。