⁣Оптимизация распределённого жадного поиска сплитов в GBDT: вычислительное бюджетирование

Узкое место любого GBDT под нагрузкой — жадный поиск порогов для сплитов. Когда фич под тысячу, а строк миллионы, строить гистограмму для каждой на каждом узле — взрывной рост стоимости. В распределённой среде это буквально трата времени на заведомо мусорные сплиты.

Почему это важно
В production ML сценариях с высокой нагрузкой — мониторинг потоковых данных, обучение на Spark, CatBoost в real-time — каждая микросекунда на сплит умножается на число фич и глубину дерева. Типичная ошибка: строить плотные гистограммы для всех фич, даже для разреженных или с низким градиентом, что перегружает сеть и CPU.

Идея вычислительного бюджетирования
Вводим явный бюджет — лимит на количество гистограмм на узел. Фичи ранжируются по эвристике: сумма абсолютных градиентов или плотность ненулевых значений. Для разреженных фич это особенно спасает — они отсекаются до передачи данных между узлами.

Пример псевдокода для распределённой среды:

def allocate_budget(feature_stats, budget=100):
    scores = {feat: len(nonzero_grads[feat]) for feat in feature_stats}
    sorted_feats = sorted(scores, key=scores.get, reverse=True)
    return sorted_feats[:budget]

for tree_level in range(max_depth):
    budget_features = allocate_budget(current_stats)
    parallel_build_histograms(budget_features)

Production-кейс и trade-offs
Из опыта внедрения в streaming-обучении: фаза сплита ускоряется на 40-60% при том же качестве. Сетевого трафика меньше — передаём гистограммы только по отобранным фичам. Однако есть нюанс: если бюджет задан без учёта gain от корня, можно отсечь хорошие сплиты в глубине. Слишком агрессивное бюджетирование (меньше 5% фич) — потеря информативности, особенно на сложных узлах с низкой чистотой.

Практический совет
Используйте адаптивный бюджет под сложность узла: для корневых узлов с большим gain можно увеличить бюджет, для глубоких — уменьшить. Это даёт баланс между скоростью и качеством, особенно в streaming-сценариях с ограничением по latency.

Типичная ошибка
Фиксированный бюджет на все уровни дерева без учёта распределения градиентов. На ранних узлах это может отсечь потенциально сильные фичи, которые станут доминантными глубже. Лучше динамически пересчитывать budget_features на каждой глубине.

Вывод: Вычислительное бюджетирование — простой и эффективный способ снизить latency в GBDT под нагрузкой, но требует адаптивного управления, чтобы не потерять качество из-за преждевременного отсечения фич.