動機
在普通監督學習中,學習器接收從某個分布抽取的有標籤樣本。主動學習允許它在一定程度上選擇要請求哪些標籤。當輸入容易取得、正確標籤卻需要昂貴實驗或專家判斷時,這種選擇可能很有價值。一個資訊量高的問題可以同時排除許多假設;隨機有標籤樣本則可能反覆落在剩餘假設都已一致的區域。
「學習器選擇一個例子」背後有多種不同模型:它能選擇實例空間中的任意點,還是只能從有限樣本池中選擇?輸入分布是否已知?預言機的答案是否總是正確?無標籤數據和計算是否有成本?不給出這些條件,標籤數量的結論可能造成誤解。我們先證明一個條件特別有利、但清楚可檢驗的結果,然後分析這些條件的作用。
定義
定義 8.1.1
(可實現成員查詢模型)
設 ,未知目標是閾值函數
學習器可以自適應地選擇任意 ,向預言機詢問準確標籤 ,每次請求計一個標籤。後續查詢可以依賴此前查詢、標籤和算法內部隨機性。評估誤差時的輸入分布為 上的均勻分布,且學習器知道這一點。輸出為某個閾值 。
總體誤差為 。標籤複雜度保證說明:對所有允許的目標,要達到指定誤差和置信度,需要多少次標籤請求。此模型只計算標籤數量,不計算查詢位置的數值精度、預言機計算或無標籤抽樣成本。
兩個閾值的分歧區域是參數之間的區間,至多相差端點。因此
等號處的標記約定只影響單點,在均勻分布下概率為零。換一個分布後,參數距離不一定等於錯誤概率。學習器也不能直接讀取目標的數值參數;它必須根據預言機回答推斷一個足夠小、包含目標的區間。
定義 8.1.2
(版本空間與樣本池查詢)
給定有限的有標籤記錄,版本空間是所選假設類中與每個已請求標籤一致的假設集合。分歧區域是至少兩個剩餘假設給出不同標籤的輸入集合。樣本池模型中,學習器取得或抽取一批無標籤輸入,只能請求池中點的標籤;成員查詢則可請求 中任意允許的點。兩種存取方式的標籤複雜度和無標籤數據成本不一定相同。
定理/命題
定理 8.1.3
(二分法學習均勻分布下的閾值)
在上述無噪聲成員查詢模型中,有一個確定性算法在取得 個標籤後,對每個 輸出總體誤差至多為 的閾值。因此對 ,至多 個標籤即可保證誤差不超過 ,置信度為一。
定理 8.1.4
(同一目標類下的被動學習比較)
設 、,並以 表示自然對數。被動算法接收 個獨立均勻輸入及其閾值標籤,並對該類中每個閾值,以至少 的概率輸出誤差至多為 的分類器。那麼必有
此下界允許算法使用隨機性,也不要求輸出必須是閾值。它計算獨立同分布有標籤樣本的數量,只比較此特定的均勻、無噪聲問題,並非所有主動與被動模型都存在相同差距。
定理 8.1.5
(匹配量級的被動上界)
對同一個均勻、無噪聲閾值類,若被動學習器返回與 個獨立同分布有標籤樣本一致的閾值,那麼只要
其誤差以至少 的概率不超過 。因此當 ,上述下界關於 和 的依賴在常數因子內是正確量級。
證明思路
證明
(二分法維持包含目標的區間)
最初學習器知道 。第 輪查詢中點 。若答案為一,目標定義給出 ,保留 ;若答案為零,則 ,保留 。後一個閉區間包含一個不可能的端點,但仍安全地包含目標。無論答案如何,區間均為閉區間、包含 ,且長度減半。
歸納得到 。輸出 ,兩個參數都在保留區間中,故距離至多為 ,這也就是均勻分布下的誤差。不需要概率計算:每個可能目標及與它一致的回答序列都滿足此不變量。 時無需標籤,界為一。中點與區間內每點的距離至多為區間長度的一半,故輸出中點可得到更精確的界 ;但現有界已經說明對 是對數依賴。
概念視角組合
二分法讀出二進位數字
二分法的每個答案正好是目標的一個二進位數字:答案為一表示 在左半部分,數字為 ;答案為零表示在右半部分,數字為 。經過 次詢問,學習器得到 的首 位數字(對 ,取不以零結尾的展開),所以誤差 就是 位數字的代價。例如 ,答案一、零、一、零拼出 。
證明
(被動樣本為何可能錯過關鍵區間)
取 和 ,二者標籤在均勻質量為 的區間上不同。令事件 表示 個輸入均未落入該區間,則 。在給定 的條件下,兩個目標產生的完整有標籤數據集具有相同分布;加入獨立的算法隨機性後仍然相同。
兩個目標分類器的分歧質量為 。對任意輸出分類器 ,包含關係 給出
因此同一輸出不可能對兩個目標都具有至多 的誤差。在給定 的共同條件分布下,兩個目標各自的失敗概率之和至少為一。乘以 ,至少一個無條件失敗概率不小於 。如果對所有目標的失敗概率均不超過 ,就需要 ;取對數得到第一個不等式。
當 時,。取 ,有 ,即得第二個不等式。下界計算的是有標籤觀測;它並不聲稱主動學習可以免費獲得真實標籤,也不聲稱每個分布都允許二分。
證明被動上界時,取任意與樣本一致的閾值。若其誤差大於 ,它位於真實參數左側或右側超過 的位置。前一種情況說明樣本沒有輸入落在 ;後一種情況說明沒有輸入落在 。若相應區間超出 ,該方向本身不可能出現。每個相關區間的均勻質量均為 ,故存在壞的一致閾值的概率至多為 。所示樣本數使其不超過 。這一論證適用於任何一致選擇,包括觀察數據後作出的選擇。
證明透視
標籤節省來自哪裏?
中點查詢在當前不確定區間已知之後才選出,所以任意一個答案都能排除區間的一半。被動樣本則可能反覆錯過兩個可能目標的分歧區域。兩個證明比較的是不同的資訊存取方式:任意無噪聲成員查詢與獨立同分布有標籤樣本。引用結論時必須同時保留這些條件。
例題
例題 8.1.6
(未知閾值的二分過程)
假設真實閾值為 ,但學習器並不知道。第一次查詢 得到一,保留 ;第二次查詢 得到零,保留 。查詢 得到一,保留 ;查詢 得到零,保留 。
四個標籤後區間長度是 。若返回左端點,誤差為 。算法不需要知道實際誤差;區間長度就是誤差證書。若返回中點,誤差為 ,至多為 。
例題 8.1.7
(具體的精度要求)
使用上述返回左端點的算法,為保證均勻誤差至多 ,取 。最終區間長度為 ,與閾值位置無關。對於置信度 ,被動下界說明任何對所有目標都成功的被動算法至少需要
個有標籤樣本,即至少 個。這分別是不同過程的充分界與必要界,並非精確最優值。被動數量允許 失敗概率,而二分保證對每個目標和每個一致回答記錄成立。
例題 8.1.8
(樣本池可能缺少有用查詢)
假設無標籤池只有 ,目標閾值不是 就是 。在兩個目標下,池中標籤完全相同:前兩點為零,後兩點為一。即使請求全部四個標籤,也無法從固定樣本池分辨目標。查詢 的成員查詢卻能立即區分它們。兩個目標在均勻分布下的分歧質量為 ,所以任何一個分類器不可能對二者的誤差都小於 。更多無標籤點可能有幫助,但必須另行計入其獲取成本並說明抽樣假設。
反例模式
查詢不一定能將版本空間平分
令 ,,並設 ,。查詢 相當於詢問目標是否為唯一假設 ;若回答為零,僅排除這一個候選。對於確定性精確識別算法,對手可以一直回答零,直到排除 個候選,餘下的目標才確定。因此可能需要 次查詢;相比之下,對 個有序閾值適當進行成員查詢,至多 次即可二分識別。此例證明的是精確識別的最壞查詢成本,本身並未給出近似學習的下界。主動選擇本身並不保證均衡劃分。
常見錯誤
常見錯誤
(參數區間小不自動意味著概率誤差小)
二分證明使用均勻輸入分布,將區間長度轉換為錯誤概率。若所有概率質量集中在短區間內某一點,該點兩側的閾值可能在全部概率質量上產生分歧。對於任意未知分布,參數區間短本身不足以保證總體誤差小。
常見錯誤
(完美預言機是條件而非結論)
一次錯誤回答就可能使真實閾值被丟棄,此後區間不變量失效。在明確規定獨立噪聲模型的情況下,重複查詢並取多數可能有用;但任意或相關的錯誤並不會自動因重複而消失。同樣,中點查詢需要成員查詢權限,固定樣本池不一定包含中點。
除非模型明確納入其他資源,標籤複雜度不會計算它們。確定窄區間可能需要高精度查詢位置;樣本池方法可能在找到有用點前檢查許多無標籤輸入。泛化結論還需說明概率針對樣本產生、預言機噪聲、算法隨機性,還是它們的組合。上面的置信度一依賴於無噪聲回答及確定性的幾何不變量。
總結
主動學習器利用此前答案選擇標籤。在任意無噪聲成員查詢及均勻輸入分布下,閾值二分法有對數標籤界;被動樣本可能錯過區分兩個目標的區域,在此例中產生上述下界。當 時,該界至少為 。改變假設類、限制樣本池、改變分布或加入標籤噪聲,都可能消除這一優勢。
練習
快速檢查
(從 出發,對 做三次二分查詢。寫出每次後的區間和最終左端點假設在均勻分布下的誤差。)
記住標籤為一表示 。
解答 · 答案
查詢 、、,得到標籤零、一、零。區間依次為 、、。左端點假設的誤差為 。
快速檢查
(若 ,上述左端點定理保證需要多少標籤?如果返回最終區間中點,可以得到甚麼誤差界?)
使用 。
解答 · 答案
五個標籤足夠,因為 。最終區間長度為 ,中點與目標相距至多 ,故均勻誤差至多 。
快速檢查
(對閾值 和 ,計算 個獨立均勻輸入在兩個目標下全部得到相同標籤的概率。解釋該事件上觀察到的有標籤數據為何不能確定哪個目標產生了它。)
先找出兩個閾值產生分歧的區間。
解答 · 答案
兩個目標在 上分歧,其質量為 ;全部 個輸入都避開該區間的概率為 。在該事件上,兩個目標對每個觀察輸入賦予相同標籤,因此數據與二者都相容;僅憑數據不能確定哪一個目標正確;對兩個目標均賦予正概率的先驗,也不能使這一共同記錄產生確定性。
快速檢查
(對反例中的單點類,令 。給出最多請求四個準確標籤就能識別目標的確定性策略,並解釋為何最壞情況下三個標籤不夠。)
想想某次查詢回答為零時,對手會怎樣回答。
解答 · 答案
查詢四個互異點。若某次答案為一,該點便識別目標;若全為零,則第五個假設是唯一剩餘者。對任何最多查詢三次的確定性策略,對手都可以回答零,使至少兩個目標與記錄相容。同一個輸出不能同時精確識別二者,故三個查詢無法保證成功。