数据挖掘：支持向量机SVM数学推导

Support Vector Machines

SVM数学推导

$$\begin{gathered} \underset{w,b}{\max }\frac{2}{||w|{|}_2} \\ s.t.:y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,2,\dots ,m \end{gathered}$$

优化问题等价于，
$$\begin{gathered} \underset{w,b}{\min }\frac{||w|{|}_2^2}{2} \\ s.t.:y^{(i)}(w^T{x}^{(i)}+b)\ge 1,i=1,2,\dots ,m \end{gathered}$$
转化问题形式为：
$$\begin{gathered} J(w)=\frac{||w|{|}_2^2}{2} \\ s.t.:1-y^{(i)}(w^T{x}^{(i)}+b)\le 0,i=1,2,\dots ,m \end{gathered}$$
使用拉格朗日乘子法，
$$L(w,b,\beta )=\frac{||w|{|}_2^2}{2}+\sum _{i=1}^m{\beta }_i[1-y^{(i)}(w^T{x}^{(i)}+b)],{\beta }_i\ge 0$$
最优解应为${\min }_{w,b}{\max }_{\beta \ge 0}L(w,b,\beta )$

转化为对偶问题${\max }_{\beta \ge 0}{\min }_{w,b}L(w,b,\beta )$
$$\begin{gathered} \frac{\partial L}{\partial w}=0\Rightarrow w-\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}=0\Rightarrow w=\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)} \\ \frac{\partial L}{\partial b}=0\Rightarrow -\sum _{i=1}^m{\beta }_i{y}^{(i)}=0\Rightarrow \sum _{i=1}^m{\beta }_i{y}^{(i)}=0 \end{gathered}$$
现在求解$\beta$
$$\begin{gathered} L(\beta )=\frac{||w|{|}_2^2}{2}+\sum _{i=1}^m{\beta }_i[1-y^{(i)}(w^T{x}^{(i)}+b)] \\ =\frac{||w|{|}_2^2}{2}-\sum _{i=1}^m{\beta }_i[y^{(i)}(w^T{x}^{(i)}+b)-1] \\ =\frac{1}{2}{w}^{T}w-\sum _{i=1}^m{\beta }_i{y}^{(i)}{w}^T{x}^{(i)}-\sum _{i=1}^m{\beta }_i{y}^{(i)}b+\sum _{i=1}^m{\beta }_i \\ =\frac{1}{2}{w}^T\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}-w^T\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}-b\sum _{i=1}^m{\beta }_i{y}^{(i)}+\sum _{i=1}^m{\beta }_i \\ =-\frac{1}{2}{w}^T\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}-b\sum _{i=1}^m{\beta }_i{y}^{(i)}+\sum _{i=1}^m{\beta }_i \\ =-\frac{1}{2}{(\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)})}^T\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}+\sum _{i=1}^m{\beta }_i \\ =-\frac{1}{2}(\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)T})\sum _{i=1}^m{\beta }_i{y}^{(i)}{x}^{(i)}+\sum _{i=1}^m{\beta }_i \\ =\sum _{i=1}^m{\beta }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\beta }_i{\beta }_j{y}^{(i)}{y}^{(j)}{x}^{(i)}{x}^{(j)} \end{gathered}$$
To solve β value, we need an Sequential Minimal Optimization algorithm.

Paper: Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines

如何求$w^{\ast }:w^{\ast }={\sum }_{i=1}^m{\beta }_i^{\ast }{y}^{(i)}{x}^{(i)}$

如何求$b^{\ast }$
$$y^s(w^T{x}^s+b)=y^s(\sum _{i=1}{\beta }_i^s{y}^{(i)}{x}^{(i)T}{x}^s+b)=1\Rightarrow b^{\ast }=y^s-\sum _{i=1}^m{\beta }_i^{\ast }{y}^{(i)}{x}^{(i)T}{x}^s$$
$y^s,x^s$是已知的样本点

非线性分类—核函数

Polynomial (homogeneous): $k(x,x^{\prime })=(x\cdot x^{\prime })$

Polynomial (inhomogeneous): $k(x,x^{\prime })=(x\cdot x^{\prime }+1)$

Radial basis function: $k(x,x^{\prime })=exp(-\gamma ||x-x^{\prime }|{|}^2),\gamma >0$

Gaussian radial basis function: $k(x,x^{\prime })=exp(-\frac{||x-x^{\prime }|{|}^2}{2{\sigma }^2})$

Sigmoid: $k(x,x^{\prime })=\tan h(kx\cdot x^{\prime }+c),k>0andc<0$