笔记：ML-LHY-15: Unsupervised Learning - Neighbor Embedding

介绍了3中非线性降维方法
LLE基于相邻点的关系，然后在低维空间保持这种关系
Laplacian Eigenmaps基于图结构的关系，然后在低维空间保持这种关系
t-SNE基于分布的关系，然后在低维空间保持这种关系，巧妙利用不同相似度函数实现拉开不同类
视频 pdf

Manifold Learning非线性降维

在之前的Unsupervised Learning - Linear Methods说到PCA是没法做非线性变换的，比如下面：

通过降维，可以使用欧氏距离计算距离。比如左边在高维空间蓝色点和红色点更近，但是在右边的2维屏幕上是蓝色点和黄色点更近。而在做数据可视化时，我们往往需要的是右边的低维度便于观察彼此距离和进行聚类。

Locally Linear Embedding (LLE)

$x^j$是$x^i$相邻的点，它们之间的关系用$w_{ij}$表示，则我们希望下式尽可能小：
$$\sum _i{\Vert x^i?\sum _j{w}_{ij}{x}^j\Vert }_2$$
所以得到的$w_{ij}$就表示一组权重，$x^j$是周围的点和这个权重$w_{ij}$来表示$x^i$

保持$w_{ij}$不变

在低维度的空间找一组$z^j$和这个权重$w_{ij}$来表示$z^i$：

$$\sum _i{\Vert z^i?\sum _j{w}_{ij}{z}^j\Vert }_2$$

所以就实现从高维转低维。不是很懂~~，了解一下。

对k的选择比较敏感：

太近太远都不是很好的关系。

Laplacian Eigenmaps

在Semi-supervised提到Smoothness Assumption：
如果2点之间通过高密度路径（hightdensity path连通，则认为y1和y2是接近的
当然，可以在基于图的结构上计算近似距离。

相似度$s\left(x^i,x^j\right)$计算：
$$s\left(x^i,x^j\right)=\exp \left(?\gamma {\Vert x^i?x^j\Vert }^2\right)$$
然后$w_{i,j}=s\left(x^i,x^j\right)$，和LLE思想类似，求得两点之间关系$w_{i,j}$后，在低维空间找一个点$z^j$，我们希望S尽可能小的情况下找到对应的$z^i$，从而实现降维。
但是和在半监督学习不同的是，$z^j,z^i$都没有标签（在半监督学习中可能通过神经网络求得一部分），所以如果$z^i=z^j=0$那么S就一定是0，是会存在问题的。所以需要对z添加约束。

我们希望低维空间是M维的，而这些点组成的矩阵求秩也应该要为M。
$$\mathrm{Span}\left\{z^1,z^2,\dots z^N\right\}=R^M$$

T-distributed Stochastic Neighbor Embedding (t-SNE)

单纯使用LLE的方法能够使得同类聚集，但是缺没法使不同类分开，比如下面：

t-SNE目的就是为了解决这个。
t-SNE做法：
求点$x_i$到$x_j$的归一化距离(做归一化的目的是在不同维空间进行比较)：
$$P\left(x^j\mid x^i\right)=\frac{S\left(x^i,x^j\right)}{{\sum }_{k?=i}S\left(x^i,x^k\right)}$$
同样的，在低维空间也可求$z_i$到$z_j$的归一化距离：
$$Q\left(z^j\mid z^i\right)=\frac{S^{\prime }\left(z^i,z^j\right)}{{\sum }_{k?=i}{S}^{\prime }\left(z^i,z^k\right)}$$
我们希望一个点的周围分布在降维后保存不变，所以可以用周围点的归一化距离描述分布，我们希望总的分布误差越小越好。而描述分布差异用的就是KL散度(相对熵)，所以对下式进行GD，求z。

$$\begin{array}{r}L={\sum }_{i}KL\left(P\left(?\mid x^i\right)\Vert Q\left(?\mid z^i\right)\right)\\ ={\sum }_i{\sum }_{j}P\left(x^j\mid x^i\right)\log \frac{P\left(x^j\mid x^i\right)}{Q\left(z^j\mid z^i\right)}\end{array}$$

ok，回到上面问题，t-SNE为什么可以把不同类拉开？
关键在于$S$和$S^{\prime }$不一样：
S和Smoothness Assumption一样，欧式距离经过RBF
$$\begin{array}{l}S\left(x^i,x^j\right)\\ =\exp \left(?{\Vert x^i?x^j\Vert }_2\right)\end{array}$$
$S^{\prime }$则发生改变：
$$S^{\prime }\left(z^i,z^j\right)=1/1+{\Vert z^i?z^j\Vert }_2$$

由于$S^{\prime }$拖尾更长，在距离远的情况下(横轴大)，在保持同分布也就是相似度要一样的话$S^{\prime }$的横轴值会拉的更远。而在距离近的情况下(横轴小)，则不会差太多：

$S^{\prime }$不发生改变则叫SNE方法。

以上参考李宏毅老师视频和ppt，仅作为学习笔记交流使用