COMP5270 Week 12 总结：Learning from Experts（题解 + 知识点）

Posted on Edited on In , Word count in article: 4.2k Reading time ≈ 15 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 12 - Learning from Experts, Week 12 - Tutorial 12 (Solutions)

Part 1: Tutorial 12 详细题解

Warm-up

Problem 1: 画 Theorem 61 / 62 中 的 bound

题目: 对不同 和 ，画 Theorem 61 的 bound 随 的变化；Theorem 62 同理。

题解:

这题主要是数值探索，核心是理解两个 bound 如何依赖 。

Theorem 61 deterministic MWU：

其中对数底数不影响形状，只影响常数。

Theorem 62 randomized MWU：

观察：

  • 当 ，错误专家被惩罚很重，适合 或很小；
  • 当 ，惩罚很轻，更稳健，适合 大的情况；
  • 但 时分母变小，会放大 项。

对 ：

若 ，bound 基本由 项决定，较小 更接近 halving。

若 ， 项主导，需要 更接近 1，避免对偶尔犯错的好专家惩罚过重。

本题用到的知识点:

  1. MWU penalty parameter tradeoff。
  2. 小：快速淘汰，但不稳健。
  3. 大：稳健，但 additive 项变差。
  4. Deterministic 与 randomized MWU bound 形式不同。

Problem 2: 已知 和 时如何选 ?

题目: 假设预先知道 和 的上界，MWU / Randomised MWU 中如何设置 ？

题解:

精确最优可以对 bound 关于 求导，或者数值最小化。

考试/推导中常用近似：平衡 numerator 中的两项。

Deterministic MWU numerator：

如果 很大，不希望 太大；如果 很小，可以用较小 。

一个合理选择是令：

即：

所以：

当 很大时：

Randomised MWU 的分子同样是：

也可用同样的平衡思路。不过由于分母是 ，更精细选择会得到常见 regret 形式：

对应：

量级的 regret。

本题用到的知识点:

  1. MWU bound 中有 项和 项。
  2. 参数选择常通过 balance terms。
  3. 是分析小惩罚 regime 的常用代换。

Problem 3: 证明 deterministic experts factor 2 下界

题目: 证明 Fact 57.3：当 ，一个专家永远预测 0，另一个永远预测 1。对任意 deterministic algorithm，存在真实序列使其犯 次错，而 best expert 至多犯 次错。

题解:

设两个专家：

  • Expert 0：每轮预测 0；
  • Expert 1：每轮预测 1。

任意 deterministic algorithm 在第 轮看到过去和两个专家建议后，会给出确定预测：

adversary 令真实值为相反：

这样算法每一轮都错，所以：

现在看两个专家。设真实序列中 0 的位置集合为 ，1 的位置集合为 。两个集合划分 ：

Expert 0 在真实值为 1 时犯错，错误数 ；Expert 1 在真实值为 0 时犯错，错误数 。

best expert 错误数：

因此：

这说明 deterministic algorithm 无法保证比 factor 2 更好。

本题用到的知识点:

  1. Adversarial sequence 根据 deterministic prediction 反着设。
  2. Best expert in hindsight。
  3. Deterministic lower bound factor 2。

Problem Solving

Problem 4: 已知 时改进 MWU bound

题目: 若提前知道 ，证明可修改 MWU 得到：

题解:

使用 Theorem 61：

令：

其中 小。

a) 若

直接取 ，Theorem 60 给：

而目标右边：

也至少是 ，所以成立。

b) 若

用近似：

以及：

更精细地，课程 solution 使用：

于是：

取：

得到：

即：

加上小 情形的 ，得到：

本题用到的知识点:

  1. MWU general bound。
  2. 令 做 Taylor expansion。
  3. 平衡 与 。
  4. 小 单独处理。

Problem 5: 每个时间区间都和该区间 best expert 比较

题目: 修改 MWU，希望对任意 chunk 都有：

算法只在某个犯错专家当前权重至少为平均权重的 时才 penalise。

题解:

a) 算法

维护 weights ，初始都为 1。每轮：

  1. 接收专家预测 ；
  2. 按 weighted majority 输出预测；
  3. 观察真值 ；
  4. 对每个犯错专家 ：
    • 若：

则：

  • 否则不再继续 penalise 它。

这里：

b-c) 一次 algorithm mistake 后总权重下降

固定一个 chunk 中某个算法犯错的时刻 。

令：

  • ：犯错专家总权重；
  • ：没犯错专家总权重；
  • ：犯错但权重低于 、因此不被 penalise 的专家总权重。

因为算法按 weighted majority 预测且预测错了，说明犯错专家权重至少一半：

低权重犯错专家总权重最多：

更新后：

等价写作：

用：

得到：

d) chunk 开始时任意专家权重下界

设 chunk 从 开始。任意专家 在 的权重满足：

原因：若它之前被 penalise，最后一次被 penalise 前权重至少为当时平均的 ，而总权重只会下降，所以到 仍有上述下界；若从未 penalise，则权重为 1，更不小。

e) chunk 结束时总权重下界

设该 chunk 上 best expert 是 ，它犯错：

次。它在 chunk 内最多被乘 这么多次，所以：

因此：

f) 结论

若算法在 chunk 中犯错 次，则由每次犯错权重下降：

结合下界：

消去 并取 log，可得：

其中 是固定常数，例如 。

本题用到的知识点:

  1. MWU potential argument。
  2. Fixed-share / sleeping-style intuition：防止老专家权重过低。
  3. 对任意 interval 做 regret bound。
  4. 上下界夹住总权重。

Advanced

Problem 6: 第 个专家最多犯 次错时的 MWU bound

题目: 有 个专家，第 个专家最多犯 次错。对 deterministic MWU 和 randomized MWU 分别给出 bound。

题解:

因为第 个专家最多犯 次错，所以最终它的权重至少：

所有专家总权重下界：

a) Deterministic MWU

若算法共犯 次错，每次错时 weighted majority 错，和讲义中分析一样，总权重最多乘：

所以：

结合上下界：

取 log 并整理：

Extra close brace or missing open brace \boxed{ C(T) \le \frac{\log\left(\frac{n(1-\beta)}{\beta(1-\beta^n)}\right)} \log\left(\frac{2}{1+\beta}\right)} }

这比只看 best expert 的 bound 更利用了“所有专家都有不同程度好坏”的结构。

b) Randomised MWU

令 是第 轮错误专家的权重比例。Randomised MWU 的期望错误数：

每轮权重变化：

因此：

取 log，用 ：

又有：

所以：

本题用到的知识点:

  1. MWU potential: total weight。
  2. 不只用 best expert，而是把所有专家最终权重下界相加。
  3. Deterministic MWU 每次 mistake 权重乘 。
  4. Randomised MWU 用 和期望线性性。

Part 2: Week 12 讲义知识点

0. 基础版导读：Learning from Experts 在学什么?

Week 12 的主题是 Learning from Experts。这是 online learning 的一个基本模型：

有很多 experts 每轮给建议，算法不知道哪个 expert 可靠，要一边做决定一边学习。

和前面分布学习不同，这里没有固定训练集，也不假设数据来自某个好分布。每一轮结果可能是 adversarial 的。目标不是“完全预测正确”，而是和最好的 expert 比，不要差太多。

基本流程

有 个 experts，进行 轮。每一轮：

  1. 每个 expert 给一个 prediction 或 action。
  2. 算法根据 experts 的建议做自己的 prediction。
  3. 真实结果揭晓。
  4. 算法和 experts 都产生 loss 或 mistake。
  5. 算法更新对 experts 的信任。

一个 expert 的总 loss 记为 ，最优 expert 的 loss 是：

算法自己的 loss 记为 或 。我们希望证明：

接近的表达式

为什么不能保证比所有 expert 都好?

如果没有任何假设，adversary 可以让算法非常难受。例如两个 experts 每轮给相反建议，算法选哪边，adversary 就把真实答案设成另一边。这说明 deterministic algorithm 在最坏情况下无法保证每轮都接近正确。

所以我们比较的是：

事后看来最好的那个 expert。

这叫 regret analysis。regret 大致是：

Consistent Expert 和 Halving

如果假设存在一个从不犯错的 expert，最简单算法是维护所有还没犯错的 experts。

Consistent Expert:

  • 每轮选一个目前还 consistent 的 expert。
  • 如果它犯错，就删除它。
  • 因为每次算法犯错时，至少删除当前选的 expert。
  • 最多犯 次错。

Halving algorithm 更聪明：

  • 每轮让所有 remaining experts 投票。
  • 算法采用多数意见。
  • 如果算法犯错，说明多数 remaining experts 都犯错。
  • 因此 remaining experts 数量至少减半。

所以最多犯：

次错。

MWU 的核心直觉

Multiplicative Weights Update (MWU) 不直接删除犯错 expert，而是降低其权重。

每个 expert 有权重 。初始 。每轮算法根据权重决定听谁的；expert 犯错或有 loss 后，把它的权重乘上一个因子：

如果 expert 累计犯错 次，那么它的权重大约是：

犯错越多，权重越小；但不会像 halving 那样一次删除。这让算法可以处理“没有完美 expert”的情况。

potential function 证明怎么读?

MWU 分析通常看总权重：

证明有两边：

上界：如果算法这一轮犯错，说明被算法支持的一侧权重大。犯错后这些权重会被乘 ，所以总权重下降一个可控比例。算法犯错越多，总权重越小。

下界：最好的 expert 权重永远是总权重的一部分。如果它犯了 次错，那么：

把总权重的上界和下界夹起来，就能推出算法 mistakes 和 的关系。

这叫 potential method，因为 是一个用来分析过程的势能函数。

deterministic MWU 和 randomized MWU

Deterministic MWU 通常用于 experts 给 binary predictions 的情况。算法看 weighted majority：哪边权重大，就预测哪边。

Randomized MWU 更一般。算法按权重比例随机选择 expert：

如果 expert 在第 轮 loss 是 ，算法的 expected loss 是：

更新常写成：

它给出的是 expected regret bound。

怎么选?

控制学习速度：

  • 太小：犯错 expert 权重降得太快，可能过早放弃暂时表现差但长期好的 expert。
  • 太接近 1：权重变化太慢，算法学习慢。

讲义中的 bound 往往含有 ，例如：

或类似形式。选 的目标是平衡两个项：一个来自初始 experts 数量 ，一个来自 best expert 的 loss 。

当知道 时，可以选更合适的 ；不知道时，通常会用通用参数或 doubling trick。

interval guarantee 的直觉

Tutorial 中有题目要求对每个时间区间都和该区间最好的 expert 比。这比只和全局最优 expert 比更强。

直觉做法是把时间切成 chunks，或者在不同起点重新启动多个 MWU 实例。这样每个区间都能找到一个“在该区间开始不久启动”的实例，与区间内最好的 expert 比较。

这类题的证明仍然围绕总权重：

  • 每次算法犯错，总权重下降。
  • 任意固定 expert 在某段里的权重下降由它在该段的错误次数控制。
  • 比较上下界得到区间内 mistake bound。

做题时怎么下手?

  • 题目说有完美 expert：优先想 Consistent Expert 或 Halving。
  • 题目说 best expert 犯 次错：用 MWU。
  • 题目出现 ：写权重更新 或 。
  • 要证明 mistake bound：对总权重 做上界和下界。
  • Randomized MWU：用期望线性性，算法 loss 是加权平均 loss。
  • 需要优化 ：把 bound 中依赖 的项平衡。

1. Learning from experts setting

有 个 experts， 个 time steps。

每轮：

  1. expert 给建议：

  1. algorithm 输出预测：

  1. 真实值 revealed；
  2. algorithm cost：

总错误：

best expert in hindsight：

目标不是让 绝对小，而是与 比较。

2. Impossible results

任意 deterministic algorithm，adversary 可以每轮设：

使：

随机算法也不能保证绝对错误小：对 uniformly random truth sequence，期望错误至少 。

即使与 best expert 比较，deterministic algorithm 也无法突破 factor 2 下界。

3. Consistent Expert algorithm

若存在一个 expert 从不犯错：

维护还没犯错的 expert 集合 。每轮选任意 跟随，观察真值后删除犯错 experts。

每次算法犯错，至少删除当前跟随的 expert。因为至少有一个 perfect expert 永远不被删除：

4. Halving algorithm

仍假设存在 perfect expert。每轮对当前 中 experts 做 majority vote，之后删除犯错 experts。

若算法犯错，说明至少一半 中 experts 错了，所以：

因此：

5. Basic MWU

不再要求 perfect expert。给每个 expert 权重，初始 。

每轮：

  • 输出 weighted majority；
  • 对犯错 expert：。

若 ，可得：

6. General deterministic MWU

对任意 ：

Extra close brace or missing open brace \boxed{ C(T)\le \frac{C^*(T)\log_2(1/\beta)+\log_2 n} \log_2(2/(1+\beta))} }

解释：

  • 小：接近 halving，适合 best expert 很准；
  • 大：更容忍 best expert 偶尔犯错。

7. Randomised MWU

随机版不是 weighted majority，而是按权重随机抽一个 expert 并跟随。

第 轮犯错概率正好是错误 experts 的权重比例：

所以：

权重更新：

分析得到：

当 且 合适时，接近：

随机化绕过了 deterministic factor 2 barrier，但 guarantee 是 in expectation。

8. Potential function method

Week 12 所有算法分析都用 potential：

证明套路：

  1. 上界：算法每次犯错时 下降；
  2. 下界：best expert 的权重仍然不太小；
  3. 联立得到 或 bound。

9. Log base

Deterministic MWU 讲义常用 ，randomised MWU 用 natural log 。换底只差常数，考试中要保持公式一致。

本周核心记忆

主题 关键结论
Best expert expert mistakes
Absolute guarantee adversarial setting 中不可能
Consistent expert 若 ，
Halving 若 ，
MWU
General MWU
Randomised MWU
Potential 总权重
Parameter tradeoff 小更激进， 大更稳健