与最佳固定专家比较
在线预测中,学习器须在看到当前损失前行动。专家会犯错,因此一次表现不佳便永久淘汰可能过于严苛。指数权重逐步降低高损失专家的影响,并把学习器总损失与事后选出的最佳单一专家比较。
固定 个专家及 轮。第 轮专家 的损失为 。以下保证把整个损失序列视为独立于学习器随机抽样而预先固定。在全信息设定下,行动之后学习器观察每个专家的损失,而非只观察抽中专家的损失。损失不必互相独立,也不必来自统计分布。
定义 5.3.1
(指数权重)
初始化 ,选择学习率 。每轮开始时计算
定义 5.3.2
(相对最佳固定专家的期望遗憾)
学习器在看见本轮损失前按 抽取一个专家,待损失揭示后更新所有权重。对固定损失序列, 是过往损失的确定性函数,所以本轮期望损失为 。相对最佳固定专家的期望遗憾为
遗憾可以为负;以下不等式是上界。
常见错误
(与每轮最佳专家比较)
基准 每轮选不同的专家,它永不大于 ,却可以小得多。取两轮损失 和 ,前者等于 ,而每个固定专家都损失 。下面的定理针对的是后一个基准,即全程只用一个专家。
势能计算
定理 5.3.3
(指数权重的遗憾界)
设损失 预先固定,且 。则对每个固定专家 ,
特别地,若预先知道 并取 ,相对最佳固定专家的期望遗憾至多为 ;固定 时,平均遗憾随 增大而趋向零。
证明
(以弦界为基础的势能论证)
对 , 的凸性使其图像不高于连接两个端点值的弦:
因此利用 时 ,得到
由于 且 ,对数有定义。另一方面,任意固定专家 的最终权重是 ,故 至少为该权重。把这个下界与求和后的上界及 结合,得到
对 ,,因此对 有 。由于 ,代入并移项先得 。再用 ,得到对每个固定专家 均成立的上界
证明透视
各项假设在哪里使用
证明用到三个要素,各用一次。 的凸性加上取值范围 给出弦界,把混合量 化为只依赖期望损失 的式子;损失超出 时弦不等式不成立。全信息用在更新每一个权重时,使 依赖全部损失。关键一步是势能 :它的增量裂项相消为 ,上界来自学习器的损失,下界来自单个专家的权重,其余各项都被舍去。由于 是任意的,这个界对所有固定专家同时成立,最佳专家事后才选出。最后一步把 换成 , 这一项就来自这里。
这个弦界论证提供有效上界,并不声称常数最优。这是加性的期望损失比较:若所有专家表现都差,它不表示绝对损失小;它也不是单次随机执行的高概率保证。
反例模式
大于一的损失
人们容易以为,对任何有界损失都可以沿用同样的常数。取 、、,损失向量为 。上界给出 。但 ,所以 ,而最佳专家的损失为 ,遗憾是 。弦不等式在 时不成立,因为 。补救方法是重新缩放:若损失落在 ,对 应用定理,遗憾上界便乘以 。
例子
例题 5.3.4
(三个专家的两轮)
取 。第一轮损失向量为 ,第二轮为 。初始权重都是一,所以第一轮期望损失为 。第一轮后权重为 ,下一轮分布为 。第二轮期望损失为 ,总期望损失为 。三个固定专家的损失为 ,最佳者损失零,因此期望遗憾为 。第二轮更新后权重是 。
例题 5.3.5
(调整学习率)
取 、。则 ,而 、。上界的两项相等,这正是这个取法使 最小的原因。保证为 :一百轮内,期望总损失比最佳专家至多多出约 ,即平均每轮约 。
例题 5.3.6
(完全相同的专家)
设 ,且每轮 。两个权重每轮都乘以 ,因此对所有 都有 、,相对任一专家的遗憾为 。上界 在此远非紧的,因为它是对所有损失序列的最坏情况。
常见错误
(期望损失不等于单次运行的损失)
单次实际执行可能不同于 ,因为学习器会抽取专家。上述计算对这些抽样取平均,专家损失序列则保持固定。例如,若学习器两轮都抽中第二个专家(概率为 ),实际损失是 ,而不是 。
保证的界限
全信息假设很重要:若只揭示抽中专家的损失,便不能按原式更新。多臂老虎机式反馈需要不同的估计量与分析。同样,所选 使用了时域 ;未知时域的方法需要自己的调度或重启分析。与分布无关的序列上界,本身并不表示在不断改变的环境下未来预测风险如何。
练习
快速检查
(取 、,某轮损失为 。给出初始分布、期望损失及更新后权重。)
由 开始。
解答 · 答案
初始分布为 ,期望损失为 。权重变为 。
快速检查
(为何势能证明能与每个固定专家比较,即使最佳专家要到所有轮次后才确定?)
论证中的专家 是任意的。
解答 · 答案
对每个专家 , 的下界都成立,所以遗憾上界对所有固定专家同时成立。算法无须知道谁最佳;对 取最小值只发生在分析中。
快速检查
(为何上述更新需要完整反馈?若只观察抽中专家的损失,哪些权重无法更新?)
留意因子 。
解答 · 答案
更新要对每个 把 乘以 。若只观察到抽中专家的损失,其他专家的因子便未知,它们的权重无法更新。
练习 5.3.7
(证明对 及 ,。)
基础证明
解答(3)
- 1
把 写成两个端点的凸组合
,权重 与 都在 内。
- 2
应用凸性
由于 是凸函数,。
依据: 函数 的二阶导数 。
- 3
化简右边
∎,正是所要的上界。