感知机算法的收敛性

感知机学习算法是否收敛？

定理：假设给定m个输入样本（$\{X(k)\},(k=1,2,...,m)$）线性可分，那么感知机学习算法的权值就会在有限次的步骤中收敛到理想输出。

定性解释：

如果两类n维样本线性可分，那么一定存在一个n-1维的平面将其分开，n-1维超平面定义为：

$W(k)=[w_0(k),w_1(k),...w_n(k)]:W^{T}X(k)=0$

$\to w_0(k)+w_1(k)x_1(k)+...+w_n(k)x_n(k)=0$

这个超平面将$X(k)$分为两类：

$W(k{)}^{T}X(k)>0\to y(k)=1\to X(k)\in C_1$

$W(k{)}^{T}X(k)<0\to y(k)=0\to X(k)\in C_0$

在训练过程中，感知机的权重不断地在被调整使得分类结果接近正确分类结果。

定量证明：

假设存在由理想的权值$W^{\ast }$确定的理想超平面$H^{\ast }$，可得到如下结果：

如果$X(k)\in C_1$，那么$X^T(k)W^{\ast }>0,y(k)=1$；

如果$X(k)\in C_0$，那么$X^T(k)W^{\ast }<0,y(k)=0$。

证明：学习算法是否能逼近$W^{\ast }$

证明：假设$W^{\ast }$是理想权值，那么任意$\alpha >0$，$\alpha W^{\ast }$也是理想权值。因为有：

$X^T(k)\alpha W^{\ast }>0$，或者 $X^T(k)\alpha W^{\ast }<0$

理性权值不为1，找到一个，乘任一大于0的常数还是理想权值

所以，算法逼近$\alpha W^{\ast }$也算逼近理想权值

证明：存在有限值N，使得$\Vert W(N)-\alpha W^{\ast }{\Vert }^2\stackrel{N\uparrow }{}0$。

证明过程：

根据学习算法，在第k次迭代过程中，可以得到权值：

$W(k+1)=W(k)+\eta (d(k)-y(k))X(k)$

​ 如果在第k次迭代，$X(k)$被正确分类，那么$d(k)-y(k)=0,W(k+1)=W(k)$

​ 如果在第k次迭代中，发生错误分类，那么：

​ 情况1：$X(k)\in C_1$，但是$X^T(k)W(k)<0$，$d(k)=1,y(k)=0$

​ 情况2：$X(k)\in C_0$，但是$X^T(k)W(k)>0$，$d(k)=0,y(k)=1$

如果能证明错误情况下，权重向纠正（减小）的方向发展，即收敛。

​ 情况1证明：

​ 在情况1下，$d(k)-y(k)=1-0=1$，$W^{T}X(k)<0$根据算法：

$W(k+1)=W(k)+\eta (d(k)-y(k))X(k)=W(k)+\eta X(k)$

$\begin{array}{rl}\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2& =[W(k+1)-\alpha W^{\ast }{]}^T[W(k+1)-\alpha W^{\ast }]\\ & =[W(k)+\eta X(k)-\alpha W^{\ast }{]}^T[W(k)+\eta X(k)-\alpha W^{\ast }]\\ & =\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2+2\eta [W(k)-\alpha W^{\ast }{]}^{T}X(k)\end{array}$

分解最后一项，其中$2\eta W^T(k)X(k)<0$，所以，上式小于把这个负项拿掉之后的剩余部分：

原式$<\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2-2\eta \alpha W^{\ast T}X(k)$

令$max\{\Vert X(k){\Vert }^2\}={\beta }^2,min\{\Vert W^{\ast T}X(k)\Vert \}=\gamma$

则上式$\le \Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2{\beta }^2-2\eta \alpha \gamma$

其中$\Vert W(k)-\alpha W^{\ast }{\Vert }^2$为第k次迭代误差，$\eta 和\beta$都为常数，$\alpha$为任意大于0常数

假设$\alpha =\frac{\eta {\beta }^2}{\gamma }(>0)$，带入上式得

上式$=\Vert W(k)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$

即$\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2<\Vert W(k)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$即迭代后误差减小

验证：$k=0:\Vert W(1)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$

$k=1:\Vert W(2)-\alpha W^{\ast }{\Vert }^2<\Vert W(1)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-2{\eta }^2{\beta }^2$

$...$

$\Vert W(N)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-N{\eta }^2{\beta }^2$

因为不等式左侧为大于零的一个数，右侧为一个常数减去线性增大的数，最后结果只能趋近于零：

$\Vert W(N)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-N{\eta }^2{\beta }^2\to 0$

$\therefore$N满足$N\le \Vert W(0)-\alpha W^{\ast }{\Vert }^2/({\eta }^2{\beta }^2)$

即N是有限的

情况2：$X(k)\in C_0$，但是$X^T(k)W(k)>0$，$d(k)=0,y(k)=1$

在情况2下，$d(k)-y(k)=0-1=-1$，$W^{T}X(k)>0$根据算法：

$W(k+1)=W(k)+\eta (d(k)-y(k))X(k)=W(k)-\eta X(k)$

$\begin{array}{rl}\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2& =[W(k+1)-\alpha W^{\ast }{]}^T[W(k+1)-\alpha W^{\ast }]\\ & =[W(k)-\eta X(k)-\alpha W^{\ast }{]}^T[W(k)-\eta X(k)-\alpha W^{\ast }]\\ & =\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2-2\eta [W(k)-\alpha W^{\ast }{]}^{T}X(k)\end{array}$

分解最后一项，其中$2\eta W^T(k)X(k)>0$，所以，上式小于把这项拿掉之后的剩余部分，即

$\begin{array}{rl}\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2& =\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2-2\eta [W(k)-\alpha W^{\ast }{]}^{T}X(k)\\ & <\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2+2\eta \alpha W^{\ast T}X(k)\end{array}$

令$max\{\Vert X(k){\Vert }^2\}={\beta }^2$

$\because X(k)\in C_0$

$\therefore W^{\ast T}X(k)<0,$令$max\{\Vert W^{\ast T}X(k)\Vert \}=\gamma (\gamma <0)$

则$\begin{array}{rl}\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2& <\Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2\Vert X(k){\Vert }^2+2\eta \alpha W^{\ast T}X(k)\\ & \le \Vert W(k)-\alpha W^{\ast }{\Vert }^2+{\eta }^2{\beta }^2+2\eta \alpha \gamma \end{array}$

其中$\Vert W(k)-\alpha W^{\ast }{\Vert }^2$为第k次迭代误差，$\eta 和\beta$都为常数，$\alpha$为任意大于0常数

假设$\alpha =-\frac{\eta {\beta }^2}{\gamma }(>0)$，带入上式得

上式$=\Vert W(k)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$

即$\Vert W(k+1)-\alpha W^{\ast }{\Vert }^2<\Vert W(k)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$即迭代后误差减小

验证：$k=0:\Vert W(1)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2$

$k=1:\Vert W(2)-\alpha W^{\ast }{\Vert }^2<\Vert W(1)-\alpha W^{\ast }{\Vert }^2-{\eta }^2{\beta }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-2{\eta }^2{\beta }^2$

$...$

$\Vert W(N)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-N{\eta }^2{\beta }^2$

因为不等式左侧为大于零的一个数，右侧为一个常数减去线性增大的数，最后结果只能趋近于零：

$\Vert W(N)-\alpha W^{\ast }{\Vert }^2<\Vert W(0)-\alpha W^{\ast }{\Vert }^2-N{\eta }^2{\beta }^2\to 0$

前提是样本线性可分，如果$X(k)$线性不可分，$W^{\ast }$将不存在。以上算法可能会导致$W(k)$改变为循环且不收敛