问题描述
对于线性二分类问题
\begin{equation}
y = \left\{
\begin{aligned}
& +1 & \sum\nolimits_{i=1}^dw_ix_i > \mbox{threshold} \\
& -1 & \sum\nolimits_{i=1}^dw_ix_i < \mbox{threshold}
\end{aligned}
\right.
\end{equation}
也可以记为
\begin{equation}
h(x) = \mbox{sign}\left(\sum_{i=1}^dw_ix_i - \mbox{threshold}\right) = \mbox{sign}\left(\sum_{i=0}^dw_ix_i\right) = \mbox{sign}\left(\mathbf{w^Tx}\right)
\end{equation}
其中，$w_0 = -\mbox{threshold}, x_0 = +1$。
问：如何估计模型模型$h(x)$的参数$\mathbf{w}$？
答：感知器算法（PLA，Perceptron Learning Algorithm）。
感知器算法
感知器算法通过迭代更新模型参数，直到没有错分的样本点。
PLA
repeat until a full cycle of not encountering mistakes {
- 找到参数$\mathbf w_t$时对应错分的样本点$\left(\mathbf x_{n(t)}, y_{n(t)}\right)$，$\mbox{sign}\left(\mathbf w^T \mathbf x_{n(t)}\right) \neq y_{n(t)}$；
- 修正参数，$\mathbf w_{t+1}\leftarrow \mathbf w_t + y_{n(t)}\mathbf x_{n(t)}$。
}
PLA更新模型参数解释：
- 当$y=+1$时，若分错，$\mathbf w^T \mathbf x < 0$，表示$\mathbf{w}$和$\mathbf x$的夹角太大（大于90度），需要调整$\mathbf w$，使其与$\mathbf x$的夹角变小；
- 当$y=-1$时，若分错，$\mathbf w^T \mathbf x > 0$，表示$\mathbf{w}$和$\mathbf x$的夹角太小（小于90度），需要调整$\mathbf w$，使其与$\mathbf x$的夹角变大。
通过参数更新规则可知
\[
\mathbf w_{t+1} ＝ \mathbf w_t + y_{n}\mathbf x_{n}
\]
两边转置后同时乘上$y_n\mathbf x_n$，可得
\[
y_n\mathbf w^T_{t+1} \mathbf x_n \geq y_n\mathbf w^T_t\mathbf x_n
\]
这表明，参数更新始终在试图纠正模型参数。
注意事项：$\mathbf w$是决策界（判别面）的法向量。
理论分析
- PLA算法会终止么？
- 能否从候选模式$h$中学习到目标模式$f$？
如果数据集$\mathcal D$线性可分，存在一个完美$\mathbf w_f$，使得对数据集中所有样本点$y_n = \mbox{sign}\left(\mathbf w_f^T\mathbf x_n\right)$，对于任意一个样本点总有
\begin{equation} y_{n(t)}\mathbf w_f^T\mathbf x_{n(t)} \geq \min_n y_n\mathbf x_f^T\mathbf x_n > 0 \end{equation}
根据感知器算法的更新规则可知 \begin{equation} \begin{aligned} \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 x_f^T\mathbf x_n \\ & > \mathbf w_f^T\mathbf w_t \end{aligned} \end{equation} 由此可见，参数更新后，$\mathbf w_{t+1}$可能会更加接近$\mathbf w_f$。但是，还不能确定是由于向量间夹角变小还是$\mathbf w_{t+1}$长度变大导致的内积增加。 \begin{equation} \begin{aligned} \|\mathbf w_{t+1}\|^2 & = \|\mathbf w_t + y_{n(t)}\mathbf x_{n(t)}\|^2 \\ & = \|\mathbf w_t\|^2 + \|y_{n(t)}\mathbf x_{n(t)}\|^2 + 2y_{n(t)}\mathbf w_t^T\mathbf x_{n(t)} \\ & \leq \|\mathbf w_t\|^2 + \|y_{n(t)}\mathbf x_{n(t)}\|^2 \\ & \leq \|\mathbf w_t\|^2 + \max_n\|\mathbf x_{n}\|^2 \end{aligned} \end{equation} 由此可见，每次更新的时候，向量长度的增加是有限的，最多增加样本最长向量的长度。
事实上，从$\mathbf w_0$开始，经过$T$次迭代后有 \begin{equation} \frac{\mathbf w_f^T}{\|\mathbf w_f\|}\frac{\mathbf w_T}{\|\mathbf w_T\|}\geq \sqrt T \times \mbox{constant} \label{eq:need_to_be_done_1} \end{equation} PLA算法迭代次数的上界满足$T\leq R^2/\rho^2$，其中 \begin{equation} R^2 = \max_n \|\mathbf x_n\|^2,~~\rho=\min_n y_n\frac{\mathbf w_f^T}{\|\mathbf w_f\|}\mathbf x_n \label{eq:need_to_be_done_2} \end{equation}
相关的证明如下：
结论：
- 对于线性可分的样本集合，通过PLA修正模型参数，$\mathbf w_f$和$\mathbf w_t$的内积增长快，$\mathbf w_t$的长度增长慢，$\mathbf w_t$越来越靠近$\mathbf w_f$，最终算最终收敛；
- 对于未知的样本集，作用在其上的PLA算法可能长时间不收敛，导致这样的情况可能是迭代次数不够（理论上的参数$T$由于目标模型$f$未知而难以估计）或者样本集存在噪声（线性不可分）。
Pocket PLA
判断样本集是否线性可分的复杂度为NP-hard。实际上，通常样本集存在一些噪声，不可能严格的线性可分，PLA算法无法满足收敛条件。Pocket PLA通过改变PLA迭代结束的条件和参数更新规则仍然可以估计模型参数。
Pocket PLA
repeat until enough iterations {
- 随机抽取参数$\mathbf w_t$时对应错分的样本点$\left(\mathbf x_{n(t)}, y_{n(t)}\right)$，$\mbox{sign}\left(\mathbf w^T \mathbf x_{n(t)}\right) \neq y_{n(t)}$；
- 修正参数，$\mathbf w_{t+1}\leftarrow \mathbf w_t + y_{n(t)}\mathbf x_{n(t)}$；
- 如果$\mathbf w_{t+1}$在样本集上的表现优于$\hat{\mathbf w}$，$\hat{\mathbf w}\leftarrow \mathbf w_{t+1}$。
}
从第3步可知，Pocket PLA的算法时间复杂度要高于PLA，如果对于线性可分的样本集，Pocket PLA比PLA慢。
