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

举报
herosunly 发表于 2021/11/19 01:03:48 2021/11/19
【摘要】   存在超平面(超平面法线向量为 w ...

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

  设初始值 w 0 ^ = 0 \hat {w_0}=0 w0^=0,如果遇到错误分类的样本,就更新权重。则 w ^ k − 1 \hat {w}_{k-1} w^k1表示的是第 k k k次模型迭代之前对应的参数。假设此时被错分的样本为 ( x i , y i ) 。 则 (x_i,y_i)。则 (xi,yi)
w ^ k ⋅ w ^ o p t = ( w ^ k − 1 + η y i x i ) ⋅ w ^ o p t ≥ w ^ k − 1 ⋅ w ^ o p t + η γ \hat {w}_{k} \cdot \hat {w}_{opt}=(\hat {w}_{k-1}+\eta y_ix_i) \cdot \hat {w}_{opt} \ge \hat {w}_{k-1} \cdot \hat {w}_{opt}+ \eta \gamma w^kw^opt=(w^k1+ηyixi)w^optw^k1w^opt+ηγ

  根据数学归纳法,可得
w ^ k ⋅ w ^ o p t ≥ k η γ \hat {w}_{k} \cdot \hat {w}_{opt} \ge k\eta \gamma w^kw^optkηγ

∣ ∣ w ^ k ∣ ∣ ≥ k η γ ||\hat {w}_{k}|| \ge k\eta \gamma w^kkηγ

  平方展开结果为:
∣ ∣ w ^ k ∣ ∣ 2 = ∣ ∣ w ^ k − 1 ∣ ∣ 2 + 2 ∣ ∣ w ^ k − 1 ∣ ∣ η y i w ^ k − 1 x k − 1 + η 2 ∣ ∣ x ^ i ∣ ∣ 2 ||\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 w^k2=w^k12+2w^k1ηyiw^k1xk1+η2x^i2

≤ ∣ ∣ w ^ k − 1 ∣ ∣ 2 + η 2 ∣ ∣ x ^ i ∣ ∣ 2 \le ||\hat {w}_{k-1}||^2 + \eta^{2}||\hat{x}_i||^2 w^k12+η2x^i2

≤ k η 2 R 2 \le k \eta^{2} R^{2} kη2R2

  所以 k 2 η 2 γ 2 ≤ k η 2 R 2 k^2\eta^2\gamma^2 \le k \eta^2 R^2 k2η2γ2kη2R2

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

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

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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200