统计学习方法-感知机

简述

由于首先接触到的是支持向量机，因此，感觉感知机算法就像是一个弱化版的支持向量机。在学习书中内容时，对对偶形式的解释进一步加强了我的理解，明白了向量内积矩阵对于算法加速的意义。

感知机模型

感知机模型属于判别模型，目的是寻找可以将特征空间的训练数据集分为正负两类的超平面。在公式中，$x$代表输入向量， $w$代表权重向量（$weight$），$b$代表偏差（$bias$）。$sign$函数代表超平面将数据集划分为正负两类。

$$f(x) = sign(w \cdot x + b) \tag 1$$ $$sign(x) = \begin{cases} +1, & \text{$x \ge 0$} \\ -1, & \text{$x < 0$} \end{cases} \tag 2$$

对于感知机模型来说，训练数据集必须是线性可分的，这样才存在超平面解。其次，分离平面也不是唯一的。由于采用随机梯度下降的方式，学习时数据的顺序也会导致超平面的变化。

损失函数

首先，我们要确定的是损失函数。感知机特殊的地方在于，它不能够直接使用平方差损失函数，因为它的损失函数需要能体现出误分类的总数。公式三可以指出，如果一个数据被误分类的话，它的真实标签与预测标签一定是符号相反的。因此，所有误分类标签的集合就是感知机的损失函数（不考虑$\Vert{w}\Vert$的话），如公式四所示（M代表误分类总集合）。

$$f(x) = -y_i (w \cdot x_i + b) > 0 \tag 3$$ $$f(x) = -\sum_{x_i \in M} y_i (w \cdot x_i + b) \tag 4$$

优化算法

感知机采用随机梯度下降算法进行优化。步骤如下

1. 选取$w$（权重）和$b$（偏差）的初值。
2. 选取训练集中的数据（$x_i$, $y_i$）。
3. 如果$f(x) = -y_i (w \cdot x_i + b) > 0$，说明需要根据该误分类点更新数据。其中$\eta$是学习率，更新值则分别是损失函数对$w$和$b$求偏导得出。 $$w \leftarrow w + \eta y_ix_i \tag 5$$ $$b \leftarrow b + \eta y_i \tag 6$$
4. 一直重复步骤2，3直到没有误分类点。
   在《统计机器学习》一书中，作者证明了对于线性可分数据集，经过有限次迭代可以得到一个完全正确分类所有训练集的超平面，这里不再展开

感知机算法的对偶形式

最开始接触对偶形式还是在支持向量机中的核方法，这里又重新接触一遍。在感知机中，对偶形式表示可以使用向量内积的方式来加速算法的收敛。在公式5和6中，我们可以看到，对于权重的更新，是学习率乘以真实标签的值再乘以数据点的值（$\eta y_i x_i$）。对于偏差的更新，是学习率乘以真实标签的值（$\eta y_i$）。如果$w$和$b$的初始值为零的话，那么最终它们的值将为:

$$w = \sum_{i=1}^{N}\alpha_i y_i x_i, \space b = \sum_{i=1}^{N}\alpha_i y_i, \space \alpha_i = n_i \eta \tag 7$$

在这里$\alpha_i$代表对应的数据点更新的次数乘以学习率。因此，当我们算出每一个数据点更新的次数，我们就可以通过公式7直接得出最后的权重与偏差。这将是非常方便的，因为在更新参数时我们会将每一个$\alpha_j y_j x_j$与当前数据点的向量$x_i$进行点乘，而$x_j$与$x_i$我们可以提前计算好内积矩阵。内积矩阵与$\alpha_j y_j$相乘时又可以使用矩阵操作，这将大大减少运算时间从而提高效率。
首先，感知机模型将会变成

$$f(x) = sign(\sum_{j=1}^{N}\alpha_j y_j x_j \cdot x + b) \tag 8$$

其中，$\alpha = (\alpha_1, \alpha_2, …., \alpha_N)^T$
因此，算法的收敛过程将会变成如下形式：

1. $\alpha \leftarrow 0, \space b \leftarrow 0$
2. 选取数据点$(x_i, y_i)$
3. 如果 $y_i (\sum_{j=1}^{N} \alpha_j y_j x_j \cdot x + b) \le 0$,
   更新 $$\alpha \leftarrow \alpha_i + \eta \tag 9$$ $$b \leftarrow b_i + \eta y_i \tag {10}$$
4. 重复2，3直到完全收敛

总结

感知机算法总的来说是个基础的机器学习二分类算法，利用真实标签与预测标签之间的正负性作为损失函数，使用随机梯度下降法来更新参数。而且，对偶形式的出现使得我们更新参数时只需要计算每一个数据点更新次数和内积矩阵的乘积，大大提高了计算速度，也为后续SVM中核方法的使用进行了铺垫。