机器学习之感知机

一、定义

        感知机是Frank Rosenblatt在1957年就职于Cornell航空实验室（Cornell Aeronautical Laboratory）时所发明的一种人工神经网络。感知机是最简单的单层人工神经网络，也是二元线性分类模型，是神经网络和支持向量机的基础。感知机学习旨在求出将训练数据集进行线性划分的分类超平面，为此，导入了基于误分类的损失函数，然后利用梯度下降法对损失函数进行极小化，从而求出感知机模型。其输入为实例的特征向量，输出为实例的类别，取+1和-1。

二、模型介绍及损失函数推导

       感知机模型如下：       

感知机模型公式

       其中，x为输入向量，sign（x）为符号函数，当括号内的值大于0时，函数值为1，当括号内的值小于等于0时，函数值为-1。w为权值向量，b为偏置向量。求感知机模型就是求模型参数w和b，需要定义一个损失函数并通过梯度下降法将损失函数最小化来求w和b。这里选择的损失函数是求误分类点到分类超平面S的总距离。输入空间中任一点到超平面S的距离为：

其中，||w||为w的L2范数。

其次，结合感知机模型，误分类点（xi,yi）应满足：

那么，误分类点到超平面S的距离（去绝对值后）为：

假设误分类点集合为M，则所有误分类点到分类超平面S的总距离即损失函数为：

       由于感知机的任务是进行二分类工作，它最终并不关心得到的超平面离各点距离的多少（与SVM不同），只关心最后分类结果是否正确即误分类点的个数，所以在推导损失函数时，可以不考虑1/||w||，则最终感知机模型的损失函数如下：

 

三、算法实现

       得到感知机的损失函数之后，需要求得w和b使得该函数取得最小值。由于该函数是凸函数，所以可以使用梯度下降法或者拟牛顿法来求解。常用的是剃度下降法，但是使用普通的基于所有样本的梯度和的均值的批量梯度下降法是行不通的。因为该损失函数是误分类驱动的，只有误分类的M集合里面的样本才可以参与损失函数的优化。于是只能采用随机梯度下降法或者小批量梯度下降法。感知机模型采用的是随机梯度下降法，即每次只需要使用一个误分类点来更新梯度。

损失函数的梯度是对w和b求偏导，即：

那么梯度下降公式，即随机选取一个误分类点(xi,yi)，对w，b进行更新式子如下：

其中，n（0<n<=1）是学习率，即学习的步长。综上，感知机学习算法如下：

        这种算法的基本思想是：当一个实例点被误分类，即位于分类超平面错误的一侧时，则调整w和b，使分类超平面向该误分类点的一侧移动，以减少该误分类点与超平面的距离，直到超平面越过该误分类点使其被正确分类为止。

四、总结

优点：（1）感知机学习算法简单且易于实现。

           （2）当样本线性可分的情况下，且学习率合适时，算法具有收敛性。

缺点：（1）感知机只能用于线性分类问题，不能解决异或分类问题，但是非线性问题是普遍存在的，所以感知机的使用率较低。

           （2）收敛速度慢。当样本线性不可分时，算法不收敛，且无法判断样本是否线性可分。