指数权重与 Hedge | Codeboy's Blog

形式陈述

Hedge 实现全信息专家协议；势函数证明使用Hoeffding 引理对单个有界变量的指数矩估计。每轮将该变量取为按 $p_t$ 选择的损失坐标，故不要求跨轮独立。

第 $t$ 轮开始时，每个专家已有累计损失 $L_{t-1,i}=\sum_{s<t}\ell_{s,i}$ 。给定固定学习率 $\eta>0$ ，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$ 会偷看答案。

直接向量实现每轮更新 $N$ 个累计损失、计算指数及归一化，并作一次混合损失内积，共需 $O(N)$ 次基本运算和 $N$ 次指数求值，保留 $O(N)$ 个数。专家预测与完整损失反馈的生成成本另计；若按 $p_t$ 抽取一位专家，累积概率扫描也需 $O(N)$ 工作。本界按精确实数模型陈述，指数计算、抽样与有限精度实现的位成本需另行核算。

Regret 证明

令 $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}.

当 $N\ge2$ 且已知 $T\ge1$ 时取 $\eta=\sqrt{8\log N/T}$ ，得到 $\sqrt{T\log N/2}$ 。 $N=1$ 时始终使用唯一专家，遗憾为零，无需把 $\eta=0$ 代入含 $1/\eta$ 的界；未知 $T$ 可用递减学习率或 doubling，而不能把优化后的固定 $\eta$ 当作任意时域通用值。

直觉

概率比为 $p_{t,i}/p_{t,j}=\exp[-\eta(L_{t-1,i}-L_{t-1,j})]$ 。算法只看累计损失差，所有专家同时增加相同损失不会改变分布。学习率越大，当前领先者越快获得质量，也越容易因短期波动而大幅改变权重。势函数一端保留最佳专家，另一端记录算法混合损失，夹逼后得到 regret。

例子与边界

概率预测例子

取两专家、 $\eta=\log2$ 。初始分布 $(1/2,1/2)$ ，第一轮损失 $(0,1)$ 后权重变成 $(1,1/2)$ ，下轮分布为 $(2/3,1/3)$ 。第二轮损失若反转为 $(1,0)$ ，算法付出 $2/3$ ，累计损失 $7/6$ ；两专家累计损失均为 $1$ ，遗憾是 $1/6$ ，随后权重重新相等。这说明领先变化会产生调整成本，保证控制的是累计比较而非逐轮胜出。

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

边界与关系

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

推论与应用

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

参考资料

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.

形式陈述 ​

Regret 证明 ​

概率预测例子 ​

边界与关系 ​

反向链接

形式陈述

Regret 证明

概率预测例子

边界与关系