同時選擇模型與分類器
較大的假設類可以更好地擬合樣本,但額外的靈活性也可能使擬合誤差過於樂觀。對於嵌套類,最小訓練誤差不會隨類擴大而增加,即使選出的分類器總體誤差更大。結構風險最小化通過為每個類的經驗誤差加上複雜度餘量來處理這一選擇,然後同時選出類和分類器。
困難在於,所選的類依賴於評估它所用的同一份樣本。事先固定一個類時成立的界,不能直接用於事後獲勝的類。我們先在各類之間分配置信額度,使所需比較同時成立。下面的結果允許任意標籤,包括不能由任何一個類實現的分布。
類、風險與權重
定義 3.1.1
(加權有限類與類半徑)
設 獨立同分布於可測實例空間和二值標籤上的固定分布 。設 是事先固定的可數序列,每個 都是有限非空的可測分類器 的集合。類之間可以重疊,也不要求嵌套。在看到樣本前固定權重 ,滿足 。
對 定義
對 ,為第 類設定半徑
對數均為自然對數。權重較小,表示分配給該類的失敗概率較少,因此罰項較大。這些權重不是各類為真的概率。半徑可能超過一;此時偏差界雖仍有效,但不能提供有效資訊。
概念視角算法
把半徑看作描述長度
把對數拆開:。第一項是在長度為 的編碼中指明類 的代價,第二項是指明其中一個成員的代價,所以 就是總描述長度除以 。對下面例子中的 ,,。
同時成立的事件與預言機不等式
定理 3.1.2
(類權重一致界與結構風險選擇)
以至少 的概率,對所有 和所有 同時有
先固定每個有限類中假設的次序。對每個 ,按此次序選擇第一個經驗風險最小化解 。再選使 最小的最小指標 ,輸出 。經驗損失可測,因此這些固定的可數平局規則使所選指標和分類器可測。下面的同時事件是可測事件的可數交。則在同一事件上,
這是一個預言機不等式:數據驅動的輸出與每個類中的最優風險加上該類餘量進行比較。右側是分析基準,不假定算法知道其值。
這裏可數列表上的最小化解確實存在。因為正權重的和有限,。對固定的 ,半徑趨於無窮,而經驗風險在 中,所以任何固定有限水平之下只能有有限個類得分。這證明了所述選擇存在,而不是假設下確界必然達到。有限列表的情形更簡單。
證明
(並集界,再接四個不等式的鏈)
對固定的 和 ,損失指示變量相互獨立、取值在 、均值為 。雙側 Hoeffding 不等式給出
對有限類使用並集界,該類的失敗概率至多為 。再使用可數並集界,總失敗概率至多為 。類重疊時可能重複計數,但不影響界的有效性。
在同時成立的事件上,對任意固定 ,選 ;有限性保證它存在。由選擇規則及兩次偏差不等式,
在同一個事件上,這對每個 都成立,因此取下確界得到預言機不等式。
證明透視
為甚麼這裏選擇類不需要第二份測試樣本
所選指標依賴數據。證明沒有假設它事先固定;而是先用預分配權重為所有類構造一個同時成立的事件。該事件成立後,便可將不等式應用於獲勝指標。這樣無需再支付一次選擇罰項,因為類權重已經計入了選擇;但這既不能取消觀測值獨立性的要求,也不使選擇後的訓練誤差本身成為無偏估計。
比較兩個得分
例題 3.1.3
(兩個罰後得分的比較)
設 、、權重為 。考慮 、 兩個類,其經驗最小化解的誤差分別為 和 。相應半徑和得分約為
第二個類擬合樣本更好,但在這兩個類之間第一個罰後得分更低。完整可數比較中,第三個類仍可能獲勝。這些得分是同時事件上的上界,不是精確總體風險;因此例子並不能證明在這次抽樣中第一類的真實風險較低。
例題 3.1.4
(小權重的代價)
保持 、、,比較權重 與 。半徑為 。 時為 ; 時為 。權重縮小到原來的 ,半徑只增加約 ,因為權重是通過 進入的。排在清單很後面的類會受到罰,但罰項不至於高得不可接受。
例題 3.1.5
(大於一的半徑)
取 、,一個 的類,權重 。則 ,所以 。由於風險落在 ,事件 平凡地成立。這個界有效,卻甚麼也沒有說;該類的罰後得分至少為 ,只有其他每個類得分更差時才會被選中。小樣本與極小權重會使保證變得空洞,定理並沒有掩蓋這一點。
為甚麼先分配權重再看數據?
反例模式
依數據選出的單元素類可以隱藏大類
令 上均勻分布,標籤處處為零。觀察樣本後,定義 在觀測過的點上輸出零,在未觀測點上輸出一。它的經驗風險為零,而至少 個點未被觀察,所以 。若事後稱 是預先指定的單元素類並給它權重一,所謂固定類半徑為 。當 、 時,該半徑約為 ,所聲稱的界在每個樣本上都失敗。這個單元素類依賴觀測到的輸入,並未指定為定理中預先固定的類之一。把它當作預先指定的類是錯誤的一步。
如果類和權重確實預先固定且可數,之後可以根據數據作選擇,因為定理同時控制每個候選。依賴數據的類或權重需要其他論證,例如用獨立樣本構造它們,或額外計入選擇機制的代價。
常見錯誤
(只按經驗風險選擇)
對嵌套的類,最小訓練誤差不會隨類變大而增加,所以只按 排序,永遠不會嚴格偏好一個類而不選包含它的更大的類,無論更大的類的容許量有多大。定理控制的是罰後得分 。從選擇規則中去掉 ,保證就不復存在。
常見錯誤
(預言機不等式中漏掉因子二)
基準是 ,而不是 。半徑被付了兩次:一次用來把所選分類器的經驗風險換成總體風險,另一次用來把基準分類器的總體風險換成經驗風險。最優風險為 、半徑為 時,保證的界是 ,而不是 。
近似與估計
預言機表達式區分兩個作用。 是第 類所能達到的近似誤差; 是估計餘量。擴大類可能降低前者,卻增大後者。單憑一次訓練樣本,一般不能知道二者的精確值。
令 。假設同一獨立同分布序列的前 項供每個 使用,並在選擇規則中取 。第一 Borel–Cantelli 引理不要求失敗事件相互獨立;由於 ,同時事件幾乎必然只失敗有限次。對每個固定 ,。因此預言機不等式對每個 給出 ,繼而 。每個被選分類器屬於類的並,所以其風險至少為 。因此
這是相對於固定類並的一致性,並非自動得到 Bayes 一致性:後者還要求該並能對所研究的分布逼近最佳可測分類器。結果是統計性的;枚舉所有類或尋找經驗最小化解可能在計算上不可行。
練習與解答
快速檢查
(設 、、、。寫出該類半徑的精確表達式。)
代入 。
解答 · 答案
,所以 。
快速檢查
(在同時成立事件上,一個類的最優真實風險為 、半徑為 。預言機不等式給所選分類器怎樣的上界?)
記住半徑要算兩次。
解答 · 答案
在同時成立事件上,所選風險至多為 。
快速檢查
(為甚麼不能把類設為一個依賴樣本的單元素集合,再不加論證地使用固定類半徑?)
比較這個單元素的訓練風險與真實風險。
解答 · 答案
單類 Hoeffding 計算要求所用假設在抽樣之前已固定;所提出的單元素可以編碼樣本,使訓練誤差人為地變小。上面的反例給出真實風險至少為 ,訓練風險卻為零。
快速檢查
(對固定 和 ,解釋為甚麼 。)
看根號下的分子和分母。
解答 · 答案
對固定的 ,分子為 ,分母為 。兩者之比趨於零,其平方根也趨於零。