今天, 我想要介绍一个充满不确定性和博弈的问题: 在线学习(Online Learning).
想象一下, 你每天都要决定是否带伞, 或者每天都要决定买哪只股票. 你手头有 \(n\) 个”专家”, 他们每天都会给你一个建议. 有些专家可能很准, 有些可能是瞎猜, 而你并不知道那些专家比较可靠. 我们需要找到一个策略, 每天选择一个专家的建议听从, 并且让我们的选择尽可能正确.
这就是经典的专家问题(The Experts Problem). 今天我们将从最朴素的想法出发, 一步步推导出一个有明确错误率上界的”最佳策略”.
问题描述
让我们把问题形式化.
假设我们有 \(n\) 个专家和 \(T\) 天, 其中\(T\) 未必是已知的.
- 在第 \(t\in [T]\) 天, 每个专家 \(i\in [n]\) 都会给出一个预测.
- 我们需要选择听从其中某一个专家的建议, 第 \(t\) 天选择的专家记为 \(i_{t}\).
- 在每一天结束时, 根据结果, 每个专家 \(i\) 都会产生一个损失 \(f_i^t \in [0, 1]\).
- 对于我们选择了的专家 \(i_t\), 那么你当天的损失就是 \(f_{i_t}^t\).
我们的终极目标是最小化我们的总损失:
\[\sum_{t=1}^{T} f_{i_t}^t\]\[f_{i_{t}}^{t} \in \left\{ 0, 1 \right\}\]为了方便讨论和思考, 这篇博客中我们默认损失是二元的:
评价标准: 遗憾
怎么评价我们做得好不好呢?
想要保证每一天都选到那个当天表现最好的专家显然是不现实的 (当然除非你会算命).
期望总损失 \(\mathcal{F}_{\{\text{total}\}}\le \sum_{t=1}^T \min_{i \in [n]} f_i^t\) 是不现实的.
因此, 我们设定一个相对目标: 在 \(T\) 天结束后, 回头看, 如果我们当初一直死心塌地地跟着某一个表现最好的专家走, 我们的损失会是多少? 我们将我们的损失与这个”最佳专家”的损失之差, 称为遗憾(Regret):
\[R = \left( \sum_{t=1}^{T} f_{i_t}^t \right) - \left( \min_{i \in [n]} \sum_{t=1}^{T} f_i^t \right)\]我们的目标是让 \(R\) 尽可能小. 最好是次线性的, 即当 \(T \to \infty\) 时, 平均每天的遗憾 \(\frac{R}{T} \to 0\).
算法
I: 盲从法
最简单的想法: 我们就死盯着第 1 个专家, 或者任意指定一个专家 \(u\), 每天都听他的.
\[\text{Algorithm}: i_t = 1, \forall t \in [T]\]这个算法怎么样?
很遗憾, 它非常糟糕. 假设我们面对是一个对抗环境. 对手只要每天让你选的那个专家出错(\(f_{i_{t}}^t = 1\)), 而让另一个专家永远正确(\(f_{\text{best}}^t = 0\)).
对抗环境: 想象有一个无所不知的”对手”, 他知道你的算法是怎么运行的, 并且能够每天针对性地设置最坏的损失函数 \(f_i^t\), 专门让你的策略表现最差. 换句话说, 对手总是在挖坑让你跳! 这是一个最恶劣的假设, 但如果我们的算法能在这种情况下都表现不错, 那它在真实世界(运气好一点的场景)肯定也能跑得很好.
那么:
- 我们的损失 = \(T\)
- 最佳专家的损失 = \(0\)
- Regret: \(R = T - 0 = T\).
这意味着我们每天都在犯错, 从来没有学到东西.
II: 少数服从多数
既然听一个人的不行, 那我们听大家的? 策略: 每天统计所有专家的预测, 选择大多数专家支持的那个结果.
这个算法怎么样? 还是很糟糕.
证明: 对手可以构造一种情况, 让那”大多数”专家(\(1, 2, \dots, n-1\))每天都错(\(f_{majority}^t = 1\)), 而总有一小撮人(\(n\))是对的. 结果依然是: \(f_{our}^t = 1\), 而 \(f_{n}^t = 0\)(存在某个专家一直是对的). \(\implies R = T\).
结论: 在对抗环境下, 任何确定性的算法都无法获得亚线性的遗憾. 也就是 \(R\) 总会正比于 \(T\).
III: 随机乱选
既然这帮专家也不一定靠谱, 那我就每天随机选一个专家听他的.
策略: 每天从 \(n\) 个专家中均匀随机选一个.
让我们看看期望损失:
\[\mathbb{E}\left[\sum_{t=1}^{T} f_{i_{t}}^{t}\right] = \sum_{t=1}^T \frac{1}{n} \sum_{i=1}^n f_i^t\]最坏情况下, 最佳专家的损失是 0, 而其他所有专家的损失都是 1. 那么平均下来的损失是 \(\frac{n-1}{n}\).
\[R \le \frac{n-1}{n}T\]虽然引入了随机性, 但这个遗憾值还是与 \(T\) 成正比, 并没有真正进行”学习”.
IV: 谁行听谁的
这是一个很符合直觉的策略: 利用历史记录! 我们记录每个专家过去的表现, 每一天都选择迄今为止损失最小的那个专家.
策略: 选择 \(i_t = \arg\min_i \sum_{\tau=1}^{t-1} f_i^\tau\).
这个算法怎么样呢? 实际上也不太好.
Claim: \(R \le \frac{n-1}{n}T\).
证明: 我们可以构造一个对抗场景. 假设只有 2 个专家 A 和 B.
- Day 1: A 错, B 对 \(\to\) 我们选 B.
- Day 2: B 错, A 对 \(\to\) 我们选 A.
- Day 3: A 错, B 对 \(\to\) 我们选 B. …
这样, 我们选谁, 谁就错(\(f_{our}^t = 1\)), 而我们没选的那个人总是对的.
最终我们的损失是 \(T\), 而最佳专家的损失大概是 \(T/2\). 虽然比全错好一点, 但 Regret 依然是 \(O(T)\) 级别的.
我们能不能做得更好?
V: 乘法权重更新 (Multiplicative Weights Update, MWU)
我们要解决的核心矛盾是: 既要相信表现好的专家(像算法 IV), 又不能完全排除其他专家(像算法 III 那样保留随机性), 同时还要能快速适应变化.
MWU 算法横空出世. 它的核心思想是: 给每个专家赋予一个权重, 如果他犯错了, 就降低他的权重(惩罚他), 然后根据权重比例随机选择专家.
算法流程
- 初始化: 给每个专家 \(i\) 赋予初始权重 \(w_i^1 = 1\).
- 对于每一天 \(t = 1, \dots, T\):
-
选择: 根据权重计算概率分布 \(p^t\), 其中选专家 \(i\) 的概率为:
\[p_i^t = \frac{w_i^t}{\sum_{j=1}^n w_j^t}\] -
更新: 观察当天的损失向量 \(f^t\), 更新每个专家的权重:
\[w_i^{t+1} = w_i^t \cdot (1 - \epsilon f_i^t)\]这里 \(\epsilon \in (0, 1)\) 是一个固定的参数, 类似于学习率.
-
直观理解:
这是一个”指数加权”的过程. 如果专家 \(i\) 错得厉害 (\(f_i^t \approx 1\)), 他的权重就会乘以 \((1-\epsilon)\), 快速衰减. 如果他全对, 权重不变.
理论分析
这个算法到底有多强? 我们有如下定理:
定理: 对于 \(\epsilon \in (0, \frac{1}{2})\), MWU 算法的期望遗憾满足:
\[\mathbb{E}[R] \le \epsilon T + \frac{\ln n}{\epsilon}\]如果 \(T\) 已知, 我们可以取最优的 \(\epsilon = \sqrt{\frac{\ln n}{T}}\), 此时:
\[\mathbb{E}[R] \le 2\sqrt{T \ln n}\]这意味着平均每日遗憾 \(\frac{R}{T} \propto \frac{1}{\sqrt{T}}\), 当 \(T \to \infty\) 时, 遗憾趋近于 \(0\)!
证明过程
为了证明这个定理, 我们需要使用势能函数法. 定义势能函数为所有权重的总和:
\[\Phi^t = \sum_{i=1}^n w_i^t\]Step 1: 寻找 \(\Phi\) 的上界
如果在第 \(t\) 天产生了损失, 总权重 \(\Phi\) 会减小.
\[\begin{align*}\Phi^{t+1} &= \sum_{i=1}^n w_i^{t+1} = \sum_{i=1}^n w_i^t(1 - \epsilon f_i^t) \\ &= \sum_{i=1}^n w_i^t - \epsilon \sum_{i=1}^n w_i^t f_i^t\end{align*}\]注意到 \(p_i^t = \frac{w_i^t}{\Phi^t}\), 所以 \(w_i^t = p_i^t \Phi^t\). 代入上式:
\[\Phi^{t+1} = \Phi^t (1 - \epsilon \sum_{i=1}^n p_i^t f_i^t) = \Phi^t (1 - \epsilon \langle p^t, f^t \rangle)\]其中 \(\langle p^t, f^t \rangle\) 正是我们在第 \(t\) 天的期望损失:
\[\mathbb{E}\left[f_{i_{t}}^{t}\right] = \sum_{i=1}^{n}p_{i}^{t}f_{i}^{t} = \langle p^t, f^t \rangle\]利用高中常用的不等式 \(1 - x \le e^{-x}\), 我们有:
\[\Phi^{t+1} = \Phi^t (1 - \epsilon \langle p^t, f^t \rangle) \le \Phi^t e^{-\epsilon \langle p^t, f^t \rangle}\]递推 \(T\) 次, 得到上界:
\[\Phi^{T+1} \le \Phi^1 \prod_{t=1}^T e^{-\epsilon \langle p^t, f^t \rangle} = n \cdot e^{-\epsilon \sum_{t=1}^T \langle p^t, f^t \rangle}\]Step 2: 寻找 \(\Phi\) 的下界
总权重一定大于等于任何一个单一专家的权重. 假设最佳专家是 \(k\).
\[\Phi^{T+1} \ge w_k^{T+1} = w_{k}^{1} \cdot \prod_{t=1}^T (1 - \epsilon f_k^t) = \prod_{t=1}^T (1 - \epsilon f_k^t)\]利用泰勒展开近似 \(\ln(1-x) \ge -x - x^2 \implies 1 - x \geq \exp(-x - x^{2})\) (\(x < \frac{1}{2}\)), 或者更严格的不等式, 我们可以推导出:
\[\Phi^{T+1} \ge \prod_{t=1}^T \exp(-\epsilon f_k^t - \epsilon^2 (f_k^t)^2) = \exp(-\epsilon \sum_{t=1}^{T} f_k^t - \epsilon^2 \sum_{t=1}^{T} (f_k^t)^2)\]Step 3: 联立求解
结合 Step 1 和 Step 2 的结果:
\[\exp(-\epsilon \sum_{t=1}^{T} f_k^t - \epsilon^2 \sum_{t=1}^{T} (f_k^t)^2) \le \Phi^{T+1} \le n \cdot \exp(-\epsilon \sum_{t=1}^{T} \langle p^t, f^t \rangle)\]两边取自然对数 \(\ln\):
\[-\epsilon \sum_{t=1}^{T} f_k^t - \epsilon^2 \sum_{t=1}^{T} (f_k^t)^2 \le \ln n - \epsilon \sum_{t=1}^{T} \langle p^t, f^t \rangle\]移项整理得到:
\[\epsilon \left( \underbrace{\sum_{t=1}^{T} \langle p^t, f^t \rangle - \sum_{t=1}^{T} f_k^t}_{R} \right) \le \ln n + \epsilon^2 \sum_{t=1}^{T} (f_k^t)^2\]由于 \(f \in [0,1]\), 所以 \((f_k^t)^2 \le f_k^t \le 1\), 粗略放缩 \(\sum_{t=1}^{T} (f_k^t)^2 \le T\). 两边同时除以 \(\epsilon\):
\[R \le \frac{\ln n}{\epsilon} + \epsilon T\]证毕.
写在最后
MWU 算法不仅仅是用来解决专家问题的, 它是一个非常强大的元算法.
- 零和博弈: 你可以用 MWU 来逼近纳什均衡.
- 线性规划: 它可以用来快速求解近似解.
- Adaboost: 著名的集成学习算法 Adaboost 本质上就是 MWU 的一种特殊形式.
除此以外, 现代大模型中, 在线学习也是一个十分重要的问题. 虽然目前大模型在线学习的领域并没有类似 MWU 的算法广为流传, 但是也许我们也能从 MWU 中汲取灵感, 并且对现有的在线学习或 TTS 方法有所创新.
更为重要的是, 我们也许能从传统算法的宝库中汲取灵感, 有的时候力大砖飞地训练方法并不是唯一的解法, 传统算法在深度学习的时代依然是十分重要的.
希望这篇文章能让你有所收获, 有所启发. 欢迎大家私信交流!