精华内容
下载资源
问答
  • 非线性可分数据最优超平面的构建

    千次阅读 2015-07-11 16:42:39
    一、非线性可分数据最优超平面的构建 二、近期总结 近两周参加学校电子设计大赛的选拔赛和加强英语四级,主要仔细阅读了svm算法比较详细的ppt,工作没有取得进展。 ...

    一、非线性可分数据最优超平面的构建





    二、近期总结

    近两周参加学校电子设计大赛的选拔赛和加强英语四级,主要仔细阅读了svm算法比较详细的ppt,工作没有取得进展。

    http://wenku.baidu.com/link?url=6kGDCyqkr9qxMOmJ8xXmJLn8iGmnsooSJoaY4oZRkMpcX6ZfrsuRzFWjmFQZjzMCTrkcVQxD4tnyBxMaSDoWu8MLwqxJ5Y2NAsv_bmJVHda
    展开全文
  • 对于SVM支持向量点的计算、其最优分类面、最优超平面的理论、计算的方法
  • SVM理论之最优超平面

    千次阅读 2013-06-08 00:36:00
    最优超平面(分类面)  如图所示, 方形点和圆形点代表两类样本, H 为分类线,H1, H2分别为过各类中离分类线最近的样本且平行于分类线的直线, H1、H2上的点(xi, yi)称为支持向量, 它们之间的距离叫做分类间隔...

    最优超平面(分类面)

     

     

      如图所示, 方形点和圆形点代表两类样本, H 为分类线,H1, H2分别为过各类中离分类线最近的样本且平行于分类线的直线, H1、H2上的点(xi, yi)称为支持向量, 它们之间的距离叫做分类间隔(margin)。中间那条分界线并不是唯一的,我们可以把它稍微旋转一下,只要不分错。所谓最优分类面(Optimal Hyper Plane)就是要求分类面不但能将两类正确分开(训练错误率为0),而且使分类间隔最大。推广到高维空间,最优分类线就变为最优分类面。支持向量是那些最靠近决策面的数据点,这样的数据点是最难分类的,因此,它们和决策面的最优位置直接相关。

      我们有两个 margin 可以选,不过 functional margin 明显是不太适合用来最大化的一个量,因为在 hyper plane 固定以后,我们可以等比例地缩放 w 的长度和 b 的值,这样可以使得 f(x)=wTx+b 的值任意大,亦即 functional margin γf可以在 hyper plane 保持不变的情况下被取得任意大,而 geometrical margin γg则没有这个问题,因为除上了 ∥w∥ 这个分母,所以缩放 w 和b 的时候γg的值是不会改变的,它只随着 hyper plane 的变动而变动,因此,这是更加合适的一个 margin 。对一个数据点进行分类,当它的 margin 越大的时候,分类的 置信度(confidence) 越大。对于一个包含 n 个点的数据集,我们可以很自然地定义它的 margin 为所有这 n 个点的 margin 值中最小的那个γg=minγg,i,于是,为了使得分类的 confidence 高,我们希望所选择的 hyper plane 能够最大化这个 margin 值。简要地说,就是找到这样一个最优分类面,使离最优分类面最近的点的几何距离最大。即最优分类面的目标函数为:

       max γ,  s.t.  yi(wT ·xi+b) = γg,i  >=  γg,i=1,…,n                                                                    (4)

     

    其中γg=  由于我们的目标就是要确定超平面,求max γg ,因此可以把无关的变量固定下来,固定的方式有两种:一种是固定 ∥w∥,另一种是固定 γf. 处于方便推导和优化的目的,我们选择第二种,令γf=1 ,则我们的目标函数化为:

        max,    s.t. , yi(wTxi+b)≥1, i=1,…,n                   (5)

    H1和H2到最优分类面H的距离相等,都等于γg.

     

              图3

     

    最优超平面的详细推导

     

      考虑训练样本{xi, yi}Ni=1, 其中xi 是输入模式的第i 个样本,yi∈{-1,+1}。设用于分离的超平面方程是g(x)=wT·x + b =0; 其中w 是超平面的法向量,b 是超平面的常数项. 现在的目的就是寻找最优的分类超平面,即寻找最优的w 和b。求这样的g(x)的过程就是求w(一个n维向量)和b(一个实数)两个参数的过程(但实际上只需要求w,求得以后找某些样本点代入就可以求得b)。因此在求g(x)的时候,w才是变量。设最优的w 和b 为w0 和b0,则最优的分类超平面为: w0 T·x + b0 =0;若得到上面的最优分类超平面,就可以用其来对测试集进行预测了。设测试集合为{ti} Ni=1,则用最优分类超平面预测出的测试集的标签为:

            ti_label = sgn(w0 · ti + b0).

    SVM 的主要思想是建立一个超平面作为决策曲面, 使得两类之间的隔离边缘被最大化。求最优分类超平面等价于求最大几何间隔,由上式可知也等价于||w||的最小值。

     

    设固定函数间隔为1,则支持向量为

        H2: wT·xi + b = -1, yi = -1 或者H1: wT·xi +b = +1, yi = +1

    设图3上H1、H2上各有一点,分别为x1,x2; 则wT·x1 + b=1 , wT·x2 + b=-1

                         => wT·(x1- x2)=2 => 两类几何间隔( x1- x2) =

    max     <=>   min ||w||  <=>  min  1/2 * ||w||2 ;                                                                            (6)

    对于任意的(xi, yi), 有 wT·xi+b<=-1, yi=-1或者wT·xi+b>=1, yi=1,即yi (wT·xi +b)>=1。

    故寻找最优超平面即正反两类间隔最大化问题, 最终归结为一个带约束的二次凸优化问题(这种问题可以用任何现成的 QP (Quadratic Programming) 的优化包进行求解。):

        min 1/2 * ||w||2, s.t. ,  yi (wT·xi +b)>=1,(i=1,2…n,n为样本数)                                                             (7)

    虽然这个问题确实是一个标准的 QP 问题,但是它也有它的特殊结构,通过 拉格朗日对偶(Lagrange Duality) 变换到对偶变量 (dual variable) 的优化问题之后,可以找到一种更加有效的方法来进行求解——这也是 SVM 盛行的一大原因,通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。

     

    使用Lagrange 乘子法可解决二次规划问题:

    1)首先建立Lagrange 函数:

      L(w,b,α)=||w||2-∑αi[yi (wT·xi +b)-1] i=1,2...n                                       (8)

      令θp(w)=mαx L(w,b,α)  s.t. αi>=0 ,  原问题即求min θp(w)=min max L(w,b,α)=p*; s.t. αi≥0

      对偶问题(交换min,max顺序): θD(w) = max αi≥0 min L(w,b,α)=d*

          显然d* <= p*,可以理解为最大值中最小的一个总比最小值中最大的一个要大。

    2)L对w 和b分别求偏导并置零,求得w=∑αi·yi·xi, ∑αiyi =0;

    3)再整理L 最终可以得到关于原问题的对偶变量α的优化问题:

         max L(w,b,α)=∑αi- 1/2 * ∑Ni=1Nj=1 αiαjyiyjxiTxj ,     s.t.,  ∑αiyi =0; αi>=0

       此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b。

    4) 求解出求偶问题的最优解(该问题用SMO算法来求解), 设用α·i 表示最优的Lagrange 乘子,则此时原问题的最优解为:

         w0 = ,b0=yj-, 任意 j;

        g(x)=<w0,x>+b=<,x>+b = ∑Nj=1 αiyi<xi,x>+b                              (9)

      则判决函数为:f(x) = sgn(∑w0x+b0), 其中x 为测试集中的样本.

      也就是说,以前新来的要分类的样本首先根据w和b做一次线性运算,然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了,我们不需要求出w,只需将新来的样本和训练数据中的所有样本做内积和即可。这一点至关重要,是之后使用 Kernel 进行非线性推广的基本前提。那么与前面所有的样本都做运算是不是太耗时了?答案是不会,由(8)式可知,对于支撑向量函数间隔等于1,对于非支持向量,函数间隔γf,而αi非负,为了满足最大化,α必须等于 0 。可见,内积运算仅与支持向量有关,可大大降低运算复杂度。

    转载于:https://www.cnblogs.com/Seiyagoo/archive/2013/06/08/3125497.html

    展开全文
  • 文章目录简介原理内容框架详细学习最优超平面支持向量线性可分定义最优化问题拉格朗日乘子法强对偶性线性不可分(部分)软间隔线性不可分(完全)核函数核函数的作用常见核函数优缺点 简介 原理 内容框架 详细...

    简介

    在这里插入图片描述

    原理

    在这里插入图片描述

    内容框架

    在这里插入图片描述

    详细学习

    最优超平面

    在这里插入图片描述

    支持向量

    在这里插入图片描述

    线性可分

    定义

    在这里插入图片描述

    最优化问题

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    拉格朗日乘子法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    强对偶性

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    线性不可分(部分)

    在这里插入图片描述
    在这里插入图片描述

    软间隔

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    线性不可分(完全)

    核函数

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    核函数的作用

    在这里插入图片描述
    在这里插入图片描述

    常见核函数

    在这里插入图片描述

    优缺点

    在这里插入图片描述

    展开全文
  • The issue at hand is to find the parameters wo and bo for the optimal hyperplane, given the training set {(xi,di)}. 转载于:https://www.cnblogs.com/donggongdechen/p/9943603.html

     The issue at hand is to find the parameters wo and bo for the optimal hyperplane, given the training set {(xi,di)}.

    转载于:https://www.cnblogs.com/donggongdechen/p/9943603.html

    展开全文
  • matlab可以用 -Conjugate gradient -BFGS -L-BFGS 等优化后的梯度方法来求解优化问题。当feature过多时,最小二乘计算复杂度过高(O(n**3)),... 来求解最优问题了。 注:返回值中的exitFlag表示是否收敛 时间: 11-12
  • 是的,咱们第1篇blog介绍了目标;...今天这个部分主要目的是和大家一起来看看,选择最优超平面的推理过程。 以下是本篇的一个简短目录: 如何找到最优超平面 如何计算两超平面间的距离 SVM的最优化问题是什么
  • 在回顾支持向量机方法的基础上,从数学上严格地证明了特征空间上最优分类超平面的几何意义。
  • SLIC与目前最优超像素算法的比较

    千次阅读 2018-08-09 15:57:43
    SLIC与目前最优超像素算法的比较 Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk 摘要 近年来,计算机视觉应用越来越依赖超像素,...
  • SLIC与目前最优超像素算法的比较 Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk 摘要 近年来,计算机视觉应用越来越依赖超像素,但并不总是清楚什么是...
  • 研究了半天,终于对“超平面”有... n 维空间中的超平面由下面的方程确定: 其中,w 和 x 都是 n 维列向量,x 为平面上的点,w 为平面上的法向量,决定了超平面的方向,b 是一个实数,代表超平面到原点的距离。且 ...
  • 根据样本的不平衡性进行超平面的相对偏移,使得当前超平面向理论的最优超平面移动,以此为基础进行相关反馈,并根据反馈结果运用超平面三原则对当前的偏移超平面再进行偏移,以解决图像的视觉多样性问题,从而得到...
  • 本文研究了运用最优调节器设计原理与闭环系统最优性须域条件确定线性二次型性能指标下清模变结构系统的最优超平面参数拒阵的设计问题,并以例说明了此设计方法相对于极点配置法的优越性。
  • 支持向量机SVM 前提概念 首先从字面的意思来看一下支持向量机,机即machine,也就是算法,...若存在a≠0,a\neq0,a̸​=0,满足对于任意的x∈Cx\in Cx∈C,都有aTx≤aTx0a^Tx\le a^Tx_0aTx≤aTx0​成立,则称超平面...
  • 超平面

    千次阅读 2013-05-24 19:23:42
    超平面 数学中超平面是n维欧氏空间中余维度等于一的线性子空间。这是平面中的直线、空间中的平面之推广。设F为域(为初等起见,可考虑)。n维空间F中的超平面是由方程定义的子集,其中是不全为零的常数。在...
  • 如何定义两个集合的最优分隔超平面呢? 找到集合"边界"上的若干点,以这些点为基础计算超平面的方向,以二维坐标平面为例子wTx+b=0w^Tx+b=0wTx+b=0,当系数wTw^TwT确定的时候,这个超平面的方向也就随之确定,以两...
  • 超平面的定义

    千次阅读 2017-10-18 08:26:49
    研究了半天,终于对“超平面”有了个初步了解。  n 维空间中的超平面由下面的方程确定:  其中,w 和 x 都是 n 维列向量,x 为平面上的点,w 为平面上的法向量,决定了超平面的方向,b 是一个实数,代表超平面到...
  • 高光谱遥感影像SVM分类中训练样本选择的研究,王晓玲,杜培军,支持向量机(SVM)分类的关键是发现分类最优超平面及类别间隔,而混合像元比纯净像元更接近类别边界,更容易找出最优超平面。针对
  • 超平面:类似与一维直线上的点(0维),二维平面上的直线(1维),三维空间上的平面(2维),但是超平面一定过原点,所以,它(k-1 dim)可以将k dim空间平分成均匀的两份。 超平面公式:假设超平面法向量为,超...
  • SVM的分类超平面的数学推导

    千次阅读 2018-10-25 01:31:02
    间隔最大的为所求最优超平面 max min y(w^T+b)/||w|| , 即求: arg&amp;amp;amp;amp;amp;amp;amp;nbsp;maxwT,b{minx&amp;amp;amp;amp;amp;amp;amp;nbsp;yi×(wTxi+b)1∣∣w∣∣},yi即labeli arg \space \...
  • 支持向量机考虑以下的两类训练样本集特征1特征2类标11+22+20+00-10-01-(1) 在图中画出这6个训练样本点和支持向量机对应的最优超平面(决策边界),并写出对应的超平面方程;(2) 假设增加一些训练样本点,这些...
  • SVM-支持向量机原理详解与实践之二   SVM原理分析 以下内容接上篇。 ... 拉格朗日对偶性(Largrange...所以以下可以将寻找最优超平面二次最优化(原问题),总结为以下几个步骤: 在原始权重空间的带约束的优...
  • 超平面思想推导

    2020-03-05 14:40:49
    超平面数学解释 w™x+b=0 ™是转置的意思,找不到别的符号了QAQ w是权重(weight)(列向量),是一个向量; x是特征向量(列向量),比如一个对象有两个特征,那么x=[x₁,x₂] 这时我们说x的维度是2; w的维度与x的维度...
  • 支持向量鉴别分析(support vector discriminant analysis, SVDA)依最优超平面法线方向投影对数据进行降维,克服了传统方法中假设数据满足高斯分布时,导致无法反映超平面单侧中多类数据间投影距离差异并影响了算法...
  • svm系列之最大分隔超平面

    千次阅读 2016-07-24 23:39:51
    svm 最大分隔超平面

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,128
精华内容 5,251
关键字:

最优超平面