求解大规模问题的多核学习正则化路径算法

doi:10.16451/j.cnki.issn1003-6059.201802011

摘要
图/表
参考文献(25)
相关文章 (3)

全文: PDF (805 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

多核学习在处理异构、不规则和分布不平坦的样本数据时表现出良好的灵活性和可解释性.针对精确正则化路径算法难以处理大规模样本数据的问题,文中提出正则化路径近似算法.根据采样分布函数进行抽样,在原始核矩阵的基础上生成近似矩阵,同时在拉格朗日乘子向量中抽取对应行,实现矩阵乘积的近似计算,提高多核学习正则化路径的求解效率.最后分析多核学习正则化路径近似算法的近似误差界和计算复杂性.在标准数据集上的实验验证文中算法的合理性和计算效率.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	王梅
	李董
	孙莺萁
	宋考平
	廖士中

关键词 ：多核学习, 正则化路径, 矩阵近似, Monte Carlo方法

Abstract：

Compared with the traditional single kernel, multiple kernel learning is more flexible and interpretable while dealing with heterogeneous, irregular and non-flat distribution samples. It is difficult for the existing accurate regularization path algorithms to solve large-scale problems. Therefore, an approximation algorithm for multiple kernel learning regularization path is proposed in this paper. The kernel matrix is randomly sampled according to the sampling distribution function, and the corresponding lines are extracted from the Lagrange multiplier vector. Then, the product of matrix is approximately computed, and the efficiency of the regularization path of multiple kernel learning is improved. Finally, the approximation error bounds and the computational complexity of the algorithm are analyzed. Experimental results on standard datasets verify the validity and efficiency of the proposed algorithm.

Key words： Multiple Kernel Learning Regularization Path Matrix Approximation Monte Carlo Method

收稿日期: 2017-08-20

ZTFLH:

TP 181

基金资助:

国家自然科学基金项目(No.61502094,51774090)、黑龙江省科学基金项目(No.F2015020,F2016002,E2016008)、北京市博士后工作经费项目(No.2015ZZ-120)、北京市朝阳区博士后工作经费项目(No.2014ZZ-14)、东北石油大学校培育基金项目(No.XN2014102)、东北石油大学计算机与信息技术学院青年基金项目资助

作者简介: 王梅,博士,副教授,主要研究方向为机器学习、模型选择、核方法.E-mail:wangmei@nepu.edu.cn.李董,硕士研究生,主要研究方向为机器学习.E-mail:lidong_nepu@163.com.孙莺萁,硕士研究生,主要研究方向为机器学习.E-mail:sunyq@nepu.edu.cn.宋考平(通讯作者),博士,教授,主要研究方向为油气田开发工程、知识工程.E-mail:skp2001i@sina.com.廖士中,博士,教授,主要研究方向为人工智能、理论计算机科学.E-mail:szliao@tju.edu.cn.

引用本文:

王梅, 李董, 孙莺萁, 宋考平, 廖士中. 求解大规模问题的多核学习正则化路径算法[J]. 模式识别与人工智能, 2018, 31(2): 190-196. WANG Mei, LI Dong, SUN Yingqi, SONG Kaoping, LIAO Shizhong. Regularization Path Algorithm of Multiple Kernel Learning for Solving Large Scale Problems. , 2018, 31(2): 190-196.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201802011 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2018/V31/I2/190

[1] BOSER B E, GUYON I M, VAPNIK V N. A Training Algorithm for Optimal Margin Classifiers // Proc of the 5th Annual Workshop on Computational Learning Theory. New York, USA: ACM, 1992: 144-152.
[2] LANCKRIET G R G, CRISTIANINI N, BARTLETT P, et al. Learning the Kernel Matrix with Semidefinite Programming. Journal of Machine Learning Research, 2004, 5: 27-72.
[3] BACH F R, LANCKRIET G R G, JORDAN M I. Multiple Kernel Learning, Conic Duality, and the SMO Algorithm // Proc of the 21st International Conference on Machine Learning. New York, USA: ACM, 2004: 41-48.
[4] SONNENBURG S, RATSCH G, SCHAFER C, et al. Large Scale Multiple Kernel Learning. Journal of Machine Learning Research, 2006, 7: 1531-1565.
[5] SONNENBURG S, RATSCH G, SCHAFER C. A General and Efficient Multiple Kernel Learning Algorithm // WEISS Y, SCHLKO-
PF B, PLATT J C, eds. Advances in Neural Information Processing Systems 18. Cambridge, USA: The MIT Press, 2005: 1273-1280.
[6] RAKOTOMAMONJY A, BACH F, CANU S, et al. SimpleMKL. Journal of Machine Learning Research, 2008, 9: 2491-2521.
[7] 孙涛,冯婕.快速随机多核学习分类算法.西安电子科技大学学报(自然科学版), 2016, 43(1): 36-40.
(SUN T, FENG J. Fast Random Multiple Kernel Learning for Cla-ssification. Journal of Xidian University(Natural Science Edition), 2016, 43(1): 36-40.)
[8] LI X D, MAO W J, JIANG W. Multiple-Kernel-Learning-Based Extreme Learning Machine for Classification Design. Neural Computing & Applications, 2016, 27(1): 175-184.
[9] 梁军,李世浩,张飞云,等.基于半无限规划的弹性多核学习算法.华中科技大学学报(自然科学版), 2015, 43(8): 103-106.
(LIANG J, LI S H, ZHANG F Y, et al. Flexible Multi-core Lear-ning Algorithm Based on Semi-Infinite Programming. Journal of Huazhong University of Science & Technology(Natural Science Edition), 2015, 43(8): 103-106.)
[10] 张仁峰,吴小俊,陈素根.通用稀疏多核学习.计算机应用研究, 2016, 33(1): 21-27.
(ZHANG R F, WU X J, CHEN S G. General Sparse Multiple Kernel Learning. Application Research of Computers, 2016, 33(1): 21-27.)
[11] 刘宁,赵建华,冯骜骜.基于主动学习的有监督在线多核学习算法.河南科学, 2016, 34(9): 1423-1427.
(LIU N, ZHAO J H, FENG A A. A Supervised Online Multiple Kernel Learning Algorithm Based on Active Learning. Henan Science, 2016, 34(9): 1423-1427.)
[12] WANG X M, HUANG Z X, DU Y J. Improving Localized Multiple Kernel Learning via Radius-Margin Bound[J/OL]. [2017-07-25]. https://doi.org/10.1156/2017/4579214.
[13] FAN Q, WANG Z, ZHA H Y, et al. MREKLM: A Fast Multiple Empirical Kernel Learning Machine. Pattern Recognition, 2017, 61: 197-209.
[14] BUCAK S, JIN R, JAIN A K. Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition // LAFFERTY J D, WILLIAMS C K I, SHAWE-TAYLOR J, et al., eds. Advances in Neural Information Processing Systems 23. Cambridge, USA: The MIT Press, 2010: 325-333.
[15] EFRON B, HASTIE T, JOHNSTONE I, et al. Least Angle Regression. The Annals of Statistics, 2004, 32(2): 407-499.
[16] HASTIE T, ROSSET S, TIBSHIRANI R, et al. The Entire Regularization Path for the Support Vector Machine. Journal of Machine Learning Research, 2004, 5: 1391-1415.
[17] GUNTER L, ZHU J. Efficient Computation and Model Selection for the Support Vector Regression. Neural Computation, 2007, 19(6): 1633-1655.
[18] ROSSET S, ZHU J. Piecewise Linear Regularized Solution Paths. The Annals of Statistics, 2007, 35(3): 1012-1030.
[19] KARASUYAMA M, TAKEUCHI I. Suboptimal Solution Path Algorithm for Support Vector Machine // Proc of the 28th International Conference on Machine Learning. New York, USA: Omnipress, 2011: 473-480.
[20] ONG C J, SHAO S Y, YANG J B. An Improved Algorithm for the Solution of the Regularization Path of Support Vector Machine. IEEE Transactions on Neural Networks, 2010, 21(3): 451-462.
[21] 廖士中,王梅,赵志辉.正定矩阵支持向量机正则化路径算法.计算机研究与发展, 2013, 50(11): 2253-2261.
(LIAO S Z, WANG M, ZHAO Z H. Regularization Path Algorithm of SVM via Positive Definite Matrix. Journal of Computer Research and Development, 2013, 50(11): 2253-2261.)
[22] DRINEAS P, KANNAN R. Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication // Proc of the 42nd IEEE Symposium on Foundations of Computer Science. Washington, USA: IEEE, 2001: 452-459.
[23] DRINEAS P, KANNAN R, MAHONEY M W. Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM Journal on Computing, 2006, 36(1): 132-157.
[24] ERIKSSON-BIQUE S, SOLBRIG M, STEFANELLI M, et al. Importance Sampling for a Monte Carlo Matrix Multiplication Algorithm, with Application to Information Retrieval. SIAM Journal on Scientific Computing, 2011, 33(4): 1689-1706.
[25] MADRID H, GUERRA V, ROJAS M. Sampling Techniques for Monte Carlo Matrix Multiplication with Applications to Image Processing // Proc of the Mexican Conference on Pattern Recognition. Berlin, Germany: Springer, 2012: 45-54.