Известия РАН. Теория и системы управления, 2023, № 4, стр. 17-24

Введение. Ансамблевые методы имеют весьма продолжительную историю и являются существенной частью технологий машинного обучения, используемых при решении задач обучения по прецедентам: классификации или предсказания числовых переменных [2, 3]. Под ансамблевым методом обычно понимается метод, вычисляющий решения в два этапа: отдельными алгоритмами ансамбля и коллективным алгоритмом.

Среди ансамблевых технологий наибольшее распространение получили метод случайных лесов [4] и метод градиентного бустинга [5]. Данные технологии успешно использовались ранее, в том числе для задач оценивания вещественных характеристик по признаковым описаниям объектов.

Задача обучения по прецедентам в приведенном смысле определяется следующим образом. Рассмотрим совокупность объектов, позволяющих измерить или вычислить $n$ своих числовых характеристик (признаков) ${{X}_{1}}, \ldots ,{{X}_{n}}$. Пусть для некоторых из этих объектов также измерен целевой признак Y, их будем называть прецедентами. Обучающей выборкой назовем множество прецедентов $S = \{ ({{y}_{1}},{{x}_{1}}), \ldots ,({{y}_{m}},{{x}_{m}})\} $, где ${{y}_{i}}$, $i = \overline {1,m} $ – значения целевой переменной $Y$ для i-го объекта, а ${{x}_{i}}$ – вектор признакового описания i-го объекта, ${{x}_{i}} = (X_{1}^{i}, \ldots ,X_{n}^{i})$. Требуется построить алгоритм A для определения (предсказания) значения Y для остальных объектов: $A(x) = y$. В случае, когда Y принимает категориальные значения, задача может называться задачей классификации, а в случае, когда Y  является непрерывной числовой характеристикой, – регрессией.

В методе случайных лесов [4] деревья генерируются независимо с использованием комбинации бэггинга и метода случайных подпространств [6, 7]. Иными словами, каждое новое дерево ${{T}_{k}}$, добавляемое в ансамбль на шаге k, строится по выборке $S_{k}^{b}$, являющейся выборкой с возвращением из проекции исходной обучающей выборки $S_{k}^{b} \subset {{S}^{b}} = \{ ({{y}_{1}},x_{1}^{b}), \ldots ,({{y}_{m}},x_{m}^{b})\} $, где $x_{i}^{b}$ – проекция вектора x_i на признаковое подпространство ${{X}^{b}} \subset \{ {{X}_{1}}, \ldots ,{{X}_{n}}\} $. Процесс генерации деревьев прекращается, когда общее число деревьев в ансамбле достигает заранее заданного числа. В методе случайных лесов применяются простые коллективные решения: при решении задач классификации объект относится в тот класс, к которому его отнесло большинство деревьев ансамбля; при решении регресионных задач коллективный прогноз вычисляется как средний прогноз по ансамблю.

В методах, основанных на градиентном бустинге, каждое новое дерево ${{T}_{k}}$, добавляемое в ансамбль на шаге k, осуществляет один шаг градиентного спуска. Пусть функция $l({{y}_{j}},A({{x}_{j}}))$ описывает потери, возникающие при использовании в качестве прогноза Y в точке ${{x}_{j}}$ величины $A({{x}_{j}})$, например квадратичная ошибка $l({{y}_{j}},A({{x}_{j}})]) = ({{y}_{j}} - A({{x}_{j}}{{))}^{2}}$. Для обучения вычисляется градиент l по $(A({{x}_{1}}), \ldots ,A({{x}_{m}}))$, $\nabla l = \{ {{r}_{1}}, \ldots ,{{r}_{m}}\} $, где ${{r}_{j}} = \partial l({{y}_{j}},A({{x}_{j}})){\text{/}}\partial A({{x}_{j}})$, $j = \overline {1,m} $. Очвидно, для квадратичной ошибки ${{r}_{j}} = 2(A({{x}_{k}}) - {{y}_{j}})$. Пусть ${{A}_{k}}$ – ансамбль, построенный к k-му шагу:

где ${{T}_{0}}$ – некоторое начальное приближение, например тождественный ноль. Если теперь ${{T}_{k}}$ обучается по выборке $\{ r_{1}^{k}, \ldots ,r_{m}^{k}\} $, тем самым аппроксимируя градиент функции потерь при $A = {{A}_{k}}$, а ${{\varepsilon }_{k}}$ – шаг градиентного спуска на шаге k, то ансамбль, построенный таким образом, будет с каждым шагом все точнее оптимизировать заданный функционал, а значит, приближать целевую переменную.

Метод случайных регрессионных лесов и метод градиентного бустинга широко применяются при решении разнообразных прикладных задач, демонстрируя во многих случаях высокую эффективность. Причем ни один из них не является бесспорным лидером – на практике встречаются задачи, где то один, то другой из этих методов демонстрируют превосходство, иногда со значительным отрывом. Вместе с тем можно предположить, что два указанных метода не исчерпывают все возможности достижения высокой эффективности ансамблевых решений. Возникает даже желание объединить эти подходы, что в какой-то мере реализуется в предлагаемом методе.

1. Оптимизируемый функционал. В методе случайных лесов ансамбли генерируются случайно, что, очевидно, не обеспечивает их оптимальности. В то же время градиентный бустинг не является в полной мере ансамблевым методом – это, несомненно, сумма алгоритмов, но каждый в отдельности аппроксимирует не целевую переменную, а производные функции потерь. В нашем методе предлагается совместить лучшее из двух подходов. С одной стороны, будем строить ансамбль из разнообразных элементов, каждый из которых в определенной степени случаен, и аппроксимирует целевую переменную. При этом сами элементы будут строиться путем оптимизации специального функционала, к выводу которого мы переходим.

Рассмотрим итерационную процедуру построения ансамбля. Обозначим через ${{B}_{i}}(x)$ произвольный алгоритм: как дерево, так, например, и линейную комбинацию деревьев, получаемый на i-м шаге. К шагу k ансамбль будет состоять из всех алгоритмов, построенных на предыдущих шагах, а ансамблевым решением ${{A}_{k}}(x)$ считаем среднее этих алгоритмов:

где $O(x)$ – тождественный ноль.

В качестве функционала ошибки нас будет интересовать среднее квадратичное отклонение:

Заметим, что этот функционал можно выразить через средний квадрат отклонения по всем объектам и алгоритмам:

для чего рассмотрим последний:

Откуда следует, что средний квадрат ошибки для алгоритма ${{A}_{k}}$ вычисляется по формуле

Два слагаемых $L(S,{{A}_{k}})$ в полученной формуле имеют простую интерпретацию. Первое описывает отклонение прогнозов от истинных значений Y, а второе представляет собой среднюю дисперсию прогнозов для объектов из S. Последнее слагаемое интерпретируется сложнее, но можно сделать несколько наблюдений. Во-первых, оно стремится к нулю при росте размера ансамбля k. Во-вторых, само его появление вызвано желанием упростить алгоритм и определить ${{A}_{k}}$ как сумму слагаемых предыдущих шагов без включения искомого алгоритма, иначе это слагаемое строго равно нулю. Наконец, в дальнейшем метод потребует еще несколько нестрогих переходов и дополнительных эвристик, поэтому не будем включать последнее слагаемое в функционал:

Таким образом, оптимальность ансамбля может достигаться за счет двух факторов: хорошей аппроксимации связи $Y$ с переменными ${{X}_{1}}, \ldots ,{{X}_{n}}$ на обучающей выборке и высокой дисперсии прогнозов обучающих объектов.

Эти рассуждения позволяют выбрать функционал для оптимизации нового слагаемого ансамбля ${{B}_{k}}$, ${{B}_{k}} = \arg {{\min }_{B}}Q(B,{{A}_{k}})$. Строгое вычисление прироста качества $L(S,{{A}_{k}}) - L(S,{{A}_{{k - 1}}})$ согласно (1.1) приводит к значительному усложнению алгоритма:

Вклад одного эдемента в этот функционал убывает с ростом размера ансамбля, поэтому логичнее для оптимизации отдельного элемента использовать $k(L(S,{{A}_{k}}) - L(S,{{A}_{{k - 1}}}))$, а эта разность, в свою очередь, с ростом $k$ приближается к следующему виду:

что уже значительно удобнее. Тем не менее, $Q(B,{{A}_{k}})$ не достигает минимума по прогнозам B(x₁), ..., $B({{x}_{m}})$ и требует введения параметра $\mu $, где $\mu \in [0,1)$. Дальнейшие построения основываются на предположении, что оптимальность ансамбля в смысле обеспечения с его помощью максимальной обобщающей способности будет достигаться для корректирующих деревьев, при которых функционал $Q(B,{{A}_{k}},\mu )$ минимален: т.е. ${{B}_{k}} = \arg \mathop {\min }\limits_B Q(B,{{A}_{k}},\mu )$.

Далее функционал (1.2) позволяет применить процедуру градиентного бустинга напрямую для построения элементов ансамбля. Такой подход был реализован в [8] и показал хорошие результаты в практических задачах. Однако он не лишен недостатков. В первую очередь это возростание сложности обучения. Кроме того, возникает необходимость подбирать шаг градиентного бустинга.

Этих недостатков лишено непосредственное построение дерева, оптимизирующего функционал (1.2). Аналогия с градиентным бустингом сохраняется, но B попадает в минимум функционала за один шаг, что снижает сложность и не требует подбора параметра. Однако такой способ связан с некоторыми техническими сложностями и будет целью последующих исследований. Для проверки самой концепции рассмотрим другой подход, реализуемый с помощью стандартных методов scikit-learn [9]. Предположим, что минимум Q достигается в точке $B{\kern 1pt} {\text{*}}({{x}_{1}}), \ldots ,B{\kern 1pt} {\text{*}}({{x}_{m}})$. В качестве ${{B}_{k}}$ может быть использовано регрессионное дерево ${{T}_{k}}$, обучаемое по выборке $\{ (B{\kern 1pt} {\text{*}}({{x}_{1}}),{{x}_{1}}), \ldots ,(B{\kern 1pt} {\text{*}}({{x}_{m}}),{{x}_{m}})\} $. По сложности и количеству параметров этот подход аналогичен предыдущему, но в данной работе мы пожертвуем простотой для достижения дополнительного разнообразия в ансамбле с помощью дополнительных техник, таких, как бэггинг и метод случайных подпространств. Опишем данный подход подробнее.

Предположим, что за первые $k - 1$ шагов получен ансамбль ${{B}_{1}}, \ldots ,{{B}_{{k - 1}}}$. Сгенерируем бутстрэп репликацию $S_{k}^{b}$ выборки S в проекции на случайное подпространство, как это описано во Введении. По репликации $S_{k}^{b}$ построим регрессионное дерево ${{T}_{k}}$. Алгоритм ${{B}_{k}}$ ищется в виде суммы ${{B}_{k}} = {{T}_{k}} + {{t}_{k}}$, где ${{t}_{k}}$ – корректирующее дерево, которое строится исходя из условия минимизации $Q({{T}_{k}} + {{t}_{k}})$.

Перепишем функционал (1.2) для этой процедуры:

На первом шаге ищется действительный вектор $t{\kern 1pt} * = t_{1}^{*}, \ldots ,t_{m}^{*}$, компонентами которого являются оптимальные смещения прогнозов, вычисляемых деревом ${{T}_{k}}$, т.е. $t{\kern 1pt} * = \arg \min Q(t,\mu )$. Минимальное значение функционала $Q(t,\mu )$ по ${{t}_{j}}$ достигается при $\partial Q(t,\mu ){\text{/}}\partial t({{x}_{j}}) = 0$ или при

Вместе с тем вычисление оптимальных смещений по формуле (1.4) может приводить к снижению точности формируемого алгоритма ${{B}_{k}}$ по отношению к ${{T}_{k}}$ при соблюдении наборов неравенств:

или

Такого снижения точности можно избежать, если при выполнении одного из наборов неравенств (1.5), (1.6) приравнивать $t_{j}^{*}$ нулю.

Таким образом, описана рекурсивная процедура построения ансамбля алгоритмов. Начиная с пустого ансамбля и тождественного нуля в качестве коллективного решения, затем пополним его суммами пар деревьев, где первое аппроксимирует целевую переменную напрямую, а второе аппроксимирует поправку, минимизирующую функционал $Q(t,\mu )$ (1.3). Построение ансамбля завершается, если k достигает задаваемого пользователем порогового значения N. Ансамбли, которые строятся с помощью представленной выше процедуры, далее будем называть декоррелированными.

2. Коллективное решение и дополнительные эвристики. Наряду со способом генерации ансамбля важную роль для достижения высокой эффективности ансамблевого алгоритма играет процедура, вычисляющая коллективное решение. Хотя ансамбль строится, исходя из соображений минимизации ошибки усредненного ответа алгоритмов, использование такой схемы коллективного решения оказалось недостаточно эффективно. В работе [8] рассматривались несколько других способов, кроме среднего по декоррелированному ансамблю, в частности стекинг [10], т.е. применение прогнозов, вычисляемых отдельными деревьями ансамбля, в качестве признаков для алгоритмов второго уровня, рассчитывающих выходное коллективное решение. Эксперименты, представленные в [8], показывают, что более высокая точность достигается с помощью стекинга со случайным регрессионным лесом, чем с простым усреднением. По этой причине в методе реализованы несколько вариантов коллективного решения: усреднение и стекинг с методом градиентного бустинга и случайным лесом, а также их выпуклой комбинацией.

Наибольшая точность предсказания обычно достигается при больших размерах ансамбля. Однако чрезмерно большое число признаков приводит к увеличению неустойчивости и снижению точности прогноза. Для снижения признакового пространства могут быть использованы различные подходы. В предлагаемом методе применяются две техники: прореживание и переоптимизация. В первом случае после вычисления полного декоррелированного ансамбля все вошедшие в него регрессионные деревья ранжируются по величине функционала $Q(B,\mu )$, где для произвольного элемента B_j, ансамбль полагается равным $\{ {{B}_{i}} \in {{A}_{k}}\,{\text{|}}\,i \ne j\} $. Далее из ансамбля исключаются все недостаточно эффективные слагаемые так, чтобы оставить заданные заранее $N'$ элементов. Эксперименты на реальных задачах не выявили заметного повышения эффективности от использоваия этой процедуры. Возможно, это не так при большем количестве исходных слагаемых, но в таком случае значительно увеличивается вычислительная сложность процедуры. Переоптимизация же оставляет количество слагаемых, но пытается дополнительно “раздвинуть” их. Рассмотрим ансамбль $\{ {{B}_{1}}, \ldots ,{{B}_{N}}\} {{\backslash }}{{B}_{j}}$ и применим процедуру построения нового алгоритма B к этому ансамблю, а затем заменим B_j на полученный алгоритм, и так для всех слагаемых по очереди. Эффект от такой процедуры также не стал грандиозным, однако эти две процедуры оставлены в методе для дальнейшего исследования.

Несколько более высокую эффективность показало применение для снижения размерности признакового пространства варианта метода экстремальной группировки (ЭГ) параметров [11]. На начальном этапе признаки случайно разбиваются на некоторое заранее заданное число групп, для каждой из которых вычисляется соответствующий групповой фактор, как среднее по всем признакам, вошедшим в группу. При этом часть из признаков умножается на –1 для обеспечения одинаковой направленности связей с целевой переменной. Используется процедура, сходная со стандартным методом кластеризации “k-средних” и заключающаяся в переносе каждого из признаков в группу, для которой модуль коэффициента корреляции между признаком и соответствующим групповым фактором максимален. Далее производится пересчет групповых факторов. Процесс завершается в случае отсутствия необходимости переноса признаков на каком-то из шагов. В реализованном методе ЭГ может быть использован как для исходных признаков, что особенно актуально, например, для химических задач с высокой коррелированностью признаков, так и для генерируемого пространства.

В работе не используются стекинг и предварительная кластеризация признаков, поскольку это некие общие процедуры, применимые к любому методу.

Таким образом, свойства итогового алгоритма определяются следующим набором параметров: $N$ – число элементов ансамбля (в экспериментах фиксировалось $N = 200$); $N{\kern 1pt} '$ – число элементов ансамбля после отсеивания (в экспериментах фиксировалось $N{\kern 1pt} ' = N$); $\mu $ – влияние декоррелирующей компоненты функционала (в экспериментах фиксировалось $\mu = 0.5$); $\nu $ – доля признаков, задействованных для построения ${{T}_{k}}$; $\kappa $ – параметр вклада ${{t}_{k}}$: ${{B}_{k}} = {{T}_{k}} + \kappa {{t}_{k}}$ (в экспериментах фиксировалось $\kappa = 1$); $G$ – число групп ЭГ в ансамбле; corrector=average|forest|boosting – тип корректирующей процедуры. Отдельно задаются параметры итоговой корректирующей процедуры. Для бустинга и бэггинга берутся параметры по умолчанию, для усреднения параметры не нужны.

Как это обычно бывает, не существует единого набора гиперпараметров, эффективного для любых прикладных задач. Пример комбинаций, позволяющих достичь преимущества по сравнению с чистымии методами градиентного бустинга и случайного леса, для предсказания свойств химических элементов представлен в [12]. В следующей главе описано применение разработанного метода для решения нескольких других задач.

3. Прикладные задачи. Для оценки качества исследованного алгоритма и диапазона оптимальных гиперпараметров были использованы следующие задачи.

Houses – выборка ’House Prices: Advanced Regression Techniques’²², содержащая данные для оценки стоимости недвижимости по различным признакам, от рельефа участка и длины примыкающей улицы до типа и качества отделки постройки и близости железной дороги. В задаче имеется 1460 объектов, описываемых 79 признаками, большинство из которых категориальные. Для применения метода к таким признакам применялась следующая процедура кодирования: по обучающей подвыборке значения признаков заменялись на среднее целевого показателя для всех объектов с таким значением признака; в тестовой подвыборке использовалось значение из обучающей подвыборки; если в тестовую подвыборку попадало значение, неизвестное в обучающей, оно заменялось на среднее значение целевого признака по всей выборке; пропуски в количественных признаках заменялись нулями, поскольку их природа – площадь отсутствующего элемента.

Prices, Costs – еще одна выборка неджвижимости³³ из репозитория UCI [13]. Выборка содержит 372 объекта, описанных 107 числовыми признаками, по которым предсказывается цена недвижимости и стоимость ее постройки. Эти две задачи рассматривались отдельно.

Systolic – задача оценивания систолического давления по сигналу электрокардиограммы (ЭКГ) [14]. Выборка содержит 836 объектов, описанных 160 спектральными показателями.

Разработанный метод реализован с помощью стандартных методов из библиотеки scikit-learn [9], новизна сводится к использованию модифицированной целевой переменной. Дерево ${{T}_{k}}$ ищется с помощью BaggingRegressor с числом элементов, равным одному, и $max\_features = \nu $. Поправка ${{t}_{k}}$ реализована с помощью DecisionTreeRegressor. Для экспериментов часть гиперпараметров фиксировалась и делалось несколько запусков с различными значениями $\mu $, $\nu $, $G$ и корректора. В этом порядке они и приводятся при описании результатов.

Также из scikit-learn были взяты референсные методы: BoostingRegressor в качестве реализации градиентного бустинга и RandomForestRegressor – как случайный лес. Все методы запускались с размером ансамбля, равным 200, и остальными параметрами по умолчанию. Мы сознательно отказались от попыток сравнить качество с другими исследователями и провели собственные тесты по нескольким соображениям, главное из которых – поставить методы в относительно одинаковые условия и выявить эффект, оказываемый техникой декорреляции. Так, задача Houses требует предобработки признаков, и улучшение результатов достигается лидерами соревнования Kaggle, в том числе за счет улучшения этой обработки. Это же во многом касаетися и задач Costs и Prices – наиболее свежее доступное исследование этих данных также во многом сосредоточено на специфике выборки [15], в то время как мы изучаем общий подход. Задача Systolic в таком виде никем не исследовалась.

Полученные результаты и параметры запуска представлены в табл. 1. Для оценки качества предсказания использовались две характеристики: коэффициент детерминации (R-квадрат, R²) и среднее абсолютное отклонение (MAE). Решение задач производилось в режиме скользящего контроля с разбиением на 10 частей. Кроме того, результаты усреднялись по 10 запускам, чтобы отразить их устойчивость, поэтому в таблице приводится среднее значение (mean) и стандартное отклонение (stdev) показателей.

Первое, на что стоит обратить внимание, это разные соотношения качества самих референсных методов. Видно, что в задачах с недвижимостью бустинг показывает значительно лучшее качество, чем случайный лес. В то же время в задаче оценивания давления бустинг значительно отстает. В свою очередь предлагаемый метод всегда демонстрирует превосходство над аутсайдером. В задачах Prices и Costs при этом удалось только сравняться с лидером. В задаче Houses лидерство уже более явное – предлагаемый метод лидирует как по R², так и по средней абсолютной ошибке. Наилучший же результат метод продемонстрировал в задаче оценивания систолического давления, где лидера пары референсных методов – на этот раз случайный лес – удалось значительно обойти по обоим критериям.

Что касается выбора гиперпараметров, то в очередной раз подтвердилась их неуниверсальность. Где-то преимущество дали высокие $\nu $, где-то – наоборот. В задачах с недвижимостью хорошим корректором оказался случайный лес, а в прогнозе давления – простое усреднение.

Заключение. Представлен новый ансамблевый регрессионный метод. Дается дополнительное обоснование подхода, уточняющее вывод, который приведен в предыдущих работах. Также рассмотрены результаты тестирования метода, оценивающие возможность его использования при решении прикладных задач в бизнесе и медицине. Результаты экспериментов подтверждают перспективность предлагаемого подхода.

Дальнейшие исследования предполагается направить на повышение быстродействия метода, что возможно достигнуть, во-первых, за счет непосредственного построения элементов ${{B}_{k}}$ как деревьев со специальным функционалом качества, а во-вторых, за счет оптимизации построения этих деревьев, в том числе с помощью библиотеки cython.