统计学习方法——感知机

感知机是机器学习的最基本模型之一，是神经网络和支持向量机的基础。

感知机的关键词

• 二分类
• 判别模型、线性模型
• 数据集线性可分时，有无穷多个解
• 无法解决XOR问题

感知机的原理

1. 感知机是根据数据实例的特征向量x对其进行二类分类的线形分类模型，输出为+1或-1。感知机的函数为：
   $$f(x)=sign(w\cdot x+b)$$
   其中$w$是权值，$b$是偏置，$w\cdot x$是$w$和$x$的内积，$sign$是符号函数，即，
   $$sign(x)=\{\begin{array}{ll}+1& x\ge 0\\ -1& x<0\end{array}$$
   当wx+b大于0时，根据sign函数，输出为1，对应正类；当wx+b小于0，输出为-1，对应负类。

2. 感知机的几何解释：线性方程 $w\cdot x+b=0$ 对应于特征空间中一个超平面$S$，这个超平面将特征空间划分为两个部分，位于两部分的点（特征向量）分别被分为正、负两类。超平面$S$也被称为分离超平面。
   一个线性方程将特征空间分成两部分。在二维特征空间内，wx+b=0即为一条之间，将平面分为两部分，直线上方的点带入wx+b计算值大于0，为正类，对应y值为+1，直线下方的点小于0，为负类，对应y值为-1。

3. 感知机学习的策略是极小化损失函 数：
   $$mi{n}_w{,}_{b}L(w,b)=-\sum y_i(w\cdot x_i+b),x_i\in M$$
   损失函数对应误分类点到分离超平面的总距离。
   该处的损失函数关注的是误分类点，而不是所有点。损失函数最小为零，即所有的点都分类正确。因此也导致了有无穷多个解。

4. 感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法。在原始形式中，首先选取一个超平面，然后用梯度下降法不断极小化目标函数，在这个过程中，一次随机选取一个误分类点使其梯度下降。

5. 当训练数据集线性可分时[补充1]，感知机学习算法是收敛的，但是存在无穷多个解，这些解既依赖于处值的选择，也依赖于迭代过程中误分类点的选择顺序。
   如果想要得到唯一的超平面，就需要对分离超平面增加约束条件。可参考支持向量机

为什么不能解决异或(XOR)问题

异或问题为二进制运算中，值相同为0，不相同为1。
把异或问题映射到二维空间里，可表示为：

图片来源： https://www.jianshu.com/p/853ebc9e69f6

在这个二维空间下，我们找不到一条直线将其分成两类。也就是说无法通过感知机模型将X分到直线的一边，同时将O分到直线的另一边。所以感知机解决不了异或问题。

补充知识

• 补充1：数据集的线性可分性
  给定一个数据集
  $$T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$$
  其中，$x_i\in X=R^n$，$y_i\in Y=\{+1,-1\}$，$i=1,2,\dots ,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）；否则，称数据集$T$线形不可分。

推荐阅读:

1. 15分钟透彻理解感知机（详细讲解+代码实现）
2. 基于sklearn的感知机python代码实现