合取式只有一個共同要求:每個保留文字都必須為真。決策列表則能依次處理例外:如果某個文字為真,就給出一個標籤;否則嘗試下一條規則。最先匹配的規則決定輸出。我們將從可實現數據中高效找出一致列表,再證明其總體錯誤率以高概率較小。
規則、次序與學習任務
固定 ,令定義域 。可用文字是 和 ,其中 。
定義 1.4.1
(帶符號文字決策列表)
帶符號文字決策列表具有規則
之後跟一個預設標籤 。對輸入 ,返回第一個為真的文字 對應的 ;若沒有文字為真,返回 。空列表是常量分類器。
稍後再次出現同一文字不會改變函數,因為滿足它的輸入已經在第一次出現時停止;因此可以只考慮文字互異且 的列表。
概念視角結構
決策列表是一棵偏斜的決策樹
把每條規則 畫成一個檢驗 的節點:為真則走向標籤為 的葉子,為假則走向下一個節點。最後一條為假的分支終止於標籤為 的葉子。含 條規則的列表恰好就是這樣的樹:共 個檢驗,每個檢驗旁掛著一片葉子,通向預設標籤的路徑長度為 。
假設一個固定目標列表 無噪聲地標記數據: 獨立同分布於 上任意分布 ,且幾乎必然有 。樣本含 個帶標籤例子。風險是獨立輸入 上的 。
逐次剝離同標籤規則的學習器
保留一個活動樣本指標集合,初始為所有指標,並從空輸出列表開始。重複以下步驟:
- 若沒有指標剩餘,添加預設標籤 0 並停止。若所有剩餘標籤都等於同一個 ,添加預設標籤 並停止。
- 否則按固定順序搜索文字,找到一個在至少一個活動例子上為真、且所有滿足它的活動例子具有同一標籤 的文字。
- 添加 ,刪除所有滿足 的活動例子,再重複。若找不到這樣的文字,報告失敗。
覆蓋集合非空的條件防止規則沒有進展。此前選過的文字在每個剩餘例子上都為假,因此不能再次被選中。由於活動集合只會縮小,且所選文字的覆蓋非空,非預設規則至多有 條。在單位成本比特存取模型下,每輪對每個文字掃描至多 個例子,同時檢查覆蓋非空和標籤一致,因此時間為 。活動指標佔用 空間,輸出佔用 個字,均不包括樣本本身。
定理 1.4.2
(可實現決策列表可被一致學習)
若同一個目標列表正確標記每個樣本,則該過程永不報告失敗,必定終止,並輸出與整個樣本一致的列表。
證明
(一個不變量與一個合格文字)
每輪之後,活動例子恰好是不滿足任何已輸出文字的樣本;每個已刪除例子都被已輸出前綴正確標記;目標 仍正確標記每個活動例子。這個不變量初始成立,刪除覆蓋的同標籤集合後仍成立。只有當活動例子中兩種標籤都出現時,才進入步驟 2。至少有一個活動例子必須觸發目標的一條規則;否則每個活動例子都會得到同一個目標預設標籤。選擇目標中最早在任意活動例子上觸發的規則。之前的目標規則在所有活動例子上都不觸發,因此每個滿足該文字的活動例子都會到達這條規則,並具有它的標籤。於是該文字覆蓋一個非空的同標籤集合,搜索必定成功。這個存在性論證與搜索順序無關;固定順序使過程確定。
選中的規則恰好標記該輪刪除的例子;此前輸出的規則在當時的所有活動例子上均為假,因此之後的規則不能改變這些預測。預設標籤標記停止時剩下的所有例子。每個非預設步驟至少刪除一個例子且不能重複使用文字,所以算法終止,輸出一致。
證明透視
最早目標規則只是存在性見證
證明使用未知目標來說明某個合格文字存在。算法可能選擇固定搜索次序中更早的另一個合格文字。它不必恢復目標的語法形式,只需正確分類觀察到的樣本。
例題 1.4.3
(同一個樣本的兩個一致列表)
在兩個比特上,設活動樣本為 、、、。它們由「若 則 1;否則若 則 0;否則 1」標記。若搜索先選 ,便以標籤 1 刪除前兩個例子;對剩下兩個例子,可選擇標籤為 0 的 ,然後使用預設標籤 1。另一種選擇是先用標籤 1 選擇 ,它刪除 和 。剩餘例子 和 可由「若 則 1;否則 0」處理,得到不同的一致列表。
常見錯誤
(用多數標籤代替要求覆蓋集合同標籤)
在同一個樣本中,文字 在 和 上都為真,所以它的覆蓋集合含有兩種標籤。無論取哪個 ,添加 都會誤分類這兩個例子之一,而兩者都被刪除就把錯誤固定下來,因為被刪除的例子不會再被檢查。一致性不變量要求每個被覆蓋的活動例子具有相同標籤。
從一致性得到 PAC 保證
令 為抽樣前固定的語法列表集合:文字互異,規則至多 條,預設標籤任選。學習器不重複文字,所以輸出屬於 。列表最多有 個規則位置。為得到簡單的固定類計數,每個規則位置至多有 種文字選擇和兩種輸出選擇。在計數時允許重複只會增加數量。算上兩個預設標籤並對長度求和,
定理 1.4.4
(分布無關的可實現界)
假設 且幾乎必然有 。對 ,若
則輸出滿足 的概率至少為 。對數是自然對數。
證明
(對固定類取並集界)
對風險 的任一固定列表 ,它在獨立同分布樣本上不犯錯的概率為 。由並集界,固定假設類中任意壞列表仍與樣本一致的概率至多為 。在概率為一的可實現事件上,學習器輸出一致,因此在上述壞事件外其風險至多為 。並集針對固定有限語法列表集合,而不是假設依賴樣本的輸出是固定的。
例題 1.4.5
(一個具體的樣本量)
當 時,計數為 。取 、,定理要求 ,所以 個樣本即可。粗略的界 比 大約大 倍,這只使定理中的對數增加約 。
例題 1.4.6
(只有單一標籤的樣本)
令 ,目標為「若 則 1;否則 0」。設樣本為 和 。第一輪所有剩餘標籤都等於 ,所以學習器添加預設標籤 並停止,輸出空列表,即常值分類器 。它與樣本一致,但在每個 的輸入上都不同於目標,所以風險為 。PAC 界說明:除非該概率很小,這樣的誤導性樣本在 足夠大時不太可能出現。
所給計數刻意求簡單而不是精確。它給出的充分樣本量級為 ,並可與多項式時間一致性算法結合。它沒有說明學到的列表在樣本外等於目標,也沒有說明此樣本界最優。
假設失效時
反例模式
衝突標籤可能使搜索停止
取同一輸入的兩個副本,給它們相反標籤。活動標籤不全相等,而任何覆蓋其中一個副本的文字也覆蓋另一個,因此不存在覆蓋非空且標籤相同的文字。算法報告失敗。沒有確定性決策列表能擬合該樣本,所以可實現性假設確實失效。此例沒有刻畫每一種噪聲模型下的行為。
常見錯誤
(決策列表不是規則的集合)
即使沒有噪聲,次序也很重要。「若 則 1;否則若 則 0;否則 1」在 上預測 1;顛倒兩條規則則預測 0。列表不是一個無序的、各自獨立生效的規則集合。
練習與解答
快速檢查
(對兩個比特的例子,目標列表在 和 上分別預測甚麼?)
按 的次序找第一個為真的文字。
解答 · 答案
在 上第一條規則觸發並返回 1;在 上第一條規則為假,所以第二條規則觸發並返回 0。
快速檢查
(若所有活動標籤均為 0,算法接下來必須輸出甚麼?為甚麼它在活動例子上一致?)
看過程的第 1 步。
解答 · 答案
算法必須以預設標籤 0 停止。活動例子均不滿足先前輸出的文字,所以由預設標籤得到 0,而前綴已正確處理被刪除的例子。
快速檢查
(為甚麼此前選中的文字不可能在之後某輪再次被選中?)
滿足該文字的例子後來怎樣了?
解答 · 答案
滿足該文字的所有活動例子都已刪除,且活動集合只會縮小;故它之後的覆蓋為空,不能再次滿足非空覆蓋規則。
快速檢查
(若固定候選列表的總體風險為 ,它與 個獨立樣本一致的概率是多少?)
每個樣本都必須被正確分類。
解答 · 答案
,因為每個獨立樣本被正確分類的概率為 。
快速檢查
(當輸出列表依賴樣本時,為甚麼需要並集界?)
哪一個概率界只對預先固定的列表有效?
解答 · 答案
不能將固定列表的概率界直接用於觀察樣本後才選出的列表;並集界給出同時控制固定類中每個列表、包括所選列表的一個事件。