合取式描述一個區域:規則中的每個文字都必須成立。析取範式(DNF)描述這些區域的並:只要至少一個項成立,輸入就是正例。我們不知道每個正例是由哪一項產生的,還能高效學習嗎?當每項使用的變量數至多為固定常數時,可以列出所有可能的短項,再刪除與負樣本矛盾的項。如果允許寬度增長,同樣的構造可能大得多。
本節使用可實現、無噪聲的 PAC 模型。證明分開處理兩個問題:算法必須確實找到一個與樣本一致的規則;然後樣本界必須控制看過樣本後才選出的規則。有限類保證解決第二個問題,本身並不提供高效算法。
項、寬度與學習模型
固定整數 和 ,輸入空間為 。
定義 1.5.1
(項與寬度為 k 的 DNF)
文字是 或 。一個項是至多 個文字的合取,各文字使用不同變量;空合取的值為 1。寬度為 的 DNF 是這些項任意子集的析取;空析取的值為 0。
這個表中恰有
個不同的語法項:選擇 個變量,並為每個變量選擇正負號。一個 DNF 可以使用這 項中的任意多個。
常見錯誤
(寬度不是項數)
寬度限制的是每個項的文字數,而非項數。至多有 項、但每項可任意長的 DNF 是另一類;下面的算法沒有證明那一類可高效學習。
未知的固定寬度 目標 給獨立樣本 標註,其中 獨立同分布於 上任意分布 ,且 。假設 的總體風險為
目標和分布在抽樣前固定,學習器不知道它們。我們的目標是 下的預測誤差,不要求恢復目標公式的精確寫法。
刪除與負例矛盾的項
令 為全部 個項的固定列表。開始時保留所有項。對每個標籤為 0 的樣本點,刪除在該點取值為 1 的所有保留項;刪除過程中忽略正例。輸出剩餘項的析取 ;若沒有剩餘項,則輸出 0。
定理 1.5.2
(一致性與單側預測)
對於任何由寬度 目標標註的樣本,該算法輸出與樣本一致的寬度 DNF。而且對每個 ,
因此可能發生的錯誤是假陽性,不是假陰性。
證明
(目標項從不被刪除)
目標中出現的每一項在每個負例上都取 0:若某項取 1,它們的析取 在該點便為 1。所以目標項都不會被刪除。因此只要 ,至少一個保留下來的目標項在 處取 1,故 。這包括每個正訓練點。另一方面,負訓練點會刪除所有在它上面取 1 的項,因此沒有保留項在該點觸發, 預測 0。故 在兩種標籤上均與樣本一致。論證同樣適用於常零目標、由空項表示的常一目標,以及沒有負例的樣本。
證明透視
包含關係的方向是甚麼?
刪除析取項會使析取式更難成立。但每個目標項都存活,輸出仍包含所有目標項,也可能包含額外項。因此輸出的正區域包含目標的正區域。這與在一個合取式中保留額外文字所得到的包含方向相反。可實現性恰好用了一次,即保證每個目標項在每個負例上都取 0;正例從不被檢查,卻自動被擬合。
例題 1.5.3
(一致但不等於目標)
取 、,目標為 。觀察到 標籤為 1, 標籤為 0。初始項為 。負例刪除 ,剩餘 。它符合兩個觀察值,卻在目標值為 0 的 上預測 1。若 對 賦予正概率,這個樣本可能留下正的總體誤差。樣本一致不等於處處相等。
例題 1.5.4
(常值目標)
令 、。若 (空項),且樣本只含正例,則沒有任何項被刪除, 是全部五個項的析取,其中含有項 ,因此處處等於 :與 一致。若 (空析取),且樣本含負例 和 ,則 刪除 , 刪除 。沒有項剩下,輸出為空析取 ,同樣等於 。若只有單個負例 ,輸出會是 ,在 上出現假陽性。
從有限假設得到 PAC 界
定理 1.5.5
(分布無關的可實現保證)
設 。如果
則對每個分布 和每個寬度 目標,刪除學習器以至少 的樣本概率滿足 。對數為自然對數。
證明
(語法假設的計數)
假設類在抽樣前固定。每個假設對應 的一個子集,因此語法假設至多有 個;不同子集可能定義相同函數,這只使上界較鬆。固定風險 的任意假設 ,獨立性給出
對固定假設類取並界,可知存在任何風險至少為 且與樣本一致的假設,其概率至多為 。在補事件上,每個一致假設的風險都小於 。前一條定理保證刪除算法依賴樣本的輸出也是一致假設,因此滿足這一結論。
證明透視
為甚麼依賴樣本的輸出也被涵蓋
這裏有依次出現的三個成分。至多 個語法假設構成的類在抽樣前固定,這使得對它取並界是合理的。對每個固定的、滿足 的 , 次抽樣的獨立性給出因子 。並界隨後產生一個概率至少為 的事件,在其上類中每個一致成員的風險都很小。學習器的輸出是看過樣本後選出的某個一致成員,因此落在該事件的結論之內;整個論證從不假設輸出與樣本獨立。
不能把最終輸出當成獨立於樣本預先固定的假設。定理給出充分樣本量,並不宣稱最優。
例題 1.5.6
(、 時的樣本量)
此時 。取 、。定理要求 ,所以 個樣本即可。該界關於 線性增長,這就是為甚麼只有固定 時它才關於 保持多項式。
「高效」依賴甚麼
對於每個負例,計算所有項至多需要 次文字操作。因此列出所有項並處理 個樣本需要 次操作(包括完整讀取輸入位),顯式列表佔 空間,不計輸入儲存。固定 時,,所以算法和上述樣本界都關於 和 為多項式。
如果 ,則 ,我們的顯式展開需要指數資源。這是本算法的局限,並不證明所有可能的 DNF 學習器都有計算下界。
常見錯誤
(樣本保證不等於算法)
有限類的界說明該類中任何一致的成員都能推廣,卻沒有說明如何找到這樣的成員。即使 固定,對 個語法假設做暴力搜索也不高效。真正提供一致輸出的是刪除規則,它的運行時間關於 和 為多項式。
上述保證依賴無噪聲可實現性,下面的例子說明這一點。
反例模式
一個被翻轉的標籤刪除了目標項
取 、,目標 , 均勻分布於 。設 處的標籤被錯誤記錄為 ,而 的標籤 正確。 處的負例記錄刪除在該點取 1 的每個項:、 和 。剩下 和 ,故 。它與所記錄的樣本一致,因為 、。但 而 :這是假陰性,所以 ,單側結論不再成立。證明所需要的恰恰是存活不變量,即沒有目標項被刪除。這個例子本身沒有分析某一種隨機噪聲模型。
練習與解答
快速檢查
(計算 、 時的 。這計算的是公式數還是候選項數?)
對 求 之和。
解答 · 答案
個候選項。這些項的語法析取至多有 個。
快速檢查
(對 、 和負例 ,哪些候選項經過該負例後存活?)
分別計算 在 處的值。
解答 · 答案
在 上取 0 的 和 存活;在該點取 1 的 被刪除。
快速檢查
(為甚麼在可實現模型中,學習器忽略正例仍能與它們一致?)
正例的標籤從何而來?
解答 · 答案
每個正例都有一個為真的目標項,而正確標記的負例不會刪除任何目標項,所以該項存活並使 預測 1。
快速檢查
(定理是否說明寬度 的 DNF 至多有 項?當 時,它是否給出多項式時間算法?)
究竟限制了甚麼?
解答 · 答案
否: 限制每項的文字數,公式可有很多項。對於 ,這個顯式算法的列表有 項,運行時間不是多項式。
快速檢查
(為甚麼不能直接對依賴數據的最終輸出使用固定假設的一致概率公式?)
哪個對象在抽樣前固定,哪個不是?
解答 · 答案
輸出隨樣本變化。對固定類取並界得到一個對所有一致候選同時成立的高概率事件,其中包括輸出。