動機
知識獲取問觀察及專家判斷怎樣變成可支持決策的表示。引擎可以完美套用規則,但規則太廣、互相矛盾或漏了變量,仍不可靠。決策樹提供透明的提議方法:每條路記所問問題,每葉記結果。
透明不把歸納變成演繹。從四例學的樹也會決定未見例,純訓練葉不證普遍物理定律。我們因此完整規範有限工具的格式、分割、終止、編譯及解釋,再分開工具正確與領域政策正確。
定義
定義 27.1.1
(訓練表、節點與二元熵)
有限表每行 對 個具名布林(Boole)屬性給零或一,標記 亦二元,重複行照計。非空節點的正標比例 ,二元熵為 ,端點零乘對數零定為零。
定義 27.1.2
(資訊增益與葉預測)
屬性 分成大小 的孩子,節點大小 ,資訊增益為:
空孩子項權重零,無須定 。葉預測多數,平手取零;空孩子取父多數作明訂後備,不是假稱該孩子有觀察證據。
定義 27.1.3
(有限學習器)
有限學習器在節點純或無剩餘屬性時停;否則選最大增益,按固定屬性順序破同分,兩支遞歸並移除所選屬性。它不會只因最大增益零就停,每路同屬性最多測一次。這個完整政策讓定理與可選剪枝啟發分開。
定義 27.1.4
(編譯規則與解釋)
葉路徑給屬性值的合取,編譯規則以此為條件、葉標記為結論。完整輸入只循一條路,解釋就是實際測試值序列與葉,不必聲稱物理因果。部分觀察則需另訂政策,例如所有完整填法都同標才答,否則未知。
定理/命題
定理 27.1.5
(有限決策樹的熵帳目)
固定非空表經有限樹分割, 是全部行到節點 v 的比例, 是其局部增益,則
每個增益非負,總減幅不超根熵,且恰在所有非空葉純時等於根熵。這是該表的經驗恆等式,不是母體泛化界。
定理 27.1.6
(有限學習與精確規則編譯)
上述學習器會終止,深度至多 m。葉規則對完整布林輸入互斥且窮盡,評估結果與樹在所有完整輸入一致。若相同特徵向量從無矛盾標記,不剪枝學習器會擬合每行,即使中途增益為零。若同向量有相反標記,任何依這些屬性的確定函數都不能同時擬合。
證明思路
證明
(凹性與逐層相消)
熵在內部的二階導數為 ,連續延伸保凹。父比例是孩子比例加權平均,凹性證父熵不小於加權子熵,即增益非負,空支以零權重處理。
每內節點增益乘全域到達比例,再對樹相加。內孩子的負熵項,恰與該孩子作內節點時的正熵項同權相消。只剩根正項與葉負項,得帳目。葉熵非負,恰在非空葉純時為零,證餘下結論。
證明透視
局部增益只是全域帳目一項
下一問可以零增益,條件化後再問卻有用。帳目把各節點增益乘到達比例,不要求根立即說明所有標記差異。零增益即停是額外建模政策,不是熵非負推出的結論。
證明
(終止、互斥規則與擬合)
終止因每個非葉調用少一屬性,深度最多 m,分支有限。完整輸入每測一次只走一邊,必到一葉並滿足其條件。兩葉有首次分岔,對同一屬性要求相反值,不能同時滿足,證互斥與窮盡,也證樹規則等價。
深度 m 後仍同組的行,全部特徵相同;標記一致時必純,較早純葉也擬合,所以全表正確。有矛盾時,確定輸出對同向量只有一值,至少一行錯。葉多數最小化該葉錯誤數,因兩種輸出分別錯另一類的行數;它不判斷哪個原標記才符合真實領域。
證明透視
每項保證用到哪個假設
終止性只用到每次遞歸調用都消耗一個屬性,所以深度至多為 。互斥性來自兩條葉路徑第一次分岔之處:該處測試同一個屬性,卻取相反的值。擬合性才是假設起作用的地方:只有在深度 時,仍被分在一組的數據行才必定有相同的特徵向量,而標籤一致令這樣的組成為純粹。若去掉一致性,同一論證只能得到一片多數葉,至少有一個錯誤。熵在這個證明中不起作用;增益規則決定建出哪一棵樹,卻不決定這三項性質是否成立。
例題詳解
例題 27.1.7
(學 OR 並核對每個 bit)
四行 為 。根熵 ,分 A 得兩等大孩子,熵一與零,增益約 。B 同分,固定順序選 A。A 零支再問 B,局部增益一,權重一半,帳目 ,葉純、訓練錯零。根增益不是整份解釋。
概念視角分析
資訊增益就是互資訊
把一個節點的數據行看作屬性值與標籤的數對 上的經驗分布,則
即聯合分布相對於其邊際分布之積的散度。在 OR 表中,、,得 ,與上面算出的增益相同。增益為零,恰好表示該屬性與標籤在這個節點內經驗上獨立。
例題 27.1.8
(編譯並解釋政策)
規則為 A 一則標一;A 零且 B 一則標一;A 零且 B 零則標零。 的實際路是 A 零、B 一、葉一。只知 A 一時,兩個 B 填法都標一;只知 A 零卻未定,因 B 改答案。正規則析取可化成 ,但原路徑仍保留工具真正問過甚麼。
例題 27.1.9
(矛盾案例暴露表示限制)
列為 。零零兩例不論怎分仍同葉卻標相反,平手取零錯一,經驗錯誤 。任何 A,B 確定規則至少錯其中一行。應檢查錯標、時間變化或漏量度;不增加資訊只加深樹,不能分開同向量。
配套可執行工具實作此政策,輸出 OR 樹、葉規則、預測及路徑;核心遞歸如下:
function grow(rows, attributes, fallback = 0) {
if (rows.length === 0) return { label: fallback };
const majority = rows.filter(row => row.y === 1).length > rows.length / 2 ? 1 : 0;
if (rows.every(row => row.y === rows[0].y) || attributes.length === 0)
return { label: majority };
const test = attributes.reduce((best, name) =>
gain(rows, name) > gain(rows, best) ? name : best);
const rest = attributes.filter(name => name !== test);
return { test,
zero: grow(rows.filter(row => row[test] === 0), rest, majority),
one: grow(rows.filter(row => row[test] === 1), rest, majority) };
}
配套另提供熵、增益、格式檢查、預測與規則抽取,這段不是聲稱未定義 helper 自己能執行的獨立程式。屬性序處理計算結果同分,浮點熵可影響極接近比較,但終止與等價性對任何剩餘屬性選擇都成立。工具應記數據、格式、同分政策與實際輸出,而不只報一句「智能建議」。
空分支尤其能區分工具政策與證據。如果訓練表從未出現某屬性組合,遞歸仍須定義完整輸入到達該分支時怎樣作答;沿用父多數令函數完整,卻沒有創造新的觀察。解釋介面應能指出這是後備葉,讓用戶知道結論來自政策延伸,而不是該分支已有很多相同案例。
知識獲取還應保存數據版本與標記依據。專家改一行標記後,樹的分割順序可能連根節點都改變,所以不能只修改屏幕上某條規則而假裝仍是原訓練結果。應重新執行同一已記錄政策,比對新舊規則與案例,再讓領域審核決定是否接受改動。可重播的工具把這些決策變得可查,不代替決策本身。
常見錯誤
反例模式
零即時增益可藏有交互作用
完整 XOR 表上 A、B 根增益都零,每孩子仍各半。但先分 A,再各問 B,全部葉純,總熵減一 bit。零增益即停會輸出常數多數,錯過完全可表示的交互作用。本學習器到純或屬性盡才停;剪枝另論。
常見錯誤
(把樹的規則當作領域定律)
工具規則是構造樹的演繹後果,不是有限觀察在無限制世界的邏輯後果。很多函數在未完整表上同意,表外卻不同。專家要檢查條件、混雜因素及錯建議成本,再用獨立、符合使用場景的案例測預測。解釋清楚也不能代替外部驗證。
常見錯誤
(以零代替缺失值、以頻率當作概率)
不要默默把缺量度當零,零在格式中是真正觀察值;完整輸入格式錯則工具拒絕,部分輸入要另一語義。葉標記比例也不自動校準為概率,尤其樹本身由同數據挑出。訓練錯小、路徑有說服力及外部可靠性是不同問題。每個後備決定都應可追溯,尤其不能把沒有案例的空葉說成已由數據驗證的專家結論。
總結
有限樹學習可完全規範與核對:熵減逐層相消,屬性耗用令終止,葉規則精確保留函數與路徑。這些是工具的演繹保證;所學函數是否反映領域,仍需充分特徵、可信標記及新證據。
練習
練習 27.1.10
(對完整的四行 XOR 表,求根熵、兩個根增益、先分 後的兩個條件增益,以及加權熵帳目。)
核心
四行 為 。
解答(3)
- 1
計算根熵與根增益
兩行標零、兩行標一,所以 bit。以 分割得兩個孩子,每個孩子各有一行零標與一行一標,熵都是一,故 ; 同樣。
- 2
計算先分 後的條件增益
關鍵一步
的每個孩子有兩行、標記不同,再以 分割便得純葉。每個孩子熵為一,其兩個子節點熵為零,所以每個條件增益是 。
依據: 根增益為零不代表下一問沒有用。
- 3
合成加權帳目
每個孩子的全域權重為二分之一,帳目為 ,等於根熵,而且所有葉都純、熵為零。第一問增益為零,並不排除兩步分割有效。
練習 27.1.11
(某節點有八行,兩種標記各四行。一次分割得類別數 與 。求資訊增益及分割後的多數類訓練錯誤。這兩個數量可以互換嗎?)
基礎
解答(3)
- 1
計算增益
父熵為 。每個孩子有四行,標記比例為 或 ,熵為 bit。兩個孩子權重都是二分之一,所以 bit。
- 2
計算訓練錯誤
每個孩子預測其多數標記,各錯一行,所以錯誤為 。
- 3
比較兩個量
前者是以 bit 計的熵減,後者是錯分比例,公式與單位都不同;兩者也都不是對未來錯誤率的保證。
練習 27.1.12
(某樹先測 : 時回傳零; 時再測 , 回傳一, 回傳零。寫出全部葉規則,化簡正條件,並評估「 而 未知」的部分觀察。)
核心
解答(3)
- 1
寫出葉規則
三片葉給出: 則標零; 且 則標一; 且 則標零。
- 2
化簡正條件
只有一片葉預測一,所以正條件是 且 ,即 。
- 3
對 套用所有完整填法政策
且 時標記為零, 且 時標記為一。兩種填法不一致,所以政策回傳未定。把未知的 當作假,是在回答另一個問題。
依據: 只有未知屬性的每個填法都給同一標記,才回傳標記。
練習 27.1.13
(兩行訓練數據有完全相同的完整特徵向量,但標記相反。證明任何依這些特徵的確定樹或規則函數都不能同時擬合兩行。再多重複其中一種標記,能消除這個表示衝突嗎?)
綜合證明
解答(3)
- 1
利用確定函數對每個向量只有一個輸出
設 為任何依特徵的確定函數, 為共同的向量,則 只是一個標記。
- 2
與兩個標記比較
關鍵一步
的一次出現標零,另一次標一,所以 至少與其中一個不同。因此 在這兩行上至少錯一行,不存在能同時擬合兩行的 。
- 3
檢視重複副本
∎增加同一標記的副本會改變多數及錯誤比例,但兩個衝突標記仍然同時存在,一個輸出仍不可能等於兩者。要處理衝突本身,需要新的資訊特徵,或修訂對數據的解讀。