分類器的符號、它到邊界的幾何距離,以及擬合時使用的目標函數,彼此相關但不同。只有所有有限 Gram 矩陣均為對稱半正定時,核函數(kernel)才可描述實特徵空間的內積。
分數有尺度,距離沒有
仿射分類器分數為 f ( x ) = w T x + b f(x)=w^Tx+b f ( x ) = w T x + b ,其中 w ≠ 0 w\ne0 w = 0 ,並按符號預測。對 c > 0 c>0 c > 0 ,把 ( w , b ) (w,b) ( w , b ) 換成 ( c w , c b ) (cw,cb) ( c w , c b ) 不改變邊界和符號,卻令每個分數乘 c c c 。有符號幾何距離是 ( w T x + b ) / ∥ w ∥ (w^Tx+b)/\|w\| ( w T x + b ) /∥ w ∥ ;除以範數消去這個任意正尺度。標籤 y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } 的有符號間隔(margin)為 y ( w T x + b ) / ∥ w ∥ y(w^Tx+b)/\|w\| y ( w T x + b ) /∥ w ∥ 。
對仿射分數 f ( x ) = w T x + b f(x)=w^Tx+b f ( x ) = w T x + b (w ≠ 0 w\ne0 w = 0 )與帶標籤的觀察 ( x , y ) (x,y) ( x , y ) (y ∈ { − 1 , 1 } y\in\{-1,1\} y ∈ { − 1 , 1 } ),函數間隔(functional margin)為 y f ( x ) yf(x) y f ( x ) ,幾何間隔(geometric margin)為 y f ( x ) / ∥ w ∥ yf(x)/\|w\| y f ( x ) /∥ w ∥ 。當且僅當函數間隔為正時,該觀察被正確分類。
數據嚴格線性可分時,可重新縮放,使最小有符號分數為 1。硬間隔支持向量機(hard-margin SVM)在 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\ge1 y i ( w T x i + b ) ≥ 1 約束下最小化 1 2 ∥ w ∥ 2 \tfrac12\|w\|^2 2 1 ∥ w ∥ 2 。最接近觀察點到邊界距離為 1 / ∥ w ∥ 1/\|w\| 1/∥ w ∥ ,兩個支撐平面距離為 2 / ∥ w ∥ 2/\|w\| 2/∥ w ∥ ;這些數值依賴所述正規化。若約束不可行,硬間隔問題沒有可行解;優化方法不能令相同特徵上的矛盾標籤變成可分。
約束 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\ge1 y i ( w T x i + b ) ≥ 1 固定的是函數間隔,不是距離。位於間隔上的點到邊界的距離是 1 / ∥ w ∥ 1/\|w\| 1/∥ w ∥ ,而它會隨 w w w 改變。把 ( w , b ) (w,b) ( w , b ) 乘以 c > 0 c>0 c > 0 ,每個函數間隔都乘 c c c ,而每個幾何間隔不變;所以單看函數間隔很大,並不能說明點離邊界有多遠。
例題:兩筆觀察與證書
一維負類觀察為 x = 0 x=0 x = 0 ,正類觀察為 x = 4 x=4 x = 4 。約束是 − b ≥ 1 -b\ge1 − b ≥ 1 和 4 w + b ≥ 1 4w+b\ge1 4 w + b ≥ 1 ;相加得 4 w ≥ 2 4w\ge2 4 w ≥ 2 ,故每個可行解均有 w ≥ 1 / 2 w\ge1/2 w ≥ 1/2 。可行選擇 w = 1 / 2 w=1/2 w = 1/2 、b = − 1 b=-1 b = − 1 達到下界,並最小化 1 2 w 2 = 1 / 8 \tfrac12w^2=1/8 2 1 w 2 = 1/8 。邊界是 x = 2 x=2 x = 2 ,每個觀察點距邊界 2,支撐平面之間距離為 4。
對偶(dual)證書以另一方式顯示下界。取乘子 α − = α + = 1 / 8 \alpha_- = \alpha_+ =1/8 α − = α + = 1/8 ,均非負;∑ α i y i = 0 \sum\alpha_i y_i=0 ∑ α i y i = 0 ,且 ∑ α i y i x i = 4 / 8 = 1 / 2 = w \sum\alpha_i y_i x_i=4/8=1/2=w ∑ α i y i x i = 4/8 = 1/2 = w 。兩個約束都取等,故滿足互補鬆弛性(complementary slackness)。對偶目標為 1 / 4 − 1 2 ( 1 / 2 ) 2 = 1 / 8 1/4-\tfrac12(1/2)^2=1/8 1/4 − 2 1 ( 1/2 ) 2 = 1/8 ,等於可行原始(primal)目標,因此證明最優。這不需要聲稱每個問題的每筆數據都有正乘子。
鉸鏈損失改變了優化問題
對分數和標籤,鉸鏈損失(hinge loss)為 max ( 0 , 1 − y f ( x ) ) \max(0,1-yf(x)) max ( 0 , 1 − y f ( x )) 。達到或超過所需函數間隔時為零,落在其內時為正;分錯或分數為零時至少為 1。一種常見軟間隔(soft-margin)目標是
1 2 ∥ w ∥ 2 + C ∑ i max ( 0 , 1 − y i ( w T x i + b ) ) , C > 0. \frac12\|w\|^2+C\sum_i\max(0,1-y_i(w^Tx_i+b)),\qquad C>0. 2 1 ∥ w ∥ 2 + C i ∑ max ( 0 , 1 − y i ( w T x i + b )) , C > 0.
這裏把損失相加;改用平均值會改變 C C C 的數值意義,所以比較時須寫明慣例。正則項偏好較小範數,損失項懲罰間隔違反。某候選值較低,只能證明另一候選在該 C C C 下非最優,本身不能證明前者全局最優。
概念視角 代數
把鉸鏈損失看成最優鬆弛量 引入鬆弛變量 ξ i ≥ 0 \xi_i\ge0 ξ i ≥ 0 ,滿足 y i ( w T x i + b ) ≥ 1 − ξ i y_i(w^Tx_i+b)\ge1-\xi_i y i ( w T x i + b ) ≥ 1 − ξ i ,並最小化 1 2 ∥ w ∥ 2 + C ∑ i ξ i \tfrac12\|w\|^2+C\sum\limits_i\xi_i 2 1 ∥ w ∥ 2 + C i ∑ ξ i 。對固定的 ( w , b ) (w,b) ( w , b ) ,可取的最小 ξ i \xi_i ξ i 是 max ( 0 , 1 − y i ( w T x i + b ) ) \max(0,1-y_i(w^Tx_i+b)) max ( 0 , 1 − y i ( w T x i + b )) ,因為 ξ i \xi_i ξ i 必須同時不小於 0 0 0 與 1 − y i ( w T x i + b ) 1-y_i(w^Tx_i+b) 1 − y i ( w T x i + b ) 。對鬆弛量取最小,恰好回到上面的目標,所以帶約束的鬆弛形式與無約束的鉸鏈形式描述同一個問題。在鬆弛形式中,ξ i \xi_i ξ i 是第 i i i 筆觀察違反間隔的量;在鉸鏈形式中,同一個數是分數上的損失。
例題:比較兩個參數選擇
沿用上述兩筆觀察。硬間隔解 ( w , b ) = ( 1 / 2 , − 1 ) (w,b)=(1/2,-1) ( w , b ) = ( 1/2 , − 1 ) 的鉸鏈損失為零,目標為 1 / 8 1/8 1/8 。對 ( w , b ) = ( 1 / 4 , − 1 / 2 ) (w,b)=(1/4,-1/2) ( w , b ) = ( 1/4 , − 1/2 ) ,兩個有符號分數均為 1 / 2 1/2 1/2 ,每個鉸鏈損失均為 1 / 2 1/2 1/2 ,目標是 1 2 ( 1 / 4 ) 2 + C ( 1 ) = 1 / 32 + C \tfrac12(1/4)^2+C(1)=1/32+C 2 1 ( 1/4 ) 2 + C ( 1 ) = 1/32 + C 。當且僅當 0 < C < 3 / 32 0<C<3/32 0 < C < 3/32 時它嚴格小於 1 / 8 1/8 1/8 ;C = 3 / 32 C=3/32 C = 3/32 時相等。比較表明在該嚴格範圍內硬間隔參數不是此軟間隔目標的最優解,但沒有求出全局軟間隔最小值。
若同一特徵向量分別有 +1 和 -1 標籤,共同分數 s s s 在硬間隔下須同時滿足 s ≥ 1 s\ge1 s ≥ 1 及 s ≤ − 1 s\le-1 s ≤ − 1 ,不可能成立。兩個鉸鏈損失之和 max ( 0 , 1 − s ) + max ( 0 , 1 + s ) ≥ 2 \max(0,1-s)+\max(0,1+s)\ge2 max ( 0 , 1 − s ) + max ( 0 , 1 + s ) ≥ 2 :∣ s ∣ ≤ 1 |s|\le1 ∣ s ∣ ≤ 1 時等於 2,其外更大。軟間隔公式可為此矛盾賦有限損失;只使用該特徵向量的確定性分類器不能同時正確標記兩者。
核函數是有結構的相似度
若存在實內積空間 H H H 與映射 ϕ : X → H \phi:\mathcal X\to H ϕ : X → H ,使對所有 x , z x,z x , z 都有 K ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z ) ⟩ K(x,z)=\langle\phi(x),\phi(z)\rangle K ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z )⟩ ,則函數 K : X × X → R K:\mathcal X\times\mathcal X\to\mathbb R K : X × X → R 稱為核函數。對點 x 1 , … , x n x_1,\dots,x_n x 1 , … , x n ,Gram 矩陣為 G = ( K ( x i , x j ) ) i , j G=(K(x_i,x_j))_{i,j} G = ( K ( x i , x j ) ) i , j 。
命題 11.1.5
(核函數的 Gram 矩陣半正定)
若 K K K 是核函數,則對任何有限選擇 x 1 , … , x n x_1,\dots,x_n x 1 , … , x n ,Gram 矩陣 G G G 對稱,且對每個 c ∈ R n c\in\mathbb R^n c ∈ R n 都有 c T G c ≥ 0 c^TGc\ge0 c T G c ≥ 0 。
對稱性來自 ⟨ ϕ ( x ) , ϕ ( z ) ⟩ = ⟨ ϕ ( z ) , ϕ ( x ) ⟩ \langle\phi(x),\phi(z)\rangle=\langle\phi(z),\phi(x)\rangle ⟨ ϕ ( x ) , ϕ ( z )⟩ = ⟨ ϕ ( z ) , ϕ ( x )⟩ ,即 K ( x , z ) = K ( z , x ) K(x,z)=K(z,x) K ( x , z ) = K ( z , x ) 。對實係數 c i c_i c i ,
∑ i , j c i c j K ( x i , x j ) = ∥ ∑ i c i ϕ ( x i ) ∥ 2 ≥ 0. \sum_{i,j}c_i c_j K(x_i,x_j)=\left\|\sum_i c_i\phi(x_i)\right\|^2\ge0. i , j ∑ c i c j K ( x i , x j ) = i ∑ c i ϕ ( x i ) 2 ≥ 0.
因此核函數的每個有限 Gram 矩陣均為對稱半正定(PSD)。要求涉及所有 有限輸入選擇,不只是某一抽樣矩陣。找到一個具有負二次型的 Gram 矩陣足以否定候選核函數;只檢查一個正矩陣卻不能證明普遍性。接近零的特徵值亦需小心數值近似。
例題:證明一個核函數、否定另一個
實數輸入下設 K ( x , z ) = 1 + x z K(x,z)=1+xz K ( x , z ) = 1 + x z 。特徵映射 ϕ ( x ) = ( 1 , x ) \phi(x)=(1,x) ϕ ( x ) = ( 1 , x ) 給出 K ( x , z ) = ϕ ( x ) T ϕ ( z ) K(x,z)=\phi(x)^T\phi(z) K ( x , z ) = ϕ ( x ) T ϕ ( z ) ;等價地,任意有限 Gram 二次型等於 ( ∑ i c i ) 2 + ( ∑ i c i x i ) 2 ≥ 0 (\sum\limits_i c_i)^2+(\sum\limits_i c_i x_i)^2\ge0 ( i ∑ c i ) 2 + ( i ∑ c i x i ) 2 ≥ 0 ,故每個有限樣本均符合半正定條件。
相反考慮 L ( x , z ) = 1 − x z L(x,z)=1-xz L ( x , z ) = 1 − x z 。輸入 0、2 的 Gram 矩陣為 ( 1 1 1 − 3 ) \begin{pmatrix}1&1\\1&-3\end{pmatrix} ( 1 1 1 − 3 ) 。取 c = ( 0 , 1 ) c=(0,1) c = ( 0 , 1 ) ,得 c T G c = − 3 < 0 c^T Gc=-3<0 c T G c = − 3 < 0 ,故非半正定;在包含這兩個輸入的定義域上,L L L 不可能是實內積核函數。負對角元素已構成反例:特徵向量的平方範數不能為負。口頭稱為「相似度」並不足以支持核技巧(kernel trick)。
常見錯誤
(只用一個正的 Gram 矩陣來驗證核函數)
單一個半正定的 Gram 矩陣不能使函數成為核函數。對 L ( x , z ) = 1 − x z L(x,z)=1-xz L ( x , z ) = 1 − x z ,在 x = 0 x=0 x = 0 的單點 Gram 矩陣是 ( 1 ) (1) ( 1 ) ,是半正定;但上面在輸入 0 0 0 與 2 2 2 的二點矩陣卻不是。候選核函數必須對每個有限輸入集都通過,或者被證明為特徵向量的內積。
為何感知器更新界需要間隔
感知器更新與最小化 SVM 目標不是同一操作。為每個輸入加入偏置座標:x ~ = ( x , 1 ) \widetilde x=(x,1) x = ( x , 1 ) 、w ~ = ( w , b ) \widetilde w=(w,b) w = ( w , b ) 。從零開始,當 y w ~ T x ~ ≤ 0 y\widetilde w^T\widetilde x\le0 y w T x ≤ 0 時更新 w ~ ← w ~ + y x ~ \widetilde w\leftarrow\widetilde w+y\widetilde x w ← w + y x 。等號慣例很重要:它決定分數零的觀察是否觸發更新。
設有限訓練集中每個 i i i 的增廣輸入 x ~ i = ( x i , 1 ) \widetilde x_i=(x_i,1) x i = ( x i , 1 ) 滿足 ∥ x ~ i ∥ ≤ R \|\widetilde x_i\|\le R ∥ x i ∥ ≤ R ,且存在單位向量 u u u ,使每個 i i i 都有 y i u T x ~ i ≥ γ > 0 y_iu^T\widetilde x_i\ge\gamma>0 y i u T x i ≥ γ > 0 。從 w ~ = 0 \widetilde w=0 w = 0 開始,當 y w ~ T x ~ ≤ 0 y\widetilde w^T\widetilde x\le0 y w T x ≤ 0 時更新 w ~ ← w ~ + y x ~ \widetilde w\leftarrow\widetilde w+y\widetilde x w ← w + y x 。無論觀察以何種次序出現,感知器的總更新次數至多為 ( R / γ ) 2 (R/\gamma)^2 ( R / γ ) 2 。
經 T T T 次更新,參數在 u u u 方向的投影至少為 T γ T\gamma T γ ,因為每次更新至少增加 γ \gamma γ 。一次更新時範數平方變為
∥ w ~ + y x ~ ∥ 2 = ∥ w ~ ∥ 2 + 2 y w ~ T x ~ + ∥ x ~ ∥ 2 ≤ ∥ w ~ ∥ 2 + R 2 . \|\widetilde w+y\widetilde x\|^2=\|\widetilde w\|^2+2y\widetilde w^T\widetilde x+\|\widetilde x\|^2\le\|\widetilde w\|^2+R^2. ∥ w + y x ∥ 2 = ∥ w ∥ 2 + 2 y w T x + ∥ x ∥ 2 ≤ ∥ w ∥ 2 + R 2 . 由更新條件,中間項非正。從零開始得 ∥ w ~ T ∥ 2 ≤ T R 2 \|\widetilde w_T\|^2\le TR^2 ∥ w T ∥ 2 ≤ T R 2 。由 Cauchy–Schwarz,T γ ≤ u T w ~ T ≤ ∥ w ~ T ∥ ≤ R T T\gamma\le u^T\widetilde w_T\le\|\widetilde w_T\|\le R\sqrt T T γ ≤ u T w T ≤ ∥ w T ∥ ≤ R T ,故 T > 0 T>0 T > 0 時 T ≤ ( R / γ ) 2 T\le(R/\gamma)^2 T ≤ ( R / γ ) 2 。論證需要分隔向量和半徑假設,並非對矛盾或不可分數據的普遍保證;它限制一次運行的總更新數,不是每一輪所需更新數。
證明透視
線性進展對平方根增長 這個證明讓兩個量互相對抗。間隔假設使投影 u T w ~ u^T\widetilde w u T w 每次更新至少增加 γ \gamma γ ,所以它至少是線性的 T γ T\gamma T γ 。更新條件使交叉項 2 y w ~ T x ~ 2y\widetilde w^T\widetilde x 2 y w T x 非正,所以範數平方每次更新至多增加 R 2 R^2 R 2 ,即 ∥ w ~ T ∥ ≤ R T \|\widetilde w_T\|\le R\sqrt T ∥ w T ∥ ≤ R T 。Cauchy–Schwarz 在 u u u 為單位向量時把兩者連起來:投影不能超過範數。線性的下界不可能長期低於平方根的上界,這就迫使 T ≤ ( R / γ ) 2 T\le(R/\gamma)^2 T ≤ ( R / γ ) 2 。
每個假設各有作用。取 u u u 為單位向量,才能把 γ \gamma γ 與 R R R 比較;把 u u u 重新縮放,只會縮放 γ \gamma γ ,數據本身不變。交叉項的符號正是用到「只在分錯時更新」之處。u u u 的存在就是可分假設:沒有它就不存在 γ \gamma γ ,論證無從收尾。
例題:上界與實際追蹤
一維正類點為 x = 2 x=2 x = 2 ,負類點為 x = 0 x=0 x = 0 。增廣分隔向量 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 對兩筆觀察的有符號分數均為 1,範數為 2 \sqrt2 2 ,故其單位正規化的間隔是 γ = 1 / 2 \gamma=1/\sqrt2 γ = 1/ 2 。增廣輸入範數為 5 \sqrt5 5 和 1,取 R = 5 R=\sqrt5 R = 5 ;定理給出至多 ( 5 / ( 1 / 2 ) ) 2 = 10 (\sqrt5/(1/\sqrt2))^2=10 ( 5 / ( 1/ 2 ) ) 2 = 10 次更新。
反覆按正類、負類次序處理。從 ( w , b ) = ( 0 , 0 ) (w,b)=(0,0) ( w , b ) = ( 0 , 0 ) 開始,正類分數為零,更新成 ( 2 , 1 ) (2,1) ( 2 , 1 ) ;負類分數為 1,故加上 − ( 0 , 1 ) -(0,1) − ( 0 , 1 ) 得 ( 2 , 0 ) (2,0) ( 2 , 0 ) 。下一輪正類分數為 4,不更新;負類分數為零,更新成 ( 2 , − 1 ) (2,-1) ( 2 , − 1 ) 。此時兩個有符號分數都為正:正類為 3,負類為 1。本次共更新三次,遠低於上界;若算法不在零分數更新,這條追蹤便不同,因此慣例是題目的一部分。
可分假設不能省略。
反例模式
沒有分隔向量時的錯誤次數上界 有人以為感知器在任何有限訓練集上都會停止。取單一輸入 x = 1 x=1 x = 1 ,增廣為 x ~ = ( 1 , 1 ) \widetilde x=(1,1) x = ( 1 , 1 ) ,它出現兩次,一次標籤為 + 1 +1 + 1 ,一次為 − 1 -1 − 1 。此時不存在分隔向量。從 w ~ = 0 \widetilde w=0 w = 0 開始,先處理 + 1 +1 + 1 的副本:分數為 0 0 0 ,規則更新成 w ~ = ( 1 , 1 ) \widetilde w=(1,1) w = ( 1 , 1 ) 。− 1 -1 − 1 的副本有 y w ~ T x ~ = − 2 ≤ 0 y\widetilde w^T\widetilde x=-2\le0 y w T x = − 2 ≤ 0 ,故更新成 w ~ = ( 1 , 1 ) − ( 1 , 1 ) = 0 \widetilde w=(1,1)-(1,1)=0 w = ( 1 , 1 ) − ( 1 , 1 ) = 0 。一輪之後參數回到 0 0 0 ,同樣的兩次更新永遠重複。上界 ( R / γ ) 2 (R/\gamma)^2 ( R / γ ) 2 不適用,因為不存在 γ > 0 \gamma>0 γ > 0 。補救辦法是加上可分假設,或改用能容許矛盾標籤的其他算法或損失,例如軟間隔目標。
對偶證書從哪裏來
證書要有用,必須清楚其不等式。對硬間隔約束取乘子 α i ≥ 0 \alpha_i\ge0 α i ≥ 0 ,構造
L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i α i ( 1 − y i ( w T x i + b ) ) . L(w,b,\alpha)=\frac12\|w\|^2+\sum_i\alpha_i\bigl(1-y_i(w^Tx_i+b)\bigr). L ( w , b , α ) = 2 1 ∥ w ∥ 2 + i ∑ α i ( 1 − y i ( w T x i + b ) ) .
在任意可行 ( w , b ) (w,b) ( w , b ) 下,每個括號均非正,故 L ( w , b , α ) ≤ 1 2 ∥ w ∥ 2 L(w,b,\alpha)\le\tfrac12\|w\|^2 L ( w , b , α ) ≤ 2 1 ∥ w ∥ 2 。對所有 w , b w,b w , b 取下確界,所得因而是每個可行原始目標的下界。b b b 的係數是 − ∑ i α i y i -\sum\limits_i\alpha_i y_i − i ∑ α i y i ;若該和不為零,對 b b b 取下確界便無下界。在零和約束下,對 w w w 最小化二次式得到 w = ∑ i α i y i x i w=\sum\limits_i\alpha_i y_i x_i w = i ∑ α i y i x i 及對偶值
g ( α ) = ∑ i α i − 1 2 ∥ ∑ i α i y i x i ∥ 2 . g(\alpha)=\sum_i\alpha_i-\frac12\left\|\sum_i\alpha_i y_i x_i\right\|^2. g ( α ) = i ∑ α i − 2 1 i ∑ α i y i x i 2 .
因此任何非負且符合零和條件的乘子都給出有效下界。若一個明確可行的原始點達到相同值,就沒有可行點更好:僅用弱對偶已足以證明最優。例題一的兩值均為 1 / 8 1/8 1/8 。互補鬆弛性說明最優時哪些約束可有正乘子,但在退化解中,位於間隔上的觀察也可有零乘子。此公式的 ∥ w ∥ \|w\| ∥ w ∥ 不包括偏置 b b b ;若另一模型對偏置正則化,其對偶會不同。
設 α i ≥ 0 \alpha_i\ge0 α i ≥ 0 且 ∑ i α i y i = 0 \sum\limits_i\alpha_iy_i=0 i ∑ α i y i = 0 ,並令 g ( α ) = ∑ i α i − 1 2 ∥ ∑ i α i y i x i ∥ 2 g(\alpha)=\sum\limits_i\alpha_i-\tfrac12\bigl\|\sum\limits_i\alpha_iy_ix_i\bigr\|^2 g ( α ) = i ∑ α i − 2 1 i ∑ α i y i x i 2 。硬間隔問題的每個可行 ( w , b ) (w,b) ( w , b ) 都滿足 1 2 ∥ w ∥ 2 ≥ g ( α ) \tfrac12\|w\|^2\ge g(\alpha) 2 1 ∥ w ∥ 2 ≥ g ( α ) 。若某個可行 ( w , b ) (w,b) ( w , b ) 使 1 2 ∥ w ∥ 2 = g ( α ) \tfrac12\|w\|^2=g(\alpha) 2 1 ∥ w ∥ 2 = g ( α ) ,則它是最優解。
記 v = ∑ i α i y i x i v=\sum\limits_i\alpha_iy_ix_i v = i ∑ α i y i x i 。對可行 ( w , b ) (w,b) ( w , b ) ,每個括號 1 − y i ( w T x i + b ) 1-y_i(w^Tx_i+b) 1 − y i ( w T x i + b ) 均非正,故 1 2 ∥ w ∥ 2 ≥ L ( w , b , α ) \tfrac12\|w\|^2\ge L(w,b,\alpha) 2 1 ∥ w ∥ 2 ≥ L ( w , b , α ) 。展開 L L L ,並用 ∑ i α i y i = 0 \sum\limits_i\alpha_iy_i=0 i ∑ α i y i = 0 消去 b b b ,
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − w T v + ∑ i α i = 1 2 ∥ w − v ∥ 2 − 1 2 ∥ v ∥ 2 + ∑ i α i ≥ g ( α ) . L(w,b,\alpha)=\tfrac12\|w\|^2-w^Tv+\sum_i\alpha_i=\tfrac12\|w-v\|^2-\tfrac12\|v\|^2+\sum_i\alpha_i\ge g(\alpha). L ( w , b , α ) = 2 1 ∥ w ∥ 2 − w T v + i ∑ α i = 2 1 ∥ w − v ∥ 2 − 2 1 ∥ v ∥ 2 + i ∑ α i ≥ g ( α ) . 若某個可行點達到 g ( α ) g(\alpha) g ( α ) ,則每個可行點的目標值都至少是該值,所以它是最優解。
概念視角 幾何
最大間隔即兩類之間最接近的一對點 數據嚴格可分時,兩個支撐平面之間的最優間距 2 / ∥ w ∥ 2/\|w\| 2/∥ w ∥ ,等於兩類凸包之間的歐氏距離(Euclidean distance),而邊界是凸包上最接近一對點的垂直平分線。對偶乘子就是這兩點的權重:∑ α i y i = 0 \sum\alpha_iy_i=0 ∑ α i y i = 0 使正類與負類的權重總和相等,w w w 則與兩點之差成比例。在兩個觀察點的例子中,兩個凸包就是點 0 0 0 與點 4 4 4 ,距離 4 = 2 / ∥ w ∥ 4=2/\|w\| 4 = 2/∥ w ∥ 。
展開對偶範數會出現 x i T x j x_i^Tx_j x i T x j 。以有效核函數替換這些項,相當於使用特徵向量 ϕ ( x i ) \phi(x_i) ϕ ( x i ) 作同一構造。這不代表每個看似對稱的公式都有效,也不代表只在一個訓練集檢查 Gram 矩陣便能證明整個定義域有效;它亦不會自動選擇特徵尺度或超參數。模型選擇應只用訓練數據擬合學得的預處理,選設定時不查最終測試標籤,然後在保留數據評估選定流程。完美擬合訓練觀察是關於這些觀察的證據,本身不保證泛化。
間隔分數亦不能自動當成已校準概率。其符號在選定閾值下提供決策,大小則依慣例量度正規化或未正規化距離;兩者都不表示分數為 2 就代表正類概率 88%。若需要概率,須另行指定校準程序並適當驗證。正則化參數 C C C 影響範數與訓練損失的取捨,但其合適值取決於損失慣例、特徵尺度及任務。每個特徵乘 2 卻不調整模型,會改變固定 w w w 的意義,也可能改變擬合最優解。
在線性例子中,把 ( w , b ) = ( 1 / 2 , − 1 ) (w,b)=(1/2,-1) ( w , b ) = ( 1/2 , − 1 ) 乘 2,邊界仍為 x = 2 x=2 x = 2 、符號不變;函數間隔變為 2,但範數也加倍,故幾何間隔仍為 2。縮放後仍可行,但正則項由 1 / 8 1/8 1/8 增至 1 / 2 1/2 1/2 ,所以不是硬間隔最小解。此檢查把正規化、幾何和優化連起來,並沒有把分數當成概率。
練習
快速檢查
(一維中,觀察 x = 3 x=3 x = 3 、y = + 1 y=+1 y = + 1 由 ( w , b ) = ( 2 , − 2 ) (w,b)=(2,-2) ( w , b ) = ( 2 , − 2 ) 評分。求它的函數間隔與幾何間隔,並求 ( 4 , − 4 ) (4,-4) ( 4 , − 4 ) 的這兩個間隔。)
用 f ( x ) = w x + b f(x)=wx+b f ( x ) = w x + b ,幾何間隔再除以 ∣ w ∣ |w| ∣ w ∣ 。
解答 · 答案 對 ( 2 , − 2 ) (2,-2) ( 2 , − 2 ) :f ( 3 ) = 4 f(3)=4 f ( 3 ) = 4 ,所以函數間隔為 4 4 4 ,幾何間隔為 4 / 2 = 2 4/2=2 4/2 = 2 。對 ( 4 , − 4 ) (4,-4) ( 4 , − 4 ) :f ( 3 ) = 8 f(3)=8 f ( 3 ) = 8 ,函數間隔為 8 8 8 ,幾何間隔為 8 / 4 = 2 8/4=2 8/4 = 2 。重新縮放改變函數間隔,但不改變幾何間隔。
快速檢查
(某分數為 f ( x ) = 0.3 f(x)=0.3 f ( x ) = 0.3 。分別在 y = + 1 y=+1 y = + 1 與 y = − 1 y=-1 y = − 1 時求鉸鏈損失。)
用 max ( 0 , 1 − y f ( x ) ) \max(0,1-yf(x)) max ( 0 , 1 − y f ( x )) 。
解答 · 答案 y = + 1 y=+1 y = + 1 :max ( 0 , 1 − 0.3 ) = 0.7 \max(0,1-0.3)=0.7 max ( 0 , 1 − 0.3 ) = 0.7 。y = − 1 y=-1 y = − 1 :y f ( x ) = − 0.3 yf(x)=-0.3 y f ( x ) = − 0.3 ,損失為 max ( 0 , 1.3 ) = 1.3 \max(0,1.3)=1.3 max ( 0 , 1.3 ) = 1.3 。對正確標籤,小的正分數仍在間隔之內,損失 0.7 0.7 0.7 ;標籤錯了,損失超過 1 1 1 。
快速檢查
(判斷 K ( x , z ) = x z K(x,z)=xz K ( x , z ) = x z 與 K ′ ( x , z ) = − x z K'(x,z)=-xz K ′ ( x , z ) = − x z 在 R \mathbb R R 上是否為有效核函數。)
為其中一個找特徵映射,為另一個找單點 Gram 矩陣。
解答 · 答案 K ( x , z ) = x z K(x,z)=xz K ( x , z ) = x z 是核函數,特徵映射為 ϕ ( x ) = x \phi(x)=x ϕ ( x ) = x 。對 K ′ K' K ′ ,在 x = 1 x=1 x = 1 的單點 Gram 矩陣為 ( − 1 ) (-1) ( − 1 ) ,取 c = 1 c=1 c = 1 得 c T G c = − 1 < 0 c^TGc=-1<0 c T G c = − 1 < 0 ,所以 K ′ K' K ′ 不是核函數。
快速檢查
(觀察:x = 0 x=0 x = 0 、y = − 1 y=-1 y = − 1 與 x = 2 x=2 x = 2 、y = + 1 y=+1 y = + 1 。求硬間隔解,並說明 α = ( 1 / 2 , 1 / 2 ) \alpha=(1/2,1/2) α = ( 1/2 , 1/2 ) 可作為其最優性的證書。)
先把兩個約束相加來界定 w w w ,再計算 g ( α ) g(\alpha) g ( α ) 。
解答 · 答案 約束為 − b ≥ 1 -b\ge1 − b ≥ 1 與 2 w + b ≥ 1 2w+b\ge1 2 w + b ≥ 1 。相加得 2 w ≥ 2 2w\ge2 2 w ≥ 2 ,故 w ≥ 1 w\ge1 w ≥ 1 ,而 ( w , b ) = ( 1 , − 1 ) (w,b)=(1,-1) ( w , b ) = ( 1 , − 1 ) 可行,目標為 1 2 \tfrac12 2 1 。對 α = ( 1 / 2 , 1 / 2 ) \alpha=(1/2,1/2) α = ( 1/2 , 1/2 ) :∑ α i y i = − 1 2 + 1 2 = 0 \sum\alpha_iy_i=-\tfrac12+\tfrac12=0 ∑ α i y i = − 2 1 + 2 1 = 0 ,∑ α i y i x i = 1 2 ⋅ 2 = 1 \sum\alpha_iy_ix_i=\tfrac12\cdot2=1 ∑ α i y i x i = 2 1 ⋅ 2 = 1 ,故 g ( α ) = 1 − 1 2 ⋅ 1 2 = 1 2 g(\alpha)=1-\tfrac12\cdot1^2=\tfrac12 g ( α ) = 1 − 2 1 ⋅ 1 2 = 2 1 。這等於原始目標,所以 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 最優。