動機
凸分類損失方便我們求解,但能夠求解,並不等於所得的最小點一定善於分類。鉸鏈損失要求帶符號的間隔;邏輯斯損失則要求概率估計。最後報告的分類錯誤率,與這兩個目標都不同。我們需要一個明確的定理把它們連起來。
正確的比較基準,是數據分佈本身容許的最佳預測。在某個輸入上,若正標籤的出現概率為 ,即使最佳的確定性分類器也有 的錯誤概率。我們應該量度學習方法超出這個不可避免部分的錯誤。這種超額風險把標籤的不確定性,與決策不佳帶來的代價分開。
以下先在每個輸入上分別解決預測問題,再把所得不等式積分,完整推導鉸鏈及邏輯斯風險的比較。最後才接回經驗風險最小化。這一步不可省略:某個損失在不受限制時有正確的最優解,不代表一個太小或選擇不當的模型類能接近那個解。
定義
設 服從固定的概率分佈,且 。假設條件概率 有一個可測版本。所有關於 的敘述,都容許忽略一個輸入概率為零的集合。例如有限輸入空間及通常以實向量為輸入的模型都滿足這個假設。分類器 是取值於 的可測函數,其風險為 。
定義 15.1.1
(分數、平手規則與條件風險)
分數函數 是取有限實數值的可測函數。當 時,其分類器 ;否則 。所以零分數預測為正。對非負的間隔損失 ,定義
這裏 是固定輸入下的條件風險,而 同時對輸入及標籤取平均。以下比較的分數假設滿足 。記 ,下確界遍及所有取有限實數值的可測分數,並設 。
我們研究 與 。所有對數均為自然對數。風險的下確界未必能由有限分數取得;我們會證明所需的下確界恆等式,而不會直接把下確界與期望交換。
每個分類器的比較基準,都是選擇較可能標籤的決策規則。
定義 15.1.2
(Bayes 規則與分類超額風險)
Bayes 規則為:當 時 ,否則 。在 時,兩種決定同樣最優;選正標籤只是固定一個代表。定義 及 。
定理與命題
定理 15.1.3
(Bayes 風險與作出錯誤決策的代價)
Bayes 規則取得最小分類風險,且
所以在 接近 時,偏離 Bayes 決策的代價很小;當其中一個標籤明顯較可能出現時,代價便較大。
定理 15.1.4
(鉸鏈與邏輯斯損失的校準)
對每個相應替代風險有限的分數,
不受模型類限制的替代風險下確界為
其中 ,並約定 。因此,替代風險收斂到不受限制的下確界,便保證分類風險收斂到 Bayes 風險。這些比較針對超額風險;原始邏輯斯風險並不是分類錯誤的概率。
這裏的校準,指替代超額風險小,便能推出分類超額風險小。上述不等式把這個推論量化。它們沒有宣稱任意損失都享有相同常數,甚至沒有宣稱任意損失都享有這個推論。
反例模式
一個不校準的凸損失
聲稱:每個凸間隔損失都是校準的。取凸而非負的損失 ,以及一個 的輸入。此時 ,故 ,零分數的替代超額風險為零。按平手規則它預測為正,分類風險為 ,而 Bayes 風險為 :分類超額風險為 。事實上,對每個 , 都使 最小,所以這個損失完全不理會標籤概率。修正是一個標準結果(此處不證):凸間隔損失校準,當且僅當它在 可微且 ;鉸鏈、邏輯斯與平方損失都符合。
證明與推導
以下給出完整的條件論證。
證明
(逐點比較兩個決策)
固定一個正標籤條件概率為 的輸入,預測正的錯誤概率為 ,預測負則為 。較小者是 ;改選另一個決策,錯誤率便增加 。當 時,不論選哪個平手代表,增加量都是零。取期望即得第一個定理。
證明
(由分段條件風險得到鉸鏈校準)
鉸鏈損失的整個條件風險圖像都是分段仿射的:
最小值為 。當 ,分數 是一個最小點;當 ,則可取 。因此可測分數 同時在每個輸入上取得條件最小值,也就取得該最小值的期望,證明了鉸鏈風險的下確界公式。
假設分數作出了與 Bayes 不同的決策。如果 ,這表示 ;由分段公式可見 。如果 ,錯誤決策表示 ,也有相同下界。所以條件替代超額風險至少為 。若決策正確,條件分類超額為零,而替代超額非負;在 時亦然。積分便得 ,並完整包含零分數的既定規則。
證明
(以相對熵得到邏輯斯校準)
對邏輯斯損失,設 ,故 。把兩個對數改寫,得到
其中 是二元相對熵。固定 ,把它視為 的函數。在 時,其值及一階導數都是零,並且
在 與 之間把這個二階導數不等式積分兩次,得到 。再利用關於 的連續性,便延伸到 及 。尤其相對熵非負。若 ,在 時取得最小值零,對應分數為 。
當 ,條件損失隨 下降至零;當 ,則隨 下降至零。這兩種情況都沒有有限的最小點。為了證明整體下確界,把對數勝算截斷到 ,並在 及 分別賦值 及 。這些分數都是有限且可測的。當 ,其條件風險逐點下降至 ,而且介於 與 之間:截斷分數是從零向條件最小點移動。由上界 及控制收斂定理,其風險趨向 。另一方面,相對熵非負保證任意分數的風險都不低於此值。因此邏輯斯風險下確界公式成立,並有 。
若分數作出錯誤決策, 與 位於 的兩側;邊界上的等號依照既定平手規則處理。故 ,而條件分類超額滿足
若決策正確,左邊為零,所以第一個不等式仍成立。取期望,並對 與常數隨機變量一使用 Cauchy–Schwarz 不等式,即得邏輯斯比較。
證明透視
邏輯斯論證如何收口
邏輯斯證明建基於一個恆等式和兩個不等式。恆等式 把條件風險分成不可避免的部分與一個散度;只要下確界恆等式成立,超額便是散度的期望。下確界恆等式正是微妙之處:在 時沒有有限分數是最優的,所以證明不能在最小點上計算風險。截斷的對數勝算給出有限分數,其條件風險隨 增大而下降,因為凸函數 在 由 向最小點移動時遞減;這些風險又以 為上界。於是控制收斂定理容許取極限。
不明顯的一步是曲率界 ,它把相對熵轉化為兩個概率之間的平方距離 。平手規則只在錯誤決策一步出現:當 時,零分數給出 並預測為正,此時 取等號。論證最後以 Cauchy–Schwarz 不等式收口,等價於對凹的平方根用 Jensen 不等式。所以邏輯斯界帶有平方根;鉸鏈界則直接讀自分段仿射的條件風險,沒有曲率一步,因而是線性的。
完整例題
例題 15.1.5
(Bayes 錯誤率可以非零,平手也需要規則)
設 取值 的概率為 ,並有 、。Bayes 決策在 選正、在 選負,風險為 。改取分數 、。兩個決策都與 Bayes 相反,包括零分數所作出的正預測。風險為 ,故超額為 。Bayes 恆等式也給出相同答案:。
兩個條件鉸鏈風險為 及 。因此 ,而 。替代超額為 ,確實大於分類超額 。若只把分類超額與原始鉸鏈風險比較,就無法清楚分辨不可避免的不確定性,以及所選分數造成的額外代價。
例題 15.1.6
(概率估計與決策提供不同資訊)
只有一個輸入,且 。取滿足 的分數,它為負,分類超額為 。邏輯斯超額為
定理給出 ,這是有效上界,但不是等號。若改取正分數,分類超額便為零,可是邏輯斯超額通常仍然為正:決策的正負可以已經正確,概率估計卻仍不準確。
例題 15.1.7
(確定標籤:鉸鏈取得下確界,邏輯斯則否)
只有一個輸入,且 。鉸鏈條件風險為 ,對每個 都是零,所以下確界由有限分數取得。邏輯斯條件風險 對每個有限 都大於零,只在 時才趨向 ;在 時它等於 。每個正分數的分類超額都是零,而 的邏輯斯界只給出 。
對負分數 ,分類超額為 。鉸鏈超額為 ,邏輯斯超額為 ,而 。在 的這個邊界值上兩個比較都成立;證明中的截斷步驟正是為這種情況而設。
反例模式
校準比較的是不受模型限制的最優值
只有一個輸入,,分數類限制為兩個常數 及 。分數 的分類風險為 ,鉸鏈風險為 ;分數 的分類風險為 ,鉸鏈風險為 。因此,類內的鉸鏈最小點反而有較差的分類風險。這不矛盾:不受限制的鉸鏈最優值為 ,在分數 取得,而該分數並不在這個類內。對所選的 ,分類超額為 ,相對於不受限制最優值的鉸鏈超額為 ,符合校準不等式。相對於兩元素類的最小值,其鉸鏈超額則為零;不能把這個零代入定理。
常見誤解
有限樣本的經驗錯誤率不會直接告訴我們 ;訓練替代風險小,也不會單獨給出總體替代超額的上界。要把校準用於學習結果,設 為非空分數類,定義其近似誤差為
假設比較中的總體風險均有限。在滿足 的事件上,假設所得分數 的經驗風險不超過 ,其中 。對類內任意比較函數 ,
對比較函數取下確界不需要最小值能夠取得。減去 ,便得 。鉸鏈分類超額由這個和控制;邏輯斯分類超額則由此和的兩倍之平方根控制。三項分別代表三種障礙:模型類欠缺合適分數、有限樣本估計,以及尚未完成的最優化。若三項都趨向零,且估計事件的概率趨向一,所得分類風險便依概率收斂至 Bayes 風險。單是增加參數個數,或單是解好一個固定最優化問題,都沒有同時證明這三項條件。
常見錯誤
(把有界損失的集中界用於不受限制的分數)
在不受限制的分數上,邏輯斯及鉸鏈損失都無界。若樣本獨立同分佈、分數類固定且不依賴數據,類的大小為 ,並且每個類內函數幾乎處處滿足 ,損失才落在 :鉸鏈可取 ,邏輯斯可取 。此時 Hoeffding 不等式配合聯合界,以至少 的概率給出 。把有界損失界用在任意分數上,就漏掉了必要假設。如果類是從同一訓練樣本選出,還需要另外控制;直接條件於這個選擇,不會自動恢復固定類的論證。
常見錯誤
(把原始邏輯斯風險當作錯誤概率)
在 的輸入上,每個分數的邏輯斯條件風險都是 ;可是那裏每個分類器的錯誤概率都恰為 ,而且都是 Bayes 最優的。原始風險超過任何可能的錯誤率。只有超額 才與 比較。
快速檢查
快速檢查
(在 的輸入上,負分數是否與選定的 Bayes 規則不同?這種不同是否貢獻分類超額?)
解答 · 答案
是不同的:選定的 Bayes 規則在 時預測為正。但它不貢獻分類超額,因為其權重 為零。邏輯斯風險卻仍可懲罰一個很有信心的負分數,因為它所給出的 偏離真實概率 。
練習
快速檢查
(只有一個輸入,。分別計算分數 的分類風險及鉸鏈超額風險。對零分數,另算邏輯斯超額風險,並驗證邏輯斯比較。保留零分數預測為正的規則。)
解答 · 答案
Bayes 決策為負,風險為 。分數 的分類風險依次為 ,故超額為 。鉸鏈風險依次為 ,而不受限制的鉸鏈最優值為 。所以鉸鏈超額為 ,各自都不小於相應的分類超額。零分數給出 ,邏輯斯超額為 ,故 。零分數在鉸鏈比較中取得等號,也說明平手規則必須明確固定。
練習 15.1.8
(對平方間隔損失 ,設 。證明 及 ,並證明不存在通用有限常數 ,使所有分佈及分數都滿足 。)
核心證明
解答(4)
- 1
對 配方
展開 ,得到 。有限可測分數 同時取得條件及總體下確界,所以 。
- 2
在錯誤決策上控制分類超額
關鍵一步
若決策錯誤且 ,則 ,右邊恰是該事件上的條件分類超額 。決策正確或 時超額為零。因此處處有 。
依據: 錯誤決策令 與 位於零的兩側,平手亦包括在內。
- 3
積分並用 Cauchy–Schwarz 不等式
。
- 4
排除線性比較
∎考慮單一輸入,、,分數為零。分類超額為 ,平方損失超額卻為 ,比值 在 趨向零時無界。
快速檢查
(一個固定的有限分數類有 個函數,每個分數都滿足 ,訓練樣本有 個獨立同分佈觀測。此類的總體鉸鏈近似誤差至多為 ,所得分數的經驗最優化誤差至多為 。給出以至少 概率成立的分類超額界,並指出哪個已知量無法只靠數算類的元素個數得知。)
解答 · 答案
鉸鏈損失上界為 。取 得 。因此以所要求的概率,分類超額至多為 。近似誤差 描述總體分佈與可用分數函數之間是否配合;單靠數目 不能證明這個誤差。最優化誤差也需要由所得解的性質另行保證,不能從類的大小推出。
練習 15.1.9
(輸入空間恰有 個點,分佈任意。設 包含所有只取 的 個分數函數。證明此類上的鉸鏈經驗最小化就是分類經驗最小化,並推導精確經驗最小點的 Bayes 超額分類保證,保留這個分數選擇帶來的常數改善。)
綜合證明
解答(4)
- 1
計算取值於 的分數的鉸鏈損失
對這類分數,預測正確時鉸鏈損失為零,錯誤時為二。因此經驗及總體鉸鏈風險都恰等於分類風險的兩倍,兩個經驗最小化選出相同的分數。
- 2
確定近似誤差
此類包含在全部輸入點上作 Bayes 決策的分數,其鉸鏈風險為 。所以鉸鏈近似誤差為零,且每個類內分數都滿足 。
- 3
應用有限類界
關鍵一步
取 。以至少 的概率,精確經驗最小化給出 ,其中 。
依據: 此類固定,有 個元素,鉸鏈損失落在 。
- 4
轉回分類超額
∎由 得 。若只用一般校準不等式 ,就會多出一個二倍因子。由於分類超額不會超過一,也可把此界與一取較小者。