Perceptron Hypothesis Set

Perceptron : 感知机

对于一个假设h(x)，结果与权值w和阈值threshold有关。

sign(x)函数表示：sign(x > 0) = +1, sign(x < 0) = -1。

对二元的h(x)，形成如下线性分类：

由此，感知机模型成为了一个线性（二分）分类器（linear/binary classifiers）。

现在的问题是，如何得到这条直线？？

Perceptron Learning Algorithm

“知错就改”的方法——PLA

这个方法即是通过不断用错误点来修正feature vector，从而让不断接近理想的。

但是要证明这一点要回答两个问题：为什么这样做能不断接近目标？这样做是否能够终止？

Guarantee of PLA

首先能想到的是，data必须线性可分，否则将永远找不到那个满足条件的直线。

但是，如何判断是否线性可分，课程中说这是一个NP-hard Problem，没有好的方法。

上图旨在证明随着correct的进行，不断接近于，趋近于目标。（这里用向量的内积来表示接近程度）

但是有一个问题：内积严格单调递增，并不一定表示两个向量的夹角就是在减小，有可能是向量的模变大了，以下就解决这个问题：

由此可以知道的是，的增长不会太快，而又不断接近于，算法会达到终止。

以上的证明，参考了网上的其他资料，有比较详细的过程，下面的Latex过程来自于HappyAngel的博客笔记：

Pros and Cons of PLA

那么在Data含有噪声（含有线性不可分点）的时候怎么办呢？

Pocket Algorithm

这是一个解决数据噪声的贪心方法，在当前保持最小的mistake，完成足够迭代后获得最优解。