专家建议预测

模型 ​

有 $N$ 个专家。第 $t$ 轮学习器选分布 $p_t\in {\mathrm{\Delta }}_N$，损失向量 ${\ell }_t\in [0,1{]}^N$ 随后揭示，学习器承受期望混合损失 $⟨p_t,{\ell }_t⟩$。相对专家 $i$ 的遗憾为

$$\sum _t⟨p_t,{\ell }_t⟩-\sum _t{\ell }_{t,i},$$

目标是同时对所有 $i$ 小。Hedge 以指数方式降低高累计损失专家的权重，可得到 $O(\sqrt{T\log N})$ 遗憾。

天气预测器可被视为专家，但它们不必独立、诚实或各自准确；保证只与最好固定专家比较。学习器的混合可作为随机选专家，也可在凸损失下直接组合预测。

全信息是关键：更新需要看到所有 ${\ell }_{t,i}$。若只观察被选专家损失，就进入bandit公理库多臂赌博机模型Multi-armed bandit · MAB每轮选择一个臂，并且只观察该臂结果的部分反馈序贯决策模型。，必须使用重要性加权估计并付出更大复杂度。批学习有限类的 $\log N$ 来自并集界，本页的 $\log N$ 来自在线势函数，形式相似但证明协议不同。

指数权重的证明图像是维护势

$$W_t=\sum _{i=1}^N\exp (-\eta L_{t,i}),$$

其中 $L_{t,i}$ 是专家累计损失。从下方看，$W_T$ 至少包含最好专家的一项 $e^{-\eta \underset{i}{min}{L}_{T,i}}$；从上方看，利用有界损失的指数矩可把每轮势变化与混合损失联系。比较两端并选 $\eta \asymp \sqrt{\log N/T}$，得到 $O(\sqrt{T\log N})$ 遗憾。

若 $N=1$，算法只能跟随唯一专家，遗憾恒为零但绝对损失可能很大；专家框架从不保证世界可预测。若专家在看见本轮随机选择后才提交建议，也破坏了标准信息次序，不能沿用同一势函数分析。

专家给“建议”和专家直接承担“损失”是等价接口的两步：若专家 $i$ 预测 $z_{t,i}$，环境揭示结果 $y_t$ 后定义 ${\ell }_{t,i}=\ell (z_{t,i},y_t)$；若损失对预测凸，学习器还可输出加权平均 $\sum _i{p}_{t,i}{z}_{t,i}$，其损失不超过混合损失。非凸 0–1 损失下通常需要随机选专家，不能无条件平均标签。

比较器只允许挑一个固定专家。若希望与最好的专家切换序列比较，要限制切换次数并增加相应罚项；否则每轮挑当轮零损失专家的 oracle 过强，标准 Hedge 的 $O(\sqrt{T\log N})$ 结论没有覆盖它。

参考资料

• Littlestone, Warmuth, “The Weighted Majority Algorithm,” 1994.
• Cesa-Bianchi, Lugosi, Prediction, Learning, and Games, Ch. 2.