算法基本功：SVM part4 SVM与对偶问题 2019-03

2019-03-03 本文已影响0人 qb学习笔记

上章讲了对偶问题一般情况，引入到SVM中。

SVM 对偶问题表达式推导：

由上一章节知道：

$f* \geq min_{x\in C} L(x,u,v) \geq min_{x} L(x,u,v) := g(u, v)$ # 直白讲即：原问题的下界为其对偶问题； g(u,v)为对偶函数。

故svm对偶问题，即最大化下界函数，为：

$max_{\alpha } g(\alpha ) = max_{a_{i}\geq 0} min_{w,b} L(w,b,\alpha )$ ， # 最大化下界函数。

顺着推：

$min_{w,b}L(w,b, x)$ = $\Sigma _{i}\alpha _i - \frac{1}{2} \Sigma_i \Sigma_j\alpha_i\alpha_jx_ix_jy_iy_j$ # 利用关于W,b 的偏导数为0 得到极值点；得到的两个条件带回L(w,b,x)，

故顺着推，对偶问题进一步化简为：

$max_{a}\Sigma _{i}\alpha _i - \frac{1}{2} \Sigma_i \Sigma_j\alpha_i\alpha_jx_ix_jy_iy_j$

subject to:

$a_{i} \geq 0$ ，

$\Sigma_i\alpha _iy_i = 0$

下一篇 SMO