感知机介绍

感知机是一个二类分类的线性分类器，是支持向量机和神经网络的基础。感知机假设数据是线性可分的，目标是通过梯度下降法，极小化损失函数，最后找到一个分割超平面，可以将数据划分成两个类别。使用感知机一个最大的前提，就是数据是线性可分的。

感知机模型函数

如果我们有m个样本，每个样本对应于n维特征和一个二元的类别输出：
$$
x^{(i)}=\left(x_{1}^{(i)}, x_{2}^{(i)}, \ldots, x_{n}^{(i)}\right), y^{(i)} \in(-1,+1) \quad(i=1,2, \ldots, m)
$$
我们的目标是找到这样一个超平面（向量形式）：
$$
w x+b=0
$$
这个超平面将特征空间划分为两个部分：
对于y（i）=-1的样本
$$
w \cdot x^{(i)}+b<0
$$

对于y（i）=+1的样本
$$
w \cdot x^{(i)}+b>0
$$
如何实现上面的分类呢？
定义一个函数:
$$
f(x)=\operatorname{sign}(w \cdot x+b)
$$
其中sign是符号函数。
上面的f（x）函数就是感知机模型函数。一旦学习到了w和b的值，我们就可以利用f（x）来判断新的样本属于哪一类别。

感知机模型损失函数

为了训练感知机模型函数的参数w和b，我们需要定义损失函数并将损失函数最小化。
我们最小化误分类点到超平面的总距离，这就是感知机模型所采用的损失函数。
空间上一点xi到超平面wx + b=0的距离公式为：
$$
w \cdot x^{(i)}+b
$$
的绝对值除以参数W的L2范数。
对于误分类点（xi，yi），总有
$$
-y^{(i)} f(x^{(i)})>0
$$
这是因为假如点的正确分类为+1，而感知机将其误分类为-1时，有f（xi）<0，那么再乘以-yi就有
$$
-y^{(i)} f(x^{(i)})>0
$$
类似地，如果点的正确分类点为-1，也有类似结论。
因此一个误分类点到超平面的距离为：
$$
-y^{(i)}\left(w \cdot x^{(i)}+b\right)
$$
除以w的L2范数。
所有误分类点到超平面的总距离为：
$$
\sum_{x^{(i)} \in M} y^{(i)}\left(w \cdot x^{(i)}+b\right)
$$
除以w的L2范数。
我们可以发现分子和分母都含有w，当分子的w扩大N倍时，分母的w的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。因此我们令分母||w ||2=1，这样可以简化我们的损失函数。
最终感知机模型的损失函数为：
$$
L(w, b)=-\sum_{x^{(i)} \in M} y^{(i)}(w \cdot x^{(i)}+b)
$$

感知机模型函数的优化算法

对于上面的损失函数，我们可以用梯度下降的方法来优化。但是用普通的基于所有样本的梯度和均值的批量梯度下降法（BGD）是行不通的，原因在于我们的损失函数里面有限定，只有误分类的点集合里面的样本才能参与损失函数的优化。
所以感知机模型选择的是采用随机梯度下降，这意味着我们每次只使用一个误分类的点来更新梯度。
给定训练集T，感知机学习的目标是最小化损失函数：
$$
L(w, b)=-\sum_{x^{(i)} \in M} y^{(i)}(w \cdot x^{(i)}+b)
$$
其中M是误分类点的集合。
损失函数的梯度为：
$$
\nabla_{w_{k}} L(w, b)=-\sum_{x^{(i)} \in M} y^{(i)} x_{k}^{(i)}
$$
$$
\nabla_{b} L(w, b)=-\sum_{x^{(i)} \in M} y^{(i)}
$$
因为采用随机梯度下降，所以每次仅采用一个误分类的样本点（xi，yi）来计算梯度对w，b进行更新：
$$
w=w-\eta \nabla_{w} L(w, b)=w+\eta y^{(i)} x^{(i)}
$$
$$
b=b-\eta \nabla_{b} L(w, b)=b+\eta y^{(i)}
$$
其中η为学习率。每次调整都使超平面向误分类点的一侧移动，以减小改误分类点与超平面间的距离，直到超平面越过该点使其被正确分类。

感知机模型的训练过程

输入m个样本，每个样本对应于n维特征和一个二元类别输出1或者-1，如下：
$$
(x^{(0)}, y^{(0)}),(x^{(1)}, y^{(1)}), \ldots(x^{(m)}, y^{(m)})
$$
输出为超平面的参数w和b。
步骤如下：

定义所有w和b的处置，设置初始学习率。
在训练集中任意抽取一个数据点（xi，yi），判断它用现有的感知机模型分类是否是误分类点，如果是，执行下一步；如果不是，则放回再抽取一个点，再判断是否是误分类点。如果所有数据点都判断过且无误分类点，则直接结束算法。
使用上一步得到的误分类点对w和b进行一次随机梯度下降，更新w和b的参数，再重新执行上一步。
感知机模型的算法对偶形式
对偶就是从一个不同的角度去解答相似问题，但是问题的解是相通的，甚至是一样一样的。
上面的计算方式是感知机模型的原始形式，而使用对偶形式可以显著地减小计算量（特征维度越高越明显）。
在原始形式中，我们的参数w和b的更新是完全基于样本点的。如果我们将参数w和b表示为样本点的线性组合，我们可以记录各个样本点在参数更新中分别被使用了多少次。
假设初始值w0，b0均为0，然后使用随机梯度下降调整w，b，设现在迭代n次，w，b关于点（xi，yi）的增量分别是
$$
\alpha_{i} y^{(i)} x^{(i)}
$$
$$
\alpha_{i} y^{(i)}
$$
那么最后学习到的w , b可以表示为:
$$
w=\sum_{i=1}^{n} \alpha_{i} y^{(i)} x^{(i)}
$$
$$
b=\sum_{i=1}^{n} \alpha_{i} y^{(i)}
$$
其中αi=niη，ni表示第i个样本点由于误分类而进行更新的次数。
某个样本点用来更新w和b的次数越多，意味着它距离分离超平面就越近，也就越难正确分类。换句话说，这样的样本点对学习结果影响最大。
这样每次判断误分类点的条件就变为：
$$
y^{(i)}(\sum_{j=1}^{n} \alpha_{i} y^{(j)} x^{(j)} \cdot x^{(i)}+b) \leq 0
$$
这种形式有一个好处，就是在训练过程中，训练样本仅以内积xj乘以xi的形式出现。而且这个内积计算的结果在下面的迭代次数中可以重用。
如果我们事先用矩阵运算计算出所有的样本之间的内积，那么在算法运行时，仅仅一次矩阵内积运算比多次循环计算省时。这就节省了很多计算时间。
这个样本内积矩阵也就是所谓的Gram矩阵：
$$
G=[x^{(i)} \cdot y^{(j)}]
$$
原始形式中我们利用
$$
y^{(i)}\left(w \cdot x^{(i)}+b\right) \leq 0
$$
判断点是否是误分类点，因为每次w都有变化，所以每次都需要计算特征向量xi和w的乘积。
而在对偶形式中我们利用
$$
y^{(i)}\left(\sum_{j=1}^{n} \alpha_{i} y^{(j)} x^{(j)} \cdot x^{(i)}+b\right) \leq 0
$$
来判断，只要事先计算好Gram矩阵，通过查找Gram矩阵就能得到样本内积xj乘以xi，这比原始形式每次迭代都需要计算xi和w的乘积节省了大量的计算时间。
另外，内积形式很方便我们引入支持向量机的核方法，用来解决数据集线性不可分时的情况。
总结：
感知机的对偶形式本质上就是用样本xi和yi的线性组合去表达原始形式中的w，b。这种形式的表达可以引入样本内积，减少计算量。
这种形式下要更新的模型参数只有一个
$$
\alpha_{i}=n_{i} \eta
$$
我们每次用一个误分类样本xi对参数进行更新，只需要将相应的ni加1，即：
$$
\alpha_{i}=\eta(n_{i}+1)=\alpha_{i}+\eta
$$
注意对偶形式的参数初始化时，αi被初始化为0（因为ni一开始都为0）。
感知机计算实例见《统计学习方法》第29页的例2.1。