统计学习方法——感知机（一）
统计学习方法——感知机
- 感知机
-
- 感知机模型
- 感知机学习策略
-
-
- 数据集的线性可分性
-
- 感知机学习策略
- 感知机学习算法
-
-
- 参考文献
-
感知机
感知机是是二分类线性分类模型，输入为实例的特征向量，输出为实例类别（-1,+1）。
感知机模型
感知机模型属于判别模型，目标是求出将训练样本进行线性划分的分离超平面。
-
感知机
假设输入空间（特征空间）为\mathcal{X}，输出空间是\mathcal{Y}，x\in \mathcal{X}是每个实例的特征向量，则从输入空间到输出空间的映射为：
f\left( x \right) = sign\left( {w \cdot x + b} \right)
也称之为感知机。其中w,b为模型参数，w是特征属性的权值向量，b为偏置项，sign函数为
sign \left( x \right) = \left\{ \begin{array}{l} {+ 1}\quad x \ge 0\\ {- 1}\quad x < 0 \end{array} \right. -
感知机的几何解释
线性方程w\cdot x+b=0对应特征空间中的一个超平面S，其中w是超平面的法向量，b是超平面的截距，如下图所示：
感知机学习策略
数据集的线性可分性
前面我们已经说过了，感知机处理数据的两个特性：二分类、线性。所以我们先来看一下数据的线性可分性。
- 数据的线性可分性
对于一个数据集T = \left\{ {\left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right), \cdots ,\left( {{x_N},{y_N}} \right)} \right\}，其中x_i\in\mathcal{X}，y_i\in\mathcal{Y}=\left\{-1,+1\right\}【体现了二分类】,i=1,2,\cdots,N，如果存在一个超平面S
w\cdot x+b=0
能够将聚集的正实例和负实例完全正确地划分，则称数据集为线性可分的，否则则是不可分的。
感知机学习策略
为了找到超平面，需要确定感知机模型参数w,b，需要一个学习策略，也就是所谓的定义并最小化（经验）损失函数。
-
损失函数的选择有两种：
误分类点的总数(此损失函数关于w,b参数不是连续可导的)- 误分类点到超平面S的总距离
-
损失函数的定义
-
L_2范数：向量各元素的平方和然后求平方根，用\left\| {} \right\|表示。
-
推导过程
-
空间中任意点x_0到平面S的距离：\frac{1}{{\left\| w \right\|}}\left| {w \cdot {x_0} + b} \right|
-
对误分类的点\left( {{x_i},{y_i}} \right)则有：- {y_i}\left( {w \cdot {x_i} + b} \right) > 0
【因为被误分类，所以y_i与\left( {w \cdot {x_i} + b} \right)必然异号，所以{y_i}\left( {w \cdot {x_i} + b} \right) < 0，- {y_i}\left( {w \cdot {x_i} + b} \right) > 0】 -
误分类点x_i带S的距离为：- \frac{1}{{\left\| w \right\|}}{y_i}\left( {w \cdot {x_i} + b} \right)
-
所有误分类点到超平面S的总距离为
- \frac{1}{{\left\| w \right\|}}\sum\limits_{{x_i} \in M} {{y_i}\left( {w \cdot {x_i} + b} \right)}
-
-
感知机学习的损失函数
不考虑\frac{1}{{\left\| w \right\|}}，就得到感知机学习的损失函数：
L\left(w,b\right)=-\sum\limits_{{x_i} \in M} {{y_i}\left( {w \cdot {x_i} + b} \right)}
其中M为误分类点的集合。
-
感知机学习算法
- 感知机学习算法
-
感知机学习算法的目标是（误分类驱动）：
\mathop {\min }\limits_{w,b} L\left( {w,b} \right) = - \sum\limits_{{x_i} \in M} {{y_i}\left( {w \cdot {x_i} + b} \right)} -
具体算法
- 随机梯度下降法：任取超平面w_0,b_0，然后每次从M中每次随机选择一个点进行梯度下降。
-
假定误分类点集合M固定，则L\left( {w,b} \right)的梯度为
{\nabla _w}L\left( {w,b} \right) = - \sum\limits_{{x_i} \in M} {{y_i}{x_i}}
{\nabla _b}L\left( {w,b} \right) = - \sum\limits_{{x_i} \in M} {{y_i}} -
随机选取一个误分类点\left( {{x_i},{y_i}} \right)，对w,b进行更新
w \leftarrow w + \eta {y_i}{x_i}
b \leftarrow b+\eta {y_i}
其中\eta \left( {0 < \eta \le 1} \right)是步长，在统计学习中又称为学习率。 -
通过迭代可以期待损失函数L\left( {w,b} \right)不断减小,直到为0。
-
【直观上说：当一个实例点被误分类则调整平面以减少该点到平面的距离，知直到全部分类正确】
不同的初值或选取不同的误分类点，解可以不同。
算法的收敛性
算法应该是收敛的，因为只有收敛才能经过有限次的迭代得到感知机模型。
* Novikoff 设训练数据集T=\left\{ {\left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right), \cdots ,\left( {{x_N},{y_N}} \right)} \right\}是线性可分的，则
1. 存在满足条件$\left\| {{{\hat w}_{opt}}} \right\| = 1$的超平面${{\hat w}_{opt}} \cdot \hat x = {w_{opt}} \cdot x + {b_{opt}} = 0$将训练数据集完全正确分开；且存在$\gamma = 0$，对所有的样本有： {y_i}\left( {{{\hat w}_{opt}} \cdot {{\hat x}_i}} \right) = {y_i}\left( {{w_{opt}} \cdot {x_i} + {b_{opt}}} \right) \ge \gamma
2. 令$R = \mathop {\max }\limits_{1 \le i \le N} \left\| {{{\hat x}_i}} \right\|$，则感知机算法在训练数据集上的误分类次数$k$满足： k \le {\left( {\frac{R}{\gamma }} \right)^2}
感知机学习算法的对偶形式
* 对偶形式的基本想法 将w和b表示为实例x_i和y_i的线性组合的形式，进一步求解w和b。
* 详细过程
* 假设初始$w_0=b_0=0$，对误分类点$\left( {{x_i},{y_i}} \right)$通过 w \leftarrow w + \eta {y_i}{x_i}
b \leftarrow b + \eta {y_i}
逐步修改w,b。
* 学到最后$w,b$表示为 w = \sum\limits_{i = 1}^N {{\alpha _i}{y_i}{x_i}}
b = \sum\limits_{i = 1}^N {{\alpha _i}{y_i}}
其中\alpha_i \ge 0, i=1,2,...,N，当\alpha=1时表示第i个实例点由于误分而进行更新的次数。
* 规范表述 输入：线性可分数据集T，学习率\eta
输出：\alpha,b；感知机模型f\left( x \right) = sign\left( {\sum\limits_{j = 1}^N {{\alpha _j}{y_j}{x_j} \cdot x + b} } \right)，其中\alpha = {\left( {{\alpha _1},{\alpha _2}, \cdots ,{\alpha _N}} \right)^T}
（1）\alpha \leftarrow 0,b \leftarrow 0
（2）在训练集中选取数据\left( {{x_i},{y_i}} \right)
（3）如果{y_i}\left( {\sum\limits_{j = 1}^N {{\alpha _j}{y_j}{x_j} \cdot {x_i} + b} } \right) \le 0
{\alpha _i} \leftarrow {\alpha _i} + \eta
b \leftarrow b + \eta {y_i}
（4）直到无误分类数据。
参考文献
《机器学习》
《统计学习方法》