感知机算法(Perceptron Learning Algorithm)

Python017

感知机算法(Perceptron Learning Algorithm),第1张

感知机(perceptron)是二类分类的线性分类模型,它的思想很简单,就是在一个二维空间中寻找一条直线将红点和蓝点分开(图1),类比到高维空间中,感知机模型尝试寻找一个超平面,将所有二元类别分开(图2)。

如果我们找不到这么一条直线的话怎么办?找不到的话那就意味着类别线性不可分(图3),也就意味着感知机模型不适合你的数据的分类。使用感知机一个最大的前提,就是数据是线性可分的。

如果我们有n个样本,每个样本有m维特征和一个二元输出类别:

感知机的目标是找到一个超平面:

让其中一个类别的样本满足 ,而另一类样本满足

,从而样本线性可分。但这样的超平面并不是唯一的,感知机模型采取不同的初始值( )解可能会不同。

我们用相量方式对上式进行表达: ,由此感知机的模型可以定义为:

,其中:

例如:将一个新的样本 带入训练好的模型 ,当   ,  被分为 类。当  ,  被分为 类。

我们将满足 的样本类别输出值取 ,满足 的样本类别输出值取 。从而正确分类的样本满足 ,而错误分类的样本满足 。损失函数的优化目标是使所有被错误分类的样本到超平面的距离之和最小。

一个被错误分类的样本 , ,到超平面的距离是 ,

其中    。 为超平面的法向量, 的大小变化并不会影响样本点到超平面的距离。我们令 ,并且假设所有错误分类的点的集合为M,则所有错误分类的样本到超平面的距离之和为:

最终构建的损失函数为:

感知机模型选择的是采用随机梯度下降,这意味着我们每次仅仅需要使用一个误分类的点来更新梯度。损失函数 的梯度如下:

随机选取一个错误分类点 ,对 进行更新:

式中 为初始值, 是步长(learning rate)。通过这样迭代可以使损失函数 不断减小,直到为0。

感知机模型的优化方法可以通俗的解释为:当一个样本被错误分类,即位于分类超平面的错误一侧时,则调整 的值,使分类超平面向该错误分类点的一侧移动,以减少该错误分类点与超平面间的距离,直至超平面越过该错误分类点,最终被正确分类。

上一节的感知机模型的算法形式我们一般称为感知机模型的算法原始形式。对偶形式是对算法执行速度的优化。对偶形式的基本想法是将 表示为样本 和标签 的线性组合,通过求解其系数而求得 。我们取初始值 为 ,选取错误分类样本 对 进行更新有:

假设为了将样本 正确分类而更新 的次数为 ,每一个样本 的 的初始值为 ,每当次样本在某一次梯度下降迭代中因误分类而更新时, 的值 ,则 关于 的增量分别为 和 。则用所有样本对 进行更新,最后得到的 可以表示为

的通俗解释:如果 的值越大,那么意味着样本 经常被误分。很明显离超平面很近的点,当超平面稍微移动一点点, 的类别就发生变化。

我们用 的等价形式  来判断错误分类。上式中 表示的是两个样本的内积,而且这个内积的结果在更新 的过程中会多次使用。如果我们事先用矩阵运算计算出所有的样本之间的内积,那么在算法运行时, 仅仅一次的矩阵内积运算比多次的循环计算省时。 计算量最大的判断误分类这儿就省下了很多的时间,这也是对偶形式的感知机模型比原始形式优的原因。

样本的内积矩阵称为Gram矩阵,它是一个对称矩阵,记为

例如: , , 则Gram矩阵为

                  

   G=      =   

                    

以上为建立感知机模型的相关理论知识,如果有需要用python建立感知机模型进行分类的小伙伴的可以上访问我的github:

https://github.com/Rocky1ee/Perceptron-Model

小伙伴们如果觉得文章还行的请点个赞呦!!同时觉得文章哪里有问题的可以评论一下  谢谢你!

最基础的部分的话需要:线性代数,机器学习,微积分,优化等等。

几乎所有操作都有矩阵运算,所以至少最基础的线性代数需要掌握

建议从单一的感知机Perceptron出发,继而认识到Decision Boundary(判别边界),以及最简单的一些“监督训练”的概念等,有机器学习的基础最好。就结果而言,诸如“过拟合”之类的概念,以及对应的解决方法比如L1 L2归一,学习率等也都可以从单个感知机的概念开始入门。

从单层感知器推广到普通的多层感知器MLP。然后推广到简单的神经网络(激活函数从阶跃“软化”为诸如tanh等类型的函数),然后引入特定类型的网络结构,比如最基本的全连接、前向传播等等概念。进而学习训练算法,比如反向传播,这需要微积分的知识(Chain rule),以及非线性优化的最基础部分,比如梯度下降法。

其次至少需要具备一些适用于研究的编程语言的技能,例如python,matlab,(C++也可行)等,哪怕不自己实现最简单的神经网络而是用API,也是需要一定计算机能力才能应用之。