感知机

Perceptron

感知机用于二分类线性问题，这说明感知机只能用于二分类问题，同时样本数据线性可分。

接下来会介绍感知机的数学定义，也就是感知机的输入输出映射；然后介绍感知机的学习算法，学习什么？学习的是感知机数学定义中提及到的参数；如何学习？会介绍两种方法，第一种是基于原始损失函数的迭代算法，另一种是基于原始损失函数的对偶形式的迭代算法，这两种算法本质上等价。

感知机的数学定义

假设输入空间 \(\mathcal{X} \subseteq \mathbb{R}^n\)，输出空间是 \(\mathcal{Y} = \{+1, -1\}\)。由输入空间到输出空间的如下函数：

\[ f(x) = \operatorname{sign} (\mathbf{w} \cdot \mathbf{x} + b) \tag{1} \]

称为感知机。其中，\(w\) 和 \(b\) 为感知机模型参数，前者叫权值 weight，后者叫偏置 bias，点乘运算为向量内积。\(\operatorname{sign}\) 是符号函数，具体定义如下：

\[ \operatorname{sign}(x) = \begin{cases} +1,& x \geq 0 \\[10pt] -1,& x < 0 \tag{2} \end{cases} \]

感知机学习策略

假设数据集线性可分，定义感知机学习的损失函数为：

\[ L(\mathbf{w}, b) = -\sum_{\mathbf{x}_i \in M} y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \tag{3} \]

其中，\(M\) 是误分类点的集合，我们的目标是极小化 \(L(\mathbf{w}, b)\)。

感知机学习算法的原始形式

随机初始化 \(\mathbf{w}\) 和 \(b\)，分别记为 \(\mathbf{w}_0\) 和 \(b_0\)，然后在训练数据集中选取数据 \((\mathbf{x}_i, y_i)\)；如果 \(y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \leq 0\),

\[ \begin{align*} &\mathbf{w} \leftarrow \mathbf{w} + \eta y_i \mathbf{x}_i \\[10pt] &b \leftarrow b + \eta y_i \end{align*} \]

重复上述选择更新过程直至没有误分类点。

这个更新过程，根据《统计学习方法》的例题，需要这样更新。假设我有一训练数据集 \(x_1, x_2, \cdots, x_N\)，我初始化完 \(\mathbf{w}\) 和 \(b\) 后，我从 \(x_1\) 开始，每次更新后都要从 \(1 \to N\) 的顺序进行验证。

感知机学习算法的对偶形式

与原始形式不同，对原始形式使用拉格朗日对偶化，得到相应的对偶形式。首先初始化系数和偏置 \(\mathbf{\alpha} \leftarrow \mathbf{0}, b \leftarrow 0\)。再在训练集中选取数据 \((\mathbf{x}_i, y_i)\)；如果 \(y_i \left(\sum_{j = 1}^{N} \alpha_j y_j (\mathbf{x}_j \cdot \mathbf{x}_i) + b \right) \leq 0\)，则更新

\[ \begin{align*} &\alpha_i \leftarrow \alpha_i + \eta \\[10pt] &b \leftarrow b + \eta y_i \end{align*} \]

tips

可以预处理出所有输入实例间的内积，并将其存为一个矩阵，这个矩阵叫做 Gram 矩阵，

\[ \mathbf{G} = [\mathbf{x}_i \cdot \mathbf{x}_j]_{N \times N} \]