林轩田《机器学习基石》（二）——Learning to answer yes or no
本次介绍课程的第一个机器学习算法：Perceptron Learning Algorithm（PLA）
注：感知机= 感知器，噪声= 杂屑，阈值= 门槛值
一、感知机模型
机器要不要发信用卡？即，机器学习如何做“是非题”。
输入：(顾客资料)
输出：(引用卡记录好坏)
实际的规则（但是我们不知道）：
资料：
有一个学习算法A，A要从hypothesis set（假说） H中找到一个出来，使得
和
越来越接近，可以用
去衡量是否可以贷款给顾客。
顾客x有很多个特征，如“年龄”、“职业”等，这些都影响我们是否要给它信用卡。我们可以对每个特征进行打分，然后得到一个总分，看它是否超过了某个“门槛”，如果超过了我们可以给信用卡，没有超过则不给。
我们今天介绍的感知机模型由权重（打分）和阈值（门槛）决定，我们找感知机模型也就是找权重和阈值。
通常，我们可以将权重和阈值合并，写成向量的形式从而简化代码。w表示合并后的向量。
顾客特征：为了方便可视化，我们假设顾客特征是二维的，可以在图中表示为一个点。
标签：正类（o +1），负类（× -1）
感知机： ，其实是一条分割直线
，将正类和负类分割在直线的两遍。
hypothesis set（假说） H：就是所有可能的线或者是高维分割平面。
二、如何从hypothesis set（假说） H中选一个更好的
首先我们知道什么？答：现存的数据（资料）。
所以我们可以要求我们找到的在看过的资料上表现都很好，使得
.（接近，最好一模一样）
思路：在空间中我们可以先找到一条线，然后不停地修正它。
我们首先复习一下点法式直线的确定：
已知直线经过点，且已知法向量
（可以看出这里的法向量是权重w），则直线方程为
所以给一个权重w和点，我们就可以确定一条直线，通常我们把经过的点设为原点（0,0）
现在我们讨论如何修正这条直线：
首先，我们要有一个初始的直线，由初始权重
确定。
之后我们来看如何修正：
（1）我要正，它给我负，说明，角度太大，所以做修正
，让角度变小
（2）我要负，它给我正，说明，角度太小，所以做修正
，让角度变大
综上，我们所做的修正为
我们从顾客1...一直将所有顾客x轮一遍，看看有没有犯错。步骤如下：
图解：
step1：我们设point 1为原点，红色为权重（也是确定直线的法向量），看到正点被分错了，所以我们更新
令，可以看到分割直线垂直于
。
对PLA，存在两个问题：
-
PLA迭代一定会停下来吗？
-
为什么一定会停下来/不会停下来？
三、PLA的收敛理论
当资料（数据）线性可分的时候，PLA会停。
对于线性可分的情况，如果有这样一条直线，能够将正类和负类完全分开，令这时候的目标权重为（我们假设这是最终的完美结果），则对每个点，必然满足
，故对任一点：
。
我们希望和
无限接近，两个向量内积越大，则两个向量越来越接近，直到两个向量相等达到上界（相等或者很接近时候的
就是我们要找的权重）。为了去除scale的影响，我们除以两个向量的模（其实就是计算两个向量的夹角）。
我们接下来证明以下公式，则可证明随着T的增大，两个向量越来越接近：
证明：
另一方面，我们直到当符号判断错误时，才会更新，所以有
故可得
可知线性可分的情况下，PLA是可以停下来并正确分类的。
四、线性不可分数据
对于非线性可分的情况，实际上并不存在，那么之前的推导并不成立，PLA不一定会停下来。
我们把新问题看做原来问题上的一点改动：
输入：(顾客资料)
输出：(引用卡记录好坏)
实际的规则（但是我们不知道）： 加一些噪声（但少）
资料：
我们是否可以找到一个线犯的错（分类错误）最少？即求解下列问题：
上述问题被证明了是NP-hard问题。所以我们的目标是找到一个差不多好的线：我们每次都把当前最好的线放到“口袋”。这种方法我们称为Pocket Algorithm。
算法用一些随机的方式，使其能够尽可能找到多一点的线进行比较。我们每次找到一条新的线，就比较他和我现在“口袋里的线”哪一条比较好（分类的错少）。直到跑了足够多的线，我们就让它停止，算法如下：
一般情况下，由于要存储原来的而且要进行比较，所以Pocket Algorithm要比PLA速度慢一些。