Fast Cross-Validation for Kernel-Based Algorithms
Fast Cross-Validation for Kernel-Based Algorithms
复制标题
基于内核的算法的快速交叉验证
DOI：
10.1109/tpami.2019.2892371
复制
发表时间：
2020-05-01
影响因子：
23.6
通讯作者：
Wang, Weiping
中科院分区：
文献类型：
--
作者：
Liu, Yong;Liao, Shizhong;Wang, Weiping
交叉验证(CV)是一种广泛采用的选择最优模型的方法。然而，由于需要多次训练，经验交叉验证误差(CVE)的计算具有很高的复杂性。在本文中，我们发展了一种新的CVE逼近理论，并针对基于核的算法提出了一种基于Bouligand影响函数(BIF)的CVE逼近方法。我们首先用泰勒展开式表示BIF和高阶BIF，并通过泰勒展开式近似CV。然后，我们推导出原始CV和近似CV之间的偏差的上界。此外，我们还提供了一种新的计算方法来计算一般分布的BIF，并对样本分布的BIF准则进行了评估，以近似CV。所提出的近似CV只需要在整个数据集上训练一次，并且适用于各种基于核的算法。实验结果表明，所提出的近似CV是合理和有效的。
Cross-validation (CV) is a widely adopted approach for selecting the optimal model. However, the computation of empirical cross-validation error (CVE) has high complexity due to multiple times of learner training. In this paper, we develop a novel approximation theory of CVE and present an approximate approach to CV based on the Bouligand influence function (BIF) for kernel-based algorithms. We first represent the BIF and higher order BIFs in Taylor expansions, and approximate CV via the Taylor expansions. We then derive an upper bound of the discrepancy between the original and approximate CV. Furthermore, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF criterion for sample distribution to approximate CV. The proposed approximate CV requires training on the full data set only once and is suitable for a wide variety of kernel-based algorithms. Experimental results demonstrate that the proposed approximate CV is sound and effective.