从错误中学习
在线学习器每一轮先看到一个输入,预测其标签,然后在下一轮之前看到正确标签。感知机保存一个向量 ,并预测 的符号。设标签 ,采用如下规则:从 开始,并按下式更新
这一非正间隔约定在平局(间隔恰为零)时也会更新。如果预测规则在平局时偏向 ,则每一次真正的错误都是一次更新,尽管平局时的更新可能预测正确。因此,对更新次数的界同时也是对错误次数的界。
具有正间隔的可分性
定义 5.2.1
(带间隔 的分离)
若单位向量 使每一轮 都有 ,其中 ,则称序列 被 以间隔 分离。数值 是 到超平面 的带符号距离;当 位于其标签所在的一侧时为正。
定理 5.2.2
(感知机错误次数界)
假设每一轮都有 ,且序列被单位向量 以间隔 分离。那么,即使序列是自适应选取的,只要满足这些假设,该规则至多执行 次更新。
证明
(线性进展对平方根增长)
只对发生更新的轮次编号,并记 为经过 次更新后的向量。每次更新都在 方向上取得进展:
这里 在本证明中用于标记更新轮次。在一次更新中有 ,所以
由归纳法得 。Cauchy–Schwarz 不等式与 给出 。当 时,两边相除再平方,得到 。该论证是确定性的:它对序列没有任何独立性假设。
证明透视
进展是线性的,而范数至多按平方根增长
每个假设恰好对应一条不等式。间隔 给出下界 ,并且每一次更新的轮次都需要它。更新条件 使范数平方中的交叉项不为正,而 控制其余部分,得出上界 。从 开始提供该归纳法的起点。最后, 只用一次,即在 Cauchy–Schwarz 不等式中,把投影 转化为由 控制。线性增长不可能永远停留在平方根型上界之下;将两者比较即得错误次数界。
常见错误
(原始得分大不等于间隔大)
如果某个非零分离向量 满足 ,则取 与 。仅凭未归一化的 取值很大,并不能说明几何间隔很大,因为对 作缩放会改变该值。若把 中的 换成 ,只要放大 就能使上界任意小,这显然荒谬。
该界说明了什么,又没有说明什么
例题 5.2.3
(读出上界)
在 中,设每个样本都满足 且 。取 ,得 、,因此至多更新四次。这个上界并不保证恰好发生四次更新;它对满足所述界的每个序列都成立。
例题 5.2.4
(一次完整的运行)
取 、、,并循环使用。取 时每个 ,故 ,而 ,所以至多 次更新。从 开始。第 1 轮:,故 。第 2 轮: 而 ,间隔为 ,故 。第 3 轮:,不更新。第二个循环中的间隔为 、、,全部为正,所以运行在 次更新后停止。不变量也成立:,。
例题 5.2.5
(上界取到等号的情形)
在一维中取每个 的 、,并取 。则 、,上界为 。由于 给出间隔 ,第一轮便更新为 。此后每个间隔都等于 ,所以恰好更新一次,上界是紧的。另外,从 开始的任何运行,第一轮必定更新,因为无论 是什么,初始间隔都为零。
该定理假设存在同一个分离向量和同一个正间隔对所有轮次都适用。对一个固定的严格分离向量作归一化之后,有限的可分数据集确实有正的最小间隔,但无限序列可能逐点被严格正确分类,却不存在一致的正间隔。例如,在一维中取 、,则 对其严格分离,然而 。对于这个分离向量,上述定理不给出有限的数值界;但这并不意味着该特定序列必然迫使发生无穷多次错误。
反例模式
逐点可分不一定给出一致正间隔
间隔 出现在分母中是有原因的。对于点列逼近分离超平面的序列,固定的严格分离向量可以在每个点上都有正的带符号得分,而这些得分的下确界却为零。假设存在单一正数 的证明,在没有进一步工作的情况下,不能用逐点的严格不等式来代替该假设。
这是对在线更新次数的界,并不自动成为未知分布下测试误差的界。要得到统计性的结论,需要一个抽样模型以及选取输出预测器的规则。
常见错误
(忘记阈值项)
该定理假设超平面是过原点的齐次超平面。仿射阈值 可以通过给输入增加一个常数坐标来表示,但此时必须重新计算增广后的范数界 与间隔;沿用原输入的 和 是没有依据的。
练习与解答
快速检查
(若 且 ,给出更新次数的界。)
代入 。
解答 · 答案
,即至多更新 次。
快速检查
(在一维中设 、、。按所述更新约定, 是多少?)
先计算间隔 。
解答 · 答案
间隔为 ,所以规则更新:。
快速检查
(为什么该证明适用于自适应序列?)
列出证明用到序列的哪些性质。
解答 · 答案
每一步只用到所述的逐点范数与间隔不等式;即使每个样本是在看到学习器先前的行为之后才选取,这些不等式仍然成立,其中没有用到概率上的独立性。
快速检查
(十次更新的界是否意味着测试误差至多为百分之十?)
比较两个陈述各自计算的是什么。
解答 · 答案
不是。在线错误次数与测试误差概率是不同的量。要把二者联系起来,需要分布假设以及对输出选取方式的分析。