Weighted Majority 算法 | Codeboy's Blog

形式陈述

算法

在专家建议协议中，有 $N\ge1$ 个每轮给出二元标签的专家，初始权重均为 $1$ 。学习器按两种标签各自获得的总权重作多数预测；真实标签揭示后，把本轮预测错误的专家权重乘 $\beta\in(0,1)$ ，正确专家保持不变。平票规则必须预先固定，因为平票轮也计入学习器错误数。

给定本轮专家预测，直接实现用 $O(N)$ 时间汇总两类权重并完成降权，维护权重需 $O(N)$ 空间；各专家产生预测的计算另计。算法无需预知时域，可在任意有限轮 $T$ 后停止，下面的错误界对每个这样的前缀都成立。

错误界推导

设学习器共犯 $M$ 次错误。每次犯错时，至少一半总权重支持学习器的错误标签，因此更新后

W_{t+1}\le\frac{1+\beta}{2}W_t.

只在犯错轮使用这一收缩，得到

W_{T+1}\le N\left(\frac{1+\beta}{2}\right)^M.

若专家 $i$ 共犯 $m_i$ 次错，它的末权重是 $\beta^{m_i}$ ，故 $W_{T+1}\ge\beta^{m_i}$ 。取对数并整理：

M\le \frac{\log N+m_i\log(1/\beta)}{ \log\bigl(2/(1+\beta)\bigr)}.

对最好的专家取最小值，得到一般序列上的相对错误界。若存在零错专家，右端只剩 $\log N/\log(2/(1+\beta))$ ，这才直接给出可实现错误界模型中的轮数无关保证。它通常含最好专家错误数的乘法系数，不应悄悄改写成 Hedge 的有界损失 regret 常数。

直觉

错误专家权重乘 beta 缩短，保留的权重汇成下一次多数表决 — Weighted Majority 的乘法降权

算法不会在专家第一次犯错时将其删除，而是让错误按乘法持续侵蚀影响力。只要学习器自己预测错，支持错误标签的权重至少占一半，因此总权重必按固定比例收缩；与此同时，任何具体专家仍保留与其累计错误数对应的 $\beta^{m_i}$ 权重。

总权重的上、下界夹住学习器错误次数：上界由学习器每次犯错触发，下界可选择事后最好的专家。比较器无需预先知道，代价是最好专家错误数前出现由 $\beta$ 决定的乘法系数。

例子与边界

一个有结构的例子

设专家分别依据短期、长期与季节性规则预测明日是否上涨。某类市场阶段让短期专家连续犯错，它的权重按 $1,\beta,\beta^2,\ldots$ 衰减；多数预测逐渐转向仍能解释数据的专家。算法不需要预先知道谁最好，也不会因一次错误永久删除专家。

边界与相邻算法

只有学习器犯错时才能断言至少一半权重被惩罚；正确轮也可能有大量专家犯错，但证明不靠这些轮。专家若输出概率或承担一般 $[0,1]$ 损失，应使用Hedge而不是强行阈值化。随机化 Weighted Majority 按权重抽专家，分析的是期望损失，算法和常数均与这里的确定性加权多数不同。

这种确定性多数不保证相对最佳专家的加性无遗憾。令两个专家恒定预测 $0$ 与 $1$ ，平票选 $0$ ，真实标签依次为 $1,0,1,0,\ldots$ 。每两轮后权重重新相等，学习器却每轮都错；在偶数 $T$ 轮后，两个专家各错 $T/2$ 次，学习器错 $T$ 次，遗憾为 $T/2$ 。这与上面的乘性错误界完全相容。

推论与应用

对任意专家 $i$ ，势函数推导给出学习器错误数关于 $m_i$ 与 $\log N$ 的显式界；选择事后错误最少者便得到未知最佳专家的保证。调节 $\beta$ 会在惩罚速度与比较器乘法系数之间折中，不能只让 $\beta$ 趋近零而期待所有项同时改善。

Weighted Majority 是乘法权重方法在二元错误反馈下的离散实例。推广到概率预测或一般有界损失时，Hedge 的指数更新和 regret 分析更自然；推广改变了反馈与目标，也必须改变定理，而不是只把“错误”替换成实数损失。

参考资料

Nick Littlestone, Manfred K. Warmuth, The Weighted Majority Algorithm, Information and Computation, 1994.
Nicolò Cesa-Bianchi, Gábor Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.

形式陈述 ​

算法 ​

错误界推导 ​

一个有结构的例子 ​

边界与相邻算法 ​

反向链接

形式陈述

算法

错误界推导

一个有结构的例子

边界与相邻算法