Manifold Learning.
流形学习(Manifold Learning)是一种非线性降维方法。
本文目录：
- Background
- Locally Linear Embedding
- Laplacian Eigenmaps
- t-SNE
1. Background
线性降维是在高维空间中寻找一个子空间，把高维空间的数据线性映射到子空间中。
对于高维空间中的流形(manifold)，线性的距离度量往往失效；如下图，欧式距离并不能代表数据的相关性：
非线性降维是将高维空间中的流形张成一个低维空间，并保留数据的相互关系。
2. Locally Linear Embedding
局部线性嵌入(Locally Linear Embedding,LLE)能够保留数据的局部相近关系。
前提假设：采样数据所在的高维空间是局部线性的,即每个采样点可以用它的近邻点线性表示。
① 对于高维空间中的每个数据点$x^i$，选择与其邻近的k个数据点，常采用$K$近邻或$ε$邻域；
② 将该点看作这些邻近点的线性组合，最小化误差：
\[min \sum_{i}^{} {\mid\mid x^i-\sum_{j}^{} {w_{ij}x^j} \mid\mid_2}\]
③ 学习得到$w_{ij}$后，固定参数；在低维空间寻找一组数据$z^i$，使得低维重构误差最小：
\[min \sum_{i}^{} {\mid\mid z^i-\sum_{j}^{} {w_{ij}z^j} \mid\mid_2}\]
3. Laplacian Eigenmaps
拉普拉斯特征映射(Laplacian Eigenmaps,LE)是一种基于图的方法。
用数据点构建一个图graph，数据间的距离定义为图中的距离;则参数定义如下：
\[w_{i,j}= \begin{cases} similarity, & \text {if connected} \\ 0, & \text{otherwise} \end{cases}\]如果在高维空间中数据点$x^1$和$x^2$的距离很近，则低维空间中$z^1$和$z^2$距离也很近:
\[S = \frac{1}{2}\sum_{i,j}^{} {w_{ij} \mid\mid z^i-z^j \mid\mid_2}\]$S$表示$z$的平滑程度(smooth)。
为防止上述优化陷入$z^i=z^j=0$，对$z$进行一些约束：
如果的维度是$M$，则要求\(span{z^1,z^2,...,z^N} = \Bbb{R}^M\)
即若希望降维到$M$维，则降维结果的维度不会低于$M$维。
4. t-SNE
见t-SNE。
