統計查詢請求的是期望值,而不是單個帶標籤樣本。獨立標籤翻轉會以有結構的方式扭曲這些期望。若翻轉率已知且低於二分之一,每個有界的乾淨查詢都能轉換成有界的噪聲查詢。這種轉換在期望層面是精確的,但噪聲接近二分之一時,其容差必須變小。
定義 7.2.1
(已知噪聲率的分類噪聲)
設 位於可測實例空間 ,乾淨標籤為 ,其中目標 可測。觀察到的標籤為 ,其中 獨立於 ,滿足 ,並對每個樣本重新獨立抽取。假設已知噪聲率滿足 ,記
定義 7.2.2
(乾淨統計查詢 oracle)
乾淨統計查詢由可測函數 和容差 組成。查詢 oracle 可返回與 的距離不超過 的任意值。學習器必須適用於每個有效答案序列,包括自適應選擇的答案。
模擬任意查詢
定理 7.2.3
(有界噪聲查詢恢復乾淨期望)
假設精確翻轉率 已知。對任意乾淨查詢 ,定義
並提出噪聲查詢
則 ,且
因此,若噪聲 SQ 答案與其期望的距離至多為 ,將其除以 就得到容差為 的有效乾淨答案。
證明
(分離與標籤無關的部分和關於標籤的奇部分)
對 ,有 。此外,
因為 ,所以 。獨立性給出 ,故
取期望便得 (2)。在這個可實現模型中,計算實際上只需要 ;獨立性是充分條件。若干淨標籤本身隨機,相應的充分條件是 。如果只知道 的上界,用錯誤的 除一般會引入偏差;未知速率需要單獨的估計或學習論證。若噪聲 oracle 返回 ,滿足 ,則 。除法後的答案不一定位於 ;有效性只要求容差不等式。若約定還要求答案落在 ,將它裁剪到該區間不會增加其與乾淨期望的距離。
證明透視
為甚麼要縮放整個查詢
與標籤無關的部分 不受噪聲改變,而關於標籤的奇部分 被縮小為 倍。若只把後者乘以 ,結果可能超出允許範圍 。(1) 轉而把整個目標期望縮小為 倍,使查詢保持有界,再透過更小的容差支付反演代價。
例題 7.2.4
(校正分類誤差查詢)
設 ,令 。則 、,而 (1) 的有界查詢為
它取值 和 ,期望為 ,其中 。等價地,噪聲誤差滿足 。例如,、 時,。一般構造適用於所有有界查詢,而不只是誤差查詢。
概念視角代數
噪聲是縮小奇部分的算子
把查詢寫成 。由於 ,它的噪聲期望為 :噪聲不改變與標籤無關的偶部分,只把標籤的奇部分乘以 。要使它等於 ,就必須取 、,這正是 (1)。
例題 7.2.5
(帶噪聲 oracle 的相關性查詢)
設 ,即 ,並設 在質量為 的集合上與目標 一致、在其餘部分不一致,所以 。對 ,有 、、,期望為 。乾淨容差為 時,噪聲 oracle 可以相差 ,即可回答 內任何值。假設它回答 ,除以 得 ,與真值 相差 ,仍在容差內;另一個極端答案 給出 ,同樣相差 。因此兩端都滿足容差,與 (2) 的保證一致。
例題 7.2.6
(兩個邊界情形:無噪聲與重噪聲)
若 ,則 ,(1) 成為 ,因為 :這個構造原樣返回乾淨查詢。在 (3) 中取 、、。 時批量為 。 時 ,,約為前者的一百倍,與因子 吻合。當 時這個因子無界增長,這預示了下面的下界。
用新鮮噪聲樣本回答自適應查詢
定理 7.2.7
(可模擬有限的自適應 SQ 計算)
假設精確速率 已知,固定一對 ,並預先固定整數查詢上限 與容差 。假設確定性的乾淨 SQ 算法至多提出 個查詢,容差均為該 ,並對同一對 的每個有效答案序列都成功。給定 ,使用一批新鮮獨立樣本回答每個噪聲查詢,其批量為
將每批樣本平均值除以 。以至少 的概率,每個模擬答案對對應乾淨查詢都有效,因此乾淨算法成功。最多使用 個噪聲樣本。
證明
(對先前的自適應記錄取條件)
在某輪,以此前全部查詢和答案為條件。下一個查詢於是固定,而它的新鮮批次獨立於先前記錄。其轉換後查詢在 中有界。因此 Hoeffding 不等式將樣本均值偏離 超過 的條件概率控制為
令 為第 輪被到達且其答案無效的事件。這個估計對到達該輪的每段先前記錄都成立,故 。對 使用並集界,得到同時有效事件。在此事件上,由 (2),每個除法後的答案都是有效乾淨答案,儘管後續查詢依賴先前答案。乾淨算法的假設於是給出成功。對隨機化乾淨學習器,類似結論還需要乾淨保證適用於可依賴學習器隨機種子的有效自適應回答策略;乾淨失敗概率隨後與 相加。這裏沒有暗中假設這個更強量詞。
這是統計模擬上界。高效計算還要求查詢和乾淨學習器可高效求值。新鮮批次使條件集中論證直接成立;對自適應選擇的查詢重複使用同一批次,需要另行分析。
噪聲代價無法消除
上界含有 。一個兩目標問題說明,對單個乾淨查詢、常數容差和常數置信度, 確實必要。它沒有證明一般 SQ 計算對 、 或 的聯合依賴最優。
定理 7.2.8
(噪聲樣本的兩目標下界)
設 。在單點實例空間上,考慮兩個可能的恆定目標 和 ,標籤以速率 獨立翻轉。即使知道 ,任何使用固定最壞情況樣本數 、並對兩個目標都以至少 的概率輸出正確標籤的學習器,必須滿足
該結果包括使用此固定樣本預算的隨機化學習器;隨機樣本數需要單獨論證。乾淨問題可由容差 的單個查詢 解決,因為答案的符號就是目標標籤。這是例子上的下界,並非聲稱每個學習類都需要這麼多樣本。
證明
(兩個相近的乘積分布難以區分)
在目標為 時,一個噪聲標籤為 的概率是 ;在目標為 時,該概率為 。令 、 為兩個 標籤分布。其 Hellinger 親和度為
對 使用柯西–施瓦茨(Cauchy–Schwarz)不等式,得到
若學習器對兩個目標都以至少 的概率正確,則其輸出是一個對兩個分布錯誤概率均不超過 的檢驗。因此事件「輸出 」的概率差至少為 ,全變差至少為 。對隨機化學習器,可在兩個分布中加入同一個獨立隨機種子;親和度不變。故 ,並有
因為 且 。
當 時,兩個目標產生完全相同的噪聲標籤分布,故無論樣本數多少,都無法對兩個目標同時達到嚴格大於 的成功概率。這個極限中的不可能性解釋了為何 時不能反演 (1)。
反例模式
已知平均噪聲率不等於獨立噪聲
設 在 上均勻分布,始終取 ,並在 處以概率 、在 處以概率 翻轉標籤。平均翻轉率為 ,但翻轉並不獨立於 。對查詢 ,乾淨期望為 。在 (1) 中使用 得到 ;其噪聲期望仍為 ,不是 。因此除以 得 ,而非 :偏差 即使樣本無限也存在,且當 時模擬答案無效。這裏 ;問題是所需的條件縮放關係失敗。純無標籤查詢不受影響。
常見錯誤
(把觀察到的噪聲誤差當成乾淨誤差)
當 時,觀察誤差為 的假設,其誤差並不是 。觀察誤差為 ,所以乾淨誤差是 。即使完美的假設,觀察誤差也是 。在不同噪聲率之間比較觀察誤差,或把 當作必須突破的下限,都混淆了這兩個量。
常見錯誤
(對自適應查詢重複使用同一批樣本)
自適應模擬的證明先對至今的記錄取條件,再使用與它獨立的一批樣本。若用同一批樣本回答所有查詢,後面的查詢就依賴於由同一批樣本算出的先前答案,條件步驟便不再成立,Hoeffding 不等式也不能對它使用。樣本總量 正是為 批新鮮樣本付出的代價。
練習與解答
快速檢查
(純無標籤查詢。若 且 ,計算 。)
先求 和 。
解答 · 答案
此時 、,所以 。 等於 。在這個特殊情形,也可以直接查詢 而無需支付噪聲代價。
快速檢查
(相關性查詢。對 、,求轉換後的查詢及其期望。)
的哪一部分關於 是奇的?
解答 · 答案
、,故 ,且 。
快速檢查
(計算批量。若 、、、,求 (3) 給出的整數 。)
先算 。
解答 · 答案
,故 ;這裏使用自然對數。
快速檢查
(拋硬幣式噪聲。為甚麼 時模擬失敗?)
先看 ,再看單點實例空間。
解答 · 答案
此時 ,無法做除法。更根本地,在單點空間上,兩種恆定目標產生相同的獨立公平噪聲標籤,因此兩種目標的成功概率之和至多為一,不可能對二者同時以超過 的成功概率識別。
快速檢查
(置信度核算。若 個自適應查詢中每一個的條件批量失敗概率至多為 ,至少有一個失敗的概率是多少?)
各輪並不獨立。
解答 · 答案
對每一輪,只在該輪被執行時才定義失敗。對條件界取平均,其無條件失敗概率至多為 。並集界給出至多 ;各輪失敗不必獨立。