Я использую AdaBoost из scikit-learn, используя типичные слабые ученики DecisionTree. Я хотел бы понять сложность выполнения в терминах размера данных N и числа слабых учеников Т. Я искал эту информацию, в том числе в некоторых оригинальных материалах Adaboost от Yoav Freund и Robert Schapire и не видел очень четкого ответа ,Что такое сложность выполнения O() AdaBoost?
Отсутствие неуважения к orgrisel, но его ответа не хватает, поскольку он полностью игнорирует количество функций.
Временная сложность AdaBoost тривиально O (T f), где f - время автономной работы слабого учащегося.
Для дерева решений с нормальным стилем, такого как C4.5, временная сложность O(N D^2), где D - количество функций. Деревом решений на одном уровне будет O (N D)
Вы не должны использовать эксперимент , чтобы определить сложность алгоритма выполнения, как было предложено. Во-первых, вы не сможете легко отличить аналогичные сложности, такие как O (N log (N)) и O (N log (N)^2). Это также может быть обмануто базовыми данными о реализации. Например, многие виды могут демонстрировать поведение O (N), когда данные в основном сортируются или содержат несколько уникальных атрибутов. Если вы предоставили ввод с несколькими уникальными значениями, время выполнения будет иметь более быстрый результат, чем ожидаемый общий случай.
Это O (N. T). Линейная зависимость от T определенна, поскольку пользователь может выбрать количество деревьев, и они будут обучаться последовательно.
Я думаю, что сложность подбора деревьев в sklearn - это O (N), где N - количество выборок в обучающем наборе. Количество функций также имеет линейное воздействие, когда max_features остается на свое значение по умолчанию.
Чтобы убедиться, что вы можете написать сценарий, который измеряет время обучения моделей adaboost на 10%, 20%, ... 100% ваших данных и для n_estimators = 10, 20, ... 100, затем график результаты с matplotlib.
Редактировать: в AdaBoost, как правило, применяется для мелких деревьев (с max_depth между 1 и 7 в целом), это может быть так, что зависимость от сложности на самом деле не является линейным Н. Я думаю, что измеряется линейный зависимость от полностью развитых деревьев в прошлом (например, как в случайных лесах). Неглубокие деревья могут иметь сложность ближе к O (N. Log (N)), но я не уверен.
И где анализируется ** итеративный ** процесс, содержащий сложность AdaBoost, содержащуюся здесь? – lejlot
AdaBoost обучает одно дерево за другим, последовательно по полному набору данных (с весом образца, обновленным по результатам предыдущих шагов). Поскольку весы не оказывают большого влияния на время обучения деревьев, которое не должно влиять на линейную зависимость сложности от T. – ogrisel
Вы правы, я пропустил определение T. – lejlot
. Также реальная сложность обучения культу решения зависит от сплиттер, но я считаю, что это O (DN log N) для единого дерева с фиксированной глубиной и оптимального разделения. При каждом расщеплении кандидатов все образцы должны быть отсортированы по значению некоторой функции. Сортировка доминирует асимптотически. –
Вы не можете сказать, что сортировка доминирует над временной сложностью, потому что она использует другую переменную. Сортировка - это только одна часть. Сложность os O (D N), если вы используете сортировку radix для числовых функций или используете категориальные функции. Я использовал общие термины, так как существует множество различных типов возможных методов индукции дерева решений. Есть и другие способы получить O (D N) время без использования сортировки –
Это все правда, и я не должен был предполагать N >> D, потому что в некоторых проблемах это неверно.Но вопрос о scikit-learn, который использует классический вид сравнения в обучении дерева решений. –