Novikoff 定理

Novikoff 定理 #

Novikoff 定理告诉我们, 对于线性可分的训练数据集, 感知机的学习算法时收敛的. 具体而言, 设训练数据集 $T={(x_1, y_1), (x_2, y_2) , (x_N, y_N)}$ 是线性可分的, 其中 $x_i \in \mathbb{R}^n$ , $y_i \in {-1, +1}$ , $i=1,2,\cdots,N$ , 则

• 存在满足条件 $|\hat{w}{opt} | = 1$ 的超平面 $w{opt} \cdot x + b_{opt} = 0$ , 将训练数据集完全正确地划分开; 且存在正数 $\gamma$ , 对所有 $i=1,2,\cdots,N$ , 满足 $$ y_i(\hat{w}{opt}\cdot \hat{x}i) = y_i(w{opt} \cdot x_i + b{opt}) \geq \gamma $$
• 令 $R = \max\limits_{1 \leq i \leq N} |\hat{x}_i|$ , 则感知机算法在训练数据集 $T$ 上的误分类次数 $k$ 满足不等式 $$ k \leq \left(\frac{R}{\gamma}\right)^2 $$

证明 #

设 $w_{opt}$ 是将训练数据集完全正确地划分开的超平面, 且 $|w_{opt}| = 1$ , 令 $\gamma = \min\limits_{1 \leq i \leq N} y_i(w_{opt} \cdot x_i + b_{opt})$ , 则对所有 $i=1,2,\cdots,N$ , 有 $$ y_i(\hat{w}{opt}\cdot \hat{x}i) = y_i(w{opt} \cdot x_i + b{opt}) > 0 $$ 所以存在正数 $\gamma = \min\limits_{1 \leq i \leq N} y_i(w_{opt} \cdot x_i + b_{opt})$ , 对所有 $i=1,2,\cdots,N$ , 满足 $$ y_i(\hat{w}{opt}\cdot \hat{x}i) = y_i(w{opt} \cdot x_i + b{opt}) \geq \gamma $$

接下来考虑感知机的学习过程. 从 $w_0 = 0$ 开始, 对每个被误分类的实例进行权重更新. 设 $\hat{w}{k - 1}$ 是第 $k$ 个误分类实例 $(x_i, y_i)$ 之前的扩充权重向量, 则有 $$y_i(\hat{w}{k - 1} \cdot \hat{x}_i) \leq 0$$ 进行更新后的权重向量为 $$ \hat{w}k = \hat{w}{k - 1} + \eta y_i \hat{x}_i $$

考虑 $\hat{w}k$ 与 $\hat{w}{opt}$ 的内积, 有 $$ \begin{aligned} \hat{w}k \cdot \hat{w}{opt} & = (\hat{w}{k - 1} + \eta y_i \hat{x}i) \cdot \hat{w}{opt} \\ & = \hat{w}{k - 1} \cdot \hat{w}{opt} + \eta y_i \hat{x}i \cdot \hat{w}{opt} \\ & \geq \hat{w}{k - 1} \cdot \hat{w}{opt} + \eta \gamma \\ & \geq \hat{w}{k - 2} \cdot \hat{w}_{opt} + 2\eta \gamma \\ & \geq \cdots \\ & \geq k \eta \gamma \\ \end{aligned} $$

再有 $$ \begin{aligned} |\hat{w}k|^2 & = |\hat{w}{k - 1} + \eta y_i \hat{x}i|^2 \\ & = |\hat{w}{k - 1}|^2 + 2\eta y_i \hat{w}_{k - 1} \cdot \hat{x}i + \eta^2 |\hat{x}i|^2 \\ & \leq |\hat{w}{k - 1}|^2 + \eta^2 R^2 \\ & \leq |\hat{w}{k - 2}|^2 + 2\eta^2 R^2 \\ & \leq \cdots \\ & \leq k \eta^2 R^2 \\ \end{aligned} $$ 故有 $$ 1\geq \frac{\hat{w}k \cdot \hat{w}{opt}}{|\hat{w}k| |\hat{w}{opt}|} \geq \frac{k \eta \gamma}{\sqrt{k} \eta R} = \sqrt{k} \frac{\gamma}{R} $$ 所以 $$ k \leq \left(\frac{R}{\gamma}\right)^2 $$ 也就是说, 误分类的次数 $k$ 是有上限的, 在训练数据集线性可分的情况下, 感知机算法是收敛的.