机器学习——SVM(5 有关SVM的一些解释)

SVM是一种正则化模型
对于上一篇所讲的Soft-Margin SVM有如下形式，
$\begin{array}{l} \mathop {\min }\limits_{b,w,\xi } \frac{1}{2}{w^T}w + C \cdot \sum\limits_{n = 1}^N {{\xi _n}} \\ \\ s.t.\;\;\;{y_n}({w^T}{z_n} + b) \ge 1 - {\kern 1pt} {\kern 1pt} {\xi _n}\;\\ \\ \;\;\;\;\;\;\;\;{\xi _n} \ge 0\\ \;\;\;\;\; \end{array}$b,w,ξmin​21​wTw+C⋅n=1∑N​ξn​s.t.yn​(wTzn​+b)≥1−ξn​ξn​≥0​
从${\xi _n}$ξn​的含义来看，${\xi _n} = {\rm{margin}}\;{\rm{violation}}$ξn​=marginviolation，它记录的是nosie数据距离边界的大小，即犯错误程度的多少，但从另一个角度去看，对于任意的参数$(b,w)$(b,w)，有，

• 当数据$({x_n},{y_n})$(xn​,yn​)破坏了边界时：${\xi _n} = 1 - {y_n}({w^T}{z_n} + b) > 0$ξn​=1−yn​(wTzn​+b)>0；
• 当数据$({x_n},{y_n})$(xn​,yn​)没有破坏边界时：${\xi _n} = 0$ξn​=0

即，${\xi _n} = \max (1 - {y_n}({w^T}{z_n} + b),0)$ξn​=max(1−yn​(wTzn​+b),0)。
所以，对于Soft-Margin SVM也可以描述成另一种无约束的形式，即，
$\mathop {\min }\limits_{b,w} \;\frac{1}{2}{w^T}w + C\sum\limits_{n = 1}^N {\max (1 - {y_n}({w^T}{z_n} + b),0)}$b,wmin​21​wTw+Cn=1∑N​max(1−yn​(wTzn​+b),0)
该形式与L2 regularization相类似，即，
$\underbrace {\min \;\frac{1}{2}{w^T}w + C\sum {\widehat {err}} }_{SVM} \leftrightarrow \underbrace {\min \;\frac{\lambda }{N}{w^T}w + \frac{1}{N}\sum {err} }_{L2}$SVMmin21​wTw+C∑err​​↔L2minNλ​wTw+N1​∑err​​
首先，可以从形式来看，

对比上式，有以下3条关系，
$\begin{array}{l} {\rm{1}}{\rm{.large}}\;{\rm{margin}} \Leftrightarrow {\rm{fewer \;hyperplanes}} \Leftrightarrow {\rm{L2 \;regularization\; of \;short\; w}}\\ \\ {\rm{2}}{\rm{.soft\; margin}} \Leftrightarrow {\rm{special \;}}\widehat {{\rm{err}}}\\ \\ {\rm{3}}{\rm{.larger\; C}} \Leftrightarrow {\rm{smaller \;}}\lambda \Leftrightarrow {\rm{less\; regularization}} \end{array}$1.largemargin⇔fewerhyperplanes⇔L2regularizationofshortw2.softmargin⇔specialerr3.largerC⇔smallerλ⇔lessregularization​

所以，可以把SVM看作是一个已经正则化过后的模型。

另外，也可以从误差衡量角度来看，
$\mathop {\min }\limits_{b,w} \;\frac{1}{2}{w^T}w + C\sum\limits_{n = 1}^N {\max (1 - {y_n}(\underbrace {{w^T}{z_n} + b}_{{\rm{linear\;score}}}),0)}$b,wmin​21​wTw+Cn=1∑N​max(1−yn​(linearscorewTzn​+b​​),0)
让上式中的$s = {w^T}{z_n} + b$s=wTzn​+b，则SVM的误差衡量方式即为，
${\widehat {{\rm{err}}}_{{\rm{SVM}}}}(s,y) = \max (1 - ys,0)—hinge \;error \;measure$errSVM​(s,y)=max(1−ys,0)—hingeerrormeasure
回顾之前的误差衡量方式有PLA中的0\1误差${\rm{er}}{{\rm{r}}_{0/1}}(s,y)$err0/1​(s,y)，逻辑回归里的交叉熵误差$er{r_{{\rm{SCE}}}}(s,y)$errSCE​(s,y)，与SVM里的hinge error放在一起，即，

$\begin{array}{l} {\rm{er}}{{\rm{r}}_{0/1}}(s,y) = \left[\kern-0.15em\left[ {ys \le 0} \right]\kern-0.15em\right]\\\\ {\widehat {{\rm{err}}}_{{\rm{SVM}}}}(s,y) = \max (1 - ys,0)\\\\ er{r_{{\rm{SCE}}}}(s,y) = {\log _2}(1 + \exp ( - ys)) \end{array}$err0/1​(s,y)=[[ys≤0]]errSVM​(s,y)=max(1−ys,0)errSCE​(s,y)=log2​(1+exp(−ys))​
其图像如下，

从上图中，可以得出如下关系，
$\begin{array}{l}- \infty \;\;\;\;\;\;\; \leftarrow \;\;\;\;ys\;\;\; \to \;\;\;\;\;\;\; + \infty \\ \approx - ys\;\;\;\;\;\;\;{\widehat {{\rm{err}}}_{{\rm{SVM}}}}(s,y)\;\;\;\;\;\;\;\; = 0\\ \approx - ys\;\;\;\;(\ln 2) \cdot {\rm{er}}{{\rm{r}}_{{\rm{SCE}}}}(s,y)\;\;\;\;\; \approx 0 \end{array}$−∞←ys→+∞≈−yserrSVM​(s,y)=0≈−ys(ln2)⋅errSCE​(s,y)≈0​

而SVM的代价函数前面还有一项$\frac{1}{2}{w^T}w$21​wTw，所以，SVM与L2-regularization logistic regression相似，即，
${\rm{SVM}} \approx {\rm{L2 - regularization \;logistic \;regression}}$SVM≈L2−regularizationlogisticregression

Probabilistic SVM

把SVM和logistic regression结合起来，进行soft binary classification,为了综合二者的优点，这里提出了一种可能的二层式的学习模型(Two-Level Learning)，即，
$g(x) = \theta (A \cdot (w_{{\rm{SVM}}}^T\Phi (x) + {b_{SVM}}) + B)$g(x)=θ(A⋅(wSVMT​Φ(x)+bSVM​)+B)
上式中，
$\begin{array}{l} A > 0,if\;{w_{{\rm{SVM}}}}\;reasonably\;good\\ B \approx 0,if\;{b_{{\rm{SVM}}}}\;reasonably\;good \end{array}$A>0,ifwSVM​reasonablygoodB≈0,ifbSVM​reasonablygood​
新的LogReg问题描述如下，
$\mathop {\min }\limits_{A,B} \;\frac{1}{N}\sum\limits_{n = 1}^N {\log (1 + \exp ( - {y_n}(A \cdot (\underbrace {w_{{\rm{SVM}}}^T\Phi (x) + {b_{SVM}}}_{{\Phi _{{\rm{SVM}}}}({x_n})}) + B)))}$A,Bmin​N1​n=1∑N​log(1+exp(−yn​(A⋅(ΦSVM​(xn​)wSVMT​Φ(x)+bSVM​​​)+B)))

Two-level learning: LogReg on SVM-transformed data

Platt’s Model of Probabilistic SVM for Soft Binary Classification
1.在数据集D上使用SVM得到$({b_{SVM}},{w_{SVM}})$(bSVM​,wSVM​) ,变换资料D为${z'_n} = w_{SVM}^T\Phi ({x_n}) + {b_{SVM}}$zn′​=wSVMT​Φ(xn​)+bSVM​ 2.在变换后的资料$({z'_n},{y_n})$(zn′​,yn​)上，使用LogReg,得出（A,B） 3.返回参数，得出模型，$g(x) = \theta (A \cdot (w_{SVM}^T\Phi (x) + {b_{SVM}}) + B)$g(x)=θ(A⋅(wSVMT​Φ(x)+bSVM​)+B)

有关Kernel的一些讨论

要让算法能用kerne表示的前提条件就是，最佳化的${w_*}$w∗​要能表示成资料${z_n}$zn​线性组合的形式(${w_*} = \sum\limits_{n = 1}^N {{\beta _n}{z_n}}$w∗​=n=1∑N​βn​zn​)，原因如下，
$w_*^T{z_n} = \sum\limits_{n = 1}^N {{\beta _n}z_n^Tz} = \sum\limits_{n = 1}^N {{\beta _n}K({x_n},x)}$w∗T​zn​=n=1∑N​βn​znT​z=n=1∑N​βn​K(xn​,x)
回顾以前的算法，

$\begin{array}{l} {\rm{SVM:}}{{\rm{w}}_{{\rm{SVM}}}} = \sum\limits_{n = 1}^N {({\alpha _n}{y_n}){z_n}} \;\;\;\;\;\;\;\;\;{\alpha _n}可由dual \;SVM求得\\ {\rm{PLA:}}{{\rm{w}}_{{\rm{PLA}}}} = \sum\limits_{n = 1}^N {({\alpha _n}{y_n}){z_n}} \;\;\;\;\;\;\;\;\;\;\;{\alpha _n}可由mis{\rm{ta}}ke \;corrections求得\\ {\rm{LogReg:}}{{\rm{w}}_{{\rm{LogReg}}}} = \sum\limits_{n = 1}^N {({\alpha _n}{y_n}){z_n}} \;\;\;\;{\alpha _n}可由total \;SGD求得 \end{array}$SVM:wSVM​=n=1∑N​(αn​yn​)zn​αn​可由dualSVM求得PLA:wPLA​=n=1∑N​(αn​yn​)zn​αn​可由mistakecorrections求得LogReg:wLogReg​=n=1∑N​(αn​yn​)zn​αn​可由totalSGD求得​

以上算法的最佳化的${w_*}$w∗​都可以表示成资料线性组合的形式。

---

下面阐述一个理论(即Representer Theorem)如下，

对于任意L2-regularized linear model，即，

$\mathop {\min }\limits_w \;\frac{\lambda }{N}{w^T}w + \frac{1}{N}\sum\limits_{n = 1}^N {err({y_n},{w^T}{z_n})}$wmin​Nλ​wTw+N1​n=1∑N​err(yn​,wTzn​)其最佳化${w_*}$w∗​均可表示为 ${w_*} = \sum\limits_{n = 1}^N {{\beta _n}{z_n}}$w∗​=n=1∑N​βn​zn​。

---

运用该理论，考虑把kernel用在LogReg里，这就是Kernel Logistic Regression(KLR)，下面就来具体说下这个KLR。

对于一个L2-regularized LogReg，描述如下，
$\mathop {\min }\limits_w \;\frac{\lambda }{N}{w^T}w + \frac{1}{N}\sum\limits_{n = 1}^N {\log (1 + \exp ( - {y_n}{w^T}{z_n}))}$wmin​Nλ​wTw+N1​n=1∑N​log(1+exp(−yn​wTzn​))

考虑到有${w_*} = \sum\limits_{n = 1}^N {{\beta _n}{z_n}}$w∗​=n=1∑N​βn​zn​，所以用参数$\beta$β来代替参数w，有，
$\mathop {\min }\limits_\beta \frac{\lambda }{N}\sum\limits_{n = 1}^N {\sum\limits_{m = 1}^N {{\beta _n}{\beta _m}K({x_n},{x_m}) + \frac{1}{N}} } \sum\limits_{n = 1}^N {\log (1 + \exp ( - {y_n}\sum\limits_{m = 1}^N {{\beta _m}K({x_m},{x_n})} ))}$βmin​Nλ​n=1∑N​m=1∑N​βn​βm​K(xn​,xm​)+N1​n=1∑N​log(1+exp(−yn​m=1∑N​βm​K(xm​,xn​)))上式，就是KLR的描述，其中参数$\beta$β可用GD/SGD方法求得。

那么，对于KLR，可用两个角度去看，

• 角度1： KLR是关于w的模型,里面包含了一个kernel的非线性转换以及一个L2 regularizer。
• 角度2： KLR是关于$\beta$β的模型，把kernel看作是一种转换，即$(K({x_1},{x_n}),K({x_2},{x_n}), \cdots ,K({x_N},{x_n}))$(K(x1​,xn​),K(x2​,xn​),⋯,K(xN​,xn​))，把前面的$\sum\limits_{n = 1}^N {\sum\limits_{m = 1}^N {{\beta _n}{\beta _m}K({x_n},{x_m})} }$n=1∑N​m=1∑N​βn​βm​K(xn​,xm​)这一项看作是一种特殊的regularizer，即，${\beta ^T}K\beta$βTKβ。