机器学习---感知机(Machine Learning Perceptron)

2021年11月25日 阅读数:3
这篇文章主要向大家介绍机器学习---感知机(Machine Learning Perceptron),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

感知机(perceptron)是一种线性分类算法,一般用于二分类问题。感知机由Rosenblatt在1957年提出,是神经网络和支持向量机的基础。经过修改损失函数,它能够发展成支持向量机;经过多层堆叠,它能够发展成神经网络。所以,虽然如今已经再也不普遍使用感知机模型了,可是了解它的原理仍是有必要的。算法

 

先来举一个简单的例子。好比咱们能够经过某个同窗的智商和学习时间(特征)来预测其某一次的考试成绩(目标),若是考试成绩在60分以上即为及格,在60分如下为不及格。这和线性回归相似,只不过设定了一个阈值,使得其能够处理分类问题。网络

 

所以,咱们定义:给定特征向量x=([x1,x2,...,xn])T以及每一个特征的权重w=([w1,w2,...,wn])T,目标y共有正负两类。那么:机器学习

 

对于某个样本,若是其 wx > 阈值(threshold),那么将其分类到正类,记为y=+1;函数

                         若是其 wx < 阈值(threshold),那么将其分类到负类,记为y=-1;学习

(注:wx是特征向量和权重向量的点积/内积,wx=w1x1+w2x2+...+wnxn优化

 

也就是说,上式分为两种状况:wx - 阈值(threshold)> 0 或 wx - 阈值(threshold)< 0。咱们能够将目标方程式简写成:y=sign(wx+b+),对y的估计就是url

(注:sign是符号函数)spa

 

wx+b=0对应于特征空间中的一个超平面,用来分隔两个类别,其中w是超平面的法向量,b是超平面的截距。.net

(这里须要用到线性代数的知识点。若是一非零向量垂直于一平面,这个向量就叫作该平面的法线向量,简称法向量。假设在二维空间,一条直线能够由一个点和法向量肯定。其点法式方程为。)3d

 

为了便于叙述,把b并入权重向量w,记做,特征向量则扩充为。这样咱们能够把对y的估计写成:。(为了简便的缘故,下面仍是都写成f(x)=sign(wx))

 

咱们但愿能找出这样一个超平面(固然在二维空间是找到一条直线),使得全部样本都能分类正确。那么应该怎么作呢?一个天然的想法就是先随意初始化一个超平面,若是出现分类错误的现象,那么咱们再将原来的这个超平面进行修正,直至全部样本分类正确。从必定程度上讲,人类就是如此进行学习的,发现错误即改正,因此说感知机是一个知错能改的模型。

 

错误分为两种状况:

一种状况是错误地将正样本(y=+1)分类为负样本(y=-1)。此时,wx<0,即wx的夹角大于90度,所以修正的方法是让夹角变小,能够把w向量减去x向量,也就是将w修正为w+yx。

另外一种状况是错误地将负样本(y=-1)分类为正样本(y=+1)。此时,wx>0,即wx的夹角小于90度,所以修正的方法是让夹角变大,能够把w向量加上x向量,也就是将w修正为w+yx。

    

 

能够看到,这两种状况下修正的方式都是相同的,所以,咱们能够经过不断迭代,最终使超平面作到彻底分类正确。咱们将PLA(Perceptron Linear Algorithm,即线性感知机算法)简单总结以下:

1,初始化w

2,找出一个分类错误点

3,修正错误,假设迭代次数为t次(t=1,2,...),那么修正公式为:

4,直至没有分类错误点,返回最终的w

 

下面是台湾大学林轩田老师在《Machine Learning Foundation》中提到的示例,用来讲明感知机算法。

 

首先,用原点到x1点的向量做为wt的初始值。

 

分类直线与wt垂直,能够看到,有一个点x3被分类错误,原本是正类,却被分到了负类,所以咱们须要使wt与x3之间的夹角变小,wt更新为wt+1

 

不断修正,直至彻底分类正确。

 

从另外一个角度来看,咱们只要肯定了参数w,也就能够找到这个分离超平面。和其余机器学习模型相似,咱们首先定义损失函数,而后转化为最优化问题,能够用梯度降低等方法不断迭代,最终学习到模型的参数。

 

咱们很天然地会想到用错误分类点的总数来做为损失函数,也就是让错误分类点的总数最小:。可是根据林轩田老师所说,这是一个NP Hard问题,是没法解决的。

 

既然不能用错误分类点的总数做为损失函数,那么只能寻找其它表现形式。感知机算法选择将全部错误分类点距离分离超平面的总距离做为损失函数,也就是要让错误分类点距离超平面的总长度最小。

 

这个总长度是怎么来的呢?

 

首先,输入空间Rn中任意一点x0到超平面S的距离为:

 

对于错误分类点(xi,yi)来讲:

 

所以,错误分类点xi到超平面S的距离能够写成:

 

 假设超平面的错误分类点的集合为M,那么全部的错误分类点到超平面S的总距离为:

 

 不考虑 ||w|| ,就获得感知机学习的损失函数:

 

(注:为何不考虑 ||w|| ?由于感知机算法最终并不关心超平面离各点的距离有多少,只是关心最后是否已经彻底分类正确,因此在最后才能够不考虑||w||。)

 

而后就是使用随机梯度降低法(SGD)不断极小化损失函数。损失函数L(w,b)的梯度由如下式子给出(对w,b分别求偏导):

 

随机选取一个误分类点(xi,yi),对w,b进行更新:

 

直至超平面可以彻底分类正确,返回w,b。这和上面说的方法实际上是同样的。
 

算法看起来很简单是吧?可是还有几个小细节咱们须要考虑。

  • 分离超平面是否只有一个?显然,若是咱们把上面林轩田老师示例里的这个分类直线稍微倾斜一点,新的直线也仍是能够彻底分类正确的。也就是说,感知机算法的解不止一个,这主要取决于w初始值和分类错误点的选择。
  • 使用感知机算法是否须要知足某种假设?因为感知机算法是线性分类器,所以数据必须线性可分(linear seperable),不然,感知机算法就没法找到一个彻底分类正确的超平面,算法会一直迭代下去,不会中止。
  • 假如数据知足线性可分这一假设,那么是否通过T次迭代,感知机算法必定能中止呢?也就是说,感知机算法最后是否必定能收敛,会不会产生循环重复的问题。答案是会收敛。感知机算法收敛性的证实可见:http://txshi-mt.com/2017/08/03/NTUML-2-Learning-to-Answer-Yes-No/
  • 咱们如今知道感知机算法最终必定会停下来,可是多久会停呢?因为T和目标参数wf有关,而wf是未知的,所以咱们不知道T最大是多少。

 

上面讨论的是数据完美线性可分的状况,那么若是数据线性不可分呢?现实中,不少时候都存在两个分类的数据混淆在一块儿的状况,PLA显然解决不了这样的问题。那么怎么办呢?其实只需把感知机算法稍微修改一下,找到一个犯错最少的超平面便可。具体的作法就是在寻找的过程当中把最好的超平面记住(放在口袋里),所以这被称之为口袋算法(Pocket Algorithm)。

 

Pocket Algorithm简单总结以下:

1,初始化w,把w做为最好的解放入口袋

2,随机找出一个分类错误点

3,修正错误,假设迭代次数为t次(t=1,2,...),那么修正公式为:

4,若是wt+1比w犯的错误少,那么用wt+1替代w,放入口袋

5,通过t次迭代后中止,返回口袋里最终的结果