摘要：在线核回归学习中,每当一个新的样本到来,训练器都需要计算核矩阵的逆矩阵,这个过程的计算复杂度至少为关于回合数的平方级别。提出将素描方法应用于假设的更新,给出一个基于素描方法的更高效的在线核回归算法。首先,将损失函数设定为平方损失,应用Nystr?m近似方法来近似核,并借鉴跟导方法(FTL)的思想,提出一个新的梯度下降算法,称之为FTL-在线核回归(F-OKR);然后,应用素描方法对其加速,使得F-OKR的计算复杂度降低到关于回合数和素描规模线性、关于数据维度平方的级别;最后,设计了一个高效的素描在线核回归算法(SOKR)。与F-OKR相比,SOKR的精度几乎没有影响,而同时在适当的数据集上,运行时间减少16.7%左右。在理论上证得了两种算法的亚线性后悔界。实验结果也验证了所提算法与Nystr?m在线梯度下降算法(NOGD)相比有更好的表现,平均损失降低约64%。

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