如何用数学证明：为什么更深的决策树永远不会具有更高的期望交叉熵？
么，它将如何导致过度拟合。
预期的交叉熵通常用作决策树的成本函数。您到处都可以找到期望的交叉熵的定义。让我们从一个简单的例子开始我们的故事。
1.从一个简单的例子
我们大多数人可能已经观察到了案例，其中较深的决策树比较浅的决策树具有更低的交叉熵。例如，袋子里有30个黑球和70个白球，     
图1：没有额外层的根节点
这里的交叉熵与期望的交叉熵相同：
让我们添加更多功能。假设这些球是用玻璃或木头制成的。对于30个黑球，其中20个是玻璃球，其中10个是木制球。对于70个白球，其中41个是玻璃球，其中29个是木制球。我们希望使用此功能来帮助对球的颜色进行分类，并使用此功能（玻璃或木材）为决策树添加一层以上的颜色。
图2：具有更多功能的决策树作为分类的额外层
现在新的期望交叉熵为：
它是：0.6079 <0.6108。再增加一层后，预期的交叉熵低于原始的交叉熵。您可以根据需要更改黑/白数字。但是，我无法提出任何相反的示例，这些示例会在添加更多层之后导致更高的预期交叉熵。
它引起了我的注意。
我的直觉告诉我这是一条规则，背后有一些有趣的事情。
2.让我们形成猜想
猜想：在预期的交叉熵会不会增加决策树加层后。   
2.1猜想的直觉
除了我们的观察，我们还有更直观的信念支持这一推测。
首先让我们看一下交叉熵。
这是什么意思？它不仅是一堆对数计算。熵是从物理学中借用的（暂时忘记了香农的信息论），熵是对无序度或随机度的度量。在我们的案例中，交叉熵的定义类似于物理学中的定义，但是更准确地说，它是对叶节点上的纯净度的一种度量。   
如果叶子节点持有的项目来自单一类型，而不是混合类型，则叶子节点更为纯净。例如，图3.C中的叶节点（充满青色，每个节点仅容纳一项，当然它是纯净的）比图3.A中的根节点纯得多。  
的预期交叉熵，这是因为每个叶节点上交叉熵的加权求和来计算，是一个为纯度超过所有叶节点的度的线性组合的测量上的决策树。对于图3.C，预期的交叉熵为0（0的线性组合为0），低于其他情况（3.A，3.B）。   
图3：仅根节点（3.A），部分展开的树（3.B），完全展开的树（3.C）。完全展开的决策树中的叶节点（图3.C，充满青色的叶节点）比仅根节点的场景（图3.A）更纯净。
看图3，我们的直觉告诉我们以下内容（ECE =预期交叉熵）：
ECE（3.A）> = ECE（3.B）> = ECE（3.C）= 0
这与我们的数学猜想一致，可以写成：
不等式1：
ECE（仅根节点）> = ECE（具有1层的树）> = ECE（具有2层的树）> = ...> = ECE（完全扩展的决策树）= 0。
如果它是真的，那将是美丽的。我们现在可以证明这一点。
3.让我们用数学来证明
我们必须证明哪一部分？
我们正在使用类似数学归纳法的程序，但是有点不同。我知道应采用以下数学归纳法：
证明0到1，通常这部分是最简单的部分
证明n到n + 1，这是困难的部分
我会做的是：
证明ECE（0层）> = ECE（1层），但是，这部分是证明中最有趣的部分
重复应用0到1的结果，并证明n到n + 1。这部分相对容易一些。
3.1。ECE（0层）> = ECE（1层）
首先，让我们简化问题而不失一般性。我们假设袋子中有两种球，蓝色和灰色。如果深入，每个节点将有两个分支（左和右）。
图4。决策树从0到1的图示。
根据图4，不平等将是
右边的这些项目可以用其他顺序书写：
根据这个公式，我们将开始使用Jenson不等式：
Jenson不等式：对于凹函数，f（E（x））> = E（f（x））
图5。借来的
我们可以将詹森不等式写成：
将其与我们要证明的不等式的右侧和左侧进行比较：
我们可以证明左> =右：
证明f（x）=-x * log（x）是凹的 使用二阶导数<= 0，这很容易。
证明以下不平等。
我只会证明第一行，而第二行是相同的：
根据简森不等式（记住l + r = b + g）
ECE（0层）> = ECE（1层）已经完成！
3.2。ECE（n层）> = ECE（n + 1层）
为了证明ECE（n层）> = ECE（n + 1层），在将第n层进一步拆分为n + 1层时，只需在每个叶节点上使用ECE（0层）> = ECE（1层）即可。
图6。在证明“ n至n + 1”时重复应用“ 0至1”。
然后我们完成了证明。我们的直觉没有说谎！的确，与较浅的决策树相比，较深的决策树永远不会具有更高的预期交叉熵。
4.最后一句话。
PS1。简森不等式极为强大！
詹森不平等并不困难。从中学奥林匹克数学竞赛开始，我就一直在使用它。但这是数据科学中的MDW（大规模毁灭性武器）！我们需要在决策树，K-means，EM的理论推测中使用它。这非常有帮助！
PS2。多亏了熵
为什么我们能够在决策树中实现詹森不等式？这是因为：1.交叉熵函数是凹的，2.预期交叉熵是交叉熵的线性组合。这两个因素是决策树“无增量熵”属性的关键。
PS3。我们在决策树中真正想要的是更低的期望交叉熵吗？
可悲的是，答案是否定的。我们想要的分类器是它能够区分不同类型的项目的能力。ECE是我们在决策树中使用的间接索引。较低的预期交叉熵仅意味着叶节点具有较高的纯度。它不能直接揭示决策树识别猫或狗的能力。较低的ECE可能是由于决策树已完全展开并且其每个节点仅包含一项的事实而导致的。当然，它是纯净的，但是它仍然很愚蠢，除了现有的样本之外，它还做出了可怕的猜测。这太合身了。   
图7。较低的预期交叉熵仅意味着叶节点上具有较高的纯度。这可能会导致过度拟合。
从图7中，您可以清楚地看到一个好的分类器（7.B）和一个过度拟合树（7.C）之间的比较，两者在期望交叉熵（= 0）中都最低。为了避免过度拟合，我们需要对树的深度进行限制。我们想要的是一个类似于7.B的分类器，而不是纯粹的但愚蠢的7.C。
题库