《统计学习方法》第二章：感知机

模型

定义

感知机是二分类的线性分类模型，感知机定义为

$$f(x)=\mathrm{sign}(w\cdot x+b)$$

$$\begin{equation} \mathrm{sign}(x)= \begin{cases} +1, &x\geqslant 0\\ -1, &x<0 \end{cases} \end{equation}$$

其中输入 $x\in \mathbf{R}^n$ 表示实例的特征向量，输出 $y\in \{+1,-1\}$表示实例的类别。模型参数 $w$ 称为权值，参数 $b$ 称为偏置。

几何模型

若 $x\in \mathbf{R}^2$,

$$\begin{align} w\cdot x+b&=0\\ (w^{(1)},w^{(2)})^\mathrm{T}\cdot (x^{(1)},x^{(2)})^\mathrm{T}+b&=0\\ \end{align}$$

该形式满足平面中的直线方程：

$$\begin{align} (i,j)^\mathrm{T}\cdot (x^{(1)},x^{(2)})^\mathrm{T}+b&=0\\ ix^{(1)}+jx^{(2)}+b&=0 \end{align}$$

其中 $w=(i,j)^\mathrm{T}$ 为直线法向量。

类似地，当 $x\in \mathbf{R}^3$ 时，感知机模型满足空间中的平面方程：

$$ix^{(1)}+jx^{(2)}+kx^{(3)}+b=0$$

且 $w=(i,j,k)^\mathrm{T}$ 为平面法向量。

因此，感知机在模型本质上是在特征空间 $\mathbf{R}^n$ 中的一个超平面 $S$，代表特征向量的点被超平面 $S$ 分隔成两部分，其中参数 $w$ 为超平面法向量。

感知机的几何模型

超平面 $S$ 也应符合 $\mathbf{R}^n$ 空间中的几何关系，所以在 $\mathbf{R}^n$ 空间中的任意一点 $x_0$ 到超平面的距离为

$$d=\frac{1}{||w||}|w\cdot x_0+b|$$

$||w||$ 是 $w$ 的 $L_2$ 范数：

$$||w||=\sqrt{\sum(w_i)^2}$$

即法向量长度。

点到超平面距离

以 $x\in \mathbf{R}^2$ 为例，将超平面 $S$ 方程转化为截距式：

$$\begin{align} ix^{(1)}+jx^{(2)}+b&=0\\ \frac{x^{(1)}}{-\frac{b}{i}}+\frac{x^{(2)}}{-\frac{b}{j}}&=1 \end{align}$$

超平面 $S$ 在 $x^{(2)}$ 轴上的截距就为 $-\frac{b}{j}$。过点 $x_0$ 作平行于 $S$ 的超平面 $S_0$，同样得到截距式：

$$\frac{x^{(1)}}{-\frac{b_0}{i}}+\frac{x^{(2)}}{-\frac{b_0}{j}}=1$$

超平面 $S_0$ 在 $x^{(2)}$ 轴上的截距为 $-\frac{b_0}{j}$。

示意图

将 $d$ 平移至蓝色三角形中，$\boldsymbol{w}$ 是超平面的法向量，$\boldsymbol{w}=w=(i,j)^\mathrm{T}$，根据向量夹角余弦公式

$$\begin{align} \cos\theta&=|\cos(\boldsymbol{w},\boldsymbol{j})|\\ &=\frac{|\boldsymbol{w}\cdot\boldsymbol{j}|}{|\boldsymbol{w}||\boldsymbol{j}|} \end{align}$$

$\boldsymbol{j}$ 为 $x^{(2)}$ 方向的单位向量，因此有

$$\begin{align} \cos\theta&=\frac{|(i,j)^\mathrm{T}\cdot(0,1)^\mathrm{T}|}{|\boldsymbol{w}|}\\ &=\frac{|j|}{|\boldsymbol{w}|} \end{align}$$

在蓝色三角形中，

$$\begin{align} d&=\left|\frac{b}{j}-\frac{b_0}{j}\right|\cos\theta\\ &=\frac{|b-b_0|}{|j|}\frac{|j|}{|\boldsymbol{w}|}\\ &=\frac{|b-b_0|}{|\boldsymbol{w}|}\\ \end{align}$$

由 $w\cdot x_0+b_0=0$ 得到 $b_0=-w\cdot x_0$，代入就可以证得

$$d=\frac{|w\cdot x_0+b|}{||w||}$$

策略

感知机的分类情况可以归为以下几类：

$w\cdot x_i+b\geqslant0$,$\ y_i=+1$，分类正确；
$w\cdot x_i+b\geqslant0$,$\ y_i=-1$，分类错误；
$w\cdot x_i+b<0$,$\ y_i=-1$，分类正确；
$w\cdot x_i+b<0$,$\ y_i=+1$，分类错误。

因此分类错误的数据点 $(x_i,y_i)$ 满足

$$-y_i(w\cdot x_i+b)>0$$

若超平面 $S$ 误分类的点的集合为 $M$，那么误分类点到超平面的距离之和为

$$\sum_{x_i\in M}\left[-\frac{1}{||w||}y_i(w\cdot x_i+b)\right]$$

略去 $\frac{1}{||w||}$（见第七章），得到经验风险函数：

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

感知机的学习策略就是在假设空间中选取 $L(w,b)$ 最小的模型参数 $w$ 和 $b$。

算法

Code Here.

感知机的学习算法就是求解以下最优化问题的算法：

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

随机梯度下降法

任意选取超平面 $w_0\cdot x+b_0=0$;
随机选取误分类点使 $L(w,b)$ 梯度下降；
不断更新 $w$ 与 $b$，直至 $L(w,b)=0$。

二元函数 $f(x,y)$ 在 $(x_0,y_0)$ 处的梯度定义为

$$\mathbf{grad}\ f(x_0,y_0)=\nabla f(x_0,y_0)=f_x(x_0,y_0)\boldsymbol{i}+f_y(x_0,y_0)\boldsymbol{j}$$

因此损失函数 $L(w,b)$ 的梯度为

$$\nabla_wL(w,b)=\frac{\partial\left[-\sum_{x_i\in M}\color{orangered}{y_i}(w\cdot \color{orangered}{x_i}+b)\right]}{\partial w}=-\sum_{x_i\in M}\color{orangered}{y_ix_i}$$

$$\nabla_bL(w,b)=\frac{\partial\left[-\sum_{x_i\in M}\color{orangered}{y_i}(w\cdot x_i+b)\right]}{\partial b}=-\sum_{x_i\in M}\color{orangered}{y_i}$$

随机选择误分类点 $(x_i,y_i)$ 更新 $w$ 与 $b$，使 $L(w,b)$ 沿梯度方向下降：

$$w\leftarrow w+\eta y_ix_i$$

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

其中 $\eta\ (0<\eta\leqslant1)$ 称为步长，不断迭代至 $L(w,b)=0$。

原始形式算法

算法2.1

输入：训练集 $T$，学习率 $\eta$
输出：$w$ 与 $b$ ，感知机模型 $f(x)=\mathrm{sign}(w\cdot x+b)$

设定步长 $\eta$，选取初值 $w_0$ 与 $b_0$，一般为 $w_0=0$，$b_0=0$；
选取点 $(x_i,y_i)$；
若 $y_i(w\cdot x_i+b)\leqslant0$，
$$w\leftarrow w+\eta y_ix_i$$

$$b\leftarrow b+\eta y_i$$
重复步骤（2），直至没有误分类点，即 $L(w,b)=0$。

对偶形式算法

经过数次以下迭代步骤：

$$w\leftarrow w+\eta y_ix_i$$

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

最终的 $w$ 和 $b$ 可以表示为

$$w=\sum_{i=1}^N \alpha_iy_ix_i$$

$$b=\sum_{i=1}^N\alpha_iy_i$$

其中 $\alpha_i=n_i\eta$，$n_i$ 表示点 $(x_i,y_i)$ 被误分类的次数。也就是说，在迭代的每一次过程中，被误分类的点 $(x_i,y_i)$ 都不断向超平面靠近，直至位于超平面的另一侧。

最后得到的感知机模型应为

$$f(x)=\mathrm{sign}\left(\sum_{i=1}^N\alpha_iy_ix_i\cdot x+b\right)$$

为了与 $x=x_i$ 代入后的模型相区别，表示为

$$f(x)=\mathrm{sign}\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\right)$$

算法2.2

输入：训练集 $T$，学习率 $\eta$
输出：$\alpha$ 与 $b$ ，感知机模型 $f(x)=\mathrm{sign}\left(\sum_{j=1}^N\alpha_iy_jx_j\cdot x+b\right)$

设定步长 $\eta$，选取初值 $\alpha$ 与 $b_0$，一般为 $\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^\mathrm{T}=0$，$b_0=0$；
选取点 $(x_i,y_i)$；
若$y_i\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b\right)\leqslant0$，
$$\alpha_i\leftarrow\alpha_i+\eta$$

$$b\leftarrow b+\eta y_i$$
重复步骤 2，直至没有误分类点。

考虑迭代的判断条件

$$y_i\left(\sum_{j=1}^N\alpha_jy_j\vec{x_j}\cdot \vec{x_i}+b\right)\leqslant0$$

每次判断都需要计算

$$\sum_{j=1}^N\alpha_jy_j\color{orangered}{\vec{x_j}\cdot \vec{x_i}}=\alpha_1y_1\color{orangered}{\vec{x_1}\cdot\vec{x_i}}+\alpha_2y_2\color{orangered}{\vec{x_2}\cdot\vec{x_i}}+\cdots+\alpha_Ny_N\color{orangered}{\vec{x_N}\cdot\vec{x_i}}$$

因此可以将内积以矩阵形式存放，即 Gram 矩阵：

$$\boldsymbol{G}=[x_i\cdot x_j]_{N\times N}=\begin{bmatrix} x_1\cdot x_1 &\cdots &x_1\cdot x_N\\ \vdots &\ddots &\vdots\\ x_N\cdot x_1 &\cdots &x_N\cdot x_N \end{bmatrix}$$

由于内积的性质，Gram 矩阵实际上是一个对称矩阵。

References

李航, 2019. 统计学习方法（第2版）. 清华大学出版社.