如何選擇𝛼αalpha在成本複雜性修剪中？
在接下來的講座樹方法中，他們在第 21 頁描述了一種用於成本複雜度修剪的樹算法。它說我們將成本複雜度修剪應用於大樹，以獲得最佳子樹序列，作為以下函數. 我最初的想法是我們有一套（IE. 然後我們計算每個集合的 K 折交叉驗證並選擇對應於最低的 K 折交叉驗證。
作為參考，我所指的 K 折交叉驗證在以下Cross-Validation的幻燈片 15 中進行了描述。
然而，經過一番思考和閱讀；我發現有一個定理，即通過最弱鏈接修剪經過的子樹序列將包含子樹. 在哪裡是最小化成本複雜性標準的子樹
在樹方法幻燈片 中的幻燈片 19 中進行了描述。 由於這個定理存在，我認為您可以推斷出每個定理的簡潔映射可能是合理的到最優子樹. 或者至少我們可以看到在一定的時間間隔內s 它將對應於特定的子樹。我在第 4 版的Elements of Statistical Learning book的第 308 頁上找到了這個定理。如果有人能闡明算法並且知道這樣的映射是否存在會有所幫助。
是的，確實存在這樣的映射，但它的用處不如預期。
總體目標是最小化成本複雜度函數 $$ C_\alpha (T) = R(T)+ \alpha|T| $$
在哪裡 $ |T| $ 是樹的葉子數 $ T $ 和 $ R(T) $ 在這些葉子上計算的損失函數。
第一步是計算子樹序列 $ T^0\supseteq T^{1}…\supseteq T^{n-1}\supseteq T^{n} $ 在哪裡 $ T_n $ 是僅由根節點組成的樹，並且 $ T_0 $ 整棵樹。
這是通過連續替換子樹來完成的 $ T_t $ 有根節點 $ t $ 帶有葉子（即折疊此子樹）。在每個步驟中，子樹 $ T_t $ 被選中，它使成本複雜度函數的降低最小化，因此是樹的最薄弱環節。
如公式：最小化 $$ C_\alpha(T-T_t) - C_\alpha(T)\ =R(T-T_t)+ \alpha|T-T_t| - (R(T)+ \alpha|T|)\ =R(T-T_t)-R(T)+\alpha(|T-T_t|-|T|)\ =^1 R(T)-R(T_t)+R(t)-R(T) + \alpha(|T|-|T_t|+1-|T|)\ =R(t)-R(T_t) + \alpha(1-|T_t|)\ $$
這正好是 0
$$ \alpha=\frac{R(t)-R(T_t)}{|T_t|-1} $$
所以最小化 $ C_\alpha(T-T_t) - C_\alpha(T) $ 意味著最小化 $ \alpha=\frac{R(t)-R(T_t)}{|T_t|-1} $
所以從整棵樹開始 $ T^0 $ （和 $ \alpha^0=0 $ ) 在每一步 s 算法
- 選擇最小化的節點 t $ \frac{R(t)-R(T^{s-1}_t)}{|T^{s-1}_t|-1} $
- 放 $ T^s=T^{s-1}-T_t $ , $ \alpha^s=\frac{R(t)-R(T^{s-1}_t)}{|T^{s-1}_t|-1} $
直到樹只包含根節點。
因此，作為輸出，我們得到一系列子樹
$ T^0\supseteq T^{1}…\supseteq T^{n-1}\supseteq T^{n} $
與相應的 $ \alpha $ -價值觀
$ 0=\alpha^0\leq\alpha^1\leq…\alpha^{n-1}\leq\alpha^{n} $
使用這些值可以定義一個映射 $ \alpha $ 到子樹列表。
但
成本複雜度函數和損失/誤差函數是在訓練數據上計算出來的，因此存在自我驗證和過擬合的危險。正因為如此決賽 $ \alpha $ 由交叉驗證確定。 $ ^2 $
計算在所有訓練數據上訓練的樹的子樹序列（在通過內部交叉驗證優化之前）至少給了我們一個可能的區間 $ \alpha $ - 可供選擇的值。
資料來源：
- Alexey Grigorev解釋的成本複雜性修剪
- Kiran Bangalore Ravi、Jean Serra對隨機森林進行成本複雜性修剪
- 弗里德曼等人的統計學習要素。人
以上所有來源均指的是*Breiman, L.、Friedman, J.、Olshen, R. 和 Stone, C. (1984)。分類和回歸樹，紐約沃茲沃思。*不幸的是，我無法得到它。
附錄
(1)為什麼這是真的？
$$ =R(T-T_t)-R(T)+\alpha(|T-T_t|-|T|)\ =R(T)-R(T_t)+R(t)-R(T) + \alpha(|T|-|T_t|+1-|T|)\ $$
用圖片更容易理解
讓我們看看 $ R(T-T_t)=R(T)-R(T_t)+R(t) $
誤差/損失函數 $ R $ 在輸入樹的所有葉子上計算。轉型 $ T-T_t $ 折疊子樹 $ T_t $ 成一片葉子 $ t $ . 所以 $ R(T-T_t) $ 是
- $ R(T) $ （在所有葉子上）
- - $ R(T_t) $ （穿過“已移除”子樹的葉子 $ T_t $ )
- + $ R(t) $ （穿過新加入的葉子 $ t $ 子樹 $ T_t $ 已折疊到）
同樣的邏輯適用於計算葉子數量的部分。
(2)如何確定 $ \alpha $ 通過交叉驗證？
我不確定這是否是佳能，但我會這樣做。
輸入：外圍交叉驗證提供的訓練數據
在整個訓練數據上訓練樹
計算子樹序列 $ S $ 和 $ \alpha $ s $ A $ 去測試。
應用內部交叉驗證。對於每次運行：在內部交叉驗證提供的訓練數據上訓練樹
計算子樹序列
對於每個 $ \alpha $ 在 $ A $ ，保留最小化的子樹 $ C_\alpha(T) $
在測試集上評估這些測試樹
選擇 $ \alpha $ 基於內部交叉驗證的最佳性能
在序列中查找子樹 $ S $ 基於整個訓練數據構建 $ \alpha $
返回那個子樹
在斯坦福大學的一次講座中描述了類似的方法（從幻燈片 10 開始）。
