在线模型选择的增量素描方法

Online learning is one of the fundamental methods of machine learning for streaming data mining and sequential prediction. Online model selection aims to study the evaluation and selection of hypothesis spaces in online learning, which is the key to the theoretical research and practical application of online learning. Most of the existing online model selection methods use offline model selection methods to select models on all examples in advance. These methods do not guarantee that the online learning process is in a single pass, have high computational complexities, and lack sound theoretical guarantees. To address these issues, we propose an incremental sketching method for online model selection, which is in a single-pass over the sequence of examples and has the consistency and high efficiency. We constructs the incremental sketches of the example sequence and the hypothesis space, maintaining the necessary information for online model selection efficiently and incrementally. Moreover, we derive the regret bounds of online model selection, design the unbiased online model selection criteria. Finally, combining incremental matrix decomposition and online convex optimization methods, we implement online model selection algorithms with a constant space complexity and a linear or sublinear time complexity with respect to the number of rounds, and further apply the proposed algorithms to online recommendation. This project develops the sketching theory for online model selection, designs the general and efficient online model selection algorithms, and provides an effective way for online machine learning applications for complex data and complex models.

在线学习是流式数据挖掘与序列决策的基本机器学习方法之一。在线模型选择旨在研究在线学习中假设空间的评价与选择，是在线学习理论研究与实际应用的关键。已有的在线模型选择方法大多预先应用离线模型选择方法在全体样本上进行模型选择，不能保证在线学习过程是单趟的，且具有较高的计算复杂度，缺乏可靠的理论保证。针对这些问题，提出在线模型选择的增量素描方法，保证在线模型选择是单趟、一致且高效的。通过构造样本序列和假设空间的增量素描结构，高效且增量地维护在线模型选择所需的必要信息；在此基础上，推导在线模型选择的后悔界，设计无偏的在线模型选择准则；最后，结合增量矩阵分解和在线凸优化，实现具有常数空间复杂度和关于回合数线性或亚线性时间复杂度的在线模型选择算法，将所提出算法应用于在线推荐场景。本项目将发展在线模型选择的素描理论，设计通用且高效的在线模型选择算法，为面向复杂数据和复杂模型的在线机器学习应用提供有效途径。

为了解决在线模型选择的理论保证和计算效率问题，本项目从如下三方面开展研究工作，并且取得了一系列原创性的创新性的前沿研究成果，具体包括：.1) 增量素描假设空间中的在线模型选择遗憾分析与算法设计：项目组聚焦于连续的候选核空间，依据每回合模型选择和模型训练的不同顺序，将连续核空间中的在线核选择分为两类，并分别给出得到最优遗憾界所需的条件，将在线核选择的整体时间复杂度降为关于回合数拟线性级，解决了在线核选择的高计算复杂度问题。实验结果验证了理论结果的正确性和所提出算法的高效性。所提出的遗憾分析框架为在线模型选择问题提出了新的理论保证和解决方案。.2) 不同约束下的高效在线选择模型理论与算法：用户的延迟反馈问题会使得在线模型选择算法收集到的历史数据中存在标签缺失或标签错误的情形，导致所选择的模型存在偏差，对在线模型选择效果造成负面影响，项目组提出了一种可自动修正环境反馈的反事实批量化赌博机算法（CBDF），对于延迟反馈，CBDF在序列决策中的每一幕中，应用反事实采样方法修正环境反馈，生成修正后的奖励值，并应用批量化赌博机策略实现在线模型选择；在在线模型选择应用场景中，在线算法的公平性变得越来越重要，项目组提出了一种名为 P-MMF 的在线学习模型来解决这个问题，P-MMF 制定公平推荐作为资源分配问题，以达到在线学习的最大最小公平性。.3) 面向偏差数据的在线推荐应用：现阶段在线推荐模型往往基于用户交互数据进行训练，用户交互数据是从用户和系统的交互过程中产生的，是以用户为中心的。但是也正是因为数据是从交互中产生的，用户的点击行为往往会受到其他因素的干扰。为了解决这一问题，项目组针对不同偏差利用因果推断技术帮助在线推荐算法进行纠偏。.围绕上述研究内容，本项目共计发表文章6篇 (全部为CCF A类论文)，获国内专利授权1个、申请国内专利3个。