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

Posted on 2026-06-01 Edited on 2026-09-29 In Course Notes , COMP5270 Word count in article: 6.2k Reading time ≈ 22 mins.

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

Part 1: Tutorial 12 详细题解

各题难度/要求说明：

Problems 1–3：课后可自行尝试，有困难时可在 tutorial 求助，但之后应自己完成。
Problem 4（⋆）：技术性较强，好练习，时间有限时可跳过只看答案。
Problems 5, 6（进阶）：好练习，较长、引导较少，在 tutorial 中讨论，有时间则自行或小组完成。

Problem 1（Warm-up）：Theorem 61 和 62 的参数绘图

题目：对绘制 Theorem 61 和 Theorem 62 的误差界，考察不同的，。

解答：

（编程练习，Mathematica 代码如下）

(* Theorem 61: C* log(1/β)/log2(2/(1+β)) + log2(n)/log2(2/(1+β)) *)
T61[beta_, cstar_, n_] := (cstar * Log[1/beta] + Log[n]) / Log[2/(1+beta)]

(* Theorem 62: C* ln(1/β)/(1-β) + ln(n)/(1-β) *)
T62[beta_, cstar_, n_] := (cstar * Log[1/beta] + Log[n]) / (1 - beta)

Plot[{T61[beta, 0, 1000], T61[beta, 10, 1000],
      T61[beta, 100, 1000], T61[beta, 1000, 1000]},
     {beta, 0.01, 0.99}]

关键观察： - 当（有完美专家）时，给出最小误差（等价于 Halving Algorithm）。 - 当较大时，最优趋向于平衡两项（参见 Problem 2）。 - Theorem 62（随机版）的界总是优于 Theorem 61（确定性版），差一个因子 2（当时）。

Problem 2：最优的选取

题目：若已知和的上界，如何设置 MWU（Theorem 61）和 Randomised MWU（Theorem 62）的参数？

解答：

精确解：对表达式关于求导，令导数为零（或数值求最小值）。

近似解（简单推导，差常数因子 2 以内）：

在两个算法的误差界中，两项分别为（或）和（或），除以公共分母。平衡两项，令：

若（即有非常好的专家），则（对错误专家给予重罚）。
若（所有专家都很差），则（惩罚很轻）。

具体计算：对 Theorem 61 中界，用近似（当），此近似给出（对时）。

Problem 3：证明 Fact 57.3——确定性算法需 2 倍

题目：证明：对任意确定性算法，存在序列使但。

解答：

设置：取个专家：专家 1 永远预测 0，专家 2 永远预测 1。

的上界：对任意序列，设，。专家 1 在上犯错（次），专家 2 在上犯错（次）。

构造使犯次错的序列：由于是确定性的，其在每步的输出完全由历史和专家建议决定（而专家 1 和 2 的建议只有，且只能用历史）。按如下方式对抗性地构造序列：

观察（两个专家建议），预测的输出，令（使犯错）
观察，预测的输出，令
以此类推，直到第步

此构造使在每一步都犯错，故，而。

结论：对确定性算法，需要 2 倍的额外代价，这个因子 2 是不可避免的。

Problem 4（⋆）：改进 MWU 使误差达

题目：设已知。修改 MWU 算法达到：

若，直接结论。
若，设，选合适的得到目标界。
综合。

解答：

(a)：若，取，由 Theorem 60：

满足目标（此时，）。

(b)：设。利用以下近似（级数展开）：

（更精确：）
（级数展开）

将 Theorem 61 的界代入：

取（当时，满足假设）：

(c)：综合 (a) 和 (b)，对任意：

Problem 5：区间稳健性——分块最优比较

题目：设对每个"块" ，希望算法的错误数满足（为块内最优专家的错误数）。考虑改版 MWU：若某专家的权重（平均权重的），才惩罚它。

(a) 写出算法。
(b) 分析犯错时总权重的变化：作为的函数。
(c) 证明。
(d) 给出每个专家在块开始时的权重下界。
(e) 给出块结束时总权重的下界。
(f) 得出结论。

解答：

(a) 算法：

在标准 MWU 基础上，Step 7 修改为：
若专家犯错且，则；否则权重不变。

(b) 权重分解：

设犯错时刻的总权重为，分为三类： - ：犯错的专家的权重之和 - ：未犯错的专家的权重之和 - ：犯错但权重（"轻量"犯错专家）的权重之和

注意（因为至多个专家，每个）。

实际上，（仅惩罚权重的犯错专家）。

等价地：。

(c) 证明 ：

由加权多数表决，犯错时，故。又，故：

(d) 每个专家在时的权重下界：

设专家在之前最后一次被惩罚时总权重为。由于惩罚条件要求，惩罚后。由于后权重不减（总权重随时间单调不增），，故：

若专家在之前从未被惩罚，则（因）。

(e) 块结束时总权重下界：

设最优专家（在块内犯次错）。由 (d) 知，且每次犯错权重乘以，故：

因此：

(f) 结论：

设在块内算法犯次错，由 (c)：

由 (e)：

整理（取对数）：

故（为常数时）。

Problem 6（进阶）：专家犯错至多次时的界

题目：个专家，已知专家犯错至多次（）。

(a) 运行 MWU（参数）时的界。
(b) 运行 Randomised MWU 时的界。

解答：

(a) MWU 的分析：

仿照课堂分析，若算法犯次错，则总权重至多（每次犯错总权重减少因子）。

另一方面，专家犯至多次错，权重至少，故：

综合：

取对数求解：

(b) Randomised MWU 的分析：

令为第步犯错权重的比例，则，最终权重：

下界同上：。

取对数，用：

整理：

Part 2: Week 12 讲义知识点——从专家学习

§0 问题设定

在线学习框架（Online Learning / Learning from Experts）：

个时间步（可以是无穷大）
个专家
每步：
1. 算法收到专家建议
2. 算法输出预测
3. 获知真实答案，支付代价

无任何假设：真实序列可以是对抗性的、随机的、相关的；专家可以互相勾结、是随机的或全知的；算法可以使用任意内存，但不能看到未来。

目标：最小化总代价。

最优专家代价：（后见之明中最优专家的错误数）。

§1 不可能结果（下界）

Fact 57.1（确定性算法：无法避免）：

对任意确定性算法和任意个专家，存在序列使。

证明：对抗者设（即算法每次都错）。

Fact 57.2（随机化算法：期望代价）：

对任意算法和任意个专家，存在（均匀随机的）序列使。

证明：取，则无论算法做什么，每步犯错概率。

§2 改变目标：后悔（Regret）

新目标：最小化相对于最优专家的超额代价（后悔，Regret）：

直觉：即使最好的专家也犯很多错，算法不应该比它好太多——但至少应该和它一样好！

Fact 57.3（确定性算法：2 倍因子必要）：

对任意确定性算法，存在序列使但。

证明：取，专家 1 永远预测 0，专家 2 永远预测 1；对抗性地令。由，，但。

§3 有完美专家时的算法

§3.1 Consistent Expert Algorithm（Algorithm 24）

场景：至少一个专家从不犯错（），但不知道是哪个。

Algorithm 24（Consistent Expert）：

初始化候选集
每步：收到建议，从中任选一个专家，预测；收到真相后，从中删除所有犯错的专家

Theorem 58：Algorithm 24 满足（即使）。

证明（势函数论证）：

势函数。

初始：
末态：（完美专家永不被移除）
每次犯错：至少减少 1（犯错专家被移除）

若犯次错，则，故。

§3.2 Halving Algorithm（Algorithm 25）

Algorithm 25（Halving）：

初始化
每步：取中专家意见的多数票预测；犯错后从中删除所有犯错专家

Theorem 59：Algorithm 25 满足（即使）。

证明（势函数论证）：

势函数，，。

每次犯错：由多数票，中至少一半的专家犯错，故被移除至少一半：

若犯次错，则，故。

Halving 的等价视角： - 初始权重 - 预测加权多数票 - 犯错专家权重乘以 0（"一次出局"）

§4 Basic MWU——所有专家都会犯错时

思路：将 Halving 中的"乘以 0"（一次出局）改为"乘以 "（软惩罚）。

Algorithm 26（Basic Multiplicative Weights Update，基础 MWU）：

初始化
每步：
- 收到建议
- 输出加权多数票
- 收到真相
- 对所有犯错专家（）：

Theorem 60（Basic MWU 的保证）：Algorithm 26 满足：

即使。

证明（势函数论证）：

势函数（总权重）。

初始：
末态下界：最优专家犯次错，权重，故

每次犯错时，至少一半总权重在犯错专家上，犯错专家权重各乘以：

设为犯错专家的权重和，犯错时，则：

若犯次错，则，结合：

§5 通用 MWU——参数化版本

Algorithm 27（Multiplicative Weights Update，通用 MWU）：

参数：惩罚参数

初始化（）
每步：
- 预测加权多数票
- 对犯错专家：（时退化为 Algorithm 26）

Theorem 61（通用 MWU）：Algorithm 27 满足：

即使。

证明：同 Theorem 60，但每次犯错总权重减少因子（而非），末态下界为：

参数的权衡：

（强惩罚）：（接近最优），但对时退化为（Halving）
（弱惩罚）：（接近 2 倍因子下界），项增大
最优：令，即（当时）

§6 Randomised MWU——突破确定性下界

动机：Fact 57.3 表明确定性算法必须付出至少 2 倍的代价；随机化可以打破这个限制！

思路：MWU 用"硬"多数票（权重占 50.1% 就满下注），更自然的做法是按权重比例随机采样一个专家。

Algorithm 28（Randomised MWU）：

参数：惩罚参数

初始化（）
每步：
- 收到建议
- 按权重比例随机采样专家：
- 输出（跟随该专家的建议）
- 收到真相，对所有犯错专家：

等价地（在二元设置中）：令，输出。

Theorem 62（Randomised MWU）：Algorithm 28 满足：

即使。

§7 Theorem 62 的完整证明

势函数：，，。

犯错概率：设（犯错专家权重占比），则，故：

势函数递推（无论是否犯错，每步都有变化）：

取对数（利用对）：

结合下界 ：

整理：

关键优势：在随机版的分析中，每步总权重的变化恰好与犯错概率相关，无需"算法犯错时才有信息"的条件——这正是随机化带来的分析优势。

§8 MWU vs Randomised MWU 比较

特征	Algorithm 27（MWU）	Algorithm 28（Randomised MWU）
类型	确定性	随机化
预测方式	加权多数票（硬决策）	按权重随机采样专家
误差界
界的形式	确定性成立	期望成立
时		（但系数更小）
优劣	始终 Theorem 62 的界（差因子）	总是不差于 Theorem 61（见图 21）

注意对数底数：Theorem 61 使用，Theorem 62 使用（自然对数）——差了一个常数，但随机版始终更优（见课堂图 21）。

§9 势函数论证方法总结

本章反复用到的势函数（Potential Function）论证是算法分析的重要技术：

步骤： 1. 定义势函数（描述算法状态的某个量） 2. 确定（初始值）和（终态下界） 3. 分析每次"坏事件"（算法犯错）时的减少量 4. 由（或乘法版）推出犯错次数上界

算法	势函数	初态	末态下界	每次犯错减少	结论
Algorithm 24				（加法）
Algorithm 25				（乘法）
Algorithm 26/27
Algorithm 28				（每步）

§10 本章知识点总览

概念	关键内容
在线学习设定	步、专家、对抗真相、最小化
Fact 57.1	确定性：不可避免
Fact 57.2	随机化：
Fact 57.3	确定性：2 倍下界（2 专家构造）
Algorithm 24	Consistent Expert；；势函数（加法减少）
Theorem 58	Algorithm 24 正确性
Algorithm 25	Halving；；势函数（乘法减少）
Theorem 59	Algorithm 25 正确性
MWU 的权重视角	初始权重 1，犯错专家乘；总权重 = 势函数
Algorithm 26	Basic MWU（）；
Theorem 60	Algorithm 26 正确性
Algorithm 27	通用 MWU（参数）；Theorem 61
Algorithm 28	Randomised MWU；按权重采样专家；Theorem 62
Theorem 61	确定性界：
Theorem 62	随机化期望界：（总 Theorem 61）
最优	令
势函数论证	定义 →分析初态/末态下界→每次犯错的减少量→推出的上界

Part 3: Week 12 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] In the "learning from experts" setting seen in class, we assume that the experts are independent.

[CN] 在课上讲的 learning from experts 设定中，我们假设个 experts 是相互独立的。

选项	答案
False	✅
True	❌

知识点：Learning from experts 框架对专家不做任何假设——专家可以任意相关、甚至可以是对手操控的。算法只根据每个专家的历史表现（犯错次数/权重）来决策，不需要独立性假设。

Question 2

[EN] There is a deterministic algorithm which achieves total error , regardless of .

[CN] 存在一个确定性算法可以达到总错误，且与无关。

选项	答案
True	❌
False	✅

知识点：Fact 57.3 表明对确定性算法，对手可构造 2 专家情形使而。更一般地，在无任何关于最优专家假设时，确定性和随机化算法的总错误 worst-case 均不能。

Question 3

[EN] The Consistent Expert algorithm is _______ and achieves total error ___, independent of , as long as some expert makes no mistake.

[CN] 只要存在某个 expert 从不犯错，Consistent Expert algorithm 是_算法，并且总错误为_，与无关。

选项	答案
Deterministic/	✅
Deterministic/	❌
Randomised/	❌
Randomised/	❌

知识点：Algorithm 24（Consistent Expert）：维护正确专家集，每次跟随中任意专家；若犯错则将当前专家从删除。势函数，每次犯错 加法减少 1，初始，故。

Question 4

[EN] The Halving algorithm is _______ and achieves total error ___, independent of , as long as some expert makes no mistake.

[CN] 只要存在某个 expert 从不犯错，Halving algorithm 是_算法，并且总错误为_，与无关。

选项	答案
Randomised/	❌
Randomised/	❌
Deterministic/	✅
Deterministic/	❌

知识点：Algorithm 25（Halving）：用加权多数投票，犯错时删除所有犯错专家。势函数，每次犯错至少一半专家被删（多数票原理），故 乘法减半，。这是从到的关键改进。

Question 5

[EN] No deterministic algorithm can always achieve total error .

[CN] 没有确定性算法能总是达到的总错误。

选项	答案
True	✅
False	❌

知识点：Fact 57.1：对确定性算法，若不假设存在好的专家，对手可构造序列使算法每步都犯错（），而最优专家仅犯错。worst-case 下总错误不能低于线性，不依赖。

Question 6

[EN] Letting denote the error (in hindsight) of the best expert, there is a deterministic algorithm which can always achieve total error at most .

[CN] 令表示事后最优 expert 的错误数，存在一个确定性算法总能达到至多的总错误。

选项	答案
True	❌
False	✅

知识点：确定性 MWU（Theorem 61）的最优乘法因子约为 2（不能接近 1）。此外 Fact 57.3 给出确定性算法的 2 倍下界。这样接近最优的保证只有随机化 MWU（Theorem 62）才能在期望意义下实现。

Question 7

[EN] Letting denote the error (in hindsight) of the best expert, there is a randomised algorithm which can always achieve total expected error at most .

[CN] 令表示事后最优 expert 的错误数，存在一个随机化算法总能达到至多的总期望错误。

选项	答案
True	✅
False	❌

知识点：Randomised MWU（Algorithm 28，Theorem 62）：。取（很小），得。取，即为。

Question 8

[EN] The MWU algorithm is a generalisation of the ______ algorithm.

[CN] MWU algorithm 是____算法的推广。

选项	答案
Halving	✅
Consistent Expert	❌
Simplex	❌

知识点：Halving 是 MWU 的极端特例——对犯错专家权重乘以，相当于直接删除。MWU 用更平滑地惩罚犯错专家，分析更精细，可同时处理的情形。

Question 9

[EN] Randomisation allows to get a better total worst-case error than what is possible deterministically.

[CN] 随机化允许我们获得比确定性算法更好的 total worst-case error。

选项	答案
True	❌
False	✅

知识点：随机化改善的是期望误差（expected total error），而非每条随机路径上的 worst-case 总错误。Fact 57.2：即使随机化算法，对手也可让（无好专家时）。随机化的优势在于实现的期望保证，确定性无法做到。

Question 10

[EN] The MWU algorithm retrieves the Halving algorithm as gets close to ___.

[CN] 当接近____时，MWU algorithm 退化/恢复为 Halving algorithm。

选项	答案
	❌
	❌
	✅

知识点：MWU 中犯错专家的权重乘以。当：犯错专家权重趋向 0，等价于删除 = Halving。当：几乎不惩罚 = 最差情形。最优平衡贡献和代价。

Week 12 Quiz 速查表

题号	核心概念	正确答案
1	Experts 独立	False
2	确定性	False
3	Consistent Expert	Deterministic/
4	Halving	Deterministic/
5	无法	True
6	确定性	False
7	随机化期望	True
8	MWU 推广自	Halving
9	随机化 worst-case	False
10	退化	（Halving）

高频混淆点： - Consistent Expert vs Halving （Q3 vs Q4）——势函数分析方式不同（加法 vs 乘法减半） - 确定性无法达到，随机化期望可以（Q6 vs Q7）——核心区别 - 随机化改进 expected error，不是 worst-case（Q9）——不要混淆 - 趋向 Halving，趋向不惩罚（Q10）

Part 1: Tutorial 12 详细题解

Problem 1（Warm-up）：Theorem 61 和 62 的参数绘图

Problem 2：最优 的选取

Problem 3：证明 Fact 57.3——确定性算法需 2 倍

Problem 4（⋆）：改进 MWU 使误差达

Problem 5：区间稳健性——分块最优比较

Problem 6（进阶）：专家 犯错至多 次时的界

Part 2: Week 12 讲义知识点——从专家学习

§0 问题设定

§1 不可能结果（下界）

§2 改变目标：后悔（Regret）

§3 有完美专家时的算法

§3.1 Consistent Expert Algorithm（Algorithm 24）

§3.2 Halving Algorithm（Algorithm 25）

§4 Basic MWU——所有专家都会犯错时

§5 通用 MWU——参数化版本

§6 Randomised MWU——突破确定性下界

§7 Theorem 62 的完整证明

§8 MWU vs Randomised MWU 比较

§9 势函数论证方法总结

§10 本章知识点总览

Part 3: Week 12 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 12 Quiz 速查表

Problem 2：最优的选取

Problem 6（进阶）：专家犯错至多次时的界