统计学习方法-感知机、超平面
目录
一、感知机
感知机是一种线性二分类模型，其思想是：对于输入空间，找到一个可以将空间分为正负两类的分离超平面，这个超平面其实就是需要的感知机。感知机分为原始形式和对偶形式。
超平面介绍
超平面：类似与一维直线上的点（0维），二维平面上的直线（1维），三维空间上的平面（2维），但是超平面一定过原点，所以，它（k-1 dim）可以将k dim空间平分成均匀的两份。
超平面公式：假设超平面法向量为，超平面上任一点为
，则超平面可表示为
，
，
。具体证明：设超平面上有一点
，则有
（法向量和超平面上的任意两点之间的连线的内积为0，因为互相垂直），则
，令
为
，则有
。
代表着超平面到原点的距离d与法向量长度||
||的乘积的相反数，证明：以三维空间中的平面为例，如图一，原点到平面
的距离是向量
的长度，它垂直于
，同时也与法向量
平行，我们可以看到
的长度其实就是向量
在
的投影，所以
，
是向量
与
的夹角，那么也就是op与
的夹角，又因为
，所以
，是个定值，我们也可以得到超平面到原点的距离d=
=
。
为什么超平面过原点，它仍到原点有距离？这个应该与超平面的定义有关：超平面是Rn 空间内的一个 n - 1 维的仿射子空间。仿射子空间概念查查看，我的理解是超平面是可以平移的，也不知道对不对。
空间中任一点x到超平面距离公式：
推导过程见https://blog.****.net/RushCode/article/details/89382749，和图一的推导类似。
感知机损失函数确定
感知机的定义如下：
是位于超平面上的点，
,
说明点位于超平面的两侧，我们的目的就是要找到一个超平面使所有的正实例点满足
，所有的负实例点满足
，下图直观的看出超平面的分割作用
感知机要求数据集是线性可分的，由此才可能获得一个分割超平面，为了找到这样一个超平面，即确定和
，我们需要一个损失函数，我们通过最小化这个损失函数来找到最优的超平面。一个最优化策略是最小化误分类点的个数，但是这样的损失函数对
，
不连续可导，这样，就不能用梯度下降法来调整参数了。另一个策是最小化误分类点到分离超平面的总距离，以总距离作为损失函数。显然，误分类个数越少，总距离越小，对一个具体的样本来说，正确分类，则损失函数是0，所以，损失函数在
，
连续可导。
我们已经知道了空间中任意一点到超平面的距离公式，
分类的符号函数和类别标签是+1、-1，对误分类的样例，我们有
，因为
与(
)是异号的。所以对于误分类的点，它到分离超平面的距离是
这样，对于误分类的点集和M,我们的到所有误分类的点到超平面的总距离是
不考虑，那么我们可以得到下面的损失函数
该损失函数就是感知机的经验风险函数。
感知机的原始形式
我们已经得到的要优化的损失函数，即下式
感知机是误分类驱动的，我们首先赋予 ，
初值，然后使用随机梯度下降法极小化损失函数。注意，极小化时，不是使用全部的误分类点进行梯度下降，而是一次随机选取一个误分类点进行梯度下降，这相当于每次调整超平面，使得当前误分类点回到正确分类的一侧，如此循环，直至所有点都正确分类(当然，这样很难达到)。
我们对，
进行梯度求偏导可得到
那么我们随机选一个误分类点，对 ，
进行梯度下降更新有
是学习率。
所以可以得到原始感知机的算法：
例题：
解答：
注意，感知机 ，
选取不同的初值，或选取不同的误分类点（次序），最后获得的感知机都可能不同。为了得到唯一的超平面，需要加约束条件，这就是下面的线性支持向量机。另外，感知机要求训练集线性可分，否则，可以想象，超平面会一直调整，这时，算法就不在收敛，感知机的损失函数值也会忽高忽低，发生震荡。
感知机的对偶形式
感知机的对偶形式与原始形式本质上没有区别，我们还记得原始形式是不断地对误分类的数据进行梯度计算更新参数，这里假设我们知道了所有训练样本参与更新的次数，即被分为误分类的次数，我们看前面的，
的更新公式，看出其实他就是在
初值的基础上累加所有样本错误分类的次数与当前学习率
和当前样本(
,
)的乘积，b类似。
更清楚的说，对一个样本(,
)，我们知道了它在最终找到超平面时被误分类了
次，那么
就得在初值
的基础上累加
，对b也是类似。
那么我们的训练目标就不时找合适的了，我们要找出每个样本对应的
，或者说，我们令
，我们要找到全部样本的
。
通过上述描述，我们的对偶感知机模型可以变成
其实
在对偶感知机模型中，我们只需要初始化所有的=0就可以了，然后在训练中逐次判断对应样本是否为错误分类，若是，则对应
加1，对应的
加
(因为
) 。所以我们可以得到下面对偶形式感知机的算法。
我们可以看到每次判断当前样本是否是错误分类时，都要计算，所以可以提前把这些计算好并以矩阵形式保存起来，这个矩阵就是Gram矩阵。
对于上面例题，我们用对偶形式的感知机求解如下：
参考：《统计学习方法》，李航