高斯核选择的线性性质检测方法*

核选择直接影响核方法的性能.已有高斯核选择方法的计算复杂度为Ω(n²),阻碍大规模核方法的发展.文中提出高斯核选择的线性性质检测方法,不同于传统核选择方法,询问复杂度为O(ln(1/δ)/ ^{2),计算复杂度独立于样本规模.文中首先给出函数 线性水平的定义,证明可使用 线性水平近似度量一个函数与线性函数类之间的距离,并以此为基础提出高斯核选择的线性性质检测准则.然后应用该准则,在随机傅里叶特征空间中有效评价并选择高斯核.理论分析与实验表明,应用性质检测以实现高斯核选择的方法有效可行.}

Linearity Property Testing Approach to Gaussian Kernel Selection

Kernel selection is critical to the performance of kernel methods. The computational complexity of the existing approaches to Gaussian kernel selection is Ω(n²). Therefore, it is an impediment to the development of large-scale kernel methods. To address this issue, a linearity property testing approach to Gaussian kernel selection is proposed. Completely different from the existing approaches, the proposed approach only needs O(ln(1/δ)/ ^{2) query complexity, and its computational complexity is independent of the sample size. Firstly, a concept called linearity level is defined. It is proved that linearity level can approximate the distance between a function and the linear function class, and the linearity property testing criterion for Gaussian kernel selection is presented via the concept of linearity level and the approximate distance. The linearity property testing criterion can be applied in random Fourier feature space to assess and select a suitable Gaussian kernel. Theoretical and experimental results demonstrate that the linearity property testing approach to Gaussian kernel selection is feasible and effective.}