规则需要处理平分的约定
考虑有限且非空的标记向量集合 ,其中 、、。由 开始。每次输入一个例子时,计算带标记分数 。若分数不大于零,便更新
否则保持 不变。特别地,分数为零也触发更新。我们计算更新次数,包括零分平局;视分类器另行采用的平局规则而定,它们未必全都是严格意义上的分类错误。
这是齐次规则:决策边界通过原点。对仿射分数 ,附加常数坐标,令 、,便可在增广向量上使用相同规则。半径及间隔必须在增广空间计算,不能只用原特征的范数。
常见错误
(在原坐标中寻找间隔)
取一维数据: 标记为 , 标记为 。对齐次分数 ,点 的带标记分数对每个 都是 ,所以在原坐标中不存在正间隔。增广为 和 后,单位向量 给出的带标记间隔都是 。间隔假设必须在实际运行规则的空间中检验。
对同一批更新的两个估计
定理 5.1.1
(感知机的有限更新次数界)
假设存在常数 、 及单位向量 ,使每个例子都满足
由 开始,每当输入的带标记分数不大于零就更新。则不论输入顺序如何,更新总次数 满足
若有限数据集按完整轮次反复输入,则至多经过 轮便会出现没有更新的一轮,此时每个训练例子的带标记分数都严格为正。
对有限数据,有限的 必定存在;实质的假设是算法实际使用的数据具有严格为正的间隔。
证明
(线性的进展对平方根的增长)
令 为第 次更新刚完成后的权重,;被略过的输入不使 增加。对例子 作更新时,
由归纳得 。另一方面,更新条件给出 ,所以
于是 。由柯西—施瓦茨(Cauchy–Schwarz)不等式及 ,得 。当 ,两边相除便得 。
关于轮数:更新次数至多为 ,而最后一轮之前的每一轮至少含一次更新,所以至多需要 轮。在没有更新的一轮中权重保持不变,所以每个例子对该权重的带标记分数都为正。
证明透视
平局约定与零起点用在哪里
两个估计需要规则的不同特征。下界只需要间隔假设,每次更新使用一次。上界需要更新条件 ,而“不大于”这几个字很重要:由于 ,第一个分数恰好是零,若规则只在分数严格为负时才更新,权重便永远离不开原点。起点 使两个界都从零开始,因而可以互相比较。证明得以完结,是因为随 线性增长的量被夹在按 增长的量之下。这个界计算的是更新总次数,不是轮数或计算时间,也没有说明在新数据上的表现。
若分离向量 未经归一化,但满足 ,取 及 ,所得的界为 。间隔很小时,这个保证就很弱;界也不一定取得。
例题
例题 5.1.2
(一个二维追踪)
使用有顺序的齐次例子
由 开始,第一个分数为零,所以 变为 。第二个分数也为零,所以负标记把 更新为 。第三个带标记分数是 ,不更新。再多一轮,带标记分数为 ,没有更新。
取 ,带标记间隔分别为 、 和 。最大的输入范数为 ,所以 给出 次更新的上界。追踪中用了 次更新;定理给的是上界,不是精确预测。
例题 5.1.3
(未经归一化的分离向量)
取例子 与 ,以及分离向量 。带标记分数 分别为 和 ,所以 。又 、,所以界为 ,即至多 次更新。实际运行: 时第一个例子的分数是 ,所以 。第二个例子的分数是 ,所以 。下一轮的分数为 和 ,不再更新。实际次数为 。
例题 5.1.4
(为偏置增广)
取一维点 (标记 )和 (标记 ),使用仿射分数。增广为 与 ,并按此顺序输入。由 开始,第一个分数是 ,所以 。第二个分数是 ,所以 。下一轮中第一个分数又是 ,所以 ;之后两个分数为 和 ,不再更新。共发生三次更新。取 ,两个带标记间隔都是 ,最大增广范数为 ,所以界为 。若只用原特征半径 ,便会漏掉常数坐标。
没有可分性时可能发生什么
反例模式
输入有界并不保证终止
命题:只要所有训练向量的范数至多为 ,感知机便只作有限次更新。取两个例子 与 ,此时 。由 开始,第一个分数是 ,所以 。第二个例子的带标记分数是 ,所以 。权重回到起点,因此再输入这两个例子,会永远重复同样的两次更新。没有单位向量 使两个例子都有正间隔,因为它们的带标记间隔是 和 。定理的间隔假设不能省略,只知道训练向量的范数有有限上界并不足够。退化的版本是数据集只含 、标记为 :每次输入都计一次更新,而零向量使 保持不变。
习题
快速检查
(若单位分离向量的间隔至少为 ,所有输入范数至多为 ,定理给出多少次更新的界?若停止规则要求完整一轮没有更新,可得什么轮数界?)
把 、 代入界。
解答 · 答案
最多 次更新。若在首次完整无更新轮后停止,最多需要 轮:此前每轮至少有一次更新。
快速检查
(在二维追踪中,计算第二次更新后三个例子的带标记分数。为何下一次完整轮不会更新?)
使用 。
解答 · 答案
分数为 。它们均严格为正,所以所指定的非正分数更新规则不会更新。
快速检查
(分离向量 的范数为 ,且每个例子的带标记分数至少为 。若 ,求单位向量 的间隔及更新次数界。)
把 除以它的范数。
解答 · 答案
单位分离向量 的间隔至少是 ,故最多更新 次。