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

作者: Joe_WQ | 来源:发表于2018-11-16 19:11 被阅读0次

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)$ .

选取初值 $\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矩阵，加快计算速度。

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

模型

策略

算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读