Manifold Learning(流形学习)

理解：流形学习就是将高维数据恢复成低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，以实现维数约简或者数据可视化。

在比较近的距离中欧式距离可以使用(如蓝色区域的几个点)，在较远距离中欧式距离不适用(如蓝色区域点-黄色区域点欧式距离>蓝色区域点-红色区域点欧式距离，但从 Manifold角度看从蓝色区域走到黄色区域距离较近)

若我们可以将数据降维，这样就方便使用欧式距离了。接下来讲一系列的非线性降维方法，凭借降维前的空间中 每个点和它邻居的关系来降维。

---

1 Locally Linear Embedding局部线性嵌入

过程

• 在高维空间中，$x^i$xi有三个邻居点$x^j$xj(红色圈处)，$x^i$xi与$x^j$xj存在某种关系$w_{ij}$wij​
• 假设$x^i$xi可以通过$x^j$xj线性组合得到
• 找到一组$w_{ij}$wij​，使得$\sum_i||x^i-\sum_jw_{ij}x^j||_2$∑i​∣∣xi−∑j​wij​xj∣∣2​最小
• 在低维空间中，固定$w_{ij}$wij​不变，找出$z^i$zi和$z^j$zj，使得$\sum_i||z^i-\sum_jw_{ij}z^j||_2$∑i​∣∣zi−∑j​wij​zj∣∣2​最小。即基于$w_{ij}$wij​，找到$x^i$xi降维后的$z^i$zi，以及$x^j$xj降维后的$z^j$zj
  

注意

• 在高维转换为低维时，通常距离近的点，其关系更稳定 不易改变。
• 但是阈值我们不可知，选的邻居个数K不能过大/过小。K=5(过小)，则维度展开不完全，降维效果不好。K=60(过大)，则意味几乎跟每个邻居都作比，降维效果仍然不好。
  

2 Laplacian Eigenmaps拉普拉斯特征图

思想
在高维空间中不可使用欧式距离计算的话，我们可以基于曲线图计算距离(Graph-based approach)。[此处需要回顾半监督学习-4.平滑假设-方法2，概要如下]

当用于无监督学习时

• 为了防止$z^i$zi=$z^j$zj=0，需要加约束条件，即假如现降维至M，则需要降维后的$z^1...z^N$z1...zN能够填满整个M维平面。即：Span$\{z^1,z^2,...,z^N\}${z1,z2,...,zN} = $R^M$RM

3 T-distributed Stochastic Neighbor Embedding(t-SNE)t分布随机邻接嵌入

以上的方法均表明高纬度中距离较近的点，降维后距离依然很近。但是并未说明高纬度中距离较远的点，降维后会如何。举例：MNIST中不同颜色代表不同数字，LLE可将同样的数字聚在一起，但是并没办法将不同的数字分开。

做法
核心思想：前面的做法是尽量使相近的点降维后距离不变，而t-SNE方法是使降维后分布接近，即距离大的降维后仍然大，距离小的降维后仍然小。

• 计算高维空间时，(i点-j点的相似度)÷(i点-所有点的相似度之和)
  
• 计算降维后，(i点-j点的相似度)÷(i点-所有点的相似度之和)
  
• 梯度下降法，使$L$L最小，补充：相对熵(又称KL散度)，是描述两个概率分布差异的一种方法。
  
  其中，计算相似度方法：
  高维度计算相似度公式为$S$S，低纬度计算相似度公式$S'$S′
  注意！t-SNE采用不同的相似度计算公式，目的是：当点相似度高时(A点)，从高维→低维时距离仍小；当点相似度低时(B点)，从高维→低维时距离急速变大。