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

doi:10.16451/j.cnki.issn1003-6059.201802011

Abstract
Figure/Table
References (25)
Related Citation (3)

Download: PDF (805 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

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

Received: 20 August 2017

ZTFLH:

TP 181

Fund:

Supported by National Natural Science Foundation of China(No.61502094,51774090), Natural Science Foundation of Heilong-jiang Province(No.F2015020,F2016002,E2016008), Beijing Postdoctoral Research Foundation(No.2015ZZ-120), Chaoyang District Postdoctoral Foundation of Beijing(No.2014ZZ-14), Cultivation Foundation of Northeast Petroleum University(No.XN2014102), Youth Foundation of School of Computer and Information Technology of Northeast Petroleum University

About author:: WANG Mei, Ph.D., associate professor. Her research interests include machine lear-ning, model selection and kernel methods.LI Dong, master student. Her research interests include machine learning.SUN Yingqi, master student. Her research interests include machine learning.SONG Kaoping(Corresponding author), Ph.D., professor. His research interests include oil and gas field development enginee-ring and knowledge engineering.LIAO Shizhong, Ph.D., professor. His research interests include artificial intelligence and theoretical computer science.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	WANG Mei
	LI Dong
	SUN Yingqi
	SONG Kaoping
	LIAO Shizhong

Cite this article:

WANG Mei,LI Dong,SUN Yingqi等. Regularization Path Algorithm of Multiple Kernel Learning for Solving Large Scale Problems[J]. , 2018, 31(2): 190-196.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.201802011 OR http://manu46.magtech.com.cn/Jweb_prai/EN/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.