简介

感知机 是 二分类 模型, 属于 判别式模型 . 目标是求出将训练数据进行线性划分的分离超平面.

感知机模型 : 输入空间为 $\chi\subseteq\textbf{R}^n$ , 输出空间是 $Y=\{+1, -1\}$ . $x\in\chi$表示输入空间中的点. 输入空间到输出空间的映射函数为:

$$f(x) = sign(\omega \cdot x + b)$$

其中, $\omega$ 和 $b$ 为感知机模型参数, $\omega \in \textbf{R}^n$ 为权值向量, $b \in \textbf{R} $ 为偏置. $sign$ 是符号函数 $
sign(x) =
\left\{
\begin{aligned}
+1, & x \geq 0 \\
-1, & x < 0
\end{aligned}
\right.
$

感知机学习策略 : 感知机的目标是学得一个超平面 $S$ : $\omega \cdot x + b = 0$ 将正实例点和负实例点完全正确分开. 可知 $S$ 由感知机模型参数 $\omega$ , $b$ 确定. 为了确定 $\omega$ , $b$ 需定义一个损失函数并将损失函数最小化. 感知机的损失函数为误分类点到超平面 $S$ 的总距离. 输入空间中的任意一点 $x_0 \in \textbf{R}$ 到超平面 $S$ 的距离公式为 :

$$\frac{1}{\parallel \omega \parallel} |\omega \cdot x_0 + b|$$

其证明过程如下 :
Definition $x_1$ is the projection of $x_0$ in $S$ , and $\omega$ is the normal vector of $S$, so $\overrightarrow{x_0x_1}$ and $\omega$ is parallel. so,
$\omega \cdot \overrightarrow{x_0x_1} = |\omega| |\overrightarrow{x_0x_1}| \cos{(0)}= \parallel \omega \parallel d$ , and
$$
\begin{align}
\omega \cdot \overrightarrow{x_0x_1} & = \omega^1 (x^1_0 - x^1_1) + \omega^2 (x^2_0 - x^2_1) + … + \omega^N (x^N_0 - x^N_1) \\
& = \omega^1 x^1_0 + \omega^2 x^2_0 + … + \omega^N x^N_0 - (\omega^1 x^1_1 + \omega^2 x^2_1 + \omega^N x^N_1)\ \ ,\ because\ of\ x_1\ on\ S,\ so\ \omega \cdot x_1 + b = 0\\
& = \omega^1 x^1_0 + \omega^2 x^2_0 + … + \omega^N x^N_0 - (-b) \\
& = \omega \cdot x_0 + b
\end{align}
$$
so, $\parallel \omega \parallel d = | \omega \cdot x_0 + b | $ , $ d = \frac{1}{\parallel \omega \parallel} | \omega \cdot x_0 + b | $
得证.

对于误分类的数据 $(x_i,\ y_i)$ 来说, 有 $ -y_i ( \omega \cdot x_i + b ) \geq 0 $ 因此, 误分类点 $x_i$ 到超平面 $S$ 的距离为 $ -\frac{1}{\parallel \omega \parallel} y_i ( \omega \cdot x_i + b ) $

则对于误分类集合 $M$ 来说, 所有误分类点到超平面 $S$ 的总距离为 :

$$ -\frac{1}{\parallel \omega \parallel} \sum_{x_i \in M}y_i( \omega \cdot x_i + b) $$

$-\frac{1}{\parallel \omega \parallel}$ 为常数, 不予考虑,则得到感知机学习的损失函数为 :

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

感知机学习问题就转化为求解损失函数的最优化问题, 最小化损失函数, 形式化的表示为 :

$$ \min_{\omega, b} L(\omega, b) = - \sum_{x_i \in M}y_i(\omega \cdot x_i + b) $$

感知机算法由误分类驱动, 采用随机梯度下降求解最优解, 梯度为分别对 $\omega, b$求偏导, 得到梯度为

$$ \nabla_{\omega}L(\omega, b) = - \sum_{x_i \in M} y_i x_i $$

$$ \nabla_{\omega}L(\omega, b) = - \sum_{x_i \in M} y_i $$

随机从集合 $M$ 中选取一个误分类点 $(x_i, y_i)$, 从梯度的相反方向对 $w, b$进行更新

$$ \omega \leftarrow \omega + \alpha y_i x_i $$

$$ b \leftarrow b + \alpha y_i$$

其中, $\alpha (0 \ < \alpha \leq 1)$ 为学习的步长, 可以通过交叉验证来选取一个合适的范围.

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

输入 : 训练数据集 $x_i \in \chi = \textbf{R}^n \ ,\ y_i \in Y = {+1,\ -1},\ i = 1, 2, …, N$ ; 学习步长 $\alpha (0 < \alpha \leq 1)$
输出 : $\omega, b$ , 感知机模型 $f(x) = sign(\omega \cdot x + b)$
Step 1 : 将 $w, b$的初始值设置为 : $w_0 = 0,\ b_0 = 0$
Step 2 : 选取训练集中的数据 $(x_i,\ y_i)$
Step 3 : if $y_i(\omega \cdot x_i + b) \leq 0$

$$\omega \leftarrow \omega+\alpha y_i x_i$$

$$b \leftarrow b + \alpha y_i$$

Step 4 : 转至 Step2, 直到不再有误分类点

收敛性 : 对于线性可分的数据集, 感知机学习算法的原始形式是收敛的. 由于水平有限, 在这里不予证明.

实验

采用 german 数据集进行实验. 链接是经过进一步处理的数据. 数据集的规模如下 :

Dataset	#样本数	#维数	#标签数
german	1,000	24	2

$\alpha$ 的值定为 $\alpha = 0.001$, 然后用1000个样本做10折交叉验证, 其结果如下 :

k-折	#precision	#recall	f1 score
1	0.80	0.16	0.27
2	0.32	1.0	0.48
3	0.23	1.0	0.37
4	0.28	1.0	0.44
5	0.28	1.0	0.44
6	0.41	1.0	0.58
7	0.30	1.0	0.46
8	0.32	1.0	0.48
9	0.29	1.0	0.45
10	0.32	1.0	0.48

代码是感知机算法原始形式的实现.