感知机（三）| 算法原始形式和对偶形式+算法收敛性 | 《统计学习方法》学习笔记（十一）

感知机学习算法

感知机学习问题转化为求解损失函数式(2)的最优化问题，最优化的方法是随机梯度下降法。

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

给定一个训练数据集
$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}
其中，$x_i\in \chi=R^n,y\in \gamma=\{-1,1\}, \space i=1,2,...,N$xi​∈χ=Rn,y∈γ={−1,1}, i=1,2,...,N,求参数$w,b$w,b，使其为以下损失函数极小问题的解：
$min_{w,b}L(w,b)=-\sum_{x_i\in M}y_i（w·x_i+b）\tag{3}$minw,b​L(w,b)=−xi​∈M∑​yi​（w⋅xi​+b）(3)
其中M为误分类点的集合。

感知机学习算法是误分类驱动的，采用随机梯度下降法（stochastic gradient descent）。

首先，任意选取一个超平面$w_0,b_0$w0​,b0​，然后用梯度下降法不断地极小化目标函数（3）。极小化过程中不是一次使M中所有误分类点的梯度下降，而是一次随机选取一个误分类点使其梯度下降。

假设误分类点集合M是固定的，那么损失函数$L(w,b)$L(w,b)的梯度为：
$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i \\ \nabla_bL(w,b)=-\sum_{x_i\in M}y_i$∇w​L(w,b)=−xi​∈M∑​yi​xi​∇b​L(w,b)=−xi​∈M∑​yi​
随机选取一个误分类点$(x_i,y_i)$(xi​,yi​)，对$w,b$w,b进行更新：
$w + \eta y_ix_i \to w \\ b + \eta y_i \to b$w+ηyi​xi​→wb+ηyi​→b
其中，$\eta(0<\eta\leq 1)$η(0<η≤1)是步长，在统计学习中又称为学习率（learning rate）。这样，通过迭代可以期待损失函数$L(w,b)$L(w,b)不断减小，知道为0。综上所述，得到如下算法：

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

输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)},其中，$x_i\in \chi=R^n,y\in \gamma=\{-1,1\}, \space i=1,2,...,N$xi​∈χ=Rn,y∈γ={−1,1}, i=1,2,...,N；学习率$\eta(0<\eta\leq 1)$η(0<η≤1)；

输出：$w,b$w,b；感知机模型$f(x)=sign(w·x+b)$f(x)=sign(w⋅x+b)

（1）选取初值$w_0,b_0$w0​,b0​

（2）在训练集中选取数据$(x_i,y_i)$(xi​,yi​)

（3）如果$y_i(w·x_i+b)\leq 0$yi​(w⋅xi​+b)≤0
$w + \eta y_ix_i \to w \\ b + \eta y_i \to b$w+ηyi​xi​→wb+ηyi​→b
（4）转至（2），直至训练集中没有误分类点。

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

例如：训练数据集，其正实例点是$x_1=(3,3)^T$x1​=(3,3)T，$x_2=(4,3)^T$x2​=(4,3)T，负实例点是$x_3=(1,1)^T$x3​=(1,1)T，试用感知机学习算法的原始形式求感知机模型$f(x)=sign(w·x+b)$f(x)=sign(w⋅x+b)。这里，$w=(w^{(1)},w^{(2)})^T,x=(x^{(1)},x^{(2)})^T$w=(w(1),w(2))T,x=(x(1),x(2))T。

解：构建最优化问题：
$min_{w,b}L(w,b)=-\sum_{x_i\in M}y_i(w·x+b)$minw,b​L(w,b)=−xi​∈M∑​yi​(w⋅x+b)
按照感知机模型求解$w,b$w,b。$\eta=1$η=1。

（1）取初值$w_0=0,b_0=0$w0​=0,b0​=0

（2）对$x_1=(3,3)^T,y_1(w_0·x_1+b)=0$x1​=(3,3)T,y1​(w0​⋅x1​+b)=0，未能被正确分类，更新$w, b$w,b
$w_1=w_0+\eta y_1x_1=(3,3)^T,\quad b_1=b_0+\eta y_1=1$w1​=w0​+ηy1​x1​=(3,3)T,b1​=b0​+ηy1​=1
得到线性模型
$w_1·x+b_1=3x^{(1)}+3x^{(2)}+1$w1​⋅x+b1​=3x(1)+3x(2)+1
（3）对$x_1,x_2$x1​,x2​，显然，$y_i(w_1·x_i+b_i)>0$yi​(w1​⋅xi​+bi​)>0，被正确分类，不修改$w,b$w,b；

对$x_3=(1,1)^T$x3​=(1,1)T，$y_3(w_1·x_3+b_1)<0$y3​(w1​⋅x3​+b1​)<0，被误分类，更新$w,b$w,b。
$w_2 = w_1+y_3x_3=(2,2)^T,\quad b_2=b_1+y_3=0$w2​=w1​+y3​x3​=(2,2)T,b2​=b1​+y3​=0
得到线性模型
$w_2·x+b_2=2x^{(1)}+2x^{(2)}$w2​⋅x+b2​=2x(1)+2x(2)
如此继续下去，直到
$w_7=(1,1)^T, \quad b_7=-3 \\ w_7·x+ b_7 = x^{(1)}+x^{(2)}-3$w7​=(1,1)T,b7​=−3w7​⋅x+b7​=x(1)+x(2)−3
对所有数据点$y_i(w_7x_i+b_7)>0$yi​(w7​xi​+b7​)>0，没有误分类点，损失函数达到极小。

分离超平面的为
$x^{(1)}+x^{(2)}-3=0$x(1)+x(2)−3=0
感知机模型为
$f(x)=sign(x^{(1)}+x^{(2)}-3)$f(x)=sign(x(1)+x(2)−3)

这是在计算中误分类点先后取$x_1,x_3,x_3,x_3,x_1,x_3,x_3$x1​,x3​,x3​,x3​,x1​,x3​,x3​得到的分离超平面和感知机模型。如果在计算中误分类点依次取$x_1,x_3,x_3,x_3,x_2,x_3,x_3,x_3,x_1,x_3,x_3$x1​,x3​,x3​,x3​,x2​,x3​,x3​,x3​,x1​,x3​,x3​,那么得到的分离超平面是$2x^{(1)}+x^{(2)}-5=0$2x(1)+x(2)−5=0。

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

二、 算法的收敛性

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

为了便于叙述与推导，将偏置b并入权重向量w，记作$\hat w=(w^T,b)^T$w^=(wT,b)T，同样也将输入向量加以扩充，加进常数1，记作$\hat x=(x^T,1)^T$x^=(xT,1)T。这样，$\hat x\in R^{n+1},\hat w\in R^{n+1}$x^∈Rn+1,w^∈Rn+1。显然，$\hat w · \hat x=w·x+b$w^⋅x^=w⋅x+b。

**定理 （Novikoff）：**设训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}是线性可分的，其中$x_i\in \chi=R^n, \space y_i\in \gamma =\{-1,+1\}, \space i=1,2,...,N$xi​∈χ=Rn, yi​∈γ={−1,+1}, i=1,2,...,N，则

（1）存在满足条件$||\hat w_{opt}||=1$∣∣w^opt​∣∣=1的超平面$\hat w_{opt}·\hat x=w_{opt}·x+b_{opt}=0$w^opt​⋅x^=wopt​⋅x+bopt​=0将训练数据集完全正确分开；且存在$\gamma >0$γ>0，对所有$i=1,2,...,N$i=1,2,...,N
$y_i(\hat w_{opt}·\hat x_i)=y_i(w_{opt}·x_i+b_{opt})\geq \gamma$yi​(w^opt​⋅x^i​)=yi​(wopt​⋅xi​+bopt​)≥γ
（2）令$R=max_{1\leq l\leq N}||\hat x_i||$R=max1≤l≤N​∣∣x^i​∣∣，则感知机算法（1）在训练数据集上的误分类次数k满足不等式
$k\leq (\frac{R}{\gamma})^2​$k≤(γR​)2​
定理表明，误分类的次数是有上界的，经过有限此搜索可以找到将训练数据完全正确分开的分离超平面。也就是说，当训练数据集线性可分时，感知机学习算法原始形式迭代是收敛的。但是，感知机学习算法存在许多解，这些解既依赖与初值的选择，也依赖于迭代过程中误分类点的选择顺序，为了得到唯一的超平面，需要对分离超平面增加约束条件，这就是线性支持向量的想法。当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

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

基本思想：将w和b表示为实例$x_i$xi​和标记$y_i$yi​的线性组合的形式，通过求解其系数而求得$w$w和$b$b。不失一般性，在算法$f(x)=sign(w·x+b)$f(x)=sign(w⋅x+b)中，可假设初始值$w_0,b_0$w0​,b0​均为0，对误分类点$(x_i,y_i)$(xi​,yi​)通过
$w \leftarrow w+ \eta y_ix_i \\ b \leftarrow b+ \eta y_i$w←w+ηyi​xi​b←b+ηyi​
逐步修改$w,b$w,b，设修改n次，则$w,b$w,b关于$(x_i,y_i)$(xi​,yi​)的增量分别是$a_iy_ix_i$ai​yi​xi​和$a_iy_i$ai​yi​，这里$a_i=n_i\eta$ai​=ni​η。这样，从学习过程不难看出，最后学习到的$w,b$w,b可以分别表示为
$w = \sum_{i=1}^Na_iy_ix_i \\ b = \sum_{i=1}^Na_iy_i$w=i=1∑N​ai​yi​xi​b=i=1∑N​ai​yi​
这里，$a_i\geq 0,\space i=1,2,...,N$ai​≥0, i=1,2,...,N，当$\eta=1$η=1时，表示第i个实例点由于误分类而进行更新的次数。实例点更新次数越多，意味着它距离分离超平面越近，也就越难正确分类。换句话，这样的实例对学习结果影响最大。

下面对照原始形式来叙述感知机学习算法的对偶形式。

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

输入：线性可分的数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，其中$x_i\in R^n,y_i\in\{-1,+1\},\space i=1,2,...,N$xi​∈Rn,yi​∈{−1,+1}, i=1,2,...,N；学习率$\eta (0<\eta \leq1)$η(0<η≤1)；

输出：$a,b$a,b；感知机模型$f(x)=sign(\sum_{j=1}^Na_jy_jx_j·x+b)$f(x)=sign(∑j=1N​aj​yj​xj​⋅x+b).

其中$\alpha = (a_1,a_2,...,a_N)^T$α=(a1​,a2​,...,aN​)T。

（1）$a \leftarrow 0, \space b\leftarrow 0$a←0, b←0

（2）在训练集中选取数据$(x_i,y_i)$(xi​,yi​)

（3）如果$y_i(\sum_{j=1}^Na_jy_jx_j·x_i+b)\leq 0$yi​(∑j=1N​aj​yj​xj​⋅xi​+b)≤0
$a_i \leftarrow a_i + \eta \\ b \leftarrow b + \eta y_i$ai​←ai​+ηb←b+ηyi​
（4）转至（2）直到没有误分类数据。

对偶形式中训练实例仅以内积的形式出现。为了方便，可以预先将训练集中实例间的内积计算出来并以矩阵的形式储存，这个矩阵就是所谓的Gram矩阵（Gram matrix）。
$G=[x_i·x_j]_{N\times N}$G=[xi​⋅xj​]N×N​
**例如：**正样本点是$x_1=(3,3)^T,\space x_2=(4,3)^T$x1​=(3,3)T, x2​=(4,3)T，负样本点是$x_3=(1,1)^T$x3​=(1,1)T，试用感知机学习算法对偶形式求感知机模型。

解：按照算法2，

（1）取$a_i=0, \space i=1,2,3, \space b=0, \eta=1$ai​=0, i=1,2,3, b=0,η=1

（2）计算$Gram$Gram矩阵
KaTeX parse error: Unknown column alignment: 1 at position 27: … \begin{array} 1̲18 & 21 & 6 \\ …
（3）误分条件
$y_i(\sum_{j=1}^Na_jy_jx_j·x_i + b)\leq 0$yi​(j=1∑N​aj​yj​xj​⋅xi​+b)≤0
参数更新
$a_i \leftarrow a_i+1, \space b\leftarrow b+y_i$ai​←ai​+1, b←b+yi​
（4）迭代。过程省略，结果见下表

（5）
$w=2x_1 + 0x_2-5x_3 = (1,1)^T \\ b=-3$w=2x1​+0x2​−5x3​=(1,1)Tb=−3
分离超平面
$x^{(1)}+x^{(2)}-3=0$x(1)+x(2)−3=0
感知机模型
$f(x)=sign(x^{(1)}+x^{(2)}-3)$f(x)=sign(x(1)+x(2)−3)

$求解的迭代过程$求解的迭代过程
对照算法1的例子，结果一致，迭代步骤也是互相对应的。

与原始形式一样，感知机学习算法的对偶。