在線分類器逐個觀察樣本,並在收到標籤之前預測。批量預測器則需要在訓練後面對新樣本。當樣本獨立地來自同一固定分布時,每次在線預測面對的樣本,相對於過去而言都是新抽取的。這使我們可以把在線表現轉化為總體風險陳述。具體輸出和概率的來源都很重要:對已保存預測器的平均風險作保證,並不自動保證其中每一個預測器的風險。
在線序列與批量混合規則
設 Z1,…,ZT 獨立同分布於 P,其中 T≥1。在看到 Zt 之前,確定性在線規則只根據 Z1,…,Zt−1 選擇可測預測器 ht;所有平局規則預先固定。將預測器表示在可測空間中,令聯合可測損失 ℓ(h,z) 取值於 [0,1],定義
L(h)=EZ∼Pℓ(h,Z),mt=ℓ(ht,Zt),L=T1t=1∑TL(ht).
假設預測器的選擇及其風險可測。已保存預測器構成隨機批量規則,定義如下。
由 h1,…,hT 構成的混合規則按以下方式回答每次未來預測:獨立於訓練樣本從 P 抽取一個新測試樣本,並獨立於訓練和測試樣本從 {1,…,T} 中均勻重新選取 J,再使用 hJ。給定訓練樣本後,包括隨機選擇 J 在內的期望測試損失為
EJ,Zℓ(hJ,Z)=T1t=1∑TL(ht)=L.
這是 Gibbs 混合規則,不一定是單個確定性分類器。以下除 log2 外,對數均為自然對數。
一般有界損失的置信界
對任意 0<δ<1,以關於 Z1,…,ZT 的至少 1−δ 的概率,
L≤T1t=1∑Tmt+2Tlog(1/δ).這裏不需要可實現性假設。概率針對訓練樣本;隨機下標已在 L 內取平均。
令 Ft=σ(Z1,…,Zt),並令 F0 為平凡資訊。由於 ht 是 Ft−1-可測的,而 Zt 獨立於 Ft−1 且服從 P,由聯合可測性和 Fubini 定理得到的條件期望固定變量引理給出
E[mt∣Ft−1]=L(ht).令 Dt=L(ht)−mt。給定歷史後它的均值為零,且處於長度為一的區間。對條件分布應用 Hoeffding 引理,對 s>0 得到 E[esDt∣Ft−1]≤es2/8。反復取條件期望得到
Eexp(st=1∑TDt)≤eTs2/8.Markov 不等式給出 Pr(t∑Dt≥Tε)≤exp(−sTε+Ts2/8)。選 s=4ε 得到 e−2Tε2;令其等於 δ。所得事件蘊含所給的界。
證明透視
相對於預測器是新樣本
論證並不把 ht 當作獨立於整個訓練集的對象:後續樣本可能影響後續預測器。我們只使用 Zt 抽取時 ht 已由過去確定這一事實。如果預測器可以在預測前查看 Zt,條件期望恆等式就可能失效。
對錯誤次數更快的界
對二元分類使用零一損失,令 M=t∑mt。下一個論證利用給定歷史後的錯誤指標服從 Bernoulli 分布。當 M 很小時,它可能更緊。
對任意預先固定的 b>0 和 0<δ<1,以關於訓練樣本的至少 1−δ 的概率,
L≤T(1−e−b)bM+log(1/δ).參數 b 在看到樣本前選擇;根據數據選取它需要額外的同時控制。該界針對混合規則的風險,在獨立同分布假設下適用於任何可測的確定性在線規則。
給定 Ft−1,令 pt=L(ht),It=mt∈{0,1}。獨立性給出 E[It∣Ft−1]=pt。令 a=1−e−b,則
E[eapt−bIt∣Ft−1]=eapt(1−apt)≤1,其中用到 1−u≤e−u。反復取條件期望得 Eexp(at∑pt−bM)≤1。由 Markov 不等式,
Pr(at∑pt−bM≥log(1/δ))≤δ.在其補事件上整理即得結論。
若有限類 H 有 N 個成員,且存在一個固定的 h∗∈H 滿足 P(h∗(X)=Y)=0,則固定目標在一個概率為一的事件上正確標記全部 T 個樣本,因此不會被淘汰。採用固定平局規則的可測折半算法在該事件上至多犯 k=⌊log2N⌋ 次錯誤。取 b=log2,以至少 1−δ 的概率有
L≤T2(klog2+log(1/δ)).
這裏用固定目標和獨立同分布可實現性,保證在線錯誤界幾乎必然成立。T 較小時右邊可能超過 1;風險始終不超過 1,因此可把界截斷為 1。
當 N=8、T=300、δ=0.05 時,k=⌊log28⌋=3。快速率界為 2(3log2+log20)/300=2(2.0794+2.9957)/300≈0.0338;一般有界損失界至多為 3/300+log20/600=0.01+0.0707≈0.0807。二者分別在其置信事件上約束同一個條件混合風險;二者都沒有說每個單獨保存的分類器具有該風險。
取 T=100、δ=0.05、M=0。取 b=log2,快速率界為 2log20/100≈0.0599,而一般界為 0+log20/200≈0.1224。當 M=0 時,快速率界仍按 1/T 衰減,而一般界的衰減不可能快於 1/T;這正是額外的 Bernoulli 結構發揮作用的情形。
取 N=8、k=3、T=10、δ=0.05。快速率的表達式為 2(2.0794+2.9957)/10≈1.015,超過 1;風險始終不超過 1,所以界被截斷為 1,沒有提供任何資訊。至多三次錯誤時的一般界仍給出 0.3+log20/20≈0.3+0.387=0.687。兩個界並無一致的優劣:T 大而 M 小時快速率較好,T 非常小時平方根界可能較好。
快速率界是對在抽樣之前固定的 b 證明的。取使右邊對觀察到的 M 最小的 b,並不在該定理涵蓋之內,因為指數矩論證只對每個固定的 b 分別控制 Eexp(at∑pt−bM)。依賴數據的選取需要同時控制,例如對有限的取值網格用並集界,並把 δ 分給網格中的各個值。
指標 mt 是不同預測器 ht 的損失,每個都只在它尚未見過的那一個樣本上量度。它們的和 M 不是任何單個分類器的訓練誤差,上述界也不適用於看完最後一個樣本後再選取的預測器 hT+1;它們適用的是已保存預測器 h1,…,hT 的平均風險 L。
如果只抽取一次下標會怎樣?
反例模式
平均值可以掩蓋差的已保存預測器
假設分布的標籤始終為 0,在線規則先保存一個始終預測 1 的分類器,然後保存九個始終預測 0 的分類器。這十個風險為 1,0,…,0,所以 L=0.1。如果均勻抽取一次下標 J,然後將它固定為部署的分類器,則它的總體風險以概率 0.1 為 1,否則為 0。單憑 L 的界,不能保證所選單個 hJ 的風險必然不超過 0.1。
每次預測都重新獨立抽取下標實現的是混合損失。只抽一次則得到隨機分類器;給定樣本後對 J 取期望,其風險仍等於同一平均值,但實際選中分類器的風險可能變化。例如,對任一給定訓練樣本,Markov 不等式給出 PrJ(L(hJ)>L/η)≤η,其中 0<η<1。與概率至少 1−δ 的樣本事件結合,總失敗概率至多為 δ+η。另行驗證或選擇也是一種方法。
練習與解答
快速檢查
(一個在線二元學習器在 T=200 個獨立同分布輪次中幾乎必然至多犯兩次錯。取 b=log2,給出 δ=0.1 時混合風險的快速率界。)
代入 M≤2、b=log2 及 1−e−b=1/2。
解答 · 答案
以至少 0.9 的概率,L≤2(2log2+log10)/200=2(1.3863+2.3026)/200≈0.0369。
快速檢查
(若所有保存的分類器總體風險都為 0.2,混合風險是多少?任取其中一個分類器的風險是多少?)
解答 · 答案
二者都是 0.2:混合風險是 T 個相等數值的平均,而每個單獨分類器的風險按假設都是 0.2。只有保存的風險互不相同時,這兩個概念才會有差別。
快速檢查
(如果允許 ht 在預測前讀取當前標籤,為甚麼一般證明會失效?)
解答 · 答案
此時給定過去後,當前樣本與選中的預測器不再獨立,因而 E[mt∣Ft−1]=L(ht) 未必成立,Dt 的條件均值也未必為零。
快速檢查
(在十個分類器的反例中,PrJ(L(hJ)>0.1) 是多少?)
數一數風險大於 0.1 的已保存分類器有幾個。
解答 · 答案
為 1/10:恰好一個已保存分類器的風險為 1>0.1,其餘九個風險為 0。雖然 L 恰為 0.1,這個事件的概率仍是 0.1。