Online Kernel Methods Via Incremental Approximation To Generalization Error

Kernel matrix approximation is the basic method to improve the efficiency of the kernel method.Existing kernel matrix approximation method is independent of the learning,and when it is used in the online kernel method,resolving the approximated kernel matrix at each round results in high computational complexity.In this paper,the approximation method of generalization error is given by the matrix approximation method of generalization error,and the efficient incremental matrix approximation method is given by incremental singular value decomposition.Integrating the generalization error approximation and the incremental matrix approximation,the incremental approximation method of the generalization error for the online kernel method is given.The main results are as follows:1.The matrix approximation for generalization error is proposed.The sampling distribution is constructed by the generalization error,which acts on the approximated kernel matrix,so that the generalization error obtained by the approximated kernel matrix approximates the real generalization error at each round.Therefore,the general method of generalization error approximation is given by the matrix approximation method.2.The incremental Nystrom method is proposed.The method uses truncated incremental singular value decomposition to solve the generalized inverse of the intersection matrix,and reduces the time complexity of inversion from O(m3)to O(mk+k3),where m is the sample size and k is the truncated rank.The restart strategy is used to reset the matrix approximation error caused by truncation.The efficiency of calculating the approximated kernel matrix is improved while the matrix approximation error is guaranteed.3.The upper bound of the matrix approximation error for incremental Nystrom method is given,and the O(T^1/2)regret bound of online kernel method is given based on the approximated generalization error.On the whole,the generalization error approximation problem is reduced to a matrix approximation problem,and the general method of generalization error approximation is given.Furthermore,by the incremental matrix approximation method,an efficient calculation method of online kernel method is given.