弱學習器可能只比拋硬幣好一點。Boosting 能把這個優勢轉化為任意小的誤差,但有一條關鍵限定:學習器必須在 boosting 所使用的變化分布上持續保持優勢。僅有訓練誤差計算並不能給出這種分布層面的保證。這裏先在明確的弱學習假設下直接證明保證,再說明如何從原始樣本源中對這些變化分布採樣。
定義 6.2.1
(邊緣為 的弱學習器)
設 是實例空間 上的未知分布,來自概念類 的未知目標 提供標籤 ,其中 的函數均為可測映射 。下文所有規則和權重均可測。固定 。邊緣為 的弱學習器具有以下無分布、可實現保證:對每個 、 上每個由該目標標記的分布 ,以及每個 ,給定來自 的 個獨立帶標籤樣本,它輸出規則 ,使
以至少 的概率成立;概率取自樣本及其獨立內部隨機性。樣本界 不依賴具體的 或 ,且學習器除帶標籤樣本外並不知道 。這個保證必須對下文遇到的每個重加權 成立。我們假設每個輸出規則在需要時可以求值;計算複雜度取決於弱學習器和規則的表示。
使用固定正步長的總體 boosting
令
從 開始。第 輪使用相對於 具有以下密度的分布 :
得到規則 後令 。每個 都是概率分布:權重正且有界,並且 。最終預測取 的符號,平局可使用任意固定規則。分析中把零間隔計為錯誤,因此上界覆蓋每一種此類平局規則。
定理 6.2.2
(總體誤差的指數下降)
若每個選出的規則在 下的誤差都不超過 ,則
這是對實際選出的規則和真實分布 的確定性蘊含。不需要假設有限假設類,也不需要經驗泛化步驟。
證明
(每個成功輪次都縮小指數勢)
令 。(2) 中的換測度給出 ,因此
不等式使用 與 。等號處的值由 的定義算得。由於 ,連乘得到 。只要 就有 ,從而得到 (3) 的第一個不等式。最後,。
證明透視
為甚麼這是總體結論
每個 都由真實的 定義,而 (1) 中的弱邊緣是真實的 誤差。勢函數是對 的期望,不是訓練平均。規則可以自適應選擇;在它們選出後,只要每條規則滿足自身的邊緣條件,確定性不等式就適用。下一步說明如何在不知道 的密度時獲得所需樣本。
對自適應重加權分布採樣
第 輪開始時,已選擇的 已由先前記錄固定。從 抽取新鮮帶標籤樣本 。對每個候選樣本,獨立地以如下概率接受:
由於 ,這個概率位於 。重複直到接受 個樣本。實現 (4) 不需要知道歸一化常數 。
定理 6.2.3
(拒絕採樣與明確的候選樣本上限)
以先前記錄為條件,被接受的樣本是來自 的獨立樣本。接受概率滿足
每輪恰好使用 個被接受樣本。對無上限的過程, 輪使用的原始 候選樣本總數的期望至多為 。因此對 ,上限
被超過的概率至多為 。
證明
(先取條件,再對自適應歷史求平均)
對任意可測 ,一個候選樣本落入 且被接受的概率為
除以總接受概率就得到 。獨立候選樣本和獨立接受硬幣使連續接受的樣本相互獨立,且具有同一個條件分布。又因為 ,得到 (5)。
以歷史為條件,每次接受所需候選數服從成功概率為 的幾何分布,所以接受 次的期望候選數至多為 。這個界對每段歷史都成立,包括弱規則不成功的歷史。取期望並求和便得到總期望界。對無上限過程使用 Markov 不等式,證明 (6)。將無上限過程的候選樣本數記為 ,中止事件為 :實際實現若將超過 就中止;在其補事件上,它與無上限過程完全相同。
例題 6.2.4
(兩輪拒絕採樣)
設 ,、,兩點的目標都是 ,。則 ,。第 1 輪中 ,。設 在 正確、在 錯誤,所以 。於是 給出 在 為 、在 為 ,且 。
第 2 輪中,(4) 的接受概率為 、。總接受概率為 ,與 一致,也滿足 (5) 的下界 。在被接受的樣本中,落在 的比例為 ,這恰是由 (2) 直接算出的 :。
常見錯誤
(接受概率不能超過一)
用概率 接受候選樣本,看似是實現 (2) 的自然做法,但這個數可能大於一:在上面的例子中, 在 上等於 。(4) 中的因子 把所有權重乘以同一個常數,使最大的權重不超過 。這並不改變 ,因為只有接受概率的比值才起作用;這也是無需計算未知歸一化常數 的原因。
強學習器與其假設
給定 ,取
每輪使用 個被接受樣本。運行上限為 (6) 的過程;若中止,則輸出任意固定規則。
定理 6.2.5
(帶置信度的弱到強保證)
對每個 和每個 ,在上述無分布弱學習假設下,返回的分類器以至少 的概率具有至多 的 -誤差。即使中止,使用的原始樣本數也至多為 。
以任意先前記錄為條件,拒絕採樣提供新鮮、獨立的 樣本。因此,即使 是自適應選擇的,弱學習器在第 輪不滿足邊緣條件的條件概率仍至多為 。對記錄求平均並使用並集界,任意一輪失敗的概率至多為 。在無上限的思想實驗中,超過候選樣本上限的概率至多為 。在兩個補事件的交集上,由 (3) 得誤差至多 ;且有上限的算法與思想實驗相同。並集界證明定理,不需要這兩個失敗事件相互獨立。
對固定邊緣 ,有 ,且 是 的多項式。因此,只要弱學習器的樣本和計算成本對相應參數為多項式,且規則可高效求值,(6) 對 和 也是多項式。這個拒絕採樣界有意取得粗,並不是最優的 boosting 樣本複雜度。若 變化,該多項式的指數依賴於 ,所以這裏不聲稱對 一致的多項式依賴。
例題 6.2.6
(上限有多粗略)
取 、。此時 ,,。勢函數的界為 。然而在 (5) 所允許的最壞情形下,最後一輪每接受一個樣本可能需要 個候選樣本。邊界情形是第一輪:,所以 ,每個候選樣本都被接受,。分析本身正確,但上限 (6) 只是證明的工具,並不是實際成本的估計。
例題 6.2.7
(三條規則各錯一個不同的點)
設 ,概念類包含兩個恆定目標 和 。對於每個點,讓 中的一條在該點預測 ,在其餘兩點預測 。使用六條規則的假設類 ,其中沒有恆定規則。對任一目標和每個分布 ,至少有一個點的質量不超過 ;選擇帶有適當符號的對應規則,其誤差至多為 。因此該類別對兩個目標都有無分布邊緣 ,儘管沒有一條單獨的規則是完美的。
例如取 。在這六條規則上用新鮮樣本做經驗誤差最小化,就得到邊緣為 的弱學習器:一致 Hoeffding 界表明,只要 ,六條規則的經驗誤差與真實誤差之差都不超過 的概率至少為 。選出規則的真實誤差因此至多為 。事實上,對正目標, 的無權多數投票是完美的;對負目標,它們的相反規則的多數投票是完美的。這展示了單條規則均不完美時組合如何成功。
反例模式
只在原分布上有邊緣並不夠
設 、,兩個點的目標均為 。在 正確、在 錯誤的規則 有 -誤差 。但只重複這條規則永遠修不好該錯誤: 的任意正權重多數投票仍是 。在重加權 (2) 下, 的相對權重每輪增加 ,其概率趨於一。最終 在 booster 所請求的分布上不再有正邊緣。只針對 的弱保證不能代替 (1)。
練習與解答
快速檢查
(一步勢函數:若某規則的 誤差為 ,推導 。)
把期望分成正確點與錯誤點兩部分。
解答 · 答案
正確點滿足 ,貢獻 ;錯誤點滿足 ,貢獻 。故比值為 。
快速檢查
(輪數:若 、目標誤差 ,求給出的充分輪數 。)
使用 。
解答 · 答案
,故 。這是充分輪數,不一定是最少輪數。
快速檢查
(不需要無窮係數:若某個選出規則的 誤差為零,會怎樣?)
在 處計算該輪的因子。
解答 · 答案
該輪因子為 。固定的 仍有限,更新有定義。這避免了根據精確誤差取自適應係數時可能出現的除零問題。
快速檢查
(自適應置信度:後來的 依賴先前隨機規則,為甚麼仍可使用 上界?)
以第 輪之前的記錄為條件。
解答 · 答案
對任意先前記錄取條件,第 輪失敗概率至多為 。取期望後,無條件概率也至多為 。再用並集界得到 ,無需假設各輪失敗相互獨立。
快速檢查
(上限不等於期望:為甚麼僅有候選樣本數的期望界不能給出確定性樣本上限?)
非負隨機變量可以超過它的平均值。
解答 · 答案
非負隨機變量可能超過其期望。Markov 不等式將該界轉化為高概率上限:取 (6) 的 時,理想過程超過 的概率至多 。在 處中止使實際資源使用有確定性界,並把該事件計入失敗概率。