《统计学习方法》读书笔记2：感知机

感知机（perceptron）的输入空间是 $\mathcal{X} \subseteq \mathbb{R}^n$ ，输出空间是 $\mathcal{Y} = \{+1, -1\}$ ，输入空间到输出空间的函数是：
$f(x) = \mathrm{sign}(w \cdot x + b)$
其中， $\mathrm{sign}$ 是符号函数：
$\mathrm{sign}(x) = \begin{cases} +1, & x \geq 0 \\ -1, & x < 0 \end{cases}$
如果存在一个超平面可以将数据的正类负类分开，那么数据被称为线性可分的。
感知机只能处理线性可分的数据。
感知机的损失函数，是所有错误分类的点到超平面的距离之和：
$-\frac{1}{\|w\|} \sum_{x_i \in M} y_i (w \cdot x_i + b)$
因为 $\frac{1}{\|w\|}$ 是常数，所以可以忽略掉它得到最终的损失函数：
$L(w, b) = -\sum_{x_i \in M} y_i (w \cdot x_i + b)$
使用此函数而不是误分类数作为代价函数的好处是，这个函数可导，便于计算。
感知机学习算法的原始形式：
1. 选取初值 $w_0, b_0$ 。
2. 在训练集中选取数据 $(x_i, y_i)$ 。
3. 如果 $y_i (w \cdot x_i + b) \leq 0$ ：
  $w \leftarrow w + \eta y_i x_i$ $b \leftarrow b + \eta y_i$
4. 转至 2，直至训练集中没有误分类点。
可以证明，算法是收敛的，也就是经过有限次迭代，一定能将线性可分的数据完全正确分类。但是解不唯一。证明方法留待以后看。
感知机存在一个对偶解法，使用对偶解法的原因可以查看这个知乎帖子。
感知机模型的对偶解法还需要仔细理解，以后补充。