An Efficient and Effective Multiple Empirical Kernel Learning Based on Random Projection

Multiple empirical kernel learning (MEKL) is demonstrated to be flexible and effective due to introducing multiple kernels. But MEKL also brings a large computational complexity in practice. Therefore, in this paper we adopt the random projection (RP) technique to efficiently construct the low-dimensional feature space, and then develop an efficient and effective MEKL named MEKLRP so as to decrease the computational complexity. The proposed MEKLRP randomly selects a subset \(S'\) of \(p\) samples from the whole training set \(S\) of \(N\) samples, and then utilizes \(S'\) to generate \(M\) different EKMs \(\{\Phi ^{rpe}_l(x)\}_{l=1}^M\). Following that, MEKLRP maps each sample \(x\) into \(\Phi _l^{rpe}(x), l=1...M\). Finally, MEKLRP applies the transformed samples into our previous MEKL framework. We highlight the contributions of the MEKLRP as follows. Firstly, the MEKLRP adopts the random characteristic of RP and efficiently decreases the computational cost of the matrix eigen-decomposition from \(O(N^3)\) to \(O(p^3)\). Secondly, the MEKLRP maintains an approximate separability at one certain margin and preserves most of the discriminant information in a low-dimensional space since the characteristic of RP in kernel-based learning. Thirdly, the MEKLRP behaves a lower generalization risk bound than its corresponding original learning machine according to the Rademacher complexity.