那么如何找到最合适的那条线呢？
知错能改算法。
PLA 什么时候能停下来？找到一条线在这个情况下所有样本都分类正确。 前提是线性可分。
\[\begin{aligned} w_{f}^{T} w_{t} &=w_{f}^{T}\left(w_{t-1}+y_{n(t-1)} x_{n(t-1)}\right) \\ & \geq w_{f}^{T} w_{t-1}+\min _{n} y_{n} w_{f}^{T} x_{n} \\ & \geq w_{0}+T \cdot \min _{n} y_{n} w_{f}^{T} x_{n} \\ & \geq T \cdot \min _{n} y_{n} w_{f}^{T} x_{n} \end{aligned}\] \[\begin{aligned}\left\|w_{t}\right\|^{2} &=\left\|w_{t-1}+y_{n(t-1)} x_{n(t-1)}\right\|^{2} \quad \text { using }(3) \\ &=\left\|w_{t-1}\right\|^{2}+2 y_{n(t-1)} w_{t}^{T} x_{n(t-1)}+\left\|y_{n(t-1)} x_{n(t-1)}\right\|^{2} \\ & \leq\left\|w_{t-1}\right\|^{2}+0+\left\|y_{n(t-1)} x_{n(t-1)}\right\|^{2} \quad \text { using }(2) \\ & \leq\left\|w_{t-1}\right\|^{2}+\max _{n}\left\|x_{n}\right\|^{2} \\ & \leq\left\|w_{0}\right\|+T \cdot \max _{n}\left\|x_{n}\right\|^{2}=T \cdot \max _{n}\left\|x_{n}\right\|^{2} \end{aligned}\]
这里能小于是因为有错才更新。
\[\begin{aligned} \frac{w_{f}^{T}}{\left\|w_{f}\right\|} \frac{w_{T}}{\left\|w_{T}\right\|} &=\frac{T \cdot \min _{n} y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}^{T}\right\| \cdot\left\|w_{t}\right\|} \\ &=\frac{T \cdot \min _{n} y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}^{T}\right\| \cdot \sqrt{T} \cdot \max _{n}\left\|x_{n}\right\|} \\ & \geq \frac{\sqrt{T} \cdot \min y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}^{T}\right\| \max _{n}\left\|x_{n}\right\| }=\sqrt{T} \cdot \text { constant } \end{aligned}\] \[\frac{w_{f}^{T}}{\left\|w_{f}\right\|} \frac{w_{T}}{\left\|w_{T}\right\|} \leq 1\] \[\begin{aligned} & \frac{\sqrt{T} \cdot \min y_{n} w_{f}^{T} x_{n}}{\left\|w_{f}^{T}\right\| \cdot \max _{n}\left\|x_{n}\right\|} \leq 1 \\ \Leftrightarrow T & \leq \frac{\max _{n}\left\|x_{n}\right\|^{2} \cdot\left\|w_{v}^{T}\right\|^{2}}{\min ^{2} y_{n} w_{f}^{T} x_{n}}=\frac{R^{2}}{\rho^{2}} \end{aligned}\]
说明 PLA 会更新，最后更新多少轮会停下来。
Pocket Algorithm
如果线性可分，Pocket 会比较慢。