感知机

感知机

想法：错误驱动。

假定

• 模型：$f(x)=sign(x)x,w\in {\mathbb{R}}^P$
• 激活函数：$sign(a)=\{\begin{array}{c}+1,a\ge 0\\ -1,a<0\end{array}$
• 被错误分类的样本：集合$\mathcal{D}$

错误分类就是给$w$一个初始值，不断的挪动我们的曲线，使得$\mathcal{D}$中元素最少。

这里的损失函数为：$L(w)=\sum _{x_i\in \mathcal{D}}I(y_i{w}^T{x}_i)$,其中$I=\{\begin{array}{c}+1,a>0\\ 0,a=0\\ -1,a<0\end{array}$

虽然很直观，但是这个方法有个问题，它的函数

1. 不连续、不可导，不能/很难求解
2. 是NP Hard问题

我们继续观察$z=y_i{w}^{T}x$，当$w$变动一点点，$z$也会变化一点点，这样就可导了，为何不将其当作一个损失函数呢？

现在构造新损失函数$L(w)$：

$$L(w)=\sum _{x_i\in {\mathcal{D}}_{wrong}}-y_i{w}^T{x}_i$$

计算时，我们采用随机梯度下降(SGD)算法

如果不是线性可分的，我们有Pocket Algorithm，它允许有一点点错误存在

• 感知机收敛定理 todo
• Pocket Algorithm