流形正则化

标记数据（黑、白圆圈）稀疏时，流形正则化可利用无标数据（灰色圆圈）将数据分类。无大量标记点时，监督学习算法智能学习非常简单的决策边界（上图）。基于邻点很可能属于同一类的假设，决策边界应避开含大量未标记点的区域。这也就是一种半监督学习。

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

流形正则器

动机

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

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

${\displaystyle {\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}}$

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

嵌入3维空间的2维流形（左）。流形正则化试图学习在展开流形上光滑的函数（右）。

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

拉普拉斯范数

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

${\displaystyle \left\|f\right\|_{I}^{2}=\int _{x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)}$

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

基于图的拉普拉斯范数

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

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

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

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

用权重${\displaystyle \gamma _{A},\ \gamma _{I}}$作为环境正则项和内蕴正则项，最终的待解表达式变为

${\displaystyle {\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} }$

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

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}K(x_{i},x)}$

利用这结果，可在${\displaystyle \alpha _{i}}$的可能选择定义的有限维空间中搜索最优解${\displaystyle f^{*}}$。[1]

拉普拉斯范数的泛函方法

图拉普拉斯之外的想法是利用邻域估计拉普拉斯量。这种方法类似于局部平均法，但众所周知处理高维问题时扩展性很差。事实上，图拉普拉斯函数会受到维数灾难影响。[2] 幸运的是，通过更先进的泛函分析，可利用函数的预期光滑性进行估算：由核导数估计拉普拉斯算子的值${\displaystyle \partial _{1,j}K(x_{i},x)}$，其中${\displaystyle \partial _{1,j}}$表示对第一个变量第j个坐标的偏导数。[4] 这第二种方法与无网格法有关，同PDE中的有限差分法形成对比。

应用

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

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

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

${\displaystyle 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}}$

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

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell }\alpha _{i}^{*}K(x_{i},x)}$

解${\displaystyle \alpha ^{*}}$可得

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

其中K定义为核矩阵，${\displaystyle K_{ij}=K(x_{i},x_{j})}$，Y是标签向量。

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

${\displaystyle 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} }$

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

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

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

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha }$

解是

${\displaystyle \alpha ^{*}=\left(JK+\gamma _{A}\ell I+{\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y}$[1]

LapRLS已被用于传感器网络、[7] 医学成像、[8][9] 物体检测、[10] 光谱学、[11] 文档分类、[12] 药物-蛋白质相互作用、[13] 压缩图像与视频等问题。[14]

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

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

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}}$[15][16]

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

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

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

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

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

${\displaystyle \alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}}$

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

${\displaystyle {\begin{aligned}&&\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\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}}$

Q的定义是

${\displaystyle Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y}$[1]

LapSVM已被应用于大地成像、[17][18][19] 医学成像、[20][21][22] 人脸识别、[23] 机器维护、[24] 脑机接口等问题。[25]

局限

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

另见

• 流形学习
• 流形假设
• 半监督学习
• 转导 (机器学习)
• 谱图论
• 再生核希尔伯特空间
• 吉洪诺夫正则化
• 微分几何

参考文献

1. Belkin, Mikhail; Niyogi, Partha; Sindhwani, Vikas. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. The Journal of Machine Learning Research. 2006, 7: 2399–2434 [2015-12-02]. 
2. Hein, Matthias; Audibert, Jean-Yves; Von Luxburg, Ulrike. From graphs to manifolds–weak and strong pointwise consistency of graph laplacians. Learning theory. Lecture Notes in Computer Science 3559. Springer. 2005: 470–485. CiteSeerX 10.1.1.103.82 . ISBN 978-3-540-26556-6. doi:10.1007/11503415_32. 
3. Belkin, Mikhail; Niyogi, Partha. Towards a theoretical foundation for Laplacian-based manifold methods. Learning theory. Lecture Notes in Computer Science 3559. Springer. 2005: 486–500. CiteSeerX 10.1.1.127.795 . ISBN 978-3-540-26556-6. doi:10.1007/11503415_33. 
4. Cabannes, Vivien; Pillaud-Vivien, Loucas; Bach, Francis; Rudi, Alessandro. Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning. 2021. arXiv:2009.04324  [stat.ML]. 
5. Jaggi, Martin. Suykens, Johan; Signoretto, Marco; Argyriou, Andreas , 编. An Equivalence between the Lasso and Support Vector Machines. Chapman and Hall/CRC. 2014. 
6. Zhou, Quan; Chen, Wenlin; Song, Shiji; Gardner, Jacob; Weinberger, Kilian; Chen, Yixin. A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing. Association for the Advancement of Artificial Intelligence. [2024-06-08]. （原始内容存档于2022-06-25）. 
7. Pan, Jeffrey Junfeng; Yang, Qiang; Chang, Hong; Yeung, Dit-Yan. A manifold regularization approach to calibration reduction for sensor-network based tracking (PDF). Proceedings of the national conference on artificial intelligence 21. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999: 988. 2006 [2015-12-02]. （原始内容存档 (PDF)于2022-07-29）. 
8. Zhang, Daoqiang; Shen, Dinggang. Semi-supervised multimodal classification of Alzheimer's disease. Biomedical Imaging: From Nano to Macro, 2011 IEEE International Symposium on. IEEE: 1628–1631. 2011. doi:10.1109/ISBI.2011.5872715. 
9. Park, Sang Hyun; Gao, Yaozong; Shi, Yinghuan; Shen, Dinggang. Interactive Prostate Segmentation Based on Adaptive Feature Selection and Manifold Regularization. Machine Learning in Medical Imaging. Lecture Notes in Computer Science 8679. Springer. 2014: 264–271. ISBN 978-3-319-10580-2. doi:10.1007/978-3-319-10581-9_33. 
10. Pillai, Sudeep. Semi-supervised Object Detector Learning from Minimal Labels (PDF). [2015-12-15]. （原始内容存档 (PDF)于2017-08-30）. 
11. Wan, Songjing; Wu, Di; Liu, Kangsheng. Semi-Supervised Machine Learning Algorithm in Near Infrared Spectral Calibration: A Case Study on Diesel Fuels. Advanced Science Letters. 2012, 11 (1): 416–419. doi:10.1166/asl.2012.3044. 
12. Wang, Ziqiang; Sun, Xia; Zhang, Lijie; Qian, Xu. Document Classification based on Optimal Laprls. Journal of Software. 2013, 8 (4): 1011–1018. doi:10.4304/jsw.8.4.1011-1018. 
13. Xia, Zheng; Wu, Ling-Yun; Zhou, Xiaobo; Wong, Stephen TC. Semi-supervised drug-protein interaction prediction from heterogeneous biological spaces. BMC Systems Biology. 2010, 4 (Suppl 2): –6. CiteSeerX 10.1.1.349.7173 . PMC 2982693 . PMID 20840733. doi:10.1186/1752-0509-4-S2-S6 . 
14. Cheng, Li; Vishwanathan, S. V. N. Learning to compress images and videos. Proceedings of the 24th international conference on Machine learning. ACM: 161–168. 2007 [2015-12-16]. 
15. Lin, Yi; Wahba, Grace; Zhang, Hao; Lee, Yoonkyung. Statistical properties and adaptive tuning of support vector machines. Machine Learning. 2002, 48 (1–3): 115–136. doi:10.1023/A:1013951620650 . 
16. Wahba, Grace; others. Support vector machines, reproducing kernel Hilbert spaces and the randomized GACV. Advances in Kernel Methods-Support Vector Learning. 1999, 6: 69–87. CiteSeerX 10.1.1.53.2114 . 
17. Kim, Wonkook; Crawford, Melba M. Adaptive classification for hyperspectral image data using manifold regularization kernel machines. IEEE Transactions on Geoscience and Remote Sensing. 2010, 48 (11): 4110–4121. S2CID 29580629. doi:10.1109/TGRS.2010.2076287. 
18. Camps-Valls, Gustavo; Tuia, Devis; Bruzzone, Lorenzo; Atli Benediktsson, Jon. Advances in hyperspectral image classification: Earth monitoring with statistical learning methods. IEEE Signal Processing Magazine. 2014, 31 (1): 45–54. Bibcode:2014ISPM...31...45C. S2CID 11945705. arXiv:1310.5107 . doi:10.1109/msp.2013.2279179. 
19. Gómez-Chova, Luis; Camps-Valls, Gustavo; Muñoz-Marí, Jordi; Calpe, Javier. Semi-supervised cloud screening with Laplacian SVM. Geoscience and Remote Sensing Symposium, 2007. IGARSS 2007. IEEE International. IEEE: 1521–1524. 2007. doi:10.1109/IGARSS.2007.4423098. 
20. Cheng, Bo; Zhang, Daoqiang; Shen, Dinggang. Domain transfer learning for MCI conversion prediction. Medical Image Computing and Computer-Assisted Intervention–MICCAI 2012. Lecture Notes in Computer Science 7510. Springer. 2012: 82–90. ISBN 978-3-642-33414-6. PMC 3761352 . PMID 23285538. doi:10.1007/978-3-642-33415-3_11.  |issue=被忽略 (帮助)
21. Jamieson, Andrew R.; Giger, Maryellen L.; Drukker, Karen; Pesce, Lorenzo L. Enhancement of breast CADx with unlabeled dataa). Medical Physics. 2010, 37 (8): 4155–4172. Bibcode:2010MedPh..37.4155J. PMC 2921421 . PMID 20879576. doi:10.1118/1.3455704. 
22. Wu, Jiang; Diao, Yuan-Bo; Li, Meng-Long; Fang, Ya-Ping; Ma, Dai-Chuan. A semi-supervised learning based method: Laplacian support vector machine used in diabetes disease diagnosis. Interdisciplinary Sciences: Computational Life Sciences. 2009, 1 (2): 151–155. PMID 20640829. S2CID 21860700. doi:10.1007/s12539-009-0016-2. 
23. Wang, Ziqiang; Zhou, Zhiqiang; Sun, Xia; Qian, Xu; Sun, Lijun. Enhanced LapSVM Algorithm for Face Recognition.. International Journal of Advancements in Computing Technology. 2012, 4 (17) [2015-12-16]. 
24. Zhao, Xiukuan; Li, Min; Xu, Jinwu; Song, Gangbing. An effective procedure exploiting unlabeled data to build monitoring system. Expert Systems with Applications. 2011, 38 (8): 10199–10204. doi:10.1016/j.eswa.2011.02.078. 
25. Zhong, Ji-Ying; Lei, Xu; Yao, D. Semi-supervised learning based on manifold in BCI (PDF). Journal of Electronics Science and Technology of China. 2009, 7 (1): 22–26 [2015-12-16]. （原始内容存档 (PDF)于2016-03-04）. 
26. Zhu, Xiaojin. Semi-supervised learning literature survey. 2005. CiteSeerX 10.1.1.99.9681 . 
27. Sindhwani, Vikas; Rosenberg, David S. An RKHS for multi-view learning and manifold co-regularization. Proceedings of the 25th international conference on Machine learning. ACM: 976–983. 2008 [2015-12-02]. 
28. Goldberg, Andrew; Li, Ming; Zhu, Xiaojin. Online Manifold Regularization: A New Learning Setting and Empirical Study. Machine Learning and Knowledge Discovery in Databases. Lecture Notes in Computer Science 5211. 2008: 393–407. ISBN 978-3-540-87478-2. doi:10.1007/978-3-540-87479-9_44. 

外部链接

软件

• ManifoldLearn库 （页面存档备份，存于互联网档案馆）与Primal LapSVM库 （页面存档备份，存于互联网档案馆）在MATLAB中实现了LapRLS和LapSVM。
• C++的Dlib库 （页面存档备份，存于互联网档案馆）包含线性流形正则化函数。