问题背景
考虑一个问题：现在我们有一些过往核发信用卡的资料，包括用户个人信息和审核结果。根据这些资料，我们希望预测能不能给下一个用户发信用卡。用户基本信息如下：
这些基本信息组成了一个向量
。不同的信息有不同的权重，设权重向量
。我们希望构造一个函数来给用户的信用打分，并且，如果信用分超过了某个阈值，我们就认为这个客户是可靠的，可以给他发信用卡：
能发：
不能：
通过阶跃函数
，进一步将这个过程函数化：
所以，当
，通过；当
，拒绝；当
，忽略。
其中：
整理该方程如下：
具体到二维空间
简化上面的问题，假设用户只有两个属性，就可以用二维空间的一个点来表示一个用户。如下所示，蓝圈表示通过，红叉表示拒绝。注意到直线的两边，一边大于0，一边小于0，也就是一边都是蓝圈，一边都是红叉。所以现在的目标就是，找到一条直线
，可以将已知的蓝圈和红叉完美区分开。
基础知识回顾
简单回顾一下线性代数的知识。一条直线可以由一个点
和法向量 
唯一确定。其点法式方程为：
。相应地，其方向向量为：
感知机学习算法
简单感知机算法（Perceptron Learning Algorithm，PLA）的思路很简单，首先随便找一条直线，然后遍历每一个已知点，如果正确，则跳过；如果错误，则利用这个点的信息对直线进行修正。修正的思路如上图所示：
是直线
的法向量。
是错误点的方向向量，
是真实值。具体情况可分为如下两种情况：
情况一：
为了将这个出错的点包括进紫色区域，
应该靠近方向。因此，
。
情况二：
为了将这个出错的点排除出紫色区域，应该远离
方向。因此，
。
综上，得到修正函数：
证明：PLA校正的正确性
那么为什么感知机算法可以逐步接近正确呢？
已知
两边同时乘上
和
，得：
因为
，所以：
注意到
恰好就是我们给出的当前用户的分数。当
，也就是我们打分打低了，修正后分数上升；当
，也就是我们打分打高了，修正后分数下降。这个结论说明，对于
这组错误数据，经过修正以后，我们打出的分数更靠近正确结果了。
证明：PLA终止的充分条件
从算法的规则上可以看出，PLA终止的必要条件是数据集中确定存在一条直线，可以将蓝圈和红叉分开，也就是线性可分：
现在证明，线性可分是PLA终止的充分条件。
（1） 设
表示第t次更新时的点，一共更新了n次。若线性可分，则必然存在一条完美的直线
，使得对
，有
。也就是：
（
为向量内积，也就是
）又由
的更新规则得：
因此：
综上，得到：
初始时
，所以：
（2） 因为每次遇到错误的数据才会更新，也就是
。其中
是第t次更新时的权重值。因此：
类似于（1），得到：
（3） 综上，得：
是一个常数，因此，随着t的增大，
也逐步增大，也就是向量
和
的夹角逐渐减小，
逐渐接近。
又因为：
，所以
。因此，PLA算法必然收敛。
Linear Pocket Algorithm
上述PLA算法的前提是数据集线性可分。但是很明显，在分类之前我们不可能知道我们手里的数据是不是线性可分的。更何况，数据集可能有噪声（noise），这些噪声是之前的经验中错误的分类结果，这些噪声将导致PLA无法收敛。因此，我们的目标就从找到一条完美划分数据集的，变成了找到一条最接近完美
，使得错误的点最少。这个转变使得我们可以理非线性可分的数据集 ：
是一个NP-hard问题。
因此问题又从“寻找最接近完美的
变成了“寻找尽可能完美的。Pocket Algorithm是PLA的变形，用于处理此类问题。算法如下：
与简单PLA不同的是：
Pocket Algorithm事先设定迭代次数，而不是等算法自己收敛；
随机遍历数据集，而不是循环遍历；
遇到错误点校正
时，只有当新得到的
优于（也就是错误更少）时才更新。因为Pocket要比较错误率，需要计算所有的数据点，因此效率要低于PLA。
如果数据集巧合是线性可分的，只要迭代次数够多，Pocket和PLA的效果是一样的，只是速度慢。
实践
讲了这么多理论知识，现在用python实践一下这个算法。简单起见，这里已知数据集是线性可分的，直接采用简单PLA就可以解决。核心代码不到20行，只需要理解train()函数即可，其它部分都是为了把这个图画出来。
运行效果如下：
原文发布时间为：2017-02-19
本文作者：ZZR
本文来自云栖社区合作伙伴“Python中文社区”，了解相关信息可以关注“Python中文社区”微信公众号
