如何理解決策樹的損失函數?

01-15

樓主，你好。

咱們可以這樣去看到問題，首先咱們將公司與通用的損失函數對比去分析： $C_{a} (T) = sum_{t=1}^{|T|}{N_{t} H_{t}(T) } + alpha |T|$ $Leftrightarrow$ $L(w,d) = frac{1}{N}sum_{i=1}^{N}{(y_{i} - f(x_{i} ))^{2} + r(d)}$

我在問題機器學習中常常提到的正則化到底是什麼意思？ - 陶輕鬆的回答 - 知乎中回答過r(d)是什麼的問題，我在文章中提到r(d)最簡單的方式就是表達成： $left| W ight| _{0}$ ,即代表損失函數中特徵項的數目，如果理解就pass，不能理解可以看看我的這篇文章，相信可以很快知道兩個損失函數的對應關係，即r(d) = $alpha left| W ight| _{0}$ 與 $r(d) = alpha |T|$ 具有完全等價的作用，都是為了約束模型複雜使用的，至於作用，很簡單：防止【過擬合】；這個時候你應該想到的就是下面第三幅畫面：

即每個樣本的，哪怕是由於雜訊產生一點小的偏差都被學習演算法學習到了，顯然他的容錯性、以及在正式使用的環境中誤差會很大，因為它「刻意」的匹配了學習了的很多無效的特徵(彎曲程度高，曲線的多項式就越複雜，還有的參數項就越多-----基本數學認知，不解釋)。

好了，既然咱們了解透了對應關係之後，咱們來對照一下，看看他們之間的關聯性；先談談他們損失函數的意義，為了便於理解，我們先去解釋通用的損失函數的意義:

即先看 $frac{1}{N}sum_{i=1}^{N}{(y_{i} - f(x_{i} ))^{2}}$ , 這個函數很好理解，即真實的分類與機器估計的分類之間的均方差，他要表達什麼意思呢？很簡答，它是要在不考慮任何的「過擬合」的情況下，只要求測試樣本的契合程度達到最高，即使得測試樣本盡量的跟學習演算法得出的分類一直，最好是100%的一致。優化的目標是：【是的該函數值越小越好】。

如果能夠理解上面劃線的這段話，咱們用自然的思維去考慮損失函數的定義問題。思考一下，如果是你，在建立了決策樹之後，你覺得應該如何去定義決策樹的損失函數？拋開書本上的那些死記硬背的東西。好了，咱們給出幾個思維導圖：

顯而易見，咱們應該讓每一個節點都盡量有自己明確的分類吧？即讓自己能夠被明確的決策出來吧？而且應該保證與其他樣本有所區分 (腦袋裡面想像上面【過擬合】的第三幅圖，如果不考慮「過擬合」，他就是單獨 $sum_{t=1}^{|T|}{N_{t} H_{t}(T) }$ 函數優化的目標)

顯而易見，為了跟通用損失函數的效果一致，即跟通用損失函數的定義一致，咱們應該讓【測試樣本與 $sum_{t=1}^{|T|}{N_{t} H_{t}(T) }$ 函數的效果】達到跟【測試樣本與 $frac{1}{N}sum_{i=1}^{N}{(y_{i} - f(x_{i} ))^{2}}$ 】完全一致的效果吧？

顯而易見，衡量「決策樹完全一致」的說明的是【確定性】吧？即確定性越強的損失函數最優值，說明學習方法效果越好。即損失函數要滿足：熵值越小函數結果越好。

顯而易見，對於「決策樹而言」，分類確定性越強的，損失就越小吧。

ok，了解了這些問題之後咱們再來確定這個問題，為了思維不至於直接跨度到下面這個表達式：

$C_{a} (T) = sum_{t=1}^{|T|}{N_{t} H_{t}(T) } + alpha |T|$

咱們先求一種極端的情況，請問在基於上文中的四個「顯而易見」的內容之後，咱們如何保證與「通用損失函數」相互對應的「決策的損失函數」達到最小？

注意我問的是情景，不是讓你寫出函數，先思考如何達到最小再說。很簡單吧：

我來回答一下：既然要保證損失最小，根據決策樹的定義而言，就只要讓測試樣本的擬合程度最高就行了吧，想想一下上面三張圖，在不考慮過擬合的情況下，只考慮損失函數的情況下，第三幅圖效果最佳吧！同理，有了這個前提，咱們不考慮決策樹的過擬合的情況下，只要保證決策樹的分類的熵的值越小越好！好的，回答上面提到的極端情況的問題，既然極端，咱們只要保證每個節點單獨成為一個葉節點就行了吧？這樣的分類就像上面的第三幅圖一樣，只要圈進去就行了，不需要考慮任何過擬合，也就是說曲線再複雜也沒關係。為什麼不需要考慮過擬合？因為這不是你經驗損失函數( $sum_{t=1}^{|T|}{N_{t} H_{t}(T) }$ )的職責，這是正則化( $alpha |T|$ )的職責，即這是正則項的功效。為什麼葉節點上只有一個樣本點的效果最好，因為熵的定義是p*log(p) 。 1*log1=0，0當然是最小的啦，熵的最小值，所以確定性最高。

好了，咱們確定了極端情況，但是畢竟不能完全按照極端的情況去處理，畢竟如果每個葉節點一個樣本，咱們的分類也沒那麼多啊，是吧？這如何是好？機器學習的思路，或者說統計學的思路咱們就可以借鑒了，既然咱們不能保證每個最小，那咱們就求他們和的極限，因為決策樹的熵都是大於0的，所以熵的和最小，就可以保證每個個體都是相對最小的，就可以保證整體最優。所以咱們將決策樹的經驗損失函數定義為，所有葉節點熵之和：

$sum_{t=1}^{|T|}{N_{t} H_{t}(T) }$

但是這樣容易出現過擬合啊，因為每次只要保證葉節點數量越多越好就行了，如果分類跟樣本差不多的時候，基本是100%過擬合的，每個樣本一個葉節點，熵最小。所以，為了防止這種情況的發生，咱們需要考慮【正則化】，正則化的過程在我的那篇文章中提到過了，我就不提了。

將r(d)定義為： $alpha |T|$ ，所以它的結構化風險定義為：

$C_{a} (T) = sum_{t=1}^{|T|}{N_{t} H_{t}(T) } + alpha |T|$

因為它是針對決策樹的，我們管這個叫做：決策樹損失函數。因為對於決策樹而言，單獨去考慮經驗損失函數是沒有任何意義的，很多情況基本100%過擬合，so，書本、機器學習的資料上面就沒有單獨去討論這個，而是直接給出了【決策樹的結構化風險】定義，即直接給出了【正則化】後的函數，而且給了它一個定向的名字，叫做「決策樹損失函數」。

說了這麼多，我感覺應該表達的還是挺通俗化的，望樓主採納；有任何問題可以在評論中給出，我看見就回答。

PS，順便提一句，所有的學習演算法的【正則化】即【經驗損失結構化】的形式都是固定的：經驗損失+範數結構，經驗損失是為了是學習演算法匹配測試樣本，範數是為了過擬合。

講到這裡，特地的給大家強調一下，生成模型和判別模型的區別。很多人都僅僅是知道有這麼兩個模型，以及定義上有差別，其實在他們的經驗風險最小化的方式也是有區別的：

判別模型有正規化過程，比較 $y_{i}$ 與 $f(x_{i} )/P(y_{i} |x_{i} )$ ,因為直接是生成f(x)或者p(y|x),所以很容易比較 y 和 f(x)的關係，也容易過擬合。過擬合產生的方式很簡單，主要就是由於缺乏過程，只能依靠f(x)/p(y|x)機械式的產生數據，知其結果不知其所以然。所以需要時時刻刻的防止他過擬合，都是依葫蘆畫瓢去判別的，所以才有r(d) 這個正則化項存在的意義。

相反，

生成模型一半都是直接給出生成數據的過程，知其結果也知其所以然，例如求聯合概率分布P(x,y),再比如說kd近鄰發、決策樹，我們是實實在在的知道每個數據欄位的含義、同時結構也有明顯的意義。所以他的過擬合情況相對來說會很少，故：

1、k近鄰法考慮的是經驗風險（等價於誤分類率），沒有考慮正則化。

2、朴樹貝葉斯法也是只考慮期望風險（等價於後驗概率最大化），沒有考慮正則化。

「沒有考慮正則化很簡單，因為他們很少【過擬合】」。一定要記住這句話，不要為了正則化而正則化，只有在【過擬合】的時候才需要。
當然事無絕對，決策樹算是生成模型的一種特例，說實話，熵也是一個很虛的概念，他代表的不確定性更多的是由於特殊欄位出現在列別當中的比率導致的，帶有比較大的偶然性。所以有點類似判別模型，故給了個正則化項。

機器學習是一門思考的科學，萬變不離其中，多考慮基礎，多思考思路，總思維、輕記憶。千萬不能死記硬背，碰到迷茫的問題的時候，站在解決問題的角度去思考一個方案，你往往就能夠明白這些書本中覺得「理所當然的公式」的意義了。

---------下面內容2016-11-19 15：06更新

----------------------------回答下面評論Erik的問題，他說兩種模型區別描述的不太清晰--------------

補充一段話：

理解，這兩個東西單純的講理論的話過於抽象，我舉個最近比較火的「互聯網烏鎮峰會排座位」的例子來說明一下這個兩個model的區別：

訓練數據集為，D={(x1,y1),(x2,y2),(x3,y3).....(xn,yn)},

x的特徵集為A=(公司市值，公司創造人員規模，影響力),

特徵一：A(公司市值)={小於10億美金,大於10億美金且小於100億美金，大於100億美金且小於1000億美金，大於1000億美金}={1，2，3}

特徵二：A(公司創造人員規模)={百，千，萬}={1，2，3}

特徵三：A(影響力)={高，中，低}={1，2，3}

將他們均數值化成1，2，3是為了在判別模型當中可以使用。

假設C為類標記，可分為7類，{1，2，3.....,7}分別代表1-7排

ok，好了，現在我們要求用判別model和生成model 分別去搭建學習演算法：

首先，通過判別model

我們可以學到到類似:f(x) = a*x1(1) + b*x1(2) +c*x1(3) ,其中a，b，c使我們根據D學習到的參數。

假設現在給定一個人，說他是馬雲，特徵為：{市值2000億美金，萬人，高影響力}，我們很簡答的只需要將他帶入f(x)就行，即：

f( {3,3,1} ) = 1,

即直接得出馬雲做第一排。這是判別model的思路。

然後，我們看看生成模型會如何生成學習，生成模型的代表就是樸素貝葉斯、k近鄰法，決策樹等等，我們隨便舉個例子，假設咱們用決策樹。首先應該是生成一系列類似於
if-then
的決策樹，根據決策樹的知識咱們知道，每次選擇熵最大的特徵作為根節點，假設特徵一即「市值」的熵最大，那麼首先判斷的就是市值，例如咱們根據市值分成3個分支，每個分支再根據熵選擇根節點。。。。。等等，例如最後的生成樹如下：

市值（根節點）

&>1000--1排 100-1000 &<100

萬-2排千-2排百-3排萬千百-6

高-3 中-4 低-3 高-4 中-5 低-6

上面每一行代表一層數，數值後面帶有數字(1-7)的，說明是葉節點，判定到此結束。得到生成樹之後，咱們，要預測馬雲座位的時候，根據其特徵，{市值2000億美金，萬人，高影響力}，咱們首先判別他的市值，然後走最左邊的節點，判定他做第一排。。

再比如要預測搜狗CEO王小川座位的時候，根據他的特徵{ 市(估)值20美金，千人，影響力高 },先判斷估值：小於100，走最右邊分支，再看公司規模：千人，接著走中間分支，再看影響力：高影響力，所以預測他做第五排。每個特徵參數都有意義吧。

ok，不好畫圖，所以屬性結構有點扭曲。但是基本思路是這樣的。

對比一下，咱們不難發現，判別模型學習的是權重，但是他不對特徵數據本身賦予什麼實際的意義，所以將其特徵值轉變為數值參數都可以，可以說他是依葫蘆畫瓢的去生成一個座位號，沒有任何人性的思維一樣，相當於跟做題目的時候直接套公式一樣，所以，很容易出現過擬合的現象，所以才需要正則化。很淺顯的道理，聯繫一下生活就知道了：你做聯繫題(
測試樣本數據 )的時候總是死用公式，一旦正式考試( 預測正式數據 )的時候，一旦出現了一個公式套不上的你就傻眼了，直接就會犯錯(
預測錯誤率增高 )。。。所以才叫過擬合，因為你的公式只適合於你做的練習題，不適合有點干擾沒法套公式的情況，就這麼個意思。

相反，生成模型，不單單能夠得出結論，而且還告訴你每個特徵的意義，讓你知道我是怎麼得出結論的。所以儘管沒有死的公式，但是一旦考試（預測正式樣本數據）時，你能夠根據生成的模型去分析每個欄位，從特徵著手去分析數據，知其然知其所以然。例如，假設現在李彥宏也來參加互聯網峰會了，我們只是知道他是兩個特徵{市值400億美金，公司不到萬人}，這個時候判別模型已經失效了，但是在生成模型當中你依然可以預測到他的座位大致就是第二、三排。而且很少出現過擬合的現象。

這就是兩個模型的區別，所以我才說：

判別模型容易過擬合，所以基本都要正則化；

生成模型很難過擬合，所以很多都沒有正則化項，但是某一些生成模型由於數據不太離散，決策時有時候也會存在一些過擬合的現象。所以有一些特殊的情況也要考慮一下過擬合。

當然這裡我只是從正則/擬合的角度去出發思考的，他們還有很多其他的差別，例如判別模型雖然沒有現實意義，但是在樣本數據量小的時候它的效果比生成模型要好的多，而且判別模型消耗的資源、複雜度都要比生成模型小得多。。有利有弊吧，還是那個思路，萬變不離其中，搞清楚了也就那麼回事而已~

以前很少打字，多有不便。希望已經解釋清楚了。

謝邀, 盡量用通俗易懂的語言描述一下, 希望能夠幫助大家理解這玩意.

1. 決策樹本質上是按照某種方法/某些條件對數據進行分類. 正如一般的樹結構, 這個分類是可以不斷嵌套, 按層逐級細分的, 直到滿足某個/某些條件為止. 一個最簡單的例子是, 對某個數據按照一個條件進行分類, 這就是最簡單的樹, 可以用很簡單的代碼實現.

例如有個數據集, 其中一個指標的直方圖如圖所示, 如果按照該指標將數據集分為A和B兩類的話, 最簡單的方式就是給定一個閾值40, 小於該閾值的, 則為B, 大於等於該閾值的, 則為A.

代碼簡單的寫成:

當然, 這個分類的效果很一般, 大概正確率是 79%. 詳細情況見圖:

這種最簡單的分類情況, 就是一個只有兩個節點的樹, 看起來就是:

在這裡, 簡單粗暴, 但效果並不太好. 於是, 我們燒著樹, 吃著火鍋唱著歌 "決策燃棵樹, 樹在鍋下泣, 本來要生長, 奈何燒太急".

2. 為了讓"決策樹"的決策做的更好, 我們不能滿足於"兩條腿"的樹, 於是, 我們給這棵樹澆灌, 讓它茁壯成長. 比如, 下面就是一棵長得更好的樹:

問題在於怎樣長出這麼一棵"好看"的樹出來呢? 其中一種方法是"貪婪", 也就是, 先設定好規則, 然後不斷進行二分分裂, 知道滿足預定的條件就截止.

3. "貪婪"演算法還算不錯, 但有其固有的缺陷, 也就是有可能陷入局部最優的情況. 一個可能的例子是, 對於某個節點, 再次分裂會使得整棵樹的效果變差, 那麼這個時候, 樹的生長就該停止了. 但其實這個時候, 如果某個子節點再次生長(分裂), 效果能夠更好. 比如:

比如上圖, 在Case 0的時候, 嘗試對AB進行分裂, 分裂成AB1和AB2, 見Case 1, 發現效果變差, 那麼貪婪演算法就會停止在這個分支的生長. 但其實如果對AB1繼續分裂, 見Case 2, 這時效果有可能變得更好. 但貪婪演算法一般不會嘗試這一步, 於是乎, 錯過了人生中更加美好的時刻.

4. 為了解決"貪婪"存在的一些問題, 一種辦法是, 先"生成"一棵足夠大的樹, 然後對其進行剪枝,看看是否效果能夠更好.如果能夠更好的話, 就把"該枝"給剪了, 留下"殘缺"的樹. 大概的樣子是:

在Case 0 的時候, 先生成一棵較大的樹. 然後嘗試著對AB2這個點進行剪枝, 剪去3和4兩個葉子節點, 測試一下效果如何? 測試的結果是效果變差了, 於是該剪去的枝得保留. 然後呢嘗試著對5,6 和7,8 等節點進行剪枝, 發現效果變好, 就繼續,一直剪到保留AC為止, 就是Case 2的情況.

5. 怎麼剪枝呢? 當然不能想上述一眼傻傻的一點點試, 有一個流行的方法叫"成本-複雜度剪枝". 大概是先生成一棵足夠大的樹T0, 然後將這棵樹進行剪枝, 然後通過設定好的標準來衡量何時終止剪枝. 這個標準就是題主截圖中的公式:

$C_{alpha}(T) = sum_{t=1}^{|T|}{N_t H_t(T) + alpha|T|}$

在這個公式中, $alpha$ 可以認為是一個參數, 用來調節樹的大小以及樹與數據擬合好壞之間的權衡. 這個值為0的話, 就是初始的 *大樹T0* 了. 這個值越大, 樹就越小, 被剪去的枝枝葉葉就越多. 而那個|T|是表示樹的葉子節點的個數, +號後面的部分大概就可以理解了, 可以認為是樹的複雜度.

6. 接下來說 $sum$ 這裡面的內容. 首先說求和符號裡面的內容, 就是 $N_tH_t(T)$ . 這個可以這麼來理解. 一棵樹有很多個節點, 對每個節點進行編號, 分別為1, 2, ..., t-1, t, t+1, ..., |T|. 那麼對於編號為t的節點, 有兩個屬性, 這兩個屬性的"名字"分別取為 $N_t$ 和 $H_t(T)$ . 前一個好理解, 就是決策樹在該節點 (在特定數據集中訓練的時候) 的樣本數. 而後一個呢, 在題主的截圖中就是另外一個公式了, 它的學名叫交叉熵, 原始定義來自於香農的資訊理論, 在決策樹發展過程中被引進來的. 對這個公式的理解在下面說, 這裡先說一下在熵被引進來之前, 決策樹用了另外一個叫"錯誤分類率", 或者簡稱"誤分率" 的條件. 它大概指對於一個樣本點來說, 它本來應該是A類的, 但卻被分在了B類中. 誤分率可以簡單的認為前面"餅圖"中的Not部分, 對於Class A節點來說就是Not A的佔比, 對於Class B來說就是Not B的佔比.

7. 通過前面的敘述, 大概能夠總結出, $C_{alpha}$ 就是成本-複雜度的一個權衡, 當最小化這個標準的目標達成後, 就能夠得到一棵不錯的決策樹.

8. 繼續6對 $H_t$ 的理解. 為了得到更好的效果, 前輩們對 $H_t$ 進行改善, 把資訊理論中熵的概念給引入到決策樹中來, 用熵來衡量決策樹的好壞, 這個就是題主中所提到的公式:

$H_t(T) = -sum_{k=1}^{K}{hat{p}_{tk}log{hat{p}_{tk}}}$ $hat{p}_{tk} = frac{N_{tk}}{N_t}$

這裡的K是分類的類別, 表示的是多(K)分類的情況, 如果K=2的話就是二分類了. $hat{p}$ 從定義就能夠看出來是指: 在節點t中, 屬於k類的樣本點的比例. 不理解的朋友們, 可以將其簡化為二值分類, 在紙上畫畫就應該能夠明白的. 交叉熵對誤分率是一個大的改進, 至少兩方面相比誤分率是有優勢的, 一是誤分率是不可微的(可微是很重要地), 另外一個是效果要比直接誤分率更好(如果效果更差, 當然不會被引進來了).

上圖中mce是指誤分率, 由於中間有個折點(在0.5的位置), 導致了其不可分. 而熵則是平滑的曲線.

差不多就這樣了, 希望看到的朋友能夠立即. 如有問題歡迎討論.

公式中H(X)可以理解為這個葉子節點的熵。如果把決策樹一直劃分下去，葉子節點的熵應該為0，只有一個類。但是如果使用一些剪枝規則，每個節點中仍然可以有熵值，也就是可以繼續劃分。

Nt是這個節點中的樣本的個數，可以看做這個節點的權重。節點中樣本數越多，權重越大。

所以，公式前面一項代表決策樹所有葉子節點的熵值的加權和。每個節點的樣本分類純度越高，這個值就越小。

後面一項是對整棵決策樹的複雜度的懲罰項，結點數越多，越複雜。相當於一個正則項，也可以理解為先驗概率：較小的樹有較大的先驗概率。

個人見解，可以參考一下：

X如果可以取三個值：x1,x2,x3,概率分別為p1,p2,p3。

那麼-log(p1),-log(p2),-log(p3)相應稱為x1,x2,x3的自信息，代表了它們各自的不確定性（資訊理論）。X的熵指的是X的所有取值的期望，H(X)可以理解為平均值，那X總的不確定性其實也可以用3*H(X)來表示。

題中N個結點，每個Nt結點都可以理解為這樣的X，那麼整棵樹的不確定性（損失）就是所有葉結點的總熵Nt*Ht(T)的和，而不是平均值Ht(T)的和。

函數後面的|T|是對整棵決策樹的複雜度的懲罰項，結點數越多，越複雜。

題主的問題可能是如何理解整個式子的意思吧，前面幾位已經講的很好了，但相信也有很多人是因為不能理解為什麼要乘以Nt才來到這個問題下的，比如我。

現學現賣一下。（只能作為理解，並沒有嚴格的推導）

首先問一個問題，Ht(T)代表的是什麼？你肯定會說是經驗熵，那什麼是經驗熵，你肯定會說是不確定度，到這裡都沒錯，那這個不確定度是什麼的不確定度呢？

我的理解是，這個葉子節點內部取k個類的不確定度，注意是節點【內部】的不確定度，每個葉子節點可以看作是獨立的，既然是內部的事情，憑什麼暴力的將各個內部的不確定度相加，我們至少到同一個級別的平台再加吧。

不知道你現在有沒有感覺暴力的相加確實少了點什麼，我的理解是，少了該節點的樣本數，也就是Nt。不知道你有沒有注意到，信息熵只用到了概率，而忽略了樣本數，也就是只關注內部各個類別的比例，而不在乎整體數量的多少，那麼乘以Nt後，我們把它叫做不確定次數，不確定程度就是不確定次數歸一化後的東西。

既然都這麼暴力了，就更暴力一點，你把Ht(T)理解成頻率，Nt*Ht(T)對應地理解成次數吧。比如有A股B股兩支股票，A股買了10次，賺了7次，B股買了100次，賺了50次，賺的頻率分別是0.7和0.5，那麼計算你投資的能力，是0.7+0.5更有意義呢還是7+50更有意義呢？我覺得7+50更有意義吧。

雖然不確定性和不確定次數並非頻率和次數，但它們的相對關係就這麼理解吧。

（純屬理解用，不嚴謹請見諒，如有更嚴格的推導和理解麻煩順便@我一下，謝謝：）！）