弱分類器必須回應當前權重
分類器即使答對大部分訓練例子,也可能反覆漏掉同一批困難個案。複製它的票不會修好那些錯誤。提升法改變訓練樣本上的分布,再要求分類器在新分布下仍有用。
所以「弱」在每輪都需要量化條件。均勻數據上的初始優勢,不能獨自支持後續全部重加權的定理。本節會明確寫出該條件,推導有限樣本的 AdaBoost 保證。
固定樣本、得分與平手規則
定義 12.1.1
(二元加權訓練問題)
固定非空樣本 ,,弱分類器 回傳 或 。第 輪權重 且總和為一,加權錯誤率為
指示量在括號條件成立時為 1,否則為 0。初始 、得分 。加權投票後,。 時預測 ,否則預測 ;例子 的訓練間隔定為 。
正間隔表示答對;零間隔是平手,本規則會把正標記答對、負標記答錯。因此證明用「答錯必有間隔至多零」這個安全方向,不宣稱兩者等價。得分是加權票,不是已校準的類別概率。
以最小正規化因子選票重
設當前分類器有 ,對候選票重 考慮
答對時 ,答錯時 。微分得 ,令其為零,得到
本節對數都是自然對數。 兩項皆正,且 ,所以這是固定方向 的唯一全局最小值,沒有聲稱整個集成已全局最優。因 ,票重為正,最小 小於 1。
新例子權重正規化為
此式保留正權重及總和一,增加錯例權重、降低正確例權重。對上述最小化票重,也可精確寫成
因此原錯例的新總權重恰為 ,原正確例也為 。下一弱學習器須在這個已改分布下找到新優勢。
定義例外回合,不把分母設為零
若 ,因全部權重正,所有訓練例都答對,該弱分類器本身已是零訓練誤差答案。若也要保留原集成,選有限係數 ,加入此票後停止。每個新間隔是 。
此時不代入對數公式。其極限係數無窮, 的下確界零不由有限係數達到;本有限停止票保證訓練符號正確,不是指數損失為零。
若 ,正優勢前提已失效。恰為 時,最優係數為 0、 為 1,沒有進步。若假設類容許把 取負,超過 的錯誤可變成 ;但取負是額外類別假設,也救不了恰好平衡的分類器。以下程序回報缺乏優勢,不會憑空保證它存在。
BOOST(sample, max_rounds):
require sample is nonempty and labels are -1 or +1
D[i] = 1 / m for each example i
F[i] = 0 for each example i
votes = empty list
for each round up to max_rounds:
h = WEAK_LEARN(D)
error = sum D[i] over examples with h(x[i]) != y[i]
if error == 0:
alpha = 1 + max_i abs(F[i])
append (alpha, h) to votes
return votes with status PERFECT_TRAINING_FIT
if error >= 1/2:
return votes with status NO_POSITIVE_EDGE
alpha = (1/2) * ln((1-error) / error)
Z = 2 * sqrt(error * (1-error))
append (alpha, h) to votes
for each example i:
F[i] = F[i] + alpha * h(x[i])
D[i] = D[i] * exp(-alpha * y[i] * h(x[i])) / Z
return votes with status ROUND_LIMIT
回傳的票及分類器定義任意輸入的得分; 儲存訓練例當前得分,用作停止測試。不要求弱學習器精確最小化加權錯誤,但以下定理要求它回傳的錯誤率有合適上界。
例題 12.1.2
(以完美弱分類器停止)
設標記為 ,當前得分為 。平手規則在得分為零時預測 ,所以集成在例 、、 上答錯。設下一個弱分類器在每個訓練例上都等於 ,即 。有限停止規則給出 。新得分為 ,間隔為 ,全部不小於 ,所以每個訓練預測都正確。若係數取 ,得分為 ,第一例的間隔為 ,那個錯誤仍會保留。
例題 12.1.3
(恰好為二分之一的分類器)
取四個等權的例子,以及只在例 和例 出錯的分類器 ,所以 。此時 ,,:權重不變,這一票對 沒有任何貢獻。把 取負,得到只在例 和例 出錯的分類器,加權錯誤仍是 ,所以取負救不了恰好平衡的分類器。弱學習器若回傳這樣的分類器,就是沒有正優勢,即程序中的狀態 NO_POSITIVE_EDGE。
權重相消,露出訓練目標
定理 12.1.4
(正規化因子乘積界定訓練錯誤)
完成 輪,且每輪 時,
中間一項是經驗指數損失。
證明
(由均勻初始權重還原每個末權重)
反覆代入更新,得到
對 求和,用 ,便得等式。對答錯例,平手規則保證 ,故 ;對答對例,錯誤指示為 0,不大於正的指數項。逐點不等式相加,再除 即可。
證明透視
權重相消證明用了甚麼、沒用甚麼
這個證明有兩個互相獨立的部分。第一部分是恆等式:由 展開 ,每輪乘入一個因子 ;由於 ,指數合併成間隔,而正規化因子累積在分母。末權重總和為一,所以指數平均值必然恰好等於 ;這個等式不需要弱分類器如何選取的任何性質。第二部分是逐點不等式,也是唯一用到平手規則的地方:答錯迫使間隔至多為零,從而 。這個不等式是單向的,並不說答錯例的間隔恰為零,也不說答對例貢獻很小。優勢假設 完全沒有進入這個證明;它要到之後證明每個 小於一時才出現。
定理 12.1.5
(一致正優勢帶來指數衰減)
若這 輪每輪在當前分布下都滿足 ,其中固定 ,則
前提針對每個當前 ,不是只針對初始均勻分布。
證明
(先界每個因子,再相乘)
設 ,則 。由 時 ,在此平方根定義域得到 。乘 個因子再用前一定理,即得結論。若出現完美弱分類器,已另證的有限停止規則直接給零訓練誤差。
有限樣本的錯誤率若嚴格小於 ,錯例數是整數便迫使它為零。完成 輪有承諾優勢的正誤差回合即可。這是有條件保證:實現不能靠假設創造優勢,同一輸入的矛盾標記可能令條件根本不可達。
常見錯誤
(界等於 並不排除一個錯誤)
當 時,恰為 的訓練誤差界與一個錯例相容,因為 個例子中錯一個,訓練誤差正是 。只有嚴格不等式 才迫使整數的錯例數小於一。選取 時,須要求 ,而不只是 。
精確演算三個自適應回合
例題 12.1.6
(四個訓練輸入與固定三分類器類別)
預測如下;此表只指定訓練輸入,沒有聲稱未見數據的標記:
| 例子 | 標記 | |||
|---|---|---|---|---|
| 1 | +1 | +1 | +1 | −1 |
| 2 | +1 | +1 | +1 | −1 |
| 3 | −1 | −1 | +1 | −1 |
| 4 | −1 | +1 | −1 | −1 |
第一輪平手選 。依次 、、 在各自回合都最小化此小類別的加權錯誤:
| 回合 | 當前權重 | 所選錯誤率 | 票重 |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 |
第一輪只錯例 4,給它新總權重的一半;第二輪修好它,卻錯例 3,令例 3 新權重成 。所以第三輪只錯例 1、2 的 變得有用,雖然它初始錯誤率是 。
一輪、兩輪後集成都各錯一例,但錯例改變;三輪後全部間隔為正:
正規化因子為 、、,三輪後指數損失為 ,實際訓練誤差 0 遠低於它。乘積目標會下降,即使某一輪零一錯誤數沒有改變。
常見錯誤
(目標每輪下降,錯例數卻不一定)
在三輪例題中,指數損失界在一輪後為 ,兩輪後為 ,而訓練誤差兩次都是 :改變的只是被錯分的是哪一個例子。定理用 的乘積界定最終誤差,對中間每一輪並沒有任何說法,所以期望錯例數單調遞減並無根據。
反例模式
複製分類器不會保留初始優勢
上述一般更新後,同一分類器的舊錯例新總權重恰為 。若不改預測就再叫它一次,加權錯誤就是 ,不是早前較小的值。
三輪例題中 初始錯誤 , 下卻是 。均勻正確率 75% 本身不能支持反覆正優勢回合。重加權創造新學習問題,不會承諾上一假設在新分布仍有優勢。
說清楚此界證明了甚麼
以上全部量都在固定訓練樣本計算,證明沒有使用抽樣假設或測試分布。總體誤差需要另外的一般化論證,零訓練誤差並非該論證;指數損失下降亦不表示每輪觀察到的零一錯誤都嚴格下降。
輪評估與更新 個權重,在弱學習器本身成本之外花 ,假設分類器評估及算術為常數時間。需儲存 個權重/得分及回傳分類器、票重。此處數學模型是精確的正權重正規化;有限精度實現須保留所欲分布,不能悄悄把數值下溢當作零加權錯誤的證據。
附解答練習
快速檢查
(重加權一個四分之一錯誤的分類器:四例初始等權,分類器只錯例 4。用兩情況更新推導新權重,並求原樣分類器在新分布的加權錯誤。)
錯例用 ,其餘用 。
解答 · 答案
。錯例得 ,每個正確例得 ,總和為一。原錯集合仍是例 4,新權重為 ,所以原正優勢不能直接重用。
快速檢查
(分清目標進步與錯例集合改變:為何三輪例題第二輪後,集成錯例 3、答對例 4?兩輪後訓練誤差與指數損失界各是多少?)
比較例 3 與例 4 的間隔 。
解答 · 答案
第二票 大於第一票 。例 3 第一分類器對、第二錯,間隔 ;例 4 則 。例 1、2 兩分類器都對。訓練錯誤仍是 ,指數損失界為 。界下降時,錯例數可以不變。
快速檢查
(小心使用整數錯例數:,且每個已完成的正誤差回合都保證優勢至少為 。給出足夠的回合數,使已證的界迫使訓練錯誤為零。為何嚴格小於 有用?)
解 ,求 。
解答 · 答案
需要 ,所以 輪足夠。此時界嚴格小於 ,但一個錯例已令錯誤率至少為 ,因此不能有錯例。若界恰等於 ,仍不能排除一個錯例。結論仍依賴每輪確實找到承諾的優勢。
快速檢查
(某分類器在當前權重下的加權錯誤為 。求 和 ,以及它的錯例在新權重下的總權重。)
使用 與 。
解答 · 答案
,。由兩情況更新,每個錯例得 ,所以錯例合計得 ,正確例合計得另外的 。