技术摘要：具有多个正确答案的学习——不同反馈模型下的遗憾界限

1. 问题定义与动机

本研究探讨了具有多个正确答案的学习问题，在这种设定下，单个输入实例 $x$ 对应一个有效的标签集合 $S \subseteq \mathcal{Y}$，而非单一的目标标签。这一表述的动机源于现代任务，如语言生成（提示词有多种可接受的补全方式）、开放式问答、对话生成以及推荐系统。

研究聚焦于在线学习范式，过程在轮次 $t \in [T]$ 中进行。在每一轮中，对手呈现一个实例 $x_t$ 和一个可接受标签集 $S_t$。学习者预测一个标签 $\hat{y}_t$，若 $\hat{y}_t \notin S_t$，则损失为 1。本文在三种不同的反馈模型下分析了该问题：

1. 错误未知（Mistake-unknown）： 学习者仅收到一个有效的标签 $y_t \in S_t$（由对手选择），但不知道自己的预测是否正确。
2. 错误已知（Mistake-known）： 学习者收到一个有效的标签 $y_t \in S_t$，以及一个揭示其预测 $\hat{y}_t$ 是否出错的二元指示器。
3. 集合值（Set-valued）： 学习者被告知整个有效标签集合 $S_t$。

分析涵盖了实现性设定（存在一个假设 $h^* \in \mathcal{H}$ 使得对于所有 $t$，$h^*(x_t) = S_t$）和不可知设定（学习者与 $\mathcal{H}$ 中使累积损失最小的最佳假设进行竞争）。

2. 方法论与组合特征描述

作者引入了新的组合维度，用以刻画在每种反馈模型下多标签假设类 $\mathcal{H}$ 的可学习性。这些维度是通过针对每种模型中可用信息的特定树分片（tree-shattering）论证来定义的。

组合维度

• 集合值 Littlestone 维度 ($LD_{set}$)： 定义在节点标记为 $\mathcal{Y}$ 子集的集合值树上。如果对于每一条预测路径，都存在一个与揭示的集合 $S_t$ 一致但在预测标签上出错的假设，则称该树被分片。
• 错误已知 Littlestone 维度 ($LD_{known}$)： 定义在节点标记为单个标签的多标签树上。分片要求与揭示的单个标签 $y_t$ 一致，且对预测出错。
• 错误未知 Littlestone 维度 ($LD_{unknown}$)： 使用“错误偏移（mistake offset）”函数定义。如果任何路径上的累积错误数加上假设的偏移量超过 $d$，则称该树是 $d$-分片的。这解释了缺乏即时正确性反馈的情况。

算法

对于实现性设定，作者为每种反馈模型提出了标准最优算法（SOA）。这些算法维护一个一致假设的候选空间（version space），并选择使剩余候选空间的最坏情况维度最小化的预测。

• 错误未知 SOA： 维护一个候选空间和一个偏移函数，预测能使最大 $LD_{unknown}$ 的子类最小化的标签。
• 错误已知 SOA： 预测以最小化由潜在错误位（mistake bit）形成的子类的最大 $LD_{known}$。
• 集合值 SOA： 预测以最小化由揭示的集合 $S_t$ 形成的子类的最大 $LD_{set}$。

3. 核心结果

实现性在线学习

本文为任何多标签类 $\mathcal{H}$ 在实现性设定下的最优错误界限提供了完整的刻画：

• 错误未知： 最优错误界限为 $\min(LD_{unknown}(\mathcal{H}), T)$。
• 错误已知： 最优错误界限为 $\min(LD_{known}(\mathcal{H}), T)$。
• 集合值： 最优错误界限为 $\min(LD_{set}(\mathcal{H}), T)$。

这些结果将以往关于有限类的研究推广到了任意（可能是无限的）假设类。作者证明了 $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$，这等价于对于任何实例，所有假设的标签集的交集非空。

不可知在线学习（遗憾界限）

一项重要的贡献是展示了在不可知设定下，遗憾率在不同反馈模型之间存在巨大差异，这与单标签学习中通常为 $\tilde{\Theta}(\sqrt{T})$ 的遗憾率形成对比。

1. 错误未知： 作者表明，即使对于 $LD_{unknown}=1$ 的简单假设类，遗憾也可能随 $T$ 线性增长（$\Omega(T)$）。这意味着，实现性可学习性（由 $LD_{unknown}$ 刻画）并不保证在该反馈模型下的不可知设定中具有亚线性遗憾。
2. 错误已知： 本文建立了一个亚线性遗憾上界 $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$。这是通过将问题归约为带有专家建议的非随机强力 Bandit 问题实现的，其中利用了一组基于 SOA 的专家。
3. 集合值：
   • 对于特定类别（例如示例类 $H_3$），遗憾是常数级的（$O(1)$）。
   • 对于一般类别，遗憾被限制在 $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$。值得注意的是，该界限独立于标签空间的大小 $|\mathcal{Y}|$，使其可以适用于无限标签空间。

批量学习意义

推导出的组合维度和在线界限意味着其对应的批量学习问题的样本复杂度界限。作者提供了第一个关于全集反馈模型下批量学习的已知上界，并改进了现有关于单正确答案情况下从有限类到无限类的界限。

4. 重要性与主张

本文声称提供了对三种不同反馈模型下实现性在线多标签学习的首次完整组合刻画。其主要的理论意义在于实现性与不可知可学习性之间的分离（在错误未知设定下），在这种设定下，标准的 Littlestone 维度无法捕捉到有意义的遗憾界限。

此外，这项工作强调了不可知多标签学习中丰富的结构：

• 反馈模型从根本上改变了可实现的遗憾率（从线性到常数）。
• 集合值反馈模型允许在特定类别上实现常数遗憾，并在一般类别上实现与维度无关的界限，这种现象在单标签学习中并未观察到。
• 结果表明，刻画不可知多标签学习需要超越足以满足实现性可学习性的组合对象。

作者明确指出，其遗憾定义与之前的研究（如 Joshi 等人 [JLB+25] 和 Raman 等人 [RST24]）不同，旨在更好地契合“最小化针对真实可接受标签集的误差”这一底层预测任务，而非仅仅是与包含特定揭示标签的假设进行竞争。