一連串問題形成分類器
決策樹讓觀察值依次通過特徵測試。內部節點的測試選出子節點,葉節點則回傳類別預測。數值測試如 ,會把特徵空間分成區域。多層測試可描述單一測試無法表達的交互作用。
訓練決策樹,不只是把問題畫出來。我們須決定葉的預測、候選分割的評分,以及何時停止或簡化樹。這些選擇處理不同問題:分割可改善訓練分數,卻未必改善新觀察的預測;貪婪規則也可能錯過有用的交互作用。
使用有限訓練樣本 ,標籤為 。觀察值有各自索引,因此容許重複特徵向量,甚至容許它們有不同標籤。本節特徵皆完整可見,數值為有限實數。每個考慮的分割,其訓練子節點都非空;缺失值處理是另一項建模選擇。
葉節點的最佳常數預測
命題 3.2.1
(多數預測令葉節點訓練錯誤最少)
設非空葉節點有 個標籤 1、 個標籤 0 的訓練觀察。常數預測 1 會錯 個,常數預測 0 會錯 個。因此零一損失下,最少的錯誤數是 ,由預測多數類取得。平手時固定一個規則,例如兩類數目相同便預測 0。
證明
(數算每個常數預測的錯誤)
常數預測恰好在另一類的觀察上出錯。預測 1 會在 個標籤 0 的觀察上出錯,預測 0 會在 個標籤 1 的觀察上出錯。二元標籤只有這兩個常數預測,所以最小值是 ,而多數類能夠取得它。
這證明固定葉區域內的局部最優,不證明區域選得好,也不證明訓練多數會是母體多數。經驗比例 是有用摘要,卻不自動是未來數據上已校準的概率。
熵量度經驗標籤的不確定性
定義 3.2.2
(二元熵與分割資訊增益)
對 的節點,設 ,定義
以連續延伸約定 。純節點熵為 0,兩類平衡的節點熵為 1 位元。
候選測試把節點分成非空子節點,以 索引,大小為 、標籤 1 比例為 。資訊增益為
權重 不可省略。若從本節點均勻選一個訓練觀察,它以該概率到達子節點 。這個和是得知測試結果後,平均剩餘的標籤熵。若小子節點與大子節點權重相同,就在計算另一個量,甚至會改變勝出的分割。
命題 3.2.3
(資訊增益不為負)
沿用定義中的記號,且每個子節點都非空,則
此外, 恰好當每個子節點的標籤比例都與父節點相同,即對所有 有 。
證明
(二元熵的凹性)
節點中的每個觀察恰好屬於一個子節點,所以父比例是加權平均 。對 ,
由於 在 上連續,它在該區間上嚴格凹。權重 都為正,總和為 1,所以 Jensen 不等式給出 ,即 。等號恰好在所有 相同時成立,而共同值必須等於它們的加權平均 。又因子熵非負,有 。
證明透視
劃分與嚴格凹性用在哪裏
關鍵一步是把 寫成各子節點比例的加權平均。這個等式成立,是因為子節點把節點劃分:標籤 1 的數目相加,各 的總和是 。若某觀察被送到兩個子節點,或不被送到任何子節點,權重總和便不再是 1,等式也就失效。
凹性只給出 。嚴格性加上正權重(來自非空子節點),才令等號成為關於數據的陳述:只有當劃分沒有改變任何子節點的標籤比例,增益才為零。
這說的是已觀察樣本的分布,不聲稱母體標籤依賴該特徵,也不保證估計出的正增益會在新數據中持續。
小而純的子節點可誤導未加權分數
例題 3.2.4
(在相同八筆觀察上比較兩個測試)
根節點有兩個二元特徵 :
| 觀察 | 標籤 | ||
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 |
| 7 | 0 | 1 | 0 |
| 8 | 0 | 1 | 0 |
根有兩類各四筆,熵為 1。測試 會隔離一筆純標籤 1,另一子節點有七筆,其中三個 1、四個 0。測試 則給出兩個四筆子節點,兩類數目分別為 及 。
| 測試 | 正確加權子熵 | 資訊增益 |
|---|---|---|
資訊增益選 。其多數葉在八筆中錯兩筆。 分割錯三筆:大子節點預測 0,錯分餘下三個 1。若根直接作常數葉,不論平手時選哪類都錯四筆。
若錯把兩個子熵直接平均, 會得到 ,低於 的 。錯誤規則因此偏好 ,使一筆觀察與其餘七筆合計有相同影響。
熵與訓練誤分類是不同準則。對一般候選劃分,較小熵不一定代表多數預測錯誤更少。例子同時報告兩項分數,不表示兩種目標可以互換。
數值分割必須尊重重複值
對數值特徵,以 送左, 送右。按該特徵排序節點觀察,並把相同值分組。若互異值為 ,便只有 種非平凡訓練劃分。每個滿足
的閾值,都給出相同訓練劃分。取 是一種精確約定,也可以取中點;但對介乎兩值之間的新觀察,兩種選擇的預測可能不同。必須儲存實際閾值,預測時也使用相同不等號。
相同特徵值不能由此測試分開。在排序後兩筆相同值之間放邊界,只會產生任何閾值都無法重現的虛構劃分。
掃描互異值群組時,維持兩類標籤的前綴計數。每次把整組由右移左,更新兩邊數目;只在兩邊都非空時計算加權熵。
BEST_THRESHOLD(observations):
sort by this feature; keep all equal values in one group
left0, left1 = 0, 0
right0, right1 = total counts of labels 0 and 1
bestGain = -INFINITY
bestThreshold = NONE
for each value group except the final group:
move the group's label counts from right to left
gain = parentEntropy - sizeWeightedChildEntropy
if gain > bestGain:
bestGain = gain
bestThreshold = this group's feature value
return the best threshold, or NONE if there is only one distinct value
命題 3.2.5
(閾值掃描對每個可行劃分恰好檢查一次)
設節點有 個觀察,數值特徵有 個互異值 。兩邊都非空的劃分 恰有 種:對 ,左邊由值為 的觀察組成。掃描對每一種各評估一次,所以在精確分數下,它回傳增益最大的劃分,增益平手時回傳閾值最小者。
證明
(閾值與值群組一一對應)
若 或 ,其中一邊為空。若 且 ,左邊恰好是前 個值群組,所以不同的 給出不同劃分。掃描逐組移動,因此第 次移動後,計數就描述第 種劃分,並由此計算增益。對全部 取最大值,就是對全部劃分取最大值。只在嚴格改善時更新最佳值,會保留遞增次序中第一個最大者,亦即閾值最小者。移動群組時每個觀察只被處理一次,所以排序之後,計數更新需 。
閾值按遞增次序掃描,而且只有嚴格改善才更新最佳值,因此此版本在同增益時選較小閾值。也可以另訂固定平手規則。此敘述指精確數學分數;數值實作須訂明精度與平手政策。本節點排序需 ,之後計數掃描需 。若 個特徵各自排序,單一節點的簡單界是 。整棵樹訓練會在之後節點重複工作,所以這不自動是全部訓練成本。深度 的樹,預測時至多做 次常數時間測試。
概念視角幾何
把決策樹看成特徵空間中的方盒
從幾何看,由 形成的決策樹以平行於座標軸的超平面切割特徵空間。每片葉子是一個方盒,即若干區間(部分可無界)的乘積,樹在每個方盒上預測同一個常數。對單一特徵的掃描,就是在已出現的取值之間,搜尋一個切割平面的 個不同位置。下面的 XOR 決策樹有四片葉子,分別對應兩個特徵切出的四個格子。
例題 3.2.6
(含重複值的閾值掃描)
取數值 ,標籤為 。節點有兩個 1 和三個 0,熵為 。互異值有四個,所以有三種可行劃分。值為 3 的兩個觀察必須留在一起。
| 閾值 | 左邊標籤 | 右邊標籤 | 加權子熵 | 增益 |
|---|---|---|---|---|
掃描儲存增益最大的 。把兩個值為 3 的觀察分開,意味著同一個測試中值 3 同時出現在兩邊,任何閾值都做不到,所以該劃分不在這三種之內。只需計算 個增益,而不是四個。
例題 3.2.7
(同一特徵值上的標籤衝突)
取觀察 。根節點有兩個 1 和一個 0,熵為 。唯一可行的劃分是 對 。左子節點的標籤為 ,熵為 1,右子節點是純的,所以增益為 。
左子節點不能再分,因為它的兩個觀察特徵值相同。按預測 0 的平手規則,該葉會把標籤為 1 的觀察判錯,所以整棵樹在三個觀察中錯一個。只使用 的任何樹都不可能更好:它對兩個 的觀察給出相同預測,而它們的標籤不同,所以至少有一個錯。剩下的錯誤是數據的性質,不是訓練程序的缺陷。
零即時增益也可能隱藏交互作用
反例模式
XOR 需要兩層,但每個第一步增益都為零
取全部四個二元特徵組合,標籤如下:
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
根的兩類平衡,按任一特徵分割後,兩個子節點也各自平衡,所以第一步資訊增益為零。若規則是最佳增益不為正便停止,就會留下訓練錯誤率為 的根分類器。
但先測試 ,再於兩個子節點測試 ,便得到四個純葉及零錯誤。第一步沒有改善即時熵分數,卻讓之後的分割能使用有用結構。一步貪婪選擇不是搜尋全部小型樹的全局方法。
容許零增益分割可幫助此例,但不會消除停止規則的需要。深度上限、最小子節點大小、沒有可用測試或標籤已純,都可以是停止原因。若相同特徵向量的標籤衝突,任何只用這些特徵的確定性測試序列,都不能把那些觀察分開。
訓練改善不等於泛化證明
假設二元特徵 與母體標籤 是獨立公平位元,訓練行與未來觀察都從此聯合分布獨立抽取。 時,樣本以正概率碰巧每筆都滿足 ,且兩個特徵值都出現。按 分割會產生純訓練葉及零訓練錯誤;但新觀察中,預測 的規則仍以概率 錯誤,因獨立性給出 。
因此,即使訓練增益達最大可能值,也就是未必等於 1 位元的父熵,仍不證明預測準確。應分清訓練、驗證及測試角色:用訓練數據擬合,用驗證數據選複雜度,保留未使用的測試集作最後評估。訓練不純度分數不能代替這些獨立的觀察。
簡化已長成的樹,一種方法是加入大小懲罰,比較候選子樹。設
其中 是訓練誤分類比例, 是葉數。考慮把有 個葉的子樹收合為一個多數葉,仍使用原本到達此子樹的相同觀察;收合錯誤數就是該區域的 。舊訓練錯誤數為 ,收合後為 。總訓練樣本數為 ,目標改變量是
錯誤數要除以整個訓練樣本大小 ,不是只除以子樹樣本數。其餘樹部分不變,在比較中抵消。若這是所選剪枝目標,差值非正便收合,等號時採偏好較小樹的平手規則。這精確比較兩個候選,不聲稱任意局部剪枝次序能找到全局最佳樹,也不聲稱某個 保證低測試錯誤。可用驗證數據協助選擇複雜度。
常見錯誤
(把子樹錯誤數除以子樹樣本數)
設 ,某個涵蓋 40 個觀察的子樹有 個葉,,,。正確的改變量是 ,所以按偏好較小樹的平手規則,該子樹會被收合。若錯誤地把錯誤數差除以 40,會得到 ,因而錯誤地保留子樹。 的每一項都以整個訓練樣本為尺度。
葉子的常數與不純度須一起替換,但加權減少量的結構不變。
通往推廣的路徑
類別更多或響應為數值時,哪些部分會改變?
葉子的常數與不純度須一起替換,但加權減少量的結構不變。
有 個類別時,熵變為 ,葉子預測出現次數最多的類別。若響應為實數並採用平方誤差,葉子上的最佳常數是其響應的平均值,對應的不純度是它們的方差,而分割後方差的加權減少量同樣非負,因為總方差可拆成子節點內部與子節點之間兩部分。劃分的論證不變;只需替換葉子規則和不純度。
有解練習
快速檢查
(1. 按觀察數加權子熵)
平衡節點有十筆觀察。候選分割把一筆標籤 1 單獨放入純子節點,另一子節點有四個 1、五個 0。求資訊增益。若錯用兩個子熵的未加權平均,會報告甚麼增益?
解答 · 解答 1
正確剩餘熵為 ,增益約 。未加權平均為 ,得到錯誤增益 。兩者父熵都用 1;差別全來自給大小一的子節點不合理的一半權重。
快速檢查
(2. 拒絕把相同特徵值分開的分割)
排序數值為 ,標籤為 。用 測試時,列出全部不同且兩邊非空的訓練劃分及增益。為何排序第二筆之後看似全純的分割不可用?
解答 · 解答 2
可用 及 ,分別代表區間 與 。每種都有一個純單元素子節點,及一個標籤比例為 或 的三筆子節點,增益同為 。閾值不能把一個 2 放左、另一個 2 放右。兩行之間看似增益 1 的分割,只是排序假象,不是有效特徵測試。
快速檢查
(3. 求 XOR 樣本的最小深度)
只容許測試個別二元特徵。證明深度一的樹不可能完全分類四筆 XOR,並給出能做到的深度二樹。嚴格正增益停止規則會怎樣?
解答 · 解答 3
深度一只有根測試及常數子預測,只能測 或 。兩種情況的每個子節點都各含一個標籤 0、1,因此每個常數葉錯一筆,合共四筆中錯兩筆。深度二可在根測 ,兩個子節點再測 ,四葉標記 ,便完全正確,所以最小深度是二。正增益停止規則不會走第一個零增益分割,停在深度零,錯誤率為 。
快速檢查
(4. 比較剪枝時不要改變分母)
訓練共有 筆。五葉子樹錯 12 筆,收合為一個多數葉則錯 20 筆。分別在 與 比較兩候選,其餘樹部分不變。
解答 · 解答 4
收合的目標改變為 。 時是 ,收合降低目標; 時是 ,此比較應保留子樹。兩者都用相同整體樣本分母 100。這只選出兩個帶懲罰訓練候選中較好的一個,本身不證明哪個在新數據上錯得較少。