当前位置:   article > 正文

浅析SVM中的对偶问题

为什么dual svm要用对偶

浅析SVM中的对偶问题

关于SVM对偶问题求解的博客有很多,但是关于为什么要进行对偶问题的分析却很零散,这里做一个总结

1. 为什么要研究对偶问题?

广义上讲,将原问题的研究转换为对偶问题的研究主要有一下几个优势:

  • 原始问题的约束方程数对应于对偶问题的变量数, 而原始问题的变量数对应于对偶问题的约束方程数, 而约束方程数目越少, 优化问题求解的复杂度越低
    如在线性SVM的原问题中,样本量为N
    p=min 12||w||2s.t. yi(wTxi+b)1

    其中2个变量:w, b,但在优化目标函数中只有1个w   N个限制条件

    在线性SVM的对偶问题中
    d=min(i=1Nj=1Nαiαjyiyjxixj12i=1Nαi)s.t. i=1Nαiyi=0αi0

    其中N个变量: αi: i=1,2...N,1个限制条件

  • 无论原问题本身是不是一个凸优化问题, 对偶问题总是可以转换为凸优化问题来研究;当原问题的难以求解时, 对偶问题可以给出一个下界,即:
    dp

2. 在SVM中研究对偶问题的优势?


假设训练集一共有N个样本,每个样本点维数为n,映射到特征空间中的维度为d
原问题的求解形式为:f(x)=sign(wTϕ(xi)+b)  所需计算的乘法次数为:d
对偶问题的求解形式为:f(x)=i=1Nαiyiκ(xi,xj)+b  可以通过KKT条件推导,只有支撑向量对应的αi不为0,设支撑向量的总个数为Nsv,对偶问题所需计算的乘法次数为:Nsvn (最少仅由2个支撑向量就可以确定一个超平面,见<>P101)
当训练样本总数不大,特征空间的维度d>>n时,选择在对偶问题中求解将有效减少计算量
同时,当前解决对偶问题已经有了非常高效的算法,如SMO

 

3. 为什么在实际问题中原问题反而应用得更多?


主要有三点:

  • 当训练集很大时,支撑向量很多,计算量:Nsvn>>d
  • 当求解一个SVM的近似解时,研究原问题反而比对偶问题更好(可以参考Chapelle等人的论文)
  • 对偶问题的Gram矩阵的大小为N * N,当训练集很大时,如N = 106,N * N = 1012,1T,内存根本开不了这么大的空间,训练都没办法训练!

4. 参考资料

Advantages of dual over primal solution of an optimization problem
Why do we prefer Dual Problem over Primal Problem in convex optimization
Why study duality in optimization?

转载于:https://www.cnblogs.com/MoonJian/p/11165725.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/740324
推荐阅读
相关标签
  

闽ICP备14008679号