A Linearity Testing Approach To Gaussian Kernel Selection

Kernel selection is critical to kernel learning.Property testing algorithms are "ul-tra"-efficient algorithms that decide whether a given object has a certain property,or is significantly different from any object that has the property.Previous kernel selec-tion criteria have high computation complexity.In this paper,using random feature mapping,the Gaussian kernel selection problem is transformed into linearity testing problem.We assess and evaluate Gaussian kernel parameters via linearity property or linear separability in random feature space.The main results are as follows.· Transform kernel selection problem of kernel binary classification into linear-ity separability testing problem.we propose a novel stochastic online kernel learn algorithm via the random feature mapping and using the instantaneous loss,which has only constant time complexity at each round.And a linearity separability tester is constructed by the efficient leaner.We also prove that the algorithm enjoys a sub-linear regret bound.· Transform kernel selection problem of kernel regression into linearity testing problem.Based on the character of linear function,we propose a novel linearity testing method with query complexity of and computational complexities inde-pendent of the size of the sample.Geometric property and algebraic property of linear function have been studied.As for algebraic property,we first define the concept of ∈ linearity level,prove that it approximates the distance between a function and the linear function class.Using the concept and the approximate distance,we then present a linearity testing criterion for Gaussian kernel selec-tion,which can be used in random Fourier feature space to assess and select a suitable Gaussian kernel.As for geometric property,we consider the property of determinant of linear function,and propose a linearity testing approach toGaussian Kernel selection with efficient determinant estimation.In summary,on the basis of property testing theory,we propose efficient and theoreti-cally sound linearity testing approach to Gaussian kernel selection.