Python机器学习算法入门之简单感知器学习算法

问题背景

考虑一个问题：现在我们有一些过往核发信用卡的资料，包括用户个人信息和审核结果。根据这些资料，我们希望预测能不能给下一个用户发信用卡。用户基本信息如下：

这些基本信息组成了一个向量 。不同的信息有不同的权重，设权重向量 。我们希望构造一个函数来给用户的信用打分，并且，如果信用分超过了某个阈值，我们就认为这个客户是可靠的，可以给他发信用卡：

• 能发：

• 不能：

通过阶跃函数 ，进一步将这个过程函数化：

所以，当 ，通过；当 ，拒绝；当 ，忽略。

其中：

整理该方程如下：

具体到二维空间

简化上面的问题，假设用户只有两个属性，就可以用二维空间的一个点来表示一个用户。如下所示，蓝圈表示通过，红叉表示拒绝。注意到直线的两边，一边大于0，一边小于0，也就是一边都是蓝圈，一边都是红叉。所以现在的目标就是，找到一条直线 ，可以将已知的蓝圈和红叉完美区分开。

基础知识回顾

简单回顾一下线性代数的知识。一条直线可以由一个点 和法向量 唯一确定。其点法式方程为： 。相应地，其方向向量为：

感知机学习算法

简单感知机算法（Perceptron Learning Algorithm，PLA）的思路很简单，首先随便找一条直线，然后遍历每一个已知点，如果正确，则跳过；如果错误，则利用这个点的信息对直线进行修正。修正的思路如上图所示： 是直线 的法向量。 是错误点的方向向量， 是真实值。具体情况可分为如下两种情况：

情况一：

为了将这个出错的点包括进紫色区域， 应该靠近 方向。因此， 。

情况二：

为了将这个出错的点排除出紫色区域， 应该远离 方向。因此，

。

综上，得到修正函数：

证明：PLA校正的正确性

那么为什么感知机算法可以逐步接近正确呢？

已知

两边同时乘上 和 ，得：

因为 ，所以：

注意到 恰好就是我们给出的当前用户的分数。当 ，也就是我们打分打低了，修正后分数上升；当 ，也就是我们打分打高了，修正后分数下降。这个结论说明，对于 这组错误数据，经过修正以后，我们打出的分数更靠近正确结果了。

证明：PLA终止的充分条件

从算法的规则上可以看出，PLA终止的必要条件是数据集中确定存在一条直线，可以将蓝圈和红叉分开，也就是线性可分：

现在证明，线性可分是PLA终止的充分条件。

（1） 设 表示第 t次更新时的点，一共更新了n次。若线性可分，则必然存在一条完美的直线 ，使得对 ，有 。也就是：

（ 为向量内积，也就是 ）又由 的更新规则得：

因此：

综上，得到：

初始时 ，所以：

（2） 因为每次遇到错误的数据才会更新，也就是 。其中 是第t次更新时的权重值。因此：

类似于（1），得到：

（3） 综上，得：

是一个常数，因此，随着 t的增大， 也逐步增大，也就是向量 和 的夹角逐渐减小， 逐渐接近 。
又因为：