chap2 感知机模型简洁总结

1、感知机模型

输入空间：$\mathcal{X} \in \mathbb{R}^n$

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

特征空间：$\{f|f(\vec{x}) = sign(\vec{w} \cdot \vec{x} + b)\}$
($sign$ 为符号函数)

2、学习策略

$x_0$到超平面的距离：$\frac{1}{\Vert \vec{w} \Vert} \lvert \vec{w} \cdot \vec{x_0} + b \rvert$
($\Vert \vec{w} \Vert$ 是 $\vec{w}$ 的 $L_2$ 范数)

由于误分类点实际类别$y_i$与预测类别$f(\vec{x_i}) = sign(\vec{w} \cdot \vec{x_i} + b)$正负相反

因此误分类点到超平面的距离是：$-\frac{1}{\Vert \vec{w} \Vert} y_i (\vec{w} \cdot \vec{x_i} + b)$

为了便于求导，损失函数可以定义为：$L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i (\vec{w} \cdot \vec{x_i} + b)$

3、学习算法

随机梯度下降：一次随机选取一个误分类点进行梯度下降

损失函数$L$ 分别对 $\vec{w}$ 和 $b$ 求梯度得：
$\nabla_{\vec{w}} L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i \vec{x_i}$、
$\nabla_{b} L(\vec{w},b) = -\sum\limits_{x_i \in M} y_i$

参数更新方式：$\vec{w} = \vec{w} + \eta y_i x_i$、$b = b + \eta y_i$
($\eta \in (0,1]$ 为学习率)

参数一直更新，直到样本点中没有误分类点为止。

4、对偶问题

由上文的学习算法可得，$\vec{w}$ 和 $b$ 是通过逐次随机选取一个误分类点更新而来

因此可以设 $\vec{w}$ 的每个元素和 $b$ 都为0，参数总共更新 $n$ 次；

最终学习到的 $\vec{w}$ 和 $b$ 可以表示为：
$\vec{w} = \sum\limits_{i=1}\limits^{N} \alpha_i y_i x_i$、
$b = \sum\limits_{i=1}\limits^{N} \alpha_i y_i$
($\alpha_i = n_i \eta$，其中 $n_i$ 为点i被选中用于更新的次数)

由第三节中提到的 $\vec{w}$ 和 $b$ 的更新方式，可以反推出 $\alpha$ 和 $b$ 的更新方式：

$\alpha_i = \alpha_i + \eta$、$b = b + \eta y_i$