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 样本外风险。

推论与应用

折半势函数证明说明每次错误至少提供一 bit 排除信息，从而得到 $\log_2|\mathcal H|$ 上界。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.

形式陈述 ​

折半证明 ​

反向链接

形式陈述

折半证明