學習算法可以通過改變後續輪次中各樣本的重要程度來改進弱規則;也可以查詢有標籤分布的平均性質,而不直接要求單個有標籤樣本。這是兩個不同的模型:提升法結合在不斷變化的權重下產生的假設,統計查詢學習則控制提供給學習算法的資訊精度。兩者的保證都必須先說明分布和誤差標準。
加權多數投票
定義 6.1.1
(指數重新加權的加權多數投票)
固定非空有標籤樣本 ,其中整數 ,;假設每個基礎規則 的輸出也屬於 。初始權重為 。第 輪選擇一個規則,其加權訓練誤差為
當 時定義
其中 使權重之和為一。歸一化之前,錯分樣本的權重乘以 ,正確樣本的權重乘以 。最終得分為 ,分類器根據其符號預測。得分為零時需要約定;下面的界將平局計作錯誤,因此對任何固定平局處理方式都成立。
上述有限更新要求 。若 ,當前規則已正確分類整個訓練樣本,可以停止。若 ,其係數為零;若誤差大於 ,係數為負。這些輪次不滿足下文的正弱優勢條件。若假設類允許取反,翻轉規則會反轉其誤差。 時,所寫的有限更新沒有定義。
例題 6.1.2
(重新加權四個樣本)
四個樣本初始等權,設 僅錯分一個,則 、,歸一化常數為 。更新後,錯分樣本的權重是 ,每個正確樣本的權重是 。第二個規則須按這些新權重評估,而不是按原先的均勻權重評估。
遞減的訓練誤差界
定理 6.1.3
(加權投票的訓練誤差界)
若每輪都滿足 並使用上述更新,則滿足 的樣本比例至多為
若每輪 ,其中固定的 ,則上界至多為 。
證明
(指數損失控制錯誤指示函數)
對任意實數 ,有 。從 出發迭代更新,得到
對 求和並使用 ,可知平均指數損失等於 ,它控制非正間隔的樣本比例。每輪有
寫 ,其中 ,則 。逐輪相乘即得結論。
證明透視
界的每一步從何而來
這個證明含一個不等式和兩個恆等式。不等式 是唯一損失資訊的地方:它把錯誤個數換成光滑的損失。第一個恆等式 成立,是因為每次更新都把權重乘以 再除以 ,指數相加恰為 ;歸一化於是迫使 的平均值恰好等於 。第二個恆等式在所選的 下計算 ;這個 正是 的極小點,因此沒有其他投票權重能使這個因子更小。弱優勢假設只在最後才出現: 當且僅當 ,否則 ,所以一致的優勢 才使乘積按幾何速度下降。論證中沒有任何地方涉及樣本如何產生,這正是結論只針對該樣本的原因。
例題 6.1.4
(沒有優勢的一輪)
延續四個樣本的例子。第一輪後權重為 ,權重大的點就是 錯分的那個。設 恰好在該點出錯,其餘三點正確。它在均勻權重下的訓練誤差是 ,但真正起作用的是它在 下的誤差 。於是 ,每個權重都乘以 ,,。這一輪不改變乘積界,只在得分中加上 。它就是定理允許的邊界情形 :沒有壞處,但必須有正優勢 才會出現小於 的因子 。
常見錯誤
(訓練誤差界不是泛化界)
人們容易把很小的 讀成「分類器在未來樣本上也準確」。該定理是關於固定訓練樣本及實際選出的假設的確定性結論,本身並不給出未來樣本上的誤差界;那需要額外的泛化論證,包括樣本及自適應選擇如何產生。定理也不保證每個遇到的分布下都存在具有所述優勢的弱學習器;這是提升分析的假設。下面的例子具體展示了這個差距。
反例模式
訓練誤差為零不代表總體誤差為零
令 上兩點等概率, 的標籤為 , 的標籤為 。處處預測 的規則具有總體錯誤率 。若獨立抽取的 個輸入恰好全為 ,這一事件概率為 ,則訓練誤差為零。泛化界控制此類誤導性樣本出現的概率,並不能使它們不可能發生。
統計查詢:以平均值作為介面
定義 6.1.5
(統計查詢預言機)
令 為實例空間 上有標籤對 的分布。對任意查詢函數 及容差 ,統計查詢預言機返回某個 ,滿足
統計查詢算法必須對容差內每一個允許的回答都有效,而不只是對精確期望有效。查詢函數、容差、查詢次數和運行時間都是模型的一部分。示性函數查詢 詢問 的錯誤率;若 輸出正負號,相關性查詢 詢問的是 。
命題 6.1.6
(以全新批次模擬統計查詢)
假設算法最多進行整數 次自適應查詢,每次均使用容差 。固定 。從 取得獨立同分布的有標籤樣本,每個查詢使用一批全新的
個樣本來回答,則所有回答均滿足容差的概率至少為 。
證明
(對互動記錄取條件,再用並集界)
在給定此前的全部查詢記錄以及選取下一查詢時使用的隨機選擇之後,當前查詢固定,而新一批樣本仍是來自 的獨立樣本。對取值於 的變量應用 Hoeffding 不等式,樣本均值偏離期望超過 的概率至多為 。此界對每一種此前記錄都成立,故無條件概率也滿足同樣的界。對至多 輪使用並集界得到結論。新樣本批次對於這個簡單的自適應論證至關重要:根據重複使用的數據集選擇查詢後,固定查詢的集中界不一定在條件下繼續成立。
這只建立了一個方向的模擬:隨機樣本可按上面的樣本成本近似有限次統計查詢回答。它並不意味著統計查詢預言機透露單個樣本,也不意味著所有使用樣本的算法都能由統計查詢高效實現。
例題 6.1.7
(自適應查詢的樣本預算)
某算法進行 次自適應查詢,容差為 ,要求所有回答都正確的概率至少為 ,即 。命題要求 ,所以每個查詢使用 個全新樣本,合共 個。在邊界情形 ,並集界是平凡的,需求為 ,即 個樣本。成本對 只是對數增長,對 卻是二次增長:把 減半至 ,因子 便乘以四。
例題 6.1.8
(解讀帶容差的回答)
假設 輸出正負號,對 的查詢返回 ,容差為 。真實相關性屬於 ,所以錯誤率屬於 。數值 只是區間中點的估計;轉換時必須保留容差。
常見錯誤
(回答給出的是保證範圍,而不是真值)
對上面的回答 ,若把錯誤率報告為恰好 ,或把 當作真實錯誤率交給後續步驟,都是錯的。區間 內的每個相關性都與該回答相容,所以只有 得到證明。由於 ,相關性的容差 對應錯誤率的容差 。統計查詢算法必須對容差內的每個回答都保持正確,而不是只對中點正確。
練習與解答
快速檢查
(四個樣本等權,規則錯分一個。求更新後該點的權重和其他三個點的權重之和。)
先算 ,再算 和 。
解答 · 答案
錯分點獲得權重 ,正確點合計權重也是 。其實 給出 ;歸一化之前,錯分點為 ,三個正確點合計為 ,兩邊各佔總和的一半。
快速檢查
(若某輪提升的誤差為 ,計算 ,並求連續十輪都具有此誤差時的乘積界。)
使用 。
解答 · 答案
,故訓練誤差的乘積界為 。取 的較弱指數界為 。這些界不一定緊。
快速檢查
(某錯誤率示性函數查詢的回答為 、容差為 。能證明真實錯誤率位於甚麼範圍?)
回答在兩個方向上最多可偏離容差。
解答 · 答案
真實錯誤率在 中。這裏端點已是有效概率;一般情況下要將容差區間與 取交集。
重複使用同一樣本:固定查詢論證在哪裏失效
上一節的證明為每個自適應統計查詢抽取一批全新的獨立同分布樣本。回答第 個查詢所用的樣本,與決定 的全部資訊相互獨立。因此我們可以對互動記錄取條件,把 視為固定查詢,再對有界的固定查詢使用一般的集中性結論。以下例子說明:重複使用同一個數據集時,這一步條件化並沒有自動成立的對應版本。
反例模式
自適應地重複使用樣本
設定。 令 ,。設 在 上均勻分布,且總有 。獨立同分布地抽取一個樣本 ,並以經驗平均 回答每個查詢 。
第一階段(非自適應)。 提出 個單點查詢 ,每個的期望值都是 。 的回答為正,當且僅當 出現在 中。因此這些回答恰好揭示了集合 。
第二階段(自適應)。 只根據這些回答,選取 。對任何樣本都有 。令 為一次獨立的新抽樣。給定互動記錄後,,所以誤差至少為 。查詢總數為 。
第一階段看似無害。 對 個點對使用並集界,可知各 兩兩不同的概率至少為 。在該事件上,每個單點回答為 或 。因此每個回答與 的差都小於 ,落在容差 之內。然而最後一個回答違反了 。
所有查詢都取值於 。 的選擇只依賴先前的回答。每個查詢若事先固定,並在全新的獨立數據上計算,都滿足一般的集中性。失效的是獨立性: 透過互動記錄成為 的函數。在同一個 上,它不再是固定查詢。
適用範圍。 這個例子並不說明所有重複使用數據集的方法都會失敗,也不說明不可能存在高概率的一致界。它只說明簡單的條件化固定查詢證明不能直接移植到這裏。它不是針對所有可重用數據算法的下界。
快速檢查
(對一般的 和 ,證明 ,並且最終差距至少為 。解釋為何這個下界只有在 時才為正。)
比較 在 上的經驗平均與它在新抽樣上的均值。
解答 · 答案
樣本中不同的輸入至多有 個,故 。給定互動記錄後,在新的獨立抽樣上該查詢的總體均值為 ,而它在 上的經驗平均為 。兩者之差是 。這個下界恰在 時嚴格為正;當 時它未必提供有用資訊。