统计学习方法-第2章-感知机

• 适用问题：二分类，Y = {-1, +1}
• 模型特点：分离超平面
• 模型类型：判别模型
• 学习策略：极小化误分类点到分离超平面的距离
• 损失函数：误分类点到超平面的距离
• 学习算法：梯度下降法

模型

输入空间: $\mathcal { X } \subseteq \mathbf { R } ^ { n }$

输出空间：$\mathcal { Y } = { + 1 , - 1 }$

决策函数：$f ( x ) = \operatorname { sign } ( w \cdot x + b )$

$$ \operatorname { sign } ( x ) = \left\{ \begin{array} { l l } { + 1 , } & { x \geqslant 0 } \\ { - 1 , } & { x < 0 } \end{array} \right. $$

策略

• 误分类点的数目， 但这样的损失函数对于 w,b 不是连续可导，不宜优化；
• 误分类点到超平面的总距离；

$$ \begin{align*} \text{单样本的距离：} & \qquad \frac { 1 } { \parallel w \parallel } \left| w \cdot x _ { 0 } + b \right| \\ \text{误分类的点：} & \qquad -y _ { i } \left( w \cdot x _ { i } + b \right) > 0 \\ \text{误分类点距离：} & \qquad -\frac { 1 } { \parallel w \parallel } y _ { i } \left( w \cdot x _ { i } + b \right) \\ \text{数据的总距离：} & \qquad -\frac { 1 } { \parallel w \parallel } \sum _ { x _ { i } \in M } y _ { i } \left( w \cdot x _ { i } + b \right) \end{align*} $$

$\frac{1}{\parallel w \parallel}$：归一化超平面法向量，令其等于 1。

\[\text 损失函数： \qquad L ( w , b ) = - \sum _ { x _ { \in } \in M } y _ { i } \left( w \cdot x _ { i } + b \right) \text，M 为误分类点的集合\]

算法

原始形式

输入：线性可分数据集

\[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 } = \mathbf { R } ^ { n }$，$y _ { i } \in \mathcal { Y } = { - 1 , + 1 }$，$i = 1,2 , \cdots , N$，学习率 $\eta ( 0 < \eta \leqslant 1 )$;

输出：$w, b$，感知机模型 $f ( x ) = \operatorname { sign } ( w \cdot x + b )$

1. 选取初值 $w_0, b_0$；

2. 在训练集中选取数据 $\left( x_i, y_i \right)$；

3. 如果 $y _ { i } \left( w \cdot x _ { i } + b \right) \leqslant 0$

   $$ \begin{align*} w & \leftarrow w + \eta y _ { i } x _ { i } \\ b & \leftarrow b + \eta y _ { i } \end{align*} $$

4. 转置 2，直至训练集中没有误分类点。

对偶形式

对偶形式的基本思想是将 $w$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数而求得 $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 } = \mathbf { R } ^ { n }$，$y _ { i } \in \mathcal { Y } = { - 1 , + 1 }$，$i = 1,2 , \cdots , N$，学习率 $\eta ( 0 < \eta \leqslant 1 )$;

输出：$\alpha, b$，感知机模型 $f ( x ) = \operatorname { sign } \left( \sum _ { j = 1 } ^ { N } \alpha _ { j } y _ { j } x _ { j } \cdot x + b \right)$，其中 $\alpha = \left( \alpha _ { 1 } , \alpha _ { 2 } , \cdots , \alpha _ { N } \right) ^ { \mathrm { T } }$。

1. $\alpha \leftarrow 0, b \leftarrow 0$;

2. 在训练集中选取数据 $\left( x_i, y_i \right)$;

3. 如果 $y _ { l } \left( \sum _ { j = 1 } ^ { N } \alpha _ { j } y _ { j } x _ { j } \cdot x _ { i } + b \right) \leqslant 0$

   $$ \begin{align*} \alpha _ { i } & \leftarrow \alpha _ { i } + \eta \\ b & \leftarrow b + \eta y _ { i } \end{align*} $$

4. 转置 2，直至训练集中没有误分类点。