|
ZZR，Python中文社区专栏作者，OpenStack工程师，曾经的NLP研究者。主要兴趣方向：OpenStack、Python爬虫、Python数据分析。 Blog：http:///
CSDN：http://blog.csdn.net/titan0427/article/details/50365480
问题背景
考虑一个问题：现在我们有一些过往核发信用卡的资料，包括用户个人信息和审核结果。根据这些资料，我们希望预测能不能给下一个用户发信用卡。用户基本信息如下： 
这些基本信息组成了一个向量 。不同的信息有不同的权重，设权重向量 。我们希望构造一个函数来给用户的信用打分，并且，如果信用分超过了某个阈值，我们就认为这个客户是可靠的，可以给他发信用卡：
能发： 不能：
通过阶跃函数 ，进一步将这个过程函数化： 
所以，当 ，通过；当 ，拒绝；当 ，忽略。
其中： 
整理该方程如下：
具体到二维空间简化上面的问题，假设用户只有两个属性，就可以用二维空间的一个点来表示一个用户。如下所示，蓝圈表示通过，红叉表示拒绝。注意到直线的两边，一边大于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()函数即可，其它部分都是为了把这个图画出来。
运行效果如下：
参考资料《国立台湾大学-机器学习基石-林轩田》第二讲 Perceptron Learning Algorithm
配图来自《国立台湾大学-机器学习基石-林轩田》 本文内容学习自互联网，采用署名-非商业性使用-相同方式共享 2.5 中国大陆协议进行许可。
优秀人才不缺工作机会，只缺适合自己的好机会。但是他们往往没有精力从海量机会中找到最适合的那个。
100offer 会对平台上的人才和企业进行严格筛选，让「最好的人才」和「最好的公司」相遇。
扫描下方二维码，注册 100offer，谈谈你对下一份工作的期待。一周内，收到 5-10 个满足你要求的好机会！
|
