最近在研究机器学习理论的时候发现了一本好书，是李航博士的《统计学习方法》，书写得深入浅出，直白易懂，虽然不厚，但把统计学习各个方面都照顾到了，非常适合我这种机器学习方面的入门者，于是产生了一种写写读书笔记的想法，至少在日后看起来，也算是自己在追求大道上的一点回忆。

先给出书的豆瓣链接：《统计学习方法》，书真的很好，再次推荐！

李航老师的微博：@李航博士

1. 感知机模型

我们先来定义一下什么是感知机。所谓感知机，就是二类分类的线性分类模型，其输入为样本的特征向量，输出为样本的类别，取+1和-1二值，即通过某样本的特征，就可以准确判断该样本属于哪一类。顾名思义，感知机能够解决的问题首先要求特征空间是线性可分的，再者是二类分类，即将样本分为{+1, -1}两类。从比较学术的层面来说，由输入空间到输出空间的函数：

http://chart.apis.google.com/chart?cht=tx&chl=f(x)/quad+=/quad+sign(w/cdot+x/quad++/quad+b)                                                                                                         （1）

称为感知机，w和b为感知机参数，w为权值（weight），b为偏置（bias）。sign为符号函数：

                                                                                                         （2）

感知机模型的假设空间是定义在特征空间中的所有线性分类模型，即函数集合{f|f(x) = w·x + b}。在感知机的定义中，线性方程w·x + b = 0对应于问题空间中的一个超平面S，位于这个超平面两侧的样本分别被归为两类，例如下图，红色作为一类，蓝色作为另一类，它们的特征很简单，就是它们的坐标

http://images.cnitblog.com/blog/414721/201304/11142837-31e4844d63c2478e8f978af1ebd59512.png

图1

作为监督学习的一种方法，感知机学习由训练集求得感知机模型，即求得模型参数w，b，这里x和y分别是特征向量和类别（也称为目标）。基于此，感知机模型可以对新的输入样本进行分类。

前面半抄书半自说自话把感知机的定义以及是用来干嘛的简单记录了一下，作为早期的机器学习方法（1957年由Frank Rosenblatt提出），它是最简单的前馈神经网络，对之后的机器学习方法如神经网络起一个基础的作用，下一节将详细介绍感知机学习策略。

2. 感知机学习策略

上节说到，感知机是一个简单的二类分类的线性分类模型，要求我们的样本是线性可分的，什么样的样本是线性可分的呢？举例来说，在二维平面中，可以用一条直线将+1类和-1类完美分开，那么这个样本空间就是线性可分的。如图1就是线性可分的，图2中的样本就是线性不可分的，感知机就不能处理这种情况。因此，在本章中的所有问题都基于一个前提，就是问题空间线性可分。

http://images.cnitblog.com/blog/414721/201304/11142837-b7136dbe52314559b5db681519065d4c.png

图2

为方便说明问题，我们假设数据集http://chart.apis.google.com/chart?cht=tx&chl=w/cdot+x/quad++/quad+b/quad+%3C/quad+0。

这里先给出输入空间中任一点到超平面S的距离：

                                                                                                               （3）

这里||w||是w的范数。

对于误分类的数据，根据我们之前的假设，有

                                                                                                          （4）

因此误分类点到超平面S的距离可以写作：

                                                                                                            （5）

假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为

                                                                                                    （6）

这里的||w||值是固定的，不必考虑，这样就得到了感知机学习的损失函数。根据我们的定义，这个损失函数自然是越小越好，因为这样就代表着误分类点越少、误分类点距离超平面S的距离越近，即我们的分类面越正确。显然，这个损失函数是非负的，若所有的样本都分类正确，那么我们的损失函数值为0。一个特定的样本集T的损失函数：在误分类时是参数w，b的线性函数。也就是说，为求得正确的参数w，b，我们的目标函数为

                                                                                          （7）

而它是连续可导的，这就使得我们可以比较容易的求得其最小值。

感知机学习的策略是在假设空间中选取使我们的损失函数（7）最小的模型参数w,b，即感知机模型。

根据感知机定义以及我们的假设，得到了感知机的模型，即目标函数（7），将其最小化的本质就是使得分类面S尽可能的正确，下一节介绍将其最小化的方法——随机梯度下降。

3. 感知机学习算法

根据感知机学习的策略，我们已经将寻找超平面S的问题转化为求解式（7）的最优化问题，最优化的方法是随机梯度下降法，书中介绍了两种形式：原始形式和对偶形式，并证明了在训练集线性可分时算法的收敛性。

3.1 原始形式

所谓原始形式，就是我们用梯度下降的方法，对参数w和b进行不断的迭代更新。具体来说，就是先任意选取一个超平面，对应的参数分别为和，当然现在是可以任意赋值的，比如说选取为全为0的向量，的值为0。然后用梯度下降不断地极小化损失函数（7)。由于随机梯度下降（stochastic     gradient descent）的效率要高于批量梯度下降（batch gradient descent）（详情可参考Andrew Ng教授的讲义，在Part 1的LMS algorithm部分），所以这里采用随机梯度下降的方法，每次随机选取一个误分类点对w和b进行更新。

设误分类点集合M是固定的，为求式（7）的最小值，我们需要知道往哪个方向下降速率最快，这是可由对损失函数L(w, b)求梯度得到，L(w, b)的梯度为

接下来随机选取一个误分类点对w,b进行更新

                                                                                                                （8）

                                                                                                                      （9）

其中http://chart.apis.google.com/chart?cht=tx&chl=/eta+(0%3C/eta+/le+1)为步长，也称为学习速率（learning rate），一般在0到1之间取值，步长越大，我们梯度下降的速度越快，也就能更快接近极小点。如果步长过大，就有直接跨过极小点导致函数发散的问题；如果步长过小，可能会耗费比较长的时间才能达到极小点。通过这样的迭代，我们的损失函数就不断减小，直到为0。综上所述，得到如下算法：

算法1 （感知机学习算法的原始形式）

输入：训练数据集，其中，，i = 1,2,…,N；学习率http://chart.apis.google.com/chart?cht=tx&chl=/eta+(0%3C/eta+/le+1)

输出：w，b；感知机模型http://chart.apis.google.com/chart?cht=tx&chl=f(x)/quad+=/quad+sign(w/cdot+x/quad++/quad+b)

（1）选取初始值，

（2）在训练集中选取数据

（3）如果（从公式（3）变换而来）

（4）转至（2），直至训练集中没有误分类点

这种学习算法直观上有如下解释：当一个样本被误分类时，就调整w和b的值，使超平面S向误分类点的一侧移动，以减少该误分类点到超平面的距离，直至超平面越过该点使之被正确分类。

书上还给出了一个例题，这是我推崇这本书的原因之一，凡是只讲理论不给例子的行为都是耍流氓！

例1 如图3所示的训练数据集，其正实例点是，，负实例点是，试用感知机学习算法的原始形式求感知机模型http://chart.apis.google.com/chart?cht=tx&chl=f(x)/quad+=/quad+sign(w/cdot+x/quad++/quad+b)，即求出w和b。这里，

http://images.cnitblog.com/blog/414721/201304/12175006-26817264c38a47f5b93d2f56aee2f9d1.png

图3

这里我们取初值http://chart.apis.google.com/chart?cht=tx&chl=/eta+=1。具体问题解释不写了，求解的方法就是算法1。下面给出这道题的Python代码（终于有一段是自己纯原创的了）。