感知机(Perceptron)是怎么实现“知错能改”的?

感知机(perceptron)是二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的分离超平面,属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面,为此导入了基于误分类的损失函数,利用梯度下降法对损失函数进行极小化,求得感知机模型。感知机学习算法具有简单而易于实现的优点,分为原始形式和对偶形式。感知机是神经网络与支持向量机的基础。

划重点:简单说就是个二分类的线性分类模型,感知机学习,就是通过训练数据集,求得感知机模型,即求的模型参数。

感知机模型

  • 由输入空间到输出空间的如下函数称为感知机:f(x)=sign(x.w+b) w叫做权值(weight)或权值向量,b叫做偏置(bias)。
  • 感知机模型的原理:给每一个属性一个权重w,对属性值和权重的乘积求和,将这个值和一个阀值(0/1)进行比较,可以判定比如是否录用这个应聘者。
  • 感知机的几何解释:线性方程. 线性分类器的几何表示:直线、平面、超平面。w.x+b=0
  • 对应于特征空间Rn中的一个超平面S,其中w是超平面的法向量[注],b是超平面的截距。这个超平面将特征空间划分为两个部分,位于两部分的点分别被分为正、负两类。因此,超平面S称为分离超平面(separating hyperplanes)。

注:比如在二维平面里,分界是一条直线的情形下,y=wTx,那么分界线对应的y取值都是0,此时对于这条线来说,w就是分界线的法向量。

感知机是咋学习的,为啥说它是知错能改?

1. 假设数据集线性可分,感知机的学习目标是求得一个能够将训练集正实例点和负实例点完全正确分开的超平面。为了找到这个超平面,即确定感知机模型参数w,b,需要确定一个学习策略,即定义(经验)损失函数并将损失函数极小化。

损失函数的一个自然选择是误分类点的总数,但是损失函数不是w,b的连续可导函数,不易优化。损失函数的另一个选择是计算误分类点到超平面的总距离。 输入空间中任一点x0x0到超平面S的距离为:

任一点到超平面距离

感知机sign(w.x+b)学习的损失函数定义为(重点):

损失函数

一个特定样本的损失函数,在误分类的时候该函数是w和b的线性函数,而正确分类的时候是0,因此损失函数时w和b的连续可导函数。

划重点:感知机学习策略就是在假设空间中选取使感知机的损失函数最小的模型参数w和b,即感知机模型。

2. 感知机学习算法转化为求解感知机损失函数的最优化问题,最优化的方法是随机梯度下降法。

学习算法: 输入:训练数据集T、学习率α 输出:w,b;感知机模型f(x)=sign(w.x + b) (1) 选取初值w0,b0 (2) 在训练集中选取数据(xi,yi) (3) 如果yi(w.xi + b) <= 0,使用随机梯度下降法更新w和b (4) 转至(2),直至训练集中没有误分类点(重复的将误分类的点一直更新)

任意选取一个超平面w0,b0w0,b0,然后用梯度下降法不断地极小化目标函数

梯度

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

其中 η 是步长,又称为学习速率。这样通过迭代可以期待损失函数 L(w,b) 不断减小,直到 0.

这种学习算法直观上解释:当一个实例类被误分类,即位于分离超平面的错误一侧时,则调整w,b的值,使分离超平面向该分类点的一侧移动,以减少该误分类点与超平面的距离,直至超平面越过该误分类点使其被正确分类。

  • 刚开始,随便一点,开始两个相同类型连线即法向量,作垂线得到初始的分类平面(线)

初始(来源:台湾国立大学林老师课程)

  • 当检测到错误后,通过旋转开始修正,得到优化的分类
  • 不断检测,直到没有错误

最后

但是这个PLA算法真的会停吗?

分两种情况讨论:数据线性可分;数据线性不可分

注意PLA 停止的条件是,对任何数据分类都正确,显然数据线性不可分时PLA 无法停止,那么我们可以用Pocket算法,运用贪心思想找到一个比较好的。

数据线性可分:

一定存在完美的w(记为wf), 使得所有的(xi, yi), yi = sign(wf*xi).可知:

下面证明在数据线性可分时,简单的感知机算法会收敛。(这个是根据林老师的定义给的,我感觉比较清晰,详细的可以看《统计学习方法》第二章)

而且量向量夹角余弦值不会大于1,可知T 的值有限。T=1,即向量内积为1,两向量重合,由此,我们证明了简单的PLA 算法可以收敛。

数据线性不可分:

Pocket Algorithm当数据线性不可分时(存在噪音),简单的PLA 算法显然无法收敛。我们要讨论的是如何得到近似的结果。我们希望尽可能将所有结果做对,即:

寻找 wg 是一个NP-hard 问题!只能找到近似解。算法如下:

Pocket Algorithm

与简单PLA 的区别:迭代有限次数(提前设定);随机地寻找分错的数据(而不是循环遍历);只有当新得到的w 比之前得到的最好的wg 还要好时,才更新wg(这里的好指的是分出来的错误更少)。由于计算w 后要和之前的wg 比较错误率来决定是否更新wg, 所以pocket algorithm 比简单的PLA 方法要低效。

Reference:

《统计学习方法》第二章 《机器学习基石》台湾国立大学第8,9

原文发布于微信公众号 - AI研习社(okweiwu)

原文发表时间:2017-05-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【机器学习笔记之三】CART 分类与回归树

本文结构: CART算法有两步 回归树的生成 分类树的生成 剪枝 ---- CART - Classification and Regression Trees...

4386
来自专栏Brian

深度学习笔记-浅层神经网络

---- 浅层神经网络 什么是浅层神经网络,我们看一下下面这个图: ? 分为如下: 1.Input Layer 2.Hidden Layer 3.Outpu...

4185
来自专栏用户2442861的专栏

聚类算法原理及python实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

2134
来自专栏宏伦工作室

用自编码器进行图像去噪

2654
来自专栏智能算法

KNN最近邻算法及其Python实现

k-NN是一种基本的分类和回归方法,用于分类时,算法思路较简单:通过计算不同特征之间的距离方法来得到最近的k个训练实例,根据k个实例的类别采用多数表决等方式进...

8697
来自专栏杨熹的专栏

用 Doc2Vec 得到文档/段落/句子的向量表达

本文结构: Doc2Vec 有什么用 两种实现方法 用 Gensim 训练 Doc2Vec ---- Doc2Vec 或者叫做 paragraph2vec, s...

1.9K10
来自专栏机器学习算法工程师

RNN入门与实践

作者:叶虎 编辑:黄俊嘉 引言 递归神经网络(Recurrent Neural Network, RNN)是神经网络家族的重要成员,而且也是深度学习领域中的得...

3677
来自专栏LhWorld哥陪你聊算法

【机器学习】--层次聚类从初识到应用

聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小. 数据聚类算法可以分为结构性或者分...

2403
来自专栏AI研习社

一文详解 Word2vec 之 Skip-Gram 模型(结构篇)

这次的分享主要是对Word2Vec模型的两篇英文文档的翻译、理解和整合,这两篇英文文档都是介绍Word2Vec中的Skip-Gram模型。下一篇专栏文章将会用T...

6154
来自专栏杨熹的专栏

CART 分类与回归树

本文结构: CART算法有两步 回归树的生成 分类树的生成 剪枝 ---- CART - Classification and Regression Trees...

3483

扫码关注云+社区

领取腾讯云代金券