一次學習一個預測
在批量問題中,學習器接收一份帶標籤樣本,然後生成分類器。在線學習中,預測與反饋交替進行。第 輪,學習器看到 並預測標籤,隨後才看到 ;它可利用反饋改變下一次預測。這個順序禁止學習器在預測前使用當前標籤。
錯誤界控制一個序列上的錯誤預測次數。它可以是確定性的,對對抗性選擇的序列也成立;但它不會自動成為關於未來樣本的概率界。我們先比較有限個二分類專家,再說明連接在線與總體觀點所需的額外獨立同分布假設。
折半一個可實現的版本空間
設 是可測實例空間上的有限非空可測分類器集合,其中 。初始令 。第 輪,在 中預測多數標籤;若平局則選 1。真實標籤揭曉後,僅保留預測該標籤的假設:
定義 5.1.1
(可實現序列與版本空間)
若存在同一個固定的 對每一輪都標註正確,則稱序列 可由 實現。與之前全部標籤一致的假設集合 稱為第 輪的版本空間。
可實現性保證每一輪 ,所以版本空間永不為空。過程不需要知道哪個成員是 。
定理 5.1.2
(折半錯誤界)
對每個可由 實現的有限序列,多數算法至多犯 次錯誤。
證明
(每次錯誤使版本空間減半)
在犯錯的一輪,當前至少一半假設預測了學習器所選的錯誤多數標籤;平局時也成立。所有這些假設都被刪除,因此 。在正確輪次中,版本空間也不會增大。經過 次錯誤後,由於 仍然保留,。因此 ,而 為整數。
證明透視
每個假設用在哪裏
論證靠兩個互相獨立的事實。多數投票提供減半:它只在犯錯的輪次起作用,那時錯誤標籤至少為 中一半的假設所持有,所以至少一半被刪除。可實現性提供幸存者 ,由此得到下限 ,它從不參與減半這一步。去掉可實現性,減半仍然成立,但下限消失, 可能變空,下面的反例正是如此。正確的輪次不會刪掉任何必要的假設,也不花費錯誤。 中的取整僅僅來自 是整數。
例題 5.1.3
(四個閾值與兩次錯誤)
令 、,其中 。對 ,兩個假設投 1、兩個投 0,平局規則預測 1。若 ,便犯一次錯,且只剩 。對 ,二者再次平局,學習器預測 1。若 ,又犯一次錯,只剩 。序列可由 實現,並達到 的界。
對某些假設類,這個界是緊的。在 個不同點上,令 包含全部 個二值函數。對任意確定性在線學習器,依次呈現每個點一次,並選擇與學習器預測相反的標籤。所得 個標籤確定了 中的一個固定目標,所以序列可實現,並迫使學習器犯 次錯誤。這是針對該類的最壞情況構造,並不聲稱每個同樣大小的類都能迫使如此多錯誤。
沒有完美專家時的加權多數法
如果數據不可實現,專家犯一次錯就永遠刪除它,可能使版本空間變空。加權多數法保留所有專家,但降低出錯者的權重。
定義 5.1.4
(帶懲罰因子的加權多數法)
令 ,選 ,初始對所有 設 。每輪預測總權重較大的標籤,平局仍選 1。看到 後更新
每一輪所有出錯專家都被更新,包括學習器預測正確的輪次。記學習器的錯誤次數為 ,專家 在相同 輪中犯錯 次。
定理 5.1.5
(加權多數錯誤界)
對於每個有限帶標籤序列,無需可實現性假設,
對數均為自然對數。特別地,用事後最優固定專家的錯誤次數代替 ,該界仍成立。
證明
(對總權重的勢函數論證)
令 ,初始 。任何一輪權重都不會增加。當學習器犯錯時,至少一半總權重投給了錯誤標籤,平局情形也包括在內。因此
經過 次錯誤,。另一方面,固定專家犯 次錯誤後的權重為 ,所以 。取對數並整理即得該界;由於 ,分母為正。
證明透視
夾住總權重
證明從上、下兩個方向界定同一個量 。上界只用到學習器的錯誤:在每個犯錯的輪次,至少一半權重落在錯誤標籤上並被乘以 ,所以 至少減少 的比例;正確的輪次只會令 減小,因此忽略它們是安全的。下界只用單個專家,因為 是非負項之和,不小於其中任何一項。由於 任意,結論對所有專家同時成立,特別是對最優的那個。這裏既不需要可實現性,也不需要專家彼此獨立或標籤具有隨機性。
例題 5.1.6
(兩個常值專家)
兩個專家分別總預測 0 和 1,取 ,標籤依次為 0、1。初始權重平局,學習器預測 1 並犯錯;新權重為 1 和 。下一輪預測 0 並犯錯,此後兩個權重均為 。兩個專家各犯一次錯,而該界給出 ,對 成立。雖然沒有專家對兩個標籤都預測正確,該界仍然有效。
例題 5.1.7
(三個專家的逐輪追蹤)
取專家 ,。第 1 輪:預測為 ,標籤為 1。投給 1 的權重為 ,投給 0 的為 ,學習器預測 0 並犯錯; 減半,權重變為 ,。第 2 輪:預測為 ,標籤為 0。投給 1 的權重為 ,投給 0 的為 ,學習器預測 1 並犯錯; 減半,權重變為 ,。第 3 輪:預測為 ,標籤為 0。投給 0 的權重為 ,投給 1 的為 ,學習器預測正確,但 仍然減半,權重變為 ,。因此 ,。對 ,定理給出 :成立,但在這麼短的運行上遠不緊。最終權重 也驗證了 的下界。
常見錯誤
(只在學習器犯錯時才懲罰專家)
在加權多數法中,每個預測錯誤的專家在每一輪都要乘以 ,包括學習器自己預測正確的輪次,上面追蹤的第 3 輪就是例子。如果只在學習器犯錯之後才更新,下界 就不成立,因為 計算的是該專家的全部錯誤。
這裏比較的是事後最優的固定專家。固定 時,乘在 前的係數一般大於一;單憑所示結果並不是次線性遺憾界定理。折半證明需單獨處理 :不能將零代入這個對數界。
反例模式
版本空間可能消失
取一個實例 、兩個常值專家 0 和 1,標籤依次為 0、1。第一個標籤後,折半法只保留常零專家;第二個標籤後不再剩下任何專家。該序列不能由單個專家實現,所以折半定理不適用。加權多數法保持正權重並仍有最優專家比較,但如果每個專家都犯很多錯,該比較並不保證絕對錯誤次數很少。
從在線錯誤到期望風險
現在假設 獨立同分布於固定分布 ,,且第 輪在線規則以固定的確定性平局規則定義可測分類器 ,只使用之前的樣本。令 。經過 輪後,獨立於樣本、從 均勻選擇 ,輸出事先保存的分類器 。在給定過去的條件下, 是新抽樣,因此
期望同時針對樣本和 。若某個固定 滿足 ,有限獨立同分布序列幾乎必然可實現。折半法因此幾乎必然至多犯 次錯,故 。該陳述針對隨機選出的已保存預測器和期望風險。它不自動成為高概率保證,也不自動保證最後一個預測器或非獨立同分布序列的表現。
常見錯誤
(把期望風險界用在最後一個預測器上)
等式 是對均勻下標 取平均。它並沒有界定 或 :在線規則可能到很晚才犯最後一次錯,單個較晚的預測器可以有很大的風險,而對全部 個預測器的平均仍然很小。
練習與解答
快速檢查
(若可實現的假設類有六個假設,折半法給出多少次錯誤的整數上界?)
套用定理並向下取整。
解答 · 答案
。若犯三次錯,剩下的假設至多 個,這不可能,因為 始終保留。
快速檢查
(對上述四個閾值,在 處按平局規則作第一次預測,並寫出標籤為 0 後保留的集合。)
分別計算 時的 。
解答 · 答案
,。兩邊各有兩個專家,故平局預測 1。標籤 0 只保留預測 0 的假設,即剩下 。
快速檢查
(加權多數法取 、,且有一個完美專家。所述定理給出的學習器整數錯誤次數上界是多少?)
完美專家的 。
解答 · 答案
定理給出 ,由於 為整數,故 。在此例中該界弱於可實現折半界 。
快速檢查
(一個獨立同分布問題滿足某個 的 ,且 。運行折半法 輪,令 均勻且獨立於樣本,輸出保存的 。對樣本和 取期望,給出其總體誤差上界。)
利用 和折半界。
解答 · 答案
折半法幾乎必然至多犯 次錯,因此期望誤差至多為 。這並不說明每次運行或最後一個在線預測器的誤差都至多為 。