標籤錯誤不一定使學習不可能
可實現的 PAC 學習假設每個觀察到的標籤都與目標概念一致。如果標籤偶爾翻轉,堅持擬合每個樣本的學習器可能拒絕一個相當有用的假設,或轉而擬合噪聲。解決方法不是忽視標籤假設,而是明確噪聲機制,並分析由此產生的觀測風險。
我們研究有限假設類上的二分類。精確模型使我們能夠比較相對被污染標籤的錯誤率和相對不可觀察的乾淨目標的錯誤率,也說明為甚麼噪聲接近二分之一時,學習在統計上更困難。這個保證針對特定的獨立噪聲模型,並不聲稱任意錯誤標注都無害。
乾淨誤差與觀測誤差
設 服從可測實例空間 上的概率分布 , 可測, 是有限非空的可測分類器集合。採樣前固定 、 和 。下文的對數均為自然對數。對 ,定義乾淨誤差
定義 9.1.1
(隨機分類噪聲)
在隨機分類噪聲模型中,標籤為 ,其中 是滿足 、且獨立於 的 Bernoulli 隨機變量。樣本使用的各對 是 的獨立同分布副本。假設 。學習器看到的是 ,而不是 或乾淨標籤。
令 為觀測標籤誤差。按 是否與 一致分類,得到關鍵恆等式
乾淨預測正確時,恰在噪聲位為一時變錯;乾淨預測錯誤時,恰在噪聲位為零時仍然錯誤。由於 ,按觀測誤差排序與按乾淨誤差排序相同。但兩種誤差並不相等:即使目標 的觀測風險也為 。
例題 9.1.2
(數值比較)
若 ,乾淨誤差為 的分類器,其觀測誤差為 。另一個乾淨誤差為 的分類器,觀測誤差為 。後者仍較差,但觀測差距 小於乾淨差距 。因此需要足夠樣本才能克服抽樣波動、檢測小差距。
有限類學習保證
給定 個獨立受噪聲污染的樣本 ,定義
選擇任一經驗風險最小化解 ,並固定平局規則。由於類有限,最小值存在。算法比較經驗誤差時不需要知道 ;但下面的樣本量保證依賴於它。搜索整個類可能在計算上昂貴,因此統計界本身並不證明高效學習。
定理 9.1.3
(獨立標籤翻轉下的乾淨超額誤差)
對 、,令
以至少 的概率(概率針對受噪聲污染的樣本),
因此,對 ,若
則以至少 的概率,乾淨超額誤差不超過 。若 ,最小乾淨誤差為零。
證明
(一致偏差,再把觀測風險換成乾淨風險)
對固定的 ,指示變量 相互獨立,取值在 ,均值為 。雙側 Hoeffding 不等式和並集界給出
在其補事件上,選 。風險恆等式使 也最小化 。由經驗最小化及兩次一致偏差界,
減去 並除以正因子 ,得到乾淨誤差界。代入所示樣本量即可保證 。
證明透視
噪聲帶來的代價出現在哪裏
並集界一致地控制含噪經驗誤差,因此對看到樣本後選出的假設仍然有效。因子 只在將觀測風險差距轉成乾淨風險差距時出現。當 接近 ,此因子的倒數放大估計誤差;樣本界中的平方因子是該方法的一個充分上界,本身並不是匹配下界。
例題 9.1.4
(一個具體的樣本量)
例如,取 、、、,上述條件為 ; 足夠。這個不依賴分布的保守數值不是每個類和分布的精確樣本需求。
在二分之一及其另一側會怎樣?
當 時,觀測標籤是獨立公平位,與 無關,所以恆等式變成對每個 都有 。資訊損失可以精確說明。
命題 9.1.5
(噪聲率為二分之一時無法學習)
設實例空間只有一個點,兩個可能的目標分別是常值零和常值一,噪聲率為 。對任何學習器,無論是否隨機化、使用多少個獨立污染樣本,兩個目標中至少有一個滿足:輸出的乾淨誤差小於 的概率至多為 。
證明
(兩個目標產生相同的數據)
在任一目標下,每個觀測標籤都是獨立公平位,所以整個樣本的分布相同,學習器輸出的分布也相同。要使乾淨誤差小於 ,學習器必須在該單點預測正確的常值。若它以概率 輸出零,則在兩個目標下的成功概率分別為 和 ,其中至少一個不超過 。即使學習器隨機化、樣本數任意大,這仍然成立。
若已知 ,排序是反轉而非消失。翻轉每個觀測標籤,可將噪聲率變為 ,繼而應用前面的分析。若噪聲率和目標均未知,不能直接假定排序方向相同。閾值 是所述標籤翻轉模型的性質,不是所有噪聲學習問題的普適邊界。
例題 9.1.6
(已知噪聲率大於二分之一)
設噪聲率 已知,某分類器的乾淨誤差為 。翻轉之前,它的觀測誤差為 ,而目標本身的觀測誤差是 :排序被反轉。學習器把收到的每個標籤翻轉後,噪聲率變為 ,同一個分類器的觀測誤差為 ,與 一致。此時在翻轉後的標籤上做經驗風險最小化,會偏好乾淨誤差較小的假設。若學習器不知道 是 還是 ,就無法選擇方向,這正是未知情形被排除的原因。
反例模式
任意錯誤標注可能反轉偏好
令 、 均勻,乾淨目標處處為 。設 的標籤從不翻轉, 的標籤總是翻轉。分類器 的觀測風險為零,乾淨誤差卻為 ;目標的觀測風險為 ,乾淨誤差為零。由於翻轉概率依賴 ,且在一點超過二分之一,常數獨立噪聲恆等式不適用。最小化受污染誤差因而可能偏好錯誤分類器。
常見錯誤
(堅持訓練誤差為零)
為無噪聲情形設計的一致假設學習器,在噪聲下會失效:只要有一個標籤被翻轉,連目標 也與樣本不一致。取 、 個例子,沒有任何標籤被翻轉的概率是 ,所以這種學習器以約 的概率拒絕 。補救辦法是最小化經驗誤差,容許一定比例的不一致。
常見錯誤
(把觀測差距當作乾淨差距)
定理把觀測差距除以 才得到乾淨差距。在 時, 的觀測風險差距對應 的乾淨差距。忘記這個除法,會把乾淨超額誤差低估為原來的五分之一。
練習與解答
快速檢查
(若 ,求乾淨誤差為 時的觀測誤差;並在同一模型下,由觀測誤差 還原乾淨誤差。)
兩個方向都使用 。
解答 · 答案
。反過來,。
快速檢查
(對 、、,寫出 時的一致半徑 ,並給出所得的乾淨超額誤差界。)
先算 。
解答 · 答案
,定理給出超額誤差至多為 ,概率至少為 。
快速檢查
(為甚麼當 時,即使有無限多個獨立樣本,學習器在單點例子中也無法區分兩個常值目標?)
比較兩個目標下數據的分布。
解答 · 答案
在任一目標下,每個觀測標籤都是獨立公平位;整個數據分布完全相同,所以觀察更多數據也不能區分這兩個假設。對任何隨機化的預測,兩個成功概率之和為一。
快速檢查
(設已知 ,標籤以這個常數比率獨立翻轉。若學習器把收到的每個標籤翻轉,會怎樣?)
問翻轉後的標籤何時與 不同。
解答 · 答案
所得標籤與 不同,恰當原先的噪聲位為零,概率為 。各例子之間的獨立性保持不變,小於二分之一的分析因此適用。