这里舍弃掉\(\frac{1}{||W||}\)是因为它是一个正的系数，并且对于\(L(w,b)\)具有伸缩性，因此不影响最小化\(L(w,b)\)。
6. 知错后如何改错？回顾微分学知识，我们知道一个全局的凸函数取得最小值是在导数为0处。但是，放在多元函数的观点来看，一元函数的导数本质上也是梯度。当一个函数沿着负梯度的方向运动是，函数值的减少是最快的；沿着正梯度方向运动时，函数值增加啊是最快的。下面我们就来求其梯度。
\[\frac{\partial L}{\partial w} = - \sum\limits_{x_i \in E} y_i x_i\]
\[\frac{\partial L}{\partial b} = - \sum\limits_{x_i \in E} y_i\]
我们来看关于\(w\)的梯度表达式，本质上就是找到所有的误分类点，然后把标签值\(y_i\)作为一个权重(\(+1/-1\))。如果\(x_1\)是一个被错误分类的点，假设这个点对应的原始标签是正类，现在被分成负类，所以在前面加一个符号，表示往反方向弥补。所以\(\sum\limits_{x_i \in E}y_ix_i\)
可以理解为通过所有错误分类的样本点拟合出一个运动方向，往那个方向运动可以弥补模型中\(w\)参数的错误。
而例1中，我们每次只选取一个样本点，假设这个样本点是\((x_i,y_i)\)，那么更新公式就是 \(w = w + \eta y_i x_i\)，其中的\(\eta\)是每次更新的步长，术语为学习率。同理，偏置项的更新公式为 \(b = b + \eta y_i\)。
7. \(Novikoff\) 定理先叙述一下这个定理。定理来自李航老师的《统计学习方法》第二版Page42。
设训练数据集\(T = {(x_1,y_1),(X_2,y_2),...,(x_N,y_N)}\)是线性可分的，其中\(x_i \in X = R^n, y_i \in Y = \{-1,+1\}, i = 1,2,...,N\)，则
(1) 存在满足条件\(||\hat{w}_{opt}|| = 1\)的超平面\(\hat{w}_{opt} \cdot \hat{x} = w_{opt} \cdot x + b_{opt}\)将训练数据集完全正确分开；且存在\(\gamma > 0\)，对所有的\(i = 1,2,...,N\)有\[y_i (\hat{w}_{opt} \cdot \hat{x}_i) = y_i (w_{opt} \cdot x_i + b_{opt}) \ge \gamma\]
(2)令\(R = \max\limits_{1 \le i \le N} ||\hat{x}_i||\)，则感知机算法在训练数据集上的误分类次数\(k\)满足不等式 \[k \le (\frac{R}{\gamma})^2\]
先从直觉上理解下这个定理表述的意思。大意是对于可以找出线性超平面做分类的数据集，存在一个下界$ \gamma $，所有样本点到超平面的距离都至少大于这个 $ \gamma $，同时错误分类的次数有一个上界，第 \(k+1\) 次之后，分类都是正确的，算法最终是收敛的。
证明
(1) 由于数据是线性可分的，因此一定存在一个分割超平面\(S\)，不妨就取\(S\)的参数为\(\hat{w}_{opt}\)，显然对于超平面上的所有点\(x\)，都有\(\hat{w}_{opt} \cdot x = w_{opt} \cdot x + b_{opt} = 0\)，并满足\(||\hat{w}_{opt}||=1\)。而对于训练数据集中的样本点，由于现在都被正确分类了，所以有\(\hat{w}_{opt} \cdot x_i > 0\)，于是取 \(\gamma = \min\limits_{i} \{y_i(w_{opt} \cdot x_i + b_{opt} \}\)，这就得到了下界。
(2) 由 \(k \le (\frac{R}{\gamma})^2\)推出\(k \gamma \le \sqrt{k} R\) 。
假设\((x_i,y_i)\)是一个在第\(k\)次被误分类的点，那么这件事的触发条件是 \(y_i (\hat{w}_{k-1} \cdot x_i) \le 0\).
由更新公式，\(\hat{w}_k = \hat{w}_{k-1} + \eta y_i \hat{x}_{i}\) .
\(\hat{w}_{k} \cdot \hat{w}_{opt} = \hat{w}_{k-1} \cdot \hat{w}_{opt} + \eta y_i \hat{w}_{opt} \cdot \hat{x}_i \ge \hat{w}_{k-1} \cdot \hat{w}_{opt} + \eta \gamma\) .
迭代\(k-1\)次立即得到 \(\hat{w}_{k} \cdot \hat{w}_{opt} \ge k\eta\gamma\).
对\(\hat{w}_k\)两边平方，
\(||\hat{w}_k||^2 = ||\hat{w}_{k-1}||^2 + 2\eta y_i \hat{w}_{k-1} \cdot \hat{x}_{i} + \eta^2 ||\hat{x}_{i}||^2\). 注意到中间这项是负数(因为这是误分类点)
立即得到 \(||\hat{w}_k||^2 \le ||\hat{w}_{k-1}||^2 + \eta^2 ||\hat{x}_{i}||^2 \le ||\hat{w}_{k-1}||^2 + \eta^2 R^2\).
迭代\(k-1\)次后立即得到 \(||\hat{w}_k||^2 \le k \eta^2 R^2\) .
即可建立不等式
\(k\eta\gamma \le \hat{w}_{k} \cdot \hat{w}_{opt} \le ||\hat{w}_{k}|| \cdot ||\hat{w}_{opt}|| \le \sqrt{k}\eta R\). 再稍加变形就得到欲证的式子。
这里\(R\)其实只是一个记号而已，它代表的意思是从所有误分类中找到模长最大的，而这个记号其实是从证明过程中产生的。
作为介绍感知机原理的文章，已经写得非常长啦，可以就此打住~
如果有任何纰漏差错，欢迎评论互动。