一次学习一个预测
在批量问题中,学习器接收一份带标签样本,然后生成分类器。在线学习中,预测与反馈交替进行。第 轮,学习器看到 并预测标签,随后才看到 ;它可利用反馈改变下一次预测。这个顺序禁止学习器在预测前使用当前标签。
错误界控制一个序列上的错误预测次数。它可以是确定性的,对对抗性选择的序列也成立;但它不会自动成为关于未来样本的概率界。我们先比较有限个二分类专家,再说明连接在线与总体观点所需的额外独立同分布假设。
折半一个可实现的版本空间
设 是可测实例空间上的有限非空可测分类器集合,其中 。初始令 。第 轮,在 中预测多数标签;若平局则选 1。真实标签揭晓后,仅保留预测该标签的假设:
定义 5.1.1
(可实现序列与版本空间)
若存在同一个固定的 对每一轮都标注正确,则称序列 可由 实现。与之前全部标签一致的假设集合 称为第 轮的版本空间。
可实现性保证每一轮 ,所以版本空间永不为空。过程不需要知道哪个成员是 。
定理 5.1.2
(折半错误界)
对每个可由 实现的有限序列,多数算法至多犯 次错误。
证明
(每次错误使版本空间减半)
在犯错的一轮,当前至少一半假设预测了学习器所选的错误多数标签;平局时也成立。所有这些假设都被删除,因此 。在正确轮次中,版本空间也不会增大。经过 次错误后,由于 仍然保留,。因此 ,而 为整数。
证明透视
每个假设用在哪里
论证靠两个相互独立的事实。多数投票提供减半:它只在犯错的轮次起作用,那时错误标签至少为 中一半的假设所持有,所以至少一半被删除。可实现性提供幸存者 ,由此得到下限 ,它从不参与减半这一步。去掉可实现性,减半仍然成立,但下限消失, 可能变空,下面的反例正是如此。正确的轮次不会删掉任何必要的假设,也不花费错误。 中的取整仅仅来自 是整数。
例题 5.1.3
(四个阈值与两次错误)
令 、,其中 。对 ,两个假设投 1、两个投 0,平局规则预测 1。若 ,便犯一次错,且只剩 。对 ,二者再次平局,学习器预测 1。若 ,又犯一次错,只剩 。序列可由 实现,并达到 的界。
对某些假设类,这个界是紧的。在 个不同点上,令 包含全部 个二值函数。对任意确定性在线学习器,依次呈现每个点一次,并选择与学习器预测相反的标签。所得 个标签确定了 中的一个固定目标,所以序列可实现,并迫使学习器犯 次错误。这是针对该类的最坏情况构造,并不声称每个同样大小的类都能迫使如此多错误。
没有完美专家时的加权多数法
如果数据不可实现,专家犯一次错就永远删除它,可能使版本空间变空。加权多数法保留所有专家,但降低出错者的权重。
定义 5.1.4
(带惩罚因子的加权多数法)
令 ,选 ,初始对所有 设 。每轮预测总权重较大的标签,平局仍选 1。看到 后更新
每一轮所有出错专家都被更新,包括学习器预测正确的轮次。记学习器的错误次数为 ,专家 在相同 轮中犯错 次。
定理 5.1.5
(加权多数错误界)
对于每个有限带标签序列,无需可实现性假设,
对数均为自然对数。特别地,用事后最优固定专家的错误次数代替 ,该界仍成立。
证明
(对总权重的势函数论证)
令 ,初始 。任何一轮权重都不会增加。当学习器犯错时,至少一半总权重投给了错误标签,平局情形也包括在内。因此
经过 次错误,。另一方面,固定专家犯 次错误后的权重为 ,所以 。取对数并整理即得该界;由于 ,分母为正。
证明透视
夹住总权重
证明从上、下两个方向界定同一个量 。上界只用到学习器的错误:在每个犯错的轮次,至少一半权重落在错误标签上并被乘以 ,所以 至少减少 的比例;正确的轮次只会令 减小,因此忽略它们是安全的。下界只用单个专家,因为 是非负项之和,不小于其中任何一项。由于 任意,结论对所有专家同时成立,特别是对最优的那个。这里既不需要可实现性,也不需要专家彼此独立或标签具有随机性。
例题 5.1.6
(两个常值专家)
两个专家分别总预测 0 和 1,取 ,标签依次为 0、1。初始权重平局,学习器预测 1 并犯错;新权重为 1 和 。下一轮预测 0 并犯错,此后两个权重均为 。两个专家各犯一次错,而该界给出 ,对 成立。虽然没有专家对两个标签都预测正确,该界仍然有效。
例题 5.1.7
(三个专家的逐轮跟踪)
取专家 ,。第 1 轮:预测为 ,标签为 1。投给 1 的权重为 ,投给 0 的为 ,学习器预测 0 并犯错; 减半,权重变为 ,。第 2 轮:预测为 ,标签为 0。投给 1 的权重为 ,投给 0 的为 ,学习器预测 1 并犯错; 减半,权重变为 ,。第 3 轮:预测为 ,标签为 0。投给 0 的权重为 ,投给 1 的为 ,学习器预测正确,但 仍然减半,权重变为 ,。因此 ,。对 ,定理给出 :成立,但在这么短的运行上远不紧。最终权重 也验证了 的下界。
常见错误
(只在学习器犯错时才惩罚专家)
在加权多数法中,每个预测错误的专家在每一轮都要乘以 ,包括学习器自己预测正确的轮次,上面跟踪的第 3 轮就是例子。如果只在学习器犯错之后才更新,下界 就不成立,因为 统计的是该专家的全部错误。
这里比较的是事后最优的固定专家。固定 时,乘在 前的系数一般大于一;单凭所示结果并不是次线性遗憾界定理。折半证明需单独处理 :不能将零代入这个对数界。
反例模式
版本空间可能消失
取一个实例 、两个常值专家 0 和 1,标签依次为 0、1。第一个标签后,折半法只保留常零专家;第二个标签后不再剩下任何专家。该序列不能由单个专家实现,所以折半定理不适用。加权多数法保持正权重并仍有最优专家比较,但如果每个专家都犯很多错,该比较并不保证绝对错误次数很少。
从在线错误到期望风险
现在假设 独立同分布于固定分布 ,,且第 轮在线规则以固定的确定性平局规则定义可测分类器 ,只使用之前的样本。令 。经过 轮后,独立于样本、从 均匀选择 ,输出事先保存的分类器 。在给定过去的条件下, 是新抽样,因此
期望同时针对样本和 。若某个固定 满足 ,有限独立同分布序列几乎必然可实现。折半法因此几乎必然至多犯 次错,故 。该陈述针对随机选出的已保存预测器和期望风险。它不自动成为高概率保证,也不自动保证最后一个预测器或非独立同分布序列的表现。
常见错误
(把期望风险界用在最后一个预测器上)
等式 是对均匀下标 取平均。它并没有界定 或 :在线规则可能到很晚才犯最后一次错,单个较晚的预测器可以有很大的风险,而对全部 个预测器的平均仍然很小。
练习与解答
快速检查
(若可实现的假设类有六个假设,折半法给出多少次错误的整数上界?)
套用定理并向下取整。
解答 · 答案
。若犯三次错,剩下的假设至多 个,这不可能,因为 始终保留。
快速检查
(对上述四个阈值,在 处按平局规则作第一次预测,并写出标签为 0 后保留的集合。)
分别计算 时的 。
解答 · 答案
,。两边各有两个专家,故平局预测 1。标签 0 只保留预测 0 的假设,即剩下 。
快速检查
(加权多数法取 、,且有一个完美专家。所述定理给出的学习器整数错误次数上界是多少?)
完美专家的 。
解答 · 答案
定理给出 ,由于 为整数,故 。在此例中该界弱于可实现折半界 。
快速检查
(一个独立同分布问题满足某个 的 ,且 。运行折半法 轮,令 均匀且独立于样本,输出保存的 。对样本和 取期望,给出其总体误差上界。)
利用 和折半界。
解答 · 答案
折半法几乎必然至多犯 次错,因此期望误差至多为 。这并不说明每次运行或最后一个在线预测器的误差都至多为 。