Support Vector Regression R94922044 黃子桓 1 導論 Support Vector Machine 除了分類 (classification) 問題外, 也可用來處理回歸 (regression) 的問題。 所謂回歸指的是每個實體 (instance) 所對應的標籤 (label) 是 連續的實數, 而非離散的相異類別 (在 SVM 裡常以整數來表示)。 處理回歸問題 的 SVM, 稱為 Support Vector Regression。 2 基本想法 如同 SVM, SVR 的目標為尋找空間中的最適平面 (hyperplane)。 和 SVM 不 同的是, SVM 找的是能將資料一分為二的平面, 而 SVR 所找的則是能準確預測資 料分佈的平面。 假設訓練資料 (training data) 表示為 (x1, y1), . . . , (xl, yl) ∈ Rd×R, 其中 x 表示輸入的「特徵(attributes)」, y 表示該特徵所對應的回歸值 (相當於 SVM 中的目標類別, target class)。 令 f (x) = w · x + b, w ∈ Rd, b ∈ R, 如果對每 個 instance xi 而言, f (xi) 和 yi 的差值都很小, 則我們知道這樣的 f (x) 能從 x 準 確地預測 y, 這個 w 即是 SVR 所要找的平面。 用數學語言來表達, 可將 SVR 改 寫成下面問題 (請對照 SVM 一起看): kwk2 minimize 1 2 subject to kyi − (w · xi − b)k ≤ ε (1) 其中 ε ≥ 0, 用來表示 SVR 預測值與實際值最大的差距, 而此演算法也因此而得 名, 稱為 ε-SVR。 式 (1) 和 SVM 相對照, 可發現十分相像, 不同者為 SVM 考慮的 1 

l∑ (ξi + ξ ⁄ i ) minimize 1 2 kwk2 + C subject to  是預測類別 (predicted class) 和實際類別 (actual class) 需同號 (表示預測正確), 而 SVR 考慮的是預測值和實際值的差需小於 ε。 在 ε 合理的情形下 (例如給定一個大得過份的 ε 就是不合理), 如果從式 (1) 能求出解, 這種情形稱為 feasible。 然而大多數的應用中, 因為有雜訊、誤差等 等各種因素, 通常不會是 feasible 的情形, 因此我們要加入額外的項, 以容許某些 instances 落在 ε 之外: i=1 yi − w · xi − b ≤ ε + ξi w · xi + b − yi ≤ ε + ξ ⁄ i ≥ 0 ⁄ i ξi, ξ (2) ⁄, 用來決定該 training 在式 (2) 中, 每個 training instance 都有其對應的 ξ 及 ξ instance 是否可以落在 ε 的範圍之外。 而 C 的作用則如同在 SVM 裡一般, 用來調整訓練模型 (training model) 是否過份或不足調適資料 (overfitting 或 underfitting)。 當問題定義清楚後, 下一步就是來仔細想想, 該怎麼解決這個問題 了! 3 ε-SVR 3.1 Dual Problem 在上一章最後我們看到 ε-SVR 問題的其本定義, 如果大家還記得 SVM 的 求解過程的話, 應該不難猜到我們打算用什麼神兵利器來處理 SVR。 沒錯, Lagrange multiplier 是我們的好朋友 :-) 利用 Lagrange multiplier, 我們可以將式 (2) 2 

寫成 Lagrange function: kwk2 + C L = l∑ (ξi + ξ i=1 i ) − l∑ ⁄ i=1 (ηiξi + η ⁄ i ξ ⁄ i ) 1 2 − l∑ − l∑ i=1 αi(ε + ξi − yi + w · xi + b) ⁄ i (ε + ξ i + yi − w · xi − b) ⁄ α i=1 因此求解式 (2) 即相當於求解 L max α,η min w,b,ξ subject to α, η ≥ 0 l∑ = w − l∑ (α i=1 = ⁄ i i=1 = C − α(⁄) i ∂L ∂b ∂L ∂w ∂L ∂ξ(⁄) i − αi) = 0 ⁄ i )xi = 0 (αi − α − η(⁄) i = 0 i = C − α(⁄) i 及 w = 將式 (5), (6), (7) 改寫成 η(⁄) 將 w, b, ξ 皆消去只留下 α, η: 由於這個問題是一 convex optimization problem, 因此 min 和 max 可交換。 我們 先考慮 min 的情形, 求極值的一般做法即是求所有變數偏微分為零值之處: (3) (4) (5) (6) (7) l ∑ i=1(αi − α l∑ l∑ ⁄ i )xi 代入式 (4) 中, 可 i,j=1 l∑ (αi − α l∑ ∑ i=1(αi − α (αi − α i=1 −1 2 max α,η subject to i )(αj − α ⁄ j )xi · xj − ε ⁄ (αi + α ⁄ i ) + yi(αi − α ⁄ i ) ⁄ i ) = 0 and αi, α ⁄ i i=1 ∈ [0, C] i=1 (8) l 推導過程中我們可看出一些性質, 首先 w 可表示成 x 的某種線性組合; 另一方面, i )(x · xi) + b 可發現計算 f (x) 的複雜度和 x 的維度 ⁄ 我們從 f (x) = 無關, 只和 Support Vector (αi − αi∗ 不為零的 instances) 的個數有關。 而式裡的 x · xi 部份如同 SVM, 可用某個 kernel function 來取代, 將線性的 SVR 搖身一變成 為非線性系統, 這部份將在後面略加介紹。 在此, 我們將不介紹如何求解式 (8), 因為我還沒看懂 . . . , 我們先介紹如何來 找 b 的值。 3 

3.2 Computing b 根據 Karush-Kuhn-Tucker (KKT) conditions, SVR 的 dual problem 只有在下述 條件成立時才有解: α αi(ε + ξi − yi + w · xi + b) = 0 i + yi − w · xi − b) = 0 ⁄ ⁄ i (ε + ξ (C − αi)ξi = 0 (C − α ⁄ i = 0 ⁄ i = 0 αiα ⁄ i )ξ (9) (10) 從上述條件我們可以發現, 僅當 α(⁄) 能落於 ε 之外。 再來, αiα 納出: ⁄ i = 0 說明 αi 和 α i = C 時, ξ(⁄) (11) i 才有可能不為零, 因此 xi 才有可 ⁄ i 不可能同時不為零。 因此我們可歸 ε − yi + w · xi + b ≥ 0 and ξi = 0 ε − yi + w · xi + b ≤ 0 ⁄ 我們可依樣畫葫蘆寫下 α i 的情形。 結合上述絛件, 我們可決定 b 的範圍: i > 0} ≤ b ≤ max{−ε+yi−w·xi|αi > 0 or α max{−ε+yi−w·xi|αi < C or α ⁄ if αi < C if αi > 0 (12) (13) i < C} ⁄ (14) 如果 b 是離散的, 測式該範圍內所有可能的值不失為一可行之法。 而若 b 非離散, 則需以其它方式求之, 恕筆者無力介紹。 3.3 Kernel Function 0 說到 SVR, 自然不能不提 kernel function。 前面提過, x · xi 可改寫成一 kernel ), 其中 Φ(x) 為一將 d 維資料投影到其它 function k(x, x 維資料的對應, 例如 R2 → R3。 透過 kernel function, SVR 跨過線性的門檻, 威力 大大提升。 ) = Φ(x) · Φ(x ), 令 k(x, x 0 0 然而並非所有雙變數的 function 都可拿來當作 kernel function, 之所以能成為 )。 kernel function, 必須滿足上述的條件, 亦即存在 Φ(x) 使得 k(x, x ) = Φ(x)·Φ(x 0 0 4 

一般言而先找 Φ(x) 再來找 k(x, x 判斷一個雙變數 function 是否是 kernel function: 0 ) 較為容易, 但我們可利用 Mercer’s Condition 來 ∫ 0 Theorem 1. k(x, x is finite, then k(x, x 0 )g(x)g(x 0 )dxdx 0 ≥ 0 ) is kernel function, if and only if for any g(x) such that g(x)2dx ∫ k(x, x 上面這段定理簡單的說就是, 如果我們找到某個 function k(x, x ), 想檢查 0 ) 是不是 kernel function, 則我們必須證明對於「所有的」g(x) 來說, 如果 0 ≥ 0。看起來並不容易, 不過我們 )g(x)g(x )dxdx k(x, x ∫ 0 0 g(x)2dx 是有限的, 則 會用一個例子來說明。 ∫ 0 Example: k(x, x 0 ) = (x · x 0 )n 是 kernel function。 ∫ 0 )dxdx 0 = )g(x)g(x 0 )ng(x)g(x 0 )dxdx 0 (x · x 0 0 1 + . . . + xdx 0 d)ng(x)g(x 0 )dxdx 0 k(x, x 證明:∫ ∫ ∫ [ ∑ ∑ (x1x = = = r1+...+rd=n r1+...+rd=n n [∫ r1!r2!··· rd! n r1!r2!··· rd! (xr1 1 xr2 2 . . . xrd d )g(x)dx ] ] 2 ≥ 0 (xr1 1 . . . xrd d x 0r1 1 . . . x 0rd d ) g(x)g(x 0 0 )dxdx (15) 像這個例子算是最簡單的介紹, 其它 kernel function 要證明就不是那麼容易 了。 5