线性分类器按输入落在超平面的哪一侧来标记它。Fisher 判别一节以类均值与散布矩阵构造了这样的超平面;岭回归一节则以最小二乘拟合线性分数。本节处理另外三种选取超平面的方法,各由不同的损失定义:只对错误作出响应的感知机;以最大似然拟合概率模型的逻辑回归;以及选出离数据最远的分离超平面的最大间隔分类器。三者都由同一个量来组织,那就是间隔。
分数与间隔
定义 29.1.1
(线性分类器、函数间隔与几何间隔)
设输入为 ,标签为 。线性分类器的参数为 ()与 ,分数为 ,预测为 。对带标签的样本 ,函数间隔为 ,它为正当且仅当样本被严格正确分类;几何间隔为 。集合 是决策超平面。
定理 29.1.2
(间隔的几何意义)
到超平面 的欧氏距离(Euclidean distance)等于 。因此几何间隔就是样本到超平面的有符号距离,在正确一侧为正。把 乘以正常数,它不变。
证明
(到超平面的距离)
点 满足 ,所以在超平面上,且 。对超平面上任一点 ,,由柯西–施瓦茨(Cauchy–Schwarz)不等式得 ,所以超平面上每一点与 的距离都不小于此值。把 乘以 ,分子与分母同乘 。
相反,函数间隔可以靠缩放变得任意大,所以谈论间隔时必须说明指哪一种。在感知机的分析中,我们把偏置并入:把每个输入扩充为 ,参数扩充为 ,使 。
感知机
感知机从 开始,按固定次序反复扫描样本。每当某个样本有 (即错误,分数为零也算错误),就更新 。完整扫描一遍而没有错误时停止。
概念视角分析
把感知机看成次梯度的一步
设间隔 ,考虑损失 。当 时,它对 的梯度为 ;在 处, 是一个次梯度。沿其反方向走单位步长,恰好就是感知机的更新;当 时损失是平的,所以不更新。
定理 29.1.3
(感知机错误次数上界)
设对所有 有 ,并存在单位向量 与 ,使 对所有 成立。则对任何扫描次序,感知机至多更新 次,因此会终止并给出一个分离超平面。
证明
(对齐量线性增长,范数平方根增长)
设 为更新 次后的参数向量,。若第 次更新用的是 ,则 ,所以 。又因为更新由 触发,
所以 。由柯西–施瓦茨不等式,,得 。每一遍未终止的扫描至少有一次更新,所以扫描遍数也是有限的。
证明透视
线性增长对平方根增长
证明沿着更新序列追踪两个量。对齐量 每次更新至少增加 ;间隔假设只在这里用到。范数平方 每次更新至多增加 ;感知机的更新规则只在这里用到,因为交叉项 恰好在该样本是错误时不为正。最后的柯西–施瓦茨一步用到 ,把线性下界 与平方根上界 相比,两者只在 时相容。从 开始,使两个界都从零起步。若对已正确分类的样本也作更新,交叉项便可能为正,范数的界随即失效;若允许 ,下界就什么也说明不了。
这个上界不依赖样本数目或维度。若数据不是线性可分,就不存在这样的 ,算法永不停止。
反例模式
不可分数据:感知机会循环
人们很容易以为感知机一定会停止,因为每次更新都纠正了触发它的样本。取四点:、 标签为 ,、 标签为 。没有超平面能严格分开它们:若四个 都为正,则两个正例给出 ,两个负例给出 ,互相矛盾。算法只会在某一遍扫描中每个样本都有 时停止,即找到严格分离超平面,所以这里永远不会停止。具体地,取扩充输入 ,按此次序由 扫描,四次更新依次得到 、、,然后又回到 ,迭代点永远重复。修正后的说法就是上面的定理:在线性可分并有正间隔 时,才保证终止。
逻辑回归
逻辑回归把 建模为 ,其中 。由于 ,对 有 。因此训练集的负对数似然为
定理 29.1.4
(逻辑损失的梯度与凸性)
,。因此
所以 是凸函数,每个驻点都是全局极小点。若数据线性可分, 没有极小点:当 时 ,而 处处为正。
导数由链式法则得到:,再微分一次得 。Hessian 公式用到 。每一项 都是半正定的,其系数为正。对可分数据, 每一项都有 ,故 ,但每个 ,所以下确界 永远取不到。这就是为何在可分数据上不加正则化的逻辑拟合会发散,也是为何要像岭回归那样加入惩罚项。
最大间隔分类器
定义 29.1.5
(硬间隔分类器)
对两种标签都出现的线性可分数据,缩放参数使最接近的样本函数间隔恰好为 。硬间隔问题为
满足这些约束的 称为可行。
定理 29.1.6
(硬间隔即最大的最小几何间隔)
对两种标签都出现的线性可分数据,硬间隔问题有最优解,且其 唯一。最优超平面在所有分离超平面中拥有最大的最小几何间隔,该间隔等于 。
证明
(最大化间隔就是最小化范数)
任何单位法向量为 、最小几何间隔为 的分离超平面,都给出范数为 的可行对 ,所以可行集非空。反过来,可行的 必有 ,因为 会要求两种标签都有 ;它的最小几何间隔至少是 。因此最大的最小几何间隔,就是最小可行 的倒数。
使某个 令 可行的全部 ,是一个多面体的投影,故为非空闭凸集。 在其上严格凸,所以恰有一个范数最小的元素;再为它取一个可行的 。所得超平面的最小几何间隔至少为 ,而任何超平面都不能超过这个值,所以间隔恰为 。
例题
例题 29.1.7
(跟踪感知机并核对上界)
取四点及标签 、、、,扩充为 ,并按此次序扫描。从 开始。
- 点 1:,更新为 。
- 点 2:分数 ,不更新。
- 点 3:,更新为 。
- 点 4:,更新为 。
- 第二遍:点 1 的分数为 ;点 2 的分数为 ,更新为 ;点 3、4 的间隔都是 。
- 第三遍:所有间隔都等于 ,算法在共四次更新后停止。
对上界取 ,它在四点上的间隔都等于 ,所以 ,而 。于是 ,恰等于实际更新次数。
例题 29.1.8
(逻辑回归的一步梯度)
取一维输入 与 ,,。所有间隔为 ,,所以 。梯度为 。步长取 ,新参数为 。间隔变为 与 ,所以 ,有所下降。这一步以第一个样本变差的间隔,换取第二个样本好得多的间隔。固定步长一般不保证损失下降;此处损失恰好下降。
例题 29.1.9
(精确的硬间隔)
取 标签 与 标签 。约束为 与 。相加得 ,故 ,,在 、 时取等,此时两个约束都取等号。间隔为 ,正是两点距离 的一半,超平面为 。
常见错误与细节
常见错误
(必须说明是哪一种间隔)
函数间隔会随缩放改变,只有几何间隔才是距离。感知机上界用的是单位分离向量 与扩充输入,所以 必须是包含常数 在内的扩充范数的上界。
常见错误
(分数为零也是错误)
感知机更新把分数为零也视为错误,所以从 开始时,第一个样本必然触发更新。
常见错误
(损失小或有分离解都不够)
逻辑损失是零一误差的光滑替代,损失小并不表示错误率小,也不表示概率已经校准。感知机的解只是某个分离超平面,取决于扫描次序;最大间隔的解在 上则是唯一的。
练习
快速检查
(设 ,。求 到超平面的距离,以及其标签为 时的几何间隔。)
先计算 。
解答 · 答案
,,所以距离为 。标签为 时,几何间隔为 ,样本被错误分类。
快速检查
(扩充输入满足 ,并有单位向量使 。给出感知机更新次数的上界。改变扫描次序,它会改变吗?)
上界只涉及 与 。
解答 · 答案
。这个上界对任何扫描次序都成立,但实际更新次数与最终的超平面可以取决于次序。
快速检查
(分别计算 与 时的 与 。)
利用 。
解答 · 答案
时,,。 时,,,所以 ,。
快速检查
(点 标签 ,点 标签 。求硬间隔的 与几何间隔。)
把两个约束相加。
解答 · 答案
约束为 与 ,即 。相加得 ,故 ,最小范数在 、 取得,此时两个约束都取等号。几何间隔为 。