machine-learning - AdaBoost 的 O() 运行时复杂度是多少？

Question

我正在使用来自 scikit-learn 的 AdaBoost，使用典型的 DecisionTree 弱学习器。我想根据数据大小 N 和弱学习者 T 的数量来了解运行时复杂性。我已经搜索了这些信息，包括 Yoav Freund 和 Robert Schapire 的一些原始 Adaboost 论文，但没有看到一个非常明确的答案.

Answer 1

没有不尊重 orgrisel 的意思，但他的答案是缺乏的，因为它完全忽略了特征的数量。

AdaBoost 的时间复杂度为 O(T f)，其中 f 是使用中的弱学习器的运行时间。

对于 C4.5 等普通风格的决策树，时间复杂度为O(ND^2)，其中 D 是特征数。单层决策树将是 O(ND)

您永远不应该像建议的那样使用实验来确定算法的运行时复杂性。首先，您将无法轻松区分类似的复杂性，例如 O(N log(N)) 和 O(N log(N)^2)。它也有被底层实现细节愚弄的风险。例如，当数据大部分已排序或包含一些独特属性时，许多排序可能会表现出 O(N) 行为。如果您输入的唯一值很少，则运行时会显示出比预期的一般情况更快的结果。

Answer 2

它是 O(N . T)。对 T 的线性依赖是确定的，因为用户可以选择树的数量并按顺序训练它们。

我认为在 sklearn 中拟合树的复杂性是 O(N)，其中 N 是训练集中的样本数。max_features当保留其默认值时，特征的数量也具有线性影响。

为了确保您可以编写一个脚本来测量 10%、20%、... 100% 的数据和 n_estimators=10、20、...100 的 adaboost 模型的训练时间，然后使用 matplotlib 绘制结果.

编辑：由于 AdaBoost 通常应用于浅树（通常max_depth在 1 到 7 之间），因此复杂度的依赖关系实际上不是线性 N。我想我测量了对完全开发树的线性依赖过去（例如在随机森林中）。浅树可能具有更接近 O(N . log(N)) 的复杂性，但我不确定。