感知机

Perceptron

感知机用于二分类线性问题

感知机的数学定义

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

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

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

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

感知机学习策略

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

$$L(w, b) = -\sum_{x_i \in M} y_i(w \cdot x_i + b) \tag{3}$$

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

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

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

$$\begin{align*} &w \leftarrow w + \eta y_i x_i \\ &b \leftarrow b + \eta y_i \end{align*}$$

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

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

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

$$\begin{align*} &\alpha_i \leftarrow \alpha_i + \eta \\ &b \leftarrow b + \eta y_i \end{align*}$$

tips

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

$$\mathbf{G} = [x_i \cdot x_j]_{N \times N}$$