線性分類器先替特徵向量計算一個分數,再按正負號選擇類別。感知器會在例子的帶標籤分數尚未嚴格為正時更新這個分數函數。它的收斂論證來自幾何:每次更新都沿著某個分離方向前進;只要數據存在正間隔,權重範數的增長便不足以容許無限多次這樣的更新。
假設和停止條件同樣重要。有限次訓練未能分開數據,可能是因為數據不可線性分離,但單憑一個太小的訓練預算,不能作出這個結論。本節會明確加入偏置座標,逐步追蹤一次精確的訓練過程,證明更新次數上界,然後才討論假設不成立時會發生甚麼。
用一個額外座標吸收偏置
設一個例子為 ,標籤為 。仿射分類器使用分數 。定義增廣向量和權重為
因此,偏置是一個需要學習的座標,不能當成無須更新的固定貢獻。作一般預測時,我們約定分數為零便選類別 。但訓練要求的是帶標籤分數嚴格為正,即 ;分類錯誤和分數為零的邊界例子都會觸發更新。
定義 9.1.1
(感知器更新與嚴格分離)
初始化 。若某個例子滿足 ,便作更新
否則保持 不變。這是步長為一的感知器。若訓練集中每個例子都滿足 ,便稱這個權重嚴格分離訓練集。
更新次數包括零間隔例子;即使預測時的平手規則剛好把某個邊界例子標對,它仍然會觸發更新。以下慣稱的「錯誤次數上界」實際上是這個連邊界更新也計算在內的次數上界。
回到原座標,規則就是 及 。正例加上自己的增廣向量,負例則減去自己的增廣向量。
常見錯誤
(只在分數嚴格為負時才更新)
一個誘人的簡化是只在 時更新。從 出發,每個分數都是零,所以沒有任何例子會觸發更新:迴圈隨即結束,,每個帶標籤分數仍然是零,並不是嚴格分離向量。對點 (標籤 )和 (標籤 ),這條規則回傳 ,而採用 的規則則在三次更新後把它們分開(見下面的第一個例題)。邊界情形 必須觸發更新。
一次更新會改善當前間隔,但未必已經修正分類
對於觸發更新的例子,
因為 ,而增廣使 不可能是零向量,所以帶標籤分數會增加。不過,增加之後仍然可能是負數。更新亦可能使其他例子的分數朝任何一個方向改變,這正是我們需要整體收斂證明的原因。
反例模式
一次修正未必足以把該例子分對
從零權重開始,先遇到一維負例 ,增廣更新會得到 。接著遇到正例 ,其增廣向量為 。舊帶標籤分數是 ;更新後得到 ,新帶標籤分數是 。
分數增加了 ,但該點仍然被分錯。這兩個例子其實可分:分數 在 1 為正,在 3 為負。數據並沒有互相矛盾;只是一次單位步長更新未必足以完成修正。
在增廣空間中寫清楚間隔假設
定義 9.1.2
(有界且具有一致正間隔的訓練集)
假設每個呈現給算法的增廣例子都滿足 。再假設存在一個固定單位向量 ,使所有訓練例子都滿足
數值 是這個單位分離向量對所有例子共同保證的正間隔。
半徑 和 的正規化都包括偏置座標。算法本身不需要知道 、 或 ;分析所需的是它們存在。
有限數據若存在嚴格分離向量,便可以先把該向量正規化,再取有限多個正帶標籤分數的最小值,得到這樣的 。這個值可能很小,所以算出的數值上界不一定緊,也不一定具有實際預測訓練時間的能力。
定理 9.1.3
(感知器錯誤次數界)
設 是帶標籤 的增廣訓練例子。假設對所有 都有 ,並且有一個單位向量 使所有 都滿足 。按任何次序、任意多輪呈現這些例子,並運行感知器更新規則,則觸發的更新次數 滿足
證明
(線性的進展對平方根的增長)
只為更新編號。設 是觸發第 次更新的例子, 為 次更新後的權重。
沿 的進展:因 ,
而 ,所以 。
範數的增長:觸發更新表示 ,因此
於是 。
用柯西—施瓦茲(Cauchy–Schwarz)不等式及 把兩者結合:
當 ,兩邊除以 再平方,得 。 時上界顯然成立。
證明透視
哪個假設推動哪一半
這個證明是兩條方向相反的不等式。間隔假設 只用於下界:不論是哪個違規例子觸發,每次更新都使 沿固定方向 至少前進 。更新條件 只用於上界:它使交叉項 不為正,所以每次更新使範數平方至多增加 。柯西—施瓦茲不等式配合 把兩者連起來,論證得以完結,是因為 對很大的 不可能成立。初始權重 使兩個界都從零開始;偏置座標則透過 與 進入,它們必須在增廣空間中取。若算法連分數已為正的例子也更新,交叉項便可能為正,上界就不再成立。
只要所有例子共有這些界限,定理便適用於任何呈現次序。對反覆完整掃描的有限訓練集,一整輪沒有更新就能核實嚴格分離:權重全程不變,而每個例子的帶標籤分數都為正。任何有更新的掃描輪至少會用去一次更新;由於可發生的更新總數有限,重複掃描最終一定會遇到一輪完全沒有更新的情況。
精確追蹤偏置與邊界更新
例題 9.1.4
(兩個訓練點需要三次更新)
取一維點 、標籤 ,以及點 、標籤 ,每輪都按這個次序呈現。增廣向量分別為 和 。
| 掃描輪與例子 | 更新前權重 | 更新前帶標籤分數 | 處理後權重 |
|---|---|---|---|
| 第 1 輪,負例 | |||
| 第 1 輪,正例 | |||
| 第 2 輪,負例 | |||
| 第 2 輪,正例 |
總共有三次更新。最後的帶標籤分數為 1 和 3,所以兩點都被嚴格分離;再掃描一輪也不會改變權重。
計算定理的上界時,取 。兩個例子的帶標籤投影同為 ,所以可取 。最大的增廣範數是 。因此已證上界為 ,而實際更新次數是三。
只使用原特徵的半徑二,便會漏掉值恆為一的偏置座標。定理所用的幾何是 的幾何,而不只是 的幾何。
最後分數是 ,邊界為 。它並沒有把原輸入直線上的通常幾何間隔最大化:閾值取 1 時,與兩個訓練點的距離都為一;閾值取 時,與負例的距離只有 。保證找到分離向量的收斂定理,並不是最大間隔的優化定理。這個分別引出課程稍後的支持向量機主題。
概念視角代數
權重是例子的帶符號和
每次更新都加上觸發該次更新的例子的 ,所以 ,其中 是例子 觸發更新的次數,且 。於是得分為 ,只透過例子之間的內積使用這些例子。在第一個例題中 ,而 。
例題 9.1.5
(平面上的兩個點)
取 (標籤 )與 (標籤 ),按此次序呈現。增廣向量為 和 。從 開始,正例的分數是 ,所以 。負例的帶標籤分數是 ,所以 。第二輪中兩個帶標籤分數都是 ,不再更新:合共兩次更新。偏置座標在中途不為零,最後卻是零。取 ,兩個帶標籤投影都是 ,兩個增廣向量的範數都是 ,所以上界為 。
例題 9.1.6
(單一例子達到上界)
設唯一的訓練例子是 ,標籤 ,故 ,。初始分數為 ,所以一次更新得 ,帶標籤分數為 ,不再有更新。取 ,得 、,所以 ,等於實際更新次數。這裏上界剛好達到;對大多數數據集,上界遠高於真實次數,正如第一個例題,上界是 ,實際更新卻只有三次。
用盡預算並不是不存在分離向量的證明
上述上界假設所有例子共有正間隔。若這個假設不成立,感知器便未必停止。例如,同一個輸入若配上相反標籤,就要求它的分數同時嚴格為正和嚴格為負;反覆呈現這些例子可以不斷觸發更新。
反例模式
標籤一致也可能需要非線性特徵
把 和 標作 ,把 標作 。仿射分數 必須滿足 、 和 。後兩個不等式同時要求 及 ,在 時不可能成立。
各輸入的標籤沒有矛盾,但在原直線上不存在仿射分離向量。若改用特徵 ,分數 卻能把它們分開。分類器對轉換後的特徵是線性的,對原輸入的邊界則是非線性的。間隔定理必須在實際使用的特徵空間中檢查。
反過來,有限次執行尚未分開數據,也不能證明數據不可分。即使數據可分,所需更新次數也可能超出所選預算。回傳狀態應該分清楚「目前已核實得到分離向量」與「訓練迴圈剛好結束」。
明確回傳核實結果的實作
以下函數接受 Python 整數或有限浮點數特徵、整數標籤 及正整數輪數上限。它透過附加座標學習偏置,並使用單位步長更新。Python 整數運算保持精確;浮點分數則是近似值。非有限輸入會被拒絕,任何溢出或非有限中間值都會報錯,而不會產生核實結果。
import math
def perceptron(rows, labels, max_epochs=100):
rows = [tuple(row) for row in rows]
labels = tuple(labels)
if not rows or len(rows) != len(labels) or type(max_epochs) is not int or max_epochs < 1:
raise ValueError("nonempty paired data and a positive integer epoch limit are required")
dimension = len(rows[0])
if not dimension or any(len(row) != dimension for row in rows):
raise ValueError("rows must have the same positive dimension")
if any(type(label) is not int or label not in (-1, 1) for label in labels):
raise ValueError("labels must be integer -1 or +1")
if any(type(x) not in (int, float) or (type(x) is float and not math.isfinite(x))
for row in rows for x in row):
raise ValueError("features must be integers or finite floats")
def checked(a, b, operation):
try:
result = a * b if operation == "multiply" else a + b
except OverflowError as exc:
raise ArithmeticError("floating-point operation overflowed") from exc
if type(result) is float and not math.isfinite(result):
raise ArithmeticError("nonfinite floating-point intermediate")
return result
def signed_score(weights, vector, label):
total = 0
for w, x in zip(weights, vector):
total = checked(total, checked(w, x, "multiply"), "add")
return checked(label, total, "multiply")
augmented = [row + (1,) for row in rows]
weights = [0] * (dimension + 1)
updates = 0
for _ in range(max_epochs):
changed = False
for vector, label in zip(augmented, labels):
if signed_score(weights, vector, label) <= 0:
weights = [checked(w, checked(label, x, "multiply"), "add")
for w, x in zip(weights, vector)]
updates += 1
changed = True
if not changed:
break
scores = [signed_score(weights, vector, label)
for vector, label in zip(augmented, labels)]
verified = all(score > 0 for score in scores)
return weights, updates, verified
調用 perceptron([(0,), (2,)], [-1, 1], max_epochs=2) 會得到 ([2, -1], 3, True)。最後的明確檢查能辨認出:最後一輪獲准掃描已經產生分離向量。若只掃描一輪,結果是 ([2, 0], 2, False);負例的帶標籤分數仍為零,儘管數據本身是可分的。
權重列表的最後一項是偏置。回傳前,函數會重新計算每個帶標籤分數。True 表示所有計算出的分數均有限且嚴格為正;False 表示至少一個計算出的分數不大於零。使用浮點數時,捨入可能改變接近零的分數,因此此數值檢查不是嚴格的精確實數分離證書。兩者都不是概率估計,也不保證對未見例子的表現。
對 個例子、 個原特徵及 輪掃描,這個實作需要 次算術工作,並在有需要時多作一次 的最終檢查。權重本身佔 空間;這個教學實作亦會儲存增廣後的訓練行。間隔上界在假設成立時限制更新次數,掃描輪數預算則即使在假設不成立時,也能限制工作量。
練習與詳解
快速檢查
(目前增廣權重是 ,一個正例的原座標為 。求它舊的帶標籤分數、更新後的權重和新的帶標籤分數。一次更新足以把它正確分類嗎?)
先把例子補上常數座標。
解答 · 答案
增廣例子為 ,所以舊分數是 。加上該向量得 ,新分數為 。分數增加了二,即它的範數平方,但仍然為負。一次更新未必能完全修正。
快速檢查
(對標籤為 的點 和 ,取 。給出增廣半徑、共同間隔及更新次數界。追蹤的運行實際作出多少次更新?)
使用增廣向量 和 。
解答 · 答案
增廣向量的範數分別為一和 ,所以 。兩個帶標籤投影都是 ,得上界 。追蹤過程作了三次更新。上界是充分保證,而不是運行長度的精確預測。
快速檢查
(展開 時,為甚麼求上界時可以捨去交叉項?若算法連已正確分類且間隔為正的例子也更新,同一論證是否仍然成立?)
留意觸發更新時 的符號。
解答 · 答案
交叉項是 ,它不為正,正是因為只有帶標籤分數不大於零時才觸發更新。若對間隔為正的例子任意更新,這一項可能為正,所述上界就不能再由同一論證得出。
快速檢查
(兩點例子只運行一輪,函數報告未能核實。這是否證明數據沒有仿射分離向量?回傳的權重有哪裏不滿足?第二輪會怎樣?)
重新計算一輪後權重的帶標籤分數。
解答 · 答案
這並不證明不可分離。權重 使負例的帶標籤分數仍為零。第二輪把權重改為 ,兩個帶標籤分數都為正,合共三次更新後最終核實成功。
快速檢查
(負例點 與正例點 所學得的閾值是 。把它與最近點的距離,和閾值 的相比。有限步收斂是否意味著得到最大的幾何間隔?)
量度每個閾值到最近訓練點的距離。
解答 · 答案
閾值 到最近點的距離是 ;閾值 到兩點的距離都是一。因此這個已收斂的感知器並不是最大間隔分離向量。定理限制的是到分離為止的更新次數,並沒有優化原空間的幾何間隔。
快速檢查
(對負例點 和正例點 ,說明為甚麼沒有分數 能把它們分開。哪一個變換後的特徵 能使分數 成功?)
把三個嚴格不等式寫成 、 的條件。
解答 · 答案
正例點要求 。負例要求 及 ,互相矛盾。取 :正例的分數是 ,每個負例的分數是 。這是在變換後特徵空間中的分離,並不是原座標上的仿射分離向量。