线性分类器为特征向量计算一个分数,再根据分数的符号选择类别。感知机通过处理那些带符号分数尚未为正的样本来学习这个分数。它的收敛论证具有几何意义:当存在正间隔时,每次更新都会沿某个分离方向取得进展,而权重范数增长得不够快,因而不可能允许无限次更新。
假设和停止条件都很重要。有限轮训练未能结束,可能是因为数据线性不可分;但仅凭训练预算较小,不能得出这个结论。下面先明确表示偏置坐标,逐步计算一次训练过程,再证明更新次数界,最后讨论假设不成立时的情况。
用额外的坐标表示偏置
设样本为 ,标签为 。仿射分类器的分数为 。定义增广向量和权重为
因此,偏置是一个需要学习的坐标,不能在更新时当作固定项省略。普通预测时,约定分数为零归入 类。不过训练时要求带符号分数严格为正,即 ;无论是分类错误还是落在零分数边界上,都要更新。
定义 9.1.1
(感知机更新与严格分离)
令初始权重 。当样本满足 时,更新
否则保持 不变。这称为单位步长感知机。如果训练集中的每个样本都满足 ,则称该权重严格分离训练集。
更新次数包括零间隔样本,即使预测时的平分规则恰好将其中某个样本判对也是如此。下文沿用“错误次数界”这一惯用名称,实际统计的是包含边界情况的更新次数。
在原坐标中,规则为 和 。正样本加上自己的增广向量,负样本则减去自己的增广向量。
常见错误
(只在分数严格为负时才更新)
一个诱人的简化是只在 时更新。从 出发,每个分数都是零,所以没有任何样本会触发更新:循环随即结束,,每个带符号分数仍然是零,并不是严格分离向量。对点 (标签 )和 (标签 ),这条规则返回 ,而采用 的规则则在三次更新后把它们分开(见下面的第一个例题)。边界情形 必须触发更新。
一次更新会增大当前间隔,但未必立即纠正分类
对于触发更新的样本,
由于 ,且增广向量 非零,带符号分数会增大;但它仍可能是负数。更新也可能使其他样本的分数向任一方向变化,因此我们需要整体性的收敛证明。
反例模式
一次修正未必能立即正确分类该样本
从零权重出发,先遇到一维负样本 。增广更新后得到 。接着遇到正样本 ,其 。原来的带符号分数为 ;更新得到 ,新的带符号分数为 。
分数增加了 ,但该点仍被错误分类。这两个样本实际上可以分离:分数 在 1 处为正,在 3 处为负。问题并非数据自相矛盾,只是一次单位更新未必足以完成修正。
在增广空间中陈述间隔假设
定义 9.1.2
(有界且具有一致分离间隔的训练集)
假设每个输入的增广样本都满足 。还假设存在一个固定的单位向量 ,使得对每个训练样本都有
成立。数 是这个单位分离向量的一致正间隔。
半径 和 的归一化都包含偏置坐标。算法本身无须知道 、 或 ;分析所需的是它们的存在性。
对于具有严格分离向量的有限数据集,将该向量归一化,再取有限个正的带符号分数的最小值,就得到这样的 。这个值可能很小,所以得到的数值上界未必紧,也未必适合实际估计。
定理 9.1.3
(感知机错误次数界)
设 是带标签 的增广训练样本。假设对所有 都有 ,并且有一个单位向量 使所有 都满足 。按任意顺序、任意多轮呈现这些样本,并运行感知机更新规则,则触发的更新次数 满足
证明
(线性的进展对平方根的增长)
只为更新编号。设 是触发第 次更新的样本, 为 次更新后的权重。
沿 的进展:因 ,
而 ,所以 。
范数的增长:触发更新表示 ,因此
于是 。
用柯西—施瓦茨(Cauchy–Schwarz)不等式及 把两者结合:
当 ,两边除以 再平方,得 。 时上界显然成立。
证明透视
哪个假设推动哪一半
这个证明是两条方向相反的不等式。间隔假设 只用于下界:无论是哪个违规样本触发,每次更新都使 沿固定方向 至少前进 。更新条件 只用于上界:它使交叉项 不为正,所以每次更新使范数平方至多增加 。柯西—施瓦茨不等式配合 把两者连起来,论证得以完结,是因为 对很大的 不可能成立。初始权重 使两个界都从零开始;偏置坐标则通过 与 进入,它们必须在增广空间中取。若算法连分数已为正的样本也更新,交叉项便可能为正,上界就不再成立。
定理适用于满足这些共同界限的任意样本顺序。对于反复完整遍历的有限训练集,若某一轮没有发生更新,便证明当前权重严格分离训练集:这一轮中权重始终不变,且每个样本的带符号分数都为正。每个发生更新的轮次至少消耗有限更新次数中的一次,因此反复遍历最终会到达无更新的一轮。
逐步追踪偏置与边界更新
例题 9.1.4
(两个训练点需要三次更新)
取一维点 ,标签为 ;,标签为 ,每轮始终按此顺序处理。增广向量分别为 和 。
| 轮次与样本 | 更新前权重 | 更新前带符号分数 | 处理后权重 |
|---|---|---|---|
| 第 1 轮,负样本 | |||
| 第 1 轮,正样本 | |||
| 第 2 轮,负样本 | |||
| 第 2 轮,正样本 |
共更新三次。最终带符号分数分别为 1 和 3,因此两个点都被严格分离;再遍历一轮不会产生变化。
为了计算上界,取 。两个样本的带符号投影都是 ,故 。最大的增广向量范数为 。因此证明得到的上界是 ,实际更新次数则是三次。
如果只使用原特征的半径 2,就遗漏了恒为 1 的偏置坐标。定理中的几何对象是 ,而不仅是 。
最终分数为 ,其边界是 。它并没有最大化原输入直线上通常的几何间隔:阈值 1 与两个训练点的距离都是 1,而阈值 到负样本的距离仅为 。证明能收敛到一个分离器,并不等于证明它求出了最大间隔;这一差别引出课程后面的支持向量机主题。
概念视角代数
权重是样本的带符号和
每次更新都加上触发该次更新的样本的 ,所以 ,其中 是样本 触发更新的次数,且 。于是得分为 ,只通过样本之间的内积来使用这些样本。在第一个例题中 ,而 。
例题 9.1.5
(平面上的两个点)
取 (标签 )与 (标签 ),按此顺序呈现。增广向量为 和 。从 开始,正样本的分数是 ,所以 。负样本的带符号分数是 ,所以 。第二轮中两个带符号分数都是 ,不再更新:共两次更新。偏置坐标在中途不为零,最后却是零。取 ,两个带符号投影都是 ,两个增广向量的范数都是 ,所以上界为 。
例题 9.1.6
(单个样本达到上界)
设唯一的训练样本是 ,标签 ,故 ,。初始分数为 ,所以一次更新得 ,带符号分数为 ,不再有更新。取 ,得 、,所以 ,等于实际更新次数。这里上界恰好达到;对大多数数据集,上界远高于真实次数,正如第一个例题,上界是 ,实际更新却只有三次。
预算用尽并不能证明分离器不存在
上述界依赖共同的正间隔。如果这一假设不成立,感知机可能不会停止。例如,同一个输入若有相反标签,就要求它的分数同时严格为正和严格为负。反复呈现这些样本可能持续触发更新。
反例模式
标签没有矛盾,仍可能需要非线性特征
令 和 的标签为 ,令 的标签为 。仿射分数 必须满足 、 和 。后两个不等式分别推出 和 ;当 时不可能同时成立。
这些标签本身定义明确,但原直线上不存在仿射分离器。若使用特征 ,分数 却能分离它们。分类器在变换后的特征中是线性的,但它在原输入中的边界是非线性的。必须在实际使用的特征空间中检查间隔定理的假设。
反过来,有限次运行尚未分离数据,也不能证明数据不可分。即使数据可分,所需更新次数也可能超过选定的预算。返回状态应当区分当前分离器已经通过验证与训练循环只是结束了这两种情况。
返回明确验证结果的实现
函数接受 Python 整数或有限浮点数特征、整数标签 和正整数轮数上限。它通过附加坐标学习偏置,并采用单位更新。Python 整数运算保持精确;浮点分数则是近似值。非有限输入会被拒绝,任何溢出或非有限中间值都会报错,而不会产生验证结果。
import math
def perceptron(rows, labels, max_epochs=100):
rows = [tuple(row) for row in rows]
labels = tuple(labels)
if not rows or len(rows) != len(labels) or type(max_epochs) is not int or max_epochs < 1:
raise ValueError("nonempty paired data and a positive integer epoch limit are required")
dimension = len(rows[0])
if not dimension or any(len(row) != dimension for row in rows):
raise ValueError("rows must have the same positive dimension")
if any(type(label) is not int or label not in (-1, 1) for label in labels):
raise ValueError("labels must be integer -1 or +1")
if any(type(x) not in (int, float) or (type(x) is float and not math.isfinite(x))
for row in rows for x in row):
raise ValueError("features must be integers or finite floats")
def checked(a, b, operation):
try:
result = a * b if operation == "multiply" else a + b
except OverflowError as exc:
raise ArithmeticError("floating-point operation overflowed") from exc
if type(result) is float and not math.isfinite(result):
raise ArithmeticError("nonfinite floating-point intermediate")
return result
def signed_score(weights, vector, label):
total = 0
for w, x in zip(weights, vector):
total = checked(total, checked(w, x, "multiply"), "add")
return checked(label, total, "multiply")
augmented = [row + (1,) for row in rows]
weights = [0] * (dimension + 1)
updates = 0
for _ in range(max_epochs):
changed = False
for vector, label in zip(augmented, labels):
if signed_score(weights, vector, label) <= 0:
weights = [checked(w, checked(label, x, "multiply"), "add")
for w, x in zip(weights, vector)]
updates += 1
changed = True
if not changed:
break
scores = [signed_score(weights, vector, label)
for vector, label in zip(augmented, labels)]
verified = all(score > 0 for score in scores)
return weights, updates, verified
调用 perceptron([(0,), (2,)], [-1, 1], max_epochs=2) 的结果为 ([2, -1], 3, True)。最后的显式检查识别出:允许的最后一轮已经产生了分离器。若只运行一轮,结果是 ([2, 0], 2, False):负样本的带符号分数仍为零,尽管该数据集是可分的。
权重列表的最后一项是偏置。返回前,函数会重新计算每个带符号分数。True 表示所有计算出的分数均有限且严格为正;False 表示至少一个计算出的分数不大于零。使用浮点数时,舍入可能改变接近零的分数,因此此数值检查不是严格的精确实数分离证书。两种状态都不是概率估计,也不保证未见样本上的表现。
对 个样本、 个原始特征和 轮遍历,该实现需要 次算术运算;必要时最后再进行一次 检查。存储权重需要 空间;这个教学实现还会实际构造并保存增广训练数据。在假设成立时,间隔界限制更新次数;即使假设不成立,轮数预算也能控制计算量。
练习与详解
快速检查
(当前增广权重是 ,一个正样本的原坐标为 。求它原来的带符号分数、更新后的权重和新的带符号分数。一次更新足以将其正确分类吗?)
先把样本补上常数坐标。
解答 · 答案
增广样本为 ,所以原分数为 。加上该向量得到 ,新分数为 。分数增加了 2,即增广向量的范数平方,但仍为负。一次更新未必能彻底纠正分类。
快速检查
(对标签为 的点 和 ,取 。给出增广半径、共同间隔及更新次数界。例题中的顺序实际产生多少次更新?)
使用增广向量 和 。
解答 · 答案
增广向量的范数分别为 1 和 ,因此 。两个带符号投影都是 ,得到上界 。例题过程更新了三次。这个上界提供充分保证,并非对运行次数的精确预测。
快速检查
(展开 时,为什么求上界时可以舍去交叉项?若算法连已正确分类且间隔为正的样本也更新,同一论证是否仍然成立?)
留意触发更新时 的符号。
解答 · 答案
交叉项是 ,它不为正,正是因为只有带符号分数不大于零时才触发更新。若对间隔为正的样本任意更新,这一项可能为正,所述上界就不能再由同一论证得出。
快速检查
(两点例子只运行一轮,函数报告未能验证。这是否证明数据没有仿射分离器?返回的权重有哪里不满足?第二轮会怎样?)
重新计算一轮后权重的带符号分数。
解答 · 答案
这并不证明不可分。权重 使负样本的带符号分数仍为零。第二轮把权重改为 ,两个带符号分数都为正,共三次更新后最终验证成功。
快速检查
(负样本点 与正样本点 所学得的阈值是 。把它到最近点的距离,与阈值 的相比。有限步收敛是否意味着得到最大的几何间隔?)
量出每个阈值到最近训练点的距离。
解答 · 答案
阈值 到最近点的距离是 ;阈值 到两点的距离都是一。因此这个已收敛的感知机并不是最大间隔分离器。定理限制的是到分离为止的更新次数,并没有优化原空间的几何间隔。
快速检查
(对负样本点 和正样本点 ,说明为什么没有分数 能把它们分开。哪一个变换后的特征 能使分数 成功?)
把三个严格不等式写成 、 的条件。
解答 · 答案
正样本点要求 。负样本要求 及 ,互相矛盾。取 :正样本的分数是 ,每个负样本的分数是 。这是在变换后特征空间中的分离,并不是原坐标上的仿射分离器。