從錯誤中學習
在線學習器先看到一個輸入,預測標籤,然後在下一輪之前才看到正確標籤。感知器維持一個向量 ,並預測 的符號。標籤為 ,採用以下規則:由 開始,並按下式更新
「間隔非正即更新」的約定令平手時也會更新。若預測規則在平手時偏向 ,則每一次實際錯誤都是一次更新,不過平手時的更新有可能原本已預測正確。因此,更新次數的上界同時也是錯誤次數的上界。
具正間隔的可分性
定義 5.2.1
(具間隔 的分離)
若單位向量 使每一輪 均有 ,其中 ,則稱序列 被 以間隔 分離。數值 是 到超平面 的帶號距離;當 位於其標籤所在的一側時為正。
定理 5.2.2
(感知器錯誤次數上界)
假設每一輪均有 ,且序列被單位向量 以間隔 分離。則該規則至多執行 次更新,即使序列是適應性地選取,只要符合這些假設亦然。
證明
(線性進展對平方根增長)
只為進行更新的回合編號,並以 表示經過 次更新後的向量。每次更新都令向量沿 方向前進:
此處 在本證明中標記各更新回合。在一次更新中,,故
由歸納法得 。由柯西–施瓦茨(Cauchy–Schwarz)不等式及 得 。當 時,兩邊相除再平方,得 。此論證是確定性的:它對序列不作任何獨立性假設。
證明透視
進展為線性增長,而範數至多按平方根增長
每個假設恰好對應一條不等式。間隔 給出下界 ,並且每一次更新的回合都需要它。更新條件 使平方範數中的交叉項不為正,而 控制其餘部分,得出上界 。由 開始提供該歸納法的起點。最後, 只用一次,即在柯西–施瓦茨不等式中,把投影 轉化為由 控制。線性增長不可能永遠停留在平方根上界之下;將兩者比較,便得出錯誤次數上界。
常見錯誤
(原始得分大不等於間隔大)
若非零分離器 滿足 ,則取 及 。單憑未正規化的 數值很大,並不能確立幾何間隔很大,因為縮放 會改變該數值。若把 中的 換成 ,只要放大 就能使上界任意小,這顯然荒謬。
此上界說明了甚麼,沒有說明甚麼
例題 5.2.3
(讀出上界)
在 中,設每個例子均有 ,且滿足 。取 ,得 、,故至多四次更新。此上界並不保證恰好出現四次更新;它對每個符合所述界限的序列均成立。
例題 5.2.4
(一次完整的運行)
取 、、,並循環使用。取 時每個 ,故 ,而 ,所以至多 次更新。由 開始。第 1 輪:,故 。第 2 輪: 而 ,間隔為 ,故 。第 3 輪:,不更新。第二個循環中的間隔為 、、,全部為正,所以運行在 次更新後停止。不變量也成立:,。
例題 5.2.5
(上界達到等號的情形)
在一維中取每個 的 、,並取 。則 、,上界為 。由於 給出間隔 ,第一輪便更新為 。此後每個間隔都等於 ,所以恰好更新一次,上界是緊的。另外,從 開始的任何運行,第一輪必定更新,因為無論 是甚麼,初始間隔都為零。
該定理假設存在一個分離器及一個正間隔,對所有回合均適用。有限的可分數據集在把某個固定的嚴格分離器正規化後,確實有正的最小間隔;但無窮序列雖可逐點被嚴格分類,卻可能沒有一致的正間隔。例如在一維中取 、,則 嚴格分離之,但 。所展示的定理無法由該分離器給出有限的數值上界;但這並不表示此特定序列必定迫使出現無窮多次錯誤。
反例模式
逐點可分未必給出一致正間隔
間隔 出現在分母並非偶然。若序列中的點趨近分離超平面,則固定的嚴格分離器對每個點可以有正的帶號得分,而這些得分的下確界卻為零。假設單一正數 的證明,在沒有進一步論證的情況下,不能以逐點嚴格不等式取代該假設。
這是對在線更新次數的上界,並不自動成為未知分布下測試誤差的上界。要得出統計結論,需要一個抽樣模型,以及選取輸出預測器的規則。
常見錯誤
(忘記閾值項)
此定理假設超平面為通過原點的齊次超平面。仿射閾值 可藉由在輸入中加入常數座標來表示,但其後必須重新計算擴張後的範數上界 及間隔;沿用原輸入的 和 是沒有根據的。
練習與解答
快速檢查
(若 且 ,請給出更新次數上界。)
代入 。
解答 · 答案
,即至多更新 次。
快速檢查
(在一維中設 、、。依所述更新約定, 是多少?)
先計算間隔 。
解答 · 答案
間隔為 ,所以規則更新:。
快速檢查
(為何此證明適用於適應性序列?)
列出證明用到序列的哪些性質。
解答 · 答案
每一步只使用所述的逐點範數與間隔不等式;即使每個例子是在看到學習器先前的行為之後才選取,這些不等式仍然成立,證明中不涉及概率獨立性。
快速檢查
(十次更新的上界是否蘊含測試誤差至多為百分之十?)
比較兩個陳述各自計算的是甚麼。
解答 · 答案
否。在線計數與測試誤差概率是不同的量。要把兩者連繫起來,需要分布假設以及對輸出選取的分析。