算法收敛证明

① 感知机算法及收敛性证明

感知机算法其实已经很熟悉了，这次看《统计学习方法》权当复习一遍，然后有一橘念个point对我来说是新的—— 感知机算法实际上采用了随机梯度下降 。这其实是一个很显然的点，但我之前看到的资料都是直接说明了超平面参数的更新方式，并从几何直观上解释了这样做是为了让超平面向误分样本点的方向旋转，而未从梯度的角度来解释，这里补充一下这个角度。

感知机（perceptron）是二分类线性分类模型，其输入空间（特征空间）是 ，输出空间是 ，前伍简由输入空间到输出空间的如下函数：

称为感知机。 和 分别是感知机的权值和偏置。

感知机的损失函数定义为 所有误分类点到超平面的距离慧裤之和 ，即：

其中 表示误分类点的集合，若 固定，则损失函数梯度为：

采用随机梯度下降法，每次随机选取一个误分类点 ，对 进行更新：

其中 称为学习率。

感知机算法流程如下：

（1）选取初值 。
（2）在训练集中选取数据 。
（3）如果 ,则更新参数：

（4）转至（2）直至训练集中无误分点。

所谓感知机算法的收敛性，就是说只要给定而分类问题是线性可分的，那么按上述感知机算法进行操作，在有限次迭代后一定可以找到一个可将样本完全分类正确的超平面。

首先，为了方便推导，我们将偏置 并入权重向量 ,记作 ，同样将输入向量加以扩充，记作 ，显然， 。

既然样本是线性可分的，我们可以假设有一个满足条件 的超平面 将样本点完全正确分开，且存在 ，对所有 ，有：

令 ，则感知机算法在训练集上误分类次数 满足：

证明：

结合上述两个结论，可以得到：

从而感知机算法的收敛性得证。

② 感知机的收敛性

感知机是最基础的机器学习模型之一，它的类别为：

该模型本质上是雹丛嫌在输入空间定义了一个分离超平面： ， 为该超平面的法向量， 为该超平面的截距。该超平面将输入空间划分为两部分，位于两侧的点（输入数据）分别属于正负两类。
给定一个线性可分的训练样本集，通过寻找合适的 和 使得训练样本集的数据被正确划分到超平面的两侧，该过程即感知机模型的训练过程。
这里有一个前提“训练样本集线性可分”，即对于训练样本集： ，其中， ，若存在某超平面 ，使得 ，则称 为线性可分数据集。

为了寻找能正确划分训练样本集的超平面，需要定义损失函数，并将损失函数极小化。如何度量损失呢？如下图所示，有A、B、C三点，表示三个样本，都在分离超平面的正侧，距离分离超平面的距离依次减小。距离越远，预测为正类的确信度越大，反之则不那么确信。

在超平面 确定的情况下， 能够相对地表示点 距离超平面的远近，而 的符号与类标记 的符号是否一致能够表示分类是否正确。所以可以用 来表示分类的正确性与确信度，这就是函数间隔（functional margin）的概念。
设 为 上被超平面 误分类的所有点的集合，则
按照机器学习约定俗成的惯例，损失函数为正，对损失函数求极小值。因此，我们将感知机的损失函数定义为 上所有被误分类的点到超平面 的函数间隔的绝对值，即：
感知机的学习策略是在假设空间中选取使上式最小的分离超平面系数 和 。

感知机的学习问题可转化为求解使损失函数最小的最优化问题，即求参数 ，使其为以下极小化问题的解。
其中，M为误分类点的集合。求解该问题可使用梯度下降算法。
损失函数 的梯度为：

如果样本集非常大，梯度下降算法每轮迭代都要计算全局梯度，这需要耗费非常大的计算资源，实际应用中通常使用随机梯度下降算法代替，即每次随机选取一个误分类点 ，对 沿梯度负方向更新。

其中 为步长，又叫做学习率。随机梯度的期望为全局梯度，因此其收敛性与梯度下降算法一致。通过不断迭代以上步骤，可以期待损失函数 不断减小，直到为0.
该算法的直观理解为：当一个实例点被误分类，调整 的值，使分离超郑肆平面向该误分类点移动，减小该误分类点与超平面的距离，直至超平面越过该点，使其被正确分类。
该算法在训练开始时需要选取一个初始分类超平面 ，经过 轮迭代后：

其中， 为第 轮迭代时随机选取的误分类点。当 时，第 轮迭代时的超平面方程为：

可以看出，学习速率 可以被约去，说明当 时，算法收敛速度与 无关。下面证明感知机训练算法收敛性，证明过程可进一步验证该结论。

证明感知机训练算法是收敛的，即证明训练过程可在有限轮迭代内完成，即迭代次数 存在一个上界。
为了便于叙述，将偏置 并入权重向量 ，记作 ，同时对输入向量 进行扩充，记作 ，显然 。

证明：
训练数据集线性可分，则存在能将数据集完全正确分开的分离超平面，对任一满足源手要求的分离超平面 ，存在 ，对所有 ：

初始时， ，随机选取某样本，若被误分类，则更新权重。令 是第 次迭代时的扩充权重向量，此次迭代随机选择的第 个误分类样本满足条件：

迭代时进行如下更新：

联合(2)(4)式，有：

联合(3)(4)式，有：

联合(5)(6)式，有：

定理得证。
从(7)式可知，迭代次数 存在上界，这说明当训练数据集线性可分时，感知机学习算法是收敛的。
进一步地，通过调整 可以改变 的取值。算法经过 次迭代结束后得到分离超平面 ，由(1)式可知， ，令 ，则可使得 ，从而得到感知机迭代次数收敛上界的精简形式：