支持向量機(第三章)

第三章 SVM最優化問題

SVMs尋找最優超平面

感知器有幾個優點：它是一個簡單的模型，算法非常容易實現，有相關理論證明可以找出一個分類數據的超平面。然而，它有一個最大的問題是每次都不能找到相同的超平面。我們為什麼關心這個？因為並不是所有的超平面都是等價的。如果感知器得到的超平面非常接近一類接據點，你有權利相信它很難推廣來適應新的數據。

SVMs 沒有這個問題。事實上，相反要尋找惟一超平面，SVMs 嘗試去尋找這個超平面。我們稱它為最優超平面，我們將說它是惟一的能最好的分割數據。

我們怎樣比較兩個超平面？

因為我們不能憑感覺選擇最優超平面，我們需要有一個排序標準來比較兩個超平面哪一個更好。

在本章接下來的部分，我們將試著去了解怎樣比較兩個超平面。另外，我們將找到一個方法去計算出一個能告訴我哪個超平面能量好的分類數據的數值。我們將要看到這些方法是如何工作的，但是現在我們可以先看它們為什麼不能工作而正確的找出它們的侷限。讓我們試著從一個例子僅用超平面的方程式去比較兩個超平面。

使用超平面方程式

給出一個示例和一個超平面，我們希望知道這個示例與超平面的關係。

一個關鍵要素是我們已經知道如果x的值滿足這個直線方程，就說明它在這條直線上。同理對於一個超平面：對於數據點x和一個超平面定義於一個向量w和偏置b，如果x在超平面上，我們將得到。

但是如果點不在超平面上將發生什麼呢？

讓我們從一個實例來看發生了什麼。在圖22中，直線定義於和b=9。我們應用超平面方程式：

· 對於點A（1，3），代入向量a=（1，3）我們得到

· 對於點B（3，5），代入向量a=（3，5）我們得到

· 對於點C（5，7），代入向量a=（5，7）我們得到

圖22：通過方程式，A 返回的結果比B大

你們可以看到，當點不在超平面上時我們得到的結果值不等於0。事實上，如果點離超平面越遠，我們得到的結果值比靠近超平面的點返回的值大。

另一個需要注意的是方程式返回的結果的符號能告訴我們點相對於直線的位置。用這個直線方向我們能得到圖23所示的結果，我們得到：

· 點A（3,5）返回2.8

· 點B（5,7）返回0

· 點C（7,9）返回-2.8

圖23：通過方程式，C返回一個負值

如果方程式返回正值，這個點在直線的下方，當它返回一個負值時，這個點在直線的上方。注意在視覺上的上方或下方並不是必要的，比如圖24所示的直線，它將是左邊或右邊，但是在邏輯上是相同的。超平面方程返回的值的符號可以告訴我們兩點處於同一邊。事實上，這就是我們第二章定義的假設函數要做的事情。

圖24：直線可以不同的方式分割空間

我們現在開始有一個解決方法來比較兩個超平面。

給出一個訓練示例（x,y）和一個定義於向量w和偏置b的超平面，我們計算數值來知道這個點與超平面的的距離。

給出數據集，我們計算每一個訓練示例的，定義數字B為

如果我們要在兩個超平面中選擇一個時，我們要選擇一個最大值的B。

很簡單，意思是我們有k個超平面，我們將計算和選擇返回值為的超平面。

示例返回負值的問題

不幸的是，使用用超平面方程返回值有它的侷限性。在方式程返回負值時選最小值就不正確了（方程式返回負值的分類）。

記住，我們總是希望返回值的點靠近超平面。B在示例返回的都是正值時工作得很好。從=+5和

一個修正這個問題的考慮是取的絕對值。

給出一個數據集，我們遍歷示例計算

這個超平面能正確分類數據碼？

計算數字B讓我們可以選擇一個超平面。但是，僅僅只是用這個數值，我們可能選出一個錯誤的。考慮圖25所示：這是一個正確的分類，而且這個B是用後一個公式算出來的2。

圖25：正確分類數據的超平面

在圖26中，示例數據被錯誤分類，但是這個B的值也是2。這個問題在於我們用B選出來的平面我們不知道哪一個是對的。理論上，它們看起來都很好，但是事實上，我們希望選擇圖25中的超平面。

圖26：錯誤分類數據的超平面

碰到這種情況如何調整我們的公式？

很好，在我們的訓練數據（x,y）中有一個部分沒有使用：就是這個y!

如果我們用來乘以y，改變一下記與，讓我們稱這個新的數為f：

f的符號總是：

· 正值表示這個點被正確分類

· 負值表示這個點被錯誤分類

給出一個訓練集, 我們可以計算：

使用這個公式，當比較兩個超平面時，我們可以一直選擇F最大的哪個。增加的功能可以讓圖25和圖26這種情況下，我們也總能選出正確分類的超平面（因為F將是一個正值，負值將是另外的平面）。

在文獻裡，數字f有一個名字，它被稱為示例數據的函數間隔（functional margin）;它的數值可以用Python計算，如代碼表19所示。類似的，數字F就是數據集的函數間隔。

代碼表19

# Compute the functional margin of an example (x,y)

# with respect to a hyperplane defined by w and b.

def example_functional_margin(w, b, x, y):

result = y * (np.dot(w, x) + b)

return result

# Compute the functional margin of a hyperplane

# for examples X with labels y.

def functional_margin(w, b, X, y):

return np.min([example_functional_margin(w, b, x, y[i])

for i, x in enumerate(X)])

用這個公式，我們發現這個超平面的函數間隔在圖25中是+2，而在圖26中是-2。因為它的間隔要大，所以我們選擇第一個。

比率不變性

看起來這次我們找到了一個好的方法去比較兩個超平面。然而，函數間隔有一個重要的問題：沒有比率不變性。

給出一個向量和偏置

向量和

這個問題，我們可以看代碼表20，當我們計算的函數間隔時，我們給出的數據是的10倍。意思是對於任一超平面，只是等比例放大

代碼表20

x = np.array([1, 1])

y = 1

b_1 = 5

w_1 = np.array([2, 1])

w_2 = w_1 * 10

b_2 = b_1 * 10

print(example_functional_margin(w_1, b_1, x, y)) # 8

print(example_functional_margin(w_2, b_2, x, y)) # 80

解決這個問題，我們只要去做一個小的調整。我們將用單位向量來代替向量w。這樣，我們將用w的範式來除w。同樣我們將用w的範式來除b平維持比率不變性。

再看求函數間隔的公式：

我們修改後變為一個新的數 γ：

之前，給出一個數據集，我們可以計算：

γ的優勢在於它能給我們一個相同的數而不用在乎w的值的大小。數γ還有一個名稱——它被稱為學習示例的幾何間隔，M就是這個數據集的幾何間隔。一個Python實現如代碼表21。

代碼表21

# Compute the geometric margin of an example (x,y)

# with respect to a hyperplane defined by w and b.

norm = np.linalg.norm(w)

result = y * (np.dot(w/norm, x) + b/norm)

return result

# Compute the geometric margin of a hyperplane

# for examples X with labels y.

def geometric_margin(w, b, X, y):

return np.min([example_geometric_margin(w, b, x, y[i])

for i, x in enumerate(X)])

我們可以驗證幾何間隔可以達到預期。在代碼表22中，對於向量和等比放大的向量

代碼表22

x = np.array([1,1])

y = 1

b_1 = 5

w_1 = np.array([2,1])

w_2 = w_1*10

b_2 = b_1*10

print(example_geometric_margin(w_1, b_1, x, y)) # 3.577708764

被稱為幾何間隔是因為我們能通過幾何方式推出這個公式。它可以測量向量x和超平面之間的距離。

在圖27中，我們看到點是X在超平面上的正交投影。我們希望找到X和之間的距離

圖27：幾何間隔就是點X與超平面之間的距離d

向量k與向量w的方向相同，所以它們有相同的單位向量。我們知道k的範式是

而且，我們可以看到，所以我們可以消掉k和做一些代數計算，我們得到：

現在，點在超平面上，意味著

最終，像我們之前一樣，我們用y來乘來確保我們選擇的超平面可以正確的分類數據，而且它給出幾何間隔方程式如我們之前所見：

圖28：定義為w=(-0.4,-1)和b=8的超平面 圖29：定義為w=(-0.4,-1)和b=8.5的超平面

現在我們有定義好的幾何間隔，讓我們看它是如何來比較兩個超平面的。我們可以看到圖28中的超平面更接近藍色星示例比紅色三角示例與圖29相比較。結果，我們得出它的幾何間隔更小。代碼表28用代碼表21定義的函數來計算每一個超平面的幾何間隔。然後得出圖29的定義為w=(-0.4,-1)和b=8.5的超平面的幾何間隔較大（0.64>0.18）。所以我們選擇這個超平面。

代碼表23

# Compare two hyperplanes using the geometrical margin.

positive_x = [[2,7],[8,3],[7,5],[4,4],[4,6],[1,3],[2,5]]

negative_x = [[8,7],[4,10],[9,7],[7,10],[9,6],[4,8],[10,10]]

X = np.vstack((positive_x, negative_x))

y = np.hstack((np.ones(len(positive_x)), -1*np.ones(len(negative_x))))

w = np.array([-0.4, -1])

b = 8

# change the value of b

print(geometric_margin(w, b, X, y)) # 0.185695338177

print(geometric_margin(w, 8.5, X, y)) # 0.64993368362

我們看到計算不同超平面的幾何間隔，只要修改w和b的值就可以了。我們可以試著稍微增加一下它們的值看看是否能得到大些的幾何間隔，但是它是隨機的，並且會花大量的時間。我們的目標是在所有可能的超平面中找到一個最優超平面來分類數據，而且這樣的超平面有無限多個。

提示：尋找最優以超平面等同於找到最大的幾何間隔的

我們怎樣才能找到產生最大幾何間隔的w的值呢？幸運的是，數學家們設計了工具來解決這種問題。要尋找w和b，我們需要解決什麼叫最優化問題。在瞭解最優化問題如何應用於SVMs前，讓我們先快速瀏覽什麼是最優化問題。

什麼是最優化問題？

無約束最優化問題

最優化問題的目標是去找到使函數最小化或最大化的變量x（意思是，尋找x的值使函數返回最小或最大值）。實例，我們希望尋找函數的最小值問題可以寫成：

或，可這樣表示：

在這個例子中，我們要自由的搜索所有可能的x的值。我們說這個問題是無約束的。我們可以看圖30，在x=0處得到函數的量小值為0。

圖30：無約束時，最小值為0

圖31：因為約束條件為x-2=0，最小值為4

有約束最優化問題

唯一等式約束

有時我們對方程本身的最小值不感興趣，但是經常遇到帶有約束條件的最小值。在某些例子中，我們增加一個約束條件通過 subject to 來表示這個問題，也常常簡寫成s.t。例如，假如我們希望知道f的最小值但是限定x為一特定值，我們可以寫成：

這個例子表示在圖31中。通常，約束條件被寫成右邊為0的等式像這個問題可以寫成：

用這個記法，我們清楚的看到約束是一次方程而目標函數f是一個二次方程。因此我們稱這個問題為二次最優化問題或是一個二次過程問題。

可行集

滿足這個問題的約束條件的變量集合被稱為可行集（或可行區域）。當解這個最優化問題時，解必須滿足可行集。在圖31中，可行集約束僅有一個變量，所以這個問題不復雜。然而，當我們要處理的函數有多個變量，像

例如：

在這個問題中，可行集是所有成對的點（x,y），像這樣。

多等式約束和向量表示

我們可以任意增加多個約束條件，在下面的例子是方程有三個約束條件的最優化問題：

當我們有多個變量時，我們可以用向量表示去提高可讀性。用向量讓方程變為

我們增加約束，頭腦中要想著去減少可行集。如果一個解被求出，所有的條件都必須滿足。

例如，我們看下面的問題：

我們可以想象x=2和x=8是解，但這不符合事實。當x=2，約束條件x-8=0就不適合；並且法x=8，約束條件x-2=0就不適合。這個問題是無解的。

提示：如果在部題中加入過多的約束條件，它可能會變為無解的。

如果你增加約束條件改變一個最優化問題，將使優化結果變糟，或者，最好，你不要改變它（Gershiwin,2010）。

不等式約束

我們可以用不等式做為約束條件：

而且我們可以組合等式約束和不等式約束：

我們怎樣解一個最優化問題？

存在很多方法來解每一種最優化問題。然而，介紹它們超過了這本書的範圍。感興趣的讀者可以去看《優化模型和應用》Optimization Models and Application (El Ghaoui, 2015) 和 《凸函數優化》Convex Optimization (Boyd & Vandenberghe, 2004)，這兩本好書即介紹了我們的主題又在網上可以免費閱讀（查閱參照資料詳細）。我們將焦點放回SVMs和掌握一個最優化問題使我們可以找到最優超平面。怎樣去解SVMs最優化問題將在下一章詳細介紹。

SVMs最優化問題

給出一個線性可分的訓練集和一個由向量w和偏移量b定義的超平面，調用超平面的幾何間隔M定義為：

這裡是調用訓練樣例

這個最優化的分類超平面就是用普通向量w和偏移量b定義的幾何間隔最大的超平面。

找到w和b，我們需要解下面的最優化問題，約束條件為樣例的間隔需要大於或等於M：

函數間隔和幾何間隔的關係：

所以我們可以重寫這個問題：

我們現在可以簡化約束條件去掉不等式兩邊的範式：

之前講過我們試著去最大化幾何間隔時等比改變W和b時不影響結果。我們可以選擇等比變化的任意w和b，幾何間隔不會變化。作為一個結果，我們決定等比改變W和b讓F=1。它不會影響這個最優化問題。

問題就成了：

因為，所以問題等同於：

又因為我們決定讓F=1，這就等價於：

這個求最大值問題就等價於下面的求最小值問題：

提示：你也可以從（https://www.svm-tutorial.com/2015/06/svm-understanding-math-part-3/）閱讀最優化問題的替代推導，在那裡我用函數間隔代替幾何間隔。

下面的式子讓這個最小化問題給出相同的結果。

分式 的增加是為了後來的方便，當我們用QP解法來解這個問題時範式的平方的優勢在於去掉了求平方根。

最終，這個最優化問題在大部分的文獻中寫成：

為什麼我們要費這麼大的勁去重寫這個問題？因為原始的最優化問題很難解，作為替代，我們現在有凸二次函數最優化問題，雖然它平淡無奇，但是非常容易解。

小結

首先，我們假定一些超平面要比其他的好：他它們要對未知的數據表現更好。在所有的超平面中，我們決定稱其中最好的超平面為最優超平面。為了找到最優超平面，我們找到一個比較兩個超平面的方法，而且最終因為一個數字可以讓我們做到。我們意識到這個數字的幾何意義且稱它為幾何間隔。

我們開始於最優超平面就是有最大幾何間隔的超平面且我們可以用間隔的最大值去找到它。為了使事情簡單化，我們注意到我們可以最小化w的範式，這個向量可以確定這個超平面，而且我們將確定w所確定的最優超平面（如果你回憶之前講過的，會知道w是用在在計算幾何向量的方程式中的）。

閱讀更多 西局書局 的文章

關鍵字: Python 鏡音雙子 技術