摘要

本周继续学习了降维技术，包括线性方法和非线性方法的应用。线性方法如PCA和LDA虽然广泛应用，但在面对复杂的数据分布时效果有限，因此引入了非线性的流形学习方法，如ISOMAP、LLE和LE。这些方法通过保留数据的局部和全局几何结构，实现了更有效的降维。此外，还学习了概率图模型，涵盖了贝叶斯网、马尔可夫随机场和条件随机场，展示了在推断和计算复杂概率分布时的应用。

Abstract

This week we continued our study of dimensionality reduction techniques, including the application of linear and nonlinear methods. Linear methods such as PCA and LDA, although widely used, have limited effectiveness in the face of complex data distributions, so nonlinear manifold learning methods such as ISOMAP, LLE, and LE have been introduced. These methods achieve more efficient dimensionality reduction by preserving the local and global geometry of the data. In addition, we learned about probabilistic graph models covering Bayesian networks, Markov random fields, and conditional random fields, demonstrating applications in inferring and calculating complex probability distributions.

1.降维的动机

对上一篇MDS和PCA的学习补充。

• 原始观察空间中的样本具有极大的信息冗余。
• 样本的高维数引发分类器设计的”维数灾难“。
• 数据可视化（推荐T-SNE对数据降维）、特征提取、分类与聚类等任务需求。

假设一个64*64像素的图片，如果从像素来考虑会出现很多的特征，但实际上可以通过人脸位置的高低以及左右脸的位置和光线就可以刻画一张图。

1.1 线性方法方法

1.1.1 主成分分析（PCA)

• PCA对于椭球状分布的样本集有很好的效果；学习所得的主方向就是椭球的主轴方向。
• PCA是一种非监督的算法，能找到很好地代表所有样本的方向，但这个方向对于分类未必是最有利的

1.1.2 线性判别分析(LDA)

• 降维目的：寻找最能把两类样本分开的投影直线，投影后两类样本的均值之差与投影样本的总类散度的比值最大。
• 求解方法：经过推导把原问题转化为关于样本集总类内散度矩阵和总类间散度矩阵的广义特征值问题。属于监督学习方法。

两者的不同：pca投影在椭球的主轴上，样本间不好区分，而lda的投影保持内间的散度尽可能大

1.1.3 线性降维方法中的不足

• 真实数据中的有用信息不能由线性特征表示
  比如：如何获取并表示多姿态人脸的姿态信息
  
  又如：如何获取运动视频序列中某个动作的对应帧
  

2.基于流形学习的非线性降维

基于上述线性降维方法中不能处理现实生活中的一些问题，提出了基于流形学习的非线性降维包括保距特征映射（ISOMAP)、局部线性嵌入（LLE)、拉普拉斯特征映射（LE)。
流行学习的目的：

• 流形学习是一种非线性的维数约简方法
• 高维观察数据变化模式本质是由少数几个隐含变量所决定的，如：人脸采样由光线亮度、人与相机的距离、人的头部姿势、人的面部表情等因素决定；
  

以下三种方法是经典的常用的非线性降维方法：

下图是经典分类结构图：

2.1 ISOMAP(Isometric feature mapping)

• 保持全局测地距离
  • 测地距离反映数据在流形上的真实距离差异
• 等距映射
  • 基于线性算法MDS,采用”测地距离“作为数据差异度量
    
    上述的欧式距离计算方法是使得MDS失效的原因。
    下图是ISOMAP在人脸上下以及左右角度的结果图
    
    上图可以看出对于整体而言，其降维后的特征提取效果很不错。
    ISOMAP特点
    前提假设
    • 数据所在的低维流形与欧式空间的一个子集整体等距
    • 该欧式空间的子集是一个凸集

思想核心
- 较近点对之间的测地距离用欧式距离代替
- 较远点之间的测地距离用最短路径来逼近
算法特点
- 适用于学习内部平坦的低维流形
- 不适用于学习有较大内在曲率的流形
- 计算点对间的最短路径比较耗时（O(N^3))

2.2 LLE(locally linear embedding)

前提假设

• 采样数据所在的低维流形在局部是线性的
• 每个采样点均可以利用其近邻样本进行线性重构表示

学习目标

• 低维空间中保持每个领域中的重构权值不变
• 在嵌入映射为局部线性的条件下，最小化重构误差
• 最终形式化为特征值分解问题

LLE实验结果

LLE优缺点总结
优点：

• 算法可以学习任意维的局部线性的低维流形
• 算法归结为稀疏矩阵特征值计算，计算复杂度相对较小
  缺点：
• 算法所学习的流形只能是不闭合的
• 算法要求在流形上是稠密采样的
• 算法对样本中的噪声和领域参数比较敏感

2.3 LE(Laplacian Eigenmap)拉普拉斯算子

• 基本思想：在高维空间中离得很近的投影到低维空间中的象也应该离得很近
• 求解方法：求解图拉普拉斯算子的广义特征值问题。

2.3.1 拉普拉斯关键步骤以及涉及公式

2.3.1.1 构建相似性图

给定数据集{x₁,x₂,…,x_n}，构建一个无向图G=(V,E)，其中每个数据点X_i是图G的一个顶点。为了定义数据点之间的相似性，一般采用K近邻图（选择每个点的k个最近邻作为其相连的顶点）， 𝜖-领域图（将与某个点距离小于阈值𝜖的点连接起来）

2.3.1.2 构造权重矩阵

权重矩阵W描述图中边的权重，常用的权重函数为高斯核函数，即：
$$W_{ij}=\{\begin{array}{ll}\exp \left(-\frac{{\Vert x_i-x_j\Vert }^2}{2{\sigma }^2}\right),& \text{if}{x}_i\text{and}{x}_j\text{are connected},\\ 0,& \text{otherwise}.\end{array}$$
其中，σ 是一个控制相似性尺度的参数。

2.3.1.3 图拉普拉斯矩阵

在有了权重矩阵W之后，计算拉普拉斯矩阵。
有以下几种形式：

• 非标准拉普拉斯矩阵：L = D - W
  其中，D是度矩阵，它是一个对角矩阵，其对角元素是各个节点的度数：
  $$D_{ii}=\sum _j{W}_{ij}$$
• 标准化拉普拉斯矩阵
  $$L_{\mathrm{sym}}=I-D^{-\frac{1}{2}}W{D}^{-\frac{1}{2}}$$

2.3.1.4 拉普拉斯特征问题

拉普拉斯的核心问题是求解以下广义特征值问题: Ly = λDy
其中，y是特征向量，是数据在低维空间中的坐标表示
λ是对应的特征向量
L是图的拉普拉斯矩阵，D是度矩阵
目标：求解最小的特征值对应的特征向量（除了第一个特征值为0的特征向量，因为它是平移不变的），通常保留m个最小非零特征值以及对应的特征向量，形成低维嵌入。

使用拉普拉斯特征映射（Laplacian Eigenmap，LE）对Swiss Roll数据集进行降维

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import SpectralEmbedding# 生成Swiss Roll数据集
n_samples = 1500
X, color = make_swiss_roll(n_samples)# 使用拉普拉斯特征映射（LE）进行降维
embedding = SpectralEmbedding(n_components=2)
X_transformed = embedding.fit_transform(X)# 绘制Swiss Roll原始数据和降维后的数据
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 7))# 原始数据的3D图
ax1 = fig.add_subplot(121, projection='3d')
ax1.scatter(X[:, 0], X[:, 1], X[:, 2], c=color, cmap=plt.cm.Spectral)
ax1.set_title("Original Swiss Roll (3D)")# 降维后的2D数据
ax2.scatter(X_transformed[:, 0], X_transformed[:, 1], c=color, cmap=plt.cm.Spectral)
ax2.set_title("Laplacian Eigenmap (2D)")plt.show()

左边是原始的三维Swiss Roll数据，右边是通过LE方法降维到二维后的结果。LE保留了局部相似性，使原始数据中相邻的点在降维后的低维空间中仍然相邻，适用于非线性流形的数据降维和可视化。

LE优缺点总结
优点：

• 算法是局部非线性方法，于谱图理论有很紧密的联系
• 算法通过求解稀疏矩阵的特征值问题解析地求出整体最优解，效率非常高
• 算法使原始空间中离得很近地点在低维空间也离得很近，可以用于聚类

缺点：

• 同样对算法参数和数据采样密度较敏感
• 不能有效保持流形地全局几何结构

3. 概率图模型

概率模型：描述提供一种描述框架，将描述任务归结为计算变量的概率分布，在概率模型中，利用已知的变量推测未知变量的分布称为”推断“，其核心在于基于可观测的变量推测除未知变量的条件分布

• 生成式：计算联合分布P(Y,R,O)
• 判别式：计算条件分布P(Y,R|O)

其中，Y为关心的变量集合；O为可观测变量集合；R为其他变量集合
直接利用概率求和规则消去变量R的时间和空间复杂度为指数级别O(2^(|Y|+|R|)),需一种优化方法来计算降低时间复杂度。
在概率图模型中，有有向图（贝叶斯网）、无向图（马尔可夫网）

3.1 贝叶斯网（隐马尔可夫模型HMM）

组成

• 状态变量：{y₁,y₂,…,y_n}通常假定是隐藏的，不可被观测的（一般是离散变量）
• 观测变量：{x₁,x₂,…,x_n}表示第i时刻的观测值集合（可以是离散的也可以是连续的）

马尔可夫链：系统下一时刻状态仅由当前状态决定，不依赖于以往的任何状态
联合概率：$$P(x_1,y_1,\dots ,x_n,y_n)=P(y_1)P(x_1\mid y_1)\prod _{i=2}^{n}P(y_i\mid y_{i-1})P(x_i\mid y_i)$$
确定一个HMM需要三组参数

• 状态转移概率：模型在各个状态间转换的概率（矩阵A)
• 输出观测概率：模型根据当前状态获得各个观测值的概率（矩阵B）
• 初试状态概率：模型在初始时刻各个状态出现的概率（Π）

通过指定状态空间Y,观测空间X,和上述三个参数，就可以确定一个隐马尔可夫模型，按如下过程生成观察序列：
1.设置t=1，并根据初始状态Π选择初始状态y₁
2.根据y_t和输出观测概率B选择观测变量取值x_t
3.根据y_t和状态转移矩阵A转移模型状态，即确定y_t+1
4.若t <= n,设置t = t+1，并转到（2）步，否则停止

下面是隐马尔可夫模型的一个例子：

3.2 马尔可夫网

• 马尔可夫随机场是典型的马尔可夫网，著名的无向图模型

分布形式化：

• 使用基于极大团的势函数（因子）----对于图中结点的一个子集，若其中任意两个结点都有边连接，则称该结点子集为一个”团“
• 联合概率分布可以使用极大团定义
• 假设所有极大团构成的集合为C*
  其概率模型为：$$P(\mathbf{x})=\frac{1}{Z^{\ast }}\prod _{Q\in {\mathcal{C}}^{\ast }}{\psi }_Q({\mathbf{x}}_Q)$$
  其中，Z*是规范化因子 ${\sum }_x{\prod }_{Q\in {\mathcal{C}}^{\ast }}{\psi }_Q({\mathbf{x}}_Q)$
  下面是图模型结构的一个例子：
  
  其联合分布概率：
  $$P(\mathbf{x})=\frac{1}{Z}{\psi }_{12}(x_1,x_2){\psi }_{13}(x_1,x_3){\psi }_{24}(x_2,x_4){\psi }_{35}(x_3,x_5){\psi }_{256}(x_2,x_5,x_6)$$

3.2.1 全局马尔可夫性的验证

• 全局马尔可夫性：在给定分离集的条件下，两个变量子集条件独立
  若令A,B,C对应的变量集分别为X_A,X_B,X_C,则X_A和X_B在X_C给定的条件独立，记为$X_A\perp X_B|X_C$
  联合概率：
  $$P(x_A,x_B,x_C)=\frac{1}{Z}{\psi }_{AC}(x_A,x_C){\psi }_{BC}(x_B,x_C)$$
  条件概率：
  $$\begin{array}{rl}P(x_A,x_B\mid x_C)& =\frac{P(x_A,x_B,x_C)}{P(x_C)}=\frac{P(x_A,x_B,x_C)}{{\sum }_{x_A^{\prime }}{\sum }_{x_B^{\prime }}p(x_A^{\prime },x_B^{\prime },x_C)}\\ & =\frac{\frac{1}{Z}{\psi }_{AC}(x_A,x_C){\psi }_{BC}(x_B,x_C)}{{\sum }_{x_A^{\prime }}{\sum }_{x_B^{\prime }}\frac{1}{Z}{\psi }_{AC}(x_A^{\prime },x_C){\psi }_{BC}(x_B^{\prime },x_C)}\\ & =\frac{{\psi }_{AC}(x_A,x_C)}{{\sum }_{x_A^{\prime }}{\psi }_{AC}(x_A^{\prime },x_C)}\cdot \frac{{\psi }_{BC}(x_B,x_C)}{{\sum }_{x_B^{\prime }}{\psi }_{BC}(x_B^{\prime },x_C)}.\end{array}$$
  $$\begin{array}{rl}P(x_A\mid x_C)& =\frac{P(x_A,x_C)}{P(x_C)}=\frac{{\sum }_{x_B^{\prime }}P(x_A,x_B^{\prime },x_C)}{{\sum }_{x_A^{\prime }}{\sum }_{x_B^{\prime }}P(x_A^{\prime },x_B^{\prime },x_C)}\\ & =\frac{{\sum }_{x_B^{\prime }}\frac{1}{Z}{\psi }_{AC}(x_A,x_C){\psi }_{BC}(x_B^{\prime },x_C)}{{\sum }_{x_A^{\prime }}{\sum }_{x_B^{\prime }}\frac{1}{Z}{\psi }_{AC}(x_A^{\prime },x_C){\psi }_{BC}(x_B^{\prime },x_C)}\\ & =\frac{{\psi }_{AC}(x_A,x_C)}{{\sum }_{x_A^{\prime }}{\psi }_{AC}(x_A^{\prime },x_C)}.\end{array}$$
  以上两个公式可以验证得到：
  $$P(x_A,x_B\mid x_C)=P(x_A\mid x_C)P(x_B\mid x_C)$$

3.2.2 马尔可夫随机场中的势函数

作用：用于定量刻画变量集X_Q中变量的相关关系，因为非负函数，且在所偏好的变量取值上有较大的函数值

上图中，假设定量均为二值变量，定义势函数为
$$\begin{array}{rl}{\psi }_{AC}(x_A,x_C)& =\{\begin{array}{ll}1.5,& \text{if }{x}_A=x_C;\\ 0.1,& \text{otherwise},\end{array}\\ {\psi }_{BC}(x_B,x_C)& =\{\begin{array}{ll}0.2,& \text{if }{x}_B=x_C;\\ 1.3,& \text{otherwise},\end{array}\end{array}$$
上述说明模型偏好X_A,X_C有相同的取值，X_B与X_C有不同的取值。令一层含义就是X_A,X_C正相关，X_B,X_C负相关。

• 为满足非负性，指数函数常被用于定义势函数$${\psi }_Q({\mathbf{x}}_Q)=e^{-H_Q({\mathbf{x}}_Q)}$$
  其中，$H_Q({\mathbf{x}}_Q)$是一个定义在变量X_Q的实值函数，常见的形式为：
  $$H_Q({\mathbf{x}}_Q)=\sum _{u,v\in Q,u\ne v}{\alpha }_{uv}{x}_u{x}_v+\sum _{v\in Q}{\beta }_v{x}_v$$

3.3 条件随机场

条件随机场是一种判别式无向图模型，条件随机场对多个变量给定相应观测值后的条件概率进行建模。
马尔可夫随机场（MRF)–生成式 和条件随机场（CRF）–判别式 对比：

4. 总结

降维技术的核心在于减少数据的维度以便于可视化和分析。线性方法，如PCA和LDA，通过在高维空间中寻找最佳的投影方向来实现降维。然而，这些方法在处理实际数据时的效果往往有限，特别是当数据具有复杂的非线性结构时。因此，基于流形学习的非线性降维方法，如ISOMAP、LLE和LE，逐渐成为研究的重点，这些方法通过保持局部或全局的几何结构，使得降维后的数据更能反映其内在特性。此外，概率图模型通过图论和概率论的结合，有效地解决了在复杂系统中变量推断的问题。