決策樹的 VC 維度是什麼？
具有 k 個二維分割的決策樹的VC 維度是多少？假設模型是 CART，並且唯一允許的拆分平行於軸。
因此，對於一次分割，我們可以在三角形中排序 3 個點，然後對於點的任何標記，我們可以獲得完美的預測（即：破碎點）
但是 2 次分裂或任何一般的 k 呢？
我不確定這是一個簡單答案的問題，我也不認為這是一個甚至需要詢問決策樹的問題。
請諮詢Aslan 等人。,計算樹的 VC 維數(2009)。他們通過在小樹中進行詳盡的搜索來解決這個問題，然後提供一個近似的遞歸公式來估計大樹上的 VC 維度。然後他們使用這個公式作為修剪算法的一部分。如果您的問題有一個封閉形式的答案，我相信他們會提供它。他們覺得有必要在很小的樹上進行迭代。
我的兩分錢值。我不確定談論決策樹的 VC 維度是否有意義。考慮一個維度響應，其中每個項目都是二元結果。這是 Aslan 等人考慮的情況。有該樣本空間中的可能結果和可能的響應模式。如果我建立一棵完整的樹，水平和葉子，然後我可以粉碎任何圖案回應。但是沒有人適合完整的樹。通常，您會過度擬合，然後使用交叉驗證進行修剪。最後得到的是一個更小更簡單的樹，但你的假設集仍然很大。阿斯蘭等人。嘗試估計同構樹族的VC維數。每個族都是一個假設集，具有自己的 VC 維度。
上一張圖片說明了一個空間樹這打破了4點：. 第四個條目是“響應”。阿斯蘭等人。會認為一棵形狀相同的樹，但使用和，比如說，是同構的並且是同一假設集的一部分。因此，雖然這些樹中的每棵樹上只有 3 片葉子，但這些樹的集合可以破碎 4 個點，在這種情況下 VC 維度為 4。但是，同一棵樹可能出現在具有 4 個變量的空間中，在這種情況下，VC 維度將為 5。所以它很複雜。
Aslan 的蠻力解決方案似乎運作良好，但他們得到的並不是人們使用的算法的真正 VC 維度，因為這些依賴於修剪和交叉驗證。很難說假設空間實際上是什麼，因為原則上，我們從大量可能的樹開始，然後修剪回更合理的東西。例如，即使有人先驗地選擇不超過兩層，也可能仍然需要修剪樹。而且我們並不真正需要 VC 維度，因為交叉驗證直接針對樣本外錯誤。
為了公平對待 Aslan 等人，他們不使用 VC 維度來表徵他們的假設空間。他們計算分支的 VC 維度並使用該數量來確定是否應該切割分支。在每個階段，他們使用所考慮分支的特定配置的 VC 維度。他們沒有從整體上看待問題的 VC 維度。
如果您的變量是連續的並且響應取決於達到閾值，那麼決策樹基本上會創建一堆感知器，因此 VC 維度可能會大於該維度（因為您必須估計截止點才能進行拆分） . 如果響應單調地依賴於連續響應，CART 會將其分解為一系列步驟，嘗試重新創建回歸模型。在那種情況下，我不會使用樹——可能是遊戲或回歸。
