成本复杂性剪枝:修剪错误

Question

有谁能解释一下这两种说法：

在成本复杂性剪枝中，剪枝树的错误永远不能小于训练数据集中的原始树。

在成本复杂性剪枝中，剪枝树错误永远不能少于验证数据集中的原始树。

第一条陈述是对的，第二条是错误的。

Answer 1

对于您选择的任何剪枝策略，这都是正确的，前提是构建原始树是为了最小化训练集中的错误。

True:剪枝树错误永远不能少于训练数据集中的原始树。

原始树是尽可能特定的，通过用叶节点替换子树，您只能得到一个不那么特定的树。因此，训练数据中的误差要么保持不变，要么增加，永不减少。

假:剪枝树错误永远不能少于验证数据集中的原始树。

我们假设验证集是未知的，并且独立于训练数据集。所以，一般情况下，你不能做任何这样的假设。在剪枝时，验证数据集上的错误可能会增加、保持不变或减少。

但是，我们预计错误会减少，因为树将变得不那么特定于培训数据，因此更有可能与不同的数据集兼容。