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

2018-11-16  本文已影响0人  Joe_WQ

date: 2018-1-15

模型

感知机的目标是找到一个可以将正负实例完全分开的分离超平面\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).

  1. 选取初值\omega_0,b_0

  2. 选取数据(x_i,y_i)

  3. 如果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矩阵，加快计算速度。

上一篇下一篇

猜你喜欢

热点阅读