最近在看林轩田机器学习基石，作为对ML基础的进一步学习。在2-Learning to Answer Yes_No中，以一个例子来总结解释一下PLA（感知学习算法）的修正过程，以及一些证明。
PLA
PLA的主要思想：逐步修正。
图中坐标原点位于正方形中心位置，样本数据线性可分，决策边界满足$w^{T}x=0$，注意下面谈到的$w$和$x$都是向量。
step-0：初始化$w=0$
step-1：第一次更新，选择样本点$x_{1}$如图所示，记为黑点。更新$w_{t+1}=w_{t}+y*x$，这里圈圈代表y为正，$w_{t}=0$，因此$w_{t+1}=x$。
又因为$w_{t}x=0$，所以可以画出第一条决策边界如下图。
step-2：接下来根据$x_{2}$进行修正，显然它是错误分类的样本点，因此$w_{t}x_{2}<0$，也就是夹角大于90$^{o}$。然后根据上面说的$w$更新规则，可以得到如下图所示紫色的向量$w_{t+1}$，以它作为决策边界的法向量，再次更新决策边界。
之后就是不断循环更新分类错误的点，直到找到合适的分类边界为止。
但这里还存在一个问题：PLA何时停止？或者说数学上怎样判定找到了合适的分类边界？
PLA的终止条件
在线性可分的情况下，假设所有样本正确分类。如果有一条直线，能够将正类和负类完全分开，令这时候的目标权重为$w_{f}$，对于每个点来说，必然满足$y_{n}=\operatorname{sign}\left(w_{f}^{T} x_{n}\right)$，对于任一点：
$y_{n(t)} \mathbf{w}_{f}^{T} \mathbf{x}_{n(t)} \geq \min _{n} y_{n} \mathbf{w}_{f}^{T} \mathbf{x}_{n}>0$……………………………………………………….(1)
也就是任一点到分类边界的距离，都大于离分类边界最近点到分类边界的距离。
上面曾经提到过，PLA是通过逐步修正$w_{t}$，让其逼近$w_{f}$，在数学上体现为$w_{t+1}$和$w_{f}$的内积越来越大，也就是说$\mathbf{w}_{t+1}$和$\mathbf{w}_{f}$之间的夹角要越来越小。因此我们计算：
$\mathbf{w}_{f}^{T} \mathbf{w}_{t+1}=\mathbf{w}_{f}^{T}\left(\mathbf{w}_{t}+y_{n(t)} \mathbf{x}_{n(t)}\right)\geq\mathbf{w}_{f}^{T} \mathbf{w}_{t}+\min _{n} y_{n} \mathbf{w}_{f}^{T} \mathbf{x}_{n}>\mathbf{w}_{f}^{T} \mathbf{w}_{t}+0$
可以看出内积的确在增大，但问题是，也有可能是$\mathbf{w}_{t+1}$的模长在增大而并非角度越来越小，因此还需要证明一下$\mathbf{w}_{t+1}$和$\mathbf{w}_{f}$向量长度的关系。首先我们知道：
只有当分类错误时，$\mathbf{w}_{t}$才会改变：
$\operatorname{sign}\left(\mathbf{w}_{t}^{T} \mathbf{x}_{n(t)}\right) \neq y_{n(t)} \Leftrightarrow y_{n(t)} \mathbf{w}_{t}^{T} \mathbf{x}_{n(t)} \leq 0$…………………………………………(2)
然后计算$\mathbf{w}_{t+1}$的长度，这里我们计算$\left|\mathbf{w}_{t+1}\right|^{2}$，方便很多：
$\begin{aligned}\left|\mathbf{w}_{t+1}\right|^{2} &=\left|\mathbf{w}_{t}+y_{n(t)} \mathbf{x}_{n(t)}\right|^{2} \\ &=\left|\mathbf{w}_{t}\right|^{2}+2 y_{n(t)} \mathbf{w}_{t}^{T} \mathbf{x}_{n(t)}+\left|y_{n(t)} \mathbf{x}_{n(t)}\right|^{2} \\ & \leq\left|\mathbf{w}_{t}\right|^{2}+0+\left|y_{n(t)} \mathbf{x}_{n(t)}\right|^{2} \\ & \leq\left|\mathbf{w}_{t}\right|^{2}+\max _{n}\left|y_{n} \mathbf{x}_{n}\right|^{2} \end{aligned}$ ……………………………………………..(3)
因此可以看到长度的增量的限度为：$\max _{n}\left|y_{n} \mathbf{x}_{n}\right|^{2}$。也就是说向量长度的增长非常缓慢，而且有上限。
至此，我们证明了$\mathbf{w}_{t+1}$的确是在不断逼近$\mathbf{w}_{f}$的，但是要如何证明$\mathbf{w}_{t+1}$何时停止呢？
这里假设循环次数为$t$，因此我们只需要证明$t$小于某个数即可，而第一步，我们先计算$\mathbf{w}^{T}_{f}$和$\mathbf{w}_{t}$单位向量的内积
$\frac{w_{f}^{T} }{\left|w_{f}\right|} \frac{w_{t} }{\left|w_{t}\right|}$。根据公式(1)可得：
再根据公式(2)可得
(这里的证明其实跟上面几乎是一样的，只是因为要证明的内容不同，所以有些不一样的地方。)
整理一下可得出结论：
$\frac{w_{f}^{T} }{\left|w_{f}\right|} \frac{w_{t} }{\left|w_{t}\right|}\geqslant\frac{t \cdot \min y_{n} w_{f}^{T} x_{n} }{\left|w_{f}^{T}\right| \cdot \sqrt{t} \cdot \max _{n}\left|x_{n}\right|}\geq \sqrt{t}\cdot\frac{ \min _{n} y_{n} w_{f}^{T} x_{n} }{\left|w_{f}^{T}\right| \cdot \max _{n}\left|x_{n}\right|}=\sqrt{t}\cdot c$
(后面的分数等于常数c，因为和$w_{t}$无关)
$\frac{w_{f}^{T} }{\left|w_{f}\right|} \frac{w_{t} }{\left|w_{t}\right|}$随着迭代次数的增长，会越来越靠近，当完全重合时，内积等于1。因此
$\frac{w_{f}^{T} }{\left|w_{f}\right|} \frac{w_{t} }{\left|w_{t}\right|}\le1$=>$\sqrt{t} \cdot c\leq1$=>$t\leq\frac{1}{c^{2} }$，存在上界。如果我们做出如下定义：
则$t\le \frac{R^{2} }{\rho^{2} }$。
非线性可分数据
PLA适用于线性可分的数据，而对于线性不可分数据。PLA可能无法停止。即便是存在个别”噪音“的数据集，PLA都几乎无法工作。因此我们可以PLA修改，得出一个新算法Packet Algorithm。它的算法流程与PLA基本类似，首先初始化权重，计算出在这条初始化的直线中，分类错误点的个数。然后对错误点进行修正，更新w，得到一条新的直线，在计算其对应的分类错误的点的个数，并与之前错误点个数比较，取个数较小的直线作为我们当前选择的分类直线。之后，再经过n次迭代，不断比较当前分类错误点个数与之前最少的错误点个数比较，选择最小的值保存。直到迭代次数完成后，选取个数最少的直线对应的w，即为我们最终想要得到的权重值。
参考资料：
[1]红色石头的机器学习基石笔记
链接：https://pan.baidu.com/s/1uauOV9xyhJkMFao31yWZXg
提取码：kffo
[2] 感知器学习算法PLA的收敛性证明
