基于局部后悔的在线核选择

作     者：张骁 廖士中 ZHANG Xiao;LIAO Shi-Zhong

作者机构：天津大学计算机科学与技术学院天津300350 

基　　金：国家自然科学基金项目(61673293)资助~~ 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2019年第42卷第1期

页      码：61-72页

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

主 题 词：在线学习 核方法 在线核选择 后悔分析 预算保持 

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 0808[工学-自动化类] 0839[0839] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2019.00061

馆 藏 号：203454349...