《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第 2章感知机

《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第 2章感知机
《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第1章 统计学习方法概论

我算是有点基础的（有过深度学习和机器学的项目经验），但也是半路出家，无论是学Python还是深度学习，都是从问题出发，边查边做，没有系统的学过相关的知识，这样的好处是入门快（如果想快速入门，大家也可以试试，直接上手项目，从小项目开始），但也存在一个严重的问题就是，很多东西一知半解，容易走进死胡同出不来（感觉有点像陷入局部最优解，找不到出路），所以打算系统的学习几本口碑比较不错的书籍。
??书籍选择： 当然，机器学习相关的书籍有很多，很多英文版的神书，据说读英文版的书会更好，奈何英文不太好，比较难啃。国内也有很多书，周志华老师的“西瓜书”我也有了解过，看了前几章，个人感觉他肯能对初学者更友好一点，讲述的非常清楚，有很多描述性的内容。对比下来，更喜欢《统计学习方法》，毕竟能坚持看完才最重要。
??笔记内容： 笔记内容尽量省去了公式推导的部分，一方面latex编辑太费时间了，另一方面，我觉得公式一定要自己推到一边才有用（最好是手写）。尽量保留所有标题，但内容会有删减，通过标黑和列表的形式突出重点内容，要特意说一下，标灰的部分大家最好读一下（这部分是我觉得比较繁琐，但又不想删掉的部分）。
??代码实现： 最后是本章内容的实践，如果想要对应的.ipynb文件，可以留言

第 2章感知机

??感知机 (perceptron) 是二类分类的线性分类模型，其输入为实例的特征向量，输 出为实例的类别，取 +1 和-1 二值。

??感知机对应于输入空间(特征空间)中将实例划 分为正负两类的分离超平面，属于判别模型。

??感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此：

• 导入基于误分类的损失函数，
• 利用梯度下降法对损失函 数进行极小化，求得感知机模型。

??感知机学习算法具有简单而易于实现的优点，分为 原始形式和对偶形式。

2.1 感知机模型

??感知机是一种线性分类模型，属于判别模型。

??感知机模型的假设空间是定义在特征空间中的所有线性分类模型(linear classification modeD 或线性分类器 (linear classifier) ，即函数集合

$$f|f(x)=\omega ?x+b$$

几何解释：线性方程

$$\omega ?x+b=0$$

??对应于特征空间 $R^n$ 中的一个超平面 S ， 其中 ω 是超平面的法向量 ， b 是超平面的截距。

??这个超平面将特征空间划分为两个部分。位于两部分的点(特征向量)分别被分为 正、负两类。因此，超平面 S称为分离超平面 (separating hyperplane) ，如图 2.1 所示。

2.2 感知机学习策略

2.2.1 数据集的线性可分性

??给定一个数据集T:

$$T=(x_l,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

$$\omega ?x+b=0$$

??能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集 T 为线性可分数据集( linearly separable data set ) ;否则，称数据集 T 线性不可分。

2.2.2 感知机学习策略

??假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。

??损失函数的一个自然选择是误分类点的总数。但是，这样的损失函数不是连续可导函数，不易优化。损失函数的另一个选择是误分类点到超平面 S 的总距离。

• 输入空间 $R^n$ 中任一点 $x_o$ 到超平面 $S$ 的 距离:

$$\frac{1}{||w||}|w?x_0+b|$$

• 对于误分类的数据 $(x_i,x_i)$ 来说，

$$?y_i(\omega ?x_i+b)>O$$

• 当 $\omega ?x_i+b>0$ 时 ， $y_i=?1$
• 当 $\omega ?x_i+b<0$ 时， $x_i=+1$

• 所有误分类点到超平面 S 的总 距离为

$$?\frac{1}{||w||}\sum _{x_i\in M}{y}_i(w?x_0+b)$$

??感知机 $sign(w?x+b)$ 学习的损失函数定义为:

$$L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_0+b)$$

??其中 M 为误分类点的集合。

??这个损失函数就是感知机学习的经验风险函数。

2.3 感知机学习算法

??感知机学习问题转化为求解损失函数式的最优化问题，最优化的方法是随 机梯度下降法。

2.3.1 感知机学习算法的原始形式

求参数 $w，b$ ， 使其为以下损失函数极小化问题的解:

$$mi{n}_{w,b}L(w,b)=?\sum _{x_i\in M}{y}_i(w?x_i+b)$$

??其中 M 为误分类点的集合。

求解思路：

• 感知机学习算法是误分类驱动的，具体采用随机梯度下降法 (stochastic gradient descent)。
• 首先，任意选取一个超平面$w_0,b_0$ ， 然后用梯度下降法不断地极小化目标函数（损失函数）
• 极小化过程中不是一次使M 中所有误分类点的梯度下降，而是一次随机 选取一个误分类点使其梯度下降。
• 假设误分类点集合 M 是固定的，那么损失函数 $L(w,b)$的梯度由下式给出：

$${?}_{w}L(w,b)=?\sum _{x_i\in M}{y}_i{x}_i$$

$${?}_{b}L(w,b)=?\sum _{x_i\in M}{y}_i$$

• 随机选取一个误分类点$（x_i,y_i）$对 $\omega ，b$ 进行更新:

$$w\leftarrow w+\eta y_i{x}_i$$

$$b\leftarrow b+\eta y_i$$

??式中 $\eta (0<\eta \le 1)$ 是步长，在统计学习中又称为学习率(learning rate) 。

??这种学习算法直观上有如下解释：

??当一个实例点被误分类，即位于分离超平面的 错误一侧时，则调整 ω， b 的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

2.3.2 算法的收敛性

??定理表明，误分类的次数 k 是有上界的，经过有限次搜索可以找到将训练数据完 全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原 始形式迭代是收敛的。

2.3.3 感知机学习算法的对偶形式

??对偶形式的基本想法是，将 $\omega$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式， 通过求解其系数而求得 $\omega$ 和 $b$。

??对偶形式中训练实例仅以内积的形式出现。

??为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的 Gram 矩阵 (Gram matrix)：
$$G=[x_i?x_i{]}_{N\times N}$$