Halving 算法 | Codeboy's Blog

形式陈述

Halving 在可实现错误界模型中维护一个有限版本空间，并用多数预测把每次错误转成候选数折半。

设有限二元假设类 $\mathcal H$ 含真实目标。第 $t$ 轮之前的版本空间是

V_t=\{h\in\mathcal H:h(x_s)=y_s\text{ for every }s<t\}.

学习器在当前实例 $x_t$ 上按 $V_t$ 中假设的多数标签预测；看到 $y_t$ 后更新 $V_{t+1}=\{h\in V_t:h(x_t)=y_t\}$ 。平票时可任取一个固定标签。

折半证明

若学习器在第 $t$ 轮犯错，支持其预测标签的假设至少占 $V_t$ 一半，而这些假设全部与真标签冲突并被删除，所以

|V_{t+1}|\le |V_t|/2.

真实目标始终留在版本空间，故 $|V_{T+1}|\ge1$ 。若总错误数为 $M$ ，只沿犯错轮连乘可得

1\le |V_{T+1}|\le |\mathcal H|2^{-M},

从而 $M\le\lfloor\log_2|\mathcal H|\rfloor$ 。

直觉

版本空间在连续错误反馈后由八个候选依次缩为四、二和一 — Halving 的版本空间折半

算法把每次错误变成一比特以上的排除信息：多数一侧被事实证明错误，候选集合至少减半。正确预测轮可能只删除一个候选，也可能不删除任何候选，因此“每轮折半”是错误说法；界只需要每个错误昂贵到足以砍掉半个版本空间。

例子与边界

若数据不可实现，版本空间可能变空，基本算法没有定义。 $\mathcal H$ 无穷时，基数的对数也不给信息，此时需要Littlestone 维等结构量。即使 $\mathcal H$ 有限，计算每个 $x_t$ 上的版本空间多数可能是计数难题；信息论错误界不是多项式时间保证。它与批学习的有限类泛化界都出现 $\log|\mathcal H|$ ，但一个控制对抗序列上的错误数，另一个控制 IID 样本外风险。

推论与应用

若显式保存 $N=|\mathcal H|$ 个候选并逐个求值，每轮至多做 $O(N)$ 次假设求值查询与标签比较，并用 $O(N)$ 个存活标记维护版本空间；假设表示及单次求值的实际成本另计。Littlestone 维则用自适应实例树深度刻画一般可实现在线类的最优确定性错误数。

版本空间多数若不可高效计算，可用 Weighted Majority 等显式专家更新获得相关但不同的保证。噪声序列则需保留有损候选或改用 regret，不能让一次冲突永久删除真规则。

参考资料

Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound, Machine Learning, 1988.
Shai Shalev-Shwartz, Online Learning and Online Convex Optimization, Foundations and Trends in Machine Learning, 2012.

形式陈述 ​

折半证明 ​

反向链接

形式陈述

折半证明