感知机(perceptron)学习笔记
本文为感知机的学习笔记
感知机(perceptron)
有监督学习。误分类驱动。
一 数学概念介绍
\(n\)维欧式空间(\(R^n\))
现实空间的抽象与推广
设\(n\)是正整数，由\(n\)个实数构成的有序数组\(x=(x_1,x_2,\dots,x_n)\)的全体所组成的集合，称为\(n\)维欧几里得空间。
超平面
\(n\)维欧氏空间中，\(n-1\)维度的线性子空间。
是一个数学概率。
Gram矩阵
一组向量内积的矩阵，给定一组向量\(v_1,v_2,\dots,v_n\)，它们的Gram矩阵(\(n\) x \(n\)维度)如下：
\[ G = \begin{bmatrix} (\mathbf{v}_1 \cdot \mathbf{v}_1) & (\mathbf{v}_1 \cdot \mathbf{v}_2) & \cdots & (\mathbf{v}_1 \cdot \mathbf{v}_n) \\ (\mathbf{v}_2 \cdot \mathbf{v}_1) & (\mathbf{v}_2 \cdot \mathbf{v}_2) & \cdots & (\mathbf{v}_2 \cdot \mathbf{v}_n) \\ \vdots & \vdots & \ddots & \vdots \\ (\mathbf{v}_n \cdot \mathbf{v}_1) & (\mathbf{v}_n \cdot \mathbf{v}_2) & \cdots & (\mathbf{v}_n \cdot \mathbf{v}_n) \end{bmatrix} \]
二 感知机
使用一个超平面对数据集进行二分类。
类比神经元(两层神经元，输入层和输出层)，示意图如下：
定义说明
设训练数据集\(D=\{(x_1,y_1),\dots,(x_m,y_m)\}\)。\((x_i,y_i)\)表示第\(i\)对样本。\(x \in \Chi \subseteq R^n\)，代表实例的特征向量。\(Y=\{+1,-1\}\)，\(y \in Y\)，代表实例的类别。得到一个模型(\(f\)代表激活函数(activate function)）: \[ f(x)=f(w \cdot x+b) \] 其中，\(w\)代表权值向量，其维度和特征向量\(x\)相同；\(b\)代表偏置，为超平面参数，对应的超平面为: \[ w \cdot x+b=0 \]
较典型的激活函数
| 名称 | 公式 | |
|---|---|---|
| 符号函数\(sign(x)\) | \(sign(x)=\begin{cases}+1, & x \geq 0 \\-1, & x < 0\end{cases}\) | |
| 阶跃函数\(sgn(x)\) | \(sgn(x)=\begin{cases}1, & x \geq 0 \\0, & x < 0\end{cases}\) | |
| \(Sigmoid\)函数 | \(Sigmoid(x)=\frac{1}{1+e^{-x}}\) |
线性可分
输入神经元数为二，进行逻辑运算
与、或、非为线性可分的问题，异或是非线性可分问题。
(1)与运算
| \(x_1\) | \(x_2\) | \(y\) |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
(2)或运算
| \(x_1\) | \(x_2\) | \(y\) |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
(3)非运算
| \(x_1\) | \(x_2\) | \(y\) |
|---|---|---|
| 1 | 0 | |
| 0 | 1 |
(4)异或运算
| \(x_1\) | \(x_2\) | \(y\) |
|---|---|---|
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
无法找到一条直线去分开这两类点
损失函数(cost function)
以选用符号函数\(sign(x)\)作为激活函数来分析
数据点到超平面的距离
首先考虑三维空间中点\((x_0,y_0,z_0)\)到某平面\(c_1x+c_2y+c_3z+c_4=0\)的距离\(d\)公式： \[ d=\frac{\vert c_1x_0+c_2y_0+c_3z_0+c_4 \vert}{\sqrt{c_1^2+c_2^2+c_3^2}} \] 再考虑输入变量\(x_i\)到超平面\(w \cdot x+b=0\)的距离公式: \[ d=\frac{\vert w \cdot x_i + b \vert}{\Vert w \Vert} \] 由于选用了符号函数作为激活函数，可以得到误分类的数据\((x_i),y_i)\)满足下列关系: \[ -y_i(w \cdot x_i+b)>0\\ \]
\[ \begin{equation} \begin{split} -y_i(w \cdot x_i+b) &=\vert w \cdot x_i + b \vert \end{split} \end{equation} \]
其中\(y_i\)代表\(x_i\)的真实类别。
可以得到样本点\(x_i\)到超平面的距离: \[ d=\frac{-y_i(w \cdot x_i+b)}{\Vert w \Vert} \] 由不等式(5)判断出误分类点之后，可以得到一个由误分类点组成的集合\(M\)，所有误分类点到超平面的总距离: \[ d_{\sum}=-\frac{1}{\Vert w \Vert}\sum_{x_i \in M}y_i(w \cdot x_i+b) \]
优化目标
下列为感知机的损失函数: \[ L(w,b)=-\sum_{x_i \in M}y_i(w \cdot x_i+b) \] 去掉公式(8)的\(\frac{1}{\Vert w \Vert}\)的几种解释：
(1)希望使得误分类点到超平面的总距离合尽可能小，达到0最好，没有误分类点更好，所以在优化时，可以去掉公式(8)的\(\frac{1}{\Vert w \Vert}\)。
(2)\(\frac{1}{\Vert w \Vert}\)不影响对样本点是否被误分类的判断。
优化目标是使得损失函数尽可能小。找到参数\(w\)合\(b\)满足: \[ \begin{equation} \begin{split} \underset {w,b}{L(w,b)} \end{split} \end{equation} \]
学习算法
原始形式
因为感知机学习是误分类驱动，不能使用全体样本进行梯度下降，下面是使用随机梯度下降法(Stochastic Gradient Descent，SGD)的介绍。
损失函数\(L(w,b)\)对\(w\)求梯度: \[ \nabla_w L(w,b)=-\sum_{x_i \in M}y_i\cdot x_i \] 注意其中\(x_i\)代表的是特征向量，不是一个数值。
损失函数\(L(w,b)\)对\(b\)求梯度: \[ \nabla_b L(w,b)=-\sum_{x_i \in M}y_i \] 随 机选取一个误分类点\((x_i,y_i)\)，对\(w\)和\(b\)进行更新: \[ w \leftarrow w-\eta(-y_i\cdot x_i)=w+\eta(y_i\cdot x_i)\\ b \leftarrow b-\eta(-y_i)=b+\eta(y_i) \]
对偶形式
设误分类点\((x_i,y_i)\)，假设\(w\)和\(b\)初始为\(0\)向量
一个分类点迭代\(n_i\)次之后，\(w\)的增量：\(n_i\eta y_i x_i=\alpha_i y_i x_i\)
一个分类点迭代\(n_i\)次之后，\(b\)的增量：\(n_i\eta y_i=\alpha_i y_i\)
其中，\(\alpha_i=n_i \eta\)
由第二部分的定义说明，训练数据集中一共有\(m\)个样本点，故最后学习到的\(w\)和\(b\)如下： \[ \begin{equation} \begin{split} w&=\sum_{i=1}^{m}{\alpha_iy_i x_i}\\ b&=\sum_{i=1}^{m}{\alpha_iy_i} \end{split} \end{equation} \] 将公式(14)代入公式(1)得感知机对偶形式： \[ f(x)=f(\sum_{i=1}^{m}{\alpha_i y_i x_i \cdot x+b}) \]
其中\(\alpha=(\alpha_1,\alpha_2,\dots,\alpha_m)^T\)
| 对偶形式的算法流程： |
|---|
| 输入：训练数据集\(D=\{(x_1,y_1),\dots,(x_m,y_m)\}\)，学习率\(\eta\) |
| (1)\(\alpha \leftarrow 0\),\(b \leftarrow 0\) |
| (2)训练集中选择\((x_j,y_j)\) |
| (3)if $y_j(_{i=1}^{m}{_i y_i x_i x_j+b}) $ \(\alpha_j \leftarrow \alpha_j+1\),\(b \leftarrow b+y_j\) |
| (4)转到(2)直到无误分类 |
参考
1、《统计学习方法》
2、《机器学习》