单层感知机的学习

【原始形式与对偶形式】

对于感知机模型 $f(\mathbf{x})=\text{sign}(\boldsymbol{\omega}\cdot \mathbf{x}+\theta)$，其损失函数为：

$$L(\boldsymbol{\omega},\theta)=-\sum_{j=1}^M y_j (\boldsymbol{\omega}\cdot\mathbf{x}_j+\theta)$$

这时感知机学习问题就转换为求解损失函数的最优化问题，即：

$$\boldsymbol{\omega}^*,\theta^* = \arg \min_{\boldsymbol{\omega},\theta}L(\boldsymbol{\omega},\theta)$$

对于上述的损失函数极小化问题，感知机学习算法一般选用随机梯度下降法进行求解，存在两种方法：原始形式、对偶形式

【原始形式】

开始时，随机选取一个超平面 $\boldsymbol{\omega}_0,\theta_0$，一般取 $\boldsymbol{\omega}_0=0,\theta_0=0$ 然后用梯度下降法不断地极小化损失函数，极小化过程中，每次随机选取一个误分类点使其梯度下降

假设误分类点集合 $M$ 是固定的，那么损失函数 $L(\boldsymbol{\omega},\theta)$ 的梯度由以下公式给出：

$$\left\{\begin{array}{rl} \triangledown_{\boldsymbol{\omega}}L(\boldsymbol{\omega},\theta) &=& -\sum\limits_{j=1}^M y_j\mathbf{x}_j \\ \triangledown_{\theta}L(\boldsymbol{\omega},\theta) &=& -\sum\limits_{j=1}^M y_j \end{array} \right.$$

在误分类点集合 $E$ 中，随机选取一个误分类点 $(\mathbf{x}_j,y_j)$，对 $\boldsymbol{\omega}$ 和 $\theta$ 进行更新，有：

$$\left\{\begin{array}{rl} \boldsymbol{\omega}' &=& \boldsymbol{\omega} + \alpha y_j\mathbf{x}_j \\ \theta' &=& \theta + \alpha y_j \end{array} \right.$$

其中，$0<\alpha\leq1$ 为学习率

这样，通过上述的更新公式，可以不断迭代以使损失函数 $L(\boldsymbol{\omega},\theta)$ 不断减小，直到为 $0$

也就是说，当一个样本点被误分类，即位于分离超平面的错误一侧时，就调整 $\boldsymbol{\omega}$ 与 $\theta$ 的值，使超平面向该误分类点一侧移动，以减少该误分类点与超平面的距离，直到超平面越过该误分类点使其被正确分类

---

下面给出感知机学习算法的原始形式算法流程

输入：训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $n$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^n$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$，学习率 $0<\alpha\leq1$

输出：参数 $\boldsymbol{\omega}$，阈值 $\theta$，感知机模型 $f(\mathbf{x})=\text{sign}(\boldsymbol{\omega}\cdot\mathbf{x}+\theta)$

算法步骤：

1. 随机选取参数与阈值的初值 $\boldsymbol{\omega}_0,\theta_0$
2. 在训练集中随机选取样本 $(\mathbf{x}_i,y_i)$
3. 若 $y_i(\boldsymbol{\omega}\cdot\mathbf{x}_i+\theta)\leq 0$，更新 $\boldsymbol{\omega}$ 与 $\theta$

$$\left\{\begin{array}{rl} \boldsymbol{\omega} &=& \boldsymbol{\omega} + \alpha y_i\mathbf{x}_i \\ \theta &=& \theta + \alpha y_i \end{array} \right.$$

1. 转至步骤 2，直到训练集中没有误分类点

【对偶形式】

对偶形式的基本想法是：将参数 $\boldsymbol{\omega}$ 和阈值 $\theta$ 表示为样本特征 $\mathbf{x}_i$ 和样本类别 $y_i$ 的线性组合形式，通过求解其系数来求得 $\boldsymbol{\omega}$ 和 $\theta$

不失一般性，假设原始形式的初值均为 $0$，即：

$$\boldsymbol{\omega}_0=0,\theta_0=0$$

对于误分点 $(\mathbf{x}_i,y_i)$，通过以下迭代公式对 $\boldsymbol{\omega}$ 和 $\theta$ 进行修改

$$\left\{\begin{array}{rl} \boldsymbol{\omega} &=& \boldsymbol{\omega}+\alpha y_i\mathbf{x}_i \\ \theta &=& \theta+\alpha y_i \end{array} \right.$$

假设修改 $n$ 次，则 $\boldsymbol{\omega}$ 和 $\theta$ 关于 $(\mathbf{x}_i,y_i)$ 的增量分别是 $n_i\alpha y_i\mathbf{x}_i$ 与 $n_i\alpha y_i$，那么，最后学习到的 $\boldsymbol{\omega}$ 和 $\theta$ 可以表示为：

$$\left\{\begin{array}{rl} \boldsymbol{\omega} &=& \sum\limits_{i=1}^N n_i\alpha y_i\mathbf{x}_i \\ \theta &=& \sum\limits_{i=1}^N n_i\alpha y_i \end{array} \right.$$

当 $\alpha=1$ 时，$\boldsymbol{\omega}$ 和 $\theta$ 被表示第 $i$ 个样本点由于误分类而进行更新的次数

更新次数越多，意味着样本点距离超平面越近，也就越难被分类

---

下面给出感知机学习算法的对偶形式算法流程

输入：线性可分训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $n$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^n$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$，学习率 $0<\alpha\leq1$

输出：参数 $\boldsymbol{\eta}=\alpha(n_1,n_2,\cdots,n_N)^T$，阈值 $\theta$，感知机模型 $f(\mathbf{x})=\text{sign} \big( (\sum\limits_{i=1}^N \eta_i y_i\mathbf{x}_i) \cdot\mathbf{x}+\theta \big)$

算法步骤：

1. 选取增量与阈值的初值 $\boldsymbol{\eta}_0,\theta_0$，取 $\boldsymbol{\eta}_0=0,\theta_0=0$
2. 在训练集中随机选取样本 $(\mathbf{x}_i,y_i)$
3. 若 $y_i \big( (\sum\limits_{j=1}^N\eta_j y_j\mathbf{x}_j)\cdot\mathbf{x}_i+\theta \big) \leq 0$，更新 $\eta_i$ 与 $\theta$

$$\left\{\begin{array}{rl} \eta_j &=& \eta_j + \alpha \\ \theta &=& \theta + \alpha y_i \end{array} \right.$$

1. 转至步骤 2，直到训练集中没有误分类点

由于对偶形式中训练样本仅以内积的形式出现，为处理方便，通常预先将训练集中样本间的内积计算出来并以矩阵的形式存储，这个矩阵是一个半正定矩阵，被称为格拉姆矩阵（Gram Matrix），即：

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

【时间复杂度】

原始形式与对偶形式则两种方法在寻找误分类样本点的过程是一样的，只是在找到一个误分点时两者后续的参数更新方法不同，这就导致了两者的时间复杂度不同

对于样本数量为 $N$，特征数量为 $n$ 的训练集，两者时间复杂度如下：

• 原始形式：每次计算 $\boldsymbol{\omega}\cdot\mathbf{x}$，计算该内积的复杂度为 $O(n)$

• 对偶形式：提前将 $\mathbf{x}_i$ 与 $\mathbf{x}_j$ 的内积存储在 Gram 矩阵中，因此只需要扫描一遍数据集，找到一个误分点后直接加上，时间复杂度为 $O(N)$

  因此，选择哪种计算方法取决于训练集的样本数量和特征数量的大小