机器学习基石笔记：02 Learning to Answer Yes/No、PLA、PA

一、Perceptron Learning Algorithm

（一）算法原理

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

图1.1 感知器假设的定义

图1.2 二维感知器

图1.3 感知器假设的向量表示

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

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

图1.4 感知器学习算法

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

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

（三）停止更新

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

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

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

图1.7 内积值的增大

图1.8 模增大的上限

图1.9 整体趋势是越发接近

图1.10 二者余弦距离的下限

（四）PLA的优缺点

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

图1.11 PLA的优缺点

二、Pocket Algorithm

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

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

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

图2.2 PA流程

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

图2.3 PLA vs PA

最后编辑于：2019.05.01 08:43:21