机器学习札记8——感知机

浏览: 1300

感知机Perceptron

导读

感知机是二分类的线性分类模型,输入是实例的特征向量(每个属性),输出是实例的类别。感知机对应于输入空间中将实例划分为正负两类的分离超平面,属于判别模型。

  • 目的:找出将训练数据进行线性划分的分离超平面
  • 导入基于误分类的损失函数,利用梯度下降法对损失函数进行极小化,求出最小值
  • 原始形式对偶形式两种
  • 感知机是种线性分类模型,属于判别模型。

感知机原理剖析及实现

应用实例

比如说我们有一个坐标轴(图中的黑色线),横的为x1轴,竖的x2轴。图中的每一个点都是由(x1,x2)决定的。

  • 如果我们将这张图应用在判断零件是否合格上,x1表示零件长度,x2表示零件质量,坐标轴表示零件的均值长度和均值重量,并且蓝色的为合格产品,黄色为劣质产品,需要剔除。
  • 那么很显然如果零件的长度和重量都大于均值,说明这个零件是合格的。也就是在第一象限的所有蓝色点。反之如果两项都小于均值,就是劣质的,比如在第三象限的黄色点。
  • 在预测上很简单,拿到一个新的零件,我们测出它的长度x1,质量x2,如果两项都大于均值,说明零件合格。这就是我们人的人工智能。




    image.png

定义

现在假设输入空间是X\subseteq{R^n},输出空间Y=\{+1, -1\}。输入x\in X表示实例的特征向量,输出y\in Y表示实例的类别,其中输入到输出的函数表示如下:f(x)=sign(w.x+b),称为感知机

  • w,b称为感知机模型参数w称为权值或者权值向量b\in R称为偏置biasw \bullet x表示二者的内机,sign表示符号函数:
    sign(x)= \begin{cases} +1, & {x \geq 0} \\ -1, & {x \leq 0} \end{cases}

感知机的几何解释为线性方程:w \bullet x+b=0这条直线就是最好的那条线,最优解。特征空间R^n对应一个超平面S,其中w是超平面的法向量b是超平面的截距。超平面将特征空间划分为两个部分。位于两部分的点分为正负两个类别。正类为+1,父类为-1。

栗子(图2.1):

image.png

策略

给定一个数据集T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}其中x_i是输入空间实例的特征向量,y_i是实例的输出类别,如果存在超平面S满足将数据集的正负实例完全分开,即满足:当w.x_i+b>0 ,有y_i=+1;当w.x_i+b<0 ,有y_i=-1。此时,将所有的数据分为线性可分数据集,否则称为线性不可分。

  • 感知机中的损失函数误分类点到超平面S的总距离,输入空间中任意一个点x_0到距离是\frac{1}{||w||}{(w.x_0+b)},其中||w||表示w的L_2范数,即:||w||=\sqrt{w_1^2+w_2^2+...+w_n^2}对于误分类的点,总有如下结论:-y_i(w.x_i+b)>0因为在误分类的时候,每个实例点满足:当w.x_i+b>0 ,有y_i=-1;当w.x_i+b<0 ,有y_i=+1。因此,误分类的点到超平面的距离:-\frac{1}{||w||}{y_i}{(w.x_0+b)},假设超平面中的所有误分类的集合M,所有误分类的点到S的总距离为:-\frac{1}{||w||}\sum_{x_i \in M}{y_i}{(w.x_0+b)},不考虑-\frac{1}{||w||}得到了感知机f(x)=sign(w.x+b)的损失函数为:L(w,b)=\sum_{x_i \in M}{y_i}{(w.x_0+b)}
  • M是误分类点的集合
  • 损失函数就是感知机学习的经验风险函数
  • 梯度只是向量,代表下降的方向
  • 通过学习率来控制下降的大小
  • 如果没有误分类点,损失函数是0
  • 误分类点越少,总距离越小,损失函数越小
  • L是参数(w,b)的连续可导函数

算法

原始形式

算法思想

感知机学习算法的最优化问题就是求解损失函数的最小值,即:\mathop {\min \limits_{w,b}L(w,b)}=\sum_{x_i \in M}{y_i}{(w.x_0+b)}。感知机的算法是误分类驱动的,具体采用的是随机梯度下降法(stochastic gradient descent),大致过程如下:

  • 选取任意的超平面w_0,b_0
  • 利用梯度下降方法去不断地极小化目标损失函数L(w, b)
  • 在不断极小化的过程中,不是一次性使用M中所有误分类点进行梯度下降,而是一次随机选取一个误分类点进行梯度下降。
  • 损失函数L(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}
    每次随机选取一个误分类点(x_i, y_i),对w, b进行更新:w\gets{w+\eta{y_ix_i}}b\gets{b+\eta{y_i}}其中\eta\in{(0,1]}表示学习率或者步长。通过不断地迭代损失函数L(w,b)使其不断的减小,直至为0

算法描述

输入:训练数据集T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},其中x_i\in X=R^n,y_i \in Y=\{-1, +1\}, i=1,2,....,N;学习率0 < \eta \leq 1

输出:w,b;感知机模型f(x)=sign(w.x+b)

  • 选取初值w_0,b_0,一般是0
  • 在训练集中选取数据(x_i,y_i)
  • 如果存在误分类点,即满足:-y_i(w.x_i+b)\geq {0}或者y_i(w.x_i+b)\leq {0},进行(w,b)的更新:w\gets{w+\eta{y_ix_i}}b\gets{b+\eta{y_i}}
  • 转到第二步,直至训练集中没有误分类点停止

直观解释:当有一个误分类点在超平面的错误一侧,调整w,b的值,使得分离超平面向着该误分类点的一侧移动,从而较小误分类点和超平面的距离,直至超平面越过该点,使其被正确地分类

栗子(2.1):

image.png

image.png

image.png

image.png

对偶形式

算法思想

对偶形式的基本思想是将w,b表示为实例x_i和输出类别y_i的线性组合的形式,通过求解系数从而求得wb

假设w,b的初值是都是0,对于误分类点通过:w\gets{w+\eta{y_ix_i}}b\gets{b+\eta{y_i}}逐步地去修改w,b,设修改n次,则w,b关于(x_i,y_i)的增量分别是\alpha _iy_ix_i\alpha_iy_i,其中\alpha_i=n_i\eta,通过不断地迭代过程,最终学习到的w,b分别表示为:w=\sum _{i=1}^{N}\alpha _iy_ix_ib=\sum _{i=1}^{N}\alpha _iy_i

在上面两个迭代式子中,\alpha_i \geq{0}, i=1,2,....N;当\eta=1时,表示第i个实例点由于误分类而进行更新的次数。

算法描述

输入:给定线性可分的训练数据集T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},其中x_i\in X=R^n,y_i \in Y=\{-1, +1\}, i=1,2,....,N;学习率0 < \eta \leq 1

输出:\alpha, b;感知机模型f(x)=sign(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)其中,\alpha=(\alpha_1,....,\alpha_N)^T;训练过程为:

1.给定初值\alpha \gets 0,b\gets0

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

3.如果y_i(\sum _{j=1}^{N}{\alpha_jy_jx_j}.x+b)\leq 0,进行(w,b)的更新:\alpha \gets{\alpha_i+\eta}b\gets{b+\eta{y_i}}
4.转到第二步,直至训练集中没有误分类点停止

对偶形式中训练实例仅仅是以内积的形式出现,著名的Gram矩阵G=[x_i\bullet y_i]_{N\times N}

栗子(2.2):

image.png

image.png

算法收敛性

对于原始形式的感知机学习算法,经过有限次迭代之后可以得到一个将训练数据集完全分离的超平面和感知机模型。为了证明过程方便,将偏置b加入权重w中,记作\hat w=(w^T,b)^T,同样的输入向量中也加入常数1,记作\hat x=(x^T, 1)^T。显然有:\hat x \in R^{n+1},\hat w \in R ^{n+1},则\hat w \bullet \hat x=w \bullet x+b,具体证明过程加入下图:

image.png

image.png

image.png

image.png

image.png

推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册