基于局部后悔的在线核选择方法综述

在线核选择是在线核学习的关键问题。不同于离线核选择，在线核选择需要在保证亚线性收敛率的同时单趟（one-pass）地进行核选择和假设更新，并且现有在线核选择方法的时间复杂度至少是关于回合数平方的，计算效率较低。针对这些问题，该文提出了一种新的基于局部后悔的在线核选择方法。该方法具有亚线性的后悔界和关于回合数对数的时间复杂度。首先，定义了基于局部后悔的核选择准则（LRC），证明该准则是假设序列期望风险的上界。然后，应用相干性来度量新实例与缓冲区中实例的相关性，并结合蓄水池采样来设计缓冲区实例的添加和删除策略。最后，构造LRC的増量更新方法，并应用在线梯度下降方法来更新假设，实现具有亚线性后悔界的在线核选择和在线核学习的高效算法。实验结果表明，该文所提出的在线核选择方法在保证精度的同时可显著提高核选择的计算效率。