浅析SVM中的对偶问题
关于SVM对偶问题求解的博客有很多,但是关于为什么要进行对偶问题的分析却很零散,这里做一个总结
1. 为什么要研究对偶问题?
广义上讲,将原问题的研究转换为对偶问题的研究主要有一下几个优势:
- 原始问题的约束方程数对应于对偶问题的变量数, 而原始问题的变量数对应于对偶问题的约束方程数, 而约束方程数目越少, 优化问题求解的复杂度越低
如在线性SVM的原问题中,样本量为N
其中2个变量:w, b,但在优化目标函数中只有1个w N个限制条件
在线性SVM的对偶问题中
其中N个变量: ,1个限制条件 - 无论原问题本身是不是一个凸优化问题, 对偶问题总是可以转换为凸优化问题来研究;当原问题的难以求解时, 对偶问题可以给出一个下界,即:
2. 在SVM中研究对偶问题的优势?
假设训练集一共有N个样本,每个样本点维数为n,映射到特征空间中的维度为d
原问题的求解形式为: 所需计算的乘法次数为:d
对偶问题的求解形式为: 可以通过KKT条件推导,只有支撑向量对应的不为0,设支撑向量的总个数为,对偶问题所需计算的乘法次数为: (最少仅由2个支撑向量就可以确定一个超平面,见<>P101)
当训练样本总数不大,特征空间的维度d>>n时,选择在对偶问题中求解将有效减少计算量
同时,当前解决对偶问题已经有了非常高效的算法,如SMO
3. 为什么在实际问题中原问题反而应用得更多?
主要有三点:
- 当训练集很大时,支撑向量很多,计算量:
- 当求解一个SVM的近似解时,研究原问题反而比对偶问题更好(可以参考Chapelle等人的论文)
- 对偶问题的Gram矩阵的大小为N * N,当训练集很大时,如N = ,N * N = ,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?