動機
平方損失要求預測近似數值標籤,分類的直接目標卻是符號正確並遠離決策邊界。鉸鏈損失量度未達指定帶符號間隔的程度。它凸但在間隔分界不可微,所以不能只改標籤向量便沿用嶺迴歸的法方程。
前面的 RKHS 構造已提供函數空間及有界評估。本節在此基礎上證明分類的存在性、有限表示、對偶及支持係數意義,不重做平方損失推導。須分清受正則化的函數、不受懲罰的截距,以及用來表示函數的係數:三者的唯一性並不相同。
軟間隔亦容許互相矛盾的觀測。最優化問題仍可解,但相同輸入而標籤相反,並不會因求解定理而變得可分辨。完整推導應同時解釋成功的分離例子和這項限制。
定義
設 k 為實對稱半正定核,RKHS 為 H。給定非空有限樣本 (xi,yi)i=1n,其中 yi∈{−1,1}。令 ki=k(xi,⋅)、Kij=k(xi,xj)、Y=diag(yi),並使用前一核空間單元已建立的再生等式與正交投影結果。
分數為 f(x)+b,其中 f∈H,截距 b 是參與最優化而不受懲罰的變量;平方範數懲罰只作用於函數。分數非負時預測正類,否則負類,零分數約定不改變訓練目標。帶符號間隔為 mi=yi(f(xi)+b),鉸鏈為 h(m)=max(0,1−m)。
固定 C>0,軟間隔原問題為
f,b,ξmin P(f,b,ξ)=21∥f∥H2+Ci∑ξi,mi+ξi≥1,ξi≥0.
分數固定時,最佳鬆弛量為 ξi=h(mi),因增加它有正成本。等價目標是 J(f,b)=∥f∥2/2+Ci∑h(mi)。此處用損失總和;若從平均損失 λ∥f∥2/2+n−1i∑h(mi) 出發,乘以 1/λ 後得到 C=1/(nλ),其中 λ>0。
令 V=span{k1,…,kn}。表示 f=i∑ciki 的訓練值為 Kc,函數範數平方為 cTKc,一般不是 ∥c∥22。奇異 Gram 矩陣可令不同係數表示同一函數;正則化函數並不等於懲罰任意係數長度。
定理 / 命題
定理 11.1.2
(鉸鏈損失的有限表示及原問題取得)
原問題的最小值可取得。每個最小化函數均在 V 內,而且所有最優三元組的函數 f 相同。截距 b 與係數表示則未必唯一。不要求 K 嚴格正定,也不要求標籤可分離。
對偶是可取得最大值的凹最優化問題
αmax D(α)=1Tα−21αTYKYα,0≤αi≤C,yTα=0.其最優值等於原問題最小值。原可行三元組與對偶可行向量同時最優,當且僅當
f=i∑αiyiki,αi(mi+ξi−1)=0,(C−αi)ξi=0對每個下標成立。這是 KKT 的駐點與互補部分;原、對偶可行性也不可省略。
對偶等式來自最優化不受懲罰的截距,不是所有核分類器自動具有的性質。先證明主結果,稍後再區分無截距和受懲罰截距。
證明思路
正交分解 f=v+r,v∈V、r⊥V。再生性給 r(xi)=0,而 ∥f∥2=∥v∥2+∥r∥2。移去非零餘項不改間隔卻嚴格降低目標,所以一旦最小值取得,每個最優函數都在有限維 V 內。核生成元相依不妨礙 V 本身作為有限維內積空間。
在有界原目標下水平集中,函數範數及每個非負鬆弛量均有界,再生評估遂界住所有訓練值。若正負標籤都出現,正類約束給截距下界,負類約束給上界,故極小化序列在 V×R×Rn 有收斂子列,閉約束與連續性給出最小點。若只有同一標籤 y,取 f=0,b=y,ξ=0 已達全域下界零。若有兩個最優函數不同,平均其可行三元組,平方範數嚴格下降而鬆弛成本線性,與最優矛盾。因此函數唯一,但此論證沒有保證截距唯一。
對 1−ξi−mi≤0 配非負乘子 αi,對 −ξi≤0 配 βi,得到
21∥f∥2+Ci∑ξi+i∑αi(1−ξi−yi(f(xi)+b))−i∑βiξi.對函數取下確界的點是 fα=i∑αiyiki。對無限制截距,下確界有限當且僅當 yTα=0;對無限制鬆弛變量,有限當且僅當 C−αi−βi=0。消去 β 得盒形限制和對偶。半正定性保證凹二次目標;盒形切片非空且緊緻,所以最大值取得。
有限維約化後,f=0,b=0,ξi=2 使兩組不等式都嚴格成立,正是此凸問題的 Slater 條件。但我們不只引用一般強對偶定理,而直接構造最優乘子。
在 J 的最小點 (f∗,b∗),令 A 是可能鉸鏈權重的盒:mi<1 時固定 αi=C;mi>1 時固定零;mi=1 時可在 [0,C]。在 V×R 定義緊緻凸集
S={(f∗−i∑αiyiki, −i∑αiyi):α∈A}.每個元素都是由純量鉸鏈支撐線相加所得的次梯度。更具體地,任意方向 d 的單側導數等於 s∈Smax⟨s,d⟩:非折點的斜率固定,折點則取兩側線性斜率的較大值;各區間獨立,可先各取最大再相加。
若零不在 S,取最小範數點 s0=0。沿集內線段微分距離平方得 ⟨s−s0,s0⟩≥0。方向 d=−s0 的最大方向導數遂不超過 −∥s0∥2<0,與最小性矛盾。因此零在 S,同時給函數駐點及 yTα=0。取最佳鉸鏈鬆弛量,A 的定義便給全部互補式,包括間隔恰為一的情況。
最後,對任意原、對偶可行對直接展開
P(f,b,ξ)−D(α)=21∥f−fα∥2+i∑αi(mi+ξi−1)+i∑(C−αi)ξi.各項非負。已構造的乘子令每項為零,證明兩個已取得最優值相等。反過來,任何最優可行對的間隙為零,各非負項也必為零,故證書既充分又必要。這沒有倒置 K,也沒有假設鉸鏈可微。
證明透視
強對偶不只是形式計算
論證由三個事實支撐。有限表示一步只用到再生性質:r⊥V 表示 r(xi)=⟨r,ki⟩=0,所以餘項對每個間隔都不可見,只徒增代價。存在性需要兩種標籤同時出現,才能從兩邊界住不受懲罰的截距;這正是單一標籤情況要另行處理的原因。強對偶的關鍵一步是幾何的:每個間隔各自提供一段權重區間,所以鉸鏈次梯度集合 S 緊緻且凸;若 0∈/S,其最小範數點給出嚴格下降方向,與最優性矛盾。嚴格可行性顯示 Slater 理論適用,但證明並不依賴它。間隙等式完成論證:它把 P−D 寫成三個非負項之和,所以令三項都為零的乘子給出相等的值,而任何零間隙的可行對都必須滿足全部 KKT 條件。單寫拉格朗日(Lagrange)函數,只得到候選對偶及弱對偶。
對選定最優對偶向量,正乘子的觀測稱為支持向量。證書給 αi=0⇒mi≥1、0<αi<C⇒mi=1、αi=C⇒mi≤1。反之,間隔嚴格大於一必有零乘子,小於一必到上界;恰等於一則容許不同盒形狀態。正間隔保證分類正確,即使小於一;負間隔保證錯誤。間隔為零時依正類平手約定,正標籤正確,負標籤錯誤。
例題詳解
取線性核 k(x,z)=xz,輸入 (−1,1)、標籤 (−1,1),則 K=(1−1−11),YKY 全一。等式約束給 α1=α2=t,對偶為區間 [0,C] 上的 2t−2t2。取 C=1/4,最大點為 t=1/4,回復 f(x)=x/2。最優截距集合恰為 [−1/2,1/2],因鉸鏈總和正好在此區間為一。選 b=0,兩個間隔、鬆弛量均為二分之一,原與對偶值均為 3/8。此選擇乃至全部 ∣b∣<1/2 下,兩點雖有正鉸鏈損失和上界乘子,分類仍正確。取 b=1/2 時負類點分數為零,依本節平手約定便分類錯誤。
例題 11.1.5
(奇異 Gram 與不唯一的支持係數)
相同核取輸入 (1,1,−1)、標籤 (1,1,−1)、C=1。K=vvT,其中 v=(1,1,−1)T,YKY 是三乘三全一矩陣。可行性給 α3=α1+α2=t≤1,目標仍為 2t−2t2,在 t=1/2 最大。任何非負分拆 α1+α2=1/2 都最優,皆給 f(x)=x,b=0、零鬆弛與值二分之一。重複點即使位於間隔邊界,也可有零乘子。一般表示係數 (1,0,0)、(0,1,0) 亦代表相同函數;這是任意係數冗餘,須與受限制對偶係數分開。
線性核取兩個零輸入、相反標籤,則 K 為零,所有 RKHS 函數在兩個觀測都為零,最優函數是零。任意 b∈[−1,1] 都最小化 C[h(b)+h(−b)]=2C,鬆弛量為 (1−b,1+b)。對偶要求兩乘子相等,於 α1=α2=C 得最大值 2C。沒有嚴格在盒內的係數可恢復唯一截距。這是合法不唯一,不是矩陣求逆失敗或原問題不可行。
概念視角結構
三種截距約定對應三種對偶
固定 b=0 會完全移去對偶等式。若最優化截距卻加 γb2/2、γ>0,則 b=(yTα)/γ,對偶多出 −(yTα)2/(2γ),不再有等式限制。只有主模型的不受懲罰截距才要求 yTα=0。把常數特徵當成普通受懲罰 RKHS 座標,會改變模型,除非明確調整懲罰約定。
若有嚴格盒內係數,由間隔一可得 b=yi−f(xi)。沒有這種點時,應用其餘 KKT 不等式求容許截距範圍,不可除奇異矩陣或假造一個自由支持點。乘子不唯一亦使支持向量的選定隨最優對偶表示而變,不必對應唯一不可替代的觀測子集。
常見錯誤
第一個錯誤關乎核本身:對偶的推導在一個確切位置用到半正定性。
反例模式
看似正的相似度可以破壞凸性
矩陣 K=(1221) 對稱且元素全正,但 (1,−1)K(1,−1)T=−2,不可能是 RKHS 的 Gram 矩陣。標籤 (1,−1) 下,可行線 α=(t,t) 會給 2t+t2,反成凸目標。把這種相似度代入公式,不能保留已證的核分類問題。需要半正定性,不只是對稱或元素為正。
駐點條件是函數等式 f=i∑αiyiki。以 f 的係數向量 c 表示,它是 Kc=KYα;當 K 奇異時,不能推出 c=Yα。在三點例子中,c=(1,0,0)T 與 Yα=(a,1/2−a,−1/2)T 都滿足 Kc=v=KYα,並表示同一個 f(x)=x。
乘子 αi=0 不代表嚴格大間隔,αi=C 也不代表分類錯誤。在三點例子中,恰在間隔上的重複點可以有 αi=0;在第一個例子中,兩點都有 αi=C,但當 ∣b∣<1/2 時都分類正確。
二次規劃最優只證明指定訓練問題的最優,並非總體準確率。核選擇、類別權重、數值容差與統計誤差界仍需額外分析。
總結
鉸鏈正則化即使在奇異核及矛盾標籤下,仍取得有限表示且有唯一 RKHS 函數。截距約定決定對偶限制。有限鉸鏈斜率幾何構造乘子,非負間隙證明強對偶與 KKT。精確 Gram 例子說明函數、截距、一般係數與支持乘子須分開理解。
練習
快速檢查
(第一個 Gram 例子改為 C=1,求對偶、函數、截距、鬆弛及共同值。為何係數此時嚴格在盒內?)
先不理上界,最大化 2t−2t2。
解答 · 答案
最大點為 t=1/2<C,故 f(x)=x,自由係數的間隔式給 b=0,兩鬆弛均零,共同值二分之一。單位間隔可達而不必停在鉸鏈分界之下;嚴格盒內的精確結論由已解對偶與 KKT 得出。
快速檢查
(寫三點例子的全部最優 α,選兩個不同向量並指出各自的支持向量。)
利用 α3=α1+α2。
解答 · 答案
全族為 (a,1/2−a,1/2),0≤a≤1/2。取零時支持下標二、三;取二分之一時是一、三。函數與所有間隔相同,個別重複邊界點可有零乘子,因此支持集合不唯一。
快速檢查
(推導加 γb2/2 後的對偶項及截距,證明可在無截距對偶中以 k+1/γ 替換原核。)
解答 · 答案
最小化 γb2/2−byTα 得 b=yTα/γ,最小值 −(yTα)2/(2γ),不要求對偶等式。新二次項是 −αTY(K+γ−111T)Yα/2,正是增廣核的無截距對偶。常數特徵此時受懲罰,與主模型不同。
快速檢查
(原、對偶可行對的間隙至多 ε,證明原問題次優度至多 ε。這可單獨控制總體分類誤差或任意表示係數間的歐氏(Euclidean)距離嗎?)
解答 · 答案
弱對偶給 D(α)≤P∗≤P,因此 P−P∗≤P−D≤ε。以最優對偶證書代入間隙等式,亦得 ∥f−f∗∥H≤2ε。這些控制指定訓練問題的最優化誤差,總體誤差仍需統計假設。當 K 奇異時,零係數方向可有任意大歐氏長度而代表同一函數,所以不能控制這類表示間距離;K 正定時則沒有此零空間障礙。