從負(fù)一開始推導(dǎo)SVM

0 解析幾何知識(shí), 點(diǎn)到平面的距離

image.png

如圖, 假設(shè)一個(gè)平面 $N: Ax+By+Cz+D = 0$ , 平面外一點(diǎn) $P(x_P, y_P, z_P)$ , $P$ 在平面上的投影為 $P'$ , 求點(diǎn) $P$ 到平面的距離即求 $\overline{PP'}$

我們可以知道平面 $N$ 的法向量為 $\vec N = (A, B, C)$ , 則這個(gè)法向量對(duì)應(yīng)的單位向量

$\vec n = \frac{\vec N}{|\vec N|} = \frac{\vec N}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.1)$

假設(shè)平面上任意一點(diǎn) $Q(x_Q, y_Q, z_Q)$ , 則 $Q$ 滿足

$Ax_Q + Bx_Q + Cx_Q + D = 0 \ \ \ \ \ \ (0.2)$

點(diǎn) $P$ 到點(diǎn) $Q$ 構(gòu)成的向量 $\vec{PQ} = (x_P - x_Q, y_P- y_Q, z_P-z_Q)$

所以 $\overline{PP'}$ 即為 $\vec{PQ}$ 在法向量 $\vec N$ 方向上的投影, 即與單位法向量 $\vec n$ 的點(diǎn)乘的結(jié)果.(這里取了個(gè)絕對(duì)值, 因?yàn)榫嚯x只能為正, 避免了向量方向問題的干擾)

$\overline{PP'} = |\vec{PQ} \cdot \vec n|=|\frac{(x_P - x_Q, y_P- y_Q, z_P-z_Q) \cdot \vec N}{\sqrt{A^2+B^2+C^2}}|$

$\overline{PP'} =\frac{|(x_P - x_Q, y_P- y_Q, z_P-z_Q) \cdot (A,B,C)|}{\sqrt{A^2+B^2+C^2}}$

$\overline{PP'} =\frac{|A(x_P - x_Q)+B( y_P- y_Q)+C( z_P-z_Q)|}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.3)$

其中與 $Q$ 點(diǎn)相關(guān)的變量 $x_Q, y_Q, z_Q$ 都可以用式 $(0.2)$ 替換

所以合并式 $(0.2), (0.3)$ 可得:

$\overline{PP'} =\frac{|Ax_P +By_P+Cz_P +D|}{\sqrt{A^2+B^2+C^2}} \ \ \ \ \ \ (0.4)$

如果用矩陣來表示, 則我們?nèi)?/p>

$\omega = \begin{bmatrix}A \\B \\C \end{bmatrix}, x_P = \begin{bmatrix}x_P \\y_P \\z_P \end{bmatrix}, b = D$

則式(0.4)可以寫為

$\overline{PP'} =\frac{|\omega^Tx_P +b|}{||\omega||}$

$||\omega||$ 即為L2范式(L2 norm), 就是平方和之后開根號(hào)

1 SVM基本問題描述和解決思路

基本問題:

假設(shè)有兩個(gè)類別的數(shù)據(jù), $(x_i, y_i)$

其中 $y_i = \begin{cases} +1 \\-1 \end{cases}$

我們?cè)噲D找到一個(gè)分隔平面(超平面) $\omega^Tx+b = 0$ (這里就是 $Ax+By+Cz+D = 0$ 的一個(gè)變體)

使得

離分隔平面 $\omega$ 最近的點(diǎn) 到分隔平面 $\omega$ 的距離最大
所有點(diǎn)都能被正確分類

目標(biāo)1: 距離最大

根據(jù)之前的預(yù)備知識(shí), 我們知道任意一點(diǎn) $P$ 到平面的距離為(李航的書說是"幾何距離")

$r = \frac{|\omega^Tx_P+b|}{||\omega||}$

我們要求分隔平面兩邊的點(diǎn)都滿足條件2: 距離分隔平面的距離最大

所以我們的求解目標(biāo)是

$\max \min \frac{2}{||\omega||}|\omega^Tx_P+b|$

目標(biāo)2: 正確分類

同時(shí)我們希望能滿足條件1, 即所有點(diǎn)能被正確分類

$y_i(\omega^T x+b) > 0$

因?yàn)?/p>

如果是正確分類的話, 所有類別為+1 的點(diǎn)都會(huì)在平面的上方, 類別為-1 的點(diǎn)都會(huì)在平面的下方.
在平面上方的點(diǎn)滿足 $(\omega^T x+b) > 0$ , 在平面下方的點(diǎn)滿足 $(\omega^T x+b) < 0$
所以如果能正確分類就有: $y_i(\omega^T x+b) > 0$

SVM的求解問題的數(shù)學(xué)表達(dá)

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| \\ s.t.\ y_i(\omega^T x+b) > 0 \ \ \ \ \ \ \ (1.1)$

翻譯一下:

找到距離平面最近的一個(gè)點(diǎn), 其距離: $\min_i \frac{1}{||\omega||}|\omega^Tx_i+b|$
把這個(gè)距離乘以2, 就是間隔了: $\min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$
把分隔平面挪動(dòng)翻轉(zhuǎn)一下, 看看是不是能擴(kuò)大這個(gè)間隔: $\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$

求解目標(biāo): $\omega, b$

2 如何簡化這個(gè)問題: 轉(zhuǎn)換為凸二次規(guī)劃問題

通過把原問題構(gòu)建成凸二次規(guī)劃問題來進(jìn)行求解, 因?yàn)橥苟我?guī)劃可解

凸二次規(guī)劃問題:

目標(biāo)函數(shù)是凸二次函數(shù): $\min_u \frac{1}{2}u^TQu + t^Tu$ (關(guān)于 $u$ 的二次函數(shù))
約束是線性約束: $s.t\ c_i^Tu \geq d_i, i = 1, 2,3,...,m$

現(xiàn)在我們的目標(biāo)就是, 把原問題湊成凸二次規(guī)劃問題

目標(biāo)函數(shù)的變換

原問題的目標(biāo)函數(shù)為:

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$

變換思路

因?yàn)榍蠼饽繕?biāo)是 $\omega, b$ , 所以 $\min_i$ 這一項(xiàng)(即變量 $i$ )要想辦法忽略掉
目標(biāo)函數(shù)為一個(gè)二次函數(shù), 原函數(shù)里面其實(shí)隱含了一個(gè)二次函數(shù): $\frac{1}{||\omega||} = \frac{1}{\sqrt{\omega^T\omega}}$
所以 $|\omega^Tx_i + b|$ 這一項(xiàng)有點(diǎn)沒有用, 我們需要想辦法忽略它

工具:

我們發(fā)現(xiàn)一個(gè)事實(shí), 如果把 $\omega, b$ 等比例放大/縮小, 式(1.1)描述的問題不變:
證明
假設(shè)一個(gè)系數(shù) $r>0$ , 使得 $\omega, b$ 放大為 $r\omega, rb$ ,
則式(1.1)變?yōu)?
$\max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| \\ s.t.\ y_i(r\omega^T x+rb) > 0$
其中目標(biāo)函數(shù) $\max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| = \max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b|$ (分母分子同乘一個(gè)r, 抵消了)
約束目標(biāo) $y_i(r\omega^T x+rb) > 0 \Leftrightarrow y_i(\omega^T x+b) > 0$ (不等式兩邊同除一個(gè)正數(shù), 不等式仍然成立)
這個(gè) $|\omega^Tx_i+b|$ 就是PQ和平面法向量 $\omega$ 點(diǎn)乘的結(jié)果蜓氨，這個(gè)結(jié)果要除以法向量的模長才是幾何間隔(我們的問題要求幾何間隔滿足一定條件)。所以如果我們只是變換法向量的長度的話械念，因?yàn)闊o論如何都會(huì)除以法向量長度拌阴，所以對(duì)于原問題并沒有任何影響(式(1.1)描述的問題不變)障癌。

變換過程

目標(biāo)函數(shù)的變換

我們假設(shè)所有的 $\omega,b$ 都乘上一個(gè)系數(shù)r拂盯，我們證明了乘上這個(gè)系數(shù)與否不影響問題的描述
于是我們總能找到一個(gè) $r^*$ 实束，使得 $\min_i |r^*\omega^Tx_i+r^*b|=1$ , 這樣的話原問題的目標(biāo)函數(shù)可以寫為 $\max_{\omega, b}\frac{2}{||r^*\omega||}$
我之前一直迷惑于這個(gè) $r^*$ 怎么處理的幽钢，后來想起來系數(shù)和問題的求解無關(guān)歉备，因?yàn)檫@是個(gè)凸二次函數(shù)嘛，想想拋物線的形狀匪燕，無論系數(shù)怎么改變拋物線最低點(diǎn)的值都會(huì)出現(xiàn)在固定的位置(系數(shù)和開口大小相關(guān))蕾羊，所以可以直接忽略系數(shù): 求解 $\max_{\omega, b}\frac{2}{||r^*\omega||}$ 等價(jià)于求解 $\max_{\omega, b}\frac{1}{||\omega||}$
$\max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b}||\omega|| \Leftrightarrow \min_{\omega, b} \omega^T\omega \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$
到這一步, 我們的目標(biāo)函數(shù)變化過程為: $\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| = \max_{w,b} \min_i \frac{2}{||r\omega||}|r\omega^Tx_i+rb| = \max_{w,b} \min_i \frac{2}{||r^*\omega||}|r^*\omega^Tx_i+r^*b|$
$= \max_{\omega, b}\frac{2}{||r^*\omega||} = \max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$

約束條件的變換

接下來看約束條件的變化, 原問題的約束條件為: $y_i(\omega^T x+b) > 0$ , 由于之前對(duì)于 $\omega, b$ 的變換引入了一個(gè)新的約束條件: $\min_i |r^*\omega^Tx_i+r^*b|=1$
$\min_i |r^*\omega^Tx_i+r^*b|=1$ , 我們可以視為 $\min_i |\omega'^Tx_i+b'|=1, (\omega' = r^*\omega, b' = r^*b)$ , 在這里, $r^*$ 的作用是對(duì) $\omega, b$ 施加限制, 所以我們可以換個(gè)思路, 直接對(duì) $\omega, b$ 施加限制: $\min_i |\omega^Tx_i+b|=1$ , 等價(jià)于 $|\omega^Tx_i+b| \geq 1$
所以新的約束條件為: $y_i(\omega^T x+b) > 0$ 且 $|\omega^Tx_i+b| \geq 1$ , 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=y_i(%5Comega%5ET%20x%2Bb)%20%3E%200" alt="y_i(\omega^T x+b) > 0" mathimg="1">的原因, 所以 $|\omega^Tx_i+b| = y_i(\omega^T x+b)$ (分類正確的條件下, 這兩個(gè)式子都能保證>0(分類正確意味著點(diǎn)不能再分隔平面上, 所以絕對(duì)值也不可能等于0)), 所以這兩個(gè)約束條件可以合并為一個(gè): $y_i(\omega^T x+b) \geq 1$

變換過程的公式推導(dǎo)

原問題為:

$\max_{w,b} \min_i \frac{2}{||\omega||}|\omega^Tx_i+b| \\ s.t.\ y_i(\omega^T x+b) > 0$

找到個(gè)系數(shù) $r^*$ 使得 $\min_i |r^*\omega^Tx_i+r^*b|=1$ ,(注意現(xiàn)在 $r^*$ 也是目標(biāo)函數(shù)之一了)

$\max_{w,b} \min_i \frac{2}{||r^*\omega||}|r^*\omega^Tx_i+r^*b|, \\ r* \\ \ \\s.t \ \min_i |r^*\omega^Tx_i+r^*b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

化簡目標(biāo)函數(shù), 湊二次函數(shù):

$\max_{\omega, b}\frac{2}{||r^*\omega||} = \max_{\omega, b}\frac{1}{||\omega||} \Leftrightarrow \min_{\omega, b} \frac{1}{2}\omega^T\omega$

于是現(xiàn)在的問題為:

$\min_{\omega, b} \frac{1}{2}\omega^T\omega, \\ r* \\ \ \\s.t \ \min_i |r^*\omega^Tx_i+r^*b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

轉(zhuǎn)換約束條件, 把關(guān)于 $r^*$ 的約束條件轉(zhuǎn)變成只與 $\omega, b$ 相關(guān)(目標(biāo)函數(shù)中的 $r^*$ 也沒了)

$\min_{\omega, b} \frac{1}{2}\omega^T\omega,\\s.t \ \min_i |\omega^Tx_i+b|=1\\ s.t.\ y_i(\omega^T x+b) > 0$

繼續(xù)轉(zhuǎn)換, 并合并兩個(gè)約束條件

$\min_{\omega, b} \frac{1}{2}\omega^T\omega\\ s.t.\ y_i(\omega^T x+b) \geq 1$

(這段變換其實(shí)是我整個(gè)SVM里面一開始最不能理解的地方, 我找到的教材都只是說了一句: 因?yàn)榭s放并不影響原問題, 所以我們就能得出 $\min_i |\omega^Tx_i+b|=1$ , 之類的解釋(包括<統(tǒng)計(jì)學(xué)習(xí)方法>也是類似的跳躍式證明). 我數(shù)學(xué)太渣真的無法自己就這樣接受這么跳躍的證明, 于是想了好久才想出了一個(gè)可以自己接受的證明方法. 不確保一定正確, 希望有人能指出錯(cuò)誤)

3 通過構(gòu)造一個(gè)新函數(shù), 合成目標(biāo)函數(shù)和約束: 拉格朗日函數(shù)

在利用二次凸優(yōu)化構(gòu)建了一個(gè)新的等價(jià)問題之后, 如何解? 現(xiàn)在的思路是把目標(biāo)函數(shù)和約束合成為一個(gè)式子, 通過求新式子的最值, 便是原問題的最值

這個(gè)方法稱為: 拉格朗日函數(shù)

拉格朗日函數(shù)求解的條件

如果一個(gè)帶約束優(yōu)化問題有諸如一下的形式:
$\min_u f(u) \\ s. t.\ g_i(u) \leq 0, \\ s.t.\ h_i(u) = 0 \\ i=1,2,3,....$
并且 $f(u)$ 連續(xù)可微

則可以將原問題轉(zhuǎn)換為一下新問題

$\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u) + \sum_{i=1}^m \alpha_ig_i(u) + \sum_{j=1}^n\beta_jh_j(u)\\ s.t \ \alpha_i \geq 0$

能進(jìn)行這樣轉(zhuǎn)換的原因

為了能證明新得到的拉格朗日函數(shù)是原問題的變形(即拉格朗日函數(shù)能變回原問題), 我們最好把 $\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u) + \sum_{i=1}^m \alpha_ig_i(u) + \sum_{j=1}^n\beta_jh_j(u)$ 和原問題中的約束條件 $g_i(u) \leq 0, h_i(u) = 0$ 放在一起看,

并且時(shí)刻記住: 因?yàn)榍蟮氖?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmin_u%20%5Cmax_%7B%5Calpha%2C%20%5Cbeta%7D%20L(u%2C%20%5Calpha%2C%20%5Cbeta%20)" alt="\min_u \max_{\alpha, \beta} L(u, \alpha, \beta )" mathimg="1">, 所以 $L(u, \alpha, \beta )$ 對(duì) $\alpha, \beta$ 有最大值, 對(duì) $u$ 有最小值

于是我們有如下的假設(shè):

如果 $g_i(u)$ 不滿足條件, 即 $g_i(u) > 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\alpha_ig_i(u)$ 這一項(xiàng), 最大值為 $+\infty$ , 導(dǎo)致 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = +\infty$ , 無解.
如果 $g_i(u)$ 滿足條件, 即 $g_i(u) \leq 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\alpha_ig_i(u)$ 這一項(xiàng), 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Calpha_i%20%5Cgeq%200" alt="\alpha_i \geq 0" mathimg="1">, 所以最大值為 $0$ (正數(shù) $\alpha_i$ 乘以負(fù)數(shù) $g_i(u)$ 結(jié)果仍為負(fù)數(shù)), 有可能有解
如果 $h_j(u)$ 不滿足條件, 即 $h_j(u) \neq 0$ : $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 中的 $\beta_jh_j(u)$ 這一項(xiàng), 因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cbeta_j" alt="\beta_j" mathimg="1">并沒有約束條件約束, 所以可以取任意值, 即 $\max_{\beta} \beta_jh_j(u) = +\infty$ , 導(dǎo)致 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = +\infty$ , 無解.
如果 $h_j(u)$ 滿足條件, 即 $h_j(u) = 0$ : 則 $\beta_jh_j(u) =0$ , $\max_{\alpha, \beta} L(u, \alpha, \beta )$ 可能有解

我們可以組合假設(shè)2和假設(shè)4, 即:

如果 $g_i(u)$ 滿足 $g_i(u) \leq 0$ , 且 $h_j(u)$ 滿足 $h_j(u) = 0$ , 則 $\max_{\alpha, \beta} L(u, \alpha, \beta ) = f(u)+0+0=f(u)$

所以此時(shí) $\min_u \max_{\alpha, \beta} L(u, \alpha, \beta ) =\min_u f(u)$ , 朗格朗日函數(shù)變換回原問題

把凸二次函數(shù)問題轉(zhuǎn)換成拉格朗日函數(shù)

$u$ 替換為 $\omega, b$ 所以有: $\min_u f(u) \Rightarrow \min_{\omega,b} f(\omega, b)$
$\min_{\omega,b} f(\omega, b)$ 替換為 $\min_{\omega, b} \frac{1}{2}\omega^T\omega$
$g_i(u) \leq 0$ 替換為 $1-y_i(\omega^T x+b) \leq 0$ : 把原約束的左邊移到了右邊而已
因?yàn)樵苟魏瘮?shù)問題中沒有類似 $h_j(u) = 0$ 的約束, 所以直接忽略 $\beta_jh_j(u)$ 這一項(xiàng)
原凸二次函數(shù)問題變?yōu)?
$\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha) = \min_{\omega, b} \max_{\alpha} \frac{1}{2}\omega^T\omega+\sum_{i=1}^m \alpha_i(1-y_i(\omega^T x+b) )$

4 通過對(duì)偶問題解拉格朗日函數(shù)

為什么要轉(zhuǎn)成對(duì)偶問題:

求解拉格朗日函數(shù)的極值的, 由于求極值的運(yùn)算是從內(nèi)向外的. 每次運(yùn)算需要先算 $\max_{\alpha}$ , 而這個(gè) $\alpha_i$ 作為新引入的變量, 只能通過計(jì)算所有值來找到最值.

而每次求得一個(gè)新的 $\alpha_i$ , 我們就要求一次 $\omega, b$ 的最值, 所以這樣非常耗時(shí)麻煩

但是如果能先求 $\omega, b$ , 每次找到一個(gè)新的 $\alpha_i$ 后就不用再計(jì)算了.

對(duì)偶問題的轉(zhuǎn)換

只要原問題滿足KKT+Slater條件, 我們便可以交換求最大值和最小值的順序:

$\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha) \overset{滿足KKT+Slater條件}{\Longrightarrow} \max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha)$

KKT條件

主問題可行: $g_i(u) \leq 0, h_i(u)=0$
對(duì)偶問題可行: $\alpha_i \geq 0$
互補(bǔ)松弛: $\alpha_ig_i(u) = 0$
(統(tǒng)計(jì)學(xué)習(xí)方法上面的條件)最優(yōu)解處對(duì) $\omega,b$ 偏導(dǎo)是0: $\nabla_{\omega, b} L(\omega^*, b^*, \alpha^*)=0$

Slater條件

當(dāng)主問題為凸優(yōu)化問題, 即 $f(u)$ 和 $g_i(u)$ 為凸函數(shù), $h_j(u)$ 為仿射函數(shù), 且可行域中至少有一點(diǎn)使不等式約束嚴(yán)格成立時(shí), 對(duì)偶問題等價(jià)于原問題.

對(duì)偶問題的證明

原問題為 $\min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha)$ , 對(duì)偶問題為 $\max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha)$ , <統(tǒng)計(jì)學(xué)習(xí)方法>寫的證明終于理解了, 這里我做一下注釋(也把符號(hào)統(tǒng)一為我這里使用的符號(hào)):

先假設(shè) $\theta_D(\omega,b) = \min_{\omega,b} L(\omega, b, \alpha)$ ,(D=dual problem對(duì)偶問題)

$\theta_P(\alpha) = \max_{\alpha} L(\omega, b, \alpha)$ , (P=prime problem原問題)

所以可知對(duì)任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) = \min_{\omega,b} L(\omega, b, \alpha) \leq L(\omega, b, \alpha) \leq \max_{\alpha} L(\omega, b, \alpha)= \theta_P(\alpha)$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmin_%7B%5Comega%2Cb%7D%20L(%5Comega%2C%20b%2C%20%5Calpha)" alt="\min_{\omega,b} L(\omega, b, \alpha)" mathimg="1"> 是對(duì) $L(\omega, b, \alpha)$ 求最小值, $\max_{\alpha} L(\omega, b, \alpha)$ 是對(duì) $L(\omega, b, \alpha)$ 求最大值, 所以最小值一定小于大于最大值

即對(duì)任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) \leq \theta_P(\alpha)$

這里的"任意"很重要, 下一步的證明的基礎(chǔ)就是這個(gè)"任意"

因?yàn)樵瓎栴}和對(duì)偶問題都有最優(yōu)解, 所以: $\max_{\alpha;\alpha \geq 0} \theta_D(\omega, b) \leq \min_{\omega, b} \theta_P(\alpha)$

因?yàn)槲覀冇? 對(duì)任意 $\omega, b, \alpha$ 都有 $\theta_D(\omega,b) \leq \theta_P(\alpha)$ , 所以就算取 $\theta_D(\omega,b)$ 的最大值和 $\theta_P(\alpha)$ 的最小值, 仍然要滿足 $\theta_D(\omega,b) \leq \theta_P(\alpha)$ , 所以 $\max_{\alpha;\alpha \geq 0} \theta_D(\omega, b) \leq \min_{\omega, b} \theta_P(\alpha)$ 成立

相當(dāng)于: $\max_{\alpha} \min_{\omega, b} L(\omega, b, \alpha) \leq \min_{\omega, b} \max_{\alpha} L(\omega, b, \alpha)$

求解SVM, 得到最簡單的計(jì)算式

因?yàn)槲覀冎皩⒃瓎栴}簡化又簡化了, 所以求解就變得很簡單.

只要對(duì) $\omega, b$ 分別求偏導(dǎo), 然后找到偏導(dǎo)等于0的時(shí)候, 這時(shí)候的極值就是最優(yōu)解

$\frac{\partial L }{\partial \omega} = 0 \Rightarrow \omega = \sum^{m}_{i=1}\alpha_iy_ix_i$

$\frac{\partial L }{\partial b} = 0 \Rightarrow b= \sum^{m}_{i=1}\alpha_iy_i = 0$

然后帶入拉格朗日函數(shù)的對(duì)偶形式里面:

$\max_{\alpha} \min_{\omega, b} \frac{1}{2}\omega^T\omega+\sum_{i=1}^m \alpha_i(1-y_i(\omega^T x+b) ), \\ s.t.\ a_i \geq 0$

就有

$\min_{\alpha} \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^{m} \alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{m}\alpha_i, \\ s.t.\ \sum_{i=1}^{m}a_iy_i = 0, \alpha_i \geq 0$

SVM的最樸素算法(線性可分支持向量機(jī)算法)

<統(tǒng)計(jì)學(xué)習(xí)方法>

P106 算法7.2

最后編輯于：2019.03.05 17:26:52

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市帽驯，隨后出現(xiàn)的幾起案子龟再，更是在濱河造成了極大的恐慌，老刑警劉巖界拦，帶你破解...
沈念sama閱讀 217,907評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件吸申，死亡現(xiàn)場離奇詭異，居然都是意外死亡享甸，警方通過查閱死者的電腦和手機(jī)截碴，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,987評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來蛉威，“玉大人日丹，你說我怎么就攤上這事◎窍樱” “怎么了哲虾？”我有些...
開封第一講書人閱讀 164,298評(píng)論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長择示。經(jīng)常有香客問我束凑，道長，這世上最難降的妖魔是什么栅盲？我笑而不...
開封第一講書人閱讀 58,586評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任汪诉，我火速辦了婚禮，結(jié)果婚禮上谈秫，老公的妹妹穿的比我還像新娘扒寄。我一直安慰自己，他們只是感情好拟烫，可當(dāng)我...
茶點(diǎn)故事閱讀 67,633評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布该编。她就那樣靜靜地躺著，像睡著了一般硕淑。火紅的嫁衣襯著肌膚如雪课竣。梳的紋絲不亂的頭發(fā)上嘉赎，一...
開封第一講書人閱讀 51,488評(píng)論 1贊 302
城市分裂傳說
那天，我揣著相機(jī)與錄音稠氮，去河邊找鬼曹阔。笑死半开，一個(gè)胖子當(dāng)著我的面吹牛隔披，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播寂拆，決...
沈念sama閱讀 40,275評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼奢米，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼！你這毒婦竟也來了纠永？” 一聲冷哼從身側(cè)響起鬓长，我...
開封第一講書人閱讀 39,176評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎尝江，沒想到半個(gè)月后涉波，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,619評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡炭序，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,819評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年啤覆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片惭聂。...
茶點(diǎn)故事閱讀 39,932評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡窗声，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出辜纲，到底是詐尸還是另有隱情笨觅，我是刑警寧澤，帶...
沈念sama閱讀 35,655評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布耕腾，位于F島的核電站见剩，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏扫俺。R本人自食惡果不足惜苍苞，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,265評(píng)論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一肩狂、第九天我趴在偏房一處隱蔽的房頂上張望局待。院中可真熱鬧，春花似錦龄砰、人聲如沸畸颅。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,871評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽没炒。三九已至涛癌，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背拳话。一陣腳步聲響...
開封第一講書人閱讀 32,994評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工先匪，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人弃衍。一個(gè)月前我還...
沈念sama閱讀 48,095評(píng)論 3贊 370
代替公主和親
正文我出身青樓呀非，卻偏偏與公主長得像，于是被迫代替她去往敵國和親镜盯。傳聞我的和親對(duì)象是個(gè)殘疾皇子岸裙，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,884評(píng)論 2贊 354

從負(fù)一開始推導(dǎo)SVM

0 解析幾何知識(shí), 點(diǎn)到平面的距離

1 SVM基本問題描述和解決思路

目標(biāo)1: 距離最大

目標(biāo)2: 正確分類

SVM的求解問題的數(shù)學(xué)表達(dá)

2 如何簡化這個(gè)問題: 轉(zhuǎn)換為凸二次規(guī)劃問題

目標(biāo)函數(shù)的變換

變換思路

工具:

變換過程

目標(biāo)函數(shù)的變換

約束條件的變換

變換過程的公式推導(dǎo)

3 通過構(gòu)造一個(gè)新函數(shù), 合成目標(biāo)函數(shù)和約束: 拉格朗日函數(shù)

拉格朗日函數(shù)求解的條件

能進(jìn)行這樣轉(zhuǎn)換的原因

把凸二次函數(shù)問題轉(zhuǎn)換成拉格朗日函數(shù)

4 通過對(duì)偶問題解拉格朗日函數(shù)

對(duì)偶問題的轉(zhuǎn)換

KKT條件

Slater條件

對(duì)偶問題的證明

求解SVM, 得到最簡單的計(jì)算式

SVM的最樸素算法(線性可分支持向量機(jī)算法)

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