在可實現學習中,每個標籤都與某個目標假設一致。在不可知學習中,即使最好的假設也可能犯錯。要做到接近最好的假設,學習器必須檢測許多點上標籤的細微偏差。我們在一個被打散的集合上構造含噪分布族,證明樣本太少時,超額風險以常數概率過大。證明允許隨機化和非正規學習器。
困難分布族
定義 2.4.1
(被打散集合上的困難含噪分布族)
設二元假設類 打散互異點 ,其中 。也就是說,每個符號向量 都能由 的某個假設在這些點上實現。固定 。對每個 ,定義分布 :先從這 個點中均勻抽取 ,再抽取 ,使
標籤有噪聲,但 是逐點 Bayes 最優標記,且 中有成員實現它。
若二元分類器 在 個點中有 個與 不同,則
事實上,預測 的條件錯誤率為 ,預測相反符號時為 。即使輸出不屬於 ,只要它在每個點輸出二元標籤,該恆等式仍成立。
兩個檢驗不可能同時過於準確
我們使用以下有限樣本檢驗不等式。對有限集合上的分布 ,令 ,,端點採用通常約定,對數為自然對數。則
這稱為 Pinsker 不等式。在這裏的有限情形中,可以選擇達到總變差的事件 ,對 及其補集應用對數和不等式,再使用 Bernoulli 參數滿足的 ,其中 。後者可由對 的二階導數 得到,因為在 處函數值和一階導數都為零;邊界情形取極限。
對先驗概率相等、根據數據猜測分布是 還是 的任何檢驗,其平均錯誤概率至少為
若檢驗在事件 上輸出「」,平均錯誤為 。對檢驗使用的獨立隨機種子取平均後,同一不等式仍成立。
單個座標難以推斷
引理 2.4.2
(由含噪標籤猜測單個符號)
固定指標 ,並固定 的符號 。令 在 上均勻,學習器(可帶獨立種子而隨機化)根據來自 的 個獨立同分布樣本猜測 。它猜錯的概率至少為
在不揭示其他符號時同樣成立。
證明
(對乘積分布使用 Pinsker 不等式)
固定指標 ,並將所有 的符號 作為額外資訊告訴學習器。令 和 表示其他符號固定且分別有 和 的兩個分布。對數為自然對數。它們的單樣本 KL 散度為
因子 是觀察到 的概率;在其他每個輸入點,兩個標籤分布一致。對 個獨立樣本,KL 散度為此值的 倍。由於 ,
由 Pinsker 不等式和二元檢驗界,即使已經知道其他符號,在其他符號固定時,對均勻的 、樣本和獨立種子取平均,錯誤猜測 的概率仍至少為
當 較大時,該界可能為負,此時只是沒有提供資訊。它適用於學習器在 上的預測,包括使用獨立內部隨機性計算出的預測。揭示額外資訊只會使檢驗更容易,所以沒有得到其他符號的學習器也滿足同一下界。
先平均,再固定一個困難分布
定理 2.4.3
(具體的不可知樣本下界)
設 且 。對任何由 個帶標籤樣本可測地輸出二元分類器的學習器,允許其使用獨立隨機種子;若
則上述分布族中存在一個固定的 ,使得以關於樣本與學習器隨機性的至少 的概率,
因此,在這一範圍內,若分布無關的不可知保證要求失敗概率嚴格小於 ,當 時必須有 。
證明
(對隨機符號取平均)
取 ,並且只在證明中令各符號獨立均勻。樣本量條件使 。對座標檢驗界先按其他符號取平均,再對 求和;由線性性,對符號、樣本和獨立學習器種子取平均後的錯誤比例期望至少為 。由超額風險恆等式,
對有限多個符號向量取平均,說明至少有一個固定的 使期望超額風險至少為 。對這個分布,超額量 位於 。若 ,則
困難的 在算法確定後選取,但在樣本和隨機種子抽取之前固定;它不會響應實際抽到的樣本而改變。
證明透視
隨機目標只是證明工具
打散只用一次:它使 Bayes 標記 屬於 ,於是類內最優風險為 ,超額風險恰為 。樣本量條件也只用一次:它使 ,把座標界變成每個符號至少 的錯誤概率。核心的一步是對隨機符號取平均,這使所有座標對稱,引理便可逐個座標應用;然後再取出一個期望超額風險至少為 的固定 。
最後一步把期望換成概率。它要求超額風險 被 界住, 就在這裏起作用:。若允許在看到每個樣本後再選目標,那將是不同且更弱的陳述。
例題 2.4.4
(困難分布族中 的超額風險)
取 、、。在 處標籤以概率 為 ,在 處標籤以概率 為 。Bayes 分類器 在每個點上的錯誤為 ,所以 。分類器 在 處正確(錯誤 ),在 處錯誤(錯誤 ),風險為 。超額風險為 ,與 一致。
例題 2.4.5
(應用下界)
取 、、,所述條件恰好取等。此時 ;定理保證在這些被打散的點上存在一個固定含噪分布,使超額風險以至少 的概率超過 。若不知道學習器,定理不會指出具體是哪一個分布。
例題 2.4.6
(座標界不提供資訊的情形)
取 、。單樣本散度為 ,所以 個樣本時精確值約為 ,由 Pinsker 不等式,總變差至多為 。文中使用的放寬界為 ,得到總變差至多為一,錯誤界為 。這是有用範圍的邊緣:從 起,放寬後的引理不再提供資訊,雖然精確散度在這裏仍能給出非零的界。定理的條件 使 遠在有用範圍之內。
適用範圍與可實現性警示
反例模式
困難分布族不是無噪聲可實現的
當 時,每個點上的兩種標籤都有正概率出現。雖然 Bayes 標記屬於 ,但沒有確定性分類器能在 上取得零風險。把假設無噪聲可實現性的定理應用到這個分布族,會忽略造成下界的標籤不確定性。
常數 為了使證明透明而選取,並不聲稱最優。我們沒有證明任意置信參數 的依賴、計算下界,或假設類沒有打散指定點時的下界。論證也不要求學習器輸出 中的成員。
常見錯誤
(準確度目標縮小時卻固定偏差)
困難分布族中的超額風險為 ,所以偏差 必須隨 縮放。若固定 ,同一論證只迫使需要約 個樣本,期望超額風險才可能降到 以下;這是 的量級,不會隨 增長。正是 的選擇產生了 的依賴。
常見錯誤
(把概率 當成置信參數)
定理對一個固定常數證明失敗概率至少為 。它沒有說明當允許的失敗概率 趨於零時樣本量必須如何增長,也沒有排除這種增長。失敗概率嚴格小於 的分布無關保證需要 ;僅此而已。
練習與解答
快速檢查
(若分類器只在 個點中的一個上與 不同,超額風險是多少?)
用「困難分布族」一節的恆等式。
解答 · 答案
。
快速檢查
(當 時,困難分布族中的類內最優風險是多少?)
它就是每個點上的 Bayes 錯誤。
解答 · 答案
。
快速檢查
(在檢驗 對 時,為甚麼只有 才產生非零 KL 散度?)
比較兩個分布在 的輸入 處的情形。
解答 · 答案
兩個候選分布的輸入分布相同,在其他每個點上的條件標籤分布也相同。在 處散度為 ,再乘以 。
快速檢查
(若 、,定理中下界條件覆蓋的最大整數 是多少?)
計算 。
解答 · 答案
。
快速檢查
(證明使用隨機符號,為甚麼最終定理仍給出一個固定困難分布?)
想一想有限個分布的平均意味著甚麼。
解答 · 答案
有限分布族的平均至少為 ,故某個固定成員的期望至少為該值。對這個分布, 給出 。