ML1-5 感知机

1. 背景与联系

感知机学习算法（The Perceptron Learning Algorithm, PLA）由 Frank Rosenblatt 于 1958 年在康奈尔航空实验室发明。有人认为这是大脑中单个神经元如何工作的近似模型。虽然它没有在实践中广泛使用，但是它很具备历史意义，可见：

• 支持向量机（SVM）的基础是感知机
• 神经网络又称多层感知机（Multi-Layer Perceptron, MLP）

因此，理解感知机原理，对我们后续的学习非常有帮助。

感知机算法可以被视为前述逻辑回归算法的简化变体。考虑修改逻辑回归方法以强制其输出精确为 0 或 1。为此，我们可以很自然地改变 $g$ 的定义为阈值函数：

$$g(z) = \begin{cases}1 & \text{if } z \ge 0 \\0 & \text{if } z < 0\end{cases}$$

如果我们仍然像之前一样令 $h_\theta(x) = g(\theta^T x)$ ，但使用这种修改后的 $g$ 的定义，并且沿用上一节中逻辑回归的更新规则：

$$\theta_j := \theta_j + \alpha \left( y^{(i)} - h_\theta(x^{(i)}) \right) x_j^{(i)}$$

那么我们就得到了感知机学习算法。

注意

感知机算法实际上是一种与逻辑回归和最小二乘线性回归不同类型的算法。
并且很难为感知器的预测赋予有意义的概率解释。

2. 感知机定义与结构

感知机是一种简单的二分类的线性分类模型。下面给出维基百科的定义：

引用

感知器使用特征向量来表示的前馈神经网络，它是一种二元分类器，把矩阵上的输入$x$（实数值向量）映射到输出值 $f(x)$ 上（一个二元的值）。

$$f(x) = \begin{cases} 1 & \text{if } w \cdot x + b > 0 \\ 0 & \text{else} \end{cases}$$

• $w$ 是实数的表示权重的向量，$w⋅x$ 是点积。
• $b$ 是偏置，一个不依赖于任何输入值的常数。偏置可以认为是激励函数的偏移量，或者给神经元一个基础活跃等级。

由于感知机旨在对单个神经元的工作进行模拟，所以我们可以拿来神经元的结构与其进行比较。下图给出了典型神经元的结构：

如图，神经元从树突接收输入信息，在胞体整合信息，通过轴突传递信息，之后在突触处产生相应的输出。感知机试图去模拟这个过程，如下图：

如图，感知机接收输入信号 $a_1, a_2, \dots, a_n$ ，$w_1, w_2, \dots, w_n$ 为各个信号连接到感知机的权值，$b$ 为偏置量。感知机接收输入信号 $a$ 的各个分量，通过线性加权 $w$ 求和并且加上偏置量 $b$ ，最后借助激活函数 $f$ 来给出一个标量输出。

根据上述结构，可以给出感知机的定义：

有数据集 $\{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$ ，其中输入空间是 $\mathcal{R}^n$ ，输出空间是 $\{-1, +1 \}$。感知机输入为实例的特征向量，输出为实例的类别，在此定义下，$+1$ 代表正类，$-1$ 代表负类。给出从输入空间到输出空间的函数：

$$t = f\left(\sum_{i=1}^{n} w_i x_i + b\right) = f(w · x + b)$$

如果继续我们之前的写法（dummy node法），令 $x_0 = 1$ ，并将偏置 $b$ 并入权重，使得 $\mathbf{w} = [ b, w_1, w_2, ..., w_n ]$，$\mathbf{x} = [1, x_1, x_2, ..., x_n]$ ，那么

$$t = f(\mathbf{w}^T \mathbf{x})$$

$f(x)$ 为符号函数 $sgn(x)$ 的反对称，即：

$$f(x) = \begin{cases} +1 & \text{if } n \ge 0 \\ -1 & \text{otherwise} \end{cases}$$

3. 感知机学习算法

感知机学习过程中需要更新参数 $\mathbf{w} = [ b, w_1, w_2, ..., w_n ]$ （更新 $w$ 和 $b$）。我们依旧将学习问题转换为最优化问题，因此需要表示感知机学习过程中的损失函数。

3.1 线性可分性

给定数据集 $T = \{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \}$，满足 $x∈ \mathcal{R}^n，y ∈ \{+1,-1\}$ ，如果存在某个超平面 $S$

$$w · x + b = 0$$

能够将数据集的正实例点和负实例点完全正确的划分到超平面 $S$ 的两侧，即对所有 $y=+1$ 的实例，有 $w·x+b>0$ ，对所有 $y=-1$ 的实例，有 $w·x+b<0$ ，则称数据集 $T$ 为线性可分数据集；否则，称数据集 $T$ 为线性不可分。

感知机只能解决线性可分问题，线性不可分时算法无法收敛。

超平面

在数学中，超平面（Hyperplane）是 $n$ 维欧氏空间中，余维度为 $1$ 的子空间。即超平面是 $n$ 维空间中的 $n-1$ 维的子空间。它是平面中的直线、空间中的平面之推广 （$n \ge 3$ 时），用于在机器学习中构建决策边界（decision boundary）。

• 余维度为 $1$，说明存在某个方向（法平面方向）， $n - 1$ 维子空间沿着此方向即可张满整个 $n$ 维空间。
• 超平面是线性组合而成的（联想二维直线，三维平面的参数，类推到高维超平面）

3.2 损失函数推导

若假设数据集是线性可分的，感知机学习的目的就是寻找到数据特征空间中的一个分离超平面（separable hyperplane）。这样的超平面由参数 $w$ 和 $b$ 确定。

感知机只在犯错时更新权重，即它是错误驱动的。

因而，感知机的损失函数一般定义为错误分类样本的个数：

$$L(w, b) = \sum_{i=1}^{N} \left[ y_i \neq f(w \cdot x_i + b) \right]$$

上述公式不是 $w$ 和 $b$ 的可导函数，优化根本无从下手。

因而，使用错误分类点到超平面 $S$ 的距离替代刚才的损失函数。

在超平面 $w·x + b = 0$ 上取任意两个点 $x_1$ 和 $x_2$，它们都满足
$$\begin{cases} w \cdot x_1 + b = 0 \\ w \cdot x_2 + b = 0 \end{cases}$$
从而有 $w \cdot (x_1 - x_2) = 0$ ，即 $w$ 是超平面 $S$ 的法向量。
对于输入空间中的任一点 $x_0$ ，设其到超平面 $S$ 的距离为 $d$，那么沿法向量方向有
$$x_0 = x_S + d \cdot \frac{w}{||w||}$$
上式两边同时左乘 $w$ ，有
$$w \cdot x_0 = w \cdot x_S + d \cdot ||w||$$
$x_S$ 在超平面 $S$ 上，有$w \cdot x_S + b = 0$ ，从而
$$d = \frac{1}{||w||} |w \cdot x_0 + b|$$

而对于被错误分类的点 $(x_k, y_k)$，总是有

$$- y_k (w \cdot x_k + b) \gt 0$$

故损失函数可以表示为

$$L(w, b) = \sum_{y_i \neq f(w \cdot x_i + b)} - \frac{1}{||w||} y_i (w \cdot x_i + b)$$
一般不考虑 $\frac{1}{||w||}$，所以

$$L(w, b) = \sum_{y_i \neq f(w \cdot x_i + b)} - y_i (w \cdot x_i + b)$$

提示

不考虑 $\frac{1}{||w||}$ 的原因：

• 若训练集线性可分，那么感知机最终一定能找到超平面 $S$，损失函数终归为 0。$\frac{1}{||w||}$ 的取值不会对这个结果造成影响。
• 感知机对超平面的求解存在多种可能，但是其目的就是只求“分对”，不求“最优”。
• 感知机学习过程中，分类是否正确，看 $f(w \cdot x_i + b)$ 的符号即可。
• 梯度形式简洁。

上式中 $y_i (w \cdot x_i + b)$ 称为样本点的函数间隔。

摘要

间隔（margin）：用于描述决策边界和两侧数据点之间的空间

• 函数间隔（Functional Margin）：形如 $\hat{\gamma}_i = y_i (w \cdot x_i + b)$
  • 通过比较分类器的预测（$w \cdot x + b$）与实际类别（$y_i$）来计算超平面的间隔。
  • 函数间隔 $\hat{\gamma}_i$ 若为正，说明分类器做出了正确的分类。分类与符号相关，与大小无关。
  • $w$ 和 $b$ 可以被任意缩放，这意味着没有有用的方式来最大化函数间隔。
• 几何间隔（Geometric Margin）：形如 $\gamma = y_i \left( \left( \frac{w}{||w||} \right) \cdot x_i + \frac{b}{||w||} \right)$
  • 定义为从数据点到决策边界的距离。
  • 几何间隔本质上与函数间隔相同，只是 $w$ 和 $b$ 被缩放了一个 $\frac{1}{||w||}$ 的因子。
• 超平面的间隔定义为所有数据点中计算出的最小间隔
  • 函数间隔代表所有被分类点中最低的"置信度"。
  • 几何间隔代表从 $x_i$ 到超平面的最小距离。

3.3 梯度下降过程

3.3.1 原始形式

根据上述损失函数的形式，我们将其转化为优化问题

$$\min_{w, b} \sum_{y_i \neq f(w \cdot x_i + b)} -y_i (w \cdot x_i + b)$$

上述问题可以采取随机梯度下降的方式进行优化，对目标函数求梯度

$$\frac{\partial L(w, b)}{\partial w} = \sum_{y_i \neq f(w \cdot x_i + b)} -y_i x_i$$

$$\frac{\partial L(w, b)}{\partial b} = \sum_{y_i \neq f(w \cdot x_i + b)} -y_i$$

上式给出感知机损失的梯度，其形式非常简洁。每次随机选择一个错误分类点 $(x_i, y_i)$ ，对参数 $w$ 和 $b$ 进行更新：

$$w \leftarrow w + \eta y_i x_i$$

$$b \leftarrow b + \eta y_i$$

式中 $\eta$ ($0 \lt \eta \le 1$)为学习率。但对于感知机来说，其实并不需要学习率，因为把更新乘以任意常数只是缩放权重，永远不会改变预测的符号。所以将学习率取为 1，更为简洁：

$$w \leftarrow w + y_i x_i$$

$$b \leftarrow b + y_i$$

3.3.2 对偶形式

假设算法初始选择 $w^{(0)} = 0$，$b^{(0)} = 0$，那么由参数更新规则

$$w \leftarrow w + \eta y_i x_i$$

$$b \leftarrow b + \eta y_i$$

设总共更新 $n$ 次，则 $w,b$ 关于 $(x_i,y_i)$ 的增量分别是 $α_iy_ix_i$ 和 $α_iy_i$，其中

$$\sum_{i=1}^{N} n_i = n$$

$$α_i=n_iη$$

当 $η = 1$ 时，$\alpha_i = n_i$ 表示第 $i$ 个实例点由于误分类而进行更新的次数。

可以发现，经过多轮更新后，有

$$w = \sum_{i=1}^{N} \alpha_i y_i x_i$$

$$b = \sum_{i=1}^{N} \alpha_i y_i$$

上式中，参数 $w$ 和 $b$ 被表达为 $x$ 和 $y$ 的线性组合，即以样本点为基。因此，我们只要求出 $\alpha$ 就可以表示参数 $w$ 和 $b$。

在训练过程中，对于样本点 $(x_i, y_i)$，需要判断其是否被误分类，即

$$f(w \cdot x_j + b) = f\left( \sum_{i=1}^{N} \alpha_i y_i x_i \cdot x_j + \sum_{i=1}^{N} \alpha_i y_i \right)$$

若上式非正，说明该样本点被误分类，则需要驱动参数更新。将 $w、b$ 关于 $\alpha$ 的参数式代入原始形式的更新规则，有

$$α_i \leftarrow α_i + η$$

$$b \leftarrow b + ηy_i$$

提示

由于训练实例仅以内积 $x_i \cdot x_j$ 的形式出现，所以在训练前可以用 Gram 矩阵存储各点之间的内积，加快速度并且减少重复计算：
$$G = [x^T_i y_i]_{N × N}$$
原始形式下有内积 $w \cdot x_i$，$w$ 每轮都在更新，所以时间复杂度高且引入在线学习。
对偶形式下实例仅仅以内积形式出现，这便于我们在之后的学习中引入核函数。

4. 感知机的局限

单层感知机无法学习不可线性分离的函数。典型例子是 XOR 问题。

如图，左图表示 OR 是线性可分的，而 XOR 是不可线性分离的。

解决方式：

• 引入高维空间，在高维空间中更容易找到分离超平面
• 引入多层感知机以解决非线性问题