为什么删去符合训练数据的规则?
决策树可以不断分裂,直至一个叶节点只描述一两条观测。这样的规则可能捕捉真实规律,也可能只是记住偶然的标签。前一节说明如何构建决策树并把它编译成规则,当时刻意把剪枝留作另一个选择。这里研究一个具体方法,判断哪些分支可以移除。
定义 28.1.1
(存储的训练标签与三份数据)
构建树之前,先留出有标签的验证数据。只用训练数据建立决策树,并让每条训练数据经过树,在每个节点记录到达该处的训练标签的多数类别。二元标签若同数,约定取 。若某节点没有训练数据,则使用预先说明、只依赖训练数据的备用标签,例如父节点的记录标签。这些标签在剪枝时保持固定,不以验证标签重新计算。另留一份完全未参与选择的测试集作最后评估;分组或时间顺序等数据来源特性也要反映在划分方式中。
算法与它真正保证的事
定义 28.1.2
(后序减错剪枝)
令 为当前的有限树, 为验证集。按固定后序处理内部节点:先后代、后父节点,子节点的顺序也固定。对节点 ,考虑把它目前的整棵子树换成一片叶,叶节点的标签采用 记录的训练多数类别。只有当替换不会增加 上的错误数时才接受;相等也接受,以选较小的树。否则保留当前子树。稍后处理祖先时,必须使用已修改的后代。根节点最后处理;一旦剪掉某祖先,其后代全部消失。这是单次扫描及一个明确的平局规则,其他剪枝变体未必采用同一规则。
定义 28.1.3
(局部错误计数)
令 为目前沿树到达 的验证数据, 为当前子树在这些数据上的错误数, 为候选叶节点的错误数。采用错误数而非比例,可清楚处理空集:若没有验证数据到达 ,两个数均为零,因此平局规则会剪去该子树。这只是简化缺乏验证证据的分支,并不证明替换后在该处预测准确。
定理 28.1.4
(每次接受替换所保证的事)
对固定的有限验证集及确定的路径规则,上述算法会终止;最终验证错误数不超过原树。每次接受替换均减少节点数。在所有可通过把原树的子树换成带有相应记录标签的叶节点而得到的树中,所得树的验证错误最少;在错误最少的树之中,它的节点数也最少。这不保证总体准确率提高。
证明
(局部改变等于两个计数之差)
在 替换子树,只会改变到达 的数据之预测,其他数据的错误数不变。因此总错误数的改变恰为 。算法只接受非正的变化。每次接受替换均移除节点;固定后序只涉及有限个节点,所以算法终止,而连续接受的操作均不增加验证错误。更强的最优性可由叶节点向上归纳。节点处任何允许的剪枝,要么把整棵子树换成记录标签的叶,要么保留节点并分别剪枝各子树。每条验证数据只进入一个子节点,故保留节点时,各子树的错误数可以相加。依归纳假设,已处理的每棵子树错误最少,且在错误数相同且最少时节点数也最少。再把保留节点的结果与候选叶节点比较,就得到该节点处错误最少的树;平局时选叶则确保节点最少。对根应用此结论即可。这只是关于用来选树的 的结论,并非关于未来数据的概率保证。
证明透视
局部比较为何等于全局改变
只有到达所选节点的数据可能改变预测;其他错误项相消。因此比较两个局部错误数,就能准确得到整个验证目标的变化。即使后代已先被剪枝,此论证仍然成立。
逐步例子:改善、平局及拒绝
例题 28.1.5
(改善、平手与拒绝)
根节点测试 。当 时,节点 测试 : 预测 , 预测 。当 时,节点 测试 : 预测 , 预测 。已记录的训练多数标签分别为 的 、 的 、根的 。例如 的训练标签 数目为 , 的为 ,就得到这三个多数标签。下表每个列表是沿该路径到达的验证标签;路径由特征值决定。
| 路径 | 验证标签 | 原预测 | 原错误数 |
|---|---|---|---|
原树在 条数据上共有 个错误。先访问 :当前子树错 次;改成叶节点 ,只错两个标签 ,共 次。接受替换,总错误降至 。再看 :当前子树错 次;叶 也错两次,即两个标签 。依平局规则替换 ,总错误仍为 。最后,根的当前子树错 次;若根改成叶节点 ,左边两个和右边三个标签 都会被判错,共 次。因此拒绝根的替换。最终树只测试 ,左边预测 、右边预测 ;验证错误率为 。
概念视角算法
剪枝是自底向上取最小值
令 为在 处子树的所有剪枝方式中,到达 的验证样本所能达到的最少错误数。则 ,其中 取遍 的子节点,而叶节点的 就是它自己的错误数。在上面的追踪中,,,,正是前面得到的最终错误数。
例题 28.1.6
(比较祖先与已修改的后代)
设根有左、右两棵子树,各有六个验证样本到达。目前左子树有 个错误,右子树有 个。换成存储标签的叶后,错误分别为 与 ,而根叶则有 个错误。依后序:左子树因 而被替换,右子树因 而保留。此时根处的现有子树有 个错误,所以有 个错误的根叶被拒绝,最后错误是 。若改用过时的原始总数 与根叶比较,便会平手而剪去根,结果错误为 ,比正确的 差。
例题 28.1.7
(平手规则改变的是树,不是验证错误)
回到上面的追踪,假设平手改为相反处理:只有严格降低验证错误才接受替换。节点 仍被替换,因为 。在 ,叶与子树都有 个错误,所以 现在被保留。根叶仍有 个错误,被拒绝。最后的树总错误是 ,与所述规则相同,但它保留了对 的测试,多出两个节点(保留的 及其两片叶,取代单一片叶)。因此接受平手的约定,是在验证错误最小的树之中选出最小的一棵。
常见错误
(从验证样本选择替换叶的标签)
替换叶必须带有存储的训练多数标签。若改由 处的验证标签决定, 就是任何单一标签在这些样本上所能达到的最小计数,比较便偏向剪枝,并且重复使用了验证标签。上面的追踪中,右边的验证数据刚好有三个 、两个 ,这个巧合不表示可以从验证标签选叶节点的标签。即使训练树不变,换另一份验证集也可能得到不同的剪枝决定。
数据泄漏与选择过拟合
反例模式
选出的完美分数不代表未来准确
假设 是每条数据独一无二的标识符, 是与 无关的公平掷硬币结果。足够灵活的树可以记住构建树所用数据的标签,令训练错误为零;但对新的独立硬币结果,其预测正确的概率只有 。若把同一批有标签数据称作验证集,剪枝决定及其分数就重用了训练信息。零训练错误不代表对新数据的预测比猜测更好。
即使验证集确实独立,它在这里仍被反复使用:每次剪枝都取决于其标签。若又在同一份数据上尝试许多树、平局规则或超参数,整个选择过程可能迎合验证数据中的噪声。因此验证错误不是独立的最终表现估计。先固定所有选择,才用未接触、具有代表性的测试数据评估一次;单一小型测试集仍有抽样不确定性。若选择后重新训练,应预先规定重新训练的流程,并以未用于选择或拟合的数据评估重新训练后的模型。
常见错误
(把选定的验证错误当作表现)
追踪中剪枝后的树,验证错误是 。这个数字是在推动每个剪枝决定的同一批标签上比较计数而得,所以并非对将来错误的独立估计。必须在所有选择冻结之后,只用一次全新的测试集。
练习
快速检查
(在节点 ,现有子树在到达它的 个验证样本上犯 个错误;训练多数标签的叶在那里犯 个错误。整棵树目前共有 个验证错误。会发生什么?新的总数是多少?)
解答 · 答案
接受替换:。 之外的错误数不变,所以新总数是 。
快速检查
(某节点没有验证样本。依上述算法,它会被剪去吗?这是否表示其替代叶的总体错误率为零?)
解答 · 答案
会:两个局部错误计数都是零,而平手被接受。空的验证子集对将来错误没有提供任何证据;零个观测之中零个错误,并不构成准确度保证。
练习 28.1.8
(某树的根有左、右两棵子树。现有验证错误分别为 与 。训练多数标签的叶会分别犯 与 个错误;根处的训练多数标签叶共犯 个错误。按后序并在平手时剪枝,做出各个决定,并写出最后错误。为何根的比较必须使用已修改的子树?)
核心
解答(3)
- 1
决定左子树
现有错误是 ,叶的错误也是 。依平手规则,左子树被替换。
- 2
决定右子树
现有错误是 ,叶的错误是 ,而 ,所以右子树被替换。
- 3
以已修改的子树决定根
此时整棵树有 个错误,根叶也是 个,依平手规则替换根;最后错误是 。根的比较必须使用已修改的子树,因为候选叶要与手上实际存在的树比较。若用原本的子树错误,就是拿过时的 与 比较;这里碰巧也接受根,但那并不是这个算法。
快速检查
(有人用全部已标注的例子生长一棵树,再把同一批例子随机分成所谓的训练和验证子集,然后剪枝。指出泄漏所在,并提出有效的三份切分流程。)
解答 · 答案
树的分裂与叶标签,已经用了后来被称为验证标签的标签;验证集并不独立于树的生长。应先切分观测,在训练数据上生长并标注树,用验证数据剪枝和选择,然后冻结整个流程,再用另外保留的测试集评估。切分还须尊重有关的分组或时间顺序。