将决策树转换为矩阵运算（matrix operations）

Transform Decision Tree into Matrix Operations

使用决策树进行推理是一个迭代过程。我们通过逐层评估某个节点上的条件来遍历决策树，直到到达一个叶节点（leaf node）。在本章中，让我们学习一项绝佳的技术，把决策树的推理表示为矩阵运算的形式。

结果是：1. 它使推理快得多，因为矩阵运算可以被高度并行化。2. 这些运算可以加载到 GPU 上以获得更快的推理，使其更便于部署。

考虑一个包含 5 个特征（feature）的二分类数据集。

假设我们在上述数据集上拟合决策树后得到如下的树结构：

在继续之前，我们假设：

• N → 数据集中的总特征数（上例数据集中为 5）。
• E → 树中的总评估节点数（上例树中有 4 个蓝色节点）。
• L → 树中的总叶节点数（树中有 5 个绿色节点）。
• C → 数据集中的总类别数（上例数据集中为 2）。

这种转换的核心思想是推导出五个矩阵（A、B、C、D、E），用以捕获决策树的结构。

让我们逐一了解它们！矩阵 A：这个矩阵将每个评估节点与其所评估的输入特征关联起来，从而表明在每个评估节点上究竟使用了哪个输入特征。

这个矩阵捕获输入特征与评估节点（上面的蓝色节点）之间的关系。所以它是一个 (N×E) 形状的矩阵。

如果列中对应的节点评估了行中对应的特征，则相应条目设为“1”。例如，在我们的决策树中，“节点 0”评估“特征 2”。

因此，对应的条目将为“1”，而其他所有条目都为“0”。

按这种方式填满整个矩阵，我们得到：

矩阵 B 的条目是每个节点的阈值。因此，它的形状为 1×E。

不过它其实是一个向量，但术语在这里并不重要。

这是一个表示每对叶节点与评估节点之间关系的矩阵。因此，它的维度是 L×E。

某个具体条目会被设为：

• “1”：如果列中对应的叶节点位于行中对应评估节点的左子树中。
• “-1”：如果列中对应的叶节点位于行中对应评估节点的右子树中。
• “0”：如果对应的叶节点和评估节点之间没有联系。

例如，在我们的决策树中，“叶节点 4”同时位于“评估节点 0”和“评估节点 1”的左子树中。因此，对应的值都为 1。

按这种方式填满整个矩阵，我们得到：

向量 D 的条目是矩阵 C 每一列中非负条目之和：

最后，这个矩阵保存叶节点与其对应输出标签之间的映射。因此，它的维度是 L×C。

如果一个叶节点把样本分类为“类别 1”，则对应条目为 1，而另一个单元格条目为 0。例如，“叶节点 4”输出“类别 1”，因此第一行对应的条目为 (1, 0)：

我们对所有其他叶节点重复这一过程，得到如下的矩阵作为矩阵 E：

至此，我们已把决策树编译成了矩阵。回顾一下，我们到目前为止创建的五个矩阵是：

• 矩阵 A 捕获每个评估节点上使用了哪个输入特征。
• 矩阵 B 存储每个评估节点的阈值。
• 矩阵 C 捕获某个叶节点是位于某个评估节点的左子树还是右子树，或者与它没有关系。
• 矩阵 D 存储矩阵 C 每一列中非负条目之和。
• 最后，矩阵 E 从叶节点映射到它们的类别标签。

假设这是我们的输入特征向量 X（5 维）：

现在，整个推理只需用这些矩阵运算即可完成：

• XA < B 得到：

• 上述结果乘以 C 得到：
• 上述结果与 D 匹配后得到：
• 最后，乘以 E，我们得到：
• 最终预测结果为“类别 1”，确实正确！注意，我们仅用矩阵运算就完成了整个推理过程：

因此，推理运算可以大幅受益于并行化和 GPU 能力。下图清楚地展示了这项技术在运行时间上的效果：

• 这里，我们训练了一个随机森林模型。
• 编译后的模型运行情况：
  • 在 CPU 上快两倍多（Tensor CPU 模型）。
  • 在 GPU 上快约 40 倍，提升巨大（Tensor GPU 模型）。
• 所有模型准确率相同——表明编译过程中没有信息损失。