Multi-kernel classification machine with reduced complexity

详细信息    查看全文

• 作者：Zhe Wang^a ; ^b ; ^{wangzhe@ecust.edu.cn" class="auth_mail} ; Changming Zhu^a ; ^{zcm19880301@163.com" class="auth_mail} ; Zengxin Niu^a ; ^{030100874@mail.ecust.edu.cn" class="auth_mail} ; Daqi Gao^a ; ^{gaodaqi@ecust.edu.cn" class="auth_mail} ; Xiang Feng^a ; ^{xfeng@ecust.edu.cn" class="auth_mail}
• 关键词：Multiple kernel learning ; Nyströ ; m approximation ; Reduced computation complexity ; Generalization risk analysis ; Pattern classification
• 刊名：Knowledge-Based Systems
• 出版年：July 2014
• 年：2014
• 卷：65
• 期：Complete
• 页码：83-95
• 全文大小：732 K

文摘

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 Nyström approximation. Firstly, we generate different kernel matrices K_p$K_p$s for given data. Secondly, we apply the Nyström approximation technique into each K_p$K_p$ so as to obtain its corresponding approximation matrix ${\stackrel{\sim }{K}}_p$. Thirdly, we fuse multiple generated ${\stackrel{\sim }{K}}_p$s into the final ensemble matrix $\stackrel{\sim }{G}$ 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 $\stackrel{\sim }{G}$ into KMHKS. In doing so, we propose a multi-kernel classification machine with reduced complexity named Nyström 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³)$O({\mathit{Mn}}^3)$ to O(Mnm²)$O({\mathit{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$K_p$. Meanwhile, NMKMHKS reduces the space complexity of storing the kernel matrices from O(Mn²)$O({\mathit{Mn}}^2)$ to O(n²)$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$K_p$s; and (4) NMKMHKS has a tighter generalization risk bound in terms of the Rademacher complexity analysis.