机器学习：感知机的基本原理

本文最后更新于 320 天前，其中的信息可能已经有所发展或是发生改变。

前言

感知机是一个古老的模型，1957年由Rosenblatt提出，是神经网络和支持向量机的基础

感知机模型

感知机是一种线性分类模型，属于判别模型。感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面，例如，在一个二维平面直角坐标系中，我们要将两种类别的点通过一根线来分开。随着维度增加，由二维上升到三维、四维，这个时候，这根线也就变成了超平面，我们需要找到一个超平面将所有二元类别分开。当然了，并不是所有时候都能找到这个平面，在这个时候，那就说明这些数据线性不可分，感知机的大前提就是线性可分。这严重限制了他的发挥，所以感知机在近代的应用也比较少了。但是作为入门还是挺好的。

数学表示

用数学的语言来说，如果我们有m个样本，每个样本对应于n维特征和一个二元类别输出，如下：

$(x_{1}^{(0)}, x_{2}^{(0)}, \dots, x_{n}^{(0)}, y_{0}), (x_{1}^{(1)}, x_{2}^{(1)}, \dots, x_{n}^{(1)}, y_{1}), \dots, (x_{1}^{(m)}, x_{2}^{(m)}, \dots, x_{n}^{(m)}, y_{m})$

我们的目标是找到这样一个超平面：

$w_{0} + w_{1} x_{1} + . . . . + w_{n} x_{n} + b = 0$

其中b是偏置项。

这样，带入特征之后得出一个target，target大于0的在这个平面的一端，小于0的在另一端。这样我们就将所有点都分开了,如果数据线性可分，这样的超平面一般都不是唯一的，也就是说感知机模型可以有多个解。

为了简化这个超平面的写法，我们增加一个特征,x0=1,这样超平面为

$\sum_{i = 0}^{n} ω_{i} x_{i} + b = 0$

进一步用向量来表示为: $ω \cdot x + b, 其中 ω 为 (n + 1) \times 1 的向量， x 为 (n + 1) \times 1 的向量， \cdot 为内积，$
后面我们都用向量来表示超平面
而感知机的模型可以定义为：

$y = sign (w \cdot x + b)$

其中：

$sign (x) = {\begin{cases} - 1 & x < 0 \\ 1 & x \geq 0 \end{cases}$

感知机的几何意义

对应于特征空间Rn中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点（特征向量）分别被分为正、负两类。因此，超平面S称为分离超平面（separating hyperplane）

如图，这是一个只有二维特征的向量空间，这里的超平面是一条直线。

对于一般的点到直线的距离：对于Ax+By+C=0
点P的坐标为(x0,y0)

$d = \frac{A x_{0} + B y_{0} + C}{\sqrt{A^{2} + B^{2}}}$

在该图中：横坐标为x1,纵坐标为x0，系数对应分别为w1,w2所以对于该图，点到该线的距离可以写成：

$d = \frac{w_{1} x_{1} + w_{2} x_{2} + b}{\sqrt{w_{1}^{2} + w_{2}^{2}}}$

对应着，当维度增加，点到超平面的距离就是：

$d = \frac{| w \cdot x + b |}{∥ w ∥}$

其中||w||是l2范数，l2范数就是w平方和的开平方

感知机的损失函数

损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是参数w，b的连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面S的总距离，这是感知机所采用的

上边已经推出点到超平面的距离为

$d = \frac{| w \cdot x + b |}{∥ w ∥}$

其次，对于误分类的数据(xi,yi)来说，因为：

$y_{i} ω \cdot x_{i} < 0$

它所以到平面的距离是：

$- \frac{^{} y_{i} ω \cdot x_{i} + b}{∥ ω ∥}$

前面要加一个负号将整体符号变成正的
我们假设所有误分类的点的集合为M，则所有误分类的样本到超平面的距离之和为

$- \frac{1}{∥ ω ∥} \sum y_{i} (ω \cdot x_{i} + b) x_{i} \in M$

这样我们就得到了初步的感知机模型的损失函数。分子和分母都含有ω,当分子的ω扩大N倍时，分母的L2范数也会扩大N倍。也就是说，分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1，然后求另一个即分子自己或者分母的倒数的最小化作为损失函数，在感知机模型中，我们采用的是保留分子，分母为1.即最终感知机模型的损失函数简化为：

$L (w, b) = - \sum_{x_{i} \in M} y_{i} (ω \cdot x_{i} + b)$

显然，损失函数是非负的，如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小

感知机模型损失函数的优化方法

损失函数为：

$L (w, b) = - \sum_{x_{i} \in M} y_{i} (ω \cdot x_{i} + b)$

感知机模型采用梯度下降来优化，但是由于损失函数针对误分类点的，所以不能采用批量梯度下降，需要随机梯度下降法(SGD)。

损失函数基于ω向量的的偏导数为：

$\frac{\partial}{\partial ω} L (ω, b) = - \sum_{x_{i} \in M} y_{i} x_{i}$

ω的梯度下降迭代公式应该为：

$ω = ω + η y_{i} x_{i}$

基于b的的偏导数为

$\frac{\partial}{\partial b} L (ω, b) = - \sum_{x_{i} \in M} y_{i}$

b的梯度下降迭代公式为：

$b = b + η y_{i}$

η为步长(学习率)、

感知机模型的算法的原始形式

输入: 训练数据集T=[ (x,,)，(x,,Y),...，(xN,YN)}，其中x;eX=RnY;EY=[-1,+1}，=1,2,...,N;学习率n(0<n<1)

输出: w，b;
感知机模型f(x) =sign(wx+b)。

选取初值w,,b;
在训练集中选取数 (xi，yi)
如果yi(wx+b) <0
对ω、b向量进行一次随机梯度下降的迭代：
ω=ω+ηyixi
b=b+ηyi
检查训练集里是否还有误分类的点，如果有，转到第二步)，直至训练集中没有误分类点。

感知机模型的算法的对偶形式

概念

这是原始的迭代公式
ω=ω+ηyixi
b=b+ηyi
们每次梯度的迭代都是选择的一个样本来更新ω
向量。最终经过若干次的迭代得到最终的结果。对于从来都没有误分类过的样本，他被选择参与ω
迭代的次数是0，对于被多次误分类而更新的样本j，它参与ω迭代的次数我们设置为mj
当ω初始值取0的时候，ω的值可以表示为：

$ω = η \sum_{j = 1}^{m} m_{j} y_{j} x_{j}$

其中mj为样本(x(j),y(j))在随机梯度下降的这一步之前因为误分类而更新的次数。
每一个样本(x(j),y(j))的mj的初始值为0，每当此样本在某一次梯度下降迭代中因误分类而更新时，mj的值加1。
由于步长η为常量
所以我们令αj=ηmj
得到： $ω = \sum_{j = 1}^{m} α_{j} y_{j} x_{j}$
同理：

$b = \sum_{j = 1}^{m} α_{j} y_{j}$

在每一步判断误分类条件的地方，原始是：
yi(wx+b) <0
那么此时，我们就可以这么表示：

$y_{i} (\sum_{j = 1}^{N} α_{j} y_{j} x_{j} \cdot x_{i} + b) < 0$

观察这个式子中，包含两个样本x(i)和x(j)
的内积，而且这个内积计算的结果在下面的迭代次数中可以重用。所以我们事先用矩阵运算计算出所有的样本之间的内积，那么在算法运行时，仅仅一次的矩阵内积运算比多次的循环计算省时。计算量最大的判断误分类这儿就省下了很多的时间，这也是对偶形式的感知机模型比原始形式优的原因。
该矩阵的名字为Gram矩阵
它是一个对称矩阵，记为 G=[x(i)∙x(j)]

算法过程：

输入: 训练数据集T=(x1,y1),(x2,y2),...,(xN,yN)，yi∈{−1,+1}，学习率η(0<η<1)

感知机模型 $f (x) = sign (\sum_{j = 1}^{n} α_{j} y_{j} x_{j} \cdot x + b)$

其中α=(α1,α2,...,αn)T

输出：α,b，(w可以由α求得)；

赋初值 α0,b0，计算Gram矩阵G=[xi,xj]N×N
选取数据点(xi,yi)
判断该数据点是否为当前模型的误分类点，即判断若 $y_{i} (\sum_{j = 1}^{N} α_{j} y_{j} x_{j} \cdot x_{i} + b) < 0$
则更新
$a_{i} = a_{i} + η$
$b = b + η y_{i}$
检查训练集里是否还有误分类的点，如果有，转到第二步)，直至训练集中没有误分类点。

原始形式和对偶形式的选择

对偶形式比原始形式的优点就是Gram矩阵，计算量最大的判断误分类这儿就省下了很多的时间，省去了内积用的时间，
所以在向量维数（特征数）过高时，计算内积非常耗时，应选择对偶形式算法加速

小结

感知机虽然已经不怎么用了，但是他是很多算法的基础，学一下子还是挺好的。
然后，这也是我学习机器学习的开端，记着这个开端！
最后：这篇文章的百分之60的时间都用来整latex数学公式了，倒也不是语法难，毕竟有gpt,但问题是我没有找到能将latex和markdown完美结合的插件！。。。

前言