感知机（Perceptron）

作者: 蛋仔鱼丸 | 来源:发表于2020-06-10 11:33 被阅读0次

【机器学习基础】从感知机模型说起
感知机（Perceptron）
感知机（Perceptron）
感知机 perceptron
感知机与神经网络
1、深度学习入门-感知机
动手学深度学习笔记（二）
机器学习算法—感知机
2018-11-06 深度学习 deep learning 简介
深度学习入门---多层感知机，过拟合和欠拟合，梯度消失和梯度爆炸

在之前的文章中我们已经讲过了逻辑回归分类器，现在趁热打铁总结一下与逻辑回归非常相似的感知机模型。感知机模型是一个非常古老的分类算法，现在很少会单独使用它，但是它的原理简单有效，很值得学习和理解，从原理上来说，感知机模型是神经网络和支持向量机的基础，理解了感知机有利于理解支持向量机和神经网络的原理。

1 感知机的原理

在广义线性模型（4）逻辑回归中我们说逻辑回归可以视为包含一个线性回归和一个值域映射两个过程，如果拿逻辑回归与感知机作比较的话，可以说感知机也同样包括这两个过程，只不过它的值域映射比逻辑回归简单很多，感知机直接将线性模型的输出映射为+1和-1，即需要预测的两个类别上，正可谓简单粗暴。所以说，感知机也是线性模型，用来处理线性可分的二分类问题，同样属于判别模型。

感知机假设数据线性可分的，希望通过学习得到一个线性的决策边界，将训练数据集正样本点和负样本点完全正确分开的分离，在决策边界一侧为正样本，另一侧为负样本，这个思路跟逻辑回归是一样的。

感知机模型可以表示为下式，其中 $sign$ 函数将线性模型的输出映射为预测类别：

$f(x)=sign(θ \cdot {x})$

$sign(x)= \begin{cases} -1& {x<0}\\ 1& {x\geq 0} \end{cases}$

2 感知机的损失函数

由点到超平面的距离计算方法可知： $|θ\cdot x|/||θ||$ 代表了样本点到决策边界的距离（文章没有用 $wx+b$ 的形式，抛弃了常数项的问题，其实是不准确的，若有看官，还请不要介意）；

同时我们可知， $θ\cdot x>0$ 的样本类别输出值取为1，满足 $θ\cdot x<0$ 的样本类别输出值取为-1，因此正确分类的样本满足 $yθ\cdot x>0$ ，而错误分类的样本满足 $-yθ\cdot x>0$ ， $- y\theta x\big / ||\theta||$ 表示了错误分类的样本到决策超平面的距离，感知机损失函数的优化目标，就是期望使错误分类的所有样本到超平面的距离之和最小（正样本+1，负样本-1这样的定义方式使得定义损失函数变得很方便），损失函数为：

$L(θ)=-\frac{1}{||θ||}\sum_{x_i\in{M}}y_iθ\cdot {x_i}$

式中，M为样本中所有错误分类样本点的集合。实际上，我们会把损失函数中参数的L2正则项 $\frac{1}{||θ||}$ 扔掉，认为它不会影响优化结果，即得到损失函数：

$L(θ)=-\sum_{x_i\in{M}}y_iθ\cdot {x_i}$

为什么可以不考虑 $1/||w||$ 呢？搜索解空间的时候， $||w||$ 会一直在变化啊？我觉得这个挺难理解的，根据资料及猜测，我觉得勉强能接受的原因为：

$1/||w||$ 不影响感知机学习算法的最终结果。因为数据集线性可分，则最终一定会找到超平面，感知机学习算法最终的终止条件是所有的输入都被正确分类，即不存在误分类的点，则此时损失函数为0，所以 $1/||w||$ 对最终结果也无影响；
忽略 $1/||w||$ ，即是没有真的达到损失函数为0，可能产生了一点误差，但大大的减小了加上 $1/||w||$ 的计算复杂度，还是划算的，提高了算法效率。

3 感知机的学习算法

确定了损失函数的形式，接下来就要进行损失函数的优化，还是使用梯度下降，由于损失函数中只有错误分类的样本点才参与计算，所以不需要使用普通的批量梯度下降了，我们选择使用随机梯度下降，每次迭代只使用一个错误分类的样本来对参数进行更新。

3.1 原始形式

感知机的学习算法的原始形式即直接使用梯度下降，其学习过程为：

输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}，y_i∈\left\{ −1,+1 \right\}$ ，学习率 $η(0<η<1)$ ；

输出： $θ$ ，其中 $θ_0$ 对应的 $x_0=1$ ，感知机模型 $f(x)=sign(θ\cdot x)$ ；

赋初值 $θ$ ；

选取数据点 $(x_i,y_i)$ ；

如果 $y_i(θ\cdot x)\leq 0$ ，即点 $(x_i,y_i)$ 为错误分类点，则：
$w \leftarrow w+ηy_ix_i$

转到2，直到训练集中没有错误分类点。

可以发现，在原始形式中，每一轮迭代都需要判断各个样本点是不是错误分类点，既对于每个样本点 $(x_i,y_i)$ 都需要计算 $y_i(θ\cdot x_i)$ ，向量内积 $θ\cdot x_i$ 的时间复杂度为 $O(n)$ ，因此总的时间复杂度为 $O(n*N*k)$ ，其中N为样本点数量，k为迭代次数（虽然每次迭代不需要全部遍历N个样本，不过表达时间复杂度时可以去掉因子保留变量，表示成 $O(n*N*k)$ ），这个时间复杂度还是比较高的，有没有更快捷的计算方法呢？我们来看看感知机的学习算法的对偶形式。

3.2 对偶形式

什么叫对偶形式？这里的对偶可不是“三尺剑，六钧弓”的意思，优化理论中的对偶问题是指每一个线性规划问题（称为原始问题）有一个与它对应的对偶线性规划问题（称为对偶问题），原始问题与对偶问题的解是对应的，得出一个问题的解，另一个问题的解也就得到了，可以简单的理解为从不同角度看待同一个问题，通过改变这个问题的形式使得我们更好求解。

根据感知机学习算法的原始形式可知，只有错误分类的样本点才会用于梯度下降计算，对于被 $n_i$ 次误分类而更新的样本 $i$ ，它参与 $θ$ 迭代的次数同样为 $n_i$ 。如果令参数 $θ$ 初始值为 $0$ ，这样我们的 $θ$ 的表达式可以写为：

$θ=\sum_{i=1}^N n_iηy_ix_i$

$\sum_{i=1}^N n_i$ 表示对全部样本 $N$ 中的每个个样本点进行 $n_i$ 次梯度下降，其中没被错误分类过的样本点 $n_i=0$ 。引用知乎上一个答案对 $n_i$ 的理解：

这样参数 $θ$ 的学习问题就转变成了样本错误分类次数 $n_i$ 的学习问题，此之谓“对偶”也。这样做的好处是什么呢？原始形式的痛点在于 $y_i(θ\cdot x_i)$ 中的内积运算，在对偶问题中转变为：

$y_i(θ\cdot x_i)=y_i(\sum_{j=1}^N n_jηy_jx_j\cdot x_i)$

由内积 $θ\cdot x_i$ 转变为内积 $x_j\cdot x_i$ ，区别是 $x$ 是已知的，可以提前通过矩阵运算得到Gram矩阵保存下来重用，样本循环和迭代的时间复杂度不变， $N$ 个 $n$ 维向量的内积计算提前，所以时间复杂度大概可以表示为 $O(n*N^2+N*k)$ ，与 $O(n*N*k)$ 倒不太好比较，不过这里按矩阵运算的时间复杂度完全没有优化来计算的，实际肯定比这小得多，并且工程上矩阵运算都是高度优化过的，非常快，所以对偶形式在使用效率上是很有优势的。

Gram矩阵

对偶形式的学习过程为：

输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}，y_i∈\left\{ −1,+1 \right\}$ ，学习率 $η(0<η<1)$ ；

输出： $n_i,i=1,2,...,N$ ，感知机模型 $f(x)=sign(\sum_{i=1}^N n_iηy_ix_i\cdot x)$

赋初值 $n_i=0$ ；

计算所有样本内积形成的Gram矩阵G。

选取数据点 $(x_i,y_i)$ ；

判断该数据点是否为当前模型的误分类点，即判断若 $y_i(\sum_{j=1}^N n_jηy_jx_j\cdot x_i)\leq 0$ 则:
$n_i \leftarrow n_i+1$

转到3，直到训练集中没有误分类点

4 总结

感知机算法原理很简单，但其中很多思路很棒，所以由它发展出了神经网络、支持向量机这样的更复杂、更准确的算法，搞懂了感知机模型的基本原理，接下来我们就来写一写跟它很相似的支持向量机~

主要参考

《统计学习方法》李航
感知机的损失函数为什么可以采用函数间隔(忽略1/||w||)?
如何理解感知机学习算法的对偶形式？

【机器学习基础】从感知机模型说起
感知机（perceptron）感知器（perceptron）1957年由Rosenblatt提出，是神经网络与支...
感知机（Perceptron）
在之前的文章中我们已经讲过了逻辑回归分类器，现在趁热打铁总结一下与逻辑回归非常相似的感知机模型。感知机模型是一个非...
感知机（Perceptron）
一. 概念 1. 模型感知机是二分类的线性分类模型，旨在求出将输入实例划分为两类的分离超平面，是神经网络与支持向...
感知机 perceptron
参考书：《统计学习方法》李航简介：感知机是二类分类的线性分类模型，输入为实例的特征向量，输出为实例的类别，取 ...
感知机与神经网络
一、感知机感知机（perceptron）由美国学者Frank Rosenblatt在1957年提出的。 1、感知...
1、深度学习入门-感知机
感知机是什么？感知机（perceptron）：感知机是神经网络（深度学习）的起源算法，学习感知机的构造是通向神...
动手学深度学习笔记（二）
从零开始写多层感知机多层感知机本节中，我们将以多层感知机（multilayer perceptron，简称 M...
机器学习算法—感知机
author : Peterdate: 2019-08-18 感知机Perceptron 导读感知机是二分类的...
2018-11-06 深度学习 deep learning 简介
一.deep learning的发展史 1.perceptron感知机假设数据集线性可分，perceptron的...
深度学习入门---多层感知机，过拟合和欠拟合，梯度消失和梯度爆炸
1.多层感知机多层感知机（MLP，Multilayer Perceptron）也叫人工神经网络（ANN，Arti...