Weighted Majority 算法

算法 ​

有 $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 \left(1/\beta \right)}{\log (2/(1+\beta ))}.$$

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

一个有结构的例子 ​

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

边界与相邻算法 ​

只有学习器犯错时才能断言至少一半权重被惩罚；正确轮也可能有大量专家犯错，但证明不靠这些轮。专家若输出概率或承担一般 $[0,1]$ 损失，应使用Hedge公理库指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。而不是强行阈值化。随机化 Weighted Majority 按权重抽专家，分析的是期望损失，算法和常数均与这里的确定性加权多数不同。

参考资料

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