感知机算法

本文将介绍四种感知机算法，包含批量感知机、pocket感知机、在线感知机以及核化感知机。

感知机算法：每发现一个错误点，就对它就行纠正。

损失函数为： \[ L(w, b) = -\sum_{x_i\in{M}}y_i(wx_i+b) \] 其中M为误分点集合。

批量感知机求解的是损失函数全局最优梯度。

损失函数的梯度： \[ \nabla_wL(w,b)=-\sum_{x_i\in{M}}y_ix_i \\ \nabla_bL(w,b)=-\sum_{x_i\in{M}}y_i \] 每轮迭代需要用到所有样本。

算法如下：

口袋算法基于贪心的思想。随机梯度下降，求解的是单个误分类点的梯度，用来近似全局最优梯度。

更新为：

随机选取一个误分类点\((x_i,y_i)\) \[ w = w+\eta y_ix_i \\ b = b+\eta y_i \] \(\eta\)为更新步长，又称学习率。

算法如下：

在线算法，来一个算一个，类似随机梯度下降求解。

算法如下：

考虑最终的\(w,b\)是修改n次后的增量，也就是： \[ w=\sum_{i=1}^{N}\alpha_iy_ix_i \\ b=\sum_{i=1}^{N}\alpha_iy_i \\ \] 其中\(\alpha_i=n_i\eta\)。

最终的\(f(x)\)如下： \[ f(x)=\sum_{i=1}^{N}\alpha_iy_ix_i\cdot x+b \] 公式中存在\(x_i\cdot x\)项，就可以采用核化理论，这就是核化感知机算法。

至此，四种感知机算法解释完毕。