線性分類器按輸入落在超平面的哪一邊來標記它。Fisher 判別一節以類均值與散佈矩陣構造了這樣的超平面;嶺回歸一節則以最小二乘擬合線性分數。本節處理另外三種選取超平面的方法,各由不同的損失定義:只對錯誤作出反應的感知機;以最大似然擬合概率模型的邏輯回歸;以及選出離數據最遠的分離超平面的最大間隔分類器。三者都由同一個量來組織,那就是間隔。
分數與間隔
定義 29.1.1
(線性分類器、函數間隔與幾何間隔)
設輸入為 ,標籤為 。線性分類器的參數為 ()與 ,分數為 ,預測為 。對帶標籤的樣本 ,函數間隔為 ,它為正當且僅當樣本被嚴格正確分類;幾何間隔為 。集合 是決策超平面。
定理 29.1.2
(間隔的幾何意義)
到超平面 的歐氏距離(Euclidean distance)等於 。因此幾何間隔就是樣本到超平面的有號距離,在正確一側為正。把 乘以正常數,它不變。
證明
(到超平面的距離)
點 滿足 ,所以在超平面上,且 。對超平面上任一點 ,,由柯西–施瓦茨(Cauchy–Schwarz)不等式得 ,所以超平面上每一點與 的距離都不小於此值。把 乘以 ,分子與分母同乘 。
相反,函數間隔可以靠縮放變得任意大,所以談論間隔時必須說明指哪一種。在感知機的分析中,我們把偏置併入:把每個輸入擴充為 ,參數擴充為 ,使 。
感知機
感知機從 開始,按固定次序反覆掃描樣本。每當某個樣本有 (即錯誤,分數為零也算錯誤),就更新 。完整掃描一遍而沒有錯誤時停止。
概念視角分析
把感知機看成次梯度的一步
設間隔 ,考慮損失 。當 時,它對 的梯度為 ;在 處, 是一個次梯度。沿其反方向走單位步長,恰好就是感知機的更新;當 時損失是平的,所以不更新。
定理 29.1.3
(感知機錯誤次數上界)
設對所有 有 ,並存在單位向量 與 ,使 對所有 成立。則對任何掃描次序,感知機至多更新 次,因此會終止並給出一個分離超平面。
證明
(對齊量線性增長,範數平方根增長)
設 為更新 次後的參數向量,。若第 次更新用的是 ,則 ,所以 。又因為更新由 觸發,
所以 。由柯西–施瓦茨不等式,,得 。每一遍未終止的掃描至少有一次更新,所以掃描遍數也是有限的。
證明透視
線性增長對平方根增長
證明沿著更新序列追蹤兩個量。對齊量 每次更新至少增加 ;間隔假設只在這裏用到。範數平方 每次更新至多增加 ;感知機的更新規則只在這裏用到,因為交叉項 恰好在該樣本是錯誤時不為正。最後的柯西–施瓦茨一步用到 ,把線性下界 與平方根上界 相比,兩者只在 時相容。從 開始,使兩個界都從零起步。若對已正確分類的樣本也作更新,交叉項便可能為正,範數的界即告失效;若容許 ,下界就甚麼也說明不了。
這個上界不依賴樣本數目或維度。若數據不是線性可分,就不存在這樣的 ,算法永不停止。
反例模式
不可分數據:感知機會循環
人們很容易以為感知機一定會停止,因為每次更新都糾正了觸發它的樣本。取四點:、 標籤為 ,、 標籤為 。沒有超平面能嚴格分開它們:若四個 都為正,則兩個正例給出 ,兩個負例給出 ,互相矛盾。算法只會在某一遍掃描中每個樣本都有 時停止,即找到嚴格分離超平面,所以這裏永遠不會停止。具體地,取擴充輸入 ,按此次序由 掃描,四次更新依次得到 、、,然後又回到 ,迭代點永遠重複。修正後的說法就是上面的定理:在線性可分並有正間隔 時,才保證終止。
邏輯回歸
邏輯回歸把 建模為 ,其中 。由於 ,對 有 。因此訓練集的負對數似然為
定理 29.1.4
(邏輯損失的梯度與凸性)
,。因此
所以 是凸函數,每個駐點都是全域極小點。若數據線性可分, 沒有極小點:當 時 ,而 處處為正。
導數由鏈式法則得到:,再微分一次得 。Hessian 公式用到 。每一項 都是半正定的,其係數為正。對可分數據, 每一項都有 ,故 ,但每個 ,所以下確界 永遠取不到。這就是為何在可分數據上不加正則化的邏輯擬合會發散,也是為何要像嶺回歸那樣加入懲罰項。
最大間隔分類器
定義 29.1.5
(硬間隔分類器)
對兩種標籤都出現的線性可分數據,縮放參數使最接近的樣本函數間隔恰好為 。硬間隔問題為
滿足這些約束的 稱為可行。
定理 29.1.6
(硬間隔即最大的最小幾何間隔)
對兩種標籤都出現的線性可分數據,硬間隔問題有最優解,且其 唯一。最優超平面在所有分離超平面中擁有最大的最小幾何間隔,該間隔等於 。
證明
(最大化間隔就是最小化範數)
任何單位法向量為 、最小幾何間隔為 的分離超平面,都給出範數為 的可行對 ,所以可行集非空。反過來,可行的 必有 ,因為 會要求兩種標籤都有 ;它的最小幾何間隔至少是 。因此最大的最小幾何間隔,就是最小可行 的倒數。
使某個 令 可行的全部 ,是一個多面體的投影,故為非空閉凸集。 在其上嚴格凸,所以恰有一個範數最小的元素;再為它取一個可行的 。所得超平面的最小幾何間隔至少為 ,而任何超平面都不能超過這個值,所以間隔恰為 。
例題
例題 29.1.7
(追蹤感知機並核對上界)
取四點及標籤 、、、,擴充為 ,並按此次序掃描。從 開始。
- 點 1:,更新為 。
- 點 2:分數 ,不更新。
- 點 3:,更新為 。
- 點 4:,更新為 。
- 第二遍:點 1 的分數為 ;點 2 的分數為 ,更新為 ;點 3、4 的間隔都是 。
- 第三遍:所有間隔都等於 ,算法在共四次更新後停止。
對上界取 ,它在四點上的間隔都等於 ,所以 ,而 。於是 ,恰等於實際更新次數。
例題 29.1.8
(邏輯回歸的一步梯度)
取一維輸入 與 ,,。所有間隔為 ,,所以 。梯度為 。步長取 ,新參數為 。間隔變為 與 ,所以 ,有所下降。這一步以第一個樣本變差的間隔,換取第二個樣本好得多的間隔。固定步長一般不保證損失下降;此處損失恰好下降。
例題 29.1.9
(精確的硬間隔)
取 標籤 與 標籤 。約束為 與 。相加得 ,故 ,,在 、 時取等,此時兩個約束都取等號。間隔為 ,正是兩點距離 的一半,超平面為 。
常見錯誤與細節
常見錯誤
(必須說明是哪一種間隔)
函數間隔會隨縮放改變,只有幾何間隔才是距離。感知機上界用的是單位分離向量 與擴充輸入,所以 必須是包含常數 在內的擴充範數的上界。
常見錯誤
(分數為零也是錯誤)
感知機更新把分數為零也視為錯誤,所以從 開始時,第一個樣本必然觸發更新。
常見錯誤
(損失小或有分離解都不足夠)
邏輯損失是零一誤差的光滑替代,損失小並不表示錯誤率小,也不表示概率已經校準。感知機的解只是某個分離超平面,取決於掃描次序;最大間隔的解在 上則是唯一的。
練習
快速檢查
(設 ,。求 到超平面的距離,以及其標籤為 時的幾何間隔。)
先計算 。
解答 · 答案
,,所以距離為 。標籤為 時,幾何間隔為 ,樣本被錯誤分類。
快速檢查
(擴充輸入滿足 ,並有單位向量使 。給出感知機更新次數的上界。改變掃描次序,它會改變嗎?)
上界只涉及 與 。
解答 · 答案
。這個上界對任何掃描次序都成立,但實際更新次數與最終的超平面可以取決於次序。
快速檢查
(分別計算 與 時的 與 。)
利用 。
解答 · 答案
時,,。 時,,,所以 ,。
快速檢查
(點 標籤 ,點 標籤 。求硬間隔的 與幾何間隔。)
把兩個約束相加。
解答 · 答案
約束為 與 ,即 。相加得 ,故 ,最小範數在 、 取得,此時兩個約束都取等號。幾何間隔為 。