感知机
in 统计学习原理 with 0 comment

感知机

in 统计学习原理 with 0 comment

感知机对应于输入空间中将实例划分为正负梁磊的分离超平面,属于判别模型

感知机

基础神经网络,其实就是多层感知机……

感知机模型

感知器要解决的问题是二分类(很简单),对于输入的实例,感知机要给出其正确的分类,而总的分类只有两个,正例和负例。

数学上来说,输入空间是$X\subseteq \bf{R}^n$,输出空间为$Y=\{+1,-1\}$。输入$x\in X$表示实例的特征向量,输出$y\in Y$表示实例的类别。这样的一个函数:

$$ f(x)={ \rm sign} (wx+b) $$

这里的$\rm sign$函数是符号函数。

从解析的角度来说,感知机作为一个函数,以实例为自变量产生一个+1或者-1的结果,从而实现分类。

从几何上来理解,感知机就是输入空间中的一个超平面,之所以是“超”,因为输入空间常常是高维的。这个超平面把整个空间一分为二,从而对空间中的点(实例)进行分类。

由解析几何,超平面的方程是:

$$ wx+b=0 $$

这里,$w$是平面法向量,$b$是截距。

对于超平面上方的点,有:

$$ wx+b>0 $$

而对于超平面下方的点,有:

$$ wx+b<0 $$

感知机学习策略

我们需要一个损失函数来度量模型的好坏,或许可以使用误分类点的总数来作为损失函数,当损失函数值为零时,所有的点就都被正确分类了,但是,这个函数很显然不是关于$w,b$的可导函数,那么也就没办法用梯度下降函数来找到它的最小值了。

我们选择另外一种方式来定义损失函数。

我们选择从误分类点到超平面的总距离来度量。

在输入空间中,任何一点$x_0$到超平面的距离是:(话说这玩意不就是几何间隔函数间隔)

$$ \frac{1}{||w||}|wx_0 +b| $$

$||w||$就是向量$w$的模(或者叫长度、$L_2$范数)。对于误分类的点$(x_i,y_i)$来说:

$$ -y_i (wx_i +b)>0 $$

所以我们可以去掉距离表达式中的绝对值:

$$ -\frac{1}{||w||}y_i(wx_i+b) $$

作为一个方向向量,$||w||$可以直接丢掉,我们得到损失函数的表达式:

$$ L(w,b)=-\sum_{x_i\in M}y_i(wx_i+b) $$

其中$M$为误分类点的集合。

$L(w,b)$是关于$w,b$的连续可导函数,于是就可以使用梯度下降了。

感知机学习算法

损失函数的梯度:

$$ \nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\ \nabla_bL(w,b)=-\sum_{x_i\in M}y_i $$

那么,我们就得到一个可以直接写在代码中的赋值表达式,通过这个表达式来更新$w,b$的值,从而找到正确的分类超平面:

$$ w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i $$

$\eta$是学习率,用来调节梯度下降的步长。

最后,给出算法的描述:

1. 选取初始值$w_0,b_0$

2. 在训练集中选取数据$(x_i,y_i)$

3. 如果$y_i(wx_i+b)\leq 0$

$$ w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i $$

4. 转至第二步,循环直至训练集中没有误分类点

感知机学习算法的对偶形式

假定$w_0=0,b_0=0$
已知:

$$ \begin{array}{l} w = \sum\limits_{i = 1}^N {{n_i}\eta {y_i}{x_i}} = \sum\limits_{i = 1}^N {{\alpha _i}} {y_i}{x_i}\\ b = \sum\limits_{i = 1}^N {{n_i}\eta {y_i}} = \sum\limits_{i = 1}^N {{\alpha _i}} {y_i} \end{array} $$

$\alpha_i=n_i\eta$中$n_i$代表对第$i$个样本的学习次数,感知机对偶形式的完整形式即为(6)式:
$$f(x) = sign(\sum\limits_{j = 1}^N {{\alpha _j}} {y_j}{x_j} \cdot x + b)$$

1. 选取初始值$\alpha=0,b=0$

2. 在训练集中选取数据$(x_i,y_i)$

3. 如果 $y_i(\sum\limits_{j = 1}^N {{\alpha _j}} {y_j}{x_j} \cdot x_i + b)\le0 x_i + b)\le0$

$$ \begin{array}{1} \alpha_i\leftarrow \alpha_i+\eta\\ b_i\leftarrow b_i+\eta y_i \end{array} $$

4. 转至第二步,循环直至训练集中没有误分类点

如果留意的话,会发现$\alpha_i$只会增加。别担心,大家都在一起增长。

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号