感知机算法（Perceptron Learning Algorithm）

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

图1：二维空间

图2：三维空间

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

图3：不可分数据

1.感知机模型

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

$((x_{1}^0，x_{2}^0...x_{m-1}^0,x_{m}^0,y_{0} ),(x_{1}^1，x_{2}^1...x_{m-1}^1,x_{m}^1,y_{1} ),....(x_{1}^n，x_{2}^n...x_{m-1}^n,x_{m}^n,y_{n} ))$

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

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b = 0$

让其中一个类别的样本满足 $\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b > 0$ ,而另一类样本满足

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b < 0$ ，从而样本线性可分。但这样的超平面并不是唯一的，感知机模型采取不同的初始值（ $\vec{\omega }_{0} ，b_{0}$ ）解可能会不同。

我们用相量方式对上式进行表达： $\vec{\omega} \bullet \vec{x} + b = 0$ ，由此感知机的模型可以定义为：

$y = sign( \vec{\omega} \bullet \vec{x} +b)$ ,其中：

例如：将一个新的样本 $\vec{x1}$ 带入训练好的模型 $\vec{\omega} \bullet \vec{x} + b$ ，当 $\vec{\omega} \bullet \vec{x1} + b \geq 0$ ， $\vec{x1}$ 被分为 $+1$ 类。当 $\vec{\omega} \bullet \vec{x1} + b < 0$ ， $\vec{x1}$ 被分为 $-1$ 类。

2.感知机模型的损失函数（Loss Function）

我们将满足 $\vec{\omega} \bullet \vec{x} + b \geq 0$ 的样本类别输出值取 $+1$ ，满足 $\vec{\omega} \bullet \vec{x} + b < 0$ 的样本类别输出值取 $-1$ 。从而正确分类的样本满足 $y（ \vec{\omega} \bullet \vec{x} + b）> 0$ ，而错误分类的样本满足 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 。损失函数的优化目标是使所有被错误分类的样本到超平面的距离之和最小。

一个被错误分类的样本 $i$ ， $y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）< 0$ ，到超平面的距离是 $-y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）/\vert \vert \vec{\omega } \vert \vert _{2}$ ，

其中 $\vert \vert \vec{\omega } \vert \vert _{2} = \sqrt{\sum_{i=1}^m\omega _{i}^2 }$ 。 $\vec{\omega }$ 为超平面的法向量， $\vec{\omega }$ 的大小变化并不会影响样本点到超平面的距离。我们令 $\vert \vert \vec{\omega } \vert \vert _{2} = 1$ ，并且假设所有错误分类的点的集合为M，则所有错误分类的样本到超平面的距离之和为：

$- \sum_{\vec{x_{i} } \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

最终构建的损失函数为：

$L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

3.感知机模型的优化方法

感知机模型选择的是采用随机梯度下降，这意味着我们每次仅仅需要使用一个误分类的点来更新梯度。损失函数 $L(\vec{\omega } ，b)$ 的梯度如下：

$∇_{\omega } L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} \vec{x_{i}}$

$∇_{b} L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i}$

随机选取一个错误分类点 $(\vec{x_{i}} ,y_{i} )$ ，对 $\vec{\omega } ，b$ 进行更新：

$\vec{\omega } \leftarrow \vec{\omega _{0} } +\eta y_{i}\vec{x_{i}}$

$b \leftarrow b_{0} +\eta y_{i}$

式中 $\vec{\omega }_{0} ，b_{0}$ 为初始值， $\eta (0<\eta \leq 1)$ 是步长（learning rate）。通过这样迭代可以使损失函数 $L(\vec{\omega } ，b)$ 不断减小，直到为0。

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

4.感知机模型的优化方法的对偶形式

上一节的感知机模型的算法形式我们一般称为感知机模型的算法原始形式。对偶形式是对算法执行速度的优化。对偶形式的基本想法是将 $\vec{\omega } ，b$ 表示为样本 $\vec{x_{i} }$ 和标签 $y_{i}$ 的线性组合，通过求解其系数而求得 $\vec{\omega } ，b$ 。我们取初始值 $\vec{\omega }_{0} ，b_{0}$ 为 $0$ ，选取错误分类样本 $(\vec{x_{i}} ,y_{i} )$ 对 $\vec{\omega } ，b$ 进行更新有：

$\vec{\omega } \leftarrow\eta y_{i}\vec{x_{i}}$

$b \leftarrow \eta y_{i}$

假设为了将样本 $\vec{x_{i} }$ 正确分类而更新 $\vec{\omega } ，b$ 的次数为 $m_{i}$ ，每一个样本 $(\vec{x_{i}} ,y_{i} )$ 的 $m_{i}$ 的初始值为 $0$ ，每当次样本在某一次梯度下降迭代中因误分类而更新时， $m_{i}$ 的值 $+1$ ，则 $\vec{\omega } ，b$ 关于 $(\vec{x_{i}} ,y_{i} )$ 的增量分别为 $m_{i} \eta y_{i}\vec{x_{i}}$ 和 $m_{i} \eta y_{i}$ 。则用所有样本对 $\vec{\omega } ，b$ 进行更新，最后得到的 $\vec{\omega } ，b$ 可以表示为

$\vec{\omega } =\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}}$

$b =\sum_{i=1}^nm_{i} \eta y_{i}$

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

我们用 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 的等价形式 $y(\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}} \bullet \vec{x} + \sum_{i=1}^nm_{i} \eta y_{i})< 0$ 来判断错误分类。上式中 $\vec{x_{i}} \bullet \vec{x}$ 表示的是两个样本的内积，而且这个内积的结果在更新 $\vec{\omega }$ 的过程中会多次使用。如果我们事先用矩阵运算计算出所有的样本之间的内积，那么在算法运行时，仅仅一次的矩阵内积运算比多次的循环计算省时。计算量最大的判断误分类这儿就省下了很多的时间，这也是对偶形式的感知机模型比原始形式优的原因。

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

$G = [\vec{x_{i} } \bullet \vec{x_{j} } ]_{n\times n}$

例如： $x_{1} =(3,3)$ , $x_{2} =(4,3)$ , $x_{3} =(1,1)$ 则Gram矩阵为

$[\vec{x_{1} } \bullet \vec{x_{1} },\vec{x_{1} } \bullet \vec{x_{2} },\vec{x_{1} } \bullet \vec{x_{3} }]$ $[18,21,6]$

G= $[\vec{x_{2} } \bullet \vec{x_{1} },\vec{x_{2} } \bullet \vec{x_{2} },\vec{x_{2} } \bullet \vec{x_{3} }]$ = $[21,25,7]$

$[\vec{x_{3} } \bullet \vec{x_{1} },\vec{x_{3} } \bullet \vec{x_{2} },\vec{x_{3} } \bullet \vec{x_{3} }]$ $[6,7,2]$

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

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

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

最后编辑于：2019.03.17 11:38:35

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,539评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,911评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,337评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,723评论 1赞 290
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,795评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,762评论 1赞 294
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,742评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,508评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,954评论 1赞 308
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,247评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,404评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,104评论 5赞 340
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,736评论 3赞 324
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,352评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,557评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,371评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,292评论 2赞 352

感知机算法（Perceptron Learning Algorithm）

1.感知机模型

2.感知机模型的损失函数（Loss Function）

3.感知机模型的优化方法

4.感知机模型的优化方法的对偶形式

推荐阅读更多精彩内容