Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based method

По запросам трудящихся (@tech_priestess), поковырялся в не очень старой, но и такой уж молодой (февраль 2022) статье от авторов из весьма уважаемого университета UC Berkley: "Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods".

Я бы перевел это как "иерахическое сжатие" (что отражает физический смысл действа, хотя можно было бы сказать, что тут происходит "иерархическое сглаживание"). И сразу скажу, пишу, как понимаю, там еще бы поковыряться в теоремках и статьях, на которые авторы ссылаются, но тогда это дело затянется совсем надолго ;)

Итак, про что статья?

Про любимые в classic ML "деревянные" методы. И улучшение их работы. Авторы решили поработать с регуляризацией деревьев. И предложили свой метод подхода к этому делу.

Частый способ регуляризации - через ограничение maximum depth (максимальной глубины) дерева. Или через pruning (подрезание) дерева. Еще можно выбирать поднаборы признаков (как в random forest), что вносит неявную регуляризацию через рандомизацию.

А можно, например, использовать leaf-based shinkage (LBS, сжатие в листе), который появился как часть XGBoost'а. В этом методе мы "штрафуем" веса листов. Фактически, чем меньше количество значений в листе, тем сильнее мы будем смещаться к выборочному среднему (лучше всего посмотреть на формулу 2 из статьи, тогда все будет понятно, растет число значений в узле - уменьшается регуляризация). Все это клево, но авторы решили посмотреть на проблему под иным углом.

Ну и все эти регуляризации работают в процессе построения деревьев. А вот авторы предлагают post-hoc метод, который вообще смотрит только на структуру дерева, ему даже исходные данные не нужны.

Идея тут интересная.

Давайте будем учитывать структуру нашего дерева. Тогда мы сможем представить предсказание, как сумму выборочного среднего в корне + поправки, которые возникают на каждом вложенном узле.

Если приводить простой пример - давайте предсказывать стоимость квартиры. Тогда в корне у нас будет какая-то средняя стоимость. А дальше мы прибавляем или убавляем цену, в зависимости от показателя (этаж выше 1го - прибавили в цене, есть клевый ремонт - опять прибавили, сосед-алкаш - убавили и т.д.).

То есть estimate = mean_root + mean_step_1 + mean_step_2 + ... (только помним, что это не сами предсказания, а условные "добавки"). Вот авторы и предложили, а давайте для каждого такого значения зададим регуляризацию в зависимости от размера выборки в листе. Тогда при малой выборке мы будем смещать предсказание к значениями родительских узлов.

И тут начинается красота (и теоремы). В общем, наша постановка задачи начинает напоминать регрессию (корень - это общее решение (bias), а потом какие-то признаки с весами). Но у нас же есть методы регуляризации для регрессии, ведь так? Ну вот давайте и применим это знание. А именно, покажем эквивалентность нашего метода ridge регрессии на отобранных деревом признаках (формально там авторы пишут про эквивалентность дерева и kernel (ядерной) регрессии)). Profit!

Но там есть еще небольшая хитрость. Мы не просто берем бинарные фичи (прошел / не прошел дальше). Мы вводим decision stumps (можно перевести как решающие пни) для каждого узла - функции, которые принимают значения, зависящие от количества и баланса данных в левой и правой ветке (см. формулу 3 в статье).

Учитывая, что они будут ортогональны, более сложная матричная задача Ridge-регрессии распадется на независимые скалярные задачи для каждого узла.

И тут стоит заметить, что не обошлось без эвристики. Авторы честно указали, что лямбду брали общую, хотя, по-хорошему, нужны разные (раз у нас все распалось на кучу маленьких подзадач). Но они же и показали, что разница не столь велика, а вот удобство растет гораздо сильнее (не нужно 100500 лямбд иметь сразу).

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

Получается примерно такой алгоритм работы решения.

Мы берем уже обученное дерево решений (или ансамбль деревьев) и далее делаем:

1. Обход дерева. 
   Для каждого узла дерева (от корня до листьев) вычисляется среднее значение целевой переменной на основе обучающих данных, попавших в этот узел.
2. Сжатие/Сглаживание (Shrinkage). 
   Значение в каждом дочернем узле пересчитывается как взвешенная сумма добавок. Начиная от предков до нашего узла, с учетом размера выборки в узлах: чем меньше примеров, тем меньше вес (и тем сильнее значение «сжимается» к родительскому).
3. Результат.
   Новые значения в листьях дерева заменяют исходные. Структура дерева (условия сплитов) при этом не меняется.

И что в итоге, какие плюсы?

1. Мы улучшаем решающую границу (фактически, сглаживаем). Пример ниже, тут классическая картинка, где деревья оставляют странные кусочки зон с другим классом (а вот при сглаживании все выглядит лучше, да и качество повыше).

2. Сглаживание делает SHAP values более "кластеризованными". Опять же, раз мы убираем шум и почти зануляем часть разбиений, мы улучшаем стабильность важности реально полезных признаков.

3. Прикольный результат еще и в том, что и метрики такого регуляризованного дерева улучшаются. У авторов было стабильное улучшение на разных данных (но тут я бы проверял для своих данных сам, мало ли, чего авторы говорят).