感知机

作者: shenghaishxt | 来源:发表于2019-03-26 11:26 被阅读0次

本文来自我的个人博客 https://www.zhangshenghai.com/posts/48428/

感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别。感知机是神经网络与支持向量机的基础。

感知机模型

假设输入空间 $\mathcal{X} \subseteq R^{n}$ ，输出空间 $\mathcal{Y} = \left\{+1, -1 \right\}$ 。输入 $x \in \mathcal{X}$ 表示实例的特征向量，对应于输入空间的点；输出 $y \in \mathcal{Y}$ 表示实例的类别。由输入空间到输出空间的函数：
$\begin{align*} \\& f \left( x \right) = sign \left( w \cdot x + b \right) \end{align*}$
称为感知机。其中， $w$ 和 $b$ 为感知机模型参数， $w \in R^{n}$ 叫做权值或权值向量， $b \in R$ 叫偏置， $w \cdot x$ 表示 $w$ 和 $x$ 的内积。 $sign$ 是符号函数，即
$\begin{align*} sign \left( x \right) = \left\{ \begin{aligned} \ & +1, x \geq 0 \\ & -1, x<0 \end{aligned} \right.\end{align*}$
感知机是一种线性分类模型，属于判别模型。感知机模型的假设空间是定义在特征空间中的所有线性分类模型或线性分类器，即函数集合 $\left\{ f | f \left( x \right) = w \cdot x + b \right\}$ 。

感知机有如下的几何解释：线性方程
$\begin{align*} \\& w \cdot x + b ＝ 0 \end{align*}$
对应于特征空间 $R^{n}$ 中的一个超平面 $S$ ，其中 $w$ 是超平面的法向量， $b$ 是超平面的截距。超平面 $S$ 将特征空间划分为两部分，位于其中的点被分为正、负两类，超平面 $S$ 称为分离超平面。

感知机的学习策略

输入空间 $R^{n}$ 中的任一点 $x_{0}$ 到超平面 $S$ 的距离：
$\begin{align*} \\& \dfrac{1}{\| w \|} \left| w \cdot x_{0} + b \right| \end{align*}$
对于误分类数据 $\left( x_{i}, y_{i} \right)$ ，当 $w \cdot x + b > 0$ 时， $y_{i}=-1$ ，当 $w \cdot x + b < 0$ 时， $y_{i}=+1$ ，即 $y_i$ 与 $w\cdot x_i +b$ 异号，有
$\begin{align} \\& -y_{i} \left( w \cdot x_{i} + b \right) > 0 \end{align}$
误分类点 $x_{i}$ 到分离超平面的距离为
$\begin{align*} \\& -\dfrac{1}{\| w \|} y_{i}\left( w \cdot x_{i} + b \right) \end{align*}$
假设超平面 $S$ 的误分类点集合为 $M$ ，则所有误分类点到超平面 $S$ 的总距离为
$\begin{align*} \\& -\dfrac{1}{\| w \|} \sum_{x_{i} \in M} y_{i} \left( w \cdot x_{i} + b \right) \end{align*}$
给定训练数据集
$\begin{align*} \\& T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\} \end{align*}$
其中， $x_{i} \in \mathcal{X} = R^{n}, y_{i} \in \mathcal{Y} = \left\{ +1, -1 \right\}, i = 1, 2, \cdots, N$ 。感知机 $sign \left( w \cdot x + b \right)$ 的损失函数定义为
$\begin{align*} \\& L \left( w, b \right) = -\sum_{x_{i} \in M} y_{i} \left( w \cdot x_{i} + b \right) \end{align*}$
其中， $M$ 为误分类点的集合。显然，损失函数 $L(w, b)$ 是非负的。如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。感知机学习的策略是在假设空间中选取使上述损失函数式最小的模型参数 $w, b$ ，即感知机模型。

感知机学习算法

感知机算法（原始形式）

输入：训练数据集 $T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\}$ ，其中 $x_{i} \in \mathcal{X} = R^{n}, y_{i} \in \mathcal{Y} = \left\{ +1, -1 \right\}, i = 1, 2, \cdots, N$ ；学习率 $\eta \left( 0 < \eta \leq 1 \right)$ 。

输出： $w,b$ ；感知机模型 $f \left( x \right) = sign \left( w \cdot x + b \right)$

选取初值 $w_{0},b_{0}$
在训练集中选取数据 $\left( x_{i}, y_{i} \right)$
如果 $y_{i} \left( w \cdot x_{i} + b \right) \leq 0$

$\begin{align*} \\& w \leftarrow w + \eta y_{i} x_{i} \\ & b \leftarrow b + \eta y_{i} \end{align*}$

转至2，直至训练集中没有误分类点

感知机算法（对偶形式）

设 $w,b$ 修改n次，则 $w,b$ 关于 $\left( x_{i}, y_{i} \right)$ 的增量分别是 $\alpha_{i} y_{i} x_{i}$ 和 $\alpha_{i} y_{i}$ ，其中 $\alpha_{i} = n_{i} \eta$ 。 $w,b$ 可表示为
$\begin{align*} \\& w = \sum_{i=1}^{N} \alpha_{i} y_{i} x_{i} \\ & b = \sum_{i=1}^{N} \alpha_{i} y_{i} \end{align*}$
其中， $\alpha_{i} \geq 0, i=1,2, \cdots, N$

输出： $\alpha,b$ ；感知机模型 $f \left( x \right) = sign \left( \sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x + b \right)$ ，其中 $\alpha = \left( \alpha_{1}, \alpha_{2}, \cdots, \alpha_{N} \right)^{T}$

$\alpha \leftarrow 0, b \leftarrow 0$
在训练集中选取数据 $\left( x_{i}, y_{i} \right)$
如果 $y_{i} \left( \sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i} + b \right) \leq 0$