浅析SVM中的对偶问题

浅浅的花香味﹌ 2023-08-17 16:20 42阅读 0赞

# 浅析SVM中的对偶问题 #

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

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

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

*  原始问题的约束方程数对应于对偶问题的变量数, 而原始问题的变量数对应于对偶问题的约束方程数, 而**约束方程数目越少, 优化问题求解的复杂度越低**  
    如在线性SVM的原问题中，样本量为N  
    \\\[ p^\* = min \\ \\frac\{1\}\{2\}||w||^2 \\\\ s.t. \\ y\_\{i\}(w^\{T\}x\_\{i\} + b ) \\geq 1 \\\]  
    其中2个变量：w, b，但在优化目标函数中只有1个w   N个限制条件  
    在线性SVM的对偶问题中  
    \\\[ d^\* = min ( \\sum\\limits\_\{i=1\}^\{N\}\\sum\\limits\_\{j=1\}^\{N\}\\alpha\_\{i\}\\alpha\_\{j\}y\_\{i\}y\_\{j\}x\_\{i\}x\_\{j\} - \\frac\{1\}\{2\}\\sum\\limits\_\{i=1\}^\{N\}\\alpha\_\{i\} )\\\\ s.t. \\ \\sum\\limits\_\{i=1\}^\{N\}\\alpha\_\{i\}y\_\{i\} = 0\\\\ \\alpha\_\{i\} \\geq 0 \\\]  
    其中N个变量： \\(\\alpha\_\{i\}: \\ i=1,2...N\\)，1个限制条件  
    
 *  无论原问题本身是不是一个凸优化问题, 对偶问题总是可以转换为**凸优化问题**来研究；当原问题的难以求解时, 对偶问题可以给出一个下界，即：  
    \\\[ d^\{\*\} \\leq p^\{\*\} \\\]

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

假设训练集一共有Ｎ个样本，每个样本点维数为ｎ，映射到特征空间中的维度为ｄ  
原问题的求解形式为：\\(f(x) = sign(w^\{T\}\\phi(x\_\{i\}) + b)\\)  所需计算的乘法次数为：ｄ  
对偶问题的求解形式为：\\(f(x) = \\sum\\limits\_\{i=1\}^\{N\}\\alpha\_\{i\}y\_\{i\}\\kappa(x\_\{i\}, x\_\{j\}) + b\\)  可以通过KKT条件推导，只有支撑向量对应的\\(\\alpha\_\{i\}\\)不为０，设支撑向量的总个数为\\(N\_\{sv\}\\)，对偶问题所需计算的乘法次数为：\\(N\_\{sv\}n\\) （最少仅由２个支撑向量就可以确定一个超平面，见<>P101）  
**当训练样本总数不大，特征空间的维度d>>n时，选择在对偶问题中求解将有效减少计算量**  
**同时，当前解决对偶问题已经有了非常高效的算法，如SMO**

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

主要有三点：

*  当训练集很大时，支撑向量很多，计算量：\\(N\_\{sv\}n >> d\\)  
    
 *  当求解一个SVM的近似解时，研究原问题反而比对偶问题更好（可以参考[Chapelle][]等人的论文）  
    
 *  对偶问题的Gram矩阵的大小为N \* N，当训练集很大时，如N = \\(10^\{6\}\\)，N \* N = \\(10^\{12\}\\)，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?][Why study duality in optimization]

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

[Chapelle]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.3368&rep=rep1&type=pdf
[Advantages of dual over primal solution of an optimization problem]: https://math.stackexchange.com/questions/2846066/advantages-of-dual-over-primal-solution-of-an-optimization-problem?rq=1
[Why do we prefer Dual Problem over Primal Problem in convex optimization]: https://math.stackexchange.com/questions/2196922/why-do-we-prefer-dual-problem-over-primal-problem-in-convex-optimization?rq=1
[Why study duality in optimization]: https://math.stackexchange.com/questions/2877393/why-study-duality-in-optimization