在接下來(lái)的兩篇文章里，我們會(huì)著重介紹支持向量機(jī)(Support Vector Machine)算法，以下簡(jiǎn)稱為SVM。SVM可以稱得上是監(jiān)督學(xué)習(xí)里最優(yōu)秀的算法了，在諸如文本分類，圖像識(shí)別，生物序列分析等領(lǐng)域有很多的應(yīng)用。

本篇文章首先介紹間隔(margin)的概念，然后給出最優(yōu)間隔分類器(optimal margin classifier)的定義，同時(shí)將該問(wèn)題轉(zhuǎn)化為一個(gè)凸優(yōu)化(convex optimization)問(wèn)題，隨后補(bǔ)充介紹拉格朗日對(duì)偶性(Lagrange duality)的知識(shí)，并由此推導(dǎo)出最優(yōu)間隔分類器的對(duì)偶問(wèn)題。

符號(hào)表示

為了使SVM的描述更簡(jiǎn)單，我們需要對(duì)之前的符號(hào)表示做一些修改。對(duì)于一個(gè)二元線性分類器，特征向量是x，輸出分類是y。之前y的取值是0和1，現(xiàn)在我們把取值修改為-1和1。之前假設(shè)函數(shù)h(x)是以θ作為參數(shù)，即：

現(xiàn)在我們使用w和b作為參數(shù)，即：

其中，如果z >= 0，那么g(z) = 1，否則g(z) = -1。用w和b表示可以顯式地讓我們把截距(intercept)b從其他參數(shù)中分離出來(lái)。對(duì)比兩種h(x)的定義，b相當(dāng)于原來(lái)的θ₀，w相當(dāng)于剩余的參數(shù)[θ₁, θ₂, ..., θ_n]^T。

注意，由于g(z)的定義變了，現(xiàn)在我們的分類器可以直接輸出1或者-1，而不是像邏輯回歸那樣先求出y = 1的概率，再根據(jù)概率預(yù)測(cè)輸出。

函數(shù)間隔和幾何間隔

下圖是一個(gè)線性分類器的圖示，圖中顯示了訓(xùn)練集的兩個(gè)分類數(shù)據(jù)(分別用圈和叉表示)，以及一個(gè)決策邊界(decision boundary)將兩類數(shù)據(jù)分割開。圖中的直線是w^Tx + b = 0，也被稱為超平面(hyperplane)。

圖中有三個(gè)點(diǎn)A、B和C，其中A離超平面最遠(yuǎn)，C離超平面最近，因而我們認(rèn)為A比C有更大的可能性屬于叉的分類。那么，我們應(yīng)該確定這個(gè)超平面呢？從直覺(jué)上看，這個(gè)超平面應(yīng)該使每個(gè)點(diǎn)離超平面的間隔都盡可能大。

為了確定這個(gè)超平面，我們需要正式給出間隔(margin)的定義。對(duì)于訓(xùn)練數(shù)據(jù)(x⁽ⁱ⁾, y⁽ⁱ⁾)，我們定義它與超平面(w, b)的函數(shù)間隔(functional margin)為：

如果y⁽ⁱ⁾ = 1，那么w^Tx + b必須是正數(shù)，并且w^Tx + b越大，函數(shù)間隔越大；相反地，如果y⁽ⁱ⁾ = -1，那么w^Tx + b必須是負(fù)數(shù)，并且w^Tx + b越小，函數(shù)間隔越大。因而函數(shù)間隔越大，分類預(yù)測(cè)的可信度越高。

有了單個(gè)訓(xùn)練數(shù)據(jù)的函數(shù)間隔的定義，我們可以定義整個(gè)訓(xùn)練數(shù)據(jù)集的函數(shù)間隔是所有訓(xùn)練數(shù)據(jù)的函數(shù)間隔的最小值，即：

函數(shù)間隔雖然可以表示分類預(yù)測(cè)的可信度，但它有一個(gè)缺點(diǎn)：如果我們成比例地增大w和b(比如把w和b替換成2w和2b)，那么函數(shù)間隔的值也會(huì)成比例地增大，然而超平面本身并沒(méi)有改變，因此這樣是無(wú)意義的。直覺(jué)上看，我們需要對(duì)參數(shù)作一些約束，比如限制||w|| = 1，而這就引出了幾何間隔(geometric margin)的定義。

幾何間隔實(shí)際上就是數(shù)據(jù)點(diǎn)到超平面的垂直距離，比如上圖中點(diǎn)A的幾何間隔就是A到超平面的距離AB，根據(jù)平面幾何的知識(shí)可以求出數(shù)據(jù)點(diǎn)(x⁽ⁱ⁾, y⁽ⁱ⁾)到超平面(w, b)的距離為：

上式就是幾何間隔的定義?？梢钥吹剑绻鹼|w|| = 1，那么幾何間隔就等于函數(shù)間隔。

另外如果我們?nèi)我饪s放w和b，那么幾何間隔并不會(huì)隨之改變。

同樣地，整個(gè)訓(xùn)練數(shù)據(jù)集的幾何間隔是所有訓(xùn)練數(shù)據(jù)的幾何間隔的最小值，即：

一般地，函數(shù)間隔和幾何間隔有如下關(guān)系：

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

上面我們討論到，尋找最優(yōu)超平面的條件應(yīng)該使每個(gè)點(diǎn)離超平面的間隔都盡可能大，因而最優(yōu)超平面也被稱為最優(yōu)間隔分類器(optimal margin classifier)。并且由于“任意縮放w和b，幾何間隔并不會(huì)隨之改變”，上述討論中的間隔應(yīng)該使用幾何間隔，所以最優(yōu)間隔分類器問(wèn)題可以定義為：

這個(gè)優(yōu)化問(wèn)題解決起來(lái)比較棘手，因?yàn)槟繕?biāo)函數(shù)是非凸函數(shù)，我們沒(méi)有辦法用現(xiàn)成的軟件可以解決這個(gè)問(wèn)題。再次考慮“任意縮放w和b，幾何間隔并不會(huì)隨之改變”這個(gè)結(jié)論，我們可以對(duì)該問(wèn)題增加一個(gè)約束：函數(shù)間隔等于1，并且最大化1 / ||w||等價(jià)于最小化||w||² ，那么問(wèn)題被轉(zhuǎn)化為：

這樣我們就把原始問(wèn)題轉(zhuǎn)化成了一個(gè)凸優(yōu)化問(wèn)題，而這個(gè)問(wèn)題可以用現(xiàn)成的二次規(guī)劃(quadratic programming)軟件來(lái)求解。

拉格朗日對(duì)偶性

這一部分我們介紹拉格朗日對(duì)偶性(Lagrange duality)，其核心思想是通過(guò)拉格朗日對(duì)偶性可以將原始問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題，而對(duì)偶問(wèn)題通常比較容易求解。

考慮如下優(yōu)化問(wèn)題：

即最小化函數(shù)f(w)，并且滿足l個(gè)等式約束(equality constraint)條件h_i(w) = 0。定義拉格朗日算子(Lagrangian)：

即等于原始目標(biāo)函數(shù)加上約束函數(shù)的線性組合，其中β_i是拉格朗日乘數(shù)(Lagrange multipliers)。分別求L關(guān)于w和β的偏導(dǎo)數(shù)即可求出原始問(wèn)題的解：

上述的優(yōu)化問(wèn)題只包含等式約束，而更廣義的優(yōu)化問(wèn)題還包含不等式約束(equality constraint)。下面我們定義這個(gè)廣義優(yōu)化問(wèn)題，也稱為原始優(yōu)化問(wèn)題(primal optimization problem)：

即最小化函數(shù)f(w)，并且滿足l個(gè)等式約束條件h_i(w) = 0和k個(gè)不等式約束條件g_i(w) <= 0。定義廣義拉格朗日算子(generalized Lagrangian)：

其中α_i和β_i是拉格朗日乘數(shù)。定義：

下標(biāo)p表示原始(primal)問(wèn)題，可以證明：

因此當(dāng)w滿足原始約束條件時(shí)，原問(wèn)題等價(jià)為：

為了后面表述方便，定義p^*是原始問(wèn)題的最優(yōu)解：

我們?cè)倏紤]另一個(gè)稍微不同的問(wèn)題，定義：

下標(biāo)D表示對(duì)偶(dual)問(wèn)題，注意在原始問(wèn)題中是關(guān)于參數(shù)α和β求最優(yōu)解，而對(duì)偶問(wèn)題是關(guān)于參數(shù)w求最優(yōu)解。定義對(duì)偶優(yōu)化問(wèn)題(dual optimization problem)：

和原始優(yōu)化問(wèn)題相比，對(duì)偶優(yōu)化問(wèn)題把max和min的順序交換了一下。同樣為了表述方便，定義d^*是對(duì)偶問(wèn)題的最優(yōu)解：

原始問(wèn)題與對(duì)偶問(wèn)題的關(guān)系如下：

事實(shí)上一個(gè)函數(shù)的max min值總是小于等于它的min max值，這里我們不作證明。而在某些情況下，我們有：

這種情況下求解原始問(wèn)題等價(jià)于求解對(duì)偶問(wèn)題。下面我們不加證明地給出使得p^* = d^*成立的條件。

假設(shè)f和g_i是凸函數(shù)，h_i是仿射(affine)函數(shù)(即存在a_i和b_i使得h_i(w) = a_i^Tw + b_i)，并且g_i是嚴(yán)格可執(zhí)行的(strictly feasible)(即存在w使得對(duì)于所有g(shù)_i(w)<0都成立)。在上述條件下，存在w^*，α^*，β^*，其中w^*是原始問(wèn)題的解，α^*，β^*是對(duì)偶問(wèn)題的解，并且滿足：

此外，w^*，α^*，β^*同時(shí)也滿足如下條件：

這些條件被稱為KKT條件(Karush-Kuhn-Tucker (KKT) conditions)。相反地，如果w^*，α^*，β^*滿足KKT條件，那么它們能成為原始問(wèn)題和對(duì)偶問(wèn)題的解。

KKT條件中等式(5)也被稱為KKT對(duì)偶互補(bǔ)條件(KKT dual complementarity condition)。這個(gè)條件表明如果α_i^* > 0，那么g_i(w^*) = 0。

最優(yōu)間隔分類器的推導(dǎo)

我們?cè)俅位氐阶顑?yōu)間隔分類器這個(gè)問(wèn)題：

把約束條件寫成如下形式：

這里我們只有一個(gè)不等式約束條件。根據(jù)KKT對(duì)偶互補(bǔ)條件，當(dāng)α_i > 0時(shí)，有g(shù)_i(w^*) = 0，即函數(shù)間隔等于1?？紤]下圖實(shí)例，其中實(shí)線表示這個(gè)訓(xùn)練集的最優(yōu)間隔超平面。

訓(xùn)練集上擁有最小間隔的點(diǎn)也是最接近超平面的點(diǎn)，這樣的點(diǎn)在上圖虛線處總共有三個(gè)。因此這三個(gè)點(diǎn)對(duì)應(yīng)的α_i是非零的，而這三個(gè)點(diǎn)被稱為該問(wèn)題的支持向量(support vectors)。事實(shí)上，支持向量的數(shù)量在整個(gè)訓(xùn)練集的占比非常小。

接下來(lái)我們對(duì)原問(wèn)題構(gòu)造拉格朗日算子：

注意，由于我們只有一個(gè)約束條件，所以這里只有α_i一個(gè)乘數(shù)。

接著我們開始求解對(duì)偶問(wèn)題，通過(guò)求L關(guān)于w的偏導(dǎo)數(shù)，可得：

通過(guò)求L關(guān)于b的偏導(dǎo)數(shù)，可得：

將等式(9)代回到等式(8)中并利用等式(10)的結(jié)論，可以得到：

因此對(duì)偶問(wèn)題可以表述為：

可以證明該優(yōu)化問(wèn)題是滿足KKT條件的，所以求解對(duì)偶問(wèn)題等價(jià)于求解原始問(wèn)題。通過(guò)求解該最大化問(wèn)題可以得到α^*，然后將其代入等式(9)可得w^*，最后再代入回原始問(wèn)題可得到b^*，即：

求解完模型各參數(shù)后，對(duì)于一個(gè)新特征x，我們需要計(jì)算w^Tx + b的值，如果值大于0，那么可以預(yù)測(cè)y = 1。根據(jù)等式(9)可得：

從上式可以看出，當(dāng)α_i確定后，我們只需要逐個(gè)計(jì)算x和每個(gè)訓(xùn)練集的內(nèi)積(inner product)。另外當(dāng)訓(xùn)練集的點(diǎn)是支持向量時(shí)才有α_i不等于0，并且支持向量只占訓(xùn)練集很少一部分，所以式子里的大多數(shù)項(xiàng)都是0，我們只需要計(jì)算x和支持向量的內(nèi)積就可以了。

通過(guò)將問(wèn)題表示成特征向量的內(nèi)積形式，其實(shí)是為了引出核函數(shù)的概念，這個(gè)概念可以啟發(fā)我們?cè)诟呔S空間下更高效應(yīng)用SVM的算法，而這是我們下一章的內(nèi)容。

總結(jié)

• 支持向量機(jī)(SVM)可以稱得上是監(jiān)督學(xué)習(xí)里最優(yōu)秀的算法了，在諸如文本分類，圖像識(shí)別，生物序列分析等領(lǐng)域有很多的應(yīng)用
• 間隔描述的是點(diǎn)到超平面的距離，尋找一個(gè)超平面使得每個(gè)點(diǎn)的間隔最大，這個(gè)問(wèn)題被稱為最優(yōu)間隔分類器
• 最優(yōu)間隔分類器可以轉(zhuǎn)化為凸優(yōu)化問(wèn)題，而這個(gè)問(wèn)題可以用現(xiàn)成的二次規(guī)劃軟件來(lái)求解
• 當(dāng)滿足一定條件下，原始問(wèn)題和對(duì)偶問(wèn)題是等價(jià)的，通過(guò)求解最優(yōu)間隔分類器的對(duì)偶問(wèn)題，我們可以推導(dǎo)出SVM最優(yōu)化公式

參考資料

• 斯坦福大學(xué)機(jī)器學(xué)習(xí)課CS229講義 pdf
• 網(wǎng)易公開課：機(jī)器學(xué)習(xí)課程 雙語(yǔ)字幕視頻