弱学习器可能只比抛硬币好一点。Boosting 能把这个优势转化为任意小的误差,但有一条关键限定:学习器必须在 boosting 所使用的变化分布上持续保持优势。仅有训练误差计算并不能给出这种分布层面的保证。这里先在明确的弱学习假设下直接证明保证,再说明如何从原始样本源中对这些变化分布采样。
定义 6.2.1
(边缘为 的弱学习器)
设 是实例空间 上的未知分布,来自概念类 的未知目标 提供标签 ,其中 的函数均为可测映射 。下文所有规则和权重均可测。固定 。边缘为 的弱学习器具有以下无分布、可实现保证:对每个 、 上每个由该目标标记的分布 ,以及每个 ,给定来自 的 个独立带标签样本,它输出规则 ,使
以至少 的概率成立;概率取自样本及其独立内部随机性。样本界 不依赖具体的 或 ,且学习器除带标签样本外并不知道 。这个保证必须对下文遇到的每个重加权 成立。我们假设每个输出规则在需要时可以求值;计算复杂度取决于弱学习器和规则的表示。
使用固定正步长的总体 boosting
令
从 开始。第 轮使用相对于 具有以下密度的分布 :
得到规则 后令 。每个 都是概率分布:权重正且有界,并且 。最终预测取 的符号,平局可使用任意固定规则。分析中把零间隔计为错误,因此上界覆盖每一种此类平局规则。
定理 6.2.2
(总体误差的指数下降)
若每个选出的规则在 下的误差都不超过 ,则
这是对实际选出的规则和真实分布 的确定性蕴含。不需要假设有限假设类,也不需要经验泛化步骤。
证明
(每个成功轮次都缩小指数势)
令 。(2) 中的换测度给出 ,因此
不等式使用 与 。等号处的值由 的定义算得。由于 ,连乘得到 。只要 就有 ,从而得到 (3) 的第一个不等式。最后,。
证明透视
为什么这是总体结论
每个 都由真实的 定义,而 (1) 中的弱边缘是真实的 误差。势函数是对 的期望,不是训练平均。规则可以自适应选择;在它们选出后,只要每条规则满足自身的边缘条件,确定性不等式就适用。下一步说明如何在不知道 的密度时获得所需样本。
对自适应重加权分布采样
第 轮开始时,已选择的 已由先前记录固定。从 抽取新鲜带标签样本 。对每个候选样本,独立地以如下概率接受:
由于 ,这个概率位于 。重复直到接受 个样本。实现 (4) 不需要知道归一化常数 。
定理 6.2.3
(拒绝采样与明确的候选样本上限)
以先前记录为条件,被接受的样本是来自 的独立样本。接受概率满足
每轮恰好使用 个被接受样本。对无上限的过程, 轮使用的原始 候选样本总数的期望至多为 。因此对 ,上限
被超过的概率至多为 。
证明
(先取条件,再对自适应历史求平均)
对任意可测 ,一个候选样本落入 且被接受的概率为
除以总接受概率就得到 。独立候选样本和独立接受硬币使连续接受的样本相互独立,且具有同一个条件分布。又因为 ,得到 (5)。
以历史为条件,每次接受所需候选数服从成功概率为 的几何分布,所以接受 次的期望候选数至多为 。这个界对每段历史都成立,包括弱规则不成功的历史。取期望并求和便得到总期望界。对无上限过程使用 Markov 不等式,证明 (6)。将无上限过程的候选样本数记为 ,中止事件为 :实际实现若将超过 就中止;在其补事件上,它与无上限过程完全相同。
例题 6.2.4
(两轮拒绝采样)
设 ,、,两点的目标都是 ,。则 ,。第 1 轮中 ,。设 在 处正确、在 处错误,所以 。于是 使 在 处为 、在 处为 ,且 。
第 2 轮中,(4) 的接受概率为 、。总接受概率为 ,与 一致,也满足 (5) 的下界 。在被接受的样本中,落在 的比例为 ,这恰是由 (2) 直接算出的 :。
常见错误
(接受概率不能超过一)
用概率 接受候选样本,看似是实现 (2) 的自然做法,但这个数可能大于一:在上面的例子中, 在 处等于 。(4) 中的因子 把所有权重乘以同一个常数,使最大的权重不超过 。这并不改变 ,因为只有接受概率的比值才起作用;这也是无需计算未知归一化常数 的原因。
强学习器与其假设
给定 ,取
每轮使用 个被接受样本。运行上限为 (6) 的过程;若中止,则输出任意固定规则。
定理 6.2.5
(带置信度的弱到强保证)
对每个 和每个 ,在上述无分布弱学习假设下,返回的分类器以至少 的概率具有至多 的 -误差。即使中止,使用的原始样本数也至多为 。
以任意先前记录为条件,拒绝采样提供新鲜、独立的 样本。因此,即使 是自适应选择的,弱学习器在第 轮不满足边缘条件的条件概率仍至多为 。对记录求平均并使用并集界,任意一轮失败的概率至多为 。在无上限的思想实验中,超过候选样本上限的概率至多为 。在两个补事件的交集上,由 (3) 得误差至多 ;且有上限的算法与思想实验相同。并集界证明定理,不需要这两个失败事件相互独立。
对固定边缘 ,有 ,且 是 的多项式。因此,只要弱学习器的样本和计算成本对相应参数为多项式,且规则可高效求值,(6) 对 和 也是多项式。这个拒绝采样界有意取得粗,并不是最优的 boosting 样本复杂度。若 变化,该多项式的指数依赖于 ,所以这里不声称对 一致的多项式依赖。
例题 6.2.6
(上限有多粗略)
取 、。此时 ,,。势函数的界为 。然而在 (5) 所允许的最坏情形下,最后一轮每接受一个样本可能需要 个候选样本。边界情形是第一轮:,所以 ,每个候选样本都被接受,。分析本身是正确的,但上限 (6) 只是证明的工具,并不是实际成本的估计。
例题 6.2.7
(三条规则各错一个不同的点)
设 ,概念类包含两个恒定目标 和 。对于每个点,让 中的一条在该点预测 ,在其余两点预测 。使用六条规则的假设类 ,其中没有恒定规则。对任一目标和每个分布 ,至少有一个点的质量不超过 ;选择带有适当符号的对应规则,其误差至多为 。因此该类别对两个目标都有无分布边缘 ,尽管没有一条单独的规则是完美的。
例如取 。在这六条规则上用新鲜样本做经验误差最小化,就得到边缘为 的弱学习器:一致 Hoeffding 界表明,只要 ,六条规则的经验误差与真实误差之差都不超过 的概率至少为 。选出规则的真实误差因此至多为 。事实上,对正目标, 的无权多数投票是完美的;对负目标,它们的相反规则的多数投票是完美的。这展示了单条规则均不完美时组合如何成功。
反例模式
只在原分布上有边缘并不够
设 、,两个点的目标均为 。在 正确、在 错误的规则 有 -误差 。但只重复这条规则永远修不好该错误: 的任意正权重多数投票仍是 。在重加权 (2) 下, 的相对权重每轮增加 ,其概率趋于一。最终 在 booster 所请求的分布上不再有正边缘。只针对 的弱保证不能代替 (1)。
练习与解答
快速检查
(一步势函数:若某规则的 误差为 ,推导 。)
把期望分成正确点与错误点两部分。
解答 · 答案
正确点满足 ,贡献 ;错误点满足 ,贡献 。故比值为 。
快速检查
(轮数:若 、目标误差 ,求给出的充分轮数 。)
使用 。
解答 · 答案
,故 。这是充分轮数,不一定是最少轮数。
快速检查
(不需要无穷系数:若某个选出规则的 误差为零,会怎样?)
在 处计算该轮的因子。
解答 · 答案
该轮因子为 。固定的 仍有限,更新有定义。这避免了根据精确误差取自适应系数时可能出现的除零问题。
快速检查
(自适应置信度:后来的 依赖先前随机规则,为什么仍可使用 上界?)
以第 轮之前的记录为条件。
解答 · 答案
对任意先前记录取条件,第 轮失败概率至多为 。取期望后,无条件概率也至多为 。再用并集界得到 ,无需假设各轮失败相互独立。
快速检查
(上限不等于期望:为什么仅有候选样本数的期望界不能给出确定性样本上限?)
非负随机变量可以超过它的平均值。
解答 · 答案
非负随机变量可能超过其期望。Markov 不等式将该界转化为高概率上限:取 (6) 的 时,理想过程超过 的概率至多 。在 处中止使实际资源使用有确定性界,并把该事件计入失败概率。