為甚麼刪去符合訓練數據的規則?
決策樹可以不斷分裂,直至一個葉節點只描述一兩筆觀察。這樣的規則可能捕捉真實規律,也可能只是記住偶然的標籤。前一節說明如何生長決策樹並把它編譯成規則,當時刻意把剪枝留作另一個選擇。這裏研究一個具體方法,判斷哪些分支可以移除。
定義 28.1.1
(儲存的訓練標籤與三份數據)
生長樹之前,先留起有標籤的驗證數據。只用訓練數據建樹,並讓每筆訓練數據經過樹,在每個節點記錄到達該處的訓練標籤的多數類別。二元標籤若同數,約定取 。若某節點沒有訓練數據,則使用預先說明、只依賴訓練數據的後備標籤,例如父節點的記錄標籤。這些標籤在剪枝時保持固定,不以驗證標籤重新計算。另留一份完全未參與選擇的測試集作最後評估;分組或時間順序等數據來源特性亦要反映在劃分方式中。
算法與它真正保證的事
定義 28.1.2
(後序減錯剪枝)
令 為目前的有限樹, 為驗證集。依固定後序處理內部節點:先後代、後父節點,子節點的次序亦固定。對節點 ,考慮把它目前的整棵子樹換成一片葉,葉的標籤採用 記錄的訓練多數類別。只有當替換不會增加 上的錯誤數時才接受;相等亦接受,以選較小的樹。否則保留目前子樹。稍後處理祖先時,必須使用已修改的後代。根節點最後處理;一旦剪掉某祖先,其後代全部消失。這是單次掃描及一個明確的同分規則,其他剪枝變體未必採用同一規則。
定義 28.1.3
(局部錯誤計數)
令 為目前沿樹到達 的驗證數據, 為目前子樹在這些數據上的錯誤數, 為候選葉的錯誤數。採用錯誤數而非比例,可清楚處理空集:若沒有驗證數據到達 ,兩個數均為零,因此同分規則會剪去該子樹。這只是簡化缺乏驗證證據的分支,並不證明替換後在該處預測準確。
定理 28.1.4
(每次接受替換所保證的事)
對固定的有限驗證集及確定的路徑規則,上述算法會終止;最終驗證錯誤數不超過原樹。每次接受替換均減少節點數。在所有可由原樹把子樹換成其記錄標籤之葉而得的樹中,所得樹的驗證錯誤最少;在錯誤最少的樹之中,它的節點數亦最少。這不保證母體準確率提高。
證明
(局部改變等於兩個計數之差)
在 替換子樹,只會改變到達 的數據之預測,其他數據的錯誤數不變。因此總錯誤數的改變恰為 。算法只接受非正的改變。每次接受替換均移除節點;固定後序只涉及有限個節點,所以算法終止,而連續接受的操作均不增加驗證錯誤。更強的最優性可由葉向上歸納。節點處任何允許的剪枝,要麼把整棵子樹換成記錄標籤的葉,要麼保留節點並分別剪枝各子樹。每筆驗證數據只走進一個子節點,故保留節點時,各子樹的錯誤數可以相加。依歸納假設,已處理的每棵子樹錯誤最少,且在同樣少的錯誤下節點數最少。再把保留節點的結果與候選葉比較,便得到該節點處錯誤最少的樹;同分時選葉則確保節點最少。對根應用此結論即可。這只是關於用來選樹的 的結論,並非關於未來數據的概率保證。
證明透視
局部比較為何等於全域改變
只有到達所選節點的數據可能改變預測;其他錯誤項相消。因此比較兩個局部錯誤數,就能準確得到整個驗證目標的變化。即使後代已先被剪枝,此論證仍然成立。
逐步例子:改善、同分及拒絕
例題 28.1.5
(改善、平手與拒絕)
根節點測試 。當 時,節點 測試 : 預測 , 預測 。當 時,節點 測試 : 預測 , 預測 。已記錄的訓練多數標籤分別為 的 、 的 、根的 。例如 的訓練標籤 數目為 , 的為 ,便得到這三個多數標籤。下表每個列表是沿該路徑到達的驗證標籤;路徑由特徵值決定。
| 路徑 | 驗證標籤 | 原預測 | 原錯誤數 |
|---|---|---|---|
原樹在 筆數據上共有 個錯誤。先訪問 :目前子樹錯 次;改成葉 ,只錯兩個標籤 ,共 次。接受替換,總錯誤降至 。再看 :目前子樹錯 次;葉 也錯兩次,即兩個標籤 。依同分規則替換 ,總錯誤仍為 。最後,根的目前子樹錯 次;若根改成葉 ,左邊兩個和右邊三個標籤 均被判錯,共 次。因此拒絕根的替換。最終樹只測試 ,左邊預測 、右邊預測 ;驗證錯誤率為 。
概念視角算法
剪枝是自底向上取最小值
令 為在 處子樹的所有剪枝方式中,到達 的驗證個案所能達到的最少錯誤數。則 ,其中 取遍 的子節點,而葉節點的 就是它自己的錯誤數。在上面的追蹤中,,,,正是前面得到的最終錯誤數。
例題 28.1.6
(比較祖先與已修改的後代)
設根有左、右兩棵子樹,各有六個驗證個案到達。目前左子樹有 個錯誤,右子樹有 個。換成儲存標籤的葉後,錯誤分別為 與 ,而根葉則有 個錯誤。依後序:左子樹因 而被替換,右子樹因 而保留。此時根處的現有子樹有 個錯誤,所以有 個錯誤的根葉被拒絕,最後錯誤是 。若改用過時的原始總數 與根葉比較,便會平手而剪去根,結果錯誤為 ,比正確的 差。
例題 28.1.7
(平手規則改變的是樹,不是驗證錯誤)
回到上面的追蹤,假設平手改為相反處理:只有嚴格降低驗證錯誤才接受替換。節點 仍被替換,因為 。在 ,葉與子樹都有 個錯誤,所以 現在被保留。根葉仍有 個錯誤,被拒絕。最後的樹總錯誤是 ,與所述規則相同,但它保留了對 的測試,多出兩個節點(保留的 及其兩片葉,取代單一片葉)。因此接受平手的慣例,是在驗證錯誤最小的樹之中選出最小的一棵。
常見錯誤
(從驗證個案選擇替換葉的標籤)
替換葉必須帶有儲存的訓練多數標籤。若改由 處的驗證標籤決定, 就是任何單一標籤在這些個案上所能達到的最小計數,比較便偏向剪枝,並且重複使用了驗證標籤。上面的追蹤中,右邊的驗證數據剛好有三個 、兩個 ,這個巧合不表示可以從驗證標籤選葉的標籤。即使訓練樹不變,換另一份驗證集也可能得到不同的剪枝決定。
數據洩漏與選擇過擬合
反例模式
選出的完美分數不代表未來準確
假設 是每筆數據獨一無二的識別碼, 是與 無關的公平擲硬幣結果。足夠靈活的樹可以記住生長樹所用數據的標籤,令訓練錯誤為零;但對新的獨立硬幣結果,其預測正確的概率只有 。若把同一批有標籤數據稱作驗證集,剪枝決定及其分數便重用了訓練資訊。零訓練錯誤不代表對新數據的預測比猜測更好。
即使驗證集確實獨立,它在這裏仍被反覆使用:每次剪枝都取決於其標籤。若又在同一份數據上嘗試許多樹、同分規則或超參數,整個選擇過程可能迎合驗證數據中的雜訊。因此驗證錯誤不是獨立的最終表現估計。先固定所有選擇,才用未接觸、具代表性的測試數據評估一次;單一小型測試集仍有抽樣不確定性。若選擇後重新訓練,應預先訂明重訓程序,並以未用於選擇或擬合的數據評估重訓後的模型。
常見錯誤
(把選定的驗證錯誤當作表現)
追蹤中剪枝後的樹,驗證錯誤是 。這個數字是在推動每個剪枝決定的同一批標籤上比較計數而得,所以並非對將來錯誤的獨立估計。必須在所有選擇凍結之後,只用一次全新的測試集。
練習
快速檢查
(在節點 ,現有子樹在到達它的 個驗證個案上犯 個錯誤;訓練多數標籤的葉在那裏犯 個錯誤。整棵樹目前共有 個驗證錯誤。會發生甚麼事?新的總數是多少?)
解答 · 答案
接受替換:。 之外的錯誤數不變,所以新總數是 。
快速檢查
(某節點沒有驗證個案。依上述算法,它會被剪去嗎?這是否表示其替代葉的母體錯誤率為零?)
解答 · 答案
會:兩個局部錯誤計數都是零,而平手被接受。空的驗證子集對將來錯誤沒有提供任何證據;零個觀察之中零個錯誤,並不構成準確度保證。
練習 28.1.8
(某樹的根有左、右兩棵子樹。現有驗證錯誤分別為 與 。訓練多數標籤的葉會分別犯 與 個錯誤;根處的訓練多數標籤葉共犯 個錯誤。按後序並在平手時剪枝,做出各個決定,並寫出最後錯誤。為何根的比較必須使用已修改的子樹?)
核心
解答(3)
- 1
決定左子樹
現有錯誤是 ,葉的錯誤也是 。依平手規則,左子樹被替換。
- 2
決定右子樹
現有錯誤是 ,葉的錯誤是 ,而 ,所以右子樹被替換。
- 3
以已修改的子樹決定根
此時整棵樹有 個錯誤,根葉也是 個,依平手規則替換根;最後錯誤是 。根的比較必須使用已修改的子樹,因為候選葉要與手上實際存在的樹比較。若用原本的子樹錯誤,就是拿過時的 與 比較;這裏碰巧也接受根,但那並不是這個算法。
快速檢查
(有人用全部已標註的例子生長一棵樹,再把同一批例子隨機分成所謂的訓練和驗證子集,然後剪枝。指出洩漏所在,並提出有效的三份切分流程。)
解答 · 答案
樹的分裂與葉標籤,已經用了後來被稱為驗證標籤的標籤;驗證集並不獨立於樹的生長。應先切分觀察,在訓練數據上生長並標註樹,用驗證數據剪枝和選擇,然後凍結整個流程,再用另外保留的測試集評估。切分還須尊重有關的分組或時間次序。