[人工智能] 支持向量机（SVM）凸优化与对偶问题求解

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 支持向量机（SVM）凸优化与对偶问题求解 -> 正文阅读

[人工智能]支持向量机（SVM）凸优化与对偶问题求解

一、对偶问题的转化

先写出一个转化对偶问题的一般性结论

原问题：

$min:f(x)$

$s.t.:g_{i}(x)\leq 0$

? ? ? $h_{i}(x)=0$

转化为的对偶问题是：

$max:\theta (\alpha ,\beta )=\underset{\forall x}{inf}:[f(x)+\sum_{i=1}^{g}\alpha _{i}*g_{i}(x)+\sum_{i=1}^{h}\beta _{i}*h_{i}(x)]$

$s.t.:\alpha _{i}\geq 0$

其中a，b是根据原问题的限制条件产生的新的变量。

二、SVM模型问题转化

原问题：

$min:\frac{1}{2}\left \| w \right \|^{2}+C\sum_{i=1}^{N}\xi _{i}$

$s.t.:y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i}$

$\xi _{i}\geq 0$

即：

$min:\frac{1}{2}\left \| w \right \|^{2}-C\sum_{i=1}^{N}\xi _{i}$

$s.t.:1+\xi _{i}-y_{i}(w^{T}x_{i}+b)\leq 0$

? $\xi _{i}\leq 0$

注意这里待求参数是w，xi，b。

转化为的对偶问题是：

$\tiny max:\theta (\alpha ,\beta )=\underset{\forall w,\xi ,b}{inf}:[\frac{1}{2}\left \| w \right \|^{2}-C\sum_{i=1}^{N}\xi _{i}+\sum_{i=1}^{N}\alpha _{i}*[1+\xi _{i}-y_{i}(w^{T}x_{i}+b)]+\sum_{i=1}^{N}\beta _{i}*\xi _{i}]$

$s.t.:\alpha _{i}\geq 0,\beta_{i}\geq 0$

注意这里实际只有a，b其实还是a只是为了区别不同的限制条件。

先求xita(a,b)，分别对w，xi，b求偏导，再代回，得

$max:\theta (\alpha ,\beta )=\sum_{i=1}^{N}\alpha _{i}-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _{i}\alpha _{j}y_{i}y_{j}x_{i}x_{j}$

$s.t.:0\leq \alpha_{i}\leq C \\ .\quad.\quad.\quad\sum_{i=1}^{N}\alpha _{i}y_{y}=0$

这样的方程求解就比较容易了，书上说用SMO算法。得到所有的a;

大学课上编程实现的好像是梯度下降。。。