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}|\ge 1$。若总错误数为 $M$，只沿犯错轮连乘可得

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

从而 $M\le \lfloor {\log }_2|\mathcal{H}|\rfloor$。

概念图像 ​

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

边界 ​

若数据不可实现，版本空间可能变空，基本算法没有定义。$\mathcal{H}$ 无穷时，基数的对数也不给信息，此时需要Littlestone 维公理库Littlestone 维Littlestone dimension · online mistake dimension以自适应实例树的路径打散刻画可实现在线学习的最优确定性错误数。等结构量。即使 $\mathcal{H}$ 有限，计算每个 $x_t$ 上的版本空间多数可能是计数难题；信息论错误界不是多项式时间保证。它与批学习的有限类泛化界都出现 $\log |\mathcal{H}|$，但一个控制对抗序列上的错误数，另一个控制 IID 样本外风险。

参考资料

• 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.