统计学习方法（第2版）最新章节_李航著

2.3　感知机学习算法

感知机学习问题转化为求解损失函数式（2.4）的最优化问题，最优化的方法是随机梯度下降法。本节叙述感知机学习的具体算法，包括原始形式和对偶形式，并证明在训练数据线性可分条件下感知机学习算法的收敛性。

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

感知机学习算法是对以下最优化问题的算法。给定一个训练数据集

其中， x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,1}， i =1,2,…, N ，求参数 w ， b ，使其为以下损失函数极小化问题的解

其中 M 为误分类点的集合。

感知机学习算法是误分类驱动的，具体采用随机梯度下降法（stochastic gradient descent）。首先，任意选取一个超平面 w ₀ , b ₀ ，然后用梯度下降法不断地极小化目标函数（2.5）。极小化过程中不是一次使 M 中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合 M 是固定的，那么损失函数 L （ w , b ）的梯度由

给出。

随机选取一个误分类点（ x _i , y _i ），对 w , b 进行更新：

式中 η （0< η ≤1）是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数 L （ w , b ）不断减小，直到为0。综上所述，得到如下算法：

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

输入：训练数据集 T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}，其中 x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,+1}， i =1,2,…, N ；学习率 η （0< η ≤1）；

输出： w ， b ；感知机模型 f （ x ）=sign（ w · x + b ）。

（1）选取初值 w ₀ , b ₀ ；

（2）在训练集中选取数据（ x _i , y _i ）；

（3）如果 y _i （ w · x _i + b ）≤0，

（4）转至（2），直至训练集中没有误分类点。

这种学习算法直观上有如下解释：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整 w ， b 的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。

算法2.1是感知机学习的基本算法，对应于后面的对偶形式，称为原始形式。感知机学习算法简单且易于实现。

例2.1 如图2.2所示的训练数据集，其正实例点是 x ₁ =（3,3） ^T ， x ₂ =（4,3） ^T ，负实例点是 x ₃ =（1,1） ^T ，试用感知机学习算法的原始形式求感知机模型 f （ x ）=sign（ w · x + b ）。这里， w =（ w ⁽¹⁾ , w ⁽²⁾ ） ^T ， x =（ x ⁽¹⁾ , x ⁽²⁾ ） ^T 。

图2.2　感知机示例

解构建最优化问题：

按照算法2.1求解 w ， b 。 η =1。

（1）取初值 w ₀ =0， b ₀ =0

（2）对 x ₁ =（3,3） ^T ， y ₁ （ w ₀ · x ₁ + b ₀ ）=0，未能被正确分类，更新 w , b

得到线性模型

（3）对 x ₁ , x ₂ ，显然， y _i （ w ₁ · x _i + b ₁ ）>0，被正确分类，不修改 w , b ；

对 x ₃ =（1,1） ^T ， y ₃ （ w ₁ · x ₃ + b ₁ ）<0，被误分类，更新 w , b 。

得到线性模型

如此继续下去，直到

对所有数据点 y _i （ w ₇ · x _i + b ₇ ）>0，没有误分类点，损失函数达到极小。

分离超平面为： x ⁽¹⁾ + x ⁽²⁾ −3=0

感知机模型为： f （ x ）=sign（ x ⁽¹⁾ + x ⁽²⁾ −3）

迭代过程见表2.1。

表2.1　例2.1求解的迭代过程

这是在计算中误分类点先后取 x ₁ ， x ₃ ， x ₃ ， x ₃ ， x ₁ ， x ₃ ， x ₃ 得到的分离超平面和感知机模型。如果在计算中误分类点依次取 x ₁ ， x ₃ ， x ₃ ， x ₃ ， x ₂ ， x ₃ ， x ₃ ， x ₃ ， x ₁ ， x ₃ ， x ₃ ，那么得到的分离超平面是2 x ⁽¹⁾ + x ⁽²⁾ −5=0。

可见，感知机学习算法由于采用不同的初值或选取不同的误分类点，解可以不同。

2.3.2　算法的收敛性

现在证明，对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。

为了便于叙述与推导，将偏置 b 并入权重向量 w ，记作，同样也将输入向量加以扩充，加进常数1，记作。这样，，。显然，。

定理2.1（Novikoff） 设训练数据集 T ={（ x ₁ , y ₁ ）,（ x ₂ , y ₂ ）,…,（ x _N , y _N ）}是线性可分的，其中 x _i ∈ X = R ⁿ ， y _i ∈ Y ={−1,+1}， i =1,2,…, N ，则

（1）存在满足条件的超平面将训练数据集完全正确分开；且存在 γ >0，对所有 i =1,2,…, N

（2）令，则感知机算法2.1在训练数据集上的误分类次数 k 满足不等式

证明（1）由于训练数据集是线性可分的，按照定义2.2，存在超平面可将训练数据集完全正确分开，取此超平面为，使。由于对有限的 i =1,2,…, N ，均有

所以存在

使

（2）感知机算法从开始，如果实例被误分类，则更新权重。令是第 k 个误分类实例之前的扩充权重向量，即

则第 k 个误分类实例的条件是

若（ x _i , y _i ）是被误分类的数据，则 w 和 b 的更新是

即

下面推导两个不等式（2.12）及（2.13）：

由式（2.11）及式（2.8）得

由此递推即得不等式（2.12）

由式（2.11）及式（2.10）得

结合不等式（2.12）及式（2.13）即得

于是

定理表明，误分类的次数 k 是有上界的，经过有限次搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是例2.1说明，感知机学习算法存在许多解，这些解既依赖于初值的选择，也依赖于迭代过程中误分类点的选择顺序。为了得到唯一的超平面，需要对分离超平面增加约束条件。这就是第7章将要讲述的线性支持向量机的想法。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

2.3.3　感知机学习算法的对偶形式

现在考虑感知机学习算法的对偶形式。感知机学习算法的原始形式和对偶形式与第7章中支持向量机学习算法的原始形式和对偶形式相对应。

对偶形式的基本想法是，将 w 和 b 表示为实例 x _i 和标记 y _i 的线性组合的形式，通过求解其系数而求得 w 和 b 。不失一般性，在算法2.1中可假设初始值 w ₀ , b ₀ 均为0。对误分类点（ x _i , y _i ）通过

逐步修改 w ， b ，设修改 n 次，则 w ， b 关于（ x _i , y _i ）的增量分别是 α _i y _i x _i 和 α _i y _i ，这里 α _i = n _i η,n _i 是点（ x _i , y _i ）被误分类的次数。这样，从学习过程不难看出，最后学习到的 w , b 可以分别表示为