【机器学习】感知机

感知机（perceptron）是二分类的线性分类模型，属于监督学习算法。输入为实例的特征向量，输出为实例的类别（取+1和-1）。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机旨在求出该超平面，为求得超平面导入了基于误分类的损失函数，利用梯度下降法对损失函数进行最优化（最优化）。感知机的学习算法具有简单而易于实现的优点，分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的，因此属于判别模型。感知机由Rosenblatt于1957年提出的，是神经网络和支持向量机的基础。

定义

假设输入空间(特征向量)为 $X⊆Rn$ ，输出空间为Y={-1, +1}。输入 $x∈X$ 表示实例的特征向量，对应于输入空间的点；输出y∈Y表示示例的类别。由输入空间到输出空间的函数为

$f(x)=sign(w⋅x+b)$

称为感知机。其中，参数w叫做权值向量weight，b称为偏置bias。 $w⋅x$ 表示w和x的点积

sign为符号函数，即

在二分类问题中， $f(x)$ 的值（+1或-1）用于分类xx为正样本（+1）还是负样本（-1）。感知机是一种线性分类模型，属于判别模型。我们需要做的就是找到一个最佳的满足 $w⋅x+b=0$ 的w和b值，即分离超平面（separating hyperplane）。如下图，一个线性可分的感知机模型

这里写图片描述

中间的直线即 $w⋅x+b=0$ 这条直线。

线性分类器的几何表示有：直线、平面、超平面。

学习策略

核心：极小化损失函数。

如果训练集是可分的，感知机的学习目的是求得一个能将训练集正实例点和负实例点完全分开的分离超平面。为了找到这样一个平面（或超平面），即确定感知机模型参数w和b，我们采用的是损失函数，同时并将损失函数极小化。

对于损失函数的选择，我们采用的是误分类点到超平面的距离（可以自己推算一下，这里采用的是几何间距，就是点到直线的距离）：

其中 $||w||$ 是 $L2$ 范数。

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

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

那么，所有点到超平面的总距离为：

不考虑 $1/||w||$ ,就得到感知机的损失函数了。

其中M为误分类的集合。这个损失函数就是感知机学习的经验风险函数。

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

学习算法

感知机学习转变成求解损失函数 $L(w,b)$ 的最优化问题。最优化的方法是随机梯度下降法（stochastic gradient descent），这里采用的就是该方法。关于梯度下降的详细内容，参考wikipedia Gradient descent。下面给出一个简单的梯度下降的可视化图：

这里写图片描述

上图就是随机梯度下降法一步一步达到最优值的过程，说明一下，梯度下降其实是局部最优。感知机学习算法本身是误分类驱动的，因此我们采用随机梯度下降法。首先，任选一个超平面 $w_0$ 和 $b_0$ ，然后使用梯度下降法不断地极小化目标函数

极小化过程不是一次使M中所有误分类点的梯度下降，而是一次随机的选取一个误分类点使其梯度下降。 $L(w,b)$ 的梯度通过偏导计算：

然后，随机选取一个误分类点，根据上面的规则，计算新的 $w,b$ ，然后进行更新：

其中 $η$ 是步长，大于0小于1，在统计学习中称之为学习率（learning rate）。这样，通过迭代可以期待损失函数 $L(w,b)$ 不断减小，直至为0.

算法描述如下：

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

输入：T={(x1,y1),(x2,y2)...(xN,yN)}（其中xi∈X=Rn，yi∈Y={-1, +1}，i=1,2...N，学习速率为η）
输出：w, b;感知机模型f(x)=sign(w·x+b)
(1) 初始化w0,b0，权值可以初始化为0或一个很小的随机数
(2) 在训练数据集中选取（x_i, y_i）
(3) 如果yi(w xi+b)≤0
           w = w + ηy_ix_i
           b = b + ηy_i
(4) 转至（2）,直至训练集中没有误分类点12345678

解释：当一个实例点被误分类时，调整w,b，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直至超越该点被正确分类。

伪代码描述：

这里写图片描述