弱分类器必须回应当前权重
分类器即使答对大部分训练例子,也可能反复漏掉同一批困难案例。复制它的投票不会修好那些错误。提升法改变训练样本上的分布,再要求分类器在新分布下仍有用。
所以“弱”在每轮都需要量化条件。均匀数据上的初始优势,不能独自支持后续全部重新加权的定理。本节会明确写出该条件,推导有限样本的 AdaBoost 保证。
固定样本、得分与平手规则
定义 12.1.1
(二元加权训练问题)
固定非空样本 ,,弱分类器 返回 或 。第 轮权重 且总和为一,加权错误率为
指示量在括号条件成立时为 1,否则为 0。初始 、得分 。加权投票后,。 时预测 ,否则预测 ;例子 的训练间隔定义为 。
正间隔表示答对;零间隔是平手,本规则会把正标签答对、负标签答错。因此证明用“答错必有间隔至多零”这个安全方向,不声称两者等价。得分是加权投票,不是已校准的类别概率。
以最小归一化因子选投票权重
设当前分类器有 ,对候选权重 考虑
答对时 ,答错时 。求导得 ,令其为零,得到
本节对数都是自然对数。 两项皆正,且 ,所以这是固定方向 的唯一全局最小值,没有声称整个集成已全局最优。因为 ,投票权重为正,最小 小于 1。
新例子权重归一化为
此式保留正权重及总和一,增加错例权重、降低正确例权重。对上述最小化投票权重,也可精确写成
因此原错例的新总权重恰为 ,原正确例也为 。下一弱学习器须在这个已改分布下找到新优势。
定义例外回合,不把分母设为零
若 ,因为全部权重正,所有训练例都答对,该弱分类器本身已是零训练误差答案。若也要保留原集成,选有限系数 ,加入此票后停止。每个新间隔是 。
此时不代入对数公式。其极限系数无穷, 的下确界零不由有限系数达到;本有限停止投票保证训练符号正确,不是指数损失为零。
若 ,正优势前提已失效。恰为 时,最优系数为 0、 为 1,没有进步。若假设类允许把 取负,超过 的错误可变成 ;但取负是额外类假设,也救不了恰好平衡的分类器。以下过程报告缺乏优势,不会凭空保证它存在。
BOOST(sample, max_rounds):
require sample is nonempty and labels are -1 or +1
D[i] = 1 / m for each example i
F[i] = 0 for each example i
votes = empty list
for each round up to max_rounds:
h = WEAK_LEARN(D)
error = sum D[i] over examples with h(x[i]) != y[i]
if error == 0:
alpha = 1 + max_i abs(F[i])
append (alpha, h) to votes
return votes with status PERFECT_TRAINING_FIT
if error >= 1/2:
return votes with status NO_POSITIVE_EDGE
alpha = (1/2) * ln((1-error) / error)
Z = 2 * sqrt(error * (1-error))
append (alpha, h) to votes
for each example i:
F[i] = F[i] + alpha * h(x[i])
D[i] = D[i] * exp(-alpha * y[i] * h(x[i])) / Z
return votes with status ROUND_LIMIT
返回的投票及分类器定义任意输入的得分; 存储训练例当前得分,用作停止测试。不要求弱学习器精确最小化加权错误,但以下定理要求它返回的错误率有合适上界。
例题 12.1.2
(以完美弱分类器停止)
设标签为 ,当前得分为 。平手规则在得分为零时预测 ,所以集成在例 、、 上答错。设下一个弱分类器在每个训练例上都等于 ,即 。有限停止规则给出 。新得分为 ,间隔为 ,全部不小于 ,所以每个训练预测都正确。若系数取 ,得分为 ,第一例的间隔为 ,那个错误仍会保留。
例题 12.1.3
(恰好为二分之一的分类器)
取四个等权的例子,以及只在例 和例 出错的分类器 ,所以 。此时 ,,:权重不变,这一票对 没有任何贡献。把 取负,得到只在例 和例 出错的分类器,加权错误仍是 ,所以取负救不了恰好平衡的分类器。弱学习器若返回这样的分类器,就是没有正优势,即程序中的状态 NO_POSITIVE_EDGE。
权重相消,露出训练目标
定理 12.1.4
(归一化因子乘积界定训练错误)
完成 轮,且每轮 时,
中间一项是经验指数损失。
证明
(从均匀初始权重还原每个末权重)
反复代入更新,得到
对 求和,用 ,便得等式。对答错例,平手规则保证 ,故 ;对答对例,错误指示为 0,不大于正的指数项。逐点不等式相加,再除 即可。
证明透视
权重相消证明用了什么、没用什么
这个证明有两个相互独立的部分。第一部分是恒等式:由 展开 ,每轮乘入一个因子 ;由于 ,指数合并成间隔,而归一化因子累积在分母。末权重总和为一,所以指数平均值必然恰好等于 ;这个等式不需要弱分类器如何选取的任何性质。第二部分是逐点不等式,也是唯一用到平手规则的地方:答错迫使间隔至多为零,从而 。这个不等式是单向的,并不说答错例的间隔恰为零,也不说答对例贡献很小。优势假设 完全没有进入这个证明;它要到之后证明每个 小于一时才出现。
定理 12.1.5
(一致正优势带来指数衰减)
若这 轮每轮在当前分布下都满足 ,其中固定 ,则
前提针对每个当前 ,不是只针对初始均匀分布。
证明
(先界每个因子,再相乘)
设 ,则 。由 时 ,在此平方根定义域得到 。乘 个因子再用前一定理,即得结论。若出现完美弱分类器,已另证的有限停止规则直接给零训练误差。
有限样本的错误率若严格小于 ,错例数是整数便迫使它为零。完成 轮有承诺优势的正误差回合即可。这是有条件保证:实现不能靠假设创造优势,同一输入的矛盾标签可能让条件根本不可达。
常见错误
(界等于 并不排除一个错误)
当 时,恰为 的训练误差界与一个错例相容,因为 个例子中错一个,训练误差正是 。只有严格不等式 才迫使整数的错例数小于一。选取 时,须要求 ,而不只是 。
精确演算三个自适应回合
例题 12.1.6
(四个训练输入与固定三分类器类)
预测如下;此表只指定训练输入,没有声称未见数据的标签:
| 例子 | 标签 | |||
|---|---|---|---|---|
| 1 | +1 | +1 | +1 | −1 |
| 2 | +1 | +1 | +1 | −1 |
| 3 | −1 | −1 | +1 | −1 |
| 4 | −1 | +1 | −1 | −1 |
第一轮平手选 。依次 、、 在各自回合都最小化此小类的加权错误:
| 回合 | 当前权重 | 所选错误率 | 投票权重 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
第一轮只错例 4,给它新总权重的一半;第二轮修好它,却错例 3,让例 3 新权重成 。所以第三轮只错例 1、2 的 变得有用,虽然它初始错误率是 。
一轮、两轮后集成都各错一例,但错例改变;三轮后全部间隔为正:
归一化因子为 、、,三轮后指数损失为 ,实际训练误差 0 远低于它。乘积目标会下降,即使某一轮零一错误数没有改变。
常见错误
(目标每轮下降,错例数却不一定)
在三轮例题中,指数损失界在一轮后为 ,两轮后为 ,而训练误差两次都是 :改变的只是被错分的是哪一个例子。定理用 的乘积界定最终误差,对中间每一轮并没有任何说法,所以期望错例数单调递减并无依据。
反例模式
复制分类器不会保留初始优势
上述一般更新后,同一分类器的旧错例新总权重恰为 。若不改预测就再调用它一次,加权错误就是 ,不是早前较小的值。
三轮例题中 初始错误 , 下却是 。均匀正确率 75% 本身不能支持反复正优势回合。重新加权创造新学习问题,不会承诺上一假设在新分布仍有优势。
说清楚此界证明了什么
以上全部量都在固定训练样本计算,证明没有使用抽样假设或测试分布。总体误差需要另外的泛化论证,零训练误差并非该论证;指数损失下降也不表示每轮观察到的零一错误都严格下降。
轮评估与更新 个权重,在弱学习器本身成本之外花 ,假设分类器评估及算术为常数时间。需存储 个权重/得分及返回分类器、投票权重。此处数学模型是精确的正权重归一化;有限精度实现须保留预期分布,不能悄悄把数值下溢当成零加权错误的证据。
附解答练习
快速检查
(重新加权一个四分之一错误的分类器:四例初始等权,分类器只错例 4。用两情况更新推导新权重,并求原样分类器在新分布下的加权错误。)
错例用 ,其余用 。
解答 · 答案
。错例得 ,每个正确例得 ,总和为一。原错集合仍是例 4,新权重为 ,所以原正优势不能直接重用。
快速检查
(分清目标进步与错例集合改变:为何三轮例题第二轮后,集成错例 3、答对例 4?两轮后训练误差与指数损失界各是多少?)
比较例 3 与例 4 的间隔 。
解答 · 答案
第二票 大于第一票 。例 3 第一分类器对、第二个错,间隔 ;例 4 则 。例 1、2 两个分类器都对。训练错误仍是 ,指数损失界为 。界下降时,错例数可以不变。
快速检查
(小心使用整数错例数:,且每个已完成的正误差轮次都保证优势至少为 。给出足够的轮数,使已证的界迫使训练错误为零。为何严格小于 有用?)
解 ,求 。
解答 · 答案
需要 ,所以 轮足够。此时界严格小于 ,但一个错例已使错误率至少为 ,因此不能有错例。若界恰等于 ,仍不能排除一个错例。结论仍依赖每轮确实找到承诺的优势。
快速检查
(某分类器在当前权重下的加权错误为 。求 和 ,以及它的错例在新权重下的总权重。)
使用 与 。
解答 · 答案
,。由两情况更新,每个错例得 ,所以错例合计得 ,正确例合计得另外的 。