規則需要處理平分的約定
考慮有限且非空的標記向量集合 ,其中 、、。由 開始。每次輸入一個例子時,計算帶標記分數 。若分數不大於零,便更新
否則保持 不變。特別地,分數為零也觸發更新。我們計算更新次數,包括零分平手;視乎分類器另行採用的平手規則,它們未必全都是嚴格意義上的分類錯誤。
這是齊次規則:決策邊界通過原點。對仿射分數 ,附加常數座標,令 、,便可在增廣向量上使用相同規則。半徑及間隔必須在增廣空間計算,不能只用原特徵的範數。
常見錯誤
(在原座標中尋找間隔)
取一維數據: 標記為 , 標記為 。對齊次分數 ,點 的帶標記分數對每個 都是 ,所以在原座標中不存在正間隔。增廣為 和 後,單位向量 給出的帶標記間隔都是 。間隔假設必須在實際運行規則的空間中檢驗。
對同一批更新的兩個估計
定理 5.1.1
(感知器的有限更新次數界)
假設存在常數 、 及單位向量 ,使每個例子都滿足
由 開始,每當輸入的帶標記分數不大於零就更新。則不論輸入次序如何,更新總次數 滿足
若有限數據集按完整輪次反覆輸入,則至多經過 輪便會出現沒有更新的一輪,此時每個訓練例子的帶標記分數都嚴格為正。
對有限數據,有限的 必定存在;實質的假設是算法實際使用的數據具有嚴格為正的間隔。
證明
(線性的進展對平方根的增長)
令 為第 次更新剛完成後的權重,;被略過的輸入不使 增加。對例子 作更新時,
由歸納得 。另一方面,更新條件給出 ,所以
於是 。由柯西—施瓦茲(Cauchy–Schwarz)不等式及 ,得 。當 ,兩邊相除便得 。
關於輪數:更新次數至多為 ,而最後一輪之前的每一輪至少含一次更新,所以至多需要 輪。在沒有更新的一輪中權重保持不變,所以每個例子對該權重的帶標記分數都為正。
證明透視
平手約定與零起點用在哪裏
兩個估計需要規則的不同特徵。下界只需要間隔假設,每次更新使用一次。上界需要更新條件 ,而「不大於」這幾個字很重要:由於 ,第一個分數恰好是零,若規則只在分數嚴格為負時才更新,權重便永遠離不開原點。起點 使兩個界都從零開始,因而可以互相比較。證明得以完結,是因為隨 線性增長的量被夾在按 增長的量之下。這個界計算的是更新總次數,不是輪數或計算時間,也沒有說明在新數據上的表現。
若分離向量 未經正規化,但滿足 ,取 及 ,所得的界為 。間隔很小時,這個保證就很弱;界也不一定取得。
例題
例題 5.1.2
(一個二維追蹤)
使用有次序的齊次例子
由 開始,第一個分數為零,所以 變為 。第二個分數也為零,所以負標記把 更新為 。第三個帶標記分數是 ,不更新。再多一輪,帶標記分數為 ,沒有更新。
取 ,帶標記間隔分別為 、 和 。最大的輸入範數為 ,所以 給出 次更新的上界。追蹤中用了 次更新;定理給的是上界,不是精確預測。
例題 5.1.3
(未經正規化的分離向量)
取例子 與 ,以及分離向量 。帶標記分數 分別為 和 ,所以 。又 、,所以界為 ,即至多 次更新。實際運行: 時第一個例子的分數是 ,所以 。第二個例子的分數是 ,所以 。下一輪的分數為 和 ,不再更新。實際次數為 。
例題 5.1.4
(為偏置增廣)
取一維點 (標記 )和 (標記 ),使用仿射分數。增廣為 與 ,並按此次序輸入。由 開始,第一個分數是 ,所以 。第二個分數是 ,所以 。下一輪中第一個分數又是 ,所以 ;之後兩個分數為 和 ,不再更新。共發生三次更新。取 ,兩個帶標記間隔都是 ,最大增廣範數為 ,所以界為 。若只用原特徵半徑 ,便會漏掉常數座標。
沒有可分性時可能發生甚麼
反例模式
輸入有界並不保證終止
命題:只要所有訓練向量的範數至多為 ,感知器便只作有限次更新。取兩個例子 與 ,此時 。由 開始,第一個分數是 ,所以 。第二個例子的帶標記分數是 ,所以 。權重回到起點,因此再輸入這兩個例子,會永遠重複同樣的兩次更新。沒有單位向量 使兩個例子都有正間隔,因為它們的帶標記間隔是 和 。定理的間隔假設不能省略,只知道訓練向量的範數有有限上界並不足夠。退化的版本是數據集只含 、標記為 :每次輸入都計一次更新,而零向量使 保持不變。
習題
快速檢查
(若單位分離向量的間隔至少為 ,所有輸入範數至多為 ,定理給出多少次更新的界?若停止規則要求完整一輪沒有更新,可得甚麼輪數界?)
把 、 代入界。
解答 · 答案
最多 次更新。若在首次完整無更新輪後停止,最多需要 輪:此前每輪至少有一次更新。
快速檢查
(在二維追蹤中,計算第二次更新後三個例子的帶標記分數。為何下一次完整輪不會更新?)
使用 。
解答 · 答案
分數為 。它們均嚴格為正,所以所指定的非正分數更新規則不會更新。
快速檢查
(分離向量 的範數為 ,且每個例子的帶標記分數至少為 。若 ,求單位向量 的間隔及更新次數界。)
把 除以它的範數。
解答 · 答案
單位分離向量 的間隔至少是 ,故最多更新 次。