指数权重与 Hedge | Codeboy's Blog

形式陈述

Hedge 实现全信息专家协议；势函数证明以指数矩控制累计损失，并在比较 log-sum-exp 时使用凸性与 Jensen 型不等式。

第 $t$ 轮开始时，每个专家已有累计损失 $L_{t-1,i}=\sum_{s<t}\ell_{s,i}$ 。Hedge 取

p_{t,i}=\frac{e^{-\eta L_{t-1,i}}}{\sum_je^{-\eta L_{t-1,j}}},

随后承受混合损失 $\widehat\ell_t=\sum_ip_{t,i}\ell_{t,i}$ ，并观察完整向量 $\ell_t\in[0,1]^N$ 。分布只使用过去损失；把当前未知 $\ell_t$ 放入 $p_t$ 会偷看答案。

令 $W_t=\sum_i e^{-\eta L_{t-1,i}}$ 。由 $[0,1]$ 变量的 Hoeffding lemma，

\log\frac{W_{t+1}}{W_t} =\log\sum_ip_{t,i}e^{-\eta\ell_{t,i}} \le-\eta\widehat\ell_t+\frac{\eta^2}{8}.

求和给 $\log W_{T+1}\le\log N-\eta\sum_t\widehat\ell_t+\eta^2T/8$ 。另一方面，对最佳专家 $i^*$ ， $\log W_{T+1}\ge-\eta L_{T,i^*}$ 。因此

\operatorname{Reg}_T =\sum_t\widehat\ell_t-\min_iL_{T,i} \le\frac{\log N}{\eta}+\frac{\eta T}{8}.

知道时域 $T$ 时取 $\eta=\sqrt{8\log N/T}$ ，得到 $\sqrt{T\log N/2}$ ；未知 $T$ 可用递减学习率或 doubling，而不能把优化后的固定 $\eta$ 当作任意时域通用值。

直觉

指数权重让累计损失差转成权重比：持续领先的专家会指数级获得质量，短期偶然失误却不会把任何候选永久删除。势函数一端保留最佳专家，另一端记录算法混合损失，夹逼后得到 regret。

例子与边界

多个天气模型各自给出明日降雨概率。只要采用一个共同的有界评分损失，Hedge 会根据累计表现形成混合分布，不必永久选定单一模型。若使用 log loss，专家报出零概率而事件发生会造成无穷损失；必须截断概率或使用专门的 mixability 分析，标准 $[0,1]$ 证明不能直接套用。

Hedge 需要全损失反馈。只观察所选臂时，需重要性加权估计，方差项也会改变。Weighted Majority按二元错误乘固定因子并作多数表决；本页处理一般有界损失和混合损失。MWU则抽象这类更新供其他问题复用。

推论与应用

把负熵作为 FTRL 正则器可重新导出同一指数权重更新，说明 Hedge 是在线凸优化几何的一种特例。二阶专家界则用实际相对损失平方和替换最坏时域，在容易序列上给出更敏感的保证。

若只见所选专家损失，重要性加权把隐藏坐标恢复成无偏估计，但会引入动作数和方差代价；若损失具有 mixability，则还可能获得快于一般 $\sqrt T$ 的专门界。

参考资料

Yoav Freund and Robert E. Schapire, “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting,” Journal of Computer and System Sciences 55(1), 1997, pp. 119–139.
Nicolò Cesa-Bianchi, Gábor Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.