感知机

1. 证明感知机学习算法的收敛性。

来源：统计学习方法

算法收敛性概念：在有限步数内能够获得一个能够正确划分训练集所有样本点的分离超平面及其相应的模型参数。

假设：该训练数据集可被线性分类器分离，并且存在一个能够将两类样本完全分开的超平面。其参数设定为W_{opt},b_{opt}。

设\hat{w_{opt}}=(w_{opt}^T,b_{opt})^T,\hat{x}=(x^T,1)^T,||\hat{w_{opt}}||=1（和SVM里的类似）

因为y_i(\hat{W_{opt}}*\hat{x}_i)=0，令\gamma =min(y_i(\hat{W_{opt}}*\hat{x}_i))

• 令R=max||\hat{x_i}||，则感知机算法再训练数据集上的误分类次数k满足

k<=(\frac{R}{\gamma})^2

证明如下：

首先证明两个式子（提示：递归）

1. \hat{W_{k}}*\hat{W_{opt}}>=kn\gamma
2. ||\hat{w_k}||^2<=kn^2R^2

kn\gamma<=\hat{W_{k}}*\hat{W_{opt}}<<||\hat{w_k}||*||\hat{w_{opt}}||=||\hat{w_k}||<=\sqrt{kn^2R^2}