（LXTML笔记）关于支持向量机[二]

下面讨论的是对偶支持向量机，先看引入

由上一节我们知道，朴素支持向量机可以通过二次规划来直接解决，但是我们假设x$x$本身是一个d$d$维的向量，然后由于可能有复杂边界，所以我们常常要讲x$x$转换到Z$Z$空间上，通过zn=ϕ(xn)$z_n=\varphi (x_n)$来实现，在实际中这里的ϕ$\varphi$往往是升维度的，因为一般是不可线性可分，然后（比如）高维的时候就变成线性可分了，不妨比如如

这样的话复杂度（如内积）完全取决于ϕ$\varphi$的形式，这里变成了至少O(d2)$O(d^2)$，这给二次规划带来了巨大的压力，那么此时我们引入SVM的对偶问题

将SVM的复杂度变为和数据的数量相联系

和正则化那一节类似地，我们可以考虑如下拉格朗日函数，企图将约束条件去掉，塞进最优化部分。

最优化问题变为了

这个操作也是迫使向的，假设有一个(b,w)$(b,w)$不满足限制条件，那么就是说yn(wTzn+b)<1$y_n(w^T{z}_n+b)<1$，所以容易知道(maxan≥0{L(b,w,a)})→+∞$\left(ma{x}_{a_n\ge 0}\{L(b,w,a)\}\right)\to +\mathrm{\infty }$，而假设全部的(b,w)$(b,w)$都满足限制条件的话，那么容易知道(maxan≥0{L(b,w,a)})=wTw$\left(ma{x}_{a_n\ge 0}\{L(b,w,a)\}\right)=w^{T}w$，这和我们原来的最优化目标是一样的。

至此，我们去掉了限制条件，下面引入对偶问题，我们知道对于

固定a$a$的话，我们轻松得到：

由于对任何固定a$a$都成立，那么我们对右边的a$a$取最大仍是成立的，我们得到了min⋅max≥max⋅min$min\cdot max\ge max\cdot min$的结论，如下图

如果上面的这个大于等于号是等号就好了，而最优化里有这样的一个结论：

对于二次规划问题，如果

• 凸函数
• 可分的
• 限制条件是线性的

那么称上述对偶问题为强对偶问题，存在一组(b,w,a)$(b,w,a)$使得两边都成立，即等号成立，即解左右两边都是一样的。下面我们来看右边的对偶问题能带来什么便利，

整理一下，现在问题变为

考虑取到最小值时候的费马点条件，对w$w$和b$b$进行求导，然后将这些必要条件放在限制条件上有

这样下来，我们可以看到我们已经去掉了”min$min$”了，此时最优化目标仅仅与a$a$有关，总结一下既有

上述中的4点展示的是KKT条件（不过略强，实际上可以稍微放松一点条件），第四点是上文中关于

的描述所保证的。

依旧采用二次规划的问题的方法即可

要还原回原来的(w,b)$(w,b)$的话，在求得所有的an$a_n$后，由我们最优条件的w=∑anynzn)$w=\sum a_n{y}_n{z}_n)$可以获得w$w$，而由于有an(1−yn(wTzn+b))=0$a_n(1-y_n(w^T{z}_n+b))=0$，所以我们只需要找到一个非零的an$a_n$就可以得到我们要的b$b$,特别地我们可以观察到，实际上，整个问题只和非零的an$a_n$有关系，之前上文中将在“胖边界”上的点成为“支持向量”，而此时我们可以更进一步地加强，称这些对应an≠0$a_n\ne 0$的点称为“支持向量”

再次将朴素SVM和对偶SVM放在一起对比 有：

这里表面上在计算对偶SVM时候，隐藏了xn$x_n$的维度d$d$，但是实际上，这部分的计算蕴含在矩阵Q$Q$中，计算这个Q$Q$并不容易，下一节，将讲到如何应用“核函数”技巧来化简计算量，让SVM能落实到应用中。