Adaptive Selective Sampling for Online Prediction with Experts

本文提出了一种结构化的分类方法来研究在线预测和主动学习问题，并基于以下六个关键标准进行了分析：
预测任务：包括二元分类、多类别分类、回归等基本形式。
反馈机制：涉及完整信息、标签高效/选择性采样及老虎机反馈等不同场景。
数据/专家的假设：涵盖对抗性、随机性、完美专家及最佳专家等假设条件。
性能指标：以遗憾为衡量标准评估算法表现。
学习范式：聚焦于在线学习框架下的实时更新策略。
算法方法：采用指数加权平均（EWA）等策略进行预测。
本文重点研究了二元序列预测问题，在线学习设置下结合标签高效/选择性采样策略，并提出了一种基于EWA的标签高效预测算法，通过分析不同场景下的表现评估其性能。

基于以下标准, 我们旨在为在线预测任务以及主动学习领域的研究提供一种系统化的方法论框架. 如相关领域的论文及其参考文献中所述, 这一分类体系有助于明确区分不同研究方向. 具体而言，则是对每个标准进行了详细的阐述.

预测任务： 这是指研究旨在解决的基本问题。

• 二元分类： 最基本的形式，在这种情况下我们旨在判断两种可能性中的一个（例如，请问明天是否会下雨？结果只能是'会下雨'或'不会下雨'）。
  • 多类别分类： 更为普遍的情况，在这里我们面对的是三种及以上类别的划分问题（例如，请对电子邮件进行分类：垃圾邮件、促销信息或其他类型的信息）。
  • 回归： 估计一个连续范围而非明确标签（例如，请预测明天气温的具体数值）。

反馈机制： 这描述了学习算法如何接收有关其预测正确性的信息。

• 完整信息： 算法在每次预测后都会获得真实标签（正确答案），从而可以直接进行比较和学习。
• 标签高效/选择性采样： 为了减少获取标签的成本, 算法会策略性地选择何时请求真实标签, 并平衡对反馈的需求与减少反馈成本.
• 老虎机反馈: 算法仅获得一个信号来判断其预测的准确性, 并未获得实际的正确答案. 在这种情况下, 提供有限的信息环境增加了挑战性.

数据/专家的假设： 这些是关于数据性质和提供建议的专家的基本假设。

• 对抗性是指最坏情况下的设定，在这种情况下数据与专家意见均可由对手选定以最大化预测难度。为此设计出的算法必须具备抗干扰能力。
• 随机性则基于假设数据与建议信息来自概率分布模型，在此情况下预测问题往往相对容易解决。
• 完美专家这一简化情形假定至少有一位权威人士始终能提供精确预测结果，在理论分析中非常有用。
• 最佳专家则是一个更为实际的情形设定，在这种情况下某位权威人士通常会比其他人表现出色但在绝对准确性上未必是最完美的选择。

性能指标： 这是衡量预测算法成功的方法。

• 遗憾： 在线学习中的核心指标，用于衡量算法与事后最佳专家相比的表现的差距有多大。遗憾越低越好。
• 风险/错误率： 算法在数据集场景中做出错误预测的发生率。这通常用于评估批量学习算法的性能。
  5.

学习范式： 这是指学习发生的整体框架。

• Online Learning: Data arrives in a sequential manner, with the algorithm dynamically adjusting its predictions.
• Batch Learning/Active Learning: The algorithm can access a pre-stored dataset and self-select representative samples for labeling, aiming to enhance model training efficiency with minimal labeled data.

算法方法： 这描述了算法用于进行预测的特定策略或策略系列。

• 指数加权平均（EWA）： 在广泛应用于机器学习领域中的一种重要方法，在为各个专家赋予权重时考虑了其以往的表现，并在对各个专家建议进行加权平均后进行预测。
• 跟随领先者（FTL）： 这是一种更为简便的策略，在追踪到迄今为止表现最佳的专家并追踪其建议时。
• 其他方法： 除了上述提到的其他方法外，还有多种不同的算法涵盖了基于边际采样、核方法以及假设之间分歧等多种技术。

根据上述6个标准，本文的分类如下：

预测任务：二元分类

本文深入探讨了二元序列预测问题，在每个时间步中变量仅取值于0和1这一特性被明确指出。第2节中对此进行了详细阐述。

*反馈机制：标签高效/选择性采样

本文的主要创新在于构建了一个让预测器在每一个时间步可以选择性地获取真实标签的算法框架。该主动反馈机制旨在减少对反馈获取的经济及资源投入，并持续维持其优异的预测效果。

关于数据/专家的假设：对抗性（重点关注最佳专家场景）

本文主要探讨对抗性设置这一领域，在该框架下所涉及的结果序列与专家建议均具有任意性。然而，在深入分析后发现，在特定条件下存在一个独特的最优专家,其表现始终优于其他所有专家。

性能指标：遗憾

本文采用了"遗憾"这一指标来评估所提出的预测算法的性能核心评价标准。该指标用于衡量算法与事后最佳专家之间的表现差距有多大。5.

学习范式：在线学习

本文主要聚焦于在线学习系统的设计与分析。其中数据以序列形式依次输入，在线学习平台中实现实时数据处理功能。系统采用迭代机制不断优化自身策略，在每次训练周期结束后根据模型输出结果调整参数。

算法方法：指数加权平均（EWA）

本文提出了一种基于指数加权平均（EWA）预测器的新标签高效特性算法设计。该方法通过动态维护每个专家模型的重要程度，并定期根据实际损失值更新模型重要性，在不牺牲预测精度的前提下显著降低了计算开销。同时该算法还采用主动选择性采样策略来优化标签获取的时间点从而实现资源的有效配置