【学习】浅析感知机--收敛性证明与对偶形式以及python代码讲解

继上篇《浅析感知机（二）--学习算法及python代码剖析》 - 知乎专栏感知机学习算法以及python实现讲完之后，其实感知机的知识大部分已经讲完，这篇文章可以收尾一下，讲解一下感知机的对偶形式，以及证明一下为什么在迭代有限次的时候可以收敛等知识。

推荐阅读方式：结合前面讲过的浅析感知机（一）--模型与学习策略 - 知乎专栏（前面公众号推送）

《浅析感知机（二）--学习算法及python代码剖析》 - 知乎专栏

（前面公众号推送）

以及李航博士的《统计学习方法》一起阅读，效果较好！

我们需要证明经过有限次迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知机模型。（证明了，我们心里才有底，否则都不知道是否能够保证收敛）

开始：

我们会有以下定理：

设训练数据集T={(x1,y1),(x2,y2),...,(xn,yn)}是线性可分的，则下面俩个定理成立：

由上面定理可以得到，直白来说，如果是一个线性可分的数据集，我是可以在有限次k更新，得到一个将数据集完美分割好的超平面（感知机模型）。下面给出证明：（前方数学证明预警，这里默认收敛性成立也是可以的，不影响应用）

定理一证明如下：

定理二证明如下：

友情提示，可能不是太清楚，但是只要仔细跟着去看，一定能够看懂。把收敛性的证明该注意的地方全部写到了。（完全按李航博士书籍顺序讲解）

那么我们可以得到结论，误分类的次数k是有上界的，当训练数据集线性可分的时候，感知机学习算法原始迭代是收敛的！（证明了算法是对的，可行的）

原文链接：

http://mp.weixin.qq.com/s/JaMdOQ4kQVgRmx9SJ2IFbw