有趣的算法04--专家问题

今天, 我想要介绍一个充满不确定性和博弈的问题: 在线学习(Online Learning).

想象一下, 你每天都要决定是否带伞, 或者每天都要决定买哪只股票. 你手头有 $n$ 个”专家”, 他们每天都会给你一个建议. 有些专家可能很准, 有些可能是瞎猜, 而你并不知道那些专家比较可靠. 我们需要找到一个策略, 每天选择一个专家的建议听从, 并且让我们的选择尽可能正确.

这就是经典的专家问题(The Experts Problem). 今天我们将从最朴素的想法出发, 一步步推导出一个有明确错误率上界的”最佳策略”.

问题描述

让我们把问题形式化.

假设我们有 $n$ 个专家和 $T$ 天, 其中$T$ 未必是已知的.

1. 在第 $t\in [T]$ 天, 每个专家 $i\in [n]$ 都会给出一个预测.
2. 我们需要选择听从其中某一个专家的建议, 第 $t$ 天选择的专家记为 $i_{t}$.
3. 在每一天结束时, 根据结果, 每个专家 $i$ 都会产生一个损失 $f_i^t \in [0, 1]$.
4. 对于我们选择了的专家 $i_t$, 那么你当天的损失就是 $f_{i_t}^t$.

我们的终极目标是最小化我们的总损失:

为了方便讨论和思考, 这篇博客中我们默认损失是二元的: $f_{i_{t}}^{t} \in \left{ 0, 1 \right}$

评价标准: 遗憾

怎么评价我们做得好不好呢?

想要保证每一天都选到那个当天表现最好的专家显然是不现实的 (当然除非你会算命).

期望总损失 $\mathcal{F}}\le \sum{t=1}^T \min_{i \in [n]} f_i^t$ 是不现实的.

因此, 我们设定一个相对目标: 在 $T$ 天结束后, 回头看, 如果我们当初一直死心塌地地跟着某一个表现最好的专家走, 我们的损失会是多少? 我们将我们的损失与这个”最佳专家”的损失之差, 称为遗憾(Regret):

我们的目标是让 $R$ 尽可能小. 最好是次线性的, 即当 $T \to \infty$ 时, 平均每天的遗憾 $\frac{R}{T} \to 0$.

算法

I: 盲从法

最简单的想法: 我们就死盯着第 1 个专家, 或者任意指定一个专家 $u$, 每天都听他的.

这个算法怎么样?

很遗憾, 它非常糟糕. 假设我们面对是一个对抗环境. 对手只要每天让你选的那个专家出错($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 算法横空出世. 它的核心思想是: 给每个专家赋予一个权重, 如果他犯错了, 就降低他的权重(惩罚他), 然后根据权重比例随机选择专家.

算法流程

1. 初始化: 给每个专家 $i$ 赋予初始权重 $w_i^1 = 1$.
2. 对于每一天 $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$ 天的期望损失:

利用高中常用的不等式 $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 方法有所创新.

更为重要的是, 我们也许能从传统算法的宝库中汲取灵感, 有的时候力大砖飞地训练方法并不是唯一的解法, 传统算法在深度学习的时代依然是十分重要的.

希望这篇文章能让你有所收获, 有所启发. 欢迎大家私信交流!