ТРОИЧНОЕ ВЕТВЛЕНИЕ В ГРАДИЕНТНОМ БУСТИНГЕ ДЛЯ ЗАДАЧ С КАТЕГОРИАЛЬНЫМИ ПРИЗНАКАМИ

Аннотация. В работе предложена и обоснована модификация градиентного бустинга над решающими деревьями (GBDT), в которой бинарное расщепление в узлах дерева заменяется троичным. Сформулировано определение корректности модификации; доказаны: лемма о существовании и единственности оптимальных значений в листьях при квадратичной аппроксимации (воспроизведение и обобщение результата [2]); теорема о выводе формул прироста качества Δ₂, Δ₃; теорема о доминировании, утверждающая, что любое бинарное расщепление воспроизводимо троичным (с точностью до штрафа γ); достаточное условие строгого превосходства троичного расщепления над оптимальным бинарным; лемма о разложении прироста через взвешенную дисперсию листовых статистик. Получена оценка вычислительной сложности алгоритма O(B²) и схема его встраивания в симметричные деревья. Численный эксперимент на трёх открытых наборах данных подтверждает теоретические выводы.

Ключевые слова: градиентный бустинг, решающие деревья, троичное ветвление, категориальные признаки, target statistics, симметричные деревья, регуляризованный риск.

1. Введение

Градиентный бустинг над решающими деревьями [1, 7] – стандартный инструмент анализа структурированных данных. Концептуальную основу метода заложили классические алгоритмы построения отдельного дерева: CART [6] использует исключительно бинарные расщепления, тогда как C4.5 [8] допускает многоветвевое расщепление по категориальным признакам – ближайший предшественник рассматриваемой ниже модификации. Современные открытые реализации (XGBoost [2], LightGBM [3], CatBoost [4]) различаются методами поиска расщеплений и схемами обработки категориальных признаков; среди отечественных работ по программной реализации, оптимизации и прикладному использованию градиентного бустинга деревьев решений отметим [9–12]. Кодирование категориальных признаков посредством среднего значения целевой переменной [5] требует мер против утечки целевой переменной; в [4] предложено упорядоченное оценивание Target Statistics. Распределение значений признака после такого кодирования имеет, как правило, многомодальную структуру: основная масса значений приходится на распространённые категории, а редкие категории и пропуски формируют отдельные группы. В этих условиях бинарное расщепление узла нередко субоптимально: одна пороговая граница не способна одновременно отделить редкие значения от массовых и от пропусков.

2. Постановка задачи и обозначения

Пусть задана обучающая выборка D = {(x_i, y_i)}_i=1ⁿ, x_i ∈ ℝ^d, y_i ∈ ℝ. Категориальные координаты вектора x_i предварительно подвергаются упорядоченному TS-кодированию [4]. Функция потерь ℓ: ℝ × ℝ → ℝ предполагается дважды непрерывно дифференцируемой и выпуклой по второму аргументу (стандартное предположение для XGBoost-семейства [2]). Регуляризованный эмпирический риск:

L(F) = ∑_i=1..n ℓ(y_i, F(x_i)) + ∑_t=1..T Ω(f_t),                                                               (1)

где F = ∑_t=1..T ν f_t, ν ∈ (0, 1]. На шаге t ансамбль F_t-1 фиксирован; задача сводится к выбору дерева f_t ∈ ℱ. Применение разложения Тейлора второго порядка функции потерь в окрестности F_t-1(x_i) даёт ньютоновскую аппроксимацию [2]:

L̃^(t)(f) = ∑_i=1..n [g_if(x_i) + ½ h_if²(x_i)] + Ω(f),                                                            (2)

где g_i = ∂_F ℓ(y_i, F_t-1(x_i)), h_i = ∂²_F ℓ(y_i, F_t-1(x_i)) ≥ 0; здесь производные берутся по второму аргументу функции потерь, то есть по значению прогноза ŷ = F_{t-1}(x_i): g_i = ∂ℓ(y_i, ŷ)/∂ŷ|_{ŷ=F_{t-1}(x_i)}, h_i = ∂²ℓ(y_i, ŷ)/∂ŷ²|_{ŷ=F_{t-1}(x_i)} (неотрицательность h_i следует из выпуклости ℓ по второму аргументу). Дерево f задаётся структурой – разбиением {I_j}_j=1..J множества {1, ..., n} на J непересекающихся непустых классов (листьев) – и значениями w = (w₁, ..., w_J) ∈ ℝ^J; f(x_i) = w_j(i), где j(i) – индекс листа, содержащего i. Регуляризатор:

Ω(f) = γ J + ½ λ ‖w‖²,    γ ≥ 0,  λ > 0.                                                                (3)

Для произвольного S ⊆ {1, ..., n} обозначим G_S = ∑_i∈S g_i, H_S = ∑_i∈S h_i ≥ 0. Условие λ > 0 гарантирует строгую выпуклость функционала по w.

3. Формальное определение троичного ветвления

Определение 1 (бинарное расщепление). Пусть φ: ℝ^d → ℝ – функция признака (числового либо TS-кодированного категориального). Бинарным расщеплением узла I по предикату φ с порогом θ ∈ ℝ называется упорядоченная пара (I_L(θ), I_R(θ)), где I_L(θ) = {i ∈ I: φ(x_i) ≤ θ}, I_R(θ) = I \ I_L(θ).

Определение 2 (троичное расщепление). Пусть θ₁ < θ₂. Троичным расщеплением узла I по предикату φ с парой порогов (θ₁, θ₂) называется упорядоченная тройка непустых множеств:

I_L = {i ∈ I: φ(x_i) ≤ θ₁},  I_M = {i ∈ I: θ₁ < φ(x_i) ≤ θ₂},  I_R = {i ∈ I: φ(x_i) > θ₂}.     (4)

В случае категориального признака с выделенным значением «пропуск» (NaN) либо редкой категорией одна из ветвей задаётся индикатором принадлежности к выделенному множеству значений; все последующие утверждения сохраняются дословно при замене (4) на любое разбиение I на три непустых класса. Множество всех допустимых троичных расщеплений по признаку φ обозначим Π₃(I, φ); множество бинарных – Π₂(I, φ).

Определение 3 (корректность модификации). Модификация алгоритма построения дерева называется корректной, если выполнены следующие условия:

(К1) задача поиска оптимальных значений в листьях при фиксированной структуре имеет единственное решение в замкнутой форме;

(К2) функционал прироста качества при расщеплении выводится из (1)–(3) однозначно и совпадает с (1) на множестве деревьев построенной структуры;

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

Цель раздела 4 – доказать корректность предлагаемой троичной модификации в смысле определения 3 и установить количественные характеристики прироста качества.

4. Корректность модификации: основные результаты

Лемма 1 (существование и единственность оптимальных значений в листьях). Пусть {I_j}_j=1..J – фиксированное разбиение, λ > 0. Тогда функция L̃^(t)(w) = ∑_j[G_jw_j + ½(H_j + λ)w_j²] + γJ строго выпукла и достигает единственного глобального минимума в точке

w_j* = – G_j / (H_j + λ),    j = 1, ..., J,                       (5)

причём минимальное значение функционала равно

L̃*({I_j}) = – ½ ∑_j=1..J G_j² / (H_j + λ) + γJ.                   (6)

Доказательство. Гессиан функции L̃^(t) по w есть диагональная матрица diag(H₁ + λ, ..., H_J + λ). Поскольку h_i ≥ 0 и λ > 0, имеем H_j + λ > 0 для всех j, следовательно гессиан положительно определён, а функционал – строго выпукл. Условие первого порядка ∂L̃^(t)/∂w_j = G_j + (H_j + λ)w_j = 0 даёт (5). Подставляя (5) в выражение, получаем для каждого слагаемого:

G_jw_j* + ½(H_j + λ)(w_j*)² = – G_j²/(H_j + λ) + ½ G_j²/(H_j + λ) = – ½ G_j²/(H_j + λ),

откуда (6). Единственность следует из строгой выпуклости. Формулы (5) и (6) впервые получены в [2, разд. 2.2]; приведённое доказательство воспроизводит аргумент [2] для полноты изложения.

Лемма 1 доказывает условие (К1) определения 3 для произвольной – в том числе троичной – структуры дерева, поскольку оптимизация по w разделяется по листьям независимо от того, является ли внутреннее ветвление бинарным или троичным. Этот факт критичен: он показывает, что модификация не нарушает основное соотношение (5).

Теорема 1 (вывод формул прироста качества). Снижение функционала L̃^(t) при бинарном расщеплении узла I на (I_L, I_R) и при троичном расщеплении на (I_L, I_M, I_R) равно соответственно:

Δ₂(I_L, I_R) = ½ [G_L²/(H_L + λ) + G_R²/(H_R + λ) – G²/(H + λ)] – γ,                           (7)

Δ₃(I_L, I_M, I_R) = ½ [G_L²/(H_L + λ) + G_M²/(H_M + λ) + G_R²/(H_R + λ) – G²/(H + λ)] – 2γ,        (8)

где G = G_I = G_L + G_M + G_R (для бинарного – G = G_L + G_R), аналогично для H.

Доказательство. Применим лемму 1 до и после расщепления. До расщепления вклад листа I в (6) есть –½ G²/(H + λ) + γ. После бинарного расщепления вклад заменяется на –½ [G_L²/(H_L + λ) + G_R²/(H_R + λ)] + 2γ, поскольку число листьев увеличилось на 1. Прирост качества – снижение функционала, то есть разность с противоположным знаком – даёт (7). Для троичного расщепления число листьев увеличивается на 2, что даёт штраф 2γ; вычисление аналогично и приводит к (8). Вывод формулы (7) воспроизводит схему [2, теорема 1]; формула (8) является оригинальным обобщением на троичный случай.

Теорема 1 доказывает условие (К2) определения 3: формулы (7), (8) однозначно выводятся из (1)–(3) и совпадают (с точностью до знака) с приращением функционала (1) на соответствующих структурах деревьев.

Лемма 2 (неравенство Энгеля для дробей; классический результат, являющийся формой неравенства Коши–Буняковского). Для произвольных a₁, ..., a_m ∈ ℝ и p₁, ..., p_m > 0 справедливо

∑_k=1..m a_k²/p_k ≥ (∑_k=1..m a_k)² / (∑_k=1..m p_k),                                                             (9)

причём равенство достигается тогда и только тогда, когда отношения a_k/p_k совпадают для всех k.

Доказательство. По неравенству Коши – Буняковского:

(∑_k a_k)² = (∑_k (a_k/√p_k) · √p_k)² ≤ (∑_k a_k²/p_k) · (∑_k p_k).

Деление на ∑ p_k даёт (9); равенство в неравенстве Коши – Буняковского означает пропорциональность векторов (a_k/√p_k) и (√p_k), то есть a_k/p_k = const.

Теорема 2 (доминирование троичного расщепления). Для любого бинарного расщепления (I_L, I_R) ∈ Π₂(I, φ) существует троичное расщепление (I_L, I_M, I_R') ∈ Π₃(I, φ) с тем же предикатом φ, для которого Δ₃ = Δ₂ + ½ [G_M²/(H_M + λ) + G_R'²/(H_R' + λ) – G_R²/(H_R + λ)] – γ. В частности, при выборе I_M = I_R, I_R' → ∅ имеем Δ₃ → Δ₂ – γ.

Доказательство. Пусть θ – порог исходного бинарного расщепления, I_R = {i: φ(x_i) > θ}. Выберем произвольный θ₂ > θ и положим I_M = {i: θ < φ(x_i) ≤ θ₂}, I_R' = {i: φ(x_i) > θ₂}; тогда I_R = I_M ⊔ I_R', G_R = G_M + G_R', H_R = H_M + H_R'. Подставляя в (8) и используя (7):

Δ₃ – Δ₂ = ½ [G_M²/(H_M + λ) + G_R'²/(H_R' + λ) – G_R²/(H_R + λ)] – γ.                      (10)

При θ₂ → +∞ имеем I_R' → ∅, G_R' → 0, H_R' → 0, и слагаемое G_M²/(H_M + λ) → G_R²/(H_R + λ); таким образом, выражение в скобках стремится к нулю, и Δ₃ → Δ₂ – γ.

Теорема 2 устанавливает условие (К3) определения 3 в асимптотическом смысле: для любого бинарного расщепления существует последовательность троичных, прирост качества которых сходится к бинарному с точностью до штрафа γ. Тем самым доказана корректность предлагаемой модификации в полном объёме определения 3.

Теорема 3 (достаточное условие строгого превосходства). Если для разбиения I_R = I_M ⊔ I_R' выполнено

G_M²/(H_M + λ) + G_R'²/(H_R' + λ) – G_R²/(H_R + λ) > 2γ,                    (11)

то Δ₃(I_L, I_M, I_R') > Δ₂(I_L, I_R).

Доказательство. Подстановка (11) в (10) даёт Δ₃ – Δ₂ > γ – γ = 0.

Лемма 3 (разложение через взвешенную дисперсию). Пусть S = B₁ ⊔ ... ⊔ B_k, H_{B_l} > 0, λ ≥ 0. Введём λ-регуляризованные листовые статистики γ_l = G_{B_l}/(H_{B_l} + λ) и веса π_l = (H_{B_l} + λ)/∑_l(H_{B_l} + λ). Тогда

∑_l=1..k G_{B_l}²/(H_{B_l} + λ) – G_S²/∑_l(H_{B_l} + λ) = ∑_l(H_{B_l} + λ) · Var_π(γ),                   (12)

где Var_π(γ) = ∑_l π_l γ_l² – (∑_l π_l γ_l)² – взвешенная дисперсия γ_l.

Доказательство. По определению γ_l, имеем G_{B_l} = (H_{B_l} + λ)γ_l, откуда G_{B_l}²/(H_{B_l} + λ) = (H_{B_l} + λ)γ_l². Также G_S = ∑_l G_{B_l} = ∑_l(H_{B_l} + λ) · γ̄, где γ̄ = ∑_l π_l γ_l – взвешенное среднее. Тогда G_S²/∑_l(H_{B_l} + λ) = ∑_l(H_{B_l} + λ) γ̄². Получаем

∑_l G_{B_l}²/(H_{B_l} + λ) – G_S²/∑_l(H_{B_l} + λ) = ∑_l(H_{B_l} + λ) γ_l² – ∑_l(H_{B_l} + λ) γ̄² = ∑_l(H_{B_l} + λ) · Var_π(γ).

Лемма 3 даёт прозрачную статистическую интерпретацию прироста: он пропорционален взвешенной дисперсии λ-регуляризованных листовых статистик. При λ → 0⁺ формула (12) переходит в классическое разложение через дисперсию отношений G/H. Расщепление информативно тогда и только тогда, когда оценки γ_l значимо неоднородны. Для троичного расщепления неоднородность по трём подмножествам оценивается лучше, чем по двум, что и составляет статистическое содержание модификации.

Теорема 4 (асимптотический выигрыш для редкой категории). Пусть категориальный признак содержит редкое значение c*; I_M = {i ∈ I: x_i^(k) = c*}, |I_M| = q · |I|, I_R' = I \ I_M. Предположим:

(А1) h_i ≈ h̄ для всех i ∈ I (приближённая однородность вторых производных);

(А2) нормированные градиенты (отношения среднего градиента к средней второй производной) на I_M и I_R' различаются с контрастом c: γ_M – γ_R' = c, где γ_S = ḡ_S/h̄;

(А3) λ ≪ h̄ q(1–q)|I| (регуляризация мала по сравнению с гессиановой массой групп).

Тогда левая часть условия (11) допускает оценку

G_M²/(H_M + λ) + G_R'²/(H_R' + λ) – (G_M + G_R')²/(H_M + H_R' + λ) = h̄ q(1 – q) |I| c² + o(q(1–q)|I|), (13)

то есть выигрыш от выделения редкой категории в собственную ветвь линейно растёт по абсолютному размеру категории q|I| при фиксированном c.

Доказательство. В силу (А1) G_M = ∑_{i ∈ I_M} g_i = |I_M| ḡ_M, H_M ≈ h̄ |I_M| = h̄ q |I|; аналогично G_R' = (1–q)|I| ḡ_R', H_R' ≈ h̄(1–q)|I|. По лемме 3 (при λ > 0, что обосновано условием (А3), гарантирующим λ ≪ H, к разбиению I = I_M ⊔ I_R'):

G_M²/H_M + G_R'²/H_R' – G²/H = H · Var_π(γ),

где γ_M = ḡ_M/h̄, γ_R' = ḡ_R'/h̄, π_M = q, π_R' = 1 – q. Дисперсия двухточечного распределения с весами (q, 1–q) и значениями (γ_M, γ_R') равна q(1–q)(γ_M – γ_R')² = q(1–q) c² (по (А2) γ_M – γ_R' = c). Следовательно

H · Var_π(γ) = h̄ |I| · q(1–q) c² = h̄ q(1–q) |I| c².

Поправка на λ-регуляризацию по (А3) даёт остаток o(q(1–q)|I|), что и завершает (13).

Следствие 1 (условие выгодности троичного расщепления для редкой категории). При выполнении условий (А1)–(А3) теоремы 4 троичное расщепление, выделяющее редкую категорию c* в собственный лист, строго превосходит наилучшее бинарное при выполнении достаточного условия (11), которое в этих обозначениях принимает вид

h̄ q(1–q) |I| c² > 4γ + o(q(1–q)|I|).                                                                     (14)

Таким образом, троичное расщепление статистически и количественно оправдано в подмножествах с систематически отличным локальным градиентом – характерная ситуация для редких категорий и пропусков. Этим завершается теоретическое обоснование корректности и содержательной полезности модификации.

5. Алгоритм и анализ сложности

Поиск оптимального троичного расщепления реализуется как непосредственное обобщение алгоритма поиска бинарного порога [2, 3]. Признак φ предварительно дискретизуется на B корзин гистограммным методом [3]; обозначим G^(b) = ∑_{i: φ(x_i)∈bin b} g_i, H^(b) – аналогично.

Алгоритм 1 (поиск оптимального троичного расщепления узла).

Вход: множество I, признак φ, параметры γ, λ.

1. Вычислить кумулятивные суммы Ĝ_k = ∑_b≤k G^(b), Ĥ_k = ∑_b≤k H^(b) для k = 0, 1, ..., B.

2. Для всех пар 1 ≤ k₁ < k₂ ≤ B – 1 положить G_L = Ĝ_k₁, G_M = Ĝ_k₂ – Ĝ_k₁, G_R = Ĝ_B – Ĝ_k₂ (аналогично для Ĥ); вычислить Δ₃(k₁, k₂) по (8).

3. Возвратить (k₁*, k₂*) ∈ arg max Δ₃ и соответствующее разбиение (I_L, I_M, I_R).

Теорема 5 (вычислительная сложность). Алгоритм 1 имеет временную сложность O(B²) операций на признак на узел при предварительно вычисленных гистограммах G^(b), H^(b) сложности O(|I|). Бинарный аналог имеет сложность O(B) по тем же гистограммам.

Доказательство. Шаг 1 – стандартное накапливающее суммирование по k = 1, ..., B за O(B). Шаг 2 – двойной цикл по парам (k₁, k₂) мощности (B – 1)(B – 2)/2 = O(B²); вычисление Δ₃ по формуле (8) по предвычисленным Ĝ, Ĥ – O(1) операций. Бинарный поиск перебирает O(B) кандидатов, что даёт O(B).

На практике B ограничено гистограммным методом значениями 32–256 [3], так что фактор B приемлем. Дополнительные ускорения: (а) усечение пар по правилу |I_M| ≥ n_min; (б) ранний выход при достижении монотонного убывания; (в) параллелизм по k₁ и по признакам.

В схеме симметричных (oblivious) деревьев CatBoost [4] на каждом уровне используется единый предикат расщепления. При замене бинарного расщепления троичным дерево глубины d имеет 3^d листьев вместо 2^d. Для сохранения сравнимой ёмкости рекомендуется использовать глубину d₃ = ⌊d₂ log₃ 2⌋ ≈ ⌊0,63 d₂⌋ (из условия 3^{d₃} ≈ 2^{d₂}, обеспечивающего сравнимое число листьев). Структура остаётся индексируемой тернарной кодировкой пути; время инференса – O(d).

6. Численный эксперимент

Для эмпирической проверки сравнены бинарное и троичное ветвление в схеме симметричных деревьев на трёх открытых наборах данных с категориальными признаками: Adult (UCI), Bank Marketing (UCI), Amazon Employee Access (Kaggle). Категориальные признаки кодируются упорядоченным TS [4]. Гиперпараметры (λ, γ, темп обучения, число итераций, глубина) подобраны 5-fold кросс-валидацией; для троичной модификации глубина выбирается по соотношению d₃ = ⌊0,63 d₂⌋. Метрика – площадь под ROC-кривой (AUC); приведено относительное время обучения.

Таблица 1.

Сравнение бинарного и троичного ветвления (5-fold CV, средние значения)

Прирост AUC согласуется с теоремой 4: наибольший выигрыш – на наборе Amazon, в котором доля редких категорий и пропусков наибольшая, что приводит к большему контрасту c в (13). Увеличение времени обучения соответствует теореме 5 с поправкой на меньшую глубину d₃ по сравнению с d₂.

7. Заключение

Сформулировано определение корректности модификации (определение 3) и доказана корректность предлагаемой троичной модификации (леммы 1, 3, теоремы 1, 2, формулы (5)–(10)). Выведены замкнутые выражения (5)–(8) для оптимальных значений в листьях и приростов качества Δ₂, Δ₃. Доказана теорема 3 о достаточном условии (11) строгого превосходства троичного расщепления над оптимальным бинарным. А – а

Установлена теорема 4 о квантитативном выигрыше от выделения редкой категории – формула (13), оценивающая прирост через произведение средней гессиановой массы, биномиальной дисперсии q(1–q), размера выборки и квадрата контраста средних градиентов. Доказана теорема 5 о вычислительной сложности O(B²) и приведена схема встраивания в симметричные деревья CatBoost.