catboost 算法中对称树背后的直觉是什么？

Question

我一直在研究 catboost 算法，但我很难看出使用对称树的意义。关于这一点，我在他们的github上找到了：

该算法的一个重要部分是它使用对称树并逐层构建它们。对称树是每一层节点使用相同分裂的树。这允许使用索引对叶子的路径进行编码。例如，有一棵深度为2的树。第一层的分裂是f1<2，第二层的分裂是f2<4。那么 f1=5，f2=0 的对象将有编号为 01b 的叶子。

他们说这有助于减少过度拟合并进行更快的推理，但是，直观地对我来说，这就像你需要两倍的深度来探索相同数量的分割。

那么，有人能解释一下使用这种类型的树实际上有什么好处吗？

非常感谢。

Answer 1

由于这是谷歌搜索的第一个结果，我将提供答案。

典型的决策树是一系列 if/else 决策。假设您可以在每个处理器周期做出 1 个这样的决定 - 这会很快，但 100% 是顺序的。要做出决定，你需要做出O(m)决定，其中m是树的最大高度。

在 CatBoost 的对称树中，每次分割都针对相同的属性。要确定向左还是向右，您只需要知道树的当前级别，该级别对应于某个特征及其值。该阈值对于该级别上的所有拆分都是相同的。通过这种方式，您可以对您的决策进行向量化- 创建阈值向量、当前用于预测的值向量并按元素进行比较。如果您有一个矢量处理器，即它可以并行执行多个整数比较（这在当今很常见），您需要 1 个处理器周期来做出决定。

正如您所看到的，差异归结为向量化，能够通过向量逐元素比较的 1 步直接从根到叶，而不是 if/else 决策序列。