流形正则化

机器学习中，流形正则化（Manifold regularization）是一种利用数据集形状以约束应在数据集上被学习的函数的技术。在很多机器学习问题中，待学习数据不能涵盖整个输入空间。例如，人脸识别系统不需要分类所有图像，只需分类包含人脸的图像。流形学习技术假定相关数据子集来自流形，是一种具有有用属性的数学结构；且待学习函数是光滑的，即不同标签的数据不应靠在一起，即在有大量数据的区域，标签函数不应快速变化。这样，流形正则化算法便可利用无标数据，通过推广的吉洪诺夫正则化推断哪些区域允许待学习函数快速变化，哪些区域不允许。流形正则化算法可将监督学习算法推广到半监督学习和转导，因为当中有无标数据。流形正则化技术已被应用于医学成像、大地成像与物体识别等领域。

## 流形正则器

### 动机

流形正则化是正则化的一种。正则化是通过惩罚复杂解，以减少过拟合、确保问题良置的一系列技术。具体说，流形正则化扩展了应用于再生核希尔伯特空间（RKHSs）的吉洪诺夫正则化。在RKHS的标准吉洪诺夫正则化下，学习算法试图从函数$\mathcal{H}$的假设空间中学习函数f。假设空间是RKHS，就是说与核K相关联，于是候选函数f都有范数$\left\| f \right\|_K$，代表候选函数在假设空间中的复杂度。算法会考虑候选函数的范数，以惩罚复杂函数。

形式化：给定一组有标训练数据$(x_1, y_1), \ldots, (x_{\ell}, y_{\ell})$，其中$x_i \in X, y_i \in Y$，以及损失函数V。基于吉洪诺夫正则化的学习算法将试图求解

$$\underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} V(f(x_i), y_i) + \gamma \left\| f \right\|_K^2$$

其中$\gamma$是超参数，用于控制算法对简单函数与更能拟合数据的函数的偏好。

<image>

流形正则化在标准吉洪诺夫正则化的环境正则项（ambient regularizer）上增加了第二个正则化项——内蕴正则项（intrinsic regularizer）。在流形假设下，数据不是来自整个输入空间X，而是来自非线性流形$M\subset X$。流形（即内蕴空间）的几何用于确定正则化范数。

### 拉普拉斯范数

内蕴正则项$\left\| f \right\|_I$有很多选择。如流形上的梯度$\nabla_{M}$，可以衡量目标函数的光滑程度。光滑函数应在输入数据密集处变化较慢，即梯度$\nabla_{M} f(x)$与边际概率密度（marginal probability density）$\mathcal{P}_X(x)$（随机选定的数据点落在x处的概率密度）呈负相关。这就为内蕴正则项提供了合适的选择：

$$\left\| f \right\|_I^2 = \int_{x \in M} \left\| \nabla_{M} f(x) \right\|^2 \, d \mathcal{P}_X(x)$$

实践中，由于边际概率密度$\mathcal{P}_X$未知，无法直接计算范数，但可根据数据进行估计。

### 基于图的拉普拉斯范数

将输入点间距解释为图，图的拉普拉斯矩阵就可帮助估计边际分布。假设输入数据包括$\ell$个有标例子（输入x与标签y的点对）、u个无标例子（无对应标签的输入）。定义W为图的边权重矩阵，$W_{ij}$是数据点$x_i,\ x_j$间的距离。定义D为对角矩阵，其中$D_{ii} = \sum_{j=1}^{\ell + u} W_{ij}$。L是拉普拉斯矩阵$D-W$。则，随着数据点数$\ell + u$增加，L将收敛于拉普拉斯-贝尔特拉米算子$\Delta_{M}$，其是梯度$\nabla_M$的散度。则若$\mathbf{f}$是f在数据处的值向量，$\mathbf{f} = [f(x_1), \ldots, f(x_{l+u})]^{\mathrm{T}}$，则就可估计内蕴范数：

$$\left\| f \right\|_I^2 = \frac{1}{(\ell+u)^2} \mathbf{f}^{\mathrm{T}} L \mathbf{f}$$

随着数据点数$\ell + u$增加，$\left\| f \right\|_I^2$的经验定义会收敛到已知$\mathcal{P}_X$时的定义。

### 基于图的方法解正则化问题

用权重$\gamma_A,\ \gamma_I$作为环境正则项和内蕴正则项，最终的待解表达式变为

$$\underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} V(f(x_i), y_i) + \gamma_A \left\| f \right\|_K^2 + \frac{\gamma_I}{(\ell+u)^2} \mathbf{f}^{\mathrm{T}} L \mathbf{f}$$

与其他核方法类似，$\mathcal{H}$可能是无限维空间。因此，若正则化表达式无法明确求解，就不可能在整个空间中搜索解；相反，表示定理表明，在选择范数$\left\| f \right\|_I$的特定条件下，最优解$f^*$必须是以每个输入点为中心的核的线性组合：对某些权重$\alpha_i$

$$f^*(x) = \sum_{i=1}^{\ell + u} \alpha_i K(x_i, x)$$

利用这结果，可在$\alpha_i$的可能选择定义的有限维空间中搜索最优解$f^*$。

### 拉普拉斯范数的泛函方法

图拉普拉斯之外的想法是利用邻域估计拉普拉斯量。这种方法类似于局部平均法，但众所周知处理高维问题时扩展性很差。事实上，图拉普拉斯函数会受到维数灾难影响。

幸运的是，通过更先进的泛函分析，可利用函数的预期光滑性进行估算：由核导数估计拉普拉斯算子的值$\partial_{1, j} K(x_i, x)$，其中$\partial_{1,j}$表示对第一个变量第j个坐标的偏导数。

这第二种方法与无网格法有关，同PDE中的有限差分法形成对比。

## 应用

选择适当的损失函数V、假设空间$\mathcal{H}$，流形正则化可推广到各种可用吉洪诺夫正则化表达的算法。两个常用例子是支持向量机和正则化最小二乘法。（正则化最小二乘包括岭回归；相关的LASSO、弹性网正则化等算法可被表为支持向量机。）这些算法的推广分别称作拉普拉斯正则化最小二乘（LapRLS）和拉普拉斯支持向量机（LapSVM）。

### 拉普拉斯正则化最小二乘（LapRLS）

正则化最小二乘（RLS）是一类回归分析算法：预测输入x的值$y = f(x)$，目标是使预测值接近数据的真实标签。RLS的设计目标是在正则化的前提下，最大限度减小预测值与真实标签之间的均方误差。岭回归是RLS的一种形式，一般来说RLS与结合了核方法的岭回归是一样的。在吉洪诺夫正则化中，损失函数V的均方误差是RLS问题陈述的结果：

$$f^* = \underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} (f(x_i) - y_i)^2 + \gamma \left\| f \right\|_K^2$$

根据表示定理，解可写作在数据点求值的核的加权和：

$$f^*(x) = \sum_{i=1}^{\ell} \alpha_i^* K(x_i, x)$$

解$\alpha^*$可得

$$\alpha^* = (K + \gamma \ell I)^{-1} Y$$

其中K定义为核矩阵，$K_{ij} = K(x_i, x_j)$，Y是标签向量。

为流形正则化添加拉普拉斯项，得到拉普拉斯RLS的表达：

$$f^* = \underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} (f(x_i) - y_i)^2 + \gamma_A \left\| f \right\|_K^2 + \frac{\gamma_I}{(\ell+u)^2} \mathbf{f}^{\mathrm{T}} L \mathbf{f}$$

再根据流形正则化的表示定理，可知

$$f^*(x) = \sum_{i=1}^{\ell + u} \alpha_i^* K(x_i, x)$$

这就得到了向量$\alpha^*$的表达式。令K是上述核矩阵，Y是数据标签向量，J是$(\ell + u) \times (\ell + u)$分块矩阵$\begin{bmatrix} I_{\ell} & 0 \\ 0 & 0_u \end{bmatrix}$：

$$\alpha^* = \underset{\alpha \in \mathbf{R}^{\ell + u}}{\arg\!\min} \frac{1}{\ell} (Y - J K \alpha)^{\mathrm{T}} (Y - J K \alpha) + \gamma_A \alpha^{\mathrm{T}} K \alpha + \frac{\gamma_I}{(\ell + u)^2} \alpha^{\mathrm{T}} K L K \alpha$$

解是

$\alpha^* = \left( JK + \gamma_A \ell I + \frac{\gamma_I \ell}{(\ell + u)^2} L K \right)^{-1} Y$

LapRLS已被用于传感器网络。

医学成像。

物体检测。

光谱学。

文档分类。

药物-蛋白质相互作用。

压缩图像与视频等问题。

### 拉普拉斯支持向量机（LapSVM）

支持向量机（SVMs）是一系列算法，常用于数据分类。直观说，SVM在类间画出边界，使最接近边界的数据尽量远离边界。这可直接表为线性规划问题，但也等同于带铰链损失的吉洪诺夫正则化，即$V(f(x), y) = \max(0, 1 - yf(x))$：

$f^* = \underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} \max(0, 1 - y_if(x_i)) + \gamma \left\| f \right\|_K^2$

将内蕴正则化项加进去，就得到了LapSVM问题的陈述：

$$f^* = \underset{f \in \mathcal{H}}{\arg\!\min} \frac{1}{\ell} \sum_{i=1}^{\ell} \max(0, 1 - y_if(x_i)) + \gamma_A \left\| f \right\|_K^2 + \frac{\gamma_I}{(\ell+u)^2} \mathbf{f}^{\mathrm{T}} L \mathbf{f}$$

同样，表示定理允许用在数据点得值的核表示解：

$$f^*(x) = \sum_{i=1}^{\ell + u} \alpha_i^* K(x_i, x)$$

将问题重写为线性规划问题、求解对偶问题就可得到$\alpha$。令K是核矩阵、J是分块矩阵$\begin{bmatrix} I_{\ell} & 0 \\ 0 & 0_u \end{bmatrix}$，则解可写作

$$\alpha = \left( 2 \gamma_A I + 2 \frac{\gamma_I}{(\ell + u)^2} L K \right)^{-1} J^{\mathrm{T}} Y \beta^*$$

其中$\beta^*$是对偶问题的解

$$\begin{align} & & \beta^* = \max_{\beta \in \mathbf{R}^{\ell}} & \sum_{i=1}^{\ell} \beta_i - \frac{1}{2} \beta^{\mathrm{T}} Q \beta \\ & \text{subject to} && \sum_{i=1}^{\ell} \beta_i y_i = 0 \\ & && 0 \le \beta_i \le \frac{1}{\ell}\; i = 1, \ldots, \ell \end{align}$$

Q的定义是

$Q = YJK \left( 2 \gamma_A I + 2 \frac{\gamma_I}{(\ell + u)^2} L K \right)^{-1} J^{\mathrm{T}} Y$

LapSVM已被应用于大地成像。

医学成像。

人脸识别。

机器维护。

脑机接口等问题。

## 局限

- 流形正则化假定不同标签的数据不在一起，这样就能从无标数据中提取信息。但这只适用于一部分问题。根据数据结构不同，可能要用不同的半监督或转导学习算法。
- 某些数据集中，函数的内蕴范数$\left\| f \right\|_I$可能非常接近环境范数$\left\| f \right\|_K$：例如，若数据由位于垂直线上的两类组成，则内蕴范数将等于环境范数。这时，即便数据符合光滑分离器假设，无标数据也无法对流形正则化学习到的解产生影响。与联合训练相关的方法已用于解决这一限制。
- 若有大量无标数据，则核矩阵K将变得极大，计算时间可能非常久。这时在线算法与流形的稀疏近似可能有所帮助。

## 外部链接

### 软件

- ManifoldLearn库 与 Primal LapSVM库 在MATLAB中实现了LapRLS和LapSVM。
- C++的 Dlib库 包含线性流形正则化函数。