支持向量機(jī)

一、什么是支持向量機(jī)

支持向量機(jī)(Suport Vector Machine,常簡(jiǎn)稱為SVM）倡勇，是一個(gè)監(jiān)督式學(xué)習(xí)的方式殖告。支持向量機(jī)屬于一般化線性分類器，這類分類器的特點(diǎn)是能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)晴圾，因此支持向量機(jī)機(jī)也被稱為最大邊緣區(qū)分類器。

SVM.png

max margin.png

藍(lán)色和紅色的線圈出來的點(diǎn)就是所謂的支持向量噪奄，離分界線最近的點(diǎn)死姚，如果去掉這些點(diǎn)，直線多半要改變位置勤篮。Classifier Boundary就是決策函數(shù)f(x)都毒，在兩個(gè)類的中間。紅色和藍(lán)色之間的間隙就是我們要的最大化分類的間隙碰缔。

二温鸽、關(guān)于拉格朗日乘子法和KKT條件

1.關(guān)于拉格朗日乘子法

有拉格朗日乘子法的地方，必然是一個(gè)組合優(yōu)化問題手负。比如
$\begin{align} min \space f = 2x_1^2+3x_2^2+7x_3^2 \\ s.t. 2x_1 + x_2 = 1 \\ 2x_2+3x_3 = 2 \end{align}$

這是一個(gè)帶等式約束的優(yōu)化問題，有目標(biāo)值姑尺，有約束條件竟终，不能直接求導(dǎo)∏畜可以使用拉格朗日方法统捶，把這個(gè)約束乘以一個(gè)系數(shù)加到目標(biāo)函數(shù)中去，這樣相當(dāng)與既考慮了原目標(biāo)函數(shù)柄粹，也考慮了約束條件喘鸟。然后分別對(duì)x求導(dǎo)等于0，
$\begin{align} \frac{\partial{f}}{\partial{x_2}} = 4x_1+2\alpha_1 = 0 \implies x_1 = -0.5\alpha_1 \\ \frac{\partial f} {\partial x_2} = 6x_2+\alpha_1+2\alpha_2 = 0 \implies x_2 = -\frac{\alpha_1+2\alpha_2}{6} \\ \frac{\partial f}{\partial x_3} = 14x_3+3\alpha_2 = 0 \implies x_3 = -\frac{3\alpha_2}{14} \end{align}$
把它帶點(diǎn)菜約束條件中去驻右，可以看到什黑，2個(gè)變量兩個(gè)等式，最終可再帶回去求x就可以了堪夭。更高一層愕把，帶有不等式的約束問題怎么辦拣凹？需要用更一般化的拉格朗日乘子法，即KKT條件恨豁，來求解這個(gè)問題嚣镜。

2.關(guān)于KKT條件

任何原始問題約束條件無非最多三種，等式約束橘蜜，大于號(hào)約束菊匿，小于號(hào)約束，而這三種最終通過將約束方程簡(jiǎn)化成兩類：約束方程等于0和約束方程小于0计福。

假設(shè)原始問題約束條件為下例所示：
$\begin{align} min \space f = x_1^2-2x_1+1+x_2^2+4x_2+4 \\ s.t. \space x_1 + 10x_2 > 10 \\ 10x_1 - 10 x_2 < 10 \end{align}$
那么把約束條件變個(gè)樣子
$\begin{align} s.t. \space 10 -x_1 - 10x_2 < 0 \\ 10x_1 - 10 x_2 < 10 \end{align}$
現(xiàn)在拿到目標(biāo)函數(shù)中去變成
$\begin{align} L(x,\alpha) = f(x)+\alpha_1 g_1(x)+\alpha_2 g_2(x) \\ = x_1^2 - 2x_1+1+x_2^2+4x_2+4+\alpha_1(10-x_1+10x_2)+\alpha_2(10x_2-x_2-10) \end{align}$

那么KKT條件的定理是什么呢跌捆？就是如果一個(gè)優(yōu)化問題在轉(zhuǎn)變成
$L(x,\alpha,\beta) = f(x) +\sum \alpha_ig_i(x) + \sum \beta_ih_i(x)$
其中g(shù)是不等式約束，h是等式約束棒搜。那么KKT條件就是函數(shù)的最優(yōu)值疹蛉，它必定滿足下面條件：

L對(duì)各個(gè)x求導(dǎo)為0
$h(x) = 0$
$\sum \alpha_ig_i(x) = 0 ,\alpha_i \le 0$

這三個(gè)等式很好理解，重點(diǎn)是第三個(gè)句子不好理解力麸，因?yàn)槲覀冎涝诩s束條件變完或可款，所有的 $g(x) \le 0$ ，且求和還要為0克蚂。那么為什么KKT的條件是這樣的呢闺鲸？

某次的g(x)在為最優(yōu)解起作用，那么它的系數(shù)值（可以）不為0埃叭，如果某次g(x)沒有為下一次的最優(yōu)解起作用摸恍，那么它的系數(shù)就必須為0。

三赤屋、函數(shù)間隔和幾何間隔

函數(shù)間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T合超平面(w,b)立镶，定義超平面(w,b)關(guān)于樣本點(diǎn) $(x_i,y_i)$ 的函數(shù)間隔為 $\hat{\gamma_i} = y_i(\omega*x_i+b)$

函數(shù)間隔可以表示分類預(yù)測(cè)的正確性及確信度。但是選擇超平面時(shí)类早，只有函數(shù)間隔是不夠的媚媒，因子只要成比較改變 $\omega$ 和b，超平面并沒有改變涩僻，但函數(shù)間隔卻擴(kuò)大了缭召。

幾何間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T和超平面 $(\omega,b)$ ，定義超平面 $(\oemga,b)$ 關(guān)于樣本點(diǎn) $(x_i,y_i)$ 的幾何間隔為 $\hat \gamma = y_i(\frac{\omega}{\|\omega\|}*x_i+\frac逆日{\|\omega\|}$ ,其中 $\|\omega\|$ 為 $\omega$ 的 $L_2$ 范數(shù)嵌巷。

如果 $\|\omega\|=1$ ，那么函數(shù)間隔和幾何間隔相等室抽。如果超平面參數(shù) $\omega,b$ 成比例地改變（超平面沒有改變）搪哪，函數(shù)間隔也成比例改變，而幾何間隔不變狠半。

四噩死、間隔最大化

支持向量機(jī)的基本想法是求解能夠正確分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面颤难。對(duì)線性可分的訓(xùn)練數(shù)據(jù)集而言，線性可分分離超平面有無窮多個(gè)（等價(jià)于感知機(jī)）已维，但是幾何間隔最大的分離超平面時(shí)唯一的行嗤。這里的間隔最大化被稱為硬間隔最大化。

間隔最大化的直觀解釋是：對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的確信度對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類垛耳。也就是說栅屏，不僅將正負(fù)實(shí)例點(diǎn)分開，而且對(duì)最難分的實(shí)例點(diǎn)（離超平面最近的點(diǎn)）也有足夠大的確信度將他們分開堂鲜。這樣的超平面應(yīng)該對(duì)未知的新實(shí)例有很好的分類預(yù)測(cè)能力栈雳。

1.最大間隔分離超平面

下面考慮如何求一個(gè)幾何間隔最大的分離超平面，即最大間隔分離超平面缔莲。具體地哥纫，這個(gè)問題可以表示為下面的約束最優(yōu)化問題：
$\begin{align} \mathop{\max}_{\omega,b} \space \gamma \\ s.t. \space y_i(\frac{\omega}{\|\omega\|}*x_i+\frac{\|\omega\|}) \ge \gamma (i=1,2,\dots,N)\\ \end{align}$
即我們希望最大化超平面 $(\omega,b)$ 關(guān)于訓(xùn)練數(shù)據(jù)集的集合間隔 $\gamma$ 痴奏，約束條件表示的是超平面 $(\omega,b)$ 關(guān)于每個(gè)訓(xùn)練樣本點(diǎn)的集合間隔至少是 $\gamma$

考慮幾何間隔和函數(shù)間隔的關(guān)系式蛀骇，可將這個(gè)問題改成為
$\begin{align} \mathop{\max}_{\omega,b} \space \hat{\gamma} \\ s.t. \space y_i(\omega*x_i+b) \ge \hat{\gamma}) (i = 1,2,\dots,N)\\ \end{align}$
函數(shù)間隔 $\hat\gamma$ 并不影響最優(yōu)化問題的解。事實(shí)上读拆，假設(shè)將 $\omega和b$ 成比例改變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda%5Comega%E5%92%8C%5Clambda%20b" alt="\lambda\omega和\lambda b" mathimg="1">,這時(shí)函數(shù)間隔變成 $\lambda\hat\gamma$ 擅憔。函數(shù)間隔的改變對(duì)最優(yōu)化問題的不等式約束沒有影響，對(duì)目標(biāo)函數(shù)的優(yōu)化也沒有影響檐晕，也就事實(shí)說暑诸，它產(chǎn)生一個(gè)等價(jià)的最優(yōu)化問題。這樣辟灰，就可以取 $\hat\gamma=1$ 个榕。將 $\hat\gamm=1$ 代入上面的最優(yōu)化問題。注意最大化 $\frac{1}{\|\omega\|}$ 和最小化 $\frac{1}{2}\|\omega\|$ 是一樣的芥喇。

于是就得到下面的線性可分支持向量機(jī)學(xué)習(xí)的最優(yōu)化問題
$\begin{align} \mathop{\min}_{\omega,b} \space \frac{1}{2}\|\omega\|^2 \\ s.t. \space y_i(\omega*x_i+b)-1 \ge 0 (i = 1,2,\dots,N)\\ \end{align}$
這是一個(gè)凸二次規(guī)劃問題(contex quadratic programming)問題笛洛。
凸優(yōu)問題是指約束最優(yōu)化問題
$\begin{align} \mathop{\min}_{\omega} \space f(\omega) \\ s.t. \space g_i(\omega) \ge 0 (i = 1,2,\dots,N) \\ h_i(\omega) = 0(i=1,2,\dots,l) \end{align}$
其中，目標(biāo)函數(shù) $f(\omega)$ 和約束函數(shù) $g_i(\omega)$ 都是 $R^n$ 上的可連續(xù)可微的凸函數(shù)乃坤，約束函數(shù) $h_i(\omega)$ 是 $R^n$ 的仿射函數(shù)。當(dāng)木匾函數(shù)是 $f(\omega)$ 是二次函數(shù)且約束函數(shù) $g_i(\omega)$ 是仿射函數(shù)時(shí)沟蔑，上述的凸優(yōu)化問題成為凸二次規(guī)劃問題湿诊。
如果求出約束最優(yōu)化問題的解 $\omega^*,b^*$ ，那么就可以得出最大間隔分離超平面 $\omega^**x+b^*=0$ 及決策函數(shù) $f(x)=sign(\omega^*x+b^*)$ 瘦材，即線性可分支持向量機(jī)模型厅须。

五、學(xué)習(xí)的對(duì)偶算法

為了求解線性可分支持向量機(jī)的最優(yōu)化問題食棕，將它作為原始最優(yōu)化問題朗和，應(yīng)用到拉格朗日對(duì)偶性错沽，通過求解對(duì)偶問題得到原始問題的最優(yōu)解，這就是線性可支持向量機(jī)的對(duì)偶算法(dual algorithm)眶拉。這樣做的優(yōu)點(diǎn)千埃，一是對(duì)偶問題往往根據(jù)容易求解；二是自然引入核函數(shù)忆植，進(jìn)而推廣到非線性可分類問題放可。

首先構(gòu)建拉格朗日函數(shù)(Lagrange function)。為此朝刊，對(duì)每一個(gè)不等式約束引入拉格朗日乘子(Lagrange multiplier) $\alpha_i \ge 0 ,i=1,2,\dots,N$ 定義拉格朗日函數(shù)：
$L(\omega,b,\alpha)=\frac{1}{2}\|\omega\|^2-sum_{i=1}^N\alpha_iyi(\omega*x_i+b)+\sum_{i=1}^N \alpha_i$
其中 $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_N)^T$ 為拉格朗日乘子向量耀里。

根據(jù)拉格朗日對(duì)偶性，原始問題的對(duì)偶問題是極大極小問題 $\mathop{max}_{\alpha}\mathop{\min}_{\omega,b}L(\omega,b,\alpha)$

為了得到對(duì)偶函數(shù)問題的解拾氓，需要先求 $L(\omega,b,\alpha)$ 對(duì) $\omega,b$ 的極小冯挎，再求 $\alpha$ 的極大
(1)求 $\mathop{\min}_{\omega,b}L(\omega,b,\alpha)$
將拉格朗日函數(shù) $L(\omega,b,\alpha)$ 分別對(duì) $\omega,b$ 求偏導(dǎo)數(shù)并令其等于0
$\begin{align} \bigtriangledown_{\omega}L(\omega,b,\alpha)=\omega-\sum_{i=1}^N\alpha_iy_ix_i=0 \\ \bigtriangledown_bL(\omega,b,\alpha) = -sum_{i=1}^N\alpha_iy_i=0 \\ \omega = \sum_{i=1}^N\alpha_iy_ix_i=0 \space(1)\\ \sum_{i=1}^N\alpha_iy_i=0 \space(2) \end{align}$

將（1）代入拉格朗日函數(shù)，并利用(2)咙鞍，即可得
$\begin{equation}\label{eq1} \begin{split} L(\omega,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)*x_i+b)+ \sum_{i=1}^N\alpha_i \\ =-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \end{split} \end{equation}$
即
$\mathop{\min}_{\omega,b}=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i$
(2)求 $\mathop{\min}_{\omega,b}$ 對(duì) $\alpha$ 的極房官，即對(duì)偶問題
$\mathop{max}_{\omega} \space -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)$
$s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N)$
將公式(3)的目標(biāo)函數(shù)由極大值轉(zhuǎn)換成求極小，就得到下面與之等價(jià)的對(duì)偶最優(yōu)化問題
$\mathop{min}_{\omega} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)$
$s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N) \space(4)$

(3)解 $\omega^*,b^*$
假設(shè) $\alpha^*=(\alpha_1^*,\alpha_2^*,\dots,\alpha_l^*)^T$ 是對(duì)偶最優(yōu)化問題的解奶陈，則存在下標(biāo)使得 $\alpha_j^* > 0$ 易阳，并求按下式求得原始最優(yōu)化的解 $\omega^*,b$

根據(jù)KKT條件成立，即得
$\begin{equation}\label{eq1} \begin{split} \bigtriangledown_{\omega}L(\omega^*,b^*,\alpha^*) = \omega^*-\sum_{i=1}^N\alpha_i^*y_ix_i = 0\\ \bigtriangledown_b L(\omega^*,b^*,\alpha^*)=-\sum_{i=1}^N \alpha_i^*y_i =0 \\ \alpha_i^*(y_i(\omega^**x_i+b^*)-1) \ge 0,i=1,2,\dots,N \\ y_i(\omega^**x_i+b^*)-1 \ge 0,i =1,2,\dots,N \\ \alpha_i^* \ge 0 ,i =1,2,\dots,N \end{split} \end{equation}$
因此
$\omega^*=\sum_{i=1}^N \alpha_i^*y_ix_i\space(5)$
$y_j^2=1$ ,且至少存在一個(gè) $\alpha_j > 0$ 吃粒，假設(shè) $\alpha^* = 0$ ,那么 $\omega= 0$ 不是原始問題的解,所以
$b^{*}=y_j-\sum_{i=1}^N \alpha_i^*y_i(x_i*x_j) \space(6)$

那么分離的超平面可以寫成
$\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*=0\space(7)$
決策函數(shù)可以寫成
$f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*) \space (8)$

由此可以看出潦俺，分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積，式（8）稱為線性可分支持向量機(jī)的對(duì)偶形式徐勃。

案例
訓(xùn)練數(shù)據(jù)正例點(diǎn)是 $x_1 = (3,3)^T,x_2=(4,3)^T$ 事示，負(fù)例點(diǎn)是 $x_3=(1,1)^T$ ，試用線性可分支持向量機(jī)
解：根據(jù)所給數(shù)據(jù)僻肖，對(duì)偶問題是
$\begin{equation}\label{eq1} \begin{split} \mathop{\min}_{\alpha} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_i \\ = \frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3)-\alpha_1-\alpha_2-\alpha_3 \\ s.t. \space \alpha_1+\alpha_2-\alpha_3 = 0 \\ \alpha_i \ge 0,i =1,2,3 \end{split} \end{equation}$

兩個(gè)向量 $\overrightarrow{a}=[a_1,a_2,\dots,a_n]$ 和 $\overrightarrow肖爵=[b_1,b_2,\dots,b_n]$ 的點(diǎn)積定義為：
$\overrightarrow{a} \ast \overrightarrow = \sum_{i=1}^Na_ib_i=a_1b_1+a_2b_2+\dots+a_nb_n$

解這一優(yōu)化問題臀脏，將 $a_3=a_1+a_2$ 代入目標(biāo)函數(shù)并記為
$s(a_1,a_2)=4a_1^2+\frac{13}{2}a_2^2+10a_1a_2-2a_1-2a_2$

對(duì) $a_1,a_2$ 求偏導(dǎo)令其為0劝堪，易知 $s(a_1,a_2)在點(diǎn)(\frac{3}{2},-1)^T$ 處取極值，該點(diǎn)不滿足約束條件 $a_2\ge 0$ 揉稚，所以最小值應(yīng)在邊界上達(dá)到秒啦。

當(dāng) $a_1 = 0時(shí)，最小值s(0,\frac{2}{13})=-\frac{2}{13}$ 搀玖，當(dāng) $a_2=0時(shí)余境，最小值s(\frac{1}{4},0)=-\frac{1}{4}$ ，于是 $s(a_1,a_2)在a_1=\frac{1}{4}，a_2=0處最小芳来，此時(shí)a_3=a_1+a_2=\frac{1}{4}$

這樣, $a_1^*=a_2^*=\frac{1}{4}$ 對(duì)應(yīng)的實(shí)例點(diǎn) $x_1,x_3$ 是支持向量含末，計(jì)算可得 $w_1^*=w_2^*=\frac{1}{2}$ , $b^*=-2$

分離超平面為 $\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0$
分離決策函數(shù)為 $f(x)=sign(\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2)$

六、軟間隔最大化

線性可分問題的支持向量機(jī)學(xué)習(xí)方法即舌，對(duì)線性不可分訓(xùn)練數(shù)據(jù)是不適用的院崇，因?yàn)檫@時(shí)上述方法中的不等式約束不能都成立没讲。線性不可分意味著不能滿足函數(shù)間隔大于等于1的約束條件。為了解決這個(gè)問題，對(duì)每個(gè)樣本點(diǎn) $(x_i,y_i)$ 都引入一個(gè)松弛變量 $\xi_i \ge 0$ 政己，使得函數(shù)間隔加上變量大于等于1懈凹，這樣約束條件變?yōu)?br> $y_i(w*x_i+b) >= 1 -\xi_i$
同時(shí)對(duì)于每個(gè)松弛變量 $\xi_i$ 泪蔫，支付一個(gè)代價(jià) $\xi_i$ ,目標(biāo)函數(shù)由原來的 $\frac{1}{2}\|w\|^2$ 變成
$\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i \space(6.1)$
C>0為懲罰參數(shù)蹦狂，一般由應(yīng)用問題解決，C值大時(shí)對(duì)誤分類的懲罰增大嗦明，C值小時(shí)對(duì)誤分類的懲罰減小笼沥。最小化木匾函數(shù)有2層意思：使得 $\frac{1}{2}\|2\|^2$ 盡量小，即間隔盡量大娶牌，同時(shí)使誤分類點(diǎn)的個(gè)數(shù)盡量小奔浅，C是調(diào)和兩者的系數(shù)

七、非線性支持向量機(jī)與核函數(shù)

1.背景知識(shí)

(1)核技巧

非線性分類問題是指通過非線性模型才能很好地進(jìn)行分類的問題诗良。非線性問題往往不好求解汹桦，希望通過線性分類問題的方法解決這個(gè)問題，所采取的方法是進(jìn)行一個(gè)非線性變換鉴裹，將非線性問題變成線性問題舞骆，通過解變換后的線性問題的方法求解原來的非線性問題。

用線性分類方法求解非線性分類問題分兩步：首先使用一個(gè)變換將原來空間的數(shù)據(jù)映射到新空間径荔；然后在新空間里用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型督禽。核技巧就屬于這樣的方法。

(2)核函數(shù)定義

設(shè)X是輸入空間（歐氏空間 $R^n$ 的子集或離散集合）总处，又設(shè)H為特征向量（希伯而空間H）狈惫，如果存在一個(gè)從X到H的映射
$\phi(x):X \to H$
使得對(duì)所有 $x,z \in X$ ，函數(shù) $K(x,z)$ 滿足條件
$K(x,z)=\phi(x)*\phi(z)$
則稱K(x,z)為核函數(shù)鹦马， $phi(x)$ 為映射函數(shù)胧谈， $\phi(x)*\phi(z)為\phi(x)和\phi(z)的內(nèi)積$ 。通常計(jì)算K(x,z)比較容易荸频，而通話 $\phi(x)和\phi(z)$ 計(jì)算K(x,z)并不容易第岖。

$\phi$ 是輸入空間到特征空間的迎神，特征空間一般是高維的试溯，甚至是無窮維，可以看到郊酒，對(duì)于給定的核K(x,z)遇绞，特征空間H和映射函數(shù) $\phi$ 的取法并不唯一键袱，可以取不同的特征空間，即便是在同一特征空間也可以取不同的映射摹闽。

(3)核技巧在支持向量機(jī)中的應(yīng)用

在對(duì)偶目標(biāo)函數(shù)中的內(nèi)積 $x_i*x_j$ 可以用核函數(shù) $K(x,z)=\phi(x)*\phi(z)$ 來代替蹄咖，此時(shí)對(duì)偶問題的目標(biāo)函數(shù)成為
$W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$
這等價(jià)于經(jīng)過映射函數(shù) $\phi$ 將原來的輸入空間變換到一個(gè)新的特征空間，將輸入空間中的內(nèi)積 $x_i*x_j$ 變換成特征空間中的內(nèi)積 $\phi(x_i)*\phi*(x_j)$ 付鹿，在新的特征空間里從訓(xùn)練樣本中學(xué)習(xí)線性支持向量機(jī)澜汤。學(xué)習(xí)是隱式地在特征空間進(jìn)行的，不需要顯式地定義特征空間和營業(yè)日函數(shù)舵匾。在實(shí)際應(yīng)用中俊抵，往往依賴領(lǐng)域知識(shí)直接選擇核函數(shù)。

2.常用核函數(shù)

(1)多項(xiàng)式核函數(shù)(polynomial kernal function)

$K(x,z)=(x*z+1)^p$
對(duì)應(yīng)的支持向量機(jī)是一個(gè)p次多項(xiàng)式分類器坐梯，在此情形下徽诲，分類決策函數(shù)成為
$f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(x_i*x+1)^p+b^*)$

(2)高斯核函數(shù)(Guassian kernel function)

$K(x,z)=exp(-\frac{\|x-z\|^2}{2\sigma^2})$
對(duì)應(yīng)的支持向量機(jī)是高斯徑向基函數(shù)(radial basis function)分類器。在此情形下吵血，分類決策函數(shù)成為
$f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(exp(-\frac{\|x-z\|^2}{2\sigma^2})+b^*)$

(3)字符串核函數(shù)

核函數(shù)不僅可以定義在歐式空間谎替，還可以定義在離散數(shù)據(jù)的集合上。比如蹋辅，字符串核函數(shù)是定義在字符串集合上的核函數(shù)钱贯。字符串核函數(shù)在文本分類、信息檢索侦另、生物信息學(xué)等方面都有應(yīng)用秩命。

兩個(gè)字符串s和t上的字符串核函數(shù)是基于映射 $\phi_n$ 的特征空間中的內(nèi)積：
$k_n(s,t)=\sum_{\mu \in \Sigma^n}[\phi_n(s)]_{\mu}[\phi_n(t)]_{\mu}$
$=\sum_{\mu \in \Sigma^n}\sum_{(i,j):s(i)=t(j)=\mu}\lambda^{l(i)}\lambda^{l(j)}$
字符串核函數(shù) $k_n(s,t)$ 給出了字符串s和t中長度等于n的所有子串組成的特征向量的余弦相似度。直觀上看淋肾，兩個(gè)字符串相同的字串越多硫麻，它們就越相似，字符串核函數(shù)的值就越大樊卓。字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速地計(jì)算拿愧。

八、序列最小最優(yōu)化算法

支持向量機(jī)的學(xué)習(xí)問題可以形式化為求解凸二次規(guī)劃問題碌尔，這樣的凸二次規(guī)劃問題具有全局最優(yōu)解浇辜，并且有許多最優(yōu)化算法可以用于這一問題的求解。但是當(dāng)訓(xùn)練樣本容量很大時(shí)唾戚，這些算法往往變得非常低效柳洋，以至無法使用。

序列最小最優(yōu)化(sequential minimal optimization,SMO)算法叹坦，是一種啟發(fā)式算法熊镣，其基本思路是：如果所有變量的解都滿足此最優(yōu)化問題的KKT條件，那么這個(gè)最優(yōu)化問題的解就得到了。因?yàn)镵KT條件是該最優(yōu)化問題的充分必要條件绪囱。否則测蹲，選擇兩個(gè)變量，固定其他變量鬼吵，針對(duì)這兩個(gè)變量構(gòu)建一個(gè)二次規(guī)劃問題扣甲。這個(gè)二次規(guī)劃問題的目標(biāo)是使函數(shù)值變得更小。重要的是齿椅，這時(shí)子問題可以通過解析方法求解琉挖，這樣就可以大大提高整個(gè)算法的計(jì)算速度。子問題有兩個(gè)變量涣脚，一個(gè)是違反KKT條件最嚴(yán)重的那一個(gè)示辈，另一個(gè)由約束條件自動(dòng)確定。如此涩澡，SMO算法將原問題不斷分解為子問題并對(duì)子問題求解顽耳，進(jìn)而達(dá)到求解原問題的目的。

1.兩個(gè)變量二次規(guī)劃的求解辦法

假設(shè)兩個(gè)變量是 $\alpha_1,\alpha_2$ 妙同，其他變量 $\alpha_i(i=3,4,\dots,N)$ 是固定的射富，于是SNO的最優(yōu)化問題的子問題可以寫成。

$\begin{align} \mathop{min}_{\alpha_1,\alpha_2} \space W(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2 \\ -(\alpha_1+\alpha_2)+y_1\alpha_1\sum{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_iK_{i2} \space(7.1) \\ s.t. \alpha_1y_1+\alpha_2y_2 = - \sum_{i=3}^N y_i \alpha_i = \zeta \space(7.2)\\ 0 \leq \alpha_i \leq C \space(7.3) (i =1,2) \end{align}$
其中粥帚， $K_{ij}=K(x_i,x_j),i,j=1,2,\dots,N,\zeta$ 是常數(shù)胰耗，目標(biāo)函數(shù)中省略不含 $\alpha_1,\alpha_2$ 的常數(shù)項(xiàng)。

為了求解兩個(gè)變量的二次規(guī)劃問題芒涡，約束可以用二維空間中的圖形表示

二變量優(yōu)化問題.png

不等式約束(7.3)使得 $(\alpha_1,\alpha_2)$ 在盒子[0,C][0,C]內(nèi)柴灯，等式約束(7.2)使 $(\alpha_1,\alpha_2)$ 在平行于盒子[0,C][0,C]的對(duì)角線的直線上。因此要求的是目標(biāo)函數(shù)在一條平行于對(duì)角線的線段上最優(yōu)值费尽。這使得兩個(gè)變量的最優(yōu)化問題成為實(shí)質(zhì)上的單變量最優(yōu)化文圖赠群，不訪考慮為變量 $\alpha_2$ 的最優(yōu)化問題。

假設(shè)初始化可行解為 $\alpha_1^{old},\alpha_2^{old}$ 旱幼，最優(yōu)化解為 $\alpha_1^{new},\alpha_2^{new}$ 查描，并且假設(shè)沿著約束方向未經(jīng)剪輯時(shí) $\alpha_2$ 的最優(yōu)解為 $\alpha_2^{new,func}$

由于 $\alpha_2^{new}$ 需滿足不等式約束(7.3)，所以最優(yōu)值 $\alpha_2^{new}$ 的取值范圍必須滿足條件
$L \leq \alpha_2^{new} \leq H$
其中柏卤，L與H是 $\alpha_2^{new}$ 所在對(duì)角線段端點(diǎn)的界冬三，如果 $y_1 \ne y_2$
$L = max(0,\alpha_2^{old}-\alpha_1^{old}),H=min(C,C+\alpha_2^{old}-\alpha_1^{old})$
如果 $y_1 = y_2$ ，則
$L=max(0,\alpha_2^{old}+\alpha_1^{old}-C),H=min(C,a_2^{old},a_1^{old})$

下面首先要求沿著約束方向未經(jīng)剪輯即未考慮不等式約束(7.3)時(shí) $a_2$ 的最優(yōu)解 $a_2^{new,func}$ 缘缚，然后在解決剪輯后 $a_2$ 的解 $a_2^{new}$ 勾笆，我們用定理來描述這個(gè)結(jié)果
$g(x)=\sum_{i=1}^Na_iy_uK(x_i,x)+b \space (7.4)$
令
$E_i=g(x_i)-y_i=(\sum_{j=1}^Na_jy_jK(x_j,x_i)+b)-y_i(i=1,2) \space(7.5)$

當(dāng)i=1,2時(shí)， $E_i$ 為函數(shù)g(x)對(duì)輸入 $x_i$ 的預(yù)測(cè)值與真實(shí)輸出 $y_i$ 之差

定理最優(yōu)化問題(7.1)~(7.3)沿著約束方向未經(jīng)剪輯時(shí)的解是
$a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{\eta$
其中 $\eta=K_{11}+K_{22}-2K_{12}=\|Phi(x_1)-\Phi(x_2)\|^2$
$\Phi(x)$ 是輸入空間到特征空間的映射

經(jīng)剪輯后的 $a_2$ 的解是
$a_2^{new} = \begin{cases} H & \quad a^{new,func} > H \\ a^{new,func}& \quad L \leq a_2^{new,func} \leq H \\ L & \quad a_2^{new,func} < L \end{cases}$
由 $a_2^{new}求得a_1^{new}$ 是
$a_1^{new} = a_1^{old}+y_1y_2(a_2^{old}-a_2^{new})$

最后編輯于：2019.08.04 10:28:47

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末桥滨，一起剝皮案震驚了整個(gè)濱河市窝爪，隨后出現(xiàn)的幾起案子弛车，更是在濱河造成了極大的恐慌，老刑警劉巖蒲每，帶你破解...
沈念sama閱讀 222,946評(píng)論 6贊 518
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件帅韧，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡啃勉，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,336評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門双妨，熙熙樓的掌柜王于貴愁眉苦臉地迎上來淮阐，“玉大人，你說我怎么就攤上這事刁品∑兀” “怎么了？”我有些...
開封第一講書人閱讀 169,716評(píng)論 0贊 364
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵挑随，是天一觀的道長状您。經(jīng)常有香客問我，道長兜挨，這世上最難降的妖魔是什么膏孟？我笑而不...
開封第一講書人閱讀 60,222評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮拌汇，結(jié)果婚禮上柒桑，老公的妹妹穿的比我還像新娘。我一直安慰自己噪舀，他們只是感情好魁淳，可當(dāng)我...
茶點(diǎn)故事閱讀 69,223評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著与倡，像睡著了一般界逛。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上纺座，一...
開封第一講書人閱讀 52,807評(píng)論 1贊 314
城市分裂傳說
那天息拜，我揣著相機(jī)與錄音，去河邊找鬼比驻。笑死该溯，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的别惦。我是一名探鬼主播狈茉，決...
沈念sama閱讀 41,235評(píng)論 3贊 424
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼掸掸！你這毒婦竟也來了氯庆？” 一聲冷哼從身側(cè)響起蹭秋，我...
開封第一講書人閱讀 40,189評(píng)論 0贊 277
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎堤撵，沒想到半個(gè)月后仁讨，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,712評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡实昨，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,775評(píng)論 3贊 343
?白月光啟示錄
正文我和宋清朗相戀三年洞豁，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片荒给。...
茶點(diǎn)故事閱讀 40,926評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡丈挟，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出志电，到底是詐尸還是另有隱情曙咽，我是刑警寧澤，帶...
沈念sama閱讀 36,580評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布挑辆，位于F島的核電站例朱，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏鱼蝉。R本人自食惡果不足惜洒嗤，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,259評(píng)論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望蚀乔。院中可真熱鬧烁竭，春花似錦、人聲如沸吉挣。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,750評(píng)論 0贊 25
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽睬魂。三九已至终吼，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間氯哮，已是汗流浹背际跪。一陣腳步聲響...
開封第一講書人閱讀 33,867評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留喉钢，地道東北人姆打。一個(gè)月前我還...
沈念sama閱讀 49,368評(píng)論 3贊 379
代替公主和親
正文我出身青樓，卻偏偏與公主長得像肠虽，于是被迫代替她去往敵國和親幔戏。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,930評(píng)論 2贊 361