【機(jī)器學(xué)習(xí)】算法原理詳細(xì)推導(dǎo)與實(shí)現(xiàn)(四):支持向量機(jī)(上)

在之前的文章中薄货，包括線性回歸和邏輯回歸螃征，都是以線性分界線進(jìn)行分割劃分種類的碎绎。而本次介紹一種很強(qiáng)的分類器【支持向量機(jī)】蝇狼，它適用于線性和非線性分界線的分類方法阅畴。

函數(shù)間隔概念

為了更好的理解非線性分界線，區(qū)別兩種分界線對(duì)于分類的直觀理解迅耘，第一種直觀理解需要考慮 logistic 回歸贱枣，我們用一個(gè) logistic 回歸函數(shù)表示當(dāng) $y=1$ 時(shí)概率表示為：

$\begin{split} p(y=1|x;\theta)&=h(\theta) \\ &=g({\theta}^Tx) \\ &=g(z) \\ \end{split}$

當(dāng) $h(\theta) \geq 0.5$ 時(shí)，即 ${\theta}^Tx \geq 0$ 時(shí) $y=1$ 颤专；同理當(dāng) $h(\theta) < 0.5$ 時(shí)纽哥，即 ${\theta}^Tx < 0$ 時(shí) $y=0$ ⊙回顧 logistic 回歸的圖像如下所示：

image

由上圖可以看出：如果 ${\theta}^Tx >> 0$ 時(shí)昵仅，那么可以相當(dāng)確定的預(yù)測(cè) $y=1$ 缓熟；如果 ${\theta}^Tx << 0$ 時(shí)累魔，那么可以相當(dāng)確定的預(yù)測(cè) $y=0$

當(dāng)我們根據(jù)這樣的樣本擬合logistic 回歸得出分類器時(shí)，這樣的分類器是良好的够滑。即對(duì)于所有的 $i$ 垦写，如果 $y^{(i)}=1$ ，那么 ${\theta}^Tx^{(i)} >> 0$ 彰触；如果 $y^{(i)}=0$ 梯投，那么 ${\theta}^Tx^{(i)} << 0$ 。換句話說况毅，如果我們根據(jù)訓(xùn)練集找到了合適的參數(shù) $\theta$ 分蓖，那么我們的學(xué)習(xí)算法不僅會(huì)保證分類結(jié)果正確，更會(huì)進(jìn)一步的保證對(duì)分類結(jié)果的 確定性尔许。

假設(shè)訓(xùn)練集都是線性可分隔的么鹤，即一定有一條直線可以將訓(xùn)練集分開，假設(shè) ${\theta}^Tx^{(i)} =0$ 代表中間那條分隔線味廊，使得正樣本和負(fù)樣本到這條線的距離最大蒸甜，即這條線是最優(yōu)的分隔線：

image

考慮上面3個(gè)點(diǎn) A 棠耕、B和C。從圖中我們可以確定A是×類別的柠新，然而C我們是不太確定的窍荧，B還算能夠確定。logistic 回歸強(qiáng)調(diào)所有的點(diǎn)盡可能的遠(yuǎn)離中間那條線即可恨憎，由此可能造成如上所示蕊退，點(diǎn)C可能屬于o類別也可能屬于×類別，所以我們這里希望找到一個(gè)分隔線憔恳，使其所有的分類結(jié)果有足夠的 確定性咕痛，這就是logistic 回歸和支持向量機(jī)的不同點(diǎn)。

間隔器

函數(shù)間隔

支持向量機(jī)的符號(hào)和logistic 回歸的符號(hào)有點(diǎn)差別喇嘱。支持向量機(jī)的取值范圍是 $y \in \{-1, 1\}$ 茉贡，而logistic 回歸的取值范圍是 $y \in \{0, 1 \}$

logistic 回歸的假設(shè)函數(shù)為：

$\begin{split} h(x)&=\theta_0x_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n \\ &=\theta^Tx \end{split}$

其中這里假設(shè) $x_0=1$ 。而支持向量機(jī)假設(shè) $\theta_0=b$ 者铜，即假設(shè)函數(shù)為：

$\begin{split} h(x)&=\theta_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n \\ &=b+\omega_1x_1+\omega_2x_2+...+\omega_nx_n \\ &=\omega^Tx+b \end{split}$

即為：

$h_{w,b}(x)=g(\omega^Tx+b)$

將其假設(shè)函數(shù)映射到 $y \in \{-1, 1 \}$ 上：

$g(z)= \begin{cases} 1, & \text{z $\geq$ 0} \\ -1, & \text{z<0} \end{cases}$

給定一個(gè)訓(xùn)練樣本 $(x^{(i)}, y^{(i)})$ 腔丧，那么定義支持向量機(jī)的間隔函數(shù)為：

$\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$

對(duì)于這個(gè)式子的理解是:

如果 $y^{(i)}=1$ ，為了獲得較大的函數(shù)間隔作烟，你需要令 $(\omega^Tx+b)$ 取得較大值愉粤，即 $(\omega^Tx+b) >> 0$ ，得到的 $\hat{\gamma}^{(i)}$ 是一個(gè)大正數(shù)
如果 $y^{(i)}=-1$ 拿撩，為了獲得較大的函數(shù)間隔衣厘，那么唯一使其獲得較大值的方式是，令 $(\omega^Tx+b) << 0$ 压恒，得到的 $\hat{\gamma}^{(i)}$ 是一個(gè)大負(fù)數(shù)

這個(gè)定義捕捉到了我們之前對(duì)于函數(shù)間隔的直觀理解的特點(diǎn)影暴，在之前logistic 回歸的直觀理解中，如果 $y^{(i)}=1$ 探赫，我們希望 $(\omega^Tx+b)$ 取較大的值型宙；如果 $y^{(i)}=-1$ ，我們希望 $(\omega^Tx+b)$ 取較小的值伦吠，這個(gè)定義用一個(gè)公式捕捉到了妆兑，我們希望函數(shù)間隔去較大值的兩種情況。

上面定義的某一個(gè)樣本的函數(shù)間隔為： $\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$ 毛仪，那么針對(duì)全局樣本得到的一個(gè)超平面的函數(shù)間隔定義為：

$\hat{\gamma}=min\hat{\gamma}^{(i)},(i=1,2,...,m)$

代表在全部的訓(xùn)練樣本上搁嗓，以分類正例和負(fù)例置信度最低的那個(gè)函數(shù)間隔為準(zhǔn)，即 函數(shù)間隔是最差的情況箱靴，也要能很好的分類正負(fù) 腺逛。

實(shí)際上，這種直觀理解存在一個(gè)小問題刨晴，要使函數(shù)間隔取較大的值是非常容易的屉来，比如說：如果我們的參數(shù)是 $\omega$ 和 $b$ 路翻，那么我們可以將 $\omega$ 變?yōu)樵瓉淼?code>2倍，將 $b$ 也變?yōu)樵瓉淼?code>2倍：

$\omega \to 2\omega茄靠，b \to 2b$

那么根據(jù)函數(shù)間隔的定義：

$\hat{\gamma}^{(i)}=y^{(i)}(\omega^Tx+b)$

如果把 $\omega$ 和 $b$ 變?yōu)樵瓉淼?code>2倍茂契，那么我可以很容易的使函數(shù)間隔加倍。所以單純的以最大化函數(shù)間隔為目標(biāo)是沒有多大意義的掉冶，因?yàn)橥ㄟ^對(duì)參數(shù)翻倍就可以使函數(shù)間隔獲得任意大的值，也許我們可以解決這個(gè)問題脐雪。通過添加一個(gè)正規(guī)化條件厌小，使得 $\omega$ 的長度為1，即 $||\omega||=1$

幾何間隔

分類器的確定邊界會(huì)由平面給出战秋，假設(shè)存在一個(gè) $B$ 點(diǎn)在分割面上璧亚，其他任何一點(diǎn)，比如 $A$ 點(diǎn)到分割面的距離脂信，這就是幾何間隔

image

那么上圖的 $A$ 點(diǎn)和分割面成 $90°$ 夾角癣蟋，即法向量表示為 $\frac{\omega}{||\omega||}$ ， $A$ 點(diǎn)到分割面的距離為 ${\gamma}$ （沒有帽子的是幾何間隔狰闪，有帽子的是函數(shù)間隔 $\hat{\gamma}$ ）疯搅，假設(shè) $A$ 點(diǎn)的坐標(biāo)為 $(x^{(i)},y^{(i)})$ ， $B$ 點(diǎn)的坐標(biāo)為(x,y)埋泵，那么可以得到 $x=x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||}$ (利用初中的幾何知識(shí))幔欧，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B%5Comega%7D%7B%7C%7C%5Comega%7C%7C%7D" alt="\frac{\omega}{||\omega||}" mathimg="1">是長度為1且與超平面垂直的單位向量，用點(diǎn) $x^{(i)}$ 減掉 ${\gamma}^{(i)}\frac{\omega}{||\omega||}$ 就是超平面上面點(diǎn) $B$ 的 $x$ 坐標(biāo)了丽声。因?yàn)榉指蠲嫔厦娴狞c(diǎn)都滿足 $\omega^Tx+b=0$ 礁蔗，而點(diǎn)B在分割面上，所以也滿足 $\omega^Tx+b=0$ 恒序，瘦麸，即：

$\omega^T(x^{(i)}-{\gamma}^{(i)}\frac{\omega}{||\omega||})+b=0$

進(jìn)一步化簡得到：

${\gamma}^{(i)}=\frac{\omega^Tx^{(i)}+b}{||\omega||}=(\frac{\omega}{||\omega||})^Tx^{(i)}+\frac谁撼{||\omega||}$

上述是假設(shè)已經(jīng)對(duì)樣本分好了正確的類別歧胁，那么如果點(diǎn) $A$ 是樣本，即很多個(gè)類似于點(diǎn) $A$ 的樣本 $(x^{(i)},y^{(i)})$ 厉碟，那么上述公式轉(zhuǎn)化為：

${\gamma}^{(i)}=y^{(i)}((\frac{\omega}{||\omega||})^Tx^{(i)}+\frac喊巍{||\omega||})$

現(xiàn)在這樣子的形式和之前的函數(shù)間隔形式非常相似，除了在這里我們對(duì)向量 $\omega$ 進(jìn)行了標(biāo)準(zhǔn)化箍鼓。所以像之前一樣崭参，我們希望幾何間隔取較大的值，也就是意味著如果我們對(duì)訓(xùn)練樣本進(jìn)行了正確的分類款咖，那么這些樣本在分類正確的一面距離分割面的距離越大越好何暮，這里用乘上 $y^{(i)}$ 來判斷樣本正負(fù)分類的方向奄喂。

這里有幾個(gè)非常容易得到的結(jié)論：

如果 $||\omega||=1$ ，那么函數(shù)間隔等于幾何間隔

幾何間隔=函數(shù)間隔 / $||\omega||$

同樣海洼，如果同時(shí)擴(kuò)大 $\omega$ 和 $b$ 跨新，那么 $||\omega||$ 也會(huì)相應(yīng)的擴(kuò)大，結(jié)果無影響坏逢。所以針對(duì)全局樣本得到的一個(gè)超平面的函數(shù)間隔定義為：

$\gamma=min \gamma ^{(i)},(i=1,2,...,m)$

最優(yōu)間隔分類器

最優(yōu)間隔分類器是指選擇合適的 $\gamma$ 域帐、 $\omega$ 、 $b$ 是整，使得間隔最大肖揣，也就是說滿足函數(shù)：

$max_{\gamma,\omega,b}->\gamma$

$y^{(i)}(\omega^Tx+b) \geq \gamma,(||\omega||=1)$

慮幾何間隔和函數(shù)間隔的關(guān)系，即 $\gamma=\frac{\hat{\gamma}}{||\omega||}$ 浮入，那么上面可以轉(zhuǎn)化為：

$max_{\gamma,\omega,b}->\frac{\hat{\gamma}}{||\omega||}$

$y^{(i)}(\omega^Tx+b) \geq \hat{\gamma}$

這樣子就取消了 $||\omega||=1$ 的約束了龙优，但是目標(biāo)函數(shù)目前不是凸函數(shù)，無法求得最優(yōu)值事秀，沒發(fā)直接帶入優(yōu)化算法里面去計(jì)算陋率，所以這里還是需要改寫一下。前面說到同時(shí)擴(kuò)大 $\omega$ 和 $b$ 對(duì)結(jié)果沒有影響秽晚，但我們最后要求的仍然是 $\omega$ 和 $b$ 的確定值瓦糟，不是他們的一組倍數(shù)值，因此赴蝇，我們需要對(duì) $\hat{\gamma}$ 做一些限制菩浙，以保證我們解是唯一的。這里為了簡便取 $\hat{\gamma}=1$ 句伶，這樣的意義是將全局的函數(shù)間隔定義為 1 劲蜻，也即是將離超平面最近的點(diǎn)的距離定義為 $\frac{1}{||\omega||}$ 。這里解釋一下為什么這么定義考余，因?yàn)榍蠼?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cfrac%7B1%7D%7B%7C%7C%5Comega%7C%7C%7D" alt="\frac{1}{||\omega||}" mathimg="1">的最大值相當(dāng)于求 $\frac{1}{2}||\omega||^2$ 的最小值先嬉，因此改寫的結(jié)果為：

$min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2$

$y^{(i)}(\omega^Tx+b) \geq 1$

這下定義變成只有線性約束了，而且是個(gè)典型的二次規(guī)劃問題（目標(biāo)函數(shù)是自變量的二次函數(shù)）楚堤，利用算法可以輕松求解疫蔓。

拉格朗日對(duì)偶

含有等式約束形式的求解最值

這里需要用到微積分知識(shí)中的拉格朗日乘子法，它可以用來求解像這樣的優(yōu)化問題身冬，例如在滿足一定數(shù)量的約束條件的前提下衅胀，求解最小化、最大化問題酥筝，在這里先簡要的介紹一下它的一種一般化的形式滚躯。拉格朗日乘子法是這樣的：假設(shè)有一個(gè)函數(shù) $f(\omega)$ ，你想使他最大化或者最小化，與此同時(shí)需要滿足一些約束條件：

$min_{\omega}->f(\omega)$

對(duì)于每個(gè) $i$ 掸掏，必須保證約束函數(shù)的值為0：

$h_i(\omega)=0,i=1,2,...,l$

給定這些約束茁影，我可以寫成向量的形式，將整個(gè)向量表示成 $h(\omega)$ ：

$\begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ ... \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0}$

上面表示所有的元素都是 $0$ 向量丧凤。如果像求解這個(gè)最優(yōu)化問題呼胚，利用拉格朗日乘子法，首先應(yīng)該創(chuàng)建一個(gè)拉格朗日算子：

$\Gamma(\omega,\beta)=f(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

它應(yīng)該等于原始的目標(biāo)函數(shù)加上這些限制函數(shù)的線性組合息裸，這些參數(shù) $\beta_i$ 被稱為拉格朗日算子蝇更，然后解決這個(gè)問題的方法是，對(duì)每一個(gè)原始值求偏導(dǎo)之后將其設(shè)為0：

$\frac{\partial_{\Gamma}}{\partial_{\omega_i}}=0;\frac{\partial_{\Gamma}}{\partial_{\beta_i}}=0$

分別對(duì) $\omega$ 和 $\beta$ 求偏導(dǎo)呼盆，使其偏導(dǎo)數(shù)等于0年扩，理論上可以解出一個(gè) $w^*$ 最優(yōu)解，是這個(gè)最優(yōu)解的必要條件是：存在 $\beta^*$ 使得這些偏導(dǎo)數(shù)的值為0访圃。所以根據(jù)這個(gè)結(jié)論厨幻，求解的過程是：

用拉格朗日乘子法創(chuàng)建一個(gè)拉格朗日算子

之后相對(duì)于原始參數(shù) $\omega$ 和拉格朗日算子 $\beta$ 求偏導(dǎo)數(shù)，并令偏導(dǎo)數(shù)等于0

之后對(duì)方程組進(jìn)行求解腿时，最后檢查下得到的解是否確實(shí)為一個(gè)最小值

至于為什么引入拉格朗日乘子法可以求出極值况脆，原因是 $f(\omega)$ 的 $d_{\omega}$ 變化方向受其他不等式的約束， $d_{\omega}$ 的變化方向與 $f(\omega)$ 的梯度垂直時(shí)才能獲得極值，而且在極值處， $f(\omega)$ 的梯度與其他等式梯度的線性組合平行易遣，因此他們之間存在線性關(guān)系锨咙。(kkt條件)

含不等式約束形式的求解最值

然后我們探討有不等式約束的極值問題求法准谚，假設(shè)不僅僅存在約束條件 $h_i(\omega)=0$ ，還存在約束條件 $g_i(\omega)\leq 0$ ，問題如下所示：

$min_{\omega}->f(\omega)$

對(duì)于每個(gè) $i$ ，必須保證約束函數(shù) $h(\omega)$ 的值為0：

$h_i(\omega)=0,i=1,2,...,l$

對(duì)于每個(gè) $i$ 悄但，必須保證約束函數(shù) $g(\omega)$ 的值小于等于0：

$g_i(\omega)\leq 0,i=1,2,...,k$

給定這些約束，我可以寫成向量的形式石抡，可以用向量表示成：

$\begin{bmatrix} h_1(\omega) \\ h_2(\omega) \\ ... \\ h_l(\omega) \\ \end{bmatrix} = \overrightarrow{0}$

$\begin{bmatrix} g_1(\omega) \\ g_2(\omega) \\ ... \\ g_k(\omega) \\ \end{bmatrix} \leq \overrightarrow{0}$

在這種情況下檐嚣，既有等式約束條件也有不等式約束條件，那么利用拉格朗日乘子法啰扛，首先應(yīng)該創(chuàng)建兩個(gè)拉格朗日算子：

$\Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

這里的 $\alpha_i$ 和 $\beta_i$ 都是拉格朗日算子嚎京。如果按這個(gè)公式和之前的方法求解，即求解最小值 $min f(\omega)$ 會(huì)出現(xiàn)問題侠讯。因?yàn)槲覀兦蠼獾氖亲钚≈低诓兀@里的 $g_i(\omega) \leq 0$ ，我們可以將 $\alpha_i$ 調(diào)整成很大的正值厢漩，來使最后的函數(shù)結(jié)果是負(fù)無窮。因此我們需要排除這種情況岩臣，即需要定義下面的函數(shù)：

$\theta_P(\omega)=max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta)$

以上公式溜嗜，假設(shè) $g_i(\omega) \geq 0$ 或者 $h_i(\omega) \neq 0$ 宵膨，那么可以調(diào)整參數(shù) $\alpha_i$ 和 $\beta_i$ 使得 $\theta_P(\omega)$ 的最大值為正無窮。

但是當(dāng) $g_i(\omega)$ 和 $h_i(\omega)$ 滿足約束條件 $g_i(\omega)\leq 0$ 和 $h_i(\omega)=0$ 時(shí)炸宵， $\theta_p(\omega)$ 的最大值為 $f(\omega)$ 辟躏。所以上面式子可知，當(dāng) $g_i(\omega) \geq 0,h_i(\omega) \neq 0$ 時(shí) $\theta_P(\omega)=\infty$ 土全，當(dāng) $g_i(\omega)\leq 0,h_i(\omega)=0$ 時(shí) $\theta_P(\omega)=f(\omega)$ ：

$\theta_P(\omega)= \begin{cases} f(\omega), & g_i(\omega)\leq 0,h_i(\omega)=0 \\ \infty, & g_i(\omega) \geq 0,h_i(\omega) \neq 0 \end{cases}$

這樣原來要求的 $min f(\omega)$ 可以轉(zhuǎn)換成求 $min \theta_P(\omega)$ 捎琐，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Ctheta_P(%5Comega)" alt="\theta_P(\omega)" mathimg="1">的最小值為 $f(\omega)$ ， $f(\omega)$ 越小則 $\theta_P(\omega)$ 越小裹匙，即求 $min f(\omega)$ 等于求 $min \theta_P(\omega)$ ：

$min_{\omega} \theta_P(\omega)=min_{\omega} max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta)$

拉格朗日對(duì)偶步驟

下面使用 $p^*$ 來表示 $min_{\omega} \theta_P(\omega)$ 瑞凑，如果直接求解，首先面對(duì)的是兩個(gè)參數(shù) $\alpha,\beta$ 概页，這個(gè)過程不容易求解籽御。因此這里引入拉格朗日對(duì)偶，即函數(shù) $\theta_P$ 的對(duì)偶函數(shù) $\theta_D$ 惰匙，它是一個(gè)以 $\alpha$ 和 $\beta$ 為變量的函數(shù)：

$\theta_D(\alpha,\beta)=min_{\omega} \Gamma(\omega,\alpha,\beta)$

由求解 $\theta_P(\omega)$ 的最小值 $min_{\omega} \theta_P(\omega)$ 的推理步驟可知技掏， $\theta_D(\alpha,\beta)$ 求解最大值的函數(shù)為

$max_{(\alpha,\beta:\alpha_i \geq 0)} \theta_D(\alpha,\beta)=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta)$

這個(gè)問題是原問題的對(duì)偶問題，相對(duì)于原問題只是更換了 $max$ 和 $min$ 的順序项鬼，而一般更換 $max$ 和 $min$ 順序總有如下式子成立：

$max (min(x)) \leq min (max(x))$

所以有：

$d^* \leq p^*$

$d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} (min_{\omega} \Gamma(\omega,\alpha,\beta)) \leq min_{\omega} (max_{(\alpha,\beta:\alpha_i \geq 0)} \Gamma(\omega,\alpha,\beta))=p^*$

下面會(huì)解釋在什么條件下兩者會(huì)相等 $d^*=p^*$ 哑梳。

假設(shè) $f(\omega)$ 和 $g_i(\omega)$ 都是凸函數(shù)， $h_i(\omega)=\alpha_i^T\omega+b_i$ 绘盟，并且存在 $\omega$ 使得所有的 $i$ 都有 $g_i(\omega)<0$ 涧衙。在這種假設(shè)下，一定存在 $\omega^*,\alpha^*,\beta^*$ 使得 $\omega^*$ 是原問題 $p^*$ 的解奥此， $\alpha^*,\beta^*$ 是對(duì)偶問題 $d^*$ 的解弧哎，以及 $d^*=p^*=\Gamma(\omega^*,\alpha^*,\beta^*)$ ，這時(shí) $\omega^*,\alpha^*,\beta^*$ 滿足kkt條件：

$\frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\omega_i}}=0,i=1,2,...,n$

$\frac{\partial_{\Gamma(\omega^*,\alpha^*,\beta^*)}}{\partial_{\beta_i}}=0,i=1,2,...,l$

$\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$

$g_i(\omega^*) \leq 0,i=1,2,...,k$

$\alpha^* \geq 0,i=1,2,...,k$

如果 $\omega^*,\alpha^*,\beta^*$ 滿足了kkt條件稚虎，那么他們就是原問題和對(duì)偶問題的解撤嫩。而 $\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$ 被稱作是kkt條件，這個(gè)條件隱含了如果 $\alpha^*>0$ 蠢终，那么 $g_i(\omega^*)=0$ 序攘。也就是說， $g_i(\omega^*)=0$ 時(shí)寻拂， $\omega$ 處于邊界上程奠，而當(dāng) $\alpha^*=0$ 時(shí)，其 $g_i(\omega^*) \leq 0$ 祭钉，即 $\omega$ 不在邊界上在可行域內(nèi)瞄沙。

最優(yōu)函數(shù)間隔器

重新回到 svm 的優(yōu)化問題，在上面我們需要優(yōu)化的問題是：

$min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2$

$y^{(i)}(\omega^Tx^{(i)}+b) \geq 1 ,i=1,2,...,m$

這里將約束條件改成：

$g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1 \leq 0 ,i=1,2,...,m$

而kkt條件可知，如果 $\alpha_i > 0$ 就一定意味著 $g_i(\omega,b)=0$ (因?yàn)? $\alpha_i^*g_i(\omega^*)=0,i=1,2,...,k$ )距境，也就是存在訓(xùn)練樣本 $(x_i,y_i)$ 使得函數(shù)間隔為1申尼，即 $g_i(\omega,b)=-y^{(i)}(\omega^Tx^{(i)}+b)+1=0$ 。它到底表示了什么可以用圖展示一下：

image

你有一些訓(xùn)練樣本和一個(gè)分隔超平面垫桂，根據(jù)上面的假設(shè) $\alpha_i > 0$ (換個(gè)說法是 $\alpha_i \neq 0$ )就一定會(huì)有函數(shù)間隔為1的樣本师幕，即上圖中虛線部分，這些里超平面最近的樣本诬滩。在這個(gè)用圖展示的例子中霹粥，所有離超平面較遠(yuǎn)樣本的函數(shù)間隔都大于1。

從上面圖形可以看出：通常情況下疼鸟，可以發(fā)現(xiàn)只有很少數(shù)量的訓(xùn)練樣本函數(shù)間隔等于1后控，在上面的圖中只有3個(gè)樣本的函數(shù)間隔等于1，只有少量的樣本到超平面的距離是最小距離愚臀，這些樣本我們稱之為支持向量忆蚀，支持向量機(jī)的支持向量就是這個(gè)意思

支持向量的數(shù)量一般都會(huì)很少，即大多數(shù)情況下拉格朗日算子 $\alpha_i =0$ 姑裂，如果 $\alpha_i = 0$ 馋袜，那么其對(duì)應(yīng)的樣本就可能不是支持向量( $g_i(\omega) \leq 0$ )。

回到上面的優(yōu)化問題舶斧，由于只有 $g_i(\omega)$ 欣鳖，所以上面的拉格朗日函數(shù)：

$\Gamma(\omega,\alpha,\beta)=f(\omega)+\sum_{i=1}^k\alpha_ig_i(\omega)+\sum_{i=1}^l\beta_ih_i(\omega)$

變成：

$\Gamma(\omega,\alpha)=f(\omega)+\sum_{i=1}^m\alpha_ig_i(\omega)$

$\implies$

$\Gamma(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1]$

注意到這里只有 $\alpha_i$ 沒有 $\beta_i$ 是因?yàn)樵瓎栴}中沒有等式約束，只有不等式約束茴厉。

下面按照對(duì)偶問題的求解步驟泽台，即需要定義下面的函數(shù)：：

$d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta)$

首先求解最小值 $min_{\omega} \Gamma(\omega,\alpha,\beta)$ ，對(duì)于固定的 $\alpha_i$ 矾缓， $\Gamma(\omega,\alpha,\beta)$ 的最小值只與 $\omega$ 和 $b$ 有關(guān)怀酷。所以分別對(duì) $\omega$ 和 $b$ 求偏導(dǎo)：

$\nabla_{\omega}\Gamma(\omega,b,\alpha)=\omega-\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}=0$

$\implies$

$\omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}$

上面得到 $\Gamma(\omega,\alpha,\beta)$ 最小值時(shí) $\omega$ 的取值。

對(duì) $b$ 求偏導(dǎo)得到：

$\frac{\partial_{\Gamma(\omega,b,\alpha)}}{\partial_{b_i}}=\sum^m_{i=1}\alpha_iy^{(i)}=0$

將上面求偏導(dǎo)得到的兩個(gè)式子嗜闻，即代入到如下拉格朗日的函數(shù)中：

$\begin{split} \Gamma(\omega,b,\alpha)&=\frac{1}{2}||\omega||^2-\sum_{i=1}^m\alpha_i[y^{(i)}(\omega^Tx^{(i)}+b)-1] \\ &=\frac{1}{2}\omega^T\omega-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}\omega^Tx^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\omega^T\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\omega^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}(\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1}\alpha_iy^{(i)}(x^{(i)})^T\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_iy^{(i)}(x^{(i)})^T\alpha_jy^{(j)}x^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}+\sum_{i=1}^m\alpha_i \\ &=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)} \end{split}$

最后得到：

$\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^m\alpha_iy^{(i)}$

$(x^{(i)})^Tx^{(j)}$ 即為向量內(nèi)積蜕依，簡化表達(dá)為 $<x^{(i)},x^{(j)}>$

由于前面知道，對(duì) $b$ 求偏導(dǎo)時(shí) $\sum_{i=1}^m\alpha_iy^{(i)}=0$ 時(shí)可以使 $b$ 取得最小值琉雳，所以最后一項(xiàng) $b\sum_{i=1}^m\alpha_iy^{(i)}$ 的值為0样眠，最小值 $min_{\omega} \Gamma(\omega,\alpha,\beta)$ 的式子轉(zhuǎn)化為：

$\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)},x^{(j)}>$

該式子只剩下 $\alpha$ 是未知變量，現(xiàn)在利用拉格朗日對(duì)偶函數(shù)求解未知函數(shù) $\alpha$

而對(duì)于原有拉格朗日對(duì)偶函數(shù)：

$d^*=max_{(\alpha,\beta:\alpha_i \geq 0)} min_{\omega} \Gamma(\omega,\alpha,\beta)$

所以原有對(duì)偶問題可以定義為：

$max_{\alpha}\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)},x^{(j)}>$

$\alpha_i \geq 0,i=1,2,...,m$

$\sum_{i=1}^m\alpha_iy^{(i)}=0$

綜上所述翠肘，只要求出 $\alpha$ 檐束，就可以根據(jù)公式：

$\omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}$

求得 $\omega$ ，一旦求出了 $\alpha$ 和 $\omega$ 束倍，就可以很容易的求出 $b$ 被丧，如下圖所示盟戏，已知 $\omega$ 可以確定超平面的方向，如下所示：

image

但是上圖只有一個(gè)超平面晚碾，實(shí)際上在沒確定參數(shù) $b$ 之前抓半，圖中可能存在很多個(gè)超平面：

image

只要知道是哪個(gè)超平面喂急，就能求解 $b$ 的值格嘁，所以一旦確定 $\alpha$ 和 $\omega$ ，就能很容易的求解出 $b$ 的值廊移。

將 $\alpha$ 和 $\omega$ 帶入原始優(yōu)化問題中求解 $b$ :

$b=\frac{max_{i:y^{(i)}=-1}\omega^Tx^{(i)}+min_{i:y^{(i)}=1}\omega^Tx^{(i)}}{2}$

對(duì)于這個(gè)公式的直觀理解是糕簿，找到分類效果最差的正樣本和分類效果最差最差的負(fù)樣本，即離超平面最近的正樣本和負(fù)樣本狡孔，即分類效果最差懂诗，即如下的兩條虛線：

image

虛線除以2就能得到正確的分類超平面。

而前面所有的出發(fā)點(diǎn)都是 $\omega^Tx+b$ 苗膝，根據(jù)求解得到 $\alpha_i$ 殃恒，如果將：

$\omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}$

帶入 $\omega^Tx+b$ 可以得到：

$\begin{split} \omega^Tx+b&=(\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)})^Tx+b \\ &=\sum^m_{i=1}\alpha_iy^{(i)}<x^{(i)} ,x>+b \end{split}$

也就是說，以前新來的樣本要分類辱揭，要首先根據(jù) $\omega$ 和 $b$ 做一次線性運(yùn)算來判斷是正樣本還是負(fù)樣本±胩疲現(xiàn)在有了 $\alpha_i$ ，就不需要先計(jì)算 $\omega$ 问窃，而是只需將信賴的樣本和訓(xùn)練數(shù)據(jù)里面的所有樣本做一次內(nèi)積和即可亥鬓。

且由kkt條件可知，只有 $\alpha_i>0$ 的時(shí)候域庇，也就是支持向量的時(shí)候才需要計(jì)算嵌戈， $\alpha_i=0$ 的時(shí)候都是0，所以就是新樣本只需要和所有的支持向量計(jì)算內(nèi)積即可听皿。

總結(jié)步驟

先確定間隔器熟呛，這里svm一般默認(rèn)是幾何間隔

由間隔器確定間隔函數(shù)

從間隔函數(shù)查看是否包含不等式約束形式

根據(jù)拉格朗日對(duì)偶步驟計(jì)算得到參數(shù)w、b

根據(jù)以上對(duì)偶問題的求解尉姨，需要在下一篇里面利用核函數(shù)解釋庵朝。

數(shù)據(jù)和代碼下載請(qǐng)關(guān)注公眾號(hào)【 機(jī)器學(xué)習(xí)和大數(shù)據(jù)挖掘 】，后臺(tái)回復(fù)【 機(jī)器學(xué)習(xí) 】即可獲取

最后編輯于：2020.02.06 12:56:09

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

人面猴
序言：七十年代末啊送，一起剝皮案震驚了整個(gè)濱河市偿短，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌馋没，老刑警劉巖昔逗，帶你破解...
沈念sama閱讀 211,423評(píng)論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異篷朵，居然都是意外死亡勾怒，警方通過查閱死者的電腦和手機(jī)婆排，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,147評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來笔链，“玉大人段只，你說我怎么就攤上這事〖ǎ” “怎么了赞枕？”我有些...
開封第一講書人閱讀 157,019評(píng)論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長坪创。經(jīng)常有香客問我炕婶，道長，這世上最難降的妖魔是什么莱预？我笑而不...
開封第一講書人閱讀 56,443評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任柠掂，我火速辦了婚禮，結(jié)果婚禮上依沮，老公的妹妹穿的比我還像新娘涯贞。我一直安慰自己，他們只是感情好危喉，可當(dāng)我...
茶點(diǎn)故事閱讀 65,535評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布宋渔。她就那樣靜靜地躺著，像睡著了一般姥饰。火紅的嫁衣襯著肌膚如雪傻谁。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,798評(píng)論 1贊 290
城市分裂傳說
那天列粪，我揣著相機(jī)與錄音审磁，去河邊找鬼。笑死岂座，一個(gè)胖子當(dāng)著我的面吹牛态蒂，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播费什，決...
沈念sama閱讀 38,941評(píng)論 3贊 407
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼钾恢，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了鸳址？” 一聲冷哼從身側(cè)響起瘩蚪，我...
開封第一講書人閱讀 37,704評(píng)論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎稿黍，沒想到半個(gè)月后疹瘦，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,152評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡巡球，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,494評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年言沐，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了邓嘹。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,629評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡险胰，死狀恐怖汹押，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情起便，我是刑警寧澤棚贾，帶...
沈念sama閱讀 34,295評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站缨睡，受9級(jí)特大地震影響鸟悴，放射性物質(zhì)發(fā)生泄漏陈辱。R本人自食惡果不足惜奖年，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,901評(píng)論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望沛贪。院中可真熱鬧陋守，春花似錦、人聲如沸利赋。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,742評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽媚送。三九已至中燥，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間塘偎，已是汗流浹背疗涉。一陣腳步聲響...
開封第一講書人閱讀 31,978評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留吟秩，地道東北人咱扣。一個(gè)月前我還...
沈念sama閱讀 46,333評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長得像涵防，于是被迫代替她去往敵國和親闹伪。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,499評(píng)論 2贊 348

【機(jī)器學(xué)習(xí)】算法原理詳細(xì)推導(dǎo)與實(shí)現(xiàn)(四):支持向量機(jī)(上)

【機(jī)器學(xué)習(xí)】算法原理詳細(xì)推導(dǎo)與實(shí)現(xiàn)(四):支持向量機(jī)(上)

函數(shù)間隔概念

間隔器

函數(shù)間隔

幾何間隔

最優(yōu)間隔分類器

拉格朗日對(duì)偶

含有等式約束形式的求解最值

含不等式約束形式的求解最值

拉格朗日對(duì)偶步驟

最優(yōu)函數(shù)間隔器

總結(jié)步驟

推薦閱讀更多精彩內(nèi)容