有限類定理可以保證一致假設具有泛化能力,卻未必解決如何計算出這樣一個假設。單調合取式讓我們同時看到這兩個部分:簡單算法能找到一致規則,而獨立樣本論證能控制其總體誤差。結果與分布無關,但依賴無噪聲的可實現性。
模型與刪除規則
定義 1.2.1
(單調合取式、目標與風險)
設 、,對 定義單調合取式
空合取式是恆為 1 的常數。未知目標是某個固定的 ; 獨立同分布於 上任意固定分布 ,標籤無噪聲:。候選規則 的風險為 。
學習器從 開始。對每個標籤為 1 的樣本,它刪除所有滿足 的座標 。更新時忽略負樣本,最後輸出 。計算至多檢查 個座標值,除樣本本身外使用 工作儲存空間。若沒有正樣本,它輸出所有 個變量的合取式。
例題 1.2.2
(用正樣本刪除座標)
當 時,取目標 。正樣本 和 分別刪除座標 4 和 2,剩下 。刪除步驟不需要負樣本 ;所得合取式將它標為零。另一個樣本即使也一致,仍可能留下額外座標。
例題 1.2.3
(沒有正樣本:所有變量的合取式)
設 ,目標為 。假設樣本只含負樣本 和 。沒有座標被刪除,所以 ,輸出為 。兩個負樣本在各自的座標中都有零,輸出將它們標為 0,因此是一致的。它的風險是 的概率,即目標的正點中除 以外的部分。若 的大部分質量落在那裏,風險便很大。這並不矛盾:這樣的樣本正是「樣本量太小、沒有見到正樣本」的罕見事件,而下面的定理說明 足夠大時這種事件的概率很小。
例題 1.2.4
(代入樣本量的界)
取 、、。則 ,,所以
定理保證的最小整數是 。這個類有 個成員, 卻只有幾百:界對 是線性的,因為類只透過 進入。把 減半為 會使要求加倍,,即 ;把 平方為 只增加約 個樣本。
輸出為何一致
引理 1.2.5
(刪除式學習器的不變量)
在無噪聲的可實現模型中,刪除式學習器維持的集合 在每一步都滿足 。因此輸出 與全部 個樣本一致,並且對每個 , 蘊含 。
證明
(目標座標從不被刪除)
每個真正的正樣本對所有 都滿足 。因此目標座標絕不會被刪除,在每一步都有 。結束時,每個觀察到的正樣本在每個保留座標上都是 1,所以被 標為 1。每個觀察到的負樣本至少有一個目標座標為零;由於所有目標座標都保留下來, 將它標為 0。因此即使沒有正樣本,輸出也與全部 個樣本一致。
此外, 蘊含 。學習器可能因為保留多餘變量而出現假負錯誤,但在上述假設下不會出現假正錯誤。這種單側錯誤是該算法的不變量,不是任意一致學習器的性質。
證明透視
保留額外變量會縮小正區域
唯一不顯然的一步,是把刪除規則讀成關於指標的陳述:只有當某個標籤為 1 的樣本在某座標上為零時,該座標才被刪除。證明用到兩個假設。標籤無噪聲,使每個標籤為 1 的樣本都是目標的真正正樣本,於是所有目標座標在其上都等於 1,沒有一個會被刪除。可實現性使每個負樣本違反目標,所以它在某個目標座標上為零。
兩個包含關係方向相反。對指標集合有 ;對正區域有 ,因為給合取式加上變量會使它更難滿足。前者給出負樣本上的一致性,後者給出沒有假正錯誤。混淆這兩個方向會顛倒對假正和假負錯誤的結論。
論證得以完結,是因為每個保留的座標都從未在正樣本上見到為 0,而目標座標絕不會被刪除。若有一個正標籤被破壞,第一步就失效,「預測與識別目標」一節末尾會說明。
分布無關的樣本保證
定理 1.2.6
(具體的可實現情形 PAC 保證)
固定 和 。如果
則對樣本取概率,輸出滿足 的概率至少為 。對數均為自然對數。該界對每個 和類中的每個目標合取式成立。
證明
(對所有合取式作並集界)
包括空合取式在內,共有 個合取式。固定一個滿足 的候選 。對每個獨立帶標籤樣本,它與目標一致的概率至多為 ,因此與全部 個樣本一致的概率至多為 。對這個固定有限類使用並集界,存在任何這樣的一致壞候選的概率至多為 。在其補事件上,每個一致候選的風險都小於 。刪除式學習器的輸出一致,所以滿足該界。
該界對所有分布一致成立,並非以某個有利樣本為條件。證明中使用了有限類,但算法無需枚舉全部 個候選。保證針對預測誤差,而非精確恢復目標變量集合。
揭示遺漏證據的另一種證明。 對每個座標,記 。在抽樣之前固定任意座標 。若 ,每個獨立樣本至少以 的概率提供刪除它的證據。該座標在全部 個樣本後存活的概率至多為 。如果沒有這樣的座標存活,一個假負結果必然滿足 且某個保留座標等於 0,所以並集界給出風險嚴格小於 。因此失敗概率至多為 。這個替代界可能比有限類界更鬆,但明確體現了稀有正樣本的作用。作並集界的事件不必獨立;獨立性用在 個樣本之間。
預測與識別目標
反例模式
相關變量妨礙精確識別
取 ,分布只支撐在 和 上。目標 和 在這個支撐集上給出相同標籤,儘管它們在 和 上不同。無論獲得多少來自該分布的獨立同分布帶標籤數據,都無法區分所選目標。兩個規則在 下都可以有零風險。分布無關的 PAC 準確性並不保證識別目標表示,也不保證在分布支撐集外的點上正確。
常見錯誤
(在負樣本上刪除座標)
很容易想到同樣用負樣本修剪,即刪除負樣本取 0 的每個座標。上面的例子已經說明這是錯的:目標為 時,負樣本 只在座標 3 上為 0,而座標 3 正是目標座標,這條規則會刪掉目標需要的變量。負樣本只說明某個目標座標為 0,卻沒有說明是哪一個。只有正樣本能提供刪除的證據。
常見錯誤
(把類的大小當成運行時間或樣本量)
證明數了全部 個合取式,但學習器從不列舉它們,樣本量只透過 依賴於這個類。運行時間是 ,樣本量對 是線性的。類的大小出現在分析中,不出現在算法中。
稀有證據也可能延遲學習,卻不違反定理。令目標為空合取式, 的概率為 , 的概率為 。若 次抽樣全是 ,其概率為 ,則沒有座標被刪除,輸出的風險為 。一次 抽樣是正樣本,會刪除每個座標,得到恆為一的目標。高概率界使誤導性樣本足夠稀有,而不是宣稱它們不可能發生。
任意標籤噪聲會破壞上述證明。當 、目標為 時,輸入 0 處一個被破壞成正標籤的樣本會刪除真實變量,此後輸出恆為 1,並可能產生假正錯誤。有噪聲的模型需要另外的假設和分析。
練習與解答
快速檢查
(當 時,處理正樣本 和 。輸出是甚麼?它將 標為何值?)
刪除每個正樣本取 0 的座標。
解答 · 答案
第一個正樣本刪除座標 3,第二個刪除座標 2。輸出為 ,將 標為 0。
快速檢查
(當 、、 時,給出定理所要求的充分整數樣本量。)
用自然對數代入,再向上取整。
解答 · 答案
取 。
快速檢查
(若未觀察到正樣本,在無噪聲可實現模型中輸出為何仍然一致?)
看負樣本對目標座標有何要求。
解答 · 答案
每個負樣本在某個目標座標上為零,而所有目標座標都保留在輸出中,所以輸出將每個負樣本標為 0。
快速檢查
(在 下風險為零是否意味著所選指標集合等於 ?說明理由。)
對照上面的雙變量例子。
解答 · 答案
不意味著。相關座標可以使不同合取式在 的整個支撐集上相同,如上面的雙變量例子。