感知机学习小结

作者: efan | 来源:发表于2019-03-18 19:30 被阅读10次

感知机学习小结
感知机
1、深度学习入门-感知机
感知机
深度学习入门(1)感知机
统计学--感知机
反馈神经网络
深度学习理论笔记（感知机）
统计学习方法笔记(第二章个人笔记)
深度学习瞎学之路--感知器

什么是感知机

是一种人工神经网络

感知机可以通过数学统计学方法完成对函数的估计或近似，能在外界信息的基础上改变内部结构，是一种自适应系统，通俗的讲就是具备学习功能。
是一种最简单形式的前馈神经网络

感知机模型的参数从输入层向输出层单向传播，整个网络中无反馈。感知机是最简单形式是因为只包含一层传播。
是一种二元线性分类器

感知机的输出结果只有+1 和–1二值，所以说感知机是一个二元分类器；

在二维空间中，感知机的模型就是一条直线，将平面中的正负样本点分离成两份，在三维中，感知机的模型就是一个平面，将空间中的正负样本点分离成两份，放到更高维的空间中，感知机的模型就是一个超平面；

这也就是说，如果在二维空间中，不存在直线刚好将正负样本点分离成两份，在三维空间中，不存在平面将空间中的正负样本点分离成两份，那么你的数据就无法使用感知机模型；

感知机的使用前提是数据本身线性可分。

感知机模型

假设我们有n个样本，每个样本包含m维输入特征和一个二元类别输出,如下所示：

$(x^{(1)}_{1}, x^{(2)}_{1}, x^{(3)}_{1}, …, x^{(m)}_{1}, y_{1}), (x^{(1)}_{2}, x^{(2)}_{2}, x^{(3)}_{2}, …, x^{(m)}_{2}, y_{2}),….(x^{(1)}_{n}, x^{(2)}_{n}, x^{(3)}_{n}, …, x^{(m)}_{n}, y_{n})$

其中， $(x^{(1)}_{1}, x^{(2)}_{1}, x^{(3)}_{1}, …, x^{(m)}_{1}, y_{1})$ 代表一个样本， $x^{(1)}_{1}$ 表示样本的一个输入特征，其下标表示这是第几个样本，上标表示这是这个样本的第几个输入特征； $y_1$ 表示样本的输出，其下标表示这是第几个样本；

我们的目的是找到这样一个超平面，即：

$\theta_{0}+\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}=0$

其满足对于所以有的正样本： $\theta_{0}+\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}>0$ ，对于所有的负样本： $\theta_{0}+\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}<0$ ；从而得到线性可分。如果数据线性可分，这样的超平面一般都不是唯一的，也就是说感知机模型可以有多个解。

简化超平面：将 $\theta_{1}x^{(1)}+\theta_{2}x^{(2)}+…+\theta_{m}x^{(m)}$ 记为向量 $(\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m})$ 与输入特征向量 $(x^{(1)}, x^{(2)}, x^{(3)}, …, x^{(m)})$ 的内积，可得超平面为：

$\theta_{0}+(\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m}) \cdot (x^{(1)}, x^{(2)}, x^{(3)}, …, x^{(m)})=0$

将 $\theta_{0}$ 记为 b （偏置 bias），将 $(\theta_{1}, \theta_{2}, \theta_{3}, …, \theta_{m})$ 记做 w （权值 weight），可得超平面为：

$w \cdot x + b = 0$

所以，我们将感知机模型定义为：

$f(x) = sign(w \cdot x+b)$

其中：

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

感知机损失函数

我们知道了感知机模型，我们还需要评价感知机模型的方法，也就是损失函数。我们将所有误分类点到超平面的总距离作为感知机模型的损失函数。

首先我们知道空间 $R$ 中任一点 $x$ 到平面 $S$ 的距离是：

$\frac{1}{||w||} |w \cdot x + b|$

其中： $||w||$ 是 $w$ 的 $L_2$ 范数 ( $L_2$ 范数是指向量各元素的平方和然后求平方根)。

接下来，我们假设所有误分类点的集合为 $M$ ，因为当 $w\cdot x+b>0$ 时， $＝y＝-1$ ，而当 $w \cdot x+b<0$ 时， $＝y＝+1$ 。所以对于误分类点来说其到平面 $S$ 的距离可写作：

$-\frac{1}{||w||} y(w \cdot x + b)$

那么所有误分类点 $M$ 到超平面 $S$ 的总距离为:

$-\frac{1}{||w||} \sum_{x \in M}{y(w \cdot x + b)}$

不考虑 $-\frac{1}{||w||}$ ，我们就得到了感知机学习的损失函数。

$L(w,b)=-\sum_{x \in M}{y(w \cdot x + b)}$

感知机学习算法

我们知道了评价感知机模型的方法，也就是损失函数。那么我们对于模型的优化也就是求解损失函数的极小化。

求解 $w, b$ ，使其为以下损失函数极小化问题的解：

$min_{w,b}L(w,b)=-\sum_{x \in M}{y(w \cdot x + b)}$

我们采用随机梯度下降法求解损失函数极小化问题。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

我们知道对于误分类集合M固定时，那么损失函数L(w,b)的梯度为：

$\nabla_{w}L(w,b)=-\sum_{x\in M}yx$

$\nabla_{b}L(w,b)=-\sum_{x\in M}y$

我们每次随机选取一个误分类点 $(x_{i}, y_{i})$ 对 $w, b$ 进行更新，那么对 $w, b$ 的更新为：

$w\leftarrow w+\eta y_{i}x_{i}$

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

其中 $\eta (0 < \eta \leq 1)$ 是步长，在机器学习中又称为学习率(learning rate)。

具体的训练步骤如下：

(1) 任意选取平面 $S_{0}$ ,使用 $(w_{0}, b_{0})$ 表示平面 $S_{0}$ ;

(2) 在误分类点集 $M$ 中选取一个误分类点 $(x_{i}, y_{i})$ ；

(3) 对 $(w, b )$ 进行一次梯度下降，即：

$w\leftarrow w +\eta y_{i}x_{i}$

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

(4) 使用新平面 $S$ 判断是否任有误分类点，如有跳转至第二步，如无即完成模型训练；

这种学习算法易于理解，可直观解释为：当存在样本点被误分类时，就调整分离超平面的位置也就是 $(w,b)$ ，使分离超平面超误分类点的一侧移动，以减少该误分类点与分离超平面间的距离，直至分离超平面越过该误分类点使其被正确分类。

此学习算法为感知机学习的基本算法，对应于后面将提到的对偶形式，称为感知机学习算法的原始形式。

感知机学习算法的对偶形式

感知机学习算法的对偶形式相较与原始形式来说，要难理解一些。但是如果你已经完全理解原始形式，那么对偶形式也很好理解；如果你对于原始形式还不是很理解，我建议完全消化了原始形式再来看对偶形式。

从某种角度来说，可以认为对偶形式是原始形式数学层面的优化，其存在的意义在于优化感知机学习算法的学习效率。

其实也不尽然，对偶形式不仅仅是数学层面的优化，其基本思路是能够解释得通的，而且这个思路在其它机器学习算法中是可以沿用的。本节将尽可能解释其基本思路。

首先，在原始算法中我们使用 $(w, b)$ 来表示最终的分离超平面 $S$ ，通过分析原始形式的迭代过程，也就是：

$w\leftarrow w+\eta y_{i}x_{i}$

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

我们知道，每次对于 $w$ 的更新是在原 $w$ 的基础上加上了某一个误分类点的输入特征、输出特征与学习率 $\eta$ 的乘积，每次对于 $b$ 的更新是在原 $b$ 的基础上加上了某一个误分类点的输出特征与学习率 $\eta$ 的乘积， $(w, b)$ 每次迭代的增量分别是 $\eta y_{i}x_{i}$ 、 $\eta y_{i}$ 。

那么我们可以认为， $(w, b)$ 最终由初始 $(w_{0}, b_{0})$ 加上增量总和组成， $(w, b)$ 的增量总和可以使用 $\sum_{i=1}^{N}a_{i}y_{i}x_{i}$ 、 $\sum_{i=1}^{N}a_{i}y_{i}$ 来分别表示，这里的 $a = {(a_{1}, a_{2}, a_{3},… ,a_{n})}^T = {(n_{1}\eta, n_{2}\eta, n_{3}\eta,… ,n_{n}\eta)}^T$ , $n_{i}$ 为迭代过程中样本集中第 $i$ 个样本共被选中几次进行梯度下降.

综上所诉，可以用以下公式来表示 $(w, b)$ :

$w = w_{0} + \sum_{i=1}^{N}a_{i}y_{i}x_{i}$

$b = b_{0} + \sum_{i=1}^{N}a_{i}y_{i}$

因为， $(w_{0}, b_{0})$ 为随机选定的初始分离超平面，可令初始值 $w_{0},b_{0}$ 均为0，那么 $(w, b)$ 为：

$w = \sum_{i=1}^{N}a_{i}y_{i}x_{i}$

$b = \sum_{i=1}^{N}a_{i}y_{i}$

那么，感知机模型 $f(x) = sign(w \cdot x+b)$ 被重新定义为：

$f(x) = sign( \sum_{i=1}^{N}a_{i}y_{i}x_{i} \cdot x+b)$

我们求解的值由 $(w, b)$ 变更为 $(a, b)$ 。

具体的训练步骤如下：

(1) 令 $(a, b)$ 均为0；

(2) 在误分类点集 $M$ 中选取一个误分类点 $(x_{i}, y_{i})$ ；

(3) 对 $(a, b )$ 进行一次更新，即：

$a_{i}\leftarrow a_{i}+\eta$
$b \leftarrow b+\eta y_{i}$

(4) 使用新平面 $S_{1}$ 判断是否任有误分类点，如有跳转至第二步，如无即完成模型训练；

那么，为什么说对偶形式相对于原始形式计算速度更快呢？？

这是因为，在原始形式中，每次迭代 $(w, b)$ ，我们要计算 $n$ (样本数量)次 $w \cdot x$ ，这里的计算量非常大；而在对偶形式中，观察模型函数可以看到，我们涉及到的内积计算是 $x_{i} \cdot x$ ，我们可以事先计算出训练集中样本之间的内积并以矩阵的形式存储，这个矩阵就是所谓的 Gram 矩阵：