计算机科学与探索 ›› 2020, Vol. 14 ›› Issue (7): 1126-1132.DOI: 10.3778/j.issn.1673-9418.1905092

• 学术研究 • 上一篇    下一篇

统一框架下在线核选择的竞争性分析

廖芸,张骁,廖士中   

  1. 天津大学 智能与计算学部,天津 300350
  • 出版日期:2020-07-01 发布日期:2020-08-12

Competitive Analysis of Online Kernel Selection in Unified Framework

LIAO Yun, ZHANG Xiao, LIAO Shizhong   

  1. College of Intelligence and Computing, Tianjin University, Tianjin 300350, China
  • Online:2020-07-01 Published:2020-08-12

摘要:

在线核选择旨在给出在线核学习每回合的最优核,是在线核学习的基础性和关键性问题。在线核选择问题可归约为专家建议框架问题,其中专家集对应候选核集;每回合,根据专家的权重及专家的建议给出预测结果,并更新专家的权重。基于这一归约,在改进已有后悔界的同时,提出期望在线核选择的概念,并应用专家建议框架与度量任务系统的统一框架,给出期望在线核选择问题的后悔界和竞争比,并证明该竞争比在损失拓展情况下是稳定的。最后,给出结合在线核学习方法的竞争比。该项工作全面推广了在线核选择的概念,在统一框架下,不仅可以得到亚线性后悔界,同时也能得到较强的竞争比,为在线核选择研究开辟了新的途径。

关键词: 竞争性分析, 在线核选择, 专家建议框架, 度量任务系统, 统一框架

Abstract:

Online kernel selection aims to find the optimal kernel for online kernel learning at each round. It is one of the fundamental and critical problems of online kernel learning. A problem of online kernel selection can be reduced to a problem of expert advice framework, where the set of experts corresponds to the set of candidate kernels. Predictions are given according to the weights and advices of the set of experts, and the weights are updated at each round. Based on the reduction, while improving the regret bound, this paper proposes the concept of expected online kernel selection. Within the unified framework of expert advice framework and metric task system, this paper presents the regret bounds and competitive ratios of expected online kernel selection, and proves that the competitive ratio is stable in expanded loss ranges. Finally, this paper derives a competitive ratio combined with online kernel learning. The work of investigating online kernel selection within the unified framework guarantees not only a sublinear regret bound, but also a strong competitive ratio, comprehensively generalizing the concept of online kernel selection and paving the way for new online kernel selection research.

Key words: competitive analysis, online kernel selection, expert advice framework, metrical task systems, unified framework