劉應興的部落格

支持向量機  (support vector machine, SVM, 或譯：支搼向量機、支援向量機)，又名支持向量網路 (support-vector network)，是一種監督式學習網路，也是一種二分法分類技術。

此法先假設待分類物件（多維度空間的點）可以用兩個平行的超平面完全隔開：

Σ_i w_i x_i  - b ≧ 1  if y = 1;   Σ_i w_i x_i - b ≦ -1  if y = -1

其中 x_i 是物件在第 i 維度的測定值，y 為其分類值。在感知機或二元判別問題，我們可以如此處用 1/-1 標記兩分類，也可以 1/0 標記，關鍵是感知機網路輸出端的激活函數；在邏輯斯迴歸，則是用 1/0 標示；而判別分析則無所謂。不過，在做分類時，我們希望資料可完全分類，如二類別線型判別分析，希望找到線型函數 f(x) = w'x 及臨界值 c 把資料點依 f(x) > c 與 < c 分隔開，在感知機網路，我們也希望輸入的資料經網路運算後的輸出能是正確分類。只是統計上我們不認為可以做到完全正確的分類，因此在判別分析我們用一些準則計算或估計 f(x) 與 c，希望能儘量減低錯誤分類的機率。在感知機網路，其目的如同統計的判別分析，只是算叉可能不同。當用來學習或配適模型的資料不可能完全分類時，在統計上可能應用邏輯斯迴歸模型，在感知機網路也可能採用 logistic 函數做為激活函數。不過，如果用於配適模型的樣本資料，或說用於機器學習的學習或訓練資料是可以完全分類的，那將是一個「災難」，在統計上很難定出這樣的 logistic 迴歸模型 。以簡單邏輯斯迴歸模型資料為例，如果存在 c 使

x_j < c 則 y_j = 0;   x_j > c 則 y_j = 1

其中註標 j 代表個體，從 logistic 迴歸模型的概似方程式來看

Σ_j [(y_j - μ_j) x_j = 0,   μ_j = 1/(1+e^{-x_j' β})

可知並無實數（向量）β 可以滿足，因為其解是對應 x_j < c 的 y_j 得 μ_j = 0; 對應 x_j > c 的 y_j 得 μ_j =1。所以雖然統計上有比較判別分析和邏輯斯迴歸方法的研究，其實都著眼於兩群體之不可分割性，因為壟輯斯迴歸的基本假設 ㏑(p(x)/(1-p(x))) = β'x 其 p(x) 必須嚴格介於 0 與 1 之間，不能有 p(x) = 0 或 1 的惰形出現；而在分類目的的方法，我們卻希望 p(x) 非 0 即 1。

支援向量機如先前所說，是假設可以用兩平行超平面

 w'x - b = Σ_i w_i x_i - b = ±1

把資料點 x_j 完全分割成 y_j = 1 或 -1 的兩群。如果這事做得到，兩類資料點之間的距離至少是兩平面的距離 d = 2/√||w||，直覺地我們希望選擇 w 使上述距離最大化，並且所有點都在兩超平面之上或之外正確分類。在實務上，上列兩超平面是足以分別兩分類最貼近的兩超平面，也就是說兩超平面上各有一個以上 x_j 資料點，這些點 x_j 就稱為「支持向量」。因此，SVM 的問題是

maximize  d = 2/√||w||,   或等價地，minimize  w'w

subject to:   y_j (Σ_i w_i x_{ij} - b)  ≧ 1,  all j

式中 j 代表學習資料點 (x_{1j}, ..., x_{kj}, y_j), j = 1, ..., n。事實上前述「可完全正確分類」並不要求有兩個完全不相交的超平面或曲面區隔兩類資料點，數學上只要存在 f(x) 使 y = 1 時 f(x) ≧ 0 而 y = -1 時 f(x) < 0，或相反方向；而實務的要求是存在 δ > 0 使 y = 1 時 f(x) ≧ δ, y = -1 時 f(x) ≦ -δ。但

若   y_j (Σ_i w_i x_{ij} - b)  ≧ δ  則   y_j (Σ_i (w_i/δ) x_{ij} - b/δ)  ≧ 1，

反之亦然，因此取 δ = 1 並不會太特殊。

雖然 SVM 是從假設待分類物件可以完全被區隔在 w'x - b = ±1 兩超平面之外開始，但事情總不是那麼完美，可能

y_j = 1 但 w'x_j - b = 1 - ξ_j;  或
y_j = -1 但 w'x_j - b = -1 + ξ_j

合併即 y_j(w'x_j - b) = 1 - ξ_j，其中 ξ_j > 0 也可以寫成

ξ_j = 1 - y_j(w'x_j - b),  當 y_j(w'x_j - b) < 1

此時除了根據具體情況，我們不知這些個體能否切割開來，如下圖所示（取自 Tommy Huang (2018) 「機器學習-支撐向量機(support vector machine, SVM)詳細推導」
）

標示為 ●（或 ○）的點和標示為 ＋ 的點交錯存在；事實上標示為 ● 的點甚至可能跑到 w'x_j - b > 1 的區域，而標示為 ＋ 的點也可能跑到 w'x_j - b < -1 的區域，不只在圖中做為區隔的兩超平面之間。另一方面，

如果  y_j(w'x_j - b) ≧ 1，則 1 - y_j(w'x_j - b) ≦ 0

因此，Σ_j max{0, 1 - y_j(w'x_j - b) 可以當做錯誤分類的替代指標，一如在感知機方法，在判別分析，及在邏輯斯迴歸採用的不同目標（損失）函數。

把兩評量準則統合在一起，我們把目標函數定為

minimize w'w + θ Σ_j max{0, 1 - y_j(w'x_j - b)} = w'w + θ Σ_j ξ_j

subject to:   y_j(w'x_j - b) ≧  1 - ξ_j,  ξ_j ≧ 0,  j = 1, ..., n

目標函數是 w 的正確定 (positive definite) 二次式加 ξ 的（正值）一次式，是一個凸函數 (convex function)；限制式是 w, ξ, 及 b 的一次不等式，即由一些在 (b, w, ξ) 空間之超平面決定的半空間的交集區域，整個問題是在一個凸區域的凸規劃（凸目標函數找最小值）問題。

支持向量機的問題涉及變數  w, ξ, 及 b，共 k + n + 1 個變數，但目標函數未涉及 b，只有 k + n 個變數，k 是 w 的分量數，n 是訓練樣本大小。限刮條件則有 2n 個，包括 y_j(w'x_j - b) ≧  1 - ξ_j, 和 ξ_j ≧ 0。一般而言 n 比 k 大，因此即使最適解是在邊界上，此邊界並非所有 2n 個不等式的邊界（等式）。這也就是說：並非所有 ξ_j 都等於 0。事實上若所有 ξ_j = 0，也就不需要這些變數和條件，然後由前面我們知道並非所有 y_j(w'x_j - b) 都等於 1。由此推知，最適解可能符合某些限制條件的邊界，但不是全部，因此不方便直接套用 Lagrange 乘數法。

另一方面，定義  ξ_j = max{0, 1 - y_j(w'x_j - b)}，則

ξ_j ≧ 0 且 ξ_j ≧ 1 - y_j(w'x_j - b)

這就是前面極小化問題的限制條件，因此如果考慮

minimize w'w + θ Σ_j max{0, 1 - y_j(w'x_j - b)} 

而不是極小化 w'w + θ Σ_j ξ_j，應可不加限制條件。上列目標函數是 w, b 的凸函數，變數範圍無限制，任一變數 w_i 或 b 趨於 ±∞ 時應無上界，因此有一絕對最小值，也是唯一的局部極大值。但 max{f(x), g(x)} 形式使得極值未必在梯度零之處（極小值所在不能微分或甚至偏導數不存在）。

回到目標函數 w'w + θ Σ_j ξ_j 在限制條件之下的極小化問題，我們可嘗試將其轉成 Lagrange 對偶問題。首先將問題的 Lagrange 函數寫出：

F(w, b, ξ, α, β)
   = (w'w + θ Σ_j ξ_j) - Σ_j α_j [y_j (w'x_j - b ) + ξ_j - 1] - Σ_j (β_j ξ_j)
   = w'w - Σ_j α_j [y_j (w'x_j - b ) - 1] + Σ_j (θ - α_j - β_j) ξ_j

函數 F 對 w, b, ξ 的梯度或偏微分別是

▽w = 2w - Σ_j α_j y_j x_j
▽b = - Σ_j α_j y_j
▽ξ = θJ - α - β

此處 J 是 n 維行向量，其元素皆為 1,，n 是訓練樣本數。就 b 而言，其可變化範圍可說無界限，要極小化 F 函數值，可根據其偏導數 ▽b 任意增減，除非其偏導數為 0，否則 F 值將無下限。這表示 α, β 不能任其變化而需額外限制；對 ξ 亦然，除非 ▽ξ 為 0，否則無法控制 F 的值。若 α, β 限制在使 ▽b, ▽ξ 可令其為 0 的範圍，當然也可計算得 w 的適當值使 ▽w = 0。結果得

w = Σ_j α_j y_j x_j/2

並附加限制式

Σ_j α_j y_j = 0, 
β_j = θ - α_j

將所有結果代入 F 函數，得

h(α) = min_{x in S} F(w, b, ξ, α, β)
        = Σ_j α_j - (1/4) Σ_i Σ_j α_i α_j y_i y_j x'_i x_j
        = Σ_j α_j - w'w   其中  w = Σ_j α_j y_j x_j/2

需要極大化 h(α) ，而限制條件

Σ_j α_j y_j = 0, 
０ ≦ α_j ≦ θ,  j = 1, ..., n.

這是在區間集 [0, θ]^n 上一個 n-1 維度超平面上求二次式 h(α) 的極大值。即使對偶問題看起來比原 Lagrange 函數極小化問題簡化，仍是有 n 個變數 α_j，一個等式限制式，以及各變數都有雙端點限制，無法用微分法求解極值。但對偶問題的目標函數顯然是個凸函數，限制在一個凸集合內的極小化問題，其解可能在邊界點，不能直接以微分法求解。

支持向量機在使用線性式無法適當分隔兩分類的對策是考慮維度的增加，或說是考慮非線性變數變換：取一向量值核函數 φ(x), 又以內積定義 k(x_i, x_j) = <φ(x_i), φ(x_j)>，用 φ(x_i) 取代上述 x_i，等於對原始分類用數據 x_i 做了變換後再使用，則以 φ(x_i) 做線性的支持向量機分類，相當於用原始數據 x_i 做非線性 SVM 分類。不過這樣的變數變換在感知機、邏輯斯迴歸等事實上也能做，而且並沒有脫離「線性」方法的範疇，但對輸入資料 x 而言確實是非線性的。除內積式定義外也有不同的 k(x_i, x_j) 定義，如

k(x_i, x_j) = (x_i．x_j + c)^d， 
k(x_i, x_j) = exp(-γ ||x_i - x_j||^2)， 
k(x_i, x_j) = tanh(κ x_i．x_j + c)

等等。但前面內積式的 k(x_i, x_j) 只是用 φ(x_j) 取代 x_j, 因此前面利用諸 x_j 所在空間之超平面做分隔的方法直接套用到 φ(x_j)，故 k(x_i, x_j) 可以直接取代 x'_i x_j，但非內積式的 k(x_i, x_j)  似不宜直接代入前述 h(α) 極值問題？實際上如何操作筆者仍未學習，在此就不多說了。

解決 h(α) 之極大化得最適解 α = α*，套入 w 在 h(α) 的「定義式」

w = Σ_j α_j y_j x_j/2

還需要解決 b 的問題，至於 ξ，用

 ξ_j = max{0, 1 - y_j(w'x_j - b)}

可得，這是 Lagrange 對偶問題法給予原問題的解。那麼 b 如何計算？假設 x_j 在支撑向量的兩超平面之一上，也就是

y_j (w'x_j - b ) ＝ 1   

則得 b = w'x_j - y_j，這是因 y_j = ±1, 所以 y_j = 1/y_j 而得。但不同 b 是這（些）超平面的平移，結果將使得諸 ξ_j 之值改變。那應如何決定計算 b 的 x_j？筆者的想法：我們的希望

一是有最少 ξ_j > 0；或二是 Σ_j ξ_j 最小。

雖然依原始目標應採後者；因非線性關係，我們考慮前者。首先依 y_j = ±1 將資料分成兩組：

y_j = 1,   w'x_j - 1 ≧ b - ξ_j
y_j = -1,  w'x_j + 1 ≦ b + ξ_j

對於 ξ_j = 0 的資料，

當  y_j = -1 時 w'x_j + 1 ≦ b 而  y_j = 1 時 b ≦ w'x_j - 1

對於 ξ_j > 0 的，

當  y_j = -1 時 w'x_j + 1 ＝ b + ξ_j 而  y_j = 1 時 b - ξ_j = w'x_j - 1

對 y_j = 1 者計算 u_j = w'x_j - 1；對 y_j = -1 的，計算 v_j = w'x_j + 1。捨棄若干 ξ_j 可能為正的，也就是 u_j 最小的和 v_j 最大的，測試不等式

max{w'x_j + 1: y_j = -1, ξ_j = 0} ≦ b  ≦ min{w'x_j - 1: y_j = 1, ξ_j = 0}

即 max{v_j: y_j = -1, ξ_j = 0} ≦ b  ≦ min{u_j: y_j = 1, ξ_j = 0}。若不等式不成立，上列不等式左邊反而比右邊大，意謂應允許更多 ξ_j > 0。反之，如果這不等式兩端有餘裕，表示可讓更多 v_j (y_j = -1) 較大或 u_j (y_j = 1)  較小者對應的 ξ_j = 0。如此，能選擇 b 使最多 ξ_j = 0，也就是最少 ξ_j > 0。

回顧問題的 Lagrange 目標函數：

F(w, b, ξ, α, β)
   = (w'w + θ Σ_j ξ_j) - Σ_j α_j [y_j (w'x_j - b ) + ξ_j - 1] - Σ_j (β_j ξ_j)
   = w'w - Σ_j α_j [y_j (w'x_j - b ) - 1] + Σ_j (θ - α_j - β_j) ξ_j

對諸 α_j, β_j 原本只要求其非負；但在轉成對偶問題時卻加了限制條件

Σ_j α_j y_j = 0,  及 
β_j = θ - α_j,  ０ ≦ α_j ≦ θ, for all j

結果 F(w, b, ξ, α, β) = w'w - Σ_j α_j y_j w'x_j + Σ_j α_j，與 b 無關，諸 ξ_j 也隱藏不見了，似乎 b 的選擇雖影響了諸 ξ_j，卻與目標無關了。

我們原本要解的是 w, b, ξ，要求對每一訓練資料點成立  y_j(w'x_j - b) ≧  1 - ξ_j，其中 ξ_j ≧ 0，使其「損失」最小；但上述程序是把前述損失與條件式整合為一 Lagrange 函數式，又轉成對偶問題，把 Lagrange 乘數當成對偶變數，極大化最小的 L:agrange 函數值，但我們要的解呢？以上過程彙整如下，

目標：
    minimize (w'w) + θ(Σ_j ξ_j)
    subject to: y_j(w'x_j - b) ≧  1 - ξ_j, ξ_j ≧ 0
另一形式：
    minimize (w'w) + θ(Σ_j max{0, 1-y_j(w'x_j - b)})
    把 max{0, 1-y_j(w'x_j - b)} 定義為 ξ_j ，則之前限制式都成立。
Lagrange 方法：
    原問題
       F(w, b, ξ, α, β) =
           w'w - Σ_j α_j [y_j (w'x_j - b ) - 1] + Σ_j (θ - α_j - β_j) ξ_j
       限制: y_j(w'x_j - b) ≧  1 - ξ_j, ξ_j ≧ 0,  all j
    對偶問題
       h(α, β) = Σ_j α_j - (1/4) Σ_i Σ_j α_i α_j y_i y_j x'_i x_j
       限制: Σ_j α_j y_j = 0,
               β_j = θ - α_j, ０ ≦ α_j ≦ θ,   all j
    對偶問題解過程:
       (1) 限制對偶變數 α, β 範圍, 使 h(α, β) 有意義, 可極大化。
       (2) 在上述限制中, 對每一可行的 (α, β) 計算出 w*, b*, ξ*。
       (3) 解對偶問題得 (α, β) 之解, 以 (α*,β*) 表示之。
疑問：
    把 (α*,β*) 代入, 計算最終的 w*, b*, ξ*, 結果能達成目標嗎?

對於上列疑問，其實有兩個問題要解決：

其一，原目標是極小化 (w'w) + θ(Σ_j ξ_j)，其中還有一個未在目標函數出現的 b, 而 w, b, ξ 受一些不等式限制，相當於限制它們在一個凸集合 S 中。而前述解法把關於 w, b, ξ 的限制以乘數 α, β 為媒界加到目標函數中，限制 α ≧ 0, β ≧ 0；成為新目標函數 F( w, b, ξ , α, β)。但在關於 F 的對偶問題中對 α, β 又加了新限制，假設原來 (α, β) 的限制是 P，現在是 P*，是否

min_S max_P F( w, b, ξ , α, β) = min_S max_P* F( w, b, ξ , α, β)

再者，原 Lagrange 函數 F 之極值問題對應原始極值問題明顯是在 Lagrange 乘數 α, β 為 0 時才等價，但 (α, β) 從限制在 P 縮減至 P* 則即使極值相等，卻不是 α = β = 0，所求得的 w, b, ξ 是否相等？

其二是 F 之原問題和對偶問題能否得相同解的問題，基本上是能否

min_S max_P* F( w, b, ξ , α, β) =  max_P* min_S F( w, b, ξ , α, β)

原本支持向量機要解決的是 min_S max_P F( w, b, ξ , α, β)，而上面談的解決方法是解  max_P* min_S F( w, b, ξ , α, β), 實際上

  max_P* min_S F( w, b, ξ , α, β) ≦ min_S max_P* F( w, b, ξ , α, β)
          ≦ min_S max_P F( w, b, ξ , α, β)

兩個不等式都能變成等式才算解決了 SVM 的問題。

目標 Lagrange 函數

F( w, b, ξ , α, β)
   = w'w - Σ_j α_j [y_j (w'x_j - b) - 1] + Σ_j (θ - α_j - β_j) ξ_j
   = w'w + Σ_j α_j [1 - y_j (w'x_j - b)]
              + Σ_j (θ - α_j - β_j) max{0, 1 - y_j (w'x_j - b)
   = w'w + Σ_{j: ξ_j=0} α_j [1 - y_j (w'x_j - b)]
              + Σ_{j: ξ_j > 0} (θ - β_j) [1 - y_j (w'x_j - b)]
   = w'w + Σ_j α_j [1 - y_j (w'x_j - b)]

在 Σ_j α_j y_j = 0, 及 0 ≦ α_j ≦ θ, j = 1, ..., n 條件下，當 ξ_j = 0, 即 y_j (w'x_j - b) > 1 時，欲極大化 F( w, b, ξ , α, β) 則對應的 α_j 應取 0；僅當 ξ_j > 0 或 y_j (w'x_j - b) < 1 時 α_j 應儘量大，最好都等於其上限 θ，唯必須受 Σ_j α_j y_j = 0, 的限制，但在 y_j (w'x_j - b) ＝ 1 時 α_j 可大可小。若 y_j = ±1 時 α_j 非零的個數一樣多，則所有對應 ξ_j > 0 的 α_j 都可取到極端值 θ，而

max_P*  F( w, b, ξ , α, β) = max_P  F( w, b, ξ , α, β) = w'w + θ Σ_j ξ_j

另一個觀察：由原來的 Lagrange 目標函數

F(w, b, ξ, α, β)
   = (w'w + θ Σ_j ξ_j) - Σ_j α_j [y_j (w'x_j - b ) + ξ_j - 1] - Σ_j (β_j ξ_j)

當 ξ_j > 0 時 y_j (w'x_j - b ) = 1 - ξ_j，可知此時 α_j 不影響 F 函數的值， y_j (w'x_j - b ) = 1 時亦然；反之，ξ_j = 0 時 β_j 不影響 F 的函數值。也就是說：如果對應 ξ_j = 0 時 α_j 取 0, ξ_j > 0 時 β_j 取 0, 則 F 的值不變而一直等於 f 的值。因此，

在諸 α_j + β_j = θ 限制下，α_j = 0 當 ξ_j = 0 （或更精確地， y_j (w'x_j - b ) = 1 - ξ_j 時），且 α_j = θ 當 ξ_j > 0，則
     F(w,b,ξ ,α,β) = f(w,b,ξ) = w'w + θ Σ_j ξ_j

這是對每一組 (w, b, ξ) 都成立，即

f(w,b,ξ) = F(w,b,ξ ,α*,β*)  = max_P* F(w,b,ξ ,α,β)

則 min_S max_P* F(w,b,ξ ,α*,β*) 所解出的  (w, b, ξ) 應也極小化了 f(w,b,ξ)，是我們所要的解。

由於在所有變數限制

y_j(w'x_j - b) ≧  1 - ξ_j,  ξ_j ≧ 0,  all j;
 Σ_j α_j y_j = 0;
β_j = θ - α_j, ０ ≦ α_j ≦ θ,   all j.

之下，目標函數

F(w, b, ξ, α, β) =  w'w - Σ_j α_j (y_j w'x_j -1) = ψ(w, α)

是 w 的二次凸函數，是 α 的直線型函數。也就是說我們現在面對的新問題是

Max_α Min_w ψ(w, α) = Min_w Max_α ψ(w, α)
        where   ψ(w, α) =  w'w - Σ_j α_j (y_j w'x_j -1)

變數範圍是：

w 狂 R^k (k 為各輸入資料點 x_j 之維度；
Σ_j α_j y_j = 0; 0 ≦ α_j ≦ θ,  j = 1, ..., n.

對於每一組在上列範圍的 w, α，令

β_j = θ - α_j,  b in R, ξ_j = max{0, 1 - y_j(w'x_j - b),  j = 1, ..., n

則 ψ(w, α) =  w'w - Σ_j α_j (y_j w'x_j -1) 可化為

w'w - Σ_j α_j [(y_j w'x_j - b) -1]
    = w'w - Σ_j α_j [y_j (w'x_j - b ) - 1] + Σ_j (θ - α_j - β_j) ξ_j
    = (w'w + θ Σ_j ξ_j)
           - Σ_j α_j [y_j (w'x_j - b ) -(1 - ξ_j)] - Σ_j (β_j ξ_j)

而 β_j 的定義加上 α_j 的範圍限制完全複製了前面極大化 h(α, β) 問題中 α, β 的範圍限制；而 ξ_j 的定義使得

y_j(w'x_j - b) ≧ 1 and ξ_j = 0;  or
y_j(w'x_j - b) = 1 - ξ_j,  ξ_j > 0

因此 ψ(w, α) 的大中取小和小中取大問題，等同於原來 F(w, b, ξ, α, β) 的大中取小和小中取大問題。

若且唯若 Max_α Min_w ψ(w, α) = Min_w Max_α ψ(w, α)，則 

Max_{α β} Min_{w, b, ξ,} F(w, b, ξ, α, β)
               =  Min_{w, b, ξ,} Max_{α β} F(w, b, ξ, α, β)

就函數 ψ(w, α) =  w'w - Σ_j α_j (y_j w'x_j -1) 而言 (w'x_j 可改成 w'x_j - b)，固定 w 之下諸 α_j 假設都是 0 或 θ，因此大中取小解的 w 對應了某一組由 0 和 θ 組成的 α。役過來說，ψ(w, α) 先對 w 做極小化得

h(α) = Σ_j α_j - w'w = Σ_j α_j - Σ_i Σ_j α_i α_j y_i y_j x'_i x_j;

對 α_j 微分，得

Ｄ_j h(α) = 1 - y_j w'x_j = d_j

式中 w 是 α 的函數。除 Σ_j α_j y_j = 0 限制外，α_j 顯然如同 ψ(w, α) 固定 w 時一般，依 d_j 正負而必須取邊界值 0 或 θ：當 d_j < 0 ( ξ_j = 0 ) 時 α_j = 0；當 d_j > 0 ( ξ_j = d_j ) 時 α_j = θ。這也就是說：

固定 w 在 W = R^k 中，於 A = {α: Σ_j α_j y_j = 0, 0 ≦ α_j ≦ θ} 中使 ψ(w, α) 最大的 α 在 A* = {α: Σ_j α_j y_j = 0, α_j = 0 或 θ} 上。

將 ψ(w, α) 先對 w 取極小，得 h(α)，則於 A 中使 h(α) 達最小的 α 也在 A* 上。

於是對每一 w in W，使 ψ(w, α) 最大的 α 是 A* 的子集 A°，再對 w 做極小化，得到的大中取小解是 A° 的一點所對應的 w°；而 ψ(w, α) 的小中取大解，就是上述 h(α) 最大化的 α 也是 A* 上的一點 α*，對應的 w = w* 是

w* = Σ_j α_j y_j x_j/2 = (θ/2) Σ_{j: y_j w*' x_j <1} y_j x_j

雖然上式看起來有點怪，w* 的計算式怎麼又涉及未知的 w* 本身？按理 w* 是在 α* 得到後再計算的，但在求解 α 時隱含上列關係，如前面所述；並且，由於 w'x_j 可以用 w'x_j - b 取代，因而 α* 如同固定 w 之下極大化 ψ(w, α) 的 α 的解，也就是說： α* 也在 A° 上。

對目標函數 ψ(w, α)，w 在 W 中而 α 在 A 中。固定 w 求 max_α ψ(w, α) 得軌跡集合 U = {(w, α):  w in W, α in A°}；固定 α 求 h(α) = min_w ψ(w, α) 得軌跡集合 V = {(w, α):  α in A}，又求 h(α) 之最大得解 (w*, α*) 其中 α* 在 A° 意謂 (w*, α*) 在 U∩V 中，即 U∩V 非空。設 (w*, α*) 為小中取大解，(w°, α°) 為大中取小解，即

ψ(w*, α*) = max_α min_w ψ(w, α)
ψ(w°, α°) = min_w max_α ψ(w, α)

小中取大解 ψ(w*, α*) 是沿著集合 V = {(w(α), α): α in A} 極大化 ψ(w(α), α)；大中取小解 ψ(w°, α°) 則沿著 U = {(w, α(w)): w in W} 極小化 ψ(w α(w))。兩集合有交集，假設 (w", α") 是交集中一點，則

ψ(w*, α*) ≧ ψ(w", α") ≧ ψ(w°, α°) ≧ ψ(w*, α*)

第一個不等式是因 (w", α") 在 V 中，而 (w*, α*) 是 V 中使 min_w ψ(w, α) 達最大的；第二個不等式是因在 U 中，(w°, α°) 是 max_α ψ(w, α) 最小的；第三個不等式是因大中取小總是不低於小中取大。由上式，得 ψ(w*, α*) ＝ ψ(w°, α°)，這意謂或者 (w*, α*) ＝ (w°, α°) ，或者兩者都是問題的解。

以上筆者用相當笨拙的方法說明了幾件事：

其一，原 SVM 目標函數極小化問題化為 Lagrange 函數極值問題，則原問題相當於 Lagrange 函數大中取小（先對 Lagrange 乘數求目標最大，再從其中取最小）問題，其對偶問題就是小中取大（先對 目標變數求目標最小，再從其中取最大）問題。但這其中我們又對 Lagrange 取值範圍做了限制，但結果對目標極值沒影響／

其二，由最適解的 Lagrange 乘數結構發現：雖然與原 Lagrange 函數極值問題大中取小解的最適 Lagrange 乘數不同，但對目標變數最適解應無影響。

其三，前述縮減 Lagrange 乘數取值範圍後的問題，使目標 Lagrange 函數簡化，相對應地，目標變數和 Lagrange 乘數也簡化，前者只看 w，後耆只看 α。而原問題（較多目標變數和較多 Lagrange 乘數）有解（大中取小解與小中取大解一致），若且唯若簡化了的問題有解。

其四，如果我們的推論沒有犯錯誤，上述簡化了的問題是有解的。

基於以上，說明了我們用 Lagrange 對偶問題求得的確實是原問題的解。