机器学习-支持向量机SVM

支持向量机, 它源于统计学习理论, 是除了集成算法之外, 接触的第一个强学习器

  功能
有监督学习

线性二分类与多分类(Linear Support Vector Classification)

非线性二分类与多分类(Support Vector Classification, SVC)

普通连续型变量的回归(Support Vector Regression)

概率型连续变量的回归(Bayesian SVM)
无监督学习

支持向量聚类(Support Vector Clustering SVC)

异常值检测(One-class SVM)
半监督学习 转导支持向量机(Transductive Support Vector Machines, TSVM)

应用: SVM在各种实际问题中都表现非常优秀, 她在手写识别数字, 和人脸识别中应用广泛, 在文本和超文本分类中举足轻重, 因为SVM可以大量减少标准归纳和转换设置中对标记训练实例的需求, 同时, SVM也被用来执行图像的分类, 并用于图像分割系统, 除此之外, SVM现在已经广泛被用于蛋白质分类, 在生物科学的尖端研究中, 人们还使用支持向量机来识别用于模型预测的各种特征, 从学术的角度来看, SVM是最接近深度学习的机器学习算法

支持向量机分类器的工作原理:

  • 支持向量机的分类方法, 是在这组分布中找出一个超平面, 作为决策边界, 使模型在数据上的分类误差尽量小, 尤其是在未知数据集上的分类误差(泛化误差)尽量小

超平面: 在几何中, 超平面是一个空间的子空间, 它是维度比所在的空间小一维的空间, 入股偶数据空间本身是三维的, 则其超平面是二维的, 则其超平面是一维直线, 在二分类问题中, 如果一个超平面能够将数据划分为两个集合, 其中每个集合中包含单独的一个类别, 我们就收这个超平面是数据的决策边界

我们有B1和B2来两条可能的决策边界, 我们可以把决策B1向两边平移, 直到碰到离这条决策边界最近的方块和圆圈后停下, 形成两个新的超平面, 分别是b11和b12, 并且我们将原始的决策边界移动到b11和b12的中间, 确保B1到b11和b12的距离相等, 在b11和b12中间的距离, 叫做B1这条决策边界的边际(margin),通常记作d, 为了简便, 我们称b11和b12为"虚线超平面", 

 当数据量变大的时候(引入测试集), 我们发现,,拥有更大的边际决策边界在分类中的泛化误差更小, 这一点可以由结构风险最小化定律来证明, 如果边际很小, 则任何轻微扰动都会对决策边界的分类产生很大的影响, 边界很小的情况, 是一种模型在训练集上变现的很好, 却在测试集上表现糟糕的情况, 所以会"过拟合". 所以我们在找寻决策边界的时候, 希望边际越大越好

 支持向量机, 就是通过找出边际最大的决策边界, 来对数据进行分类的分类器, 因此, 支持向量分类器又叫做最大边际分类器

 支持向量机的三层理解

  • 目标是"找出边际的最大决策边界", 听起来是一个十分熟悉的表达, 这是一个最优化问题, 而最优化问题往往和损失函数联系在一起, 和逻辑回归中的过程一样, SVM也是通过最小化损失函数来求解一个用于后续模型使用的重要信息;决策边界
    • 第一层: 定义决策边界的数学表达式, 并基于此表达式定义分类函数, 为寻找最大边际, 引出损失函数 1/2 * || ω ||2         (对于非线性数据, 使用非线性转化来升高原始数据的维度, 使用核函数在低维度空间中进行计算, 以求解出高维度空间中的线性超平面, 添加松弛系数,作为惩罚项, 以允许部分样本点在边界之内存在)
    • 第二层: 为求解能够使边际最大化的W和b,引入拉格朗日因子α, 引入拉格朗日对偶函数, 使求解w和b的过程转化为对α的求解,  使用SMO或梯度下降等方法求解α,在根据α解出w和b,最终找出决策边界
    • 第三层: 能够使用数学完全证明以上两个过程

线性SVM的损失函数

  • 对于二分类标签, 假设每个样本的特征数为2, 则有i = (x1i, x2i, yi)T 分别由我们的特征向量和标签组成, 在平面上以, x2为横坐标, x1为纵坐标, , 所以我们可以定义出决策边界的函数
    • x1 = ax2 + b
    • 变换得:
    •  其中, [a,-1]就是我们的参数向量ω, x就是我们的特征向量, b是我们的截距, 注意, 这个表达式长的非常像我们的线性回归公式, 只不过线性回归中等号一边是标签, 回归后会拟合出一个标签, 而决策边界的表达式中却没有标签的存在, 全部由参数, 特征和截距组成的一个式子, 等号的一边是0
    • 在一组数据下, 给定固定的ω和b, 这个式子就可以是一条固定的直线, 在ω和b不确定的状况下, 这个表达式ωTx + b = 0 就可以代表任意一条直线, 如果在ω和b固定时, 给定一个唯一的x取值, 这个表达式就可以表示固定的一个点, 在SVM中, 我们就使用这个表达式来表示我们的决策边界, 我们的目标时求解能够让决策边际最大化的决策边界, 所以我们要求解参数向量ω和截距b
    • 一个列向量的转置乘以另一个列向量, 可以获得两个向量的点击(dot product), 表示为(ω·(xa -xb)), 两个向量的点积为0, 则说明两个向量的方向时相互垂直的, 又因为xa, xb时一条线上的两个点, 相减后的向量时由xb指向xa, 所以xa - xb的方向是平行于它们所在直线(决策边界), 而ω与xa - xb相互垂直, 所以参数向量ω的方向必然垂直于我们的决策边界
    • 此时, 我们有了我们的决策边界, 任意一个紫色的点xp就可以表示为(由于紫色的点所代表的标签是1, 我们规定,p>0)
      • ω ? xp + b = p
      对于任意一个红色的点xr而言, 我们将表示为(由于红色所代表的标签是-1, 我们规定,r<0)
      • ω ? xr + b = r
    • 核心误区:
      • 注意, 在这里, p和r的符号是我们认为规定的, 如果k和k'是由原来的决策边界平移得到的话, 紫色的点在决策边界上方, ω?x + b = 0应该要向上平移, 直线向上平移的话是增加截距, 应该写成ω?x + b + 正数 = 0
    • 为了推导和计算方便, 我们规定:
      • 标签是{-1.1}, 
      • 决策边界以上的点, 标签都为正, 并且调整ω和b的符号, 让这个点在ω?x+b上得出结果为正
      • 决策边界以下的点, 标签都为负, 并且通过调整ω和b的符号, 让这个点在ω?x+b上得出的结果为负
      • 结论: 决策边界以上的点都为正, 以下的点都为负, 是我们为了计算简便, 而认为规定的, 这种规定不会影响对参数ω和截距b的求解
    • 决策边界的两边要有两个超平面, 这两个超平面在二维空间中就是两条平行线(我们的虚线超平面), 而它们之间的距离就是我们的边际d, 而句测边界位于这两条线的中间, 所以这两条线必然是对称的, 
      • ω?x+b = k,ω?x + b = -k     两边同时除以k得:
      • ω?x + b = 1, ω?x + b = -1     ...........................①
      • 这就是我们平行于决策边界的两条线的表达式, 表达式两边的1和-1分别表示了两条平行于决策边界的虚线到决策边界的相对距离, 此时, 我们可以让这两条线分别过两类数据中距离我们决策边界最近的点, 这些点就被称为"支持向量", 而决策边界永远在这两条线的中间.
    • 线性代数中模唱的运用
      • 向量b除以自身的模长|| b ||可以得到b方向上的单位向量
      • 向量a乘以向量b方向上的单位向量, 可以得到向量a在向量b上的投影长度
    • 所以, 我们将①式中的两式做减法得:
      • ω ? (xp -xr) = 2, 将此式除以|| ω ||得:
      • 自此,我们得到了最大边际关于|| ω ||的表达式, 因此要想求d的最大值, 就求得|| ω ||的最小值, 同时我们可以转为下式, 求ω的最小值
        • 之所以要在模长上加平方,是因为模长的本质是一个距离, 所以它是一个带根号的存在, 我们对它取平方, 式为了消除根号
    • 我们的两条虚线表示超平面, 式数据边缘所在的点, 所以对于人一样本i, 我们可以吧决策函数写作
      • ω?xi + b ≥1  if yi = 1
      • ω?xi + b ≤-1 if yi = -1
    • 整理两个式子可得:
      • 这个式子我们称为函数间隔, 将函数间隔作为条件附加到我们f(ω)上, 我们就得到了SVM的算是函数的最初形态:
    • 函数间隔与几何间隔
      • 函数间隔: 对于给定的数据集T和超平面(ω,b), 定义超平面(ω, b)关于样本点(xi, yi)的函数间隔为
        • γi = yi(ω?xi + b), 这其实式我们虚线超平面的表达式整理过后的式子, 函数间隔可以表示分类预测的正确性以及确信度
      • 在函数间隔的基础上除以ω的模长|| ω ||来得到几何间隔:
        •  几何间隔的本质其实是点xi到超平面(ω, b), 即到我们决策边界(带符号)的距离
    • 重要数学公式补充: 已知直线的表达式, 求, 平面上任一点到直线的距离公式

线性SVM的拉格朗日对偶韩素好和决策函数

  • 我们的损失函数式二次的, 并且我们的损失函数中的约束条件在参数ω和b下式线性的, 求解这样的损失函数被称为"凸优化问题", 拉格朗日乘数法正好可以用来解决凸优化问题, 所以, 使用拉格朗日乘数将损失函数改写形式如下:
    • 其中, αi就叫做拉格朗日乘数,参数向量ω,b, xi式特征矩阵, yi是标签
  • 拉格朗日也分为两部分, 第一部分和我们原始的损失函数一样, 第二部分呈现了我们带有不等式的约束条件, 我们希望L(ω,b,α)不仅能够代表我们原有的损失函数f(ω)和约束条件, 还能够表示我们想要最小化损失函数来求解ω和b的意图, 所以我们要先以α为参数 求解L(ω,b,α)的最大值, 再以ω, b为参数, 求解L(ω,b,α)的最小值, 因此,我们可以写作
  • 拉格朗日函数→拉格朗日对偶函数
    • 对于任何一个拉格朗日函数L(x,α) = f(x) + Σi=1qαihi(x) 都存在一个与它对应的对偶函数g(α), 只带由拉格朗日乘数α作为唯一的参数, 如果L(x,α)的最优解存在并可以表示为minL(x,α), 并且对偶函数的最优解也存在并可以表示为maxg(α), 则我么可以定义对偶差异, 即拉格朗日对偶函数的最优解之间的差值
      • 如果Δ=0, 则称L(x,α)与其对偶函数之间存在强对偶关系, 此时我们就可以通过求解其对偶函数的最优解来替代原始函数的最优解
    • 函数Ld就是我恩的对偶函数, 对所有存在对偶函数的拉格朗日函数我们由对偶差异如下:
      • Δ = minL(x,α) - maxg(x)
    • 则对于我们的L(ω, b,α)和Ld,我们则有:
      • Δ = minmaxL(ω, b, α) - maxLd
    • 我们对L(ω, b, α)求偏导数让偏导数等于0, 所以我们求解对偶函数的过程其实就是在求解L(ω, b,α)的最小值, 所以我们又可以把公式写成:
    • 对偶函数与原始函数转化过程, 我们只需要求解对偶函数的最大值, 就可以求出α, 最终, 目标函数转化为:
    • 一旦我们求得了α值, 我们就可以使用求导后得到的(1)式求解ω, 并可以使用(1)式和决策边界的表达式结合, 得到下面式子


    • 当求得特征向量ω和b, 我们就得到了我们决策边界的表达式, 也就可以利用决策边界和其他有关的超平面进行分类了, 我们的决策函数就可以被写作:
    • 其中xtexst式任意测试样本, sign(h)式h>0时返回1, h<0时返回-1, 的符号函数, 至此, SVM四种相关函数: 损失函数的初始形态, 拉格朗日函数, 拉格朗日对偶函数以及最后的决策函数.

 画决策边界:contour函数

  • Contour是我们专门用来绘制等高线的函数, 等高线本质上是在二维图像上表现三维图像的一种形式, 其中二维x和y式两条坐标轴上的取值, 而Z表示高度, Contour就是x和y构成平面上的所有点中, 高度一致的点连接乘线段的函数, 在同一等高线上的点一定具有相同的Z值, 我们可以利用这个性质来绘制我们的决策边界
scikit-learn

相关

scikit-learn 梯度提升树(GBDT)调参小结

python调用scikit-learn机器学习

（数据科学学习手札138）使用sklearnex大幅加速scikit-learn运算

用scikit-learn学习DBSCAN聚类

标签