感知机

约 1446 个字 预计阅读时间 10 分钟

感知机 是 F.Rosenblatt 提出的一个人工神经网络，可被视为是一种最简单形式的前馈神经网络，是一种二元线性分类器。

感知机

假设输入空间 \(\mathcal{X} \subseteq \mathbb{R}^{n}\) ，输出空间 \(\mathcal{Y}=\left\{ +1,-1 \right\}\)，输入 \(x\in \mathcal{X}\) 表示实例的特征向量，对应于输入空间的点，输出 \(y\in \mathcal{Y}\) 表示实例的类别，由输入空间到输出空间的如下函数：

\[ f(x) = \text{sign}(\vec{w}\cdot \vec{x}+b) \]

称为感知机，其中 \(\vec{w}\in \mathbb{R}^{n}\) 称为权值向量（weight vector），\(b\in \mathbb{R}\) 叫做偏置（bias），\(w\cdot x\) 表示内积， \(\text{sign}\) 表示符号函数，即

\[ \text{sign}(x) = \begin{cases} +1 ,\quad x\geq 0 \\ -1,\quad x< 0 \end{cases} \]

感知机处理的是线性可分数据集

数据集的线性可分性

给定一个数据集 \(T =\left\{ (x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{N},y_{N}) \right\}\) 其中 \(x_{i}\in \mathcal{X} = \mathbb{R}^{N},y_{i} \in \mathcal{Y} = \left\{ +1,-1 \right\}i=1,2,\dots,N\) ，如果存在超平面 \(\mathcal{S}\)

\[ w\cdot x + b= 0 \]

能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 \(y_{i}=+1\) 的实例 \(i\) ，有 \(w\cdot x_{i}+b> 0\)，对所有 \(y= -1\) 的实例，有 \(w\cdot x_{i} +b <0\) ，则称数据集 \(T\) 为线性可分数据集（linearly separable data set），否则，称数据集 \(T\) 线性不可分

对于一个数据 \((x_{0},y_{0})\) 其到超平面 \(w\cdot x+ b= 0\) 的距离为

\[ \frac{\lvert w\cdot x_{0} +b\rvert }{\lVert w \rVert } \]

这是一个绝对值函数，不易优化，对于误分类点，定义给出他们应满足 \(-y_{i}(w\cdot x_{i} +b)> 0\) ，因此上式也可以写作

\[ -\frac{1}{\lVert w \rVert } y_{i}(w\cdot x_{i}+b) \]

感知机的损失函数定义为

\[ - \frac{1}{\lVert w \rVert } \sum_{x_{i}\in M}^{} y_{i}(w\cdot x_{i}+b) \]

其中 \(M\) 为误分类点的集合，为了使计算方便，取 \(\lVert w \rVert=1\) 即做归一化处理。

显然，损失函数使非负的，如果没有无分类点，损失函数值为 0。而且，误分类点越少，误分类点离超平面越近，损失函数值越小。一个特定的样本点的损失函数：在误分类时是参数 \(w,b\) 的线性函数，在正确分类时是 0。因此，给定训练数据集 \(T\) ，损失函数 \(L(w,b)\) 是 \(w,b\) 的连续可导函数。

因此求解如下最优化问题：

\[ \underset{ w,b }{ \min } L(w,b) = - \sum_{x\in M}^{} y_{i}(w\cdot x_{i}+b) \]

采取随机梯度下降法（Stochastic gradient descent） 来求解这个问题。在每次迭代中，我们随机均匀采样的一个样本索引 \(i\in \left\{ 1,\dots,n \right\}\) ，并计算梯度 \(\nabla f_{i}(x)\) 来更新权重，在本问题中，对应如下迭代公式：

\[ w \leftarrow w + \eta y_{i}x_{i} \]

\[ b \leftarrow b+ \eta y_{i} \]

其中 \(\eta\) 为学习率，每次迭代的计算开销为 \(\mathcal{O}(1)\) 。随机梯度 \(\nabla f_{i}(x)\) 是对梯度 \(\nabla f(x)\) 的无偏估计：

\[ \mathbb{E}[\nabla f_{i}(x)] = \frac{1}{n} \sum_{i=1}^{n} \nabla f_{i}(x) = \nabla f(x) \]

方便起见，将 \(b\) 合并入权重向量 \(\vec{w}\)，记为 \(\hat{w} =(\vec{w}^{T},b)^{T}\) ，同时，数据可记为 \(\hat{x} = (x^{T},1)^{T}\)，超平面则可改写成 \(\hat{w}\cdot \hat{x} = 0\)，对应的迭代公式则为

\[ \hat{w}_{k}= \hat{w}_{k-1}+\eta y_{i}\hat{x}_{i} \]

Warning

注意感知机只找出能将线性可分数据集划分成两个数据集的超平面，并没有限定找到的超平面，对于同一份线性可分数据集，算法给出的解并不唯一，不同的初值可能会给处不同的超平面

下面定理给出了感知机的收敛性

Novikoff Theorem

设训练数据集 \(T =\left\{ (x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{N},y_{N}) \right\}\) 其中 \(x_{i}\in \mathcal{X} = \mathbb{R}^{N},y_{i} \in \mathcal{Y} = \left\{ +1,-1 \right\}i=1,2,\dots,N\) ，则

• 存在满足条件 \(\lVert \hat{w}_{opt} \rVert = 1\) 的超平面 \(\hat{w}_{opt}\cdot \hat{x} =0\) 将训练数据集完全正确分开，且存在 \(\gamma > 0\) 对所有的 \(i=1,2,\dots,N\)

\[ y_{i}(\hat{w}_{opt}\cdot \hat{x}_{i}) = y_{i}(w_{opt}\cdot x_{i}+b_{opt})\geq \gamma \]

• 令 \(R = \underset{ 1\leq i \leq N }{ \max }\lVert x_{i} \rVert\) ，则算法在训练数据集上的误分类次数 \(k\) 满足不等式

\[ k \leq \left( \frac{R}{\gamma} \right) ^{2} \]

先证明第一个不等式，由于训练数据集是线性可分的，故存在超平面可将数据集完全正确分开，取超平面 \(\hat{w}_{opt}\cdot x =0\) ，使 \(\lVert \hat{w}_{opt} \rVert=1\)，对于有限的 \(i=1,2,\dots,N\)，有：

\[ y_{i}(\hat{w}_{opt}\cdot \hat{x}_{i}) = y_{i}(w_{opt}\cdot x_{i}+b_{opt})>0 \]

所以存在 \(\gamma = \underset{ i }{ \min } \left\{ y_{i}(\omega_{opt}\cdot x_{i}+b_{opt}) \right\}\) 使得

\[ y_{i}(\hat{w}_{opt} \cdot \hat{x}_{i}) = y_{i}(w_{opt}\cdot x_{i}+b_{opt})\geq \gamma \]

在这证明第二个定理前，先推导两个不等式

\[ \begin{align} & \hat{w}_{k}\cdot \hat{w}_{opt}\geq k \eta \gamma \\ & \lVert \hat{w}_{k} \rVert^{2}\leq k \eta^{2} R^{2} \end{align} \]

利用迭代公式和第一个定理，给出

\[ \hat{w}_{k}\cdot \hat{w}_{opt} = \hat{w}_{k-1}\cdot \hat{w}_{opt}+\eta y_{i}\hat{w}_{opt} \cdot \hat{x}_{i}\geq \hat{w}_{k-1}\cdot \hat{w}_{opt+}\eta \gamma \]

递推可得

\[ \hat{w}_{k}\cdot \hat{w}_{opt} \geq \hat{w}_{k-1}\cdot \hat{w}_{opt+}\eta \gamma \geq\hat{w}_{k-2}\cdot \hat{w}_{opt+}2\eta \gamma\geq\dots\geq k \eta \gamma \]

由于

\[ \begin{align} \lVert \hat{w}_{k} \rVert &= \lVert \hat{w}_{k-1} \rVert ^{2}+2\eta y_{i}\hat{w}_{k-1}\cdot \hat{x}_{i}+\eta^{2} \lVert \hat{x}_{i} \rVert ^{2} \\ &\leq \lVert \hat{w}_{k-1} \rVert^{2} +\eta^{2}\lVert \hat{x}_{i} \rVert^{2} \\ &\leq \lVert \hat{w}_{k-1} \rVert ^{2}+\eta^{2} R^{2} \\ &\leq \lVert \hat{w}_{k-2} \rVert ^{2}+2\eta^{2}R^{2}\leq\dots \\ &\leq k \eta^{2} R^{2} \end{align} \]

有柯西施瓦兹不等式可得

\[ \begin{align} k \eta \gamma \leq \hat{w}_{k}\cdot \hat{w}_{opt}&\leq \lVert \hat{w}_{k} \rVert\lVert \hat{w}_{opt} \rVert \leq \sqrt{ k }\eta R \\ k^{2}\gamma^{2}&\leq k R^{2} \end{align} \]

即

\[ k\leq \left( \frac{R}{\gamma} \right) ^{2} \]

Summary

上述收敛性性定理表明：

• 误分类的次数k是有上界的，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的；
• 感知机算法存在许多解，既依赖于初值，也依赖迭代过程中误分类点的选择顺序；
• 若需要到唯一分离超平面，需增加约束，如SVM(support vector machine,支持向量机)；

感知机的对偶形式

\[ \begin{aligned} &w= \sum_{i=1}^{N} \alpha_{i}y_{i}x_{i}\\ &b = \sum_{i=1}^{N}\alpha_{i}y_{i} \end{aligned} \]

可见 SVM 的证明