引言
近鄰分類器根據查詢點附近的標籤作預測,樸素貝葉斯(Bayes)則以可分解的概率模型預測。分類樹採取另一種方法:它遞歸地把特徵空間劃分為與座標軸平行的區域,在每個區域預測一個標籤。劃分以貪心方式學習:在每個節點,算法選取使該節點訓練標籤的不純度下降最多的一次分割。
本節討論二元標籤 和基尼(Gini)不純度。我們會定義準則、證明其增益的精確公式、指定完全確定的擬合規則,並親手計算一棵完整的樹。最後要區分不純度下降能證明甚麼,以及不能證明甚麼:它描述的是訓練標籤,而非測試誤差。
節點與基尼不純度
定義 5.6.1
(節點、標籤比例與基尼不純度)
節點是一個有 個元素的訓練樣本對 的有限多重集合。若其中有 個標籤為 ,其標籤比例為 ,基尼不純度為
這裏 是經驗比例,只描述這批有限的標籤。這定義有具體的概率意義。從節點的經驗標籤分布中有放回且獨立地抽取兩個標籤 ,每次抽到 的概率均為 。兩個標籤不同,必定是一個為 、另一個為 :
「有放回」不可省略。當 ,若從大小為 的節點不放回抽樣,所得概率為 ,一般與有放回的數值不同。
要避免兩種常見誤解:
常見錯誤
(把基尼不純度當作訓練錯誤率)
若節點預測多數標籤,錯分的訓練點比例是 ,而不是 。當 ,有 ;由對稱性,對每個 都有 。等號只在 成立。例如 時,,錯誤率卻是 。
常見錯誤
(把葉子比例當作已校準的概率)
一片葉子若含兩個訓練點,且標籤都是 ,便有 ;這不代表落入該葉子的新點必以概率 帶有標籤 。校準是新數據上的預測性質,須以保留的數據檢查。
滿足對稱性 ;它恰在純節點()為零,並在 達到最大值 。
分割與增益恆等式
定義 5.6.2
(分割與基尼增益)
一次分割把父節點分成兩個非空子節點 ,大小滿足 。記
分割的基尼增益是父節點不純度減去按大小加權的子節點不純度:
計算標籤 的數目可得 。兩邊除以 ,得到
定理 5.6.3
(基尼增益恆等式)
對任何把節點分成兩個非空子節點的分割,
因此 ,且 當且僅當 。
證明
(直接展開與全方差公式)
直接展開。 寫 、。由 及 ,
所以
展開 ,並利用 及 ,便得
利用條件方差。 從父節點均勻抽取一個訓練點,令 為其標籤, 記錄它所屬的子節點。 是均值為 的伯努利(Bernoulli)變量,所以 ;同樣地,,。由全方差公式,
因此 。變量 以概率 取值 ,以概率 取值 ;這種兩點分布的方差是 。
兩個子節點非空時 ,故可得等號成立的條件。
證明透視
增益恆等式依靠甚麼
兩種論證都只用到父節點與子節點之間的一條聯繫:計數恆等式 ,即父節點比例是子節點比例按大小加權的平均。其餘全是對單一函數 的代數運算。
關鍵一步是 為二次函數。由於 是加權平均, 中的線性部分互相抵消,只剩下二次部分 ,即兩個子節點比例的加權方差。正是 的嚴格凹性,使這個差距在 時必為正。
兩個子節點非空這一條件用了兩次:它使 有定義,也給出 ,這就是「僅當」方向的全部內容。若把 換成錯誤分類率 ,論證便不成立:該函數雖然是凹函數,但在 兩側各自是線性的,所以只要 位於 的同一側,差距就是零。下面第一個反例正是這種情況。
恆等式說明:子節點的 標籤比例相差大,而且大小不過分懸殊時,增益較大。整個計算只用到有限訓練樣本,因此這是經驗不純度的下降。
概念視角算法
Gini 分割就是最小平方分割
把標籤當作數值,並以每個子節點的平均值擬合該節點。子節點的平方誤差便是 , 亦同理。因此加權子節點不純度等於兩均值擬合總平方誤差的 倍;Gini 增益最大的分割,正是以平方誤差為損失的迴歸樹在 標籤上會選的分割。葉節點比例 就是這個最小平方擬合值。
若改為總體版本,便要用 等未知條件概率代替經驗比例。也可採用總體條件熵,但那是另一準則。訓練增益只估計這類量,節點愈小,估計可能愈不穩定。因此 並不保證測試誤差下降。
確定性的擬合規則
為使算法可以重現,我們預先固定所有選擇。特徵都是數值,索引為 。節點深度從根節點起計算經過的分割次數,因此根的深度是 。
- 候選閾值。 在一個節點,對每個特徵 ,將該節點訓練點的不同 值由小至大排列,以相鄰不同值的中點作候選閾值。閾值 把 送往 ,把 送往 。因為 嚴格介乎兩個觀察值之間,兩個子節點都非空。
- 選擇。 選取增益最大的正增益候選分割。若有並列,先選特徵索引較小者,再選閾值較小者。
- 停止。 若節點純淨、沒有正增益候選分割,或深度等於擬合前固定的上限 ,就把它變為葉子。
- 葉子預測。 預測多數標籤;若 ,預測 。
計算成本。 在大小為 的節點,逐一排序各特徵需 。排序後,每個特徵可從左至右掃描,維持左子節點中標籤 的累計數,使每個閾值的評估需 ,所有特徵合共 。同一深度的節點持有互不重疊的數據子集,因此每層重新排序的成本至多為 。實際總成本取決於節點大小與實作選擇,例如是否預先排序。類別特徵需要另外的分割規則,此處不作分析。
外推。 若查詢值超出某特徵的訓練範圍,預測仍由閾值規則決定:沿該特徵落入最左或最右的區域。這只是規則的結果,並非數據範圍外標籤規律仍然延續的證據。
例題 5.6.4
(特徵之間的並列改變樣本以外的預測)
取 中四點:、、、。根節點有 、。
沿特徵 由小至大,標籤為 。閾值 對應 ,增益依次為 、,以及由對稱性得的 。沿特徵 的次序是 ,標籤為 ,三個增益同樣是 。
最大值 由 和 同時達到。並列規則選特徵索引較小者,所以擬合的樹是 、,兩片葉子純淨,訓練誤差為零。
被捨棄的分割形成相同的訓練劃分 ,得到的樹是 、,訓練誤差亦為零。但在查詢點 ,選中的樹預測 ,被捨棄的樹預測 。訓練標籤無法在兩者之間作決定;並列規則本身是擬合模型的一部分。
例題 5.6.5
(重複的特徵值留下非純葉子)
取 ,標籤 。父節點有 、。只有兩個不同值,所以唯一候選是 。
左子節點含 的兩點,標籤 ,故 、;右子節點是 的單一點,故 。直接計算 ;用恆等式得 。增益為正,所以根節點分割。
左子節點的 只有一個不同值,沒有候選閾值,於是成為 的葉子,按並列規則預測 。訓練誤差為 。任何閾值樹都不能做得更好,因為特徵值相同而標籤不同的兩點必定落入同一片葉子。這是下文所證純度結果的邊界情況:那裏要求特徵值互不相同,而此處這個假設不成立。
完整算例:一棵樹
例題 5.6.6
(親手擬合一維樹)
取 ,標籤為 ,深度上限不構成限制。父節點有 、,故 、。
根節點。 候選閾值為 。下表每行均可用恆等式 核對。
| 左側標籤 | 加權子節點 | |||||
|---|---|---|---|---|---|---|
和 都達到最大增益 。按並列規則選較小的 。左子節點 的標籤均為 ,因此是純葉子。
右子節點。 其點為 ,標籤 。此處 、,候選閾值為 。
- :左子節點 純淨。右子節點 的 ,乘權重 得 ,增益為 。
- :左子節點 的 ,乘權重 得 ;右子節點 純淨。增益為 。
- :左子節點 的 、,乘權重 得 ;右子節點 純淨。增益為 。
規則選 。右孫節點 純淨,標籤為 。左孫節點 標籤為 ,唯一閾值 把它分成兩片純葉子,增益為 。
擬合區域。
最深的葉子位於深度 ,所以任何 均會重現這棵樹。訓練誤差為零。
這裏訓練誤差為零並不代表預測概率已校準。 和 附近的區域各只依據一個觀察值。
反例與限制
反例模式
基尼不純度下降,分類錯誤率卻沒有下降
把大小為 的父節點分成兩個大小均為 的子節點。左子節點有一個標籤為 ,故 ;右子節點有兩個,故 。父節點的 、。子節點的 分別為 和 ,加權平均為 。增益為 。
每個節點都預測 。父節點錯分 點,子節點合共錯分 點,訓練錯誤分類率維持 。基尼不純度是一個平滑的替代指標;即使預測沒有改變,它仍會獎勵 和 的分離。
這個反例針對準則本身。下一個反例則針對停止規則:只要沒有單一分割具正增益,規則便會停止。
反例模式
零增益停止規則漏掉交互作用
考慮四個權重相等的點:、、、。以任一特徵在 分割,均得 ,所以增益為 。擬合規則在根節點停止;按並列預測規則,根預測 ,訓練錯誤率為 。
然而,一棵深度為 的樹可先按第一個特徵分割,再在每個子節點按第二個特徵分割,完全擬合四點。失敗來自貪心的正增益停止規則,並不表示樹無法表達這個模式。
記住樣本中的偶然特徵也可以達到訓練純淨。下一個結果在明確模型下說明這一點。
定理 5.6.7
(記憶不能創造訊號)
假設訓練數據 和測試對 滿足: 是公平伯努利變量,並且 與整個組合 獨立,其中 包含預測器的內部隨機性。設 為利用 和 擬合的任何預測器,則
證明
(條件化論證)
對 、 和預測器的內部隨機性取條件。此時預測 是固定標籤 。由於 公平且與所有被條件化的變量獨立,。再對 和內部隨機性取平均,數值仍為 。
本節的擬合規則確實可以記憶樣本,下一個結果說明這一點。
命題 5.6.8
(互不相同的特徵值迫使葉子純淨)
設某特徵 在 個訓練點上的取值兩兩不同,且深度上限滿足 。則確定性擬合規則產生的樹的葉子全部純淨,因此訓練誤差為零。
證明
(分出最小值的點)
設大小為 的節點不純,含 個標籤 ,。特徵 上把 最小的點單獨分出的候選分割有 。若該點標籤為 ,則 ,;若標籤為 ,則 ,。無論哪種情況都有 ,由增益恆等式,這個候選的增益為正;因此除非節點深度等於 ,它必會被分割。
每次分割都產生兩個非空子節點,所以由歸納法,深度為 的節點至多含 點。非純節點至少含兩點,故其深度至多為 ;深度上限從不會令非純節點停止。任何分割的子節點在 上的取值仍兩兩不同,論證可以重複。沿每條路徑節點大小嚴格遞減,所以擬合必會終止,而且每片葉子都純淨。純葉子預測自身的標籤,因此沒有訓練點被錯分。
若訓練標籤亦是獨立公平硬幣,而測試標籤符合上述聯合獨立假設,那麼由記憶結果,這棵零訓練誤差的樹的測試誤差仍為 。這些是假設的模型,並非對任何特定數據集的斷言。
驗證的紀律
任何從數據學得參數的預處理都必須只在每個訓練摺內擬合,包括插補值、縮放參數和閾值搜尋本身。
對單一特徵作嚴格遞增變換,不會改變樹能形成的訓練分割;但插補可以改變這些分割。選擇 、最小葉子大小或剪枝程度均屬模型選擇,需要驗證數據。在所有選擇固定前,最後測試集必須保持未使用。基於分割的特徵重要度只描述擬合樹如何使用訓練數據,沒有因果意義。
習題
練習 5.6.9
(對上述四個 XOR 點,計算各單一特徵分割的根節點增益。解釋為何擬合規則停止,並給出一棵零訓練誤差的深度 樹。)
基礎
解答(3)
- 1
計算特徵 的分割
在 , 的標籤為 , 的標籤為 。故 ,。
- 2
應用停止規則
沒有候選分割具正增益,因此根成為預測 的葉子。
依據: 特徵 的情況對稱,其唯一分割的增益也為 。
- 3
給出零誤差的樹
先按 分割,再於兩個子節點都按 分割,便得到四片各含一點的純葉子。正增益規則看不到零增益的首次分割可以讓後續分割達到完全擬合。
練習 5.6.10
(大小為 的父節點分為兩個大小均為 的子節點,、。用兩種方法計算 ,並比較訓練錯誤率。)
基礎
解答(3)
- 1
直接計算
、、,所以 。
- 2
用恆等式計算
。
- 3
比較訓練錯誤率
三個節點均預測 ;父節點錯分 點,子節點合共錯分 點,因此分割前後錯誤率都是 。
練習 5.6.11
(對 上的 ,給出閾值 的各項數目並驗證增益。然後交換所有標籤,討論甚麼會改變。)
核心
解答(4)
- 1
列出數目
父節點有 、;左子節點有 、;右子節點有 、。
- 2
驗證增益
、、,且 。
- 3
交換標籤
關鍵一步
所有增益及選出的分割次序都不變。但並列葉子的預測則另有情況。
依據: ,而兩個比例都換成補數時 不變。
- 4
檢查並列葉子
當 ,節點 成為標籤 的葉子,預測 。交換標籤後它的標籤為 ,仍預測 ;換回原本的標籤意義,這次預測對應類別 。故固定的並列規則對標籤交換並不對稱。
練習 5.6.12
(一個數據集每人有多筆數據,隨機按行分割卻把同一人放進訓練和驗證集。解釋問題,並給出正確程序。)
綜合
解答(3)
- 1
找出洩漏
深樹可能隔離出特定人士的特徵組合,使同一人的驗證數據落入以其訓練數據擬合的葉子。若部署目標是預測新人士,驗證分數便可能反映對熟悉人士的記憶,對該目標產生樂觀偏差。
- 2
按組別分割並在摺內擬合
關鍵一步
應按組別分割,讓每個人的所有數據只落在一個摺內。在各訓練摺內擬合插補、任何縮放和閾值搜尋,再對保留的組別評估。利用驗證結果選擇 或剪枝程度,之後才在從未見過的人的獨立最終測試集上評估一次。
- 3
說明程序估計的對象
這個程序估計新人士表現,仍依賴各人可視為從共同總體獨立抽取的程度。這是數據收集方式的假設,並非分割本身能證明的結論。