机器学习-感知机

原 作者 冯鑫 | 发表于 | 分类于 2015级

感知机是1957年，由Rosenblatt提出，是神经网络和支持向量机的基础。感知机是二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别类型。
假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练数据集正实例点和负实例点完全正确分开的分离超平面。如果是非线性可分的数据，则最后无法获得超平面。

感知机模型

感知机的输入特征向量x为n维向量，输出y∈{+1,-1}.
感知机从输入空间到输出空间的模型如下：
f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w \cdot {x}+b)
其中 w ∈ R n w∈R^n 叫做权值， b ∈ R b∈R 叫做偏置。
sign是符号函数，即：
s i g n ( x ) = { − 1 x < 0 1 x ≥ 0 sign(x)= \begin{cases} -1& {x<0}\\ 1& {x\geq 0} \end{cases}

感知机有如下几何解释：
线性方程w·x+b=0 对应于特征空间 R n R^n 中的一个超平面S，其中w是超平面的法向量，b是超平面的截距。这个超平面将特征空间划分为两个部分。位于两部分的点分别被分为正、负两类。如下图所示：

在这里插入图片描述
感知机的学习目的就是确定最佳的w和b


数据集的线性可分性

给定一个训练集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} ，如果存在某个超平面S:w·x+b=0能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称为该数据集T线性可分，否则称为线性不可分。


感知机学习策略

损失函数

感知机的损失函数采用误分类点到超平面S的总距离。

首先，写出输入空间中任意一点 x 0 x_0 到超平面S的距离： ∣ w ⋅ x 0 + b ∣ ∣ ∣ w ∣ ∣ \frac{|w\cdot {x_0}+b|}{||w||}
其中，||w||是w的 L 2 L_2 范数， L 2 L_2 范数定义为向量所有元素的平方和的开平方。

对于误分类的数据( x i , y i x_i,y_i )来说， − y i ( w ⋅ x i + b ) > 0 -y_i(w\cdot {x_i}+b)>0 成立
因为当 w ⋅ x i + b > 0 w\cdot {x_i}+b>0 时， y i = − 1 y_i=-1 ，而当 w ⋅ x i + b < 0 w\cdot {x_i}+b<0 时， y i = + 1 y_i=+1 .
因此，误分类点 x i x_i 到超平面S的距离是：
− y i ( w ⋅ x i + b ) ∣ ∣ w ∣ ∣ -\frac{y_i(w\cdot {x_i}+b)}{||w||}
假设超平面S的误分类点集合为M，那么所有误分类点到超平面S的总距离为：
− 1 ∣ ∣ w ∣ ∣ ∑ x i ∈ M y i ( w ⋅ x i + b ) -\frac{1}{||w||}\sum_{x_i\in{M}}y_i(w\cdot {x_i}+b) .

不考虑 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ，则感知机的损失函数定义为：
L ( w , b ) = − ∑ x i ∈ M y i ( w ⋅ x i + b ) L(w,b)=-\sum_{x_i\in{M}}y_i(w\cdot {x_i}+b)
其中M为误分类点的集合.

显然，损失函数是非负的。如果没有误分类点，损失函数值是0。而且，误分类点越少，误分类点离超平面越近，损失函数值就越小。给定训练数据集T，损失函数 L ( w , b ) L(w,b) 是w,b的连续可导函数。


为什么可以不考虑 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||}

  • 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} 不影响 y i ( w ⋅ x i + b ) y_i(w\cdot {x_i}+b) 正负的判断，即不影响学习算法的中间过程。因为感知机学习算法是误分类驱动的，这里需要注意的是所谓的“误分类驱动”指的是我们只需要判断 − y i ( w ⋅ x i + b ) -y_i(w\cdot{x_i}+b) 的正负来判断分类的正确与否，而 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} 并不影响正负值的判断。所以 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} 对感知机学习算法的中间过程可以不考虑。
  • 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} 不影响感知机学习算法的最终结果。因为感知机学习算法最终的终止条件是所有的输入都被正确分类，即不存在误分类的点。则此时损失函数为0. 对应于 − 1 ∣ ∣ w ∣ ∣ ∑ i ∈ M y i ( w ⋅ x i + b ) -\frac{1}{||w||}\sum_{i\in{M}}y_i(w\cdot {x_i}+b) ，即分子为0.则可以看出 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} 对最终结果也无影响。

感知机学习算法

原始形式

输入：训练数据集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} ， y i ∈ { − 1 , + 1 } y_i\in{\{-1,+1\}} ，学习率 η ( 0 < η < 1 ) \eta(0<\eta<1)
输出：?,?；感知机模型 f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w\cdot {x}+b)

  1. 赋初值 w 0 , b 0 w_0,b_0
  2. 选取数据点 ( x i , y i ) (x_i,y_i)
  3. 判断该数据点是否为当前模型的误分类点，即判断若 y i ( w ⋅ x i + b ) < = 0 y_i(w\cdot {x_i}+b)<=0
    则更新:
    w = w + η y i x i w={w+\eta{y_ix_i}}
    b = b + η y i b={b+\eta{y_i}}
  4. 转到2，直到训练集中没有误分类点

对偶形式

由于?,?的梯度更新公式：
w = w + η y i x i w={w+\eta{y_ix_i}}
b = b + η y i b={b+\eta{y_i}}
我们的?,?经过了?次修改后的，参数可以变化为下公式，其中?=??：
w = ∑ x i ∈ M η y i x i = ∑ i = 1 n α i y i x i w=\sum_{x_i\in{M}}\eta{y_ix_i}=\sum_{i=1}^n\alpha_iy_ix_i
b = ∑ x i ∈ M η y i = ∑ i = 1 n α i y i b=\sum_{x_i\in{M}}\eta{y_i}=\sum_{i=1}^n\alpha_iy_i

这样我们就得出了感知机的对偶算法：

输入：训练数据集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)} ， y i ∈ { − 1 , + 1 } y_i\in{\{-1,+1\}} ，学习率 η ( 0 < η < 1 ) \eta(0<\eta<1)
输出：?,?；感知机模型 f ( x ) = s i g n ( w ⋅ x + b ) f(x)=sign(w\cdot {x}+b)
其中 α = ( α 1 , α 2 , . . . , α n ) T \alpha=(\alpha_1,\alpha_2,...,\alpha_n)^T

  1. 赋初值 w 0 , b 0 w_0,b_0
  2. 选取数据点 ( x i , y i ) (x_i,y_i)
  3. 判断该数据点是否为当前模型的误分类点，即判断若 y i ( w ⋅ x i + b ) < = 0 y_i(w\cdot {x_i}+b)<=0
    则更新:
    α i = α i + η \alpha_i={\alpha_i+\eta}
    b = b + η y i b={b+\eta{y_i}}
  4. 转到2，直到训练集中没有误分类点

为了减少计算量，我们可以预先计算式中的内积，得到Gram矩阵:
G = [ x i , x j ] N × N G=[x_i,x_j]_{N×N}


训练过程

我们大概从下图看下感知机的训练过程:
在这里插入图片描述

线性不可分的过程：
在这里插入图片描述