区块链技术博客
www.b2bchain.cn

统计学习方法第二章:感知机学习算法求职学习资料

本文介绍了统计学习方法第二章:感知机学习算法求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

第二章 感知机学习算法

界限清晰,才能一分为二,不致混乱


[toc]

引入

感知机学习算法在我眼中其实就是为样本找一条界限,就如同以前地理中所学的,秦岭以北的区域就是北方,以南的区域就是南方。所以在地图上分辨南北,你只要看他在秦岭南边还是北边就好了。那感知机学习算法也是这样,通过训练数据找到最合适的界限,然后就把输入进来的数据一分为二,完成了分类的效果。

所以我们的算法所要完成的就是找到这个界限的数学描述,而这个界限在感知机学习算法里面有个特别高大上的名字”超平面“。

平面就平面,为啥要加个超字呢?而且一开始不是说好是找一条界限的么,那不就是一根线么?

别急,慢慢来,我们刚刚举了一个例子,是在地图上分南北区域。所以我们找的是秦岭那一条线对吧。那要是我让你区分地面以上,地面以下。你是不是就要以地面这个面为界限进行区分。又或者我们回到我们初中的数轴,要你区分正负数的时候,是不是就是找到原点,左边是负数,右边是正数。

所以我们在做分类的时候的界限不一定是一条线,也可能是点,面,甚至是高维空间。所以,我们统一称为超平面。

然后,我们来说感知机学习算法的限制条件,首先,由于我们求解的需要。我们对超平面有一定的限制,就是这个超平面必须要是线性的,比如点,直线,平面这种。 不能是,曲线,圆,球,甚至更加奇怪的界限。所以开始地理上的那个例子其实不太严谨,但是大家意会一下就好啦!

那么超平面做了限制之后,我们对于数据的分布也有一定的限制!就是这些数据一定要是线性可分的。简单来时,就是你一定要能够通过我们之前所说的超平面将其一分为二。 所以我们一般把感知机称为二分类的线性分类模型

好,说了这么多开场白,下面我们就来看看感知机到底是怎么实现的呢?我先带大家捋一遍整个过程,再逐步细化。

假设现在我们有一组线性可分的训练数据集,感知机学习的目标是求得一个能够将训练集的中的两类不同的实例完全正确分开的分离超平面。也就是说感知机的结果是求一个分离超平面的数学表达!,那具体超平面的数学表达是怎么表达的呢?

回顾一下,我们从小对于直线和平面的数学定义:
$$ Ax+By+C=0$$
$$Ax+By+Cz=D=0$$
这里面的不定参数是$A,B,C,D$。如果我们想要得到直线和平面的确切表达,就需要把这里面的A,B,C,D求出来。那我们拓展到任意维平面用$x_i$来表达每一个坐标,用$w_i$来代表每一个坐标前的参数,用$b$来表达常数项。就能得到一个任意维超平面的表达式
$$sum_iw_ix_i+b=0$$
然后更进一步,我们用向量$mathbf{w}={w_1,w_2,w_3…w_i}$, $mathbf{x}={x_1,x_2,x_3…x_i}$,来改写这个式子,我们就能得到
$$mathbf{w} mathbf{x}+b=0$$
$mathbf{w} mathbf{x}$表示两个向量的内积运算,即对应位置坐标相乘再求和。所以感知器学习算法最终想要得到的就是这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量$b$,而专业的叫法称这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$为权值(weight), $b$ 称为偏置(bias).

那假设我已经得到了这个平面之后,我们是不是就需要通过这个平面判定。那我想要判定就得找到一个判定函数呀,比如说我平面上方的点,输入进入这个判定函数之后,能够得到一个值。一个平面下方的点,输入进入这个判定函数之后,就能得到一个另外的值。而且这两个值是很容易区分出来的。所以我们想到了一个非常牛逼的函数:
$$f(x)=sign(x)= begin{cases}
+1 quad xgeq0
-1 quad x<0,
end{cases}$$
$f(x)=sign(x)$是符号函数,如果输入进去的值是非负数,输出值就为1,如果是负数,输出值就为0.
我们把我们的超平面和这个符号函数组合一下就变成
$$f(x)=sign(mathbf{w}mathbf{x}+b),$$
这样我们就能够将数据集的正实例点和负实例点完全划分到超平面的两侧。详细来说就是对于$y_i$=+1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b>0$,对于$y_i$=-1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b<0$.

找到了判定方法,由我们之前的基础知识,我们知道我们需要确定一个学习策略,具体来说就是找到一个合适的损失函数,并极小化这个损失函数,得到我们的感知机训练模型,以此来确定$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量 $b$。

那我们的第一想法自然是,极小化分错的点数,但是由于我们的点的个数数是离散值,没办法通过求导来优化,所以我们只能选择其他的办法。那么想出感知机算法的大牛用了另一种思路,将所有误分类的点到超平面的距离之和作为误差函数。这样当所有的点都被正确分类之后,就能取到极小值。

那我们又来回忆一下高中的知识,我们用数学公式是怎样表达一个点到直线的距离的?假设直线是$Ax+By+C=0$, 点的坐标是是$(x_i,y_i)$,那么距离的表达就是
$$d=frac{|Ax_i+By_i+C|}{sqrt{A^2+B^2}}$$
那如果我们用之前的$mathbf{w}mathbf{x}+b$来表达这个平面的话,对应下来这个$d$就能被改写成
$$d=frac{|mathbf{w}mathbf{x_i}+b|}{||mathbf{w}||}$$
$||mathbf{w}||$表达的是权值向量的模,也称为二范数。另外对于误分类的点来说,$mathbf{w}mathbf{x_i}+b$ 与 $y_i$是异号的,我们有
$$-y_i(mathbf{w}mathbf{x_i}+b)>0$$
其中$y_i={+1,-1}$,所以距离的表达又可以写为
$$d=frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
考虑全部误分类点到超平面的距离,我们就有
$$d=sum_{x_iin M}frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
不考虑$frac{1}{||mathbf{w}||}$, 就能得到感知机学习算法里的损失函数。

关于为什么可以不考虑前面这一项我找到了如下解释, 供各位参考

统计学习方法第二章:感知机学习算法
参考:https://www.cnblogs.com/huangyc/p/9706575.html


感知机学习算法的原始形式

下面我们来具体讲解感知机学习算法的流程。先从最简单的感知机学习算法开始

给定一个训练数据集
$$T={(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_i,y_i)}$$
其中,$x_iinmathbf{X}=R^n$, $y_iin{-1,1}$,$i=1,2,…,N$, 求参数$w,b, $使其为函数极小化的解
$$min_{w,b}=-sum_{x_iin M}mathbf{w}mathbf{x_i}+b$$
其中$M$为误分类的集合。极小化的方法采用随机梯度下降(stochastic gradient descent)。

首先,任意选取一组超平面参数$w_0$, $b_0$,然后用梯度下降法不断极小化目标函数。极小化过程不是一次使M中所有误分类点梯度下降,而是一次随机选取一个误分类点。


(如果对于梯度下降法不熟悉,有想要了解的话,可以去看知乎中的详细解释
:https://www.zhihu.com/question/305638940)


如果只是想简单理解梯度下降的意思的话,你就想象现在在一个坡上,你想到这个坡的最低点去,那你肯定是要下坡对不对。那换到函数导数(梯度)里面,如果现在这一点的导数(梯度)大于零,函数想要变小,那是不是就得往回走,如果这一点导数小于零,函数想要变小,那就往前走。那么两种情况可以共同表达为:
$$x=x-etanabla_x$$
公式中$eta(0<etaleq1)$是步长,在统计学习中又称为学习率(learning rate)。当到达最小值点,导数(梯度)等于0(在误差范围内),迭代结束。那为啥一定要是梯度方向or反方向呢,因为这样下降得快!

那么回到我们的问题,假设分类点集合M是固定的,那么损失函数$L(w,b)$的梯度表示为:
$$
nabla_w L(w,b)=-sum_{x_iin M}y_ix_i
nabla_b L(w,b)=-sum_{x_iin M}y_i
$$
那么我们每次选取一个误分类点$(x_i,y_i)$,对$w,b$进行梯度更新:
$$
wleftarrow w+eta y_ix_i
bleftarrow b+eta x_i
$$
这样,通过迭代可以期待损失函数L(w,b)不断减小,直到为0。那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P39)。
统计学习方法第二章:感知机学习算法


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

那么有原始形式,肯定会有精进版本,下面讲一下感知机学习算法的对偶形式。

对偶问题这个词来源于凸优化理论,一般是指一个与原问题形式上不同,但最终优化结果实质相同的优化问题。一般我们需要对偶问题,有以下几个方面的考虑:

  1. 提升算法性能(降低原算法的时间复杂度,降低原算法的空间复杂度)
  2. 解决原算法不能解决的问题

在这里感知机的对偶问题主要是为了提升算法性能,加快算法的收敛速度。

统计学习方法第二章:感知机学习算法
那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P44)。

统计学习方法第二章:感知机学习算法

关于原始形式和对偶形式的使用

  • 向量维数(特征数)过高时,计算内积非常耗时,应选择对偶形式算法加速。
  • 在向量个数(样本数)过多时,每次计算累计和就没有必要,应选择原始算法

感知机学习算法的收敛性

算法的收敛性描述了感知机学习算法有效所需要满足的条件
统计学习方法第二章:感知机学习算法

证明见李航《统计学习方法》(第二版)P42

结论说明:当训练数据集线性可分时,误分类的次数是有上界的,说明感知机学习算法原始形式迭代是收敛的。当训练集线性不可分的时候,感知机学习算法不收敛,迭代结果震荡。


第二章 感知机学习算法

界限清晰,才能一分为二,不致混乱


[toc]

引入

感知机学习算法在我眼中其实就是为样本找一条界限,就如同以前地理中所学的,秦岭以北的区域就是北方,以南的区域就是南方。所以在地图上分辨南北,你只要看他在秦岭南边还是北边就好了。那感知机学习算法也是这样,通过训练数据找到最合适的界限,然后就把输入进来的数据一分为二,完成了分类的效果。

所以我们的算法所要完成的就是找到这个界限的数学描述,而这个界限在感知机学习算法里面有个特别高大上的名字”超平面“。

平面就平面,为啥要加个超字呢?而且一开始不是说好是找一条界限的么,那不就是一根线么?

别急,慢慢来,我们刚刚举了一个例子,是在地图上分南北区域。所以我们找的是秦岭那一条线对吧。那要是我让你区分地面以上,地面以下。你是不是就要以地面这个面为界限进行区分。又或者我们回到我们初中的数轴,要你区分正负数的时候,是不是就是找到原点,左边是负数,右边是正数。

所以我们在做分类的时候的界限不一定是一条线,也可能是点,面,甚至是高维空间。所以,我们统一称为超平面。

然后,我们来说感知机学习算法的限制条件,首先,由于我们求解的需要。我们对超平面有一定的限制,就是这个超平面必须要是线性的,比如点,直线,平面这种。 不能是,曲线,圆,球,甚至更加奇怪的界限。所以开始地理上的那个例子其实不太严谨,但是大家意会一下就好啦!

那么超平面做了限制之后,我们对于数据的分布也有一定的限制!就是这些数据一定要是线性可分的。简单来时,就是你一定要能够通过我们之前所说的超平面将其一分为二。 所以我们一般把感知机称为二分类的线性分类模型

好,说了这么多开场白,下面我们就来看看感知机到底是怎么实现的呢?我先带大家捋一遍整个过程,再逐步细化。

假设现在我们有一组线性可分的训练数据集,感知机学习的目标是求得一个能够将训练集的中的两类不同的实例完全正确分开的分离超平面。也就是说感知机的结果是求一个分离超平面的数学表达!,那具体超平面的数学表达是怎么表达的呢?

回顾一下,我们从小对于直线和平面的数学定义:
$$ Ax+By+C=0$$
$$Ax+By+Cz=D=0$$
这里面的不定参数是$A,B,C,D$。如果我们想要得到直线和平面的确切表达,就需要把这里面的A,B,C,D求出来。那我们拓展到任意维平面用$x_i$来表达每一个坐标,用$w_i$来代表每一个坐标前的参数,用$b$来表达常数项。就能得到一个任意维超平面的表达式
$$sum_iw_ix_i+b=0$$
然后更进一步,我们用向量$mathbf{w}={w_1,w_2,w_3…w_i}$, $mathbf{x}={x_1,x_2,x_3…x_i}$,来改写这个式子,我们就能得到
$$mathbf{w} mathbf{x}+b=0$$
$mathbf{w} mathbf{x}$表示两个向量的内积运算,即对应位置坐标相乘再求和。所以感知器学习算法最终想要得到的就是这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量$b$,而专业的叫法称这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$为权值(weight), $b$ 称为偏置(bias).

那假设我已经得到了这个平面之后,我们是不是就需要通过这个平面判定。那我想要判定就得找到一个判定函数呀,比如说我平面上方的点,输入进入这个判定函数之后,能够得到一个值。一个平面下方的点,输入进入这个判定函数之后,就能得到一个另外的值。而且这两个值是很容易区分出来的。所以我们想到了一个非常牛逼的函数:
$$f(x)=sign(x)= begin{cases}
+1 quad xgeq0
-1 quad x<0,
end{cases}$$
$f(x)=sign(x)$是符号函数,如果输入进去的值是非负数,输出值就为1,如果是负数,输出值就为0.
我们把我们的超平面和这个符号函数组合一下就变成
$$f(x)=sign(mathbf{w}mathbf{x}+b),$$
这样我们就能够将数据集的正实例点和负实例点完全划分到超平面的两侧。详细来说就是对于$y_i$=+1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b>0$,对于$y_i$=-1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b<0$.

找到了判定方法,由我们之前的基础知识,我们知道我们需要确定一个学习策略,具体来说就是找到一个合适的损失函数,并极小化这个损失函数,得到我们的感知机训练模型,以此来确定$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量 $b$。

那我们的第一想法自然是,极小化分错的点数,但是由于我们的点的个数数是离散值,没办法通过求导来优化,所以我们只能选择其他的办法。那么想出感知机算法的大牛用了另一种思路,将所有误分类的点到超平面的距离之和作为误差函数。这样当所有的点都被正确分类之后,就能取到极小值。

那我们又来回忆一下高中的知识,我们用数学公式是怎样表达一个点到直线的距离的?假设直线是$Ax+By+C=0$, 点的坐标是是$(x_i,y_i)$,那么距离的表达就是
$$d=frac{|Ax_i+By_i+C|}{sqrt{A^2+B^2}}$$
那如果我们用之前的$mathbf{w}mathbf{x}+b$来表达这个平面的话,对应下来这个$d$就能被改写成
$$d=frac{|mathbf{w}mathbf{x_i}+b|}{||mathbf{w}||}$$
$||mathbf{w}||$表达的是权值向量的模,也称为二范数。另外对于误分类的点来说,$mathbf{w}mathbf{x_i}+b$ 与 $y_i$是异号的,我们有
$$-y_i(mathbf{w}mathbf{x_i}+b)>0$$
其中$y_i={+1,-1}$,所以距离的表达又可以写为
$$d=frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
考虑全部误分类点到超平面的距离,我们就有
$$d=sum_{x_iin M}frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
不考虑$frac{1}{||mathbf{w}||}$, 就能得到感知机学习算法里的损失函数。

关于为什么可以不考虑前面这一项我找到了如下解释, 供各位参考

统计学习方法第二章:感知机学习算法
参考:https://www.cnblogs.com/huangyc/p/9706575.html


感知机学习算法的原始形式

下面我们来具体讲解感知机学习算法的流程。先从最简单的感知机学习算法开始

给定一个训练数据集
$$T={(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_i,y_i)}$$
其中,$x_iinmathbf{X}=R^n$, $y_iin{-1,1}$,$i=1,2,…,N$, 求参数$w,b, $使其为函数极小化的解
$$min_{w,b}=-sum_{x_iin M}mathbf{w}mathbf{x_i}+b$$
其中$M$为误分类的集合。极小化的方法采用随机梯度下降(stochastic gradient descent)。

首先,任意选取一组超平面参数$w_0$, $b_0$,然后用梯度下降法不断极小化目标函数。极小化过程不是一次使M中所有误分类点梯度下降,而是一次随机选取一个误分类点。


(如果对于梯度下降法不熟悉,有想要了解的话,可以去看知乎中的详细解释
:https://www.zhihu.com/question/305638940)


如果只是想简单理解梯度下降的意思的话,你就想象现在在一个坡上,你想到这个坡的最低点去,那你肯定是要下坡对不对。那换到函数导数(梯度)里面,如果现在这一点的导数(梯度)大于零,函数想要变小,那是不是就得往回走,如果这一点导数小于零,函数想要变小,那就往前走。那么两种情况可以共同表达为:
$$x=x-etanabla_x$$
公式中$eta(0<etaleq1)$是步长,在统计学习中又称为学习率(learning rate)。当到达最小值点,导数(梯度)等于0(在误差范围内),迭代结束。那为啥一定要是梯度方向or反方向呢,因为这样下降得快!

那么回到我们的问题,假设分类点集合M是固定的,那么损失函数$L(w,b)$的梯度表示为:
$$
nabla_w L(w,b)=-sum_{x_iin M}y_ix_i
nabla_b L(w,b)=-sum_{x_iin M}y_i
$$
那么我们每次选取一个误分类点$(x_i,y_i)$,对$w,b$进行梯度更新:
$$
wleftarrow w+eta y_ix_i
bleftarrow b+eta x_i
$$
这样,通过迭代可以期待损失函数L(w,b)不断减小,直到为0。那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P39)。
统计学习方法第二章:感知机学习算法


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

那么有原始形式,肯定会有精进版本,下面讲一下感知机学习算法的对偶形式。

对偶问题这个词来源于凸优化理论,一般是指一个与原问题形式上不同,但最终优化结果实质相同的优化问题。一般我们需要对偶问题,有以下几个方面的考虑:

  1. 提升算法性能(降低原算法的时间复杂度,降低原算法的空间复杂度)
  2. 解决原算法不能解决的问题

在这里感知机的对偶问题主要是为了提升算法性能,加快算法的收敛速度。

统计学习方法第二章:感知机学习算法
那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P44)。

统计学习方法第二章:感知机学习算法

关于原始形式和对偶形式的使用

  • 向量维数(特征数)过高时,计算内积非常耗时,应选择对偶形式算法加速。
  • 在向量个数(样本数)过多时,每次计算累计和就没有必要,应选择原始算法

感知机学习算法的收敛性

算法的收敛性描述了感知机学习算法有效所需要满足的条件
统计学习方法第二章:感知机学习算法

证明见李航《统计学习方法》(第二版)P42

结论说明:当训练数据集线性可分时,误分类的次数是有上界的,说明感知机学习算法原始形式迭代是收敛的。当训练集线性不可分的时候,感知机学习算法不收敛,迭代结果震荡。


第二章 感知机学习算法

界限清晰,才能一分为二,不致混乱


[toc]

引入

感知机学习算法在我眼中其实就是为样本找一条界限,就如同以前地理中所学的,秦岭以北的区域就是北方,以南的区域就是南方。所以在地图上分辨南北,你只要看他在秦岭南边还是北边就好了。那感知机学习算法也是这样,通过训练数据找到最合适的界限,然后就把输入进来的数据一分为二,完成了分类的效果。

所以我们的算法所要完成的就是找到这个界限的数学描述,而这个界限在感知机学习算法里面有个特别高大上的名字”超平面“。

平面就平面,为啥要加个超字呢?而且一开始不是说好是找一条界限的么,那不就是一根线么?

别急,慢慢来,我们刚刚举了一个例子,是在地图上分南北区域。所以我们找的是秦岭那一条线对吧。那要是我让你区分地面以上,地面以下。你是不是就要以地面这个面为界限进行区分。又或者我们回到我们初中的数轴,要你区分正负数的时候,是不是就是找到原点,左边是负数,右边是正数。

所以我们在做分类的时候的界限不一定是一条线,也可能是点,面,甚至是高维空间。所以,我们统一称为超平面。

然后,我们来说感知机学习算法的限制条件,首先,由于我们求解的需要。我们对超平面有一定的限制,就是这个超平面必须要是线性的,比如点,直线,平面这种。 不能是,曲线,圆,球,甚至更加奇怪的界限。所以开始地理上的那个例子其实不太严谨,但是大家意会一下就好啦!

那么超平面做了限制之后,我们对于数据的分布也有一定的限制!就是这些数据一定要是线性可分的。简单来时,就是你一定要能够通过我们之前所说的超平面将其一分为二。 所以我们一般把感知机称为二分类的线性分类模型

好,说了这么多开场白,下面我们就来看看感知机到底是怎么实现的呢?我先带大家捋一遍整个过程,再逐步细化。

假设现在我们有一组线性可分的训练数据集,感知机学习的目标是求得一个能够将训练集的中的两类不同的实例完全正确分开的分离超平面。也就是说感知机的结果是求一个分离超平面的数学表达!,那具体超平面的数学表达是怎么表达的呢?

回顾一下,我们从小对于直线和平面的数学定义:
$$ Ax+By+C=0$$
$$Ax+By+Cz=D=0$$
这里面的不定参数是$A,B,C,D$。如果我们想要得到直线和平面的确切表达,就需要把这里面的A,B,C,D求出来。那我们拓展到任意维平面用$x_i$来表达每一个坐标,用$w_i$来代表每一个坐标前的参数,用$b$来表达常数项。就能得到一个任意维超平面的表达式
$$sum_iw_ix_i+b=0$$
然后更进一步,我们用向量$mathbf{w}={w_1,w_2,w_3…w_i}$, $mathbf{x}={x_1,x_2,x_3…x_i}$,来改写这个式子,我们就能得到
$$mathbf{w} mathbf{x}+b=0$$
$mathbf{w} mathbf{x}$表示两个向量的内积运算,即对应位置坐标相乘再求和。所以感知器学习算法最终想要得到的就是这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量$b$,而专业的叫法称这个向量$mathbf{w}={w_1,w_2,w_3…w_i}$为权值(weight), $b$ 称为偏置(bias).

那假设我已经得到了这个平面之后,我们是不是就需要通过这个平面判定。那我想要判定就得找到一个判定函数呀,比如说我平面上方的点,输入进入这个判定函数之后,能够得到一个值。一个平面下方的点,输入进入这个判定函数之后,就能得到一个另外的值。而且这两个值是很容易区分出来的。所以我们想到了一个非常牛逼的函数:
$$f(x)=sign(x)= begin{cases}
+1 quad xgeq0
-1 quad x<0,
end{cases}$$
$f(x)=sign(x)$是符号函数,如果输入进去的值是非负数,输出值就为1,如果是负数,输出值就为0.
我们把我们的超平面和这个符号函数组合一下就变成
$$f(x)=sign(mathbf{w}mathbf{x}+b),$$
这样我们就能够将数据集的正实例点和负实例点完全划分到超平面的两侧。详细来说就是对于$y_i$=+1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b>0$,对于$y_i$=-1的实例点$i$, 有$mathbf{w}mathbf{x_i}+b<0$.

找到了判定方法,由我们之前的基础知识,我们知道我们需要确定一个学习策略,具体来说就是找到一个合适的损失函数,并极小化这个损失函数,得到我们的感知机训练模型,以此来确定$mathbf{w}={w_1,w_2,w_3…w_i}$,以及标量 $b$。

那我们的第一想法自然是,极小化分错的点数,但是由于我们的点的个数数是离散值,没办法通过求导来优化,所以我们只能选择其他的办法。那么想出感知机算法的大牛用了另一种思路,将所有误分类的点到超平面的距离之和作为误差函数。这样当所有的点都被正确分类之后,就能取到极小值。

那我们又来回忆一下高中的知识,我们用数学公式是怎样表达一个点到直线的距离的?假设直线是$Ax+By+C=0$, 点的坐标是是$(x_i,y_i)$,那么距离的表达就是
$$d=frac{|Ax_i+By_i+C|}{sqrt{A^2+B^2}}$$
那如果我们用之前的$mathbf{w}mathbf{x}+b$来表达这个平面的话,对应下来这个$d$就能被改写成
$$d=frac{|mathbf{w}mathbf{x_i}+b|}{||mathbf{w}||}$$
$||mathbf{w}||$表达的是权值向量的模,也称为二范数。另外对于误分类的点来说,$mathbf{w}mathbf{x_i}+b$ 与 $y_i$是异号的,我们有
$$-y_i(mathbf{w}mathbf{x_i}+b)>0$$
其中$y_i={+1,-1}$,所以距离的表达又可以写为
$$d=frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
考虑全部误分类点到超平面的距离,我们就有
$$d=sum_{x_iin M}frac{-y_i(mathbf{w}mathbf{x_i}+b)}{||mathbf{w}||}$$
不考虑$frac{1}{||mathbf{w}||}$, 就能得到感知机学习算法里的损失函数。

关于为什么可以不考虑前面这一项我找到了如下解释, 供各位参考

统计学习方法第二章:感知机学习算法
参考:https://www.cnblogs.com/huangyc/p/9706575.html


感知机学习算法的原始形式

下面我们来具体讲解感知机学习算法的流程。先从最简单的感知机学习算法开始

给定一个训练数据集
$$T={(x_1,y_1),(x_2,y_2),(x_3,y_3),…,(x_i,y_i)}$$
其中,$x_iinmathbf{X}=R^n$, $y_iin{-1,1}$,$i=1,2,…,N$, 求参数$w,b, $使其为函数极小化的解
$$min_{w,b}=-sum_{x_iin M}mathbf{w}mathbf{x_i}+b$$
其中$M$为误分类的集合。极小化的方法采用随机梯度下降(stochastic gradient descent)。

首先,任意选取一组超平面参数$w_0$, $b_0$,然后用梯度下降法不断极小化目标函数。极小化过程不是一次使M中所有误分类点梯度下降,而是一次随机选取一个误分类点。


(如果对于梯度下降法不熟悉,有想要了解的话,可以去看知乎中的详细解释
:https://www.zhihu.com/question/305638940)


如果只是想简单理解梯度下降的意思的话,你就想象现在在一个坡上,你想到这个坡的最低点去,那你肯定是要下坡对不对。那换到函数导数(梯度)里面,如果现在这一点的导数(梯度)大于零,函数想要变小,那是不是就得往回走,如果这一点导数小于零,函数想要变小,那就往前走。那么两种情况可以共同表达为:
$$x=x-etanabla_x$$
公式中$eta(0<etaleq1)$是步长,在统计学习中又称为学习率(learning rate)。当到达最小值点,导数(梯度)等于0(在误差范围内),迭代结束。那为啥一定要是梯度方向or反方向呢,因为这样下降得快!

那么回到我们的问题,假设分类点集合M是固定的,那么损失函数$L(w,b)$的梯度表示为:
$$
nabla_w L(w,b)=-sum_{x_iin M}y_ix_i
nabla_b L(w,b)=-sum_{x_iin M}y_i
$$
那么我们每次选取一个误分类点$(x_i,y_i)$,对$w,b$进行梯度更新:
$$
wleftarrow w+eta y_ix_i
bleftarrow b+eta x_i
$$
这样,通过迭代可以期待损失函数L(w,b)不断减小,直到为0。那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P39)。
统计学习方法第二章:感知机学习算法


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

那么有原始形式,肯定会有精进版本,下面讲一下感知机学习算法的对偶形式。

对偶问题这个词来源于凸优化理论,一般是指一个与原问题形式上不同,但最终优化结果实质相同的优化问题。一般我们需要对偶问题,有以下几个方面的考虑:

  1. 提升算法性能(降低原算法的时间复杂度,降低原算法的空间复杂度)
  2. 解决原算法不能解决的问题

在这里感知机的对偶问题主要是为了提升算法性能,加快算法的收敛速度。

统计学习方法第二章:感知机学习算法
那么对于感知机算法原始形式的归纳可见下图(摘自李航《统计学习方法》(第二版) P44)。

统计学习方法第二章:感知机学习算法

关于原始形式和对偶形式的使用

  • 向量维数(特征数)过高时,计算内积非常耗时,应选择对偶形式算法加速。
  • 在向量个数(样本数)过多时,每次计算累计和就没有必要,应选择原始算法

感知机学习算法的收敛性

算法的收敛性描述了感知机学习算法有效所需要满足的条件
统计学习方法第二章:感知机学习算法

证明见李航《统计学习方法》(第二版)P42

结论说明:当训练数据集线性可分时,误分类的次数是有上界的,说明感知机学习算法原始形式迭代是收敛的。当训练集线性不可分的时候,感知机学习算法不收敛,迭代结果震荡。


部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 统计学习方法第二章:感知机学习算法求职学习资料
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们