感知机收敛性(Novikoff定理证明)

  存在超平面（超平面法线向量为${\hat{w}}_{opt}$，$||{\hat{w}}_{opt}||=1$，超平面方程为$\hat{x}\cdot {\hat{w}}_{opt}=x\cdot w_{opt}+b_{opt}=0$）。其中${\hat{w}}_{opt}$包括了偏置项，它的表达为${\hat{w}}_{opt}=(w^T,b{)}^T$。超平面对于所有训练数据都能够正确分开，并且对于所有训练样来说都满足$y_i(x_i\cdot w_{opt}+b_{opt})\ge \gamma$。对于每个训练样本满足$||\widehat{x_i}||\le R$，则模型迭代次数$k$满足不等式
$$k\le (\frac{R}{\gamma }{)}^2$$

  设初始值$\widehat{w_0}=0$，如果遇到错误分类的样本，就更新权重。则${\hat{w}}_{k-1}$表示的是第$k$次模型迭代之前对应的参数。假设此时被错分的样本为$(x_i,y_i)。则$
$${\hat{w}}_k\cdot {\hat{w}}_{opt}=({\hat{w}}_{k-1}+\eta y_i{x}_i)\cdot {\hat{w}}_{opt}\ge {\hat{w}}_{k-1}\cdot {\hat{w}}_{opt}+\eta \gamma$$

  根据数学归纳法，可得
$${\hat{w}}_k\cdot {\hat{w}}_{opt}\ge k\eta \gamma$$

$$||{\hat{w}}_k||\ge k\eta \gamma$$

  平方展开结果为：
$$||{\hat{w}}_k|{|}^2=||{\hat{w}}_{k-1}|{|}^2+2||{\hat{w}}_{k-1}||\eta y_i{\hat{w}}_{k-1}{x}_{k-1}+{\eta }^2||{\hat{x}}_i|{|}^2$$

$$\le ||{\hat{w}}_{k-1}|{|}^2+{\eta }^2||{\hat{x}}_i|{|}^2$$

$$\le k{\eta }^2{R}^2$$

  所以$$k^2{\eta }^2{\gamma }^2\le k{\eta }^2{R}^2$$

$$k\le (\frac{R}{\gamma }{)}^2$$

文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/herosunly/article/details/103512144