#dl #books

#llm #code

#dl #llm #courses

#ml #interview

Готовимся к собесу, шпаргалка по деревьям

Общее понимание градиентного бустинга

Изначальный алгоритм Фридмана (Friedman, 2001) задаёт базовый принцип.
Идея: мы берём функцию потерь (loss), которую нужно минимизировать ансамблем слабых моделей (обычно деревья решений).

Начинаем с базовой константы (например, среднее значение таргета).

На каждом шаге строим новое дерево по текущим градиентам функции потерь (первая производная по предсказанию).

Значения в листьях подбираются так, чтобы минимизировать loss в этой области (иногда используют и вторую производную для точности).

Каждое дерево добавляется в модель с коэффициентом обучения (learning rate), чтобы не переобучиться.

Фридман показал, что этот подход работает и для регрессии (MSE), и для классификации (логлосс/NLL).

Chen & Guestrin, 2016 — это про XGBoost.

В XGBoost формализовали общее выражение для прироста качества (gain) узла с учётом первых и вторых производных.

Значение листа считается по формуле:

w_j = - (sum(g_i)) / (sum(h_i) + lambda)

где
g_i — первый градиент,
h_i — второй градиент (Гессиан),
lambda — коэффициент регуляризации.

Прирост качества (gain) при разбиении узла:

gain = 0.5 * ( ( (sum(g_left))^2 / (sum(h_left) + lambda) )
             + ( (sum(g_right))^2 / (sum(h_right) + lambda) )
             - ( (sum(g_total))^2 / (sum(h_total) + lambda) ) ) - gamma

где
g_left, h_left — суммы градиентов и Гессианов для левого узла,
g_right, h_right — суммы для правого узла,
g_total, h_total — суммы для всего узла до разбиения,
gamma — минимальный прирост, чтобы оставить разбиение (если меньше, то узел схлопывается, читай прунинг).

Prokhorenkova et al., 2018 — про CatBoost.
Там основное — как бороться с переобучением и эффективно работать с категориальными признаками.

Категориальные фичи: кодирование делается через "средние по таргету", но с порядковым шифтом (ordered target encoding). То есть значение для объекта считается только по предыдущим объектам в случайной перестановке. Это сильно уменьшает target leakage.

Симметричные деревья: все разбиения на одном уровне одинаковые (level-wise). Это ускоряет инференс (можно SIMD/CPU оптимизации).

Очень много готовых функций потерь (MSE, логлосс, ранжирование, custom).

Для ранжирования — используют попарные лоссы (например, YetiRank, Pairwise). Данные группируются по запросам, и дерево строится так, чтобы правильно упорядочивать документы внутри группы.

Вопросы на собесе

1. Можно ли параллелить инференс?
Да. Каждое дерево считается независимо, потом результаты суммируются. Сумма — операция коммутативная, значит, можно распараллелить по деревьям.

2. Можно ли исключить дерево из ансамбля?
Формально да — это просто сумма функций. Но в отличие от бэггинга, деревья в бустинге строятся последовательно: каждое корректирует ошибки предыдущих. Если убрать дерево, качество почти всегда ухудшится.

3. В чём отличие от бэггинга/Random Forest?

В бустинге деревья строятся последовательно и учитывают ошибки прошлых шагов.

В RF деревья строятся независимо, а результат усредняется.

RF больше про снижение дисперсии, boosting — про уменьшение смещения.

4. Почему используют вторые производные (Hessian)?
Потому что это даёт более точную аппроксимацию loss при подборе весов листьев (аналог Ньютона вместо градиентного спуска).

#ml #interview