首页 > 代码库 > 【统计学习】随机梯度下降法求解感知机模型

【统计学习】随机梯度下降法求解感知机模型

1. 感知机学习模型

   感知机是一个二分类的线性分类问题,求解是使误分类点到超平面距离总和的损失函数最小化问题。采用的是随机梯度下降法,首先任意选取一个超平面w0和b0,然后用梯度下降法不断地极小化目标损失函数,极小化过程中不是一次使所有误分类点的梯度下降,而是一次随机选取一个误分类点使其梯度下降。假设误分类点集合M是固定的,那么损失函数L(w,b)的梯度:
                                     技术分享
随机选取一个误分类点,对w和b进行更新:
                                        技术分享
其中n是步长,又称为学习率(learning rate),这样通过迭代可以使损失函数L(w,b)不断减小,直到训练集中没有误分类点。直观的解释:当一个实例点被误分类,即位于超平面的错误一侧时,则调整w和b的值,使分离超平面向该误分类点的一侧移动,以减少该误分类点与超平面间的距离,直至超平面越过该分类点使其正确分类[1]。注意:当训练数据集线性可分时,这个迭代是收敛的,也就是经过有限次数的迭代是可以找到最优的超平面的[1]。下面就详细讲解这个迭代的过程。

2.感知机算法的原始形式

输入:

训练数据集 T={(x1,y1),(x2,y2),...,(xn,yn)},其中x1∈Rn,yi={+1,-1},i=1, 2, ..., n,学习率η(0 < η<= 1)

输出:

w, b;感知机模型 f(x) = sign(w·x + b)

过程:

1, 选取初值w, b

2, 在训练集中取数据(xi,yi)

 3, 若 yi(w·xi+ b) <= 0 即分类不正确,则:

       w= w + ηyixi

         b= b + ηyi

注:因为此时分类不对,所以yi= -1

4, 转至步骤2,直到训练数据集中无误分类点

3.感知机算法的对偶形式

在原始形式中有公式:

      w= w + ηyixi

        b= b + ηyi

那么假设一共修改了n次,则w,b关于(xi(1),xi(2))的增量分别为:

      aiyixi和 aiyi                    (ai= niη)

 即: 技术分享

若η=1,则ai就是第i个点由于误分类而进行更新的次数,即ai = ni

ai越大 => 实例点更新次数越多 =>越难正确分类,换句话说:这样的实例对学习结果影响更大!

 算法如下:

输入:

线性可分数据集 T={(x1,y1),(x2,y2),...,(xn,yn)},其中x1∈Rn,yi={+1,-1},i=1, 2, ..., n,学习率η(0 < η<= 1)

输出:

感知机模型 f(x) = sign( aiyixi·x + b)

过程:

1, 令a = 0,b = 0

2,  在训练集中取数据(xi,yi)

3,  若技术分享

则:

        ai= ai + η

        b= b + ηyi

4,  转至2直到无误分类数据

而由于对偶形式的训练实例仅以内积形式出现

所以我们预先将训练集中实例间的内积计算出来并以矩阵形式存储,即:产生Gram矩阵(格拉姆矩阵)

G = [ xi, yi ]n*n

 
[1] 李航,《统计学习方法》,第2章,2.3节

【统计学习】随机梯度下降法求解感知机模型