Weighted Majority 算法 | Codeboy's Blog

形式陈述

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

设学习器共犯 $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)}.

对最好的专家取最小值便得到经典mistake bound。它通常含最好专家错误数的乘法系数，不应悄悄改写成 Hedge 的有界损失 regret 常数。

直觉

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

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

例子与边界

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

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

推论与应用

对任意专家 $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.