【李宏毅2020 ML/DL】P58 Unsupervised Learning - Neighbor Embedding | LLE, t-SNE

我已经有两年 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}$来描述。将 $w_{ij}$ 值固定住。

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

$\sum\limits_i||z^i-\sum\limits_j w_{ij}z^j ||_2$

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

Laplacian Eigenmaps

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

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

复习一下半监督学习

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

$S=\frac{1}{2}\sum\limits_{i,j} w_{i,j}(y^i-y^j)^2=y^TLy$

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

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

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

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

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

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

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

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

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

T-distributed Stochastic Neighbor Embedding (t-SNE)

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

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

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

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

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

如何找 $z$ ？则让 $P$ 与 $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)}$

运算量有些大。可能需要先降维，再用 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)$

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

在信息熵的基础上，我们定义 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}$

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

t-SNE Similarity Measure

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

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

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

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

如上，这样得效果是：

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

即，t-SNE让gap夸张化。

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