文献类型：期刊文献

英文题名：Multi-kernel classification machine with reduced complexity

作者：Wang, Zhe[1,2];Zhu, Changming[1];Niu, Zengxin[1];Gao, Daqi[1];Feng, Xiang[1]

机构：[1]E China Univ Sci & Technol, Dept Comp Sci & Engn, Shanghai 200237, Peoples R China;[2]Soochow Univ, Prov Key Lab Comp Informat Proc Technol, Suzhou 215006, Peoples R China

年份：2014

卷号：65

起止页码：83

外文期刊名：KNOWLEDGE-BASED SYSTEMS

收录：;EI(收录号：20142317783175);WOS:【SCI-EXPANDED(收录号:WOS:000337871900009)】；

基金：This work was partially supported by Natural Science Foundations of China under Grant Nos. 61272198 and 21176077, Innovation Program of Shanghai Municipal Education Commission under Grant No. 14ZZ054, the Fundamental Research Funds for the Central Universities, Shanghai Key Laboratory of Intelligent Information Processing of China under Grant No. IIPL-2012-003, Nature Science Foundation of Shanghai Province of China under Grant No. 11ZR1409600, and Shanghai Pujiang Program under Grant No. 12PJ1402200.

语种：英文

外文关键词：Multiple kernel learning; Nystrom approximation; Reduced computation complexity; Generalization risk analysis; Pattern classification

摘要：Multiple Kernel Learning (MKL) has been demonstrated to improve classification performance effectively. But it will cause a large complexity in some large-scale cases. In this paper, we aim to reduce both the time and space complexities of MKL, and thus propose an efficient multi-kernel classification machine based on the Nystrom approximation. Firstly, we generate different kernel matrices K(p)s for given data. Secondly, we apply the Nystrom approximation technique into each K-p so as to obtain its corresponding approximation matrix (K) over tilde(p). Thirdly, we fuse multiple generated (K) over tilde(p)s into the final ensemble matrix (G) over tilde with one certain heuristic rule. Finally, we select the Kernelized Modification of Ho-Kashyap algorithm with Squared approximation of the misclassification errors (KMHKS) as the incorporated paradigm, and meanwhile apply the (G) over tilde into KMHKS. In doing so, we propose a multi-kernel classification machine with reduced complexity named Nystrom approximation matrix with Multiple KMHKSs (NMKMHKS). The experimental results here validate both the effectiveness and efficiency of the proposed NMKMHKS. The contributions of NMKMHKS are that: (1) compared with the existing MKL, NMKMHKS reduces the computational complexity of finding the solution scale from O(Mn-3) to O(Mnm(2)), where M is the number of kernels, n is the number of training samples, and m is the number of the selected columns from K-p. Meanwhile, NMKMHKS reduces the space complexity of storing the kernel matrices from O(Mn-2) to O(n(2)); (2) compared with the original KMHKS, NMKMHKS improves the classification performance but keeps a comparable space complexity; (3) the better recognition of NMKMHKS can be got in a strong correlation between multiple used K(p)s; and (4) NMKMHKS has a tighter generalization risk bound in terms of the Rademacher complexity analysis. (C) 2014 Elsevier B.V. All rights reserved.