关键词: 核方法, 循环随机特征映射, 随机假设空间, 线性学习算法, 大规模核方法

Abstract:  Large-scale kernel methods are main machine learning methods for current big data analysis and mining. Kernel methods search the reproducing kernel Hilbert spaces (RKHSs) for some hypotheses to handle original nonlinear learning problems, which requires quadratic time complexity with respect to the size of training set and makes predicting with a kernelized procedure on the entire training set. Hence kernel methods are unpractical for large-scale datasets. To address these issues, this paper proposes an efficient approach to large-scale kernel methods with random hypothesis spaces. Firstly, the circulant random feature mapping is used to construct random hypothesis spaces, called circulant random hypothesis spaces (CRHSs), in loglinear time with respect to the dimensionality of input data. Then, in CRHSs, off-the-shelf linear algorithms are applied to train linear model, which has linear or sublinear time complexity with respect to the size of training set. Theoretically, a uniform generalization error bound in CRHS is presented, which also converges to the generalization error of the optimal hypothesis in RKHS with high probability. The experimental results on benchmark datasets demonstrate that the proposed approach improves the efficiency of non-linear kernel methods significantly while guaranteeing prediction accuracies. The proposed approach is theoretically guaranteed and computationally efficient, exhibiting a state-of-the-art approach to large-scale kernel methods.

Key words: kernel methods, circulant random feature mapping, random hypothesis space, linear learning algorithm, large-scale kernel methods