首页 > 其他分享 >支持向量机学习笔记--原理篇(一)

支持向量机学习笔记--原理篇(一)

时间:2023-07-10 20:32:02浏览次数:61  
标签:yi xi 函数 -- 分类 学习 感知机 原理篇 向量


支持向量机学习笔记–原理篇(一)

前言

初步学习机器学习给我最大的感受是它背后需要强大的数学知识,理论推导往往能帮助我们理解其本质。而在我看来,单纯的求解数学问题还不够,我们需要有把这部分理论知识运用到实际应用中去的能力。支持向量机(support vector)是机器学习中用来解决监督分类问题的一种方法。

本文致力于把复杂的理论简化到简单的低维情况,配以图的方式对相关理论进行学习性解释。最后再用python语言实现它,以实践的方式,把数学公式应用到计算机编程领域。自知水平有限,大部分内容均是在学习过程中所参考的资料,本文不再重复上述所讲的任何观点以及重证理论公式,只在关键处加入自己的思考,以括号注释,呈现自己思考的过程。

ps:本文假设读者有了一定机器学习的基础,对基本概念均有所了解。

思考

  • 感知机是什么?
  • 支持向量机是什么?
  • 支持向量机是为了解决什么问题而被提出来

感知机

感知机概念

感知机是二元分类中最简单的模型,我们先学习感知机,来慢慢加深对支持向量机的理解。

书本《统计学习方法》定义为:感知机是二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1二值。(注释:输出空间只取+1和-1,这在后续公式推导时有非常大的好处。)感知机对应于输入空间中将实例划分为正负两类的分离超平面,属于判别模型。

简单来说,对于一个二元分类问题,感知机能够根据给定的算法训练出一种线性模型来对数据进行分类的效果。首先我们来看这个函数:


f(x)=wx+b


初中我们就学过这样一条直线所代表的含义,即在X-Y轴上画出一条直线,那么在感知机中它是什么样的物理含义呢?咱们再来看看感知机输入空间到输出空间的映射函数:



f(x)=sign(wx+b)


其中

w和b为感知机模型参数, w∈Rn叫做权值(weight)或权值向量(weight verctor), b∈R叫作偏置(bias), w⋅x表示 w和x的内积。sign是符号函数,即



sign(x)={+1,x≥0or−1,x<0


输入空间到输出空间的映射函数,是感知机的终极模型,因此算法也是建立在该模型上进行探讨的,数据的存在是为了训练模型所定义的参数,而这参数便是

w和b,但仅定义这个模型显然是无法求解参数的,不急,咱们继续看看该函数在三维空间实际的几何图形是什么样的。



明明是二维!怎么是三维呢,其实

f(x)函数所代表的维度为 n+1维,n是特征向量 x的维度,而+1维则代表了输出空间的维度。图中,二维空间向量可以用X表示,其中 Xi=(x1,x2)T表示,第三维我们不以z轴来表示,而是以一种直观的形状来代表。假设负类为小方块,正类为小圆圈。

配上图我们便能理解该模型的物理含义了,大量的数据集表在我们面前,如果它们是线性可分的,那我们就能找到一条直线来区分正类和负类,但实际情况却总是出乎意料,现实世界的复杂程度超过了我们预测,往往数据都是非线性可分的,因此感知机升级到了支持向量机用来解决一些非线性问题,当然支持向量机还不是简单的为解决该问题所存在,后续还会提到。回到上图,当w⋅x+b>0时,代表该点在f(x)的上方,即sign(x)为1。只要找到w,b就能对数据进行二元分类。

感知机学习策略

假设训练数据集是线性可分的,感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为了找出这样的超平面,即确定感知机模型参数w,b需要确定一个学习策略,即定义经验损失函数并将损失函数极小化。

什么!经验损失函数。。。也就是在斯坦福大学机器学习课程中所定义的cost function。联想到实际物理情况中去,经验损失是我们根据已有数据进行拟合后所得出的在大脑中目前最好的“规则引擎”,当遇到类似情况时,我们找到该“规则引擎”对数据做预测or分类。但往往令人遗憾的是,我们涉世未深,所得到的数据只是我们漫长时间线上的很小一部分,该“规则引擎”显然还未拟合的很好,每当出现大量的预测错误时,我们便需要更改我们的规则引擎,怎么变?什么时候变?需要一个衡量标准,那好,把之前的数据拿出来,加上现有数据,我们重新计算一遍平均误差,选择误差最小的代表我们最新的规则引擎。

回归数学,损失函数的一个自然选择是误分类点的总数。但是,这样的损失函不是参数w,b的连续可导函数,不易优化。损失函数的另一个选择是误分类点到超平面S的总距离,这是感知机所采用的,为此,首先写出输入空间Rn中任一点x0到超平面S的距离:


1∥w∥|w⋅x0+b|


这里,

∥w∥是 w的L2范数。


抛开高级范数定义,上述公式就是中学所学过的一个点到直线的距离。其次,对误分类的数据

(xi,yi)来说,



−yi(w⋅xi+b)>0

成立。因为当w⋅xi+b>0,yi=−1,而当w⋅xi+b<0时,yi=+1.因此,误分类点xi到超平面S的距离是



−1∥w∥yi(w⋅xi+b)

这样,假设超平面S的误分类点集合为M,那么所有误分类点到超平面S的总距离为



−1∥w∥∑xi∈Myi(w⋅xi+b)

不考虑1∥w∥,就得到感知机学习的损失函数。

给定训练数据集


T={(x1,y1),(x2,y2),...,(xN,yN)}

其中,xi∈Rn,yi∈Y={+1,−1},i=1,2,3,...N.感知机sign(w⋅x+b)学习的损失函数定义为



L(w,b)=−∑xi∈Myi(w⋅xi+b)

其中M为误分类点的集合。这个损失函数是感知机学习的经验风险函数。

显然,损失函数L(w,b)是非负的。如果没有误分类点,损失函数值是0。(正确分类点不记录损失函数的点集合)而且,误分类点越少,误分类点离超平面越近,损失函数值就越小。一个特定的样本点的损失函数:在误分类时是参数w,b的线性函数,在正确分类时是0。因此,给定训练数据集T,损失函数L(w,b)是w,b的连续可导函数。

感知机学习算法

上节给出了具体的损失函数


L(w,b)=−∑xi∈Myi(w⋅xi+b)

一个很直观的想法便是求解该损失函数的极小值,即可表示为



minL(w,b)=−∑xi∈Myi(w⋅xi+b)

感知机学习算法是误分类驱动的,具体采用随机梯度下降法。首先,任意选取一个超平面w0,b0,然后用梯度下降法不断地极小化目标函数。极小化过程中不是一次使用M中所有误分类点的梯度下降,而是一次随机选取一个误分类点使其梯度下降。(有关梯度下降算法,看最近能否找到相关资料,重新开篇文章进行讲解,这里直接给出w,b的更新公式,因为我只知道了该公式的形式化解释,随机梯度下降和所有误分类点的梯度下降在书中并没有找到相关联系)

随机选取一个误分类点(xi,yi),对w,b进行更新:



w←w+ηyixi



b←b+ηyi

式中η(0<η≤1)是步长,在统计学习中又成为学习率。这样通过迭代可以期待损失函数L(w,b)不断减小,直到为0。综上所述,得到如下算法:
算法:(感知机学习算法的原始形式)

输入:训练数据集T={(x1,y1),,(x2,y2),...(xN,yN)},其中xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N;学习率η(0<η≤1);
输出:w,b;感知机模型f(x)=sign(w⋅x+b);
(1)选取初值w0,b0
(2)在训练集中选取数据(xi,yi)
(3)如果yi(w⋅xi+b)≤0

w←w+ηyixi

b←b+ηyi

(4) 转至(2),直至训练集中没有误分类点


这里采用了随机梯度下降算法,即在更新w,b时,只单独计算了某个(xi,yi)点。那为什么这样的更新算法便能找到L(w,b)的极小值呢?

步骤1、2可以忽略不看,重点关注步骤3。判别式yi(w⋅x+b)≤0是用来删选所有误分类点,然后根据误分类点做w,b的数值更新。

观察判别式yi(w⋅xi+b)≤0,我们能发现什么几何含义呢?我们根据yi进行分类,当yi=+1时,符合判别式的xi的情况为(w⋅xi+b)≤0;同理,当yi=−1时,符合判别式的xi的情况为(w⋅xi+b)≥0.我们记margin=w⋅xi+b.

在二维坐标轴上容易观察出,实际坐标距离为


realmargin=1∥w∥|w⋅xi+b|.


因此忽略系数

1∥w∥,margin可以理解为实际的误分类点离我们所假设直线的误差距离。在直线上方,margin为正,在直线下方margin为负。

因此很容易想到,误差距离是所有误分类点形成的距离,那么根据每一个误差分类点,如果margin为正,就应该使margin变为负,如果margin为负,应该使margin为正。总结一句话,针对所有误分类点,更新w,b,使得margin应该朝相反方向发生变化。即正变负,负变正。

好,有了这样简单的规律总结,我们便需要构造这样的更新式了,我们直接给出结论,证明它的确符合上述规律即可。式为:


w←w+ηyixi


b←b+ηyi



w,b只是根据原来的值,加上误分类点值做了更新。先来看 b的变化情况,η在区间[0,1]之间,因此 b和 yi之间关系即为反向关系(你增我减,你减我增,跟你势不两立!),代入margin,得



marginnew=w⋅xi+bold+ηyi


marginold=w⋅xi+bold

marginnew和marginold符合反向变化关系。同理,来看看w的变化情况,代入magrin得


marginnew=wold⋅xi+ηyixixTi+b


marginold=wold⋅xi+b

同样的marginnew和marginold符合反向变化关系。综上所述,对于所有的误分类点,如果margin不符合条件,我们便让它反向变化一次,当然针对同一个误分类点,我们可以让它变化n次,直到符合判别式条件。如果遇到线性不可分问题,那么该算法也将无解。

Python实现

参考《机器学习实战》中的代码,单独开一章来剖析SMO算法的具体实现。老规矩,看代码之前先看数据。

训练集:training.data
每个实例就是一个二维向量和一个±1的label:

3.542485  1.977398  -1
3.018896  2.556416  -1
7.551510  -1.580030 1
2.114999  -0.004466 -1
8.127113  1.274372  1
7.108772  -0.986906 1
8.610639  2.046708  1
2.326297  0.265213  -1
3.634009  1.730537  -1
0.341367  -0.894998 -1

初始化代码如下:

if __name__=="__main__":
    """
      加载数据集
      :param fileName:
      :return:
    """
  if len(sys.argv)!=4:
    print "Usage:python perceptron.py n trainFile modelFile"
    exit(0)
  eta = float(sys.argv[1])
  trainFile =file(sys.argv[2])
  modelFile =file(sys.argv[3],'w')

  lens =0

  for line in trainFile:
    chunk = line.strip().split(' ')
    lens = len(chunk)-1 #feature X lens
    tmp_all =[]
    tmp =[]
    for i in range(1,lens+1):
      tmp.append(float(chunk[i]))
    tmp_all.append(tmp)
    tmp_all.append(float(chunk[0]))
    training_set.append(tmp_all)
  trainFile.close()
  for i in range(lens):
    w.append(0)
  for i in range(1000):# iterator 1000
    check()
  print "The training_set is not linear separable."

w,b更新:

def update(item):
  global w,b,lens,eta
  for i in range(lens):
    w[i] =w[i]+eta*item[1]*item[0][i]
  b = b+ eta*item[1]
  print w,b

L(w,b)=−∑xi∈Myi(w⋅xi+b)误差函数计算:

def cal(item):
  global w,b
  res =0
  for i in range(len(item[0])):
    res += item[0][i]*w[i]
  res +=b
  res *=item[1]
  return res

判别式yi(w⋅xi+b)≤0判断:

def check():
  flag =False
  for item in training_set:
    if cal(item) <=0:
      flag = True
      update(item)
  if not flag: #False
    print "RESULT:W:"+str(w)+"b:"+str(b)
    tmp=''
    for keys in w:
      tmp +=str(keys)+' '
    tmp = tmp.strip()
    modelFile.write(tmp+'\n')
    modelFile.write(str(b)+'\n')
    modelFile.write(str(lens)+'\n')
    modelFile.write(str(eta)+'\n')
    modelFile.close()
    os._exit(0)
  flag =False

至此,感知机的基本原理和代码实现已基本讲解完成,在下篇中将继续学习感知学习算法的对偶形式,该对偶形式目测能够与支持向量机形成一些有趣的对比,待学习…

最后来一句废话吧,不积跬步,无以至千里;不积小流,无以成沧海。

参考文献及推荐阅读

  • 感知机(python实现)
  • 李航. 统计学习方法[M]. 北京:清华大学出版社,2012


标签:yi,xi,函数,--,分类,学习,感知机,原理篇,向量
From: https://blog.51cto.com/u_16184402/6680340

相关文章

  • Linux 内核0.11 系统调用详解(上)
    备注:本文通过三个问题,引出Linux内核0.11的系统调用。操作系统为什么要引出系统调用?回答这个问题前,请先参看如下图:由图可以看出,从操作系统的角度来看,一台计算机主要分为两级:用户级以及内核级,系统调用主要作用就是连接用户级和内核级的“插座”。上层用户的许多对计算机硬件的操作,......
  • 使用递归函数来实现输入正整数,将正整数分解鸡(质因)数
    介绍一下递归函数:当我们定义一个函数时,如果函数内部调用了自身,那么这个函数就称为递归函数。递归函数是一种解决问题的方法,它将大问题分解为相同或类似的小问题,并通过逐步解决这些小问题来解决整个问题。使用递归函数的核心思想是将一个问题拆解为更简单的子问题,并且解决子问题的方......
  • 字符的格式化
    #请实现一个程序,实现如下需求点:#1.程序开始的时候提示用户输入学生年龄信息格式如下:#MikeMos,9;JackGreen,21#我们假设用户输入上面的信息,必定会遵守下面的规则:#学生信息之间用分号隔开(分号前后可能有不定数量的空格)#每个学生信息里的姓名和年岭之间用......
  • C#开发ESP32E(3)Wifi配置使用
    1.安装Wifi配置库(nanoFramework.System.Device.Wifi)1.1nanoFramework.System.Device.Wifi介绍API预览--地址:https://docs.nanoframework.net/api/System.Device.Wifi.html该库可配置ESP32使用Wifi模块进行通信与Wifi建立连接有如下步骤:创建Wifi适配器扫描Wifi列表......
  • 2023年7月10日 天气:晴
       今天早上起来背了20个英语单词,然后学习了一个小时的Java编程,接下来就看了一会构建之法。最后就是写了一会pta上的作业。  明天打算6点起床然后晨跑半小时,然后编程一小时。再就是出去打会羽毛球。再就是看会英语阅读。......
  • Windows计算机如何在线打开Sketch文件?
    自Sketch诞生以来,只有Mac版本。Windows计算机如何在线打开Sketch文件?即时设计已经解决了你遇到的大部分问题,不占用内存也是免费的。您可以使用此软件直接在线打开Sketch文件,完整预览并导出CSS、SVG、PNG等,还具有编辑功能! 如何导入Sketch文件?如果需要切换设计工具,能够......
  • Linux部分常用零碎命令
    1:开放一具体端口firewall-cmd--zone=public--add-port=8888/tcp--permanent #开放8888端口2:关闭一具体端口firewall-cmd--zone=public--remove-port=8888/tcp--permanent #关闭8888端口3:重启后防火墙生效firewall-cmd--reload #配置立即生效......
  • 《代码中的软件工程》学习总结及心得体会
    本学期我选修了孟宁老师开设的《高级软件工程》课程,作为一名软件工程专业的学生,本课程的内容以及《代码中的软件工程》一书让我受益匪浅。在课程以及书本内容中,我了解到软件工程的概念和重要性。软件工程是一门研究如何以系统化、规范化和可量化的方式开发和维护软件的学科。通过......
  • 电脑使用管理
    1、电脑使用管理2、桌面管理:干净整洁、文件夹管理、不常用软件隐藏3、磁盘管理:cclean、分盘cd4、常用软件:软件安装到d盘Install文件夹、c盘平时不要动警告:必须卸载360、鲁大师图像:quicker(工具箱)、snispaste(截屏)、ps、cdr视频:splayer(播放器)、剪应(视频)、An(动画)数据:origin(数据......
  • 【DS】P9062 [Ynoi2002] Adaptive Hsearch&Lsearch(区间最近点对)
    ProblemLink给定平面上\(n\)个点,\(Q\)次询问编号在\([l,r]\)内的点的最近点对。\(n,Q\le2.5\times10^5\)。技巧:平面网格化乱搞都是错的。看见欧几里德距离,想到平面网格化。考虑一个平面最近点对的网格化做法:随机点的顺序,按顺序依次考虑,考虑到第\(i\)个点时,设当前最......