另一種學習保證
分類器給出單一標籤;有時我們希望輸出一組可能的標籤,並控制真標籤落在集合外的頻率。分割保形預測無需假設概率模型正確便能給出這類保證。其概率涉及同時抽取校準樣本與未來例子的整個實驗,並不保證每個人或每個群組都有相同覆蓋率。
定義 11.1.1
(非符合度分數與校準設定)
設標籤集合 。選定可測、有限值的非符合度分數 ,且其選擇獨立於校準及測試例子;分數愈大表示標籤 與輸入 愈不吻合。例如,對先前訓練的 ,可取 。分數不必是校準良好的概率。它可以來自另一份訓練樣本,只要該訓練樣本獨立於校準和測試例子。
設 在給定獨立訓練數據後仍可交換;獨立同分布是充分的特例。要求 及 。校準分數為 ,其中 ;構造集合時不使用未知的測試真標籤 。
有限樣本規則
定義 11.1.2
(分割保形的閾值與預測集合)
將校準分數排列為 ,並設
對新輸入 ,輸出
索引用 而非 ,因為未知測試分數也佔 個秩中的一個。若 ,此規則使用 而非觀察所得的有限閾值;返回兩個標籤是保守而且定義良好的做法。
定理 11.1.3
(由可交換秩得到邊際覆蓋)
在上述假設下,。此概率在給定任何獨立訓練數據後,對校準及測試例子取平均。
證明
(由測試分數的秩得到邊際覆蓋)
先對獨立訓練數據取條件,使分數函數固定。給全部 個分數附上獨立同分布的連續平手排序變量 ,這些變量獨立於所有分數和訓練數據,再按字典次序排列數對 。例子可交換、排序變量獨立同分布,所以這些數對可交換;它們幾乎必然互不相同,因此測試數對在 個數對中的秩 均勻分布在 。
若 ,則 ,真標籤以概率一被覆蓋。否則 。在事件 上,測試數對屬於最小的 個數對,所以排在它前面的校準數對至多有 個,第 小的校準數對排在它之後。字典次序細化了分數的次序,因此 ,即 。覆蓋概率因此至少為 。平手排序變量只用於證明;實際規則保留等號,無需隨機化。
證明透視
可交換性與計數 $n+1$ 在哪裏起作用
證明靠三個要素。可交換性恰好只用一次,使測試的秩均勻;證明沒有用到分數或數據分布的任何性質,所以保證對每個分布都成立。平手排序變量把可能有平手的樣本變成嚴格排序,卻不改變所關心的事件:字典次序細化分數次序,所以 仍然推出 。這個蘊含是單向的,因此平手只會使非隨機集合更大。計數 出現,是因為測試分數也是被排序的一項;若用索引 ,就等於按錯誤的位置個數來校準。如果分數依賴校準數據,第一個要素就會失效:這 個數對不再可交換。
保證對獨立訓練數據成立,但一般不對某個已實現的校準集合取條件成立。它討論真標籤,並非說集合內每個標籤的後驗概率至少為 。集合很大可以安全卻不夠有用;覆蓋率本身不能控制集合大小。
命題 11.1.4
(分數沒有平手時的精確覆蓋率)
除上述假設外,再設 個分數幾乎必然沒有平手。則 ,從而
證明
(不用平手排序變量的秩計數)
沒有平手時,由可交換性,測試分數在 個分數中的秩 均勻分布在 。對 :若 ,則 ;若 ,則至少有 個校準分數嚴格小於 ,所以 。因此覆蓋率恰為 。當 時覆蓋率為 。最後,由 得下界,由 得上界。
校準例子
例題 11.1.5
(閾值、集合與空集合)
取四個校準分數 和 。則 、。用分數 且 ,兩個候選分數為 和 ,所以 。若 ,分數是 和 ,所得集合為空。這個規則允許空集合;定理限制它對邊際未覆蓋的貢獻,並不排除某個特定輸入出現空集合。
若用同一組四個分數但取 ,則 ,閾值為 ,返回兩個標籤。若改用觀察所得的最大分數,便是另一個規則,不能直接套用上述所需水平的證明。
例題 11.1.6
(用秩計數得到精確覆蓋率)
取 、。則 ,。分數沒有平手時,測試分數等可能地佔據五個秩中的任何一個,真標籤恰在其秩為 、 或 時被覆蓋。覆蓋率因此為 ,落在 內,與命題一致;因為 不是整數,結果略為保守。
例題 11.1.7
(平手使規則保持保守)
設分數對每個例子都是常數 ,所以五個分數全部平手。取 、,得 、。測試分數 滿足 ,所以真標籤以概率一被覆蓋,而不只是 。規則使用 且不拆開平手,所以有平手時覆蓋率只會高於無平手的值。代價是集合較大:這裏 保留所有分數為 的標籤。
邊際覆蓋可以掩蓋群組差異
反例模式
群組覆蓋率可以遠低於邊際水平
考慮一個特意簡化的分布:、,且 恆成立。定義真標籤的固定分數為 、;對兩種輸入都取 。令 個校準例子獨立抽取、,故 。恰好當至少兩個校準輸入屬於 時,閾值才為一;否則為零。
若測試輸入為 ,真標籤恰好在閾值為一時被覆蓋。因此該群組的條件覆蓋率為
遠低於 。在 上,真分數永遠為零,覆蓋率為一。整體覆蓋率約為 ,仍高於 。這並不矛盾:定理對群組取平均。此例並非聲稱該分數是有用的分類器,而是用來分清保證中的量詞。
論證何時不再適用
固定分數後,證明需要校準和測試例子可交換。如果看過同一組校準分數後才調整分數或選擇 ,上述秩論證可能失效。分布轉移也可能破壞可交換性。對相關數據、自適應重用校準數據、條件覆蓋或群組保證,需要另行分析。訓練準確度及概率模型品質可能影響集合大小,卻不能使邊際覆蓋自動變成對每個輸入的保證。
常見錯誤
(索引中用 而非 )
索引 看似自然,卻會覆蓋不足。取 、,它給出 ;分數沒有平手時覆蓋率為 。正確的索引 給出 。測試分數佔據 個秩中的一個,所以水平必須按 計算。
常見錯誤
(用校準數據來擬合分數)
若函數 是用其後用來校準的同一批例子擬合的,校準數對便不再與新的測試數對可交換:擬合出的模型通常對自己的例子擬合得比新例子好,校準分數偏小, 偏小,集合可能漏掉超過 比例的新標籤。應按設定所要求的,用另一份樣本擬合分數。
練習與解答
快速檢查
(若 、,求 。分數互不相同且可交換時,此規則的覆蓋率是多少?)
使用 和無平手命題。
解答 · 答案
。若可交換分數互不相同,測試秩不超過 的概率為 ;平手可能令非隨機集合更保守。
快速檢查
(若 、,此規則使用甚麼閾值?)
先算 ,再與 比較。
解答 · 答案
,所以 ,返回兩個標籤。
快速檢查
(若所有校準分數都是 且 ,分數恰為 的測試候選會被納入嗎?)
看 定義中的不等號。
解答 · 答案
會。此時 ,規則使用 ,保留平手而不是剔除它們。
快速檢查
(當 時,定理是否保證每個子群組都有 覆蓋率?)
想想概率是對哪些隨機性取的。
解答 · 答案
不保證。這是對各群組取平均的邊際敘述;上面的兩群組例子提供反例,稀有群組的覆蓋率只有約 。
關於分割保形預測的邊際覆蓋及其假設,可參閱 Gibbs、Cherian 和 Candès 的研究論文 第 2.1 節。