Research On Kernel Approximation And The Application In SVM

Due to the rapid development of Internet technology in recent years, artificial intelligence receives more and more attention. However, because of the explosive growth of data, the scale of problems that machine learning faces is also growing. The computation and storage of large-scale kernel matrix has become a major bottleneck of generation ability of the main kernel methods such as support vector machines (SVM).The core idea of the kernel matrix approximation algorithm is using partial samples to calculate the kernel matrix instead of using all data, which reduces the time and memory required greatly. The simplest and most widely used method is the Nystrom method for approximating. However, the sample points of this method is selected randomly, so a relatively large impact on approximation error is caused inevitably. Thus, researchers have proposed various improved algorithms, such as integrated Nystrom, whose main idea is to increase the sampling points to reduce errors. At the same time, there are some other methods put the idea of clustering into Nystrom method and consider the low-rank structure and cluster structure of the kernel matrix, such as MEKA method.It can be seen that the keys of the kernel matrix approximation method has two aspects. One is how to sample, the other is whether other information of kernel matrix can be used or not. Thus, according to the characteristics of SVM, a worth trying idea is to make the class labels and decision borders information as the reference of the kernel matrix approximation algorithm, in order to improving the efficiency of SVM.This paper describes the ideas and principles of SVM and several existing major kernel matrix approximation methods, and proposes a Nystrom kernel matrix approximation algorithm based on collaborative clustering. Collaborative clustering is algorithm based on k-means clustering, which can find a small scale of sample points which are most likely to become support vectors in the data set. Collaborative clustering method allows sample points chosen by the original Nystrom algorithm to lose little classification information. This can significantly improve SVM’s learning efficiency with the premise of ensuring the same classification accuracy. Although the time complexity of this method will slightly increase with respect to the original Nystrom algorithm, this method also has a higher classification accuracy, which is substantially equivalent to calculate a complete kernel matrix, compared to the original Nystrom method.In addition, the paper also applies MEKA kernel matrix approximation algorithm into SVM, re-clusters samples using class labels, and recalculates the relationship between each corner block. Experiments show that this algorithm can significantly reduce the time complexity of the original MEKA algorithm.