Data-方法-05 感知机

The general freedom in academic life is, in my view, one of its most important features. The long vacations are exceedingly attractive as is also the general feeling of freedom in hours of work. - Claude Shannon

Data系列：目录｜配置｜代码仓库｜对应实战
对应《统计学习方法（第2版）》第2章、《数据挖掘导论》第5章、《机器学习》第5章。
感知机作为神经网络和支持向量机的基础，可以说占据了这几十年来人工智能的江山。虽然现在很多的书籍中，已经更多地从神经网络的角度来解释感知机，将其归在了神经网络的章节之中。~~但作为一个能快速单开一章的方法，我又怎么舍得把它放在别的内容之中呢~~

1. 感知机模型

感知机或感知器(preceptron)由Frank Roseblatt于1957年提出，是二分类的线性分类模型，属于判别模型。感知机可以说是最简单的人工神经网络，只有一个神经元。
输入：实例的特征向量$x$，输入空间为 $\mathcal{X}\subseteq {\rm R}^n$
输出：实例的类别$y$，输出空间为 $\mathcal{Y}=\{+1,-1\}$
任务：寻找出将训练数据线性划分的分离超平面(separating hyperplane)，寻找由输入空间到输出空间的函数，
- $f(x)={\rm sign}(w\cdot x+b)$
  - $w$：权值(weight)，神经元的角度看为突触
  - $b$：偏置(bias)，神经元的角度看为阈值(threshold)的相反数
- $f$：激活函数(activvation function)，神经元的角度看为细胞体
- ${\rm sign}$函数：符号函数，也可以写为${\rm sgn}$
  
  $$ {\rm sign(x)}= \begin{cases} +1,\quad &x\ge0\\ -1,&x<0 \end{cases} $$
分离超平面示意(来自《统计学习方法》)：

2. 感知机学习

【学习策略-损失函数】

感知机学习目标：求一个将训练集正负实例点完全正确分开的分离超平面。
学习策略：定义（经验）损失函数并将损失函数，并将损失函数极小化。
损失函数的自然选择是误分类点的总数，但由于这样不是参数$w$、$b$的连续可导函数，不易优化，所以没有选择。
感知机学习策略实际选择的是，误分类点到超平面$S$的总距离。
任意一点$x_0$到超平面的距离为：$\frac{1}{||w||}|w\cdot x_0+b|$，$||w||$表示L2范数
误分类数据$(x_i,y_i)$有：$y_i(w\cdot x_i+b)<0$
- 设误分类集合为$M$，则总距离为：$-\frac{1}{||w||}y_i(w\cdot x_i+b)$
不考虑$\frac{1}{||w||}$，则感知机学习的损失函数（经验风险函数）为：$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$
- 是$w$, $b$的连续可导函数
感知机学习就是在假设空间$\{f|f(x)=w\cdot x+b\}$中选取使损失函数$L(w,b)$最小的模型参数$w,b$，即求解损失函数的最优化问题，采用的方法是随机梯度下降法(stochastic gradient descent)。

【学习算法-原始形式】

感知机学习算法是误分类驱动、错误驱动的，采用随机梯度下降法进行最优化。
简单来说，先任意选择一个超平面$w_0,b_0$，然后每次随机选择一个误分类点通过梯度下降法不断地极小化目标函数。
感知机学习算法原始形式：
- 输入：
  - 训练数据集$T=\{(x_1,y_1),(x_2,y_2)...,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}\subseteq {\rm R}^n$，$y_i\in\mathcal{Y}=\{+1,-1\}$
  - 学习率(learning rate)/步长$\eta$ ($0<\eta\le1$)
- 输出：
  - $w,b$，感知机模型$f(x)={\rm sign}(w\cdot x+b)$
- 算法步骤：
  1. 选取初始值$w_0,b_0$；
  2. 在训练集中选取数据$(x_i,y_i)$；
  3. 如果为误分类点，即$y_i(w\cdot x_i+b)\le0$，
    
    $$ \begin{aligned} &w\leftarrow w+\eta y_ix_i\\ &b\leftarrow b+\eta y_i \end{aligned} $$
  4. 到2步，直至没有误分类点。
感知机学习算法由于采取不同的初值或选取不同的误分类点，解可以不同。

【学习算法-对偶形式】

对偶形式的基本想法是，将$w$和$b$表示为实例$x_i$和标记$y_i$的线性组合的形式，通过求解其系数而得到$w$和$b$。
对偶形式的构造：
- 在原始形式中，设初始值$w_0$和$b_0$均为0，对误分类点$(x_i,y_i)$进行随机梯度下降，逐步修改$w$和$b$；
- 设修改$n$次，则$w$和$b$关于$(x_i,y_i)$的增量分别为$\alpha_iy_ix_i$和$\alpha_iy_i$，即$\alpha_i=n_i\eta$；
- 最后学到的$w,b$可以表示为：
  
  $$ \begin{aligned} &w=\sum^N_{i=1}\alpha_iy_ix_i\\ &b=\sum^N_{i=1}\alpha_iy_i \end{aligned} $$
感知机学习算法对偶形式：
- 输入：
  - 训练数据集$T=\{(x_1,y_1),(x_2,y_2)...,(x_N,y_N)\}$，其中$x_i\in\mathcal{X}\subseteq {\rm R}^n$，$y_i\in\mathcal{Y}=\{+1,-1\}$
  - 学习率(learning rate)/步长$\eta$ ($0<\eta\le1$)
- 输出：
  - $\alpha,b$，感知机模型 $f(x)={\rm sign}(\sum^N_{j=1}\alpha_jy_jx_j\cdot x+b)$，其中$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$
- 算法步骤：
  1. $\alpha\leftarrow0$，$b\leftarrow0$；
  2. 在训练集中选取数据$(x_i,y_i)$；
  3. 如果为误分类点，即$(\sum^N_{j=1}\alpha_jy_jx_j\cdot x_i+b)\le0$，
    
    $$ \begin{aligned} &\alpha_i\leftarrow\alpha_i+\eta\\ &b\leftarrow b+\eta y_i \end{aligned} $$
  4. 到2步，直至没有误分类点。
在对偶形式中，训练实例仅以内积形式$x_ix_j$出现，所以可以预先将内积求出并以矩阵形式存储，这个矩阵就是所谓的Gram矩阵：$\textbf{G}=[x_i\cdot x_j]_{N\times N}$。
与原始形式一样，感知机学习算法的对偶形式也是存在多个解。
两个形式的计算示例可以参考《统计学习方法》中的示例。

3. 感知机学习的评价

【线性可分性与收敛性】

对一个数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，若存在某个超平面$S$：$w\cdot x+b=0$ 能将正实例点和负实例点完全正确地划分到超平面的两侧，即对所有$y_i=+1$的实例$i$，有$w\cdot x_i+b>0$；对所有$y_i=-1$的实例$i$，有$w\cdot x_i+b<0$。则称数据集$T$为线性可分数据集(linearly separable data set)，否则称之为线性不可分。
当数据集线性可分时，感知机学习算法的原始形式和对偶形式迭代都是收敛的(converge)；而当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡(fluctuation)（《统计学习方法》中给出了推导的过程，证明对线性可分数据集，感知机学习的迭代次数是有上限的）。