【Novikoff 定理】
设训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$ 是是线性可分的，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $n$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^n$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$，则：
- 存在满足条件 $||W_{opt}||_2=1$ 的超平面 $S:W_{opt}X=\boldsymbol{\omega}_{opt}\cdot\mathbf{x}+\theta_{opt}=0$ 将训练集完全正确分开，且存在 $\gamma>0$，对所有的 $i=1,2,…,N$，有：
- 令 $R=\max\limits_{i}||X_i||_2$，则感知机学习算法原始形式在训练集上的误分类次数 $k$ 满足以下不等式：
该定理表明，分离超平面下样本点的函数间隔 $y_i(\boldsymbol{\omega}_{opt}\cdot\mathbf{x}_i+\theta_{opt})$ 存在下界，误分类次数 $k$ 存在上界，经过有限次搜索可以找到将训练集完全正确分开的分离超平面
也就是说，当训练集线性可分时，感知机学习算法原始形式是迭代收敛的
而当训练集线性不可分时，感知机学习算法原始形式是不迭代收敛的，迭代结果会发生震荡，为处理训练集线性不可分的情况，由此出现了多层感知机（Multi-Layer Perceptron）
【证明】
对于线性可分数据集，感知机学习算法的原始形式收敛，即：经过有限次迭代后，可以得到一个训练集完全正确划分的分离超平面及感知机模型
首先将阈值 $\theta$ 并入权重 $\boldsymbol{\omega}$ 中，记作：
同时，将输入向量 $\mathbf{x}$ 进行扩充，加入常数 $1$，记作：
由此，$W,X\in \mathbb{R}^{n+1}$，且有：
设训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$ 是线性可分的，那么根据数据集的线性可分性，存在超平面 $S$ 可将训练集完全正确分开，设该超平面为：
取 $||W_{opt}||_2=1$，对于有限的 $i=1,2,…,N$，均有：
令：
故有：
感知机学习算法一般从 $\boldsymbol{\omega}=0,\theta=0$ 开始迭代，当样本被误分类时，更新权重与阈值
取 $W_{k-1}$ 为第 $k$ 个误分类样本之前的扩充权重向量，即：
假设 $(\mathbf{x}_j,y_j)$ 是第 $k$ 个被误分类，即被 $W_{k-1}=(\boldsymbol{\omega}_{k-1}^T,\theta_{k-1})^T$ 误分类的样本，则其满足：
且权重 $\boldsymbol{\omega}$ 与阈值 $\theta$ 的更新为：
即：
考虑将训练集线性可分的超平面 $S:W_{opt}X=0$，有：
由于 $\min\limits_j\{y_jW_{opt}X_j\}=\min\limits_j \{y_j(\boldsymbol{\omega}_{opt}\mathbf{x}_j+\theta_{opt})\}=\gamma$，故有：
根据上式进行递推，有：
即：
进一步，考虑到：
对其两边同取 $l_2$ 范数的平方，有：
根据第 $k$ 个被误分类样本所满足的条件：
有：
故：
令 $R=\max\limits_{1\leq i\leq N}||X_i||_2$，则有：
结合递推不等式：
故有：
即：
根据 $W_kW_{opt}\geq k\alpha\gamma$，结合上式，有：
即：
故有：
