感知机模型(Perceptron)的收敛性解读 | 统计学习方法

作者: 舟晓南 | 来源:发表于2022-04-23 14:17 被阅读0次

Python复现，使用了随机梯度下降法，梯度下降法，adagrad和对偶形式四种算法：

舟晓南：感知机模型python复现 - 随机梯度下降法；梯度下降法；adagrad；对偶形式

在《统计学习方法》的感知机算法章节中，作者提出了一个问题，即如何证明一个线性可分的数据集，可以在有限次的迭代后得到这个分离超平面。我们称在有限次迭代后获得分离超平面的性质为感知机算法的收敛性。对于一个线性不可分的数据集，感知机模型将进入无法收敛的状态，即无法获得一个可以将所有实例正确分类的分离超平面，而是在迭代过程中进入震荡。

算法的收敛性：

感知机模型： $\\f(x)=\operatorname{sign}(w \cdot x+b)$

首先为了计算方便，将b并入权重向量w，记作 $\hat{w}=(\mathrm{w}， \mathrm{b})$ ，同样输入向量也需要相应地扩充，记作 $\hat{x}=(x， 1)$ 。

$\\\hat{w} \cdot \hat{x}=(\mathrm{w}， \mathrm{b}) \cdot(x， 1)=\mathrm{w} \cdot \mathrm{x}+\mathrm{b}$

证明1：

设训练集线性可分，那么存在超平面可将训练集完全正确分开，此超平面设为：

$\\\hat{w}_{\mathrm{opt}} \cdot \hat{x}=w_{\mathrm{opt}} \cdot x+b_{\mathrm{opt}}=0$

在我的另一篇关于感知机的文章：

舟晓南：统计学习方法 - 感知机模型解读 | 数据分析，机器学习，学习历程全记录

中提到作为函数间隔可以等比例放大缩小，因此这里为了方便可以将 $\hat{w}_{\mathrm{opt}}$ 放大缩小至 $\left\|\hat{w}_{\mathrm{opt}}\right\|=1$ 。

因为被正确分类的实例有：

$\\y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)>0$

且i有限（实例的数量有限），因此在 $y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)$ 中存在一个最小值，设此最小值为γ：

$\\\gamma=\min _{i}\left\{y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)\right\}$

那么对于所有实例来说，都有不等式（1）：

$\\y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right) \geqslant \gamma$

证明2：

因为感知机算法从初始权重向量 $\hat{w}_{0}=0$ 开始，可令 ${\hat{w}}_{k-1}$ 是第k个误分类实例之前的扩充权重向量，且(xi,yi)是被其误分类的样本点。

对于误分类的实例，满足：

$\\y_{i}\left(\hat{w}_{k-1} \cdot \hat{x}_{i}\right) \leqslant 0$

经过损失函数求导得到梯度后，w可进行更新：

$\\\hat{w}_{k}=\hat{w}_{k-1}+\eta y_{i} \hat{x_{i}}$

那么利用不等式（1）可得：

$\\\begin{aligned} \hat{w}_{k} \cdot \hat{w}_{\text {opt }}=\left(\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i}\right) \cdot & \hat{w}_{\text {opt }}=\hat{w}_{k-1} \cdot \hat{w}_{\text {opt }}+\eta y_{i} \hat{w}_{\text {opt }} \cdot \hat{x}_{i} \\ & \geqslant w_{k-1} \cdot \hat{w}_{\text {opt }}+\eta \gamma \end{aligned}$

由此可推得不等式（2）：

$\\\hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \geqslant \hat{w}_{k-1} \cdot \hat{w}_{\mathrm{opt}}+\eta \gamma \geqslant \hat{w}_{k-2} \cdot \hat{w}_{\mathrm{opt}}+2 \eta \gamma \geqslant \cdots \geqslant k \eta \gamma$

接着，因为实例有限，即i有限，我们可以定义 $R= \max \left\|\hat{x}_{i}\right\|$ ，在此基础上计算 $\left\|\hat{w}_{k}\right\|^{2}$ ：

$\\\left\|\hat{w}_{k}\right\|^{2}=\hat{w}_{k} \cdot \hat{w}_{k}=\left(\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i}\right)^{2}=\left\|\hat{w}_{k-1}\right\|^{2}+2 \eta y_{i} \hat{w}_{k-1} \cdot \hat{x}_{i}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2}$

因为(xi, yi)是误分类项，所以 $y_{i} \hat{w}_{k-1} \cdot \hat{x}_{i}$ 为负，且 $\eta \in(0，1]$ ，所以可推得不等式（3）：

$\\\left\|\hat{w}_{k}\right\|^{2} \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2} \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2} R^{2} \leqslant\left\|\hat{w}_{k-2}\right\|^{2}+2 \eta^{2} R^{2} \leqslant \cdots \leqslant k \eta^{2} R^{2}$

结合不等式（2）和不等式（3），及 $\left\|\hat{w}_{opt}\right\|=1$ 的前提条件，可得：

$\\ k \eta \gamma \leqslant \hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \leqslant\left\|\hat{w}_{k}\right\|\left\|\hat{w}_{\mathrm{opt}}\right\| =\left\|\hat{w}_{k}\right\|= \sqrt{k} \eta R$