决策树的结构风险理解

作者：陶轻松
链接：https://www.zhihu.com/question/34075616/answer/131957868
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

咱们可以这样去看到问题，首先咱们将公司与通用的损失函数对比去分析：

我在问题机器学习中常常提到的正则化到底是什么意思？ - 陶轻松的回答 - 知乎中回答过r(d)是什么的问题，我在文章中提到r(d)最简单的方式就是表达成：,即代表损失函数中特征项的数目，如果理解就pass，不能理解可以看看我的这篇文章，相信可以很快知道两个损失函数的对应关系，即r(d) = 与 具有完全等价的作用，都是为了约束模型复杂使用的，至于作用，很简单：防止【过拟合】；：

即每个样本的，哪怕是由于噪声产生一点小的偏差都被学习算法学习到了，显然他的容错性、以及在正式使用的环境中误差会很大，因为它“刻意”的匹配了学习了的很多无效的特征(弯曲程度高，曲线的多项式就越复杂，还有的参数项就越多-----基本数学认知，不解释)。

好了，既然咱们了解透了对应关系之后，咱们来对照一下，看看他们之间的关联性；先谈谈他们损失函数的意义，为了便于理解，我们先去解释通用的损失函数的意义:

即先看, 这个函数很好理解，即真实的分类与机器估计的分类之间的均方差，他要表达什么意思呢？很简答，它是要在不考虑任何的“过拟合”的情况下，只要求测试样本的契合程度达到最高，即使得测试样本尽量的跟学习算法得出的分类一直，最好是100%的一致。优化的目标是：【是的该函数值越小越好】。

如果能够理解上面划线的这段话，咱们用自然的思维去考虑损失函数的定义问题。思考一下，如果是你，在建立了决策树之后，你觉得应该如何去定义决策树的损失函数？抛开书本上的那些死记硬背的东西。好了，咱们给出几个思维导图：
显而易见，咱们应该让每一个节点都尽量有自己明确的分类吧？即让自己能够被明确的决策出来吧？而且应该保证与其他样本有所区分 (脑袋里面想象上面【过拟合】的第三幅图，如果不考虑“过拟合”，他就是单独 函数优化的目标)
显而易见，为了跟通用损失函数的效果一致，即跟通用损失函数的定义一致，咱们应该让【测试样本与函数的效果】达到跟【测试样本与】完全一致的效果吧？
显而易见，衡量“决策树完全一致”的说明的是【确定性】吧？即确定性越强的损失函数最优值，说明学习方法效果越好。即损失函数要满足：熵值越小函数结果越好。
显而易见，对于“决策树而言”，分类确定性越强的，损失就越小吧。

ok，了解了这些问题之后咱们再来确定这个问题，为了思维不至于直接跨度到下面这个表达式：

咱们先求一种极端的情况，请问在基于上文中的四个“显而易见”的内容之后，咱们如何保证与“通用损失函数”相互对应的“决策的损失函数”达到最小？
注意我问的是情景，不是让你写出函数，先思考如何达到最小再说。很简单吧：
我来回答一下：既然要保证损失最小，根据决策树的定义而言，就只要让测试样本的拟合程度最高就行了吧，想想一下上面三张图，在不考虑过拟合的情况下，只考虑损失函数的情况下，第三幅图效果最佳吧！同理，有了这个前提，咱们不考虑决策树的过拟合的情况下，只要保证决策树的分类的熵的值越小越好！好的，回答上面提到的极端情况的问题，既然极端，咱们只要保证每个节点单独成为一个叶节点就行了吧？这样的分类就像上面的第三幅图一样，只要圈进去就行了，不需要考虑任何过拟合，也就是说曲线再复杂也没关系。为什么不需要考虑过拟合？因为这不是你经验损失函数()的职责，这是正则化( )的职责，即这是正则项的功效。为什么叶节点上只有一个样本点的效果最好，因为熵的定义是p*log(p) 。 1*log1=0，0当然是最小的啦，熵的最小值，所以确定性最高。

好了，咱们确定了极端情况，但是毕竟不能完全按照极端的情况去处理，毕竟如果每个叶节点一个样本，咱们的分类也没那么多啊，是吧？这如何是好？机器学习的思路，或者说统计学的思路咱们就可以借鉴了，既然咱们不能保证每个最小，那咱们就求他们和的极限，因为决策树的熵都是大于0的，所以熵的和最小，就可以保证每个个体都是相对最小的，就可以保证整体最优。所以咱们将决策树的经验损失函数定义为，所有叶节点熵之和：

但是这样容易出现过拟合啊，因为每次只要保证叶节点数量越多越好就行了，如果分类跟样本差不多的时候，基本是100%过拟合的，每个样本一个叶节点，熵最小。所以，为了防止这种情况的发生，咱们需要考虑【正则化】，正则化的过程在我的那篇文章中提到过了，我就不提了。

将r(d)定义为： ，所以它的结构化风险定义为：

因为它是针对决策树的，我们管这个叫做：决策树损失函数。因为对于决策树而言，单独去考虑经验损失函数是没有任何意义的，很多情况基本100%过拟合，so，书本、机器学习的资料上面就没有单独去讨论这个，而是直接给出了【决策树的结构化风险】定义，即直接给出了【正则化】后的函数，而且给了它一个定向的名字，叫做“决策树损失函数”。

说了这么多，我感觉应该表达的还是挺通俗化的，望楼主采纳；有任何问题可以在评论中给出，我看见就回答。

PS，顺便提一句，所有的学习算法的【正则化】即【经验损失结构化】的形式都是固定的：经验损失+范数 结构，经验损失是为了是学习算法匹配测试样本，范数是为了过拟合。
讲到这里，特地的给大家强调一下，生成模型和判别模型的区别。很多人都仅仅是知道有这么两个模型，以及定义上有差别，其实在他们的经验风险最小化的方式也是有区别的：
判别模型有正规化过程，比较 与,因为直接是生成f(x)或者p(y|x),所以很容易比较 y 和 f(x)的关系，也容易过拟合。过拟合产生的方式很简单，主要就是由于缺乏过程，只能依靠f(x)/p(y|x)机械式的产生数据，知其结果不知其所以然。所以需要时时刻刻的防止他过拟合，都是依葫芦画瓢去判别的，所以才有r(d) 这个正则化项存在的意义。

相反，
生成模型一半都是直接给出生成数据的过程，知其结果也知其所以然，例如求联合概率分布P(x,y),再比如说kd近邻发、决策树，我们是实实在在的知道每个数据字段的含义、同时结构也有明显的意义。所以他的过拟合情况相对来说会很少，故：
1、k近邻法考虑的是经验风险（等价于误分类率），没有考虑正则化。
2、朴树贝叶斯法也是只考虑期望风险（等价于后验概率最大化），没有考虑正则化。
“没有考虑正则化很简单，因为他们很少【过拟合】”。一定要记住这句话，不要为了正则化而正则化，只有在【过拟合】的时候才需要。

当然事无绝对，决策树算是生成模型的一种特例，说实话，熵也是一个很虚的概念，他代表的不确定性更多的是由于特殊字段出现在列别当中的比率导致的，带有比较大的偶然性。所以有点类似判别模型，故给了个正则化项。

机器学习是一门思考的科学，万变不离其中，多考虑基础，多思考思路，总思维、轻记忆。千万不能死记硬背，碰到迷茫的问题的时候，站在解决问题的角度去思考一个方案，你往往就能够明白这些书本中觉得“理所当然的公式”的意义了。