流形正則化
機器學習中,流形正則化(Manifold regularization)是一種利用數據集形狀以約束應在數據集上被學習的函數的技術。在很多機器學習問題中,待學習數據不能涵蓋整個輸入空間。例如,人臉識別系統不需要分類所有圖像,只需分類包含人臉的圖像。流形學習技術假定相關數據子集來自流形,是一種具有有用屬性的數學結構;且待學習函數是光滑的,即不同標籤的數據不應靠在一起,即在有大量數據的區域,標籤函數不應快速變化。這樣,流形正則化算法便可利用無標數據,通過推廣的吉洪諾夫正則化推斷哪些區域允許待學習函數快速變化,哪些區域不允許。流形正則化算法可將監督學習算法推廣到半監督學習和轉導,因為當中有無標數據。流形正則化技術已被應用於醫學成像、大地成像與物體識別等領域。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Example_of_unlabeled_data_in_semisupervised_learning.png/250px-Example_of_unlabeled_data_in_semisupervised_learning.png)
流形正則器
編輯動機
編輯流形正則化是正則化的一種。正則化是通過懲罰複雜解,以減少過擬合、確保問題良置的一系列技術。具體說,流形正則化擴展了應用於再生核希爾伯特空間(RKHSs)的吉洪諾夫正則化。在RKHS的標準吉洪諾夫正則化下,學習算法試圖從函數 的假設空間中學習函數f。假設空間是RKHS,就是說與核K相關聯,於是候選函數f都有範數 ,代表候選函數在假設空間中的複雜度。算法會考慮候選函數的範數,以懲罰複雜函數。
形式化:給定一組有標訓練數據 ,其中 ,以及損失函數V。基于吉洪諾夫正則化的學習算法將試圖求解
其中 是超參數,用於控制算法對簡單函數與更能擬合數據的函數的偏好。
流形正則化在標準吉洪諾夫正則化的環境正則項(ambient regularizer)上增加了第二個正則化項——內蘊正則項(intrinsic regularizer)。在流形假設下,數據不是來自整個輸入空間X,而是來自非線性流形 。流形(即內蘊空間)的幾何用於確定正則化範數。[1]
拉普拉斯範數
編輯內蘊正則項 有很多選擇。如流形上的梯度 ,可以衡量目標函數的光滑程度。光滑函數應在輸入數據密集處變化較慢,即梯度 與邊際概率密度(marginal probability density) (隨機選定的數據點落在x處的概率密度)呈負相關。這就為內蘊正則項提供了合適的選擇:
實踐中,由於邊際概率密度 未知,無法直接計算範數,但可根據數據進行估計。
基於圖的拉普拉斯範數
編輯將輸入點間距解釋為圖,圖的拉普拉斯矩陣就可幫助估計邊際分佈。假設輸入數據包括 個有標例子(輸入x與標籤y的點對)、u個無標例子(無對應標籤的輸入)。定義W為圖的邊權重矩陣, 是數據點 間的距離。定義D為對角矩陣,其中 。L是拉普拉斯矩陣 。則,隨着數據點數 增加,L將收斂於拉普拉斯-貝爾特拉米算子 ,其是梯度 的散度。[2][3]則若 是f在數據處的值向量, ,則就可估計內蘊範數:
隨着數據點數 增加, 的經驗定義會收斂到已知 時的定義。[1]
基於圖的方法解正則化問題
編輯用權重 作為環境正則項和內蘊正則項,最終的待解表達式變為
與其他核方法類似, 可能是無限維空間。因此,若正則化表達式無法明確求解,就不可能在整個空間中搜索解;相反,表示定理表明,在選擇範數 的特定條件下,最優解 必須是以每個輸入點為中心的核的線性組合:對某些權重
利用這結果,可在 的可能選擇定義的有限維空間中搜索最優解 。[1]
拉普拉斯範數的泛函方法
編輯圖拉普拉斯之外的想法是利用鄰域估計拉普拉斯量。這種方法類似於局部平均法,但眾所周知處理高維問題時擴展性很差。事實上,圖拉普拉斯函數會受到維數災難影響。[2] 幸運的是,通過更先進的泛函分析,可利用函數的預期光滑性進行估算:由核導數估計拉普拉斯算子的值 ,其中 表示對第一個變量第j個坐標的偏導數。[4] 這第二種方法與無網格法有關,同PDE中的有限差分法形成對比。
應用
編輯選擇適當的損失函數V、假設空間 ,流形正則化可推廣到各種可用吉洪諾夫正則化表達的算法。兩個常用例子是支持向量機和正則化最小二乘法。(正則化最小二乘包括嶺回歸;相關的LASSO、彈性網正則化等算法可被表為支持向量機。[5][6])這些算法的推廣分別稱作拉普拉斯正則化最小二乘(LapRLS)和拉普拉斯支持向量機(LapSVM)。[1]
拉普拉斯正則化最小二乘(LapRLS)
編輯正則化最小二乘(RLS)是一類回歸分析算法:預測輸入x的值 ,目標是使預測值接近數據的真實標籤。RLS的設計目標是在正則化的前提下,最大限度減小預測值與真實標籤之間的均方誤差。嶺回歸是RLS的一種形式,一般來說RLS與結合了核方法的嶺回歸是一樣的。[來源請求]在吉洪諾夫正則化中,損失函數V的均方誤差是RLS問題陳述的結果:
根據表示定理,解可寫作在數據點求值的核的加權和:
解 可得
其中K定義為核矩陣, ,Y是標籤向量。
為流形正則化添加拉普拉斯項,得到拉普拉斯RLS的表達:
再根據流形正則化的表示定理,可知
這就得到了向量 的表達式。令K是上述核矩陣,Y是數據標籤向量,J是 分塊矩陣 :
解是
LapRLS已被用於傳感器網絡、[7] 醫學成像、[8][9] 物體檢測、[10] 光譜學、[11] 文檔分類、[12] 藥物-蛋白質相互作用、[13] 壓縮圖像與視頻等問題。[14]
拉普拉斯支持向量機(LapSVM)
編輯支持向量機(SVMs)是一系列算法,常用於數據分類。直觀說,SVM在類間畫出邊界,使最接近邊界的數據儘量遠離邊界。這可直接表為線性規劃問題,但也等同於帶鉸鏈損失的吉洪諾夫正則化,即 :
將內蘊正則化項加進去,就得到了LapSVM問題的陳述:
同樣,表示定理允許用在數據點得值的核表示解:
將問題重寫為線性規劃問題、求解對偶問題就可得到 。令K是核矩陣、J是分塊矩陣 ,則解可寫作
其中 是對偶問題的解
Q的定義是
LapSVM已被應用於大地成像、[17][18][19] 醫學成像、[20][21][22] 人臉識別、[23] 機器維護、[24] 腦機接口等問題。[25]
局限
編輯另見
編輯參考文獻
編輯- ^ 1.0 1.1 1.2 1.3 1.4 1.5 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.0 2.1 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.
- ^ 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.
- ^ 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].
- ^ Jaggi, Martin. Suykens, Johan; Signoretto, Marco; Argyriou, Andreas , 編. An Equivalence between the Lasso and Support Vector Machines. Chapman and Hall/CRC. 2014.
- ^ 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.
- ^ 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].
- ^ 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.
- ^ 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.
- ^ Pillai, Sudeep. Semi-supervised Object Detector Learning from Minimal Labels (PDF). [2015-12-15].
- ^ 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.
- ^ 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.
- ^ 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 .
- ^ 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].
- ^ 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 .
- ^ 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 .
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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=
被忽略 (幫助) - ^ 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.
- ^ 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.
- ^ 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].
- ^ 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.
- ^ 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].
- ^ Zhu, Xiaojin. Semi-supervised learning literature survey. 2005. CiteSeerX 10.1.1.99.9681 .
- ^ 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].
- ^ 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庫包含線性流形正則化函數。