Learning to Answer Yes/No

一、 Perceptron Hypothesis Set

引入一个例子：银行将要根据用户的年龄、性别、年收入等情况来判断是否给该用户发信用卡。现在有训练样本D，该样本包含了客户的信息以及是否发放信用卡。我们需要根据D，通过算法A，在H中选择最好的h，得到g并使得g无限接近目标函数f。这一流程就是根据先验知识建立判定给用户发送信用卡的模型。银行用这个模型对以后申请者进行判定：发信用卡和不发信用卡，并用两个状态机代表+1和-1。

在机器学习的整个流程中，有一个非常重要的选择就是：选择何种模型，即Hypothesis Set。选择什么样的模型，很大程度上会影响机器学习的效果和表现。

这里引入Perceptron（感知器）这一概念。

针对该案例我们进行数学模型化，把用户的个人信息作为特征向量x, 共有d个特征向量，每个特征赋予不同的权重w,表示该特征对输出判定（是否发信用卡）的影响权重有多大。那么所有特征向量的加权和的数值与一个设定的threshold进行比较：大于这个阈值，输出就是+1，就代表发信用卡；如果小于这个这个阈值，输出就是-1，就代表不发信用卡。感知器模型，就是当特征加权值和threshold的差大于或者等于0，输出h(x)=1；当特征加权值和threshold的差小于0，输出h(x)=-1。我们目的就是要计算出所有的w和threshold。

对上述的数学模型我们做一个简化的理解。我们都参加过考试，一门考试有多道题且每道题的分数使不一样的。这就对应我们的模型中d个特征向量，每一道题的分数对应不同的w。我们最后判断你的考试是否通过，是通过将每一道题的得分相加与60分做比较，超过60为通过考试，低于60为不通过。

图1

为了进行公式化表达，使用w0替换上述公式中的-threshold，并且引入一个x0=+1，那么h（x）的表达式可以进行一个改写，同时转化为一个高阶向量的内积，变化过程与结果如下图2所示：

图2

each "tall" w represents a hypothesis h & is multiplied with "tall" x ——will use tall versions to simplify notation.

为了更清晰地说明Perceptrons模型，我们假设Perceptrons在二维平面上，那么此时取h（x）=sign(wox0+w1x1+w2x2)。此时我们对应的物理模型是指只有两个维度的数据。如下图3所示，w0是平面上一条分类的直线，直线一侧是Positive（+1），直线另一侧是negative（-1）。

图三

通过以上数学模型，我们可以得出一个结论

Perceptrons= liner classifiers

线性分类器，我们一般用来回答是非问题。如果是更高维度的向量，线将对应着更高维度的图形。比如三维可能就是平面分类器。

二、 Perceptron Learning Algorithm（PLA）

根据上一节，我们已经知道了hypothesis set 由很多直线构成。接下来，我们需要通过算法A，来选择一条最好的直线，能将平面上所有的正类和负类完全分开，也就是我们需要找到一个最好的g，使得g无限近似于f。这是困难的，因为这样的直线是有无数条的。我们采用修正的思想去找这一条线。

首先再平面上随意取一条直线，看看哪些点分类出现了偏差。然后开始对第一个错误的点进行修正，通过变换直线的位置，使得中国错误点变成分类正确的点。接着，对错误点以此进行修正，直到所有的点都完全分类正确，这样得到的直线就是最好的的直线。这种“逐步修正的思想，就是PLA思想。

PLA详细方法

首先随机选择一条直线进行分类。然后没找到第一个分类错误的点。如果这个点表示的是+1，被误判成为了-1，就是说wtTXn(t)<0,那么就是说w和x的夹角大于了90°，其中w是直线的法向量。所以，x被误分在直线的下侧（相对于法向量，法向量的方向就是正类所在的一侧），修正的方法就是使w和x夹角小于90°。通常做法是使w=w+yx，y=1。如图四所示，一次或多次的更新后的w+yx与x夹角小于90°，能保证x位于直线的上侧，那么就完成了该点的直线修正。

同理wtTXn(t)>0,那么就是说w和x的夹角小于了90°，其中w是直线的法向量。所以，x被误分在直线的下侧（相对于法向量，法向量的方向就是正类所在的一侧），修正的方法就是使w和x夹角大于90°。通常做法是使w=w+yx，y=-1。如图四所示，一次或多次的更新后的w+yx与x夹角大于90°，能保证x位于直线的下侧，那么就完成了该点的直线修正。

按照这种思想，遇到了错误点就惊喜修正，不断进行迭代。要注意一点：每一次修正直线，可能使之前分类正确的点变成了错误点，这是可能发生的。但是我们可以通过不断迭代，不断修正，最终会将所有点完全正确分类（PLA前提使线性可分）。

实际编程操作中，可以一个点一个点进行遍历，发现错误的点就进行修正，直到所有点全部分类正确。这被称为Cyclic PLA。