感知机type
status
date
slug
summary
tags
category
icon
password
Property
原理
感知机模型
感知机的思想很简单，比如在一个平台上有很多的男孩女孩，感知机的模型就是尝试找到一条直线，能够把所有的男孩和女孩隔离开。放到三维空间或者更高维的空间，感知机的模型就是尝试找到一个超平面，能够把所有的二元类别隔离开。当然，如果找不到这么一条直线的话怎么办？找不到的话那就意味着类别线性不可分，也就意味着感知机模型不适合你的数据的分类。
使用感知机一个最大的前提，就是数据是线性可分的。这严重限制了感知机的使用场景。它的分类竞争对手在面对不可分的情况时，比如支持向量机可以通过核技巧来让数据在高维可分，神经网络可以通过激活函数和增加隐藏层来让数据可分。
用数学的语言来说，如果有个样本，每个样本对应于维特征和一个二元类别输出，如下：
目标是找到这样一个超平面，即：
让其中一种类别的样本都满足 ，另一种类别的样本都满足 ，从而得到线性可分。如果数据线性可分，这样的超平面一般都不是唯一的，也就是说感知机模型可以有多个解。
为了简化这个超平面的写法，增加一个特征 ，这样超平面为 。进一步用向量来表示为： ，其中 为 的向量， 为 的向量, 为内积，后面都用向量来表示超平面。
感知机的模型可以定义为： 其中：
感知机模型损失函数
为了便于定义损失函数，将满足 的样本类别输出值取为1，满足的样本类别输出值取为-1。因为正确分类的样本满足 ，而错误分类的样本满足 。损失函数的优化目标，就是期望使误分类的所有样本，到超平面的距离之和最小。
由于 ，所以对于每一个误分类的样本 ，到超平面的距离是
假设所有误分类的点的集合为M，则所有误分类的样本到超平面的距离之和为：
这样就得到了初步的感知机的损失函数（乘以则误分类的样本距离刚好为正值，不需要绝对值了）
研究可以发现，分子和分母都含有 ，当分子的扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，这样可以简化损失函数（我们关心的是损失函数取极值的时候模型参数的值，对具体的损失函数的极值不感兴趣）。在感知机模型中，采用的是保留分子，即最终感知机模型的损失函数简化为：
注：支持向量机采用的是固定分子为1，然后求 的最大化。采用不同的损失函数主要与它的后面的优化算法有关系。
感知机模型损失函数的优化方法
损失函数：，其中是所有误分类的点的集合。这个损失函数可以用梯度下降法或者拟牛顿法来解决，常用的是梯度下降法。
但是普通的基于所有样本的梯度和的均值的批量梯度下降法（BGD）是行不通的，原因在于损失函数里面有限定，只有误分类的M集合里面的样本才能参与损失函数的优化，所以只能采用随机梯度下降（SGD）或者小批量梯度下降（MBGD）。
感知机模型选择的是采用随机梯度下降，这意味着每次仅仅需要使用一个误分类的点来更新梯度。
损失函数基于向量的的偏导数为：
的梯度下降迭代公式应该为：
由于采用随机梯度下降，所以每次仅仅采用一个误分类的样本来计算梯度，假设采用第个样本来更新梯度，则简化后的向量的梯度下降迭代公式为：
其中为步长， 为样本输出1或者-1， 为的向量
感知机模型的算法
这里对感知机模型基于随机梯度下降来求向量的算法做一个总结。
算法的输入为个样本，每个样本对应于维特征和一个二元类别输出1或者-1 ：
输出为分离超平面的模型系数 向量
算法的执行步骤如下：
- 定义所有为1。选择向量的初值和步长的初值，可以将向量置为0向量，步长设置为1。要注意：由于感知机的解不唯一，使用的这两个初值会影响向量的最终迭代结果。
- 在训练集里面选择一个误分类的点，用向量表示即，这个点应该满足：
- 对向量进行一次随机梯度下降的迭代：
- 检查训练集里是否还有误分类的点，如果没有，算法结束，此时的向量即为最终结果。如果有，继续第2步。
误分类点就是使用当前迭代时的值，计算出，如果小于0则是误分类点。第一轮迭代才是给的的初始值，后面在每一轮迭代都会改变，因此是使用当前迭代时的值才准确
感知机模型的算法对偶形式
对偶形式是对算法执行速度的优化，这里的对偶和SVM里的拉格朗日对偶完全不是一个概念。
感知机模型的算法原始形式，可以看出，每次梯度的迭代都是选择的一个样本来更新向量。最终经过若干次的迭代得到最终的结果。对于从来都没有误分类过的样本，他被选择参与迭代的次数是0，对于被多次误分类而更新的样本，它参与迭代的次数我们设置为。如果令向量初始值为0向量， 向量的表达式可以写为：
其中为样本在随机梯度下降到当前的这一步之前因误分类而更新的次数。
每一个样本 的的初始值为0，每当此样本在某一次梯度下降迭代中因误分类而更新时，的值加1。
由于步长 为常量，令 ，这样向量的表达式为：
在每一步判断误分类条件的地方，用 的变种 来判断误分类。注意到这个判断误分类的形式里面是计算两个样本 的内积，而且这个内积计算的结果在下面的迭代次数中可以重用。如果事先用矩阵运算计算出所有的样本之间的内积，那么在算法运行时， 仅仅一次的矩阵内积运算比多次的循环计算省时。 计算量最大的判断误分类这儿就省下了很多的时间，这也是对偶形式的感知机模型比原始形式优的原因。
样本的内积矩阵称为Gram矩阵，它是一个对称矩阵，记为
这里给出感知机模型的算法对偶形式的内容：
算法的输入为个样本，每个样本对维特征和一个二元类别输出1或者-1，如下：
输出为分离超平面的模型系数向量
算法的执行步骤如下：
- 定义所有为1，步长初值，设置的初值0。可以将设置为1。步长初值会影响向量最终迭代结果
- 计算所有样本内积形成的Gram矩阵G
- 在训练集里面选择一个误分类的点 ，这个点应该满足： ， 在检查是否满足时可以通过查询Gram矩阵的 的值来快速计算是否小于0
- 对向量的第i个分量进行一次更新： （因为 ，本次迭代后误分类次数加一，自然要加上）
- 检查训练集里是否还有误分类的点，如果没有，算法结束，此时的向量最终结果为下式；如果有，继续第3步
为向量的第个分量
补充
点到超平面距离公式推导
空间中任意一点到超平面S的距离公式：
推导：
取点空间中一点 ，超平面：，其中，，均为N维向量
设点到平面的距离为，点 在平面上的投影点为 ，则 满足
因为向量平行于平面的法向量，故有
， 为向量的范数
又因
故
得
感知机损失函数是凸函数，那存在全局最优解，那为什么感知机的解又不唯一？
感知机的分类条件是线性条件，其损失函数也是线性的，所以是一个比较简单的凸优化问题。
感知机算法规定了的更新步骤，它导致不能取到任意值，只能取各个数据向量的整系数线性组合。这个限制使得感知机往往会错过最优解。同时，感知机算法的终止条件是所有数据均正确分类，并不是最小化，所以只会找到一个可行解，而不是使得最小的最优解。
对偶形式为什么要用这个G矩阵？
可以理解G矩阵是一个二维数组，实现计算出这个二维数组里面所有的位置的值，并保存起来。
在后面计算：
时，这部分不用重复去计算，所以省了时间，因为这个内积计算在迭代的时候经常会重复用到。
