0%

感知机模型

感知机模型是一个二分类模型,通常将输入空间映射到新的特征空间中再进行计算,模型的学习目标是寻找能够在特征空间内将实例划分为正负两类的分离超平面,其数学表达式如下:

$$ y(x)=f(w^T\phi(x))=w_0\phi(x_0)+w_1\phi(x_1)+…+w_n\phi(x_n)$$

这里 $ f(\cdot)$ 叫做激活函数,有时也被称为单位阶跃函数:

$$f(a)= \begin{cases} +1& a \ge 0 \\ -1& a \lt 0 \end{cases}$$

感知机学习策略

决策函数:
$$ g(x) = \sum_{i=1}^m w_i x_i + w_0 = {\bf w^T x} + bw_0$$

增广表示:
$$ g(x) = \sum_{i=1}^m w_i x_i = {\bf \hat w^T \hat x} $$
其中,${\bf \hat w} = ({\bf w}, b)^T$ ,${\bf \hat x} = ({\bf x}, 1)^T$。

所以其学习准则为:最小化错分样本的误差代价.如果训练集是可分的,感知机的学习目的是求得一个能将训练集正实例点和负实例点完全分开的分离超平面。对于损失函数的选择,我们采用的是误分类点到超平面的距离:

$$\dfrac{1}{\parallel w\parallel}|w*x_{0}+b|$$

对于误分类点 $(x_i,y_i)$ 来说:

$$- y_i(w * x_{i}+b)>0$$

误分类点到超平面的距离为:

$$ -\dfrac{1}{\parallel w\parallel}y_i(w*x_{0}+b) $$

记误分类点的集合为 $M$,那么所有误分类点点到超平面的总距离为:

$$-\dfrac{1}{\parallel w\parallel} \sum_{x_i\epsilon M} y_i|w*x_{0}+b|$$

不考虑权重,得到感知机的损失函数:

$$ L(w,b) = - \sum_{x_i\epsilon M} y_i(w*x_{0}+b) $$

可以看出,损失函数是非负的。如果没有误分类点,则损失函数的值为 $0$,而且误分类点越少,误分类点距离超平面就越近,损失函数值就越小。同时,损失函数 $L(w,b)$ 是连续可导函数。

感知机原始形式

感知机学习算法本身是误分类驱动的,因此我们采用随机梯度下降法。首先,任选一个超平面 $w_0$ 和 $b_0$,然后使用梯度下降法不断地极小化目标函数:

$$ min_{w,b} L(w,b) = - \sum_{x_i\epsilon M} y_i(w*x_{0}+b) $$

极小化过程不是一次使 $M$ 中所有误分类点的梯度下降,而是一次随机的选取一个误分类点使其梯度下降,损失函数的梯度为:
$$ \frac{\partial L(w,b)}{\partial w} = - \sum_{x_i\epsilon M}y_ix_i \\\frac{\partial L(w,b)}{\partial b} = - \sum_{x_i\epsilon M}y_i $$

随机选取一个误分类点 $(x_i, y_i)$,对参数进行更新:
$$w_{t+1}=w_t + \eta {x_iy_i}\\
b_{t+1}=b_t + \eta {y_i}$$

感知机随机梯度下降法的直观解释:对于感知机而言,当一个样本点被误分类之后,被误分类的样本点会位于决策超平面的错误的一侧,这时感知机会调整 $w,b$ 的值,使决策超平面向该误分类点的一侧移动,移动的尺度由 $\eta$ 决定,每一次移动,都可以减少误分类点和决策超平面之间的距离,直到决策超平面越过该误分类点,使其被正确分类为止。

算法举例

感知机对偶形式

感知机算法的对偶形式,是针对感知机随机梯度下降法来设计的。其基本思想是:感知机的原始形式中,$x$ 是自变量,$y$ 是因变量, $w,b$ 是模型的参数,通俗点说,在感知机的原始算法中,是用参数 $w,b$ 来表示 $x$ 和 $y$ 的。对偶式就是要把这这个关系反过来,用样本 $x$ 和 $y$ 的线性组合来表示参数 $w$ 和 $b$。

感知机随机梯度下降法的参数更新方式为:

$$ w_{t+1}=w_t + \eta {x_iy_i}\\
b_{t+1}=b_t + \eta {y_i}$$

对于第 $i$ 个样本,每次其被分类错误,都会有一次基于 $x_i, y_i$的 权值更新,那么假设到最后,整个感知机算法更新结束时,第 $i$ 个样本点总共更新了 $n_i$ 次。这样就不难得到最后学习到的参数为:

$$ w=\sum_{i=1}^N{n_i \eta y_i x_i} = \sum_{i=1}^N{\alpha_i y_i x_i} \\
b=\sum_{i=1}^N{n_i \eta y_i} = \sum_{i=1}^N{\alpha_i y_i} $$

感知机模型的对偶形式为:

$$ y(x)=f(w^Tx+b)=f({\sum_{j=1}^N{\alpha_j y_j x_j}}*x + \sum_{j=1}^N{\alpha_j y_j}) $$

上式中,为了和样本点的下标 $(x_i, y_i)$ 区别开来,这里选用的下标是 $j$。

其训练过程为:在训练集中选取一个样本点 $(x_i, y_i)$ ,如果该点分类错误,那么该点的权值更新次数加一次:

$$n_i=n_i+1$$

于是,参数更新规则为:

$$ \alpha_i = \eta(n_i+1) = \alpha_i + \eta \\ b = b + \eta y_i $$

感知机模型对偶形式的直观解释:在所有训练样本依次循环的输入到算法中,如果对于某个样本分类错误,那么算法就根据该样本点做一次更新。循环上面这个过程,直到所有的样本点都能够分类正确。

在感知机对偶式的训练过程中,对错误分类点有:

$$y_i({\sum_{j=1}^N{\alpha_j y_j x_j}}*x_i + \sum_{j=1}^N{\alpha_j y_j}) \le 0$$

上式可以重写为:

$$ y_i(\sum_{j=1}^N{\alpha_j y_j (x_j*x_i)} + \sum_{j=1}^N{\alpha_j y_j}) \le 0 $$

这就表明:样本点的特征向量是以内积的形式存在于感知机对偶形式的训练算法中。为了简化计算过程,可以将训练集合之间的内积提前求出来,然后在训练过程中直接调用,样本点间的内积矩阵也就是所谓的 $Gram$ 矩阵:

$$G=[x_i,x_j]_{N*N}$$

这里的内积,也就是 SVM 算法中核方法的原型。

算法举例

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 李航,《统计学习方法》,清华大学出版社