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

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

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

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

$$\hat{w} = (w^T, b)^T$$

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

$$\hat{x} = (x^T, 1)^T$$

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

收敛性证明

Novikoff 定理

式(2.8)证明

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

$$
\hat{w}_{opt} \cdot \hat{x} = (w_{opt}^T, b_{opt})^T \cdot (x^T, 1)^T = w_{opt} \cdot x + b_{opt} = 0
$$

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

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

样本中所有数据均满足

式(2.9)证明

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

$$
\hat{w}_{k-1} = (w_{k-1}^T, b_{k-1})^T
$$

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

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

$$
\begin{align}
w_k &\leftarrow w_{k-1} + \eta y_i x_i \\
b_k &\leftarrow b_{k-1} + \eta y_i
\end{align}
$$

即

下面推导两个不等式

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

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

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

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

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

因此可得

$$
k \leq (\frac{R}{\gamma})^2
$$

参考

李航. 统计学习方法