《统计学习方法》-感知机

模型

感知机的目标是找到一个可以将正负实例完全分开的分离超平面$\omega X+b=0$，模型的形式显而易见，为：

$$ f(x)=sign(\omega X+b)\\ 其中sign(x)=\left\{\begin{matrix} +1, & x\geqslant 0\\ -1, & x<0 \end{matrix}\right. $$

当在平面的上面时，划分成一类，下面一类。

感知机的目标是找到一个可以将正负实例完全分开的分离超平面，需要定义一个策略，即定义（经验）损失函数并将损失函数最小化。

损失函数一个自然选择是误分类点的总数，另一个是误分类点到超平面S的总距离，是参数$\omega,b$的连续可导函数，有利于优化。

$$ 误分类点到S的总距离L=-\frac{1}{\left \| \omega \right \|}\sum_{x_i\in M}y_i(\omega x_i+b),M为误分类点的集合 $$

由于$-\frac{1}{\left \| \omega\right \|}$是在一次迭代中是定值，对最后的结果不会产生影响，所以最后感知机的最小化代价函数是：

$$ L(\omega, b)=\min-\sum_{x_i \in M}y_i(\omega x_i+b),M为误分类点的集合 $$

原始形式，直接对$\omega,x$进行求导，进行迭代：

$$ \begin{aligned} \frac{\partial L(\omega,b)}{\partial \omega}&=y_i x_i\\ \frac{\partial L(\omega,b)}{\partial b}&=y_i \end{aligned} $$

设学习率是$\eta$，则：整个模型是输入数据集T和学习率$\eta,(0<\eta\leqslant 1)$，输出$\omega,b$，得到感知机模型$f(x)=sign(\omega x+b)$.

选取初值$\omega_0,b_0$
选取数据$(x_i,y_i)$
如果$y_i(\omega x_i+b)\leqslant 0$，即是误分类点，则进行迭代更新$\omega,b$：
$$ \begin{aligned} \omega&\leftarrow \omega+\eta\frac{\partial L(\omega,b)}{\partial \omega}\\ b&\leftarrow b+\eta\frac{\partial L(\omega,b)}{\partial b} \end{aligned} $$

算法的对偶形式：

对偶形式可以看成是对求解问题的另一种解法，这里是将对$\omega,b$的求导换成了对$\eta,b$的求导。

对误分类点逐步修改n次，则$\omega,b$关于$(x_i,y_i)$的增量分别是$\alpha_iy_ix_i$和$\alpha_iy_i$，这里$\alpha_i=n_i\eta$. 这样，从学习过程不难看出，最后学习到的$\omega,b$可以分别表示为

$$ \begin{aligned} \omega&=\sum_{i=1}^N \alpha_iy_ix_i\\ b&=\sum_{i=1}^N \alpha_iy_i \end{aligned} $$

这样，误分类条件变成了:

$$ 如果：y_i(\sum_{j=1}^N \alpha_jy_jx_jx_i+b)\leqslant 0\\ \begin{aligned} \alpha_i&\leftarrow \alpha_i+\eta\\ b&\leftarrow b+\eta y_i \end{aligned} $$

当训练集线性可分时，感知机算法是收敛的，误分类次数k满足不等式：

$$ k\leqslant \left(\frac{R}{\gamma}\right)^2 $$

优势是可以先求出Gram矩阵，加快计算速度。