感知机(Perceptron)

感知机(Perceptron)是一种二分类的线性分类模型,输入为实例的特征向量,输出为实例的类别,取+1和-1值。感知机对应于输入空间中将实例划分为正负两类的分离超平面,属于判别模型,感知机学习旨在求出将训练数据进行线性划分的分离超平面,基于五分类的损失函数,利用梯度下降法对损失函数进行极小化,求得模型参数。该模型有原始形式和对偶形式两种形式。

1. 感知机模型

假设输入空间(特征空间)是 $\chi \subseteq R^n$,输出空间时 $Y=\{+1, -1\}$,输入 $x \in \chi$ 表示实例的特征向量,对应于输入空间(特征空间)的点,输出 $y \in Y$ 表示实例的类别,由输入空间到输出空间的函数:

称为感知机,其中w和b为感知机模型参数, $w\in R^n$ 叫做权值(weight)或权值向量(weight vector), $b\in R$ 叫做偏置(bias), $w \cdot x$ 表示 $w$ 和 $x$ 的内积,sign是符号函数

假设训练数据集是线性可分的,感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面 $S$。关于如何得到 $w$ 和 $b$ 的值,是通过损失函数来求得的。损失函数一般要求损失函数是参数 $w,b$ 的连续可导的函数,因此如果使用误分类点的数目作为损失函数显然不利于参数的优化。在感知机中,我们所选择的损失函数是误分类点到分离超平面的 $S$ 的距离。关于空间中一点 $x_0$ 到分离超平面的距离为:

若$x_0$是正实例点时,被误分类负实例点,则此时 $w\cdot x_0 +b <0, y_0="1$," 若$x_0$是负实例点时,被误分类正实例点,则此时="" $w\cdot="" x_0="" +b="">0, y_0=-1$, 因此 $y_0(w\cdot x_0 +b)<0$,

因此,对于误分类点的数据$(x_i,y_i)$,该点到分离超平面$S$的距离可以表示为:

因此,所有误分类点到分离超平面的距离和为:

其中, $M$ 为误分类点的集合。

在线性函数中,我们同时扩大或缩小 $w,b$,函数不改变,因此我们可以使 $||w||=1$.因此,感知机的损失函数为(经验风险函数):

2. 感知机模型的优化

2.1 原始形式

感知机学习算法是误分类驱动的,采用随机梯度下降法。对于固定的误分类集合 $M$,那么损失函数的梯度为

若随机选取一个误分类点$(x_i, y_i)$,对$w,b$ 进行更新:

其中$\eta(0<\eta \leq 1)$是步长或学习率(learning rate)

感知机学习算法的原始形式

输入:训练数据集$T=\{(x_1,y_1), (x_2,y_2),\dots,(x_N,y_N) \}$,学习率为$\eta(0<\eta \leq 1)$

输出:w,b;感知机模型$f(x)=sign(w\cdot x+b)$

(1) 选取初始值 $w_0, b_0$

(2) 在训练集中选取数据$(x_i, y_i)$

(3) 如果 $y_i(w\cdot x_i +b) \leq 0$

(4) 转至 (2),直至训练集中没有误分类点

2.2 对偶形式