统计学习方法：感知机

感知机(perceptron)是一种非常简单的模型，简单到不能再简单。感知机是理解SVM的基石，这里介绍谈感知机是为了后面的一些复杂一些的方法做准备。

抛出问题

我们使用感知机来模拟类似这样的一个问题：

在一个围棋棋盘上有许多散乱的棋子，其中有黑子也有白子。已知它们可以被很干净利落的被分为两部分，每部分都没有别的颜色的棋子，这样作为下棋者我们就可以很愉快的不用再挑棋子放进盒子里了！作为一个强迫症患者，你希望能直接用手一揽就把其中一部分棋子放入盒中，那么问题就是：手该如何放置才能使得这些棋子立马被干净利落的分为两部分呢？

（这么2的问题可能只有我才想得出了…）

问题思考

那么我们就来思考这个问题。首先我们明确情况，在已有条件中，有一个苛刻以及理想化的条件需要注意：散落的棋子可以被很干净利落的被分为两份。这里的干净利落是个不明确的表述，但是基本可以理解为我们可以用“一刀切”的方式把棋子分为两部分。在数据科学里，我们把这个条件称为数据 线性可分 。这是一个非常重要的前提条件。 其次，我们的问题是，我们需要把散落的棋子分为两部分，那么我们可以认为，这是一个典型的 二分类 问题。 用抽象一些的语言来描述就是，我们需要对整个问题建模，将棋子的散落情况整理成数据集D，我们的模型需要学习一个这样的映射：

y^:R2→C

其中C={−1,+1}，R2为数据集D的空间。 我们用+1和-1分别表示来过那种棋子的颜色。那么数据是什么呢？由于我们是对棋盘上的棋子根据他们现在的位置来分类，因此我们大可以将每颗棋子在棋盘上的坐标作为采样数据。对于每一个样本，我们可以得到这样的一个向量：

x=[x1,x2]

那么我们到底采用什么样的模型呢？别急，我们再来看问题。

注意我们的关键词——“一刀切”。一刀切我们可以理解为用一条直线把所有棋子构成的整体分为两个部分。那么，我们的模型只需要描述成一条直线即可。于是有这样的模型：

y=w⋅x+b

那么直线的参数又该如何得到呢？我们再来看问题。

由于棋子有两类，我们要做的是把棋盘上的棋子根据它们自身现在在棋盘上的位置把它们分为两类。而我们的目标是 保证每一类的棋子都为相同颜色 ，换句话说，我们希望被直线分割开的两边都没有分错类的棋子。那么我们就可以得到我们的策略——模型采用的期望风险函数：

Loss(y,y^)=1n∑in=1I(y,y^)

这里n为样本总量,y^为预测类别，y为实际类别，I为指示函数，若括号内参数相等则值为0，反之为1。 这是0-1损失函数的经验期望风险。

根据统计学习三要素，我们来看看我们现在问题的梳理情况： 我们有了模型，策略，我们还需要一个算法。 提前剧透一下，我们使用传统的梯度下降来求解这个问题。至于具体的内容还是先不详细解释。写到这娱乐的部分也该结束了。让我们回归理论严肃的统计学习。

模型

我们用更正式的语言来表达这个问题。 不知读者看到这里是否想到一个问题。模型使用上述写的形式是否存在问题？ 答案是，确实存在。我只是为了方便初学者从最简单的数学知识理解才写成那样的形式。那么我们来修正我们的模型： 先来看看问题出在哪儿。从指示函数考虑，我们在每次求损失的时候，需要判断当前的实例被分为哪一类，然后再计算损失。

那么该如何判断被分为了哪一类呢？我们都知道可以根据是在直线上方还是下方来划分分类。假如我们指定将直线上方的实例分为+1，反之为-1。但是当数据集中，恰好上方的实例都为-1，下方为+1时，我们的数据将永远是误分类。无论如何调整k都无法完美分类。因为k只控制斜率，b控制截距。但是在考虑分类的时候，我们还有一个地方需要去确定，那就是分类的类标签。使用上述的直线方程无法表示类标签。

于是，我们的感知机实际上是这样来考虑的（真正理论诞生的时候应该是没有这种问题的吧，应该是直接提出了下面这个模型的）： 我们使用一个 超平面 来划分数据空间。超平面是n维欧氏空间中余维度等于一的线性子空间。这是平面中的直线、空间中的平面之推广。简单来说指的就是在数据空间中一个用w⋅x+b=0来表示的一个平面，其中w与x都是向量，且维数与数据空间相同。

学过立体集合的多知道，w其实就是超平面的法向量，由于是向量，它具有方向，它就可以解决二分类问题中的类标签的归属问题，并且可以很好的将问题推广至N维情况。

当然，在历史上应该并不是为了解决类标签问题才使用超平面的。其实对于一个N维的输入空间使用一个超平面分割来考虑是一件非常自然的事。

策略

解决上面那个很不成样子的问题时，我们采用的损失函数为0-1损失函数。为什么使用0-1损失函数呢？因为一个很简单也很符合题意的思路就是：既然要完美把两部分棋子分开，那我们只要选取使得两部分棋子中被误分类的棋子个数为0不就好了吗？

顺理成章的想法，但是正因为简单，而产生了一个问题：我们怎么把策略和模型参数联系起来呢？ 如果使用0-1损失函数，那么从公事上看我们很难对它做出优化。可能只能用一个很暴力的办法，就是设定一个初始的超平面位置，然后选定一个很小的角度变化量，按照变化量对超平面进行旋转，每次都计算一次误分类，直到找到使损失函数为0的位置为止。有时候甚至肯可能因为变化量不够小，而导致没法得到这个角度。可想而知这个计算量非常大，而且整个计算过程也不易于优化，但同时又有相当多的冗余计算。

那么这时，我们就需要换个思路——改变我们的损失函数。 由于我们定义用一个超平面来分割我们的数据，那么我们就该利用好这些相关的性质。很容易想到我们可以用误分类的点的距离总和来作为损失函数。

空间中点到平面的距离：

d=1||w|||w⋅x+b|

其中||w||是L~2~范数（范数定义的是向量长度的一种计算方式）。 考虑误分类样本(x,y)，有下式：

−y(w⋅x+b)>0

因此得到距离：

d=1||w||y(w⋅x+b)

因此，得到损失函数：

Loss(w,b)=−∑xi∈Myi(w⋅xi+b)

这里省略L~2~范数，因为对于同一模型它可以看做常数。这里的M为每次迭代被感知机误分类的点的集合。 观察损失函数，我们可以看到损失函数是一个非负数。当完美分类时，损失函数值为0。且该函数可导，因此我们就可以定一个优化目标，用算法对它进行优化。

算法

这是一个很典型的优化问题。通常我们采用梯度下降的办法来解决这个问题。 所谓梯度下降，就是每次迭代模型参数，我们都向着下降最快的方向进行更新，以此来求解极小值。这样我们可以快速进行迭代、更新。貌似有个证明，证明梯度下降是一定能够收敛的。 梯度下降有两种，一种是批量梯度下降(batch gradient descent)，另一种是随机梯度下降（stochastic gradient decent）。这两者在我之前发的关于FTRL的文章里有所介绍，也可以参照网上的资料自行查阅。

简单来说这两者算法的区别就在于批量算法是每次迭代过程扫描所有样本，在总体损失上进行迭代。随机梯度下降是每次只根据单个样本的损失进行更新。很明显前者能在理论上收敛到全局最优，而后者虽然速度快，但是可能收敛于局部最优。特别的，当损失函数的极值分布比较变态的情况下，随机梯度下降和批量梯度下降可能都不会有很好的结果。但是通常情况下，我个人更倾向于采用随机梯度下降，因为它比较快，且效果一般也并不比批量的差，而且对于收敛于局部极值的问题可以考虑通过增加一个逐渐衰减的冲量项使其越过局部极值。当然具体使用哪种可以根据实际情况而定。

回到感知机，我们确定采用随机梯度下降来解这个问题。在这个过程中，我们计算整体损失函数的导数，再 随机选取一个样本进行参数更新。那么首先，我们需要计算出损失函数对参数的梯度，从而确定参数更新公式。对于一个随机的样本(x,y)：

▽wLoss(w,b)=−∑x∈Myx

▽bLoss(w,b)=−∑x∈My

w=w+ηyx

b=b+ηy

这里η是学习步长的参数，又称为学习率。在FTRL中我们对这个参数探讨过它的取值问题，在这里无需关注。通常需要频繁调试它来得到一个较好的学习结果。至于w，我们对它每一维的初值往往会设置随机的较小值，这样可以做到“破对称”，防止每一维因为相同的起始值而导致最后训练出相同的权值。

下面附上代码（N久以前写的代码，记得当时怎么都没出个正确值，不过我还是在贴上来的时候稍微改了改，有谁验证一下说说好不好用哈~作为作者我也真够懒的…）：