对于线性可分的数据集，感知机学习算法的原始形式是收敛的。也就是说，经过有限次的迭代，可以找到一个将数据集完全正确划分的分离超平面。

本文是 <统计学习方法> 第二章感知机收敛性证明的笔记，主要加入了一点自己的理解。

在证明之前，先定义下相关的符号标记。

1. 将参数 b 并入权重向量 w，记作

$$\begin{array}{}\text{(1)}& \hat{w}=(w^T,b{)}^T\end{array}$$

2. 将输入向量加进常数 1，记作

$$\begin{array}{}\text{(2)}& \hat{x}=(x^T,1{)}^T\end{array}$$

很显然，向量内积 $\hat{w}\cdot \hat{x}=w\cdot x+b$

收敛性证明

Novikoff 定理

Novikoff 定理

式 (2.8) 证明

由于训练数据集是线性可分的，存在超平面将训练数据集完全正确分开，取此超平面为

$$\begin{array}{}\text{(3)}& {\hat{w}}_{opt}\cdot \hat{x}=(w_{opt}^T,b_{opt}{)}^T\cdot (x^T,1{)}^T=w_{opt}\cdot x+b_{opt}=0\end{array}$$

使 $||{\hat{w}}_{opt}||=1$。由于样本均分类正确，所以对所有的样本，均满足

分类正确

因此可以从所有样本中找到一个最小取值，使得

最小值

样本中所有数据均满足

所有值

式 (2.9) 证明

感知机算法中，如果实例被误分类，则更新权重。令 ${\hat{w}}_{k-1}$ 是第 $k$ 个误分类实例之前的扩充权重向量，即

$$\begin{array}{}\text{(4)}& {\hat{w}}_{k-1}=(w_{k-1}^T,b_{k-1}{)}^T\end{array}$$

则对于第 k 个误分类实例，它的误分类判断条件为

误分类条件

若 $(x_i,y_i)$ 是被 ${\hat{w}}_{k-1}=(w_{k-1}^T,b_{k-1}{)}^T$ 误分类的数据，则 w 和 b 的更新规则是

$$\begin{array}{}\text{(5)}& w_k& \leftarrow w_{k-1}+\eta y_i{x}_i\text{(6)}& b_k& \leftarrow b_{k-1}+\eta y_i\end{array}$$

即

更新规则

下面推导两个不等式

不等式 1

其中第二步用到了式 (2.8)

不等式 2

其中第一步用到了 $||y_i||=1$(因为 $y_1$ 的取值范围为 - 1 或 1)，第二步用到了式 (2.10)，第三步用到了 $R$ 的定义，第四步及之后用到了数学归纳法

结合不等式 (2.12) 和 (2.13) 可得

不等式 2 推导

首先看下第一个不等式，其中第一步就是 (2.12)，第二步用到了施瓦茨不等式，第三步用到了 (2.13) 和证明一的条件 $||{\hat{w}}_{opt}||=1$

再看第二个不等式，对第一个不等式两侧取平方可得

因此可得

$$\begin{array}{}\text{(7)}& k\le (\frac{R}{\gamma }{)}^2\end{array}$$

参考

李航。统计学习方法