乘法权重更新方法 | Codeboy's Blog

形式陈述

元方法而非单一算法

乘法权重描述一种可复用结构：维护非负权重，把它们归一化为概率分布，观察反馈后按每个动作的损失成比例缩放。专家建议、某些 boosting、零和博弈和近似线性规划都可出现这套结构，但反馈范围、收益或损失符号不同，对应的更新和常数也不同。

指数损失版本

对 $N$ 个动作，初始 $w_{1,i}=1$ 。第 $t$ 轮使用

p_{t,i}=\frac{w_{t,i}}{W_t},\qquad W_t=\sum_jw_{t,j},

并在观察 $\ell_{t,i}\in[0,1]$ 后更新

w_{t+1,i}=w_{t,i}e^{-\eta\ell_{t,i}}.

这里 $p_t$ 是概率分布， $\eta>0$ 是学习率。若实际只观察被选动作的损失，就不能直接使用全信息版本，必须构造估计量。

势函数推导

从上方看，Hoeffding 引理给

\log\frac{W_{t+1}}{W_t} =\log\mathbb E_{i\sim p_t}e^{-\eta\ell_{t,i}} \le-\eta\langle p_t,\ell_t\rangle+\frac{\eta^2}{8}.

求和后得到 $\log W_{T+1}\le\log N-\eta L_A+\eta^2T/8$ ，其中 $L_A=\sum_t\langle p_t,\ell_t\rangle$ 。从下方看，对任意固定动作 $i$ ，

W_{T+1}\ge w_{T+1,i}=e^{-\eta L_i}.

合并两式便有

L_A-L_i\le\frac{\log N}{\eta}+\frac{\eta T}{8}.

这就是指数势函数的上下夹逼；取 $\eta\asymp\sqrt{\log N/T}$ 得 $O(\sqrt{T\log N})$ regret。

直觉

权重不是在猜“谁永远正确”，而是在记录每个动作至今仍值得保留多少相对可信度。指数更新把累计损失变成乘法衰减，归一化后，高损失动作自然失去概率质量，却不会因一次错误被永久删除。

总权重势函数同时面向两端：上界记录算法每轮平均损失让整体质量缩小多少，下界保留任意固定比较动作剩下的质量。两端夹住同一个 $W_{T+1}$ ，便把算法损失与最佳固定动作连接起来。

例子与边界

线性化版本与范围

有些文献采用 $w_{t+1,i}=w_{t,i}(1-\eta\ell_{t,i})$ 。为保持权重非负，需 $\eta\ell_{t,i}\le1$ ，并用 $e^{-x}$ 与 $1-x$ 的比较重新推导常数。收益版会提升高收益动作而不是惩罚高损失动作。把这些式子拼接，会得到错误的学习率范围。

关系与边界

Hedge是全信息有界损失上的清晰实例；Weighted Majority只在二元错误后乘固定因子。势能法在这里跟踪总权重的指数增长，而算法分析中的摊还势能通常比较单次真实成本，目的不同。不是任何“把数乘到权重上”的启发式都继承上述定理。

推论与应用

当 $T$ 预先已知时，令 $\eta\asymp\sqrt{\log N/T}$ 得到最优量级 $O(\sqrt{T\log N})$ 。未知时域可用 doubling trick 或随时间变化的学习率，但必须重新处理势函数求和；把最终 $T$ 直接代入每一轮并不是在线算法。

同一结构还能把约束满足、零和博弈和 boosting 写成“动作—损失—势函数”的三步循环。迁移时首先确认反馈是全信息还是 bandit、数值是损失还是收益、范围是否有界，再选择合法更新；元方法复用的是证明结构，不是固定常数。

参考资料

Sanjeev Arora, Elad Hazan, Satyen Kale, The Multiplicative Weights Update Method: A Meta-Algorithm and Applications, Theory of Computing, 2012.
Nicolò Cesa-Bianchi, Gábor Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.

形式陈述 ​

元方法而非单一算法 ​

指数损失版本 ​

势函数推导 ​

线性化版本与范围 ​