Автоматика и телемеханика, № 12, 2022
© 2022 г. Н.С. КОРОЛЕВ (korolev.nikolay.s@gmail.com)
(Московский государственный университет им. М.В. Ломоносова),
О.В. СЕНЬКО, д-р физ.-мат. наук (senkoov@mail.ru)
(ФИЦ “Информатика и управление” РАН, Москва)
МЕТОД ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБУЧЕНИЯ
ГРАДИЕНТНОГО БУСТИНГА, ОСНОВАННЫЙ
НА МОДИФИЦИРОВАННЫХ ФУНКЦИЯХ ПОТЕРЬ
Рассматривается новый метод повышения качества обучения градиент-
ного бустинга, а также увеличения его обобщающей способности, осно-
ванный на использовании модифицированных функций потерь. В ходе
выполнения вычислительных экспериментов была показана возможная
применимость данного метода для улучшения качества градиентного бу-
стинга, решающего различные задачи классификации и регрессии на ре-
альных данных.
Ключевые слова: градиентный бустинг, дерево решений, функции потерь,
машинное обучение, анализ данных.
DOI: 10.31857/S0005231022120078, EDN: KSLBAE
1. Введение
Методы машинного обучения широко используются при решении разнооб-
разных прикладных задач [1-3], в которых требуется предсказать значения
некоторой неизвестной величины по значениям известных показателей объ-
ектов. В последние годы все большее распространение приобретают ансам-
блевые методы [4, 5], среди которых следует выделить методы, использую-
щие ансамбли регрессионных или решающих деревьев. Известными способа-
ми генерации ансамблей являются метод бэггинга и метод случайных под-
пространств, используемые в случайных лесах, а также метод градиентного
бустинга. Эффективность случайных лесов и ансамблевых методов, основан-
ных на градиентном бустинге, подтверждается обширной практикой решения
прикладных задач. Вместе с тем убедительные теоретические обоснования
их оптимальности отсутствуют. Все это свидетельствует об актуальности ис-
следований, направленных на поиск новых критериев оптимальности гене-
рируемых ансамблей и методов вычисления коллективных решений, которые
позволили бы увеличить обобщающую способность ансамблевых алгоритмов.
В [6] рассматривается схема поиска ансамбля регрессионных деревьев с ми-
нимальной квадратичной ошибкой для среднего прогноза по ансамблю. При
этом регрессионные деревья, входящие в ансамбль, генерируются с помощью
процедуры бэггинга и дополнительного одношагового градиентного спуска.
В настоящей работе анализируется связь схемы с минимальной ошибкой для
среднего прогноза со стандартной процедурой градиентного бустинга. Пока-
зано, что данная схема по сути сводится к относительно небольшой моди-
78
фикации стандартной процедуры, которая тем не менее позволяет добиться
заметного увеличения обобщающей способности.
2. Модификация градиентного бустинга
Обозначим: x1, . . . , xN
точки в некотором многомерном пространстве,
соответствующие известным и легко измеряемым признакам реальных объ-
ектов; y1, . . . , yN
значения некоторых трудно измеряемых признаков объек-
тов. Встает задача поиска некоторой функции f(x) такой, что yi = f(xi) + εi,
где εi ошибка предсказания на i-м объекте, т.е. функция f(x) должна при-
ближать реальную зависимость между искомыми значениями yi и известны-
ми признаками xi. Для построения функции f(x) используется информация
лишь о некоторых T < N объектах, а качество приближения проверяется по
оставшимся N - T объектам.
Данная задача хорошо решается методами ансамблирования, основанны-
ми на построении большого количества деревьев решений. Одним из таких
методов является градиентный бустинг [7]. В этой работе стоит задача улуч-
шения качества работы данного метода за счет изменения процедуры обуче-
ния градиентного бустинга с использованием модифицированных функций
потерь.
2.1. Градиентный бустинг
Пусть:
X матрица из T строк, i-я строка равна xi;
Y вектор из T элементов, i-й элемент равен yi.
Градиентный бустинг [7] основан на итеративном построении функции
f (x) за счет использования большого количества деревьев решений, каждое
из которых исправляет ошибки предыдущих. Изначально задается оптими-
зируемый функционал. Одним из стандартных оптимизируемых функциона-
1
∑
лов является среднеквадратичная ошибка L(f(x), X, Y ) =
(f(xi) - yi)2.
T i=1
Также вводится некоторое изначальное значение функции предсказа-
1
∑
ния f0(x) = 0 или f0(x) =
yi. Далее итеративно строятся функции
T i=1
fi(x) = fi-1(x) + βihi(x), где hi(x) дерево решений, обученное по следую-
щей схеме:
Алгоритм 1 (оригинальный алгоритм градиентного бустинга).
1. Из выборки X, Y при помощи метода бутстрапирования и случайной
проекции на произвольное подпространство признаков получается новая вы-
боркаXi
Yi.
2. Находится антиградиент функции потерь по функции f в точке теку-
щего ансамбляĥ(x) = -∇f (L(f(x),Xi
Yi))
f (x)=fi-1(x)
3. Строится дерево решений hi(x) по выборке
Xi,ĥ(Xi).
79
4. fi(x) = fi-1(x) + βihi(x), где βi ∈ R некоторый коэффициент, с кото-
рым добавляется дерево hi(x) в уже существующий лес fi-1(x).
Спустя некоторое заранее оговоренное количество итераций процесс оста-
навливается и очередное fi(x) считается искомым f(x).
При этом возможно достаточно большое количество выбора стратегий βi.
Наиболее известными являются:
• βi = const,
const
• βi =
√
,
i+1
const
• βi =
,
i+1
• βi = argminL(fi-1(x) + βh(x),Xi
Yi).
β
Также существуют различные модификации градиентного бустинга, поз-
воляющие улучшить его обобщающую способность и скорость работы, такие
как CatBoost [8], XGBoost [9], LightGBM [10].
2.2. Измененный алгоритм градиентного бустинга
В данной статье придется изменить алгоритм градиентного бустинга. Из-
меним шаг 2. Вместо того, чтобы брать функцию, равную антиградиен-
ту функции потерь, будем искать такую функциюĥ(x), добавка которой
к исходной функции fi-1(x) приведет к минимизации функции потерь, т.е.
L(fi-1(x) +ĥ(x),Xi
Yi) → min.
ĥ(x)
Алгоритм 2 (измененный алгоритм градиентного бустинга).
1. Из выборки X, Y при помощи метода бутстрапирования и случайной
проекции на произвольное подпространство признаков получается новая вы-
боркаXi
Yi.
2. Находится такая функция
ĥ(x), что функция потерь от функции
fi-1(x)+ĥ(x) на выборкеXi
Yi будет минимальна: L(fi-1(x)+ĥ(x),Xi
Yi) →
→ min. Приравнивая градиент функции потерь к нулю, получим
∑
2
∇ˆh(x)L(fi-1(x) +ĥ(x),Xi
Yi) =
(fi-1(xik) +ĥ(xik) - ŷik) = 0,
T
k=1
ĥ(xik) = ŷik - fi-1(xik),
где xik, ŷik
признаки k-го объекта в выборкеXi
Yi.
3. Строится дерево решений hi(x) по выборке
Xi,ĥ(Xi).
4. fi(x) = fi-1(x) + βihi(x), где βi ∈ R некоторый коэффициент, с кото-
рым добавляется дерево hi(x) в уже существующий лес fi-1(x).
Заметим, что в случае, когда функция ошибки L зависит квадратично
от функции f(x) и при этом коэффициент при f2(x) не зависит от значе-
80
ний выборки, предложенный измененный алгоритм градиентного бустинга
полностью совпадает с оригинальным вариантом (с точностью до изменения
learning rate’а, который в данном случае обозначается как βi).
3. Модифицированные функции потерь
3.1. Разложение ошибки
Для произвольного ансамбля алгоритмов известно [11] разложение ошибки
ансамбля на смещение отдельных алгоритмов и дисперсию. Сформулируем
это разложение в виде теоремы.
Теорема 1. Пусть x,y произвольные случайные величины; даны K
функций hk(x), и функция f(x) задана как среднее арифметическое этих K
функций:
∑
1
f (x) =
hk(x),
K
k=1
тогда верно:
∑[
]
1
(1)
E(y - f(x))2
=
E(hk(x) - y)2 - E(hk(x) - f(x))2
K
k=1
Доказательство.
∑
∑
1
1
E(hk(x) - y)2 =
E(hk(x) - f(x) + f(x) - y)2 =
K
K
k=1
k=1
1
∑[
]
=
E(hk(x) - f(x))2 - 2 E [(hk(x) - f(x))(y - f(x))] + E(y - f(x))2
=
K
k=1
∑[
]
1
=
E(hk(x) - f(x))2 + E(y - f(x))2
-
K
k=1
[
]
∑
2
-
E (hk(x) - f(x))(y - f(x))
=
K
k=1
∑[
]
1
=
E(hk(x) - f(x))2 + E(y - f(x))2
-
K
k=1
[
]
∑
2
-
E (y - f(x)) (hk(x) - f(x))
=
K
k=1
∑[
]
1
=
E(hk(x) - f(x))2 + E(y - f(x))2
-
K
k=1
2
-
E [(y - f(x))(Kf(x) - Kf(x))] =
K
81
∑[
]
1
=
E(hk(x) - f(x))2 + E(y - f(x))2
=
K
k=1
∑
1
=E(y - f(x))2 +
E(hk(x) - f(x))2.
K
k=1
1
∑
Перенося слагаемое
E(hk(x) - f(x))2 в левую часть, получим:
K k=1
1
∑[
]
E(y - f(x))2
=
E(hk(x) - y)2 - E(hk(x) - f(x))2
K
k=1
Соответственно для уменьшения среднеквадратичной ошибки необходи-
мо уменьшать среднеквадратичную ошибку каждого отдельного предикто-
ра hk(x), а также увеличивать расхождение между прогнозами различных
предикторов. Вдохновляясь данным разложением, в следующей главе пред-
ложим использовать для обучения градиентного бустинга функцию ошибки,
которая будет очень сильно напоминать правую часть данного разложения.
3.2. Среднеквадратичная ошибка с удалением от обученного ансамбля
В модифицированном алгоритме градиентного бустинга, описанном в гла-
ве 2.2, на каждой итерации градиентного бустинга оптимизируется средне-
квадратичная ошибка:
∑
1
L(f(x) + h(x), X, Y ) =
(f(xi) + h(xi) - yi)2,
T
i=1
где f(xi) предсказания обученного на текущий момент ансамбля, yi от-
клики, h(xi) предсказания нового дерева решений (по ним происходит оп-
тимизация функционала).
Исходя из выведенной ранее формулы 1 для повышения обобщающей спо-
собности леса деревьев решений разумно на каждом шаге оптимизировать
функцию
∑[
]
1
(2)
(h(xi) + f(xi) - yi)2 - γ(f(xi) - h(xi))2
T
i=1
∑
Здесь часть1T (h(xi) + f(xi) - yi)2 соответствует слагаемомуE(hk(x) - y)2
i=1
в формуле 1 (для текущей итерации k) за тем исключением, что здесь
хотим, чтобы именно сумма функций f(x) + h(x) предсказывала искомый
отклик y. Данное изменение было сделано в силу того, что функция
∑
1
(h(xi) + f(xi) - yi)2 является среднеквадратичной функцией потерь для
T
i=1
82
T
2
алгоритма градиентного бустинга, в то время как функция1
(h(xi) - yi)
T
i=1
соответствует процедуре обучения случайного леса. Стоит отметить, что,
формально говоря, это не соответствует формуле 1, поэтому отметим, что
формула 1 приводится как источник вдохновения и мотивации авторов
использовать функцию потерь под формулой 2.
В данной функции есть дополнительная добавка -γ(h(xi) - f(xi))2, поз-
воляющая добиться дополнительной регуляризации за счет различия меж-
ду новым обучаемым деревом и уже обученным лесом решающих деревьев.
Кроме того, это соответствует разложению среднеквадратичной ошибки ан-
самбля по формуле 1 с одним лишь исключением коэффициентом γ перед
вторым слагаемым. Коэффициент γ < 1 необходим для существования мини-
мума по h(x) для функции 2.
Соответственно обучение деревьев будет производиться на откликах, пре-
образованных следующей функцией:
ĥ(xik) =ŷk -(1+γ)fi-1(xk)
1-γ
Заметим, что для γ = 1 (как в оригинальной формуле разложения ошибок)
минимум не находится, поэтому используется коэффициент γ.
Кроме того, поскольку итоговое дерево h(x), обученное на выходахĥ(x),
будет добавляться с некоторым коэффициентом βi, то, если обучать дерево
на выходах (1 - γ)ĥ(xik) = ŷik - (1 + γ)fi-1(xik), обученное дерево на самом
деле будет соответствовать (1 - γ)h(x) и можно получить точно такой же
βi
лес, добавив полученное дерево с коэффициентом
1-γ
3.3. Смещенная среднеквадратичная ошибка
∑
Будем использовать L(f(x), X, Y ) =1T (αf(xi) - yi)2, где α ∈ R++. В та-
i=1
кой ситуации новые деревья решений будут обучаться на выборке, у которой
отклики были преобразованы следующей функцией:
ĥ(xik) =1
ŷik - fi-1(xik).
α
Заметим, что, как и в предыдущем случае, возможно обучение дерева ре-
шений на выходах αĥ(xik) = ŷik - αfi-1(xik) и добавления дерева решений с
βi
коэффициентом
α
Основная идея данного подхода заключается в том, чтобы добавить шума
в обучаемые деревья решений, для того чтобы уменьшить корреляцию меж-
ду выходами различных деревьев решений в итоговом лесе, что позволяет
увеличить обобщающую способность обучаемой модели [12].
Отметим, в такой ситуации оказывается, что использование данной функ-
ции потерь с параметром α = 1 + γ абсолютно эквивалентно использованию
83
предыдущей модификации функции потерь. Кроме того, логично использо-
вать только лишь 0 ≤ γ ≤ 1, так как в случае γ < 0 будет поощряться похо-
жесть откликов нового дерева решений на отклики всего ансамбля, в то время
как было решено уменьшать корреляцию между ними, а в случае γ > 1 функ-
∑
[
]
1
ция
(h(xi) + f(xi) - yi)2 - γ(h(xi) - f(xi))2
будет иметь минимум в
T
i=1
точках h(xi) = ±∞. В соответствии с границами изменения γ, а также вы-
веденной зависимостью α = 1 + γ получаем, что имеет смысл рассматривать
лишь α ∈ [1; 2].
4. Вычислительные эксперименты
Для проверки качества работы представленного метода будем решать раз-
личные задачи классификации и регрессии, используя обычный градиентный
бустинг, сравнивая результаты работы с градиентным бустингом с исполь-
зованием смещенной квадратичной ошибки1. Кроме того, проводились вы-
числительные эксперименты с использованием среднеквадратичной ошибки
с удалением от обученного ансамбля, но их результаты полностью совпадают
с использованием обычной смещенной квадратичной ошибки, что соответ-
ствует теории.
4.1. Описание данных
4.1.1. Обнаружение аритмии. Данные2 состоят из 452 записей ЭКГ.
Каждая запись представлена в виде набора из 279 признаков, 206 из ко-
торых линейные, остальные 73 являются перечислимыми. Кроме того, в
признаках встречаются пропуски. В данных присутствует информация о том,
какой вид аритмии присутствует у пациента, или отмечается факт, что арит-
мия отсутствует [13]. По этим данным строится дополнительный признак
¾наличие аритмии¿, который равен 0, если аритмия отсутствует, или 1 при
наличии любого вида аритмии. Ставится задача классификации по целевому
бинарному признаку ¾наличие аритмии¿. Целевой метрикой качества явля-
ется ROC AUC.
4.1.2. Таяние ледников в Арктике. Данные3 состоят из 170 записей
о ледниках в Арктике. Необходимо предсказать, растаял ли ледник или нет,
имея информацию о 96 параметрах исследуемого ледника. Целевая метрика
качества ROC AUC.
4.1.3. Предсказание продаж. Данные состоят из 869 записей о количе-
стве продаж некоторого товара вместе с описанием товара. Описание состоит
из 286 бинарных признаков и двух линейных численных признаков. Решает-
ся задача регрессии по целевому признаку ¾количество продаж¿. Целевой
метрикой качества является коэффициент детерминации R2.
=sharing
84
4.1.4. Предсказание систолического давления. Данные представля-
ют из себя 837 записей о 160 параметрах пациентов. Ставится задача ре-
грессии по целевому признаку ¾систолическое давление¿ выборки. Целевой
метрикой качества является коэффициент детерминации R2.
4.2. Процедура обучения
Каждая из выборок данных делится на три подвыборки: обучающую, про-
верочную и тестовую в соотношении 65%/10%/25% соответственно. Затем
обучение разбивается на два этапа:
1) поиск гиперпараметра α,
2) проверка эффективности обучения модели.
4.2.1. Поиск гиперпараметра α. На каждом наборе данных произво-
дится поиск гиперпараметра α в модели градиентного бустинга со средне-
квадратичной ошибкой. Для этого производится обучение нескольких мо-
делей на обучающей выборке с различными значениями гиперпараметра α.
Затем качество каждой модели проверяется на проверочной выборке. Пара-
метр, соответствующий модели с наилучшим качеством на данной выборке,
используется для следующего этапа обучения.
4.2.2. Проверка эффективности обучения модели. На этом этапе
обучающая и проверочная выборки по каждому из наборов данных объеди-
няются, и на соответствующей выборке производится обучение всех после-
дующих моделей.
Модель градиентного бустинга со смещенной среднеквадратичной ошиб-
кой обучается на полученном наборе данных с параметром α, выведенным
с предыдущего этапа, затем качество модели оценивается на тестовой части
выборки. Аналогичная процедура обучения производится с моделью обычно-
го градиентного бустинга.
4.3. Результаты экспериментов
Наиболее хороших результатов на различных задачах удалось достичь для
α = 1,1. Использование модифицированной функции потерь позволило улуч-
шить предсказательную способность градиентного бустинга как на задачах
классификации, так и на задачах регрессии.
Целевая метрика на тестовой выборке для лесов, обученных стандартной проце-
дурой градиентного бустинга (столбец ¾Среднекв. ошибка¿) и с использованием
смещенной среднеквадратичной ошибки (столбец ¾Смещенная среднекв. ошибка¿)
Набор данных Среднекв. ошибка Смещенная среднекв. ошибка Параметр α
Аритмия
0,89 (ROC AUC)
0,90 (ROC AUC)
1,7
Ледники
0,72 (ROC AUC)
0,75 (ROC AUC)
1,1
Продажи
0,21 (R2)
0,26 (R2)
1,1
Сист. давл.
0,41 (R2)
0,46 (R2)
1,1
85
0,900
0,895
1,0
1,2
1,4
1,6
1,8
2,0
a
Рис. 1. ROC AUC при обучении классификатора с использованием смещенной
среднеквадратичной ошибки для различных параметров α в задаче предска-
зания аритмии.
0,750
0,725
0,700
0,675
0,650
1,0
1,2
1,4
1,6
1,8
2,0
a
Рис. 2. ROC AUC при обучении классификатора с использованием смещенной
среднеквадратичной ошибки для различных параметров α в задаче предска-
зания таяния ледников.
Итоговые результаты экспериментов представлены в таблице.
Помимо этого приведем графики качества в зависимости от параметра α
для каждой задачи (рис. 1-4).
4.4. Анализ полученных результатов
Полученные результаты показывают, что использование модифицирован-
ных функций потерь в процедуре обучения решающего дерева при помощи
градиентного бустинга способно достаточно серьезно увеличивать обобщаю-
щую способность предсказания в сравнении с обычной процедурой обучения
градиентного бустинга.
На графиках зависимости качества модели от параметра α явно видно,
что при больших значениях параметра α алгоритм имеет слишком низкую
обобщающую способность и начинает терять в качестве, помимо этого в трех
из четырех задачах наилучшим выбором коэффициента α было 1,1, поэтому
считаем, что именно таким стоит выбирать значения гиперпараметра α.
Кроме того, наблюдается эффект недообучения при использовании моди-
фицированных функций потерь в случае, когда объектов достаточно много.
86
0,2
0
-0,2
-0,4
1,0
1,2
1,4
1,6
1,8
2,0
a
Рис. 3. R2 при обучении регрессора с использованием смещенной среднеквад-
ратичной ошибки для различных параметров α в задаче предсказания про-
даж.
0,4
0,3
0,2
1,0
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
a
Рис. 4. R2 при обучении регрессора с использованием смещенной среднеквад-
ратичной ошибки для различных параметров α в задаче предсказания систо-
лического давления.
В такой ситуации применялась смешанная стратегия обучения первая по-
ловина итераций обучалась с использованием смещенной среднеквадратич-
ной ошибки, а вторая половина обучалась в соответствии со стандартным
алгоритмом градиентного бустинга.
5. Заключение
В процессе выполнения работы были получены следующие результаты.
Разработан метод повышения эффективности обучения градиентного
бустинга, основанный на использовании модифицированных функций потерь.
Получено теоретическое доказательство эквивалентности метода, ис-
пользующего смещенную среднеквадратичную ошибку, и метода, использую-
щего среднеквадратичную ошибку с удалением от обученного ансамбля.
Проведены вычислительные эксперименты, которые показали возмож-
ную применимость данного метода для улучшения обобщающей способности
лесов решений, построенных алгоритмом градиентного бустинга, на различ-
ных реальных задачах регрессии и классификации.
87
Выявлено значение параметра α = 1,1 в смещенной среднеквадратичной
ошибке, при котором достигается наиболее стабильный эффект прироста ка-
чества работы модели.
СПИСОК ЛИТЕРАТУРЫ
1.
Friedman Jerome H. Multiple Additive Regression Trees with Application in Epi-
demiology // Statist. in Medicine. 2003. V. 22. No. 9. P. 1365-1381.
2.
Elith J. Boosted Regression Trees for ecological modeling // CRAN. 2018. V. 77(4).
P. 802-813.
3.
Lalchand V. Extracting more from boosted decision trees: A high energy physics case
study // arXiv:2001.06033. 2020.
4.
Breiman L. Random forests // Machine Learning. 2001. V. 45. No. 1.
5.
Zhi-Hua Z. Ensemble Methods: Foundations and Algorithms // Chapman and
Hall/CRC. 2012.
6.
Журавлев Ю.И., Сенько О.В., Докукин А.А., Киселева Н.Н., Саенко И.А. Двух-
уровневый метод регрессионного анализа, использующий ансамбли деревьев
с оптимальной дивергенцией // ДАН. Математика, информатика, процессы
управления. 2021. Т. 499. № 1. С. 63-66.
7.
Friedman Jerome H. Stochastic gradient boosting // Comput. Statist. & Data Anal.
2002. V. 38. No. 4. P. 367-378.
8.
Prokhorenkova L., Gusev G., Vorobev A., Dorogush A.V., Gulin A. CatBoost: unbi-
ased boosting with categorical features // arXiv:1706.09516. 2017.
9.
Chen T., Guestrin C. XGBoost: A Scalable Tree Boosting System //
arXiv:1603.02754. 2016.
10.
Ke G. et al. LightGBM: A Highly Efficient Gradient Boosting Decision Tree //
Advances in Neural Information Processing Systems. 2017. V.30. P. 3146-3154.
11.
Gavin Brown, Jeremy Wyatt, Rachel Harris, Xin Yao Diversity creation methods:
A survey and categorisation // Information Fusion. 2005. V. 6. P. 367-378.
12.
Докукин А.А., Сенько О.В. Оптимальные выпуклые корректирующие процеду-
ры в задачах высокой размерности // Ж. вычисл. матем. и матем. физ. 2011.
Т. 51. С. 1751-1760.
13.
Guvenir H. Altay, Acar B., Muderrisoglu H. Arrhythmia Data Set //
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 31.01.2022
После доработки 21.06.2022
Принята к публикации 29.06.2022
88
