一、Perceptron Learning Algorithm

（一）算法原理

PLA本质是二元线性分类算法，即用一条线／一个面／一个超平面将1、2维／3维／4维及以上数据集根据标签的不同一分为二。算法确定后，根据取值的不同形成不同的，构成假设集合。如2维感知器算法，根据,,的不同取值，构成了不同的，这些最终构成。为了方便表示，将阈值的相反数记为，对应的数据点增加一维，恒为1。算法就是根据给定数据集从中选出与目标模式最为相似的。

图1.1 感知器假设的定义
图1.2 二维感知器
图1.3 感知器假设的向量表示

（二）更新规则／学习过程

遍历数据集合，若遇到异常点，即由当前更新为新的。
若异常点的值为+1，表明与当前的内积值为负，角度过大，更新后角度将会变小；若异常点的值为-1，表明与当前的内积值为正，角度过小，更新后角度将会变大。
更新的本质其实是从中选出与更为相似的的过程。

图1.4 感知器学习算法

更新后不能保证异常点变为正常点，只是异常的程度小了点。

图1.5 感知器一次更新的结果

（三）停止更新

在当前的情况下，遍历中所有数据点，无异常点时停止更新。
然而一定能够保证能停止更新吗？即在当前下无法找到一个新的使得对应的与更为接近？
答案是只要数据线性可分就能！

图1.6 PLA停止更新的充要条件

与的内积值随着更新次数的上升而增大，同时，的模也在增大。不过，内积增大的程度往往大于模增大的程度，保证了随着更新次数的上升，与趋于越来越接近。

图1.7 内积值的增大
图1.8 模增大的上限
图1.9 整体趋势是越发接近
图1.10 二者余弦距离的下限

（四）PLA的优缺点

优点：简单、快速、任意维度；
缺点：假设数据线性可分，然而我们并不知道，也就不知道是否可分。再来，要是知道线性可分，也已经知道了，没有必要再用PLA了；经过多少次更新才能收敛也不知道，如上证明，与有关，然而我们不知道。

图1.11 PLA的优缺点

二、Pocket Algorithm

若数据线性不可分，使用PA，即既然异常点无法避免，PA在中找到一个使得异常点数目最小的作为。
NP问题：为多项式型时间复杂度，为指数型时间复杂度。问题分为可解问题和不可解问题，多项式型时间复杂度的可解问题为P问题，验证时为多项式型时间复杂度的问题为NP问题，能否可解未知。P问题肯定是NP问题，NP问题不一定是P问题。

图2.1 数据线性不可分的情况

PA，初始化，放到口袋里，若遇到异常点，使用PLA的更新规则得到新的，遍历数据集，若是新的下异常点的数目更少，则用新的替换旧的放到口袋中，否则不替换。继续遍历数据集，得到下一个异常点，重复上述过程至足够迭代次数。口袋里放的永远是目前使得异常点最少的。
PA不影响PLA的正常运行，只是从历史中挑出使得样本内分类错误最少的作为最终返回值。

图2.2 PA流程

如果数据集是线性可分的，PLA和PA都能够实现内无异常点的分类，但是PA的时间会长于PLA，因为多了比较两个不同的下遍历一轮数据所得异常点数目多少的过程。

图2.3 PLA vs PA