Адаптивные стратегии обучения градиентного бустинга тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Ибрагимов Булат Ленарович

• Ибрагимов Булат Ленарович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Ибрагимов Булат Ленарович

Введение

Глава 1. Градиентный бустинг

1.1 Основные концепции

1.2 Стохастический градиентный бустинг

1.3 Адаптивные методы обучения градиентного бустинга

Глава 2. Сэмплирование с наименьшей дисперсией

2.1 Постановка задачи

2.2 Решение задачи оптимального сэмплирования

2.3 Алгоритм Minimal Variance Sampling (MVS)

2.4 Поиск порогового значения за линейное время

2.5 Адаптивный алгоритм MVS

2.6 Результаты экспериментов

Глава 3. Адаптивная ранняя остановка

3.1 Постановка задачи

3.2 Ранняя остановка с помощью кросс-валидации

3.3 Основная идея адаптивной ранней остановки

3.4 Регрессионные методы для адаптивной ранней остановки

3.5 Использование кластеризации для адаптивной ранней остановки

3.6 Алгоритм Direct Supervised Partitioning (DSP)

3.7 Алгоритм Indirect Supervised Partitioning (ISP)

3.8 Протокол валидации и подбора гиперпараметров

3.9 Результаты экспериментов

Глава 4. Адаптивный подбор гиперпараметров на основе

Out-of-Sample оценок

4.1 Мотивация

4.2 Влияние качества отдельных деревьев на процесс обучения

4.3 Оптимизация гиперпараметров на основе OOS оценок

4.4 Эксперименты

Стр.

Глава 5. Применение градиентного бустинга к оценке

индивидуального эффекта воздействия

5.1 Задача uplift моделирования

5.2 Использование градиентного бустинга с многомерным выходом

5.3 Псевдометки для предсказания uplift

5.4 Моделирование uplift с множественными воздействиями

5.5 Эксперименты

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Список рисунков

Список таблиц

Введение

Актуальность темы исследования. Несмотря на значительный рост популярности глубоких нейросетевых моделей, градиентный бустинг [1] остается высокоактуальным в условиях обработки больших данных и решения сложных задач машинного обучения [2]. Градиентный бустинг зарекомендовал себя как один из наиболее эффективных методов для создания высокоточных моделей предсказания благодаря своей способности объединять множество слабых моделей в одну сильную. Однако, несмотря на его эффективность, существующие методы градиентного бустинга не способны подстраивать свое поведение под различные данные, что ограничивает качество получаемых моделей. Существует потребность в разработке более гибких и адаптивных алгоритмов, которые смогут учитывать уникальные особенности каждого набора данных и изменяющиеся условия обучения. Разработка подобного рода алгоритмов может значительно расширить их применимость в различных областях, таких как финансы, медицина, маркетинг и интернет-технологии, где требуется высокая точность предсказаний и способность обрабатывать большие объемы данных [3, 4, 5, 6, 7].

Степень разработанности темы. Одной из ключевых проблем градиентного бустинга [8] является выбор оптимального количества моделей в ансамбле, чтобы избежать переобучения и обеспечить высокую точность. Методы ранней остановки, такие как предложенные в работе [1], используют проверочный набор данных для определения момента остановки обучения, что предотвращает переобучение. Однако стандартный подход к ранней остановке предполагает универсальный размер ансамбля для всех точек данных, что может быть неэффективно в условиях гетерогенных данных.

Современные методы, такие как Stochastic Gradient Boosting (SGB) [9] и Gradient-Based One-Side Sampling (GOSS) [10], были разработаны для улучшения вычислительной эффективности и точности моделей за счет адаптивного выбора данных для обучения. SGB добавляет случайность в процесс построения деревьев, что снижает вычислительную сложность и иногда улучшает качество модели. GOSS, в свою очередь, выбирает наиболее важные объекты на основе величины градиента, что позволяет улучшить точность оценки разбиений в деревьях решений. В то же время предложенные методы не всегда дают

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

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

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

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

Задачи исследования. Для достижения поставленных целей были определены следующие задачи:

1. Анализ существующих подходов к адаптивному обучению градиентного бустинга, выявление их слабых сторон, поиск путей их улучшения.

2. Разработка теоретической базы для новых адаптивных алгоритмов обучения градиентного бустинга.

3. Разработка применимых на практике алгоритмов адаптивного обучения градиентного бустинга.

4. Реализация предложенных алгоритмов в рамках существующих и широко используемых библиотеках машинного обучения.

5. Проведение серии экспериментов для оценки эффективности предложенных методов, а также сравнения с существующими подходами.

6. Проведение сравнительного анализа результатов экспериментов и получение практических рекомендаций по обучению моделей градиентного бустинга.

Научная новизна. В рамках данного исследования предложены следующие инновационные подходы:

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

2. Алгоритмы адаптивной ранней остановки обучения (DSP, ISP). Эти алгоритмы учитывают гетерогенность данных, обеспечивая более точное управление процессом обучения и предотвращая переобучение.

3. Алгоритм адаптивного подбора гиперпараметров и анализа поведения модели на основе качества обучаемых деревьев. Данный алгоритм позволяет эффективно оценивать качество всего ансамбля и улучшать его, оптимизируя структуру деревьев на каждом шаге обучения.

4. Uplift-моделирование [14] с использованием многовыходных моделей градиентного бустинга. Этот подход позволяет более точно оценивать влияние различных факторов на результат, что особенно важно в маркетинговых и медицинских приложениях.

5. Валидационные протоколы и методы оптимизации гиперпараметров. Предложенные методы обеспечивают более надежную и быструю настройку моделей, что сокращает время разработки и улучшает качество предсказаний.

6. Применение предложенных методов в современных фреймворках машинного обучения (CatBoost [11], LightGBM [10]). Интеграция в популярные фреймворки подтверждает практическую применимость и эффективность новых подходов, что делает их доступными для широкого круга пользователей.

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

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

Методология исследования. Основные методы, используемые в работе, можно разделить на несколько ключевых этапов: разработка теоретической базы и алгоритмов; реализация и интеграция; эмпирическая оценка и экспериментальное тестирование. Последний пункт включает в себя процедуры оценки и валидации результатов; построение дизайна экспериментов; применение популярных библиотек машинного обучения, таких как LightGBM и CatBoost, для реализации и тестирования предложенных алгоритмов. Сравнительный анализ проводился при помощи методов математической статистики. Для практической реализации алгоритмов, а также для проведения экспериментов использовались языки программирования C++ и Python с применением библиотек машинного обучения CatBoost, LightGBM, XGBoost, PyBoost, Hyperopt, CausalML, scikit-uplift.

Положения, выносимые на защиту:

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

2. Разработанные алгоритмы ранней остановки (DSP, ISP) позволяют более точно и эффективно управлять процессом обучения, улучшая общую точность моделей.

3. Новый подход контроля за процессом обучения, основанный на out-of-sample оценках качества отдельных деревьев позволяет улучшать качество моделей и эффективно бороться с переобучением на шиоком спектре задач.

4. Новый подход к моделированию uplift с использованием многовыходных моделей градиентного бустинга повышает точность предсказаний по сравнению с традиционными методами и дает более стабильные результаты на разных наборах данных.

5. Разработанные алгоритмы были интегрированы в такие популярные фреймворки, как CatBoost и LightGBM, что подтверждает их

практическую значимость и эффективность для широкого круга задач машинного обучения.

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

Введение диссертации (часть автореферата) на тему «Адаптивные стратегии обучения градиентного бустинга»

Апробация работы.

Результаты исследования были представлены и обсуждены на ряде научных конференций и семинарах:

- Международная конференция Neural Information Processing Systems, 8-14 декабря, 2019, Ванкувер, Канада

- 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 25-29 августа, 2024, Барселона, Испания

- журнал «Труды МФТИ», Том 16, №3(63), 2024

- 57я научная конференция МФТИ, 2019, Долгопрудный, Россия

- 59я научная конференция МФТИ, 2021, Долгопрудный, Россия

- международная конференция AI Journey, 2019-2021

Публикации. Основные результаты автора по теме диссертации представлены в виде статей на конференциях, индексируемых Scopus и Web of Science [69, 70, 71], а также периодическом научном журнале, рекомендованом ВАК [72].

Объем и структура работы. Диссертация состоит из введения, 5 глав и заключения. Полный объём диссертации составляет 139 страниц с 27 рисунками и 13 таблицами. Список литературы содержит 71 наименование.

Благодарности. Автор выражает искреннюю благодарность своему научному руководителю, Гусеву Глебу Геннадьевичу, за его неоценимую помощь и поддержку на протяжении всего периода работы над диссертацией. Отдельно

автор выражает признательность своим коллегам, в частности Александру Воробьеву, Людмиле Прохоренковой и Антону Вахрушеву, которые оказали помощь в обсуждении идей и внесли большой вклад в настоящую работу. Невозможно переоценить поддержку родителей автора, Ибрагимовой Ильмиры Рафкатовны и Ибрагимова Ленара Лябибовича.

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

Глава 1. Градиентный бустинг

1.1 Основные концепции

Градиентный бустинг [1] является одним из наиболее влиятельных и широко используемых методов в области машинного обучения, особенно в задачах с табличными данными [2]. Его успех в соревнованиях по анализу данных, таких как Kaggle, и в различных реальных приложениях — от маркетинга [15] до биоинформатики [16] — обусловлен высокой гибкостью, точностью и способностью моделировать сложные зависимости. Чтобы полностью понять механизмы и эффективность градиентного бустинга, необходимо рассмотреть его основные концепции, такие как бустинг, оптимизация функций потерь и построение ансамблей моделей. В данной секции мы рассмотрим основные идеи, которые лежат в основе градиентного бустинга, включая его теоретические основы и практическое применение.

Бустинг как метод ансамблевого обучения.

Бустинг [17] относится к классу методов ансамблевого обучения, в которых несколько слабых моделей (обычно деревья решений) последовательно объединяются для формирования сильного предсказателя. Основная идея бустинга заключается в том, что каждая новая модель пытается скорректировать ошибки предыдущих моделей, таким образом постепенно улучшая общую производительность ансамбля.

Формально, модель бустинга можно описать следующим образом. Дана выборка V = где х{ е ^ — вектор признаков, а у^ е К —

целевая переменная. Задача бустинга состоит в том, чтобы найти оптимальную функцию Е (х), которая аппроксимирует целевую переменную у на всей выборке V. Функция Е(х) представляется в виде суммы М базовых моделей из класса простых моделей Т\

Каждая базовая модель /т(х) обучается на взвешенной выборке Vm = {(хг,Тгт)}-=1, где Тгт — остатки предыдущих моделей:

м

(1.1)

т=1

rim yi Fm-l(xi) • (1.2)

Бустинг появился как решение проблемы высоких смещений (bias), характерных для простых моделей, таких как неглубокие деревья решений. В отличие от других методов ансамблей, таких как бэггинг [18], бустинг акцентирует внимание на обучении каждого последующего предсказателя на ошибках предыдущих моделей. Это достигается путём использования взвешенного обучения, где объекты, которые были неправильно предсказаны предыдущими моделями, получают больший вес при обучении следующей модели. Этот процесс позволяет бустингу справляться с задачами с высокой сложностью и нелинейными зависимостями в данных.

Одним из первых методов бустинга был AdaBoost [19], который использовал экспоненциальную функцию потерь (L(y,F(x)) = exp(-yF(x))) и адаптивное изменение весов наблюдений (wi = exp(-yiF(хг))). Однако метод AdaBoost оказался чувствителен к выбросам и зашумленным данным. Это привело к развитию градиентного бустинга, который использует более гибкие функции потерь и оптимизирует их через градиентный спуск.

Деревья решений в качестве базовых моделей.

Дерево решений [20] — модель, которая представляет собой древовидную структуру, где каждый узел представляет собой некоторое условие, по которому пространство признаков разбивается на два подпространства. В качестве условий, как правило, используются пороги на значениях признаков (например, xj < t). В листьях дерева находятся предсказания модели, которые могут быть как числовыми (регрессия), так и категориальными (классификация). Формально, дерево решений представляет собой функцию:

т

f (x) = J2 fjI(x e Dj), (1.3)

j=l

где fj — значение в листе j, Dj — область, соответствующая листу j.

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

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

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

Градиентный бустинг как метод оптимизации.

Градиентный бустинг, предложенный в работах Фридмана [1], отличается от AdaBoost тем, что использует общее правило оптимизации, основанное на градиентном спуске для минимизации произвольных дифференцируемых функций потерь, осуществляя градиентный спуск в функциональном пространстве.

Пусть Ь — функция потерь, которую необходимо минимизировать. Тогда задача градиентного бустинга на т-ом шаге — обучить модель /т е Т, которая минимизирует следующий функционал (для упрощения мы опускаем возможные регуляризационные слагаемые):

N

Ь(У, Рт-\(Х) + ¡т(х)) = ^ Ь(Уг 5 Е'т-1(хг) + /т (хг))- (1.4)

г=1

Обозначим градиент функции потерь по предсказаниям Ет-1(х) как дг = Ур=рт-1х)Ь(уг,р), а вторую производную функции потерь как Нг = ^2=р> 1(х,)Ь(уг,р). Воспользуемся приближением Тейлора второго порядка для функции потерь и получим упрощенную формулу для оптимизации:

N 1

1 - с2

АЬ = Ь(у, Гт-1(х) + /т(х)) - Ь(у, Рт-1&)) « ^Шт(Хг) + 2/2Х)] -

2

г=1

В случае использования деревьев решений в качестве базовых моделей Т оптимизируемый функционал можно представить в виде:

аь == ™

где учтено, что в каждом листе ] дерева находится некоторое подмножество

г- 7 9г

объектов ^, а оптимальное значение в этом листе равно —^—^ •

Итоговая модель градиентного бустинга Е представляет собой взвешенную сумму базовых моделей:

м

F(x) = J2 afm(x), (1.7)

m=l

где а — шаг обучения (learning rate).

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

— логистическая функция потерь (logloss). Эта гибкость и способность к адаптации под различные функции потерь делает градиентный бустинг мощным инструментом в различных приложениях.

Регуляризация в градиентном бустинге.

Одна из ключевых проблем, с которой сталкивается градиентный бустинг,

— это переобучение, особенно на малых и шумных выборках. Для борьбы с этим используются различные методы регуляризации. Наиболее популярные стратегии включают:

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

2. Шаг обучения (learning rate): шаг обучения контролирует, насколько сильно каждая новая модель корректирует предсказания предыдущей. Маленькие значения шага обучения делают процесс обучения более медленным, но при этом модель становится более устойчивой к переобучению, так как новые деревья вносят меньшие изменения в ансамбль. Это один из важнейших гиперпараметров, влияющих на производительность градиентного бустинга.

3. Стохастический градиентный бустинг [9]: одна из вариаций градиентного бустинга включает стохастические элементы, такие как сэмплирование подвыборок данных или признаков для каждого дерева.

Этот метод, о котором подробнее будет сказано в Секции 1.2, позволяет снизить корреляцию между деревьями и улучшить обобщающую способность модели.

4. Принцип ранней остановки: ещё один важный метод регуляризации — это ранняя остановка обучения, когда алгоритм прекращает добавление новых деревьев, если не наблюдается значительного улучшения на валидационной выборке. Это предотвращает переобучение на тестовых данных и помогает улучшить обобщение. Подробнее про этот метод рассказано в Секции 3.2.

Особенности функции потерь и их роль в градиентном бустинге.

Ключевым элементом градиентного бустинга является функция потерь, которая определяет, как алгоритм оценивает ошибки и корректирует их на каждом этапе обучения. Функция потерь может быть выбрана в зависимости от типа задачи, и от неё зависит, каким образом модель будет корректировать свои предсказания. Например, в задачах бинарной классификации широко используется логистическая функция потерь, которая формирует вероятность отнесения объекта к одному из классов, тогда как в задачах регрессии предпочтение отдаётся среднеквадратичной ошибке, которая минимизирует отклонение предсказаний от истинных значений.

Существует также возможность использовать произвольные дифференцируемые функции потерь, что делает градиентный бустинг весьма гибким инструментом. В частности, для задач с несбалансированными классами, такими как fraud detection или задачи ранжирования в поисковых системах, могут использоваться нестандартные функции потерь, адаптированные под специфику задачи [21].

1.2 Стохастический градиентный бустинг

Стохастический градиентный бустинг (Stochastic Gradient Boosting, SGB) [9] представляет собой модификацию классического градиентного бустинга, целью которой является улучшение обобщающей способности, а также повышение эффективности обучения за счёт использования стохастических методов. В основе этой техники лежит принцип стохастической оптимизации,

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

Основная идея стохастического градиентного бустинга.

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

1. Переобучение (overfitting): обучение на всех доступных данных повышает зависимость моделей между собой, что увеличивает дисперсию предсказаний, что в свою очередь снижает её способность к обобщению на новых данных. Это особенно актуально для небольших выборок или данных с шумом.

2. Высокие вычислительные затраты: обучение на всём наборе данных на каждом этапе может быть чрезвычайно ресурсоёмким, особенно при больших объёмах данных. Это приводит к значительным временным и пространственным затратам.

Стохастический градиентный бустинг решает эти проблемы, вводя элемент случайности на этапе обучения. Основная идея заключается в том, чтобы на каждом шаге обновления модели использовать не весь набор данных, а случайную подвыборку наблюдений или признаков. Это позволяет значительно улучшить её обобщающую способность и снизить вычислительные затраты [12].

Сэмплирование подвыборок данных.

Одним из наиболее распространённых методов в стохастическом градиентном бустинге является случайное сэмплирование подвыборок данных для каждого нового дерева. Этот подход схож с методом бэггинга (bagging), используемым в Random Forest [22], но с ключевым отличием: в градиентном бустинге каждое новое дерево обучается на ошибках предыдущего, а не независимо, как в бэггинге.

Процесс сэмплирования выглядит следующим образом. На каждом этапе обучения выбирается случайная подвыборка данных, составляющая долю s Е [0,1] от общего числа наблюдений. Эта выборка используется для обучения очередного дерева на данном этапе. Например, если s = 0.8, то каждое дерево будет обучаться на 80% случайно выбранных данных.

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

Данный подход успешно используется в популярных библиотеках градиентного бустинга (XGBoost [12], CatBoost [11], LightGBM [10]), в которых параметр subsample позволяет гибко контролировать баланс между точностью и скоростью обучения. Было показано, что использование подвыборок улучшает не только обобщающую способность модели, но и её вычислительную эффективность, особенно при работе с большими данными.

Сэмплирование признаков.

Ещё одна важная стохастическая техника, используемая в градиентном бустинге, заключается в случайном сэмплировании признаков (feature subsampling, random subspace) [23]. Идея заключается в том, чтобы обучать каждое новое дерево не на полном наборе признаков, а на его случайной подвыборке. Такой подход также снижает корреляцию между деревьями и улучшает обобщающую способность модели.

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

Преимущества стохастического градиентного бустинга.

Стохастический градиентный бустинг имеет несколько важных преимуществ по сравнению с классическим градиентным бустингом:

1. Улучшение обобщающей способности: за счёт введения стохастичности модель становится менее подверженной переобучению. Случайное сэмплирование данных и признаков помогает модели избегать чрезмерного подстраивания под конкретные шумные объекты или

нерелевантные признаки. Это приводит к лучшей обобщающей способности, особенно в задачах с небольшими или зашумленными данными.

2. Снижение вычислительных затрат: стохастическое сэмплирование данных и признаков значительно уменьшает количество вычислений на каждом шаге обучения. Поскольку не все данные и/или признаки используются для построения каждого дерева, время обучения сокращается, что особенно важно при работе с большими наборами данных.

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

4. Гибкость настройки: стохастический градиентный бустинг предлагает множество параметров настройки, таких как размер подвыборки данных и признаков. Это позволяет пользователю гибко управлять компромиссом между точностью модели и её вычислительной эффективностью. Например, небольшие подвыборки данных ускоряют обучение, но могут ухудшить точность предсказаний, тогда как использование всех данных на каждом шаге увеличивает точность, но замедляет процесс обучения.

Ограничения стохастического градиентного бустинга.

Несмотря на многочисленные преимущества, стохастический градиентный бустинг имеет и свои ограничения:

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

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

именно факторы наиболее сильно влияют на предсказания, может стать менее очевидным.

1.3 Адаптивные методы обучения градиентного бустинга

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

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

1. Адаптивный выбор шага обучения (learning rate): корректировка шага обучения для каждого нового дерева или на каждой итерации. Малый шаг позволяет модели двигаться медленно и осторожно, предотвращая переобучение, тогда как большой шаг ускоряет обучение, но может привести к нестабильности. Адаптивные методы позволяют динамически уменьшать шаг обучения на основе наблюдаемых ошибок на валидационных данных.

2. Адаптивное управление количеством итераций: ранняя остановка (early stopping)— один из распространённых методов адаптивного обучения, при котором обучение модели прекращается, когда дальнейшее увеличение числа деревьев не приводит к улучшению на валидационной выборке. Это позволяет предотвратить переобучение, не требуя явного контроля числа деревьев.

3. Адаптивный выбор данных и признаков: стохастические методы, такие как GOSS (Gradient-Based One-Side Sampling) в LightGBM [10], реализуют адаптивные стратегии для выбора подвыборок данных на каждой итерации в зависимости от их важности для минимизации функции потерь. Эти методы снижают вычислительные затраты, сохраняя высокое качество модели.

4. Адаптивный выбор гиперпараметров отдельных моделей: адаптивные методы могут также применяться для выбора свойств деревьев решений, таких как глубина, количество листьев и минимальное количество объектов в листе. В отличие от классического алгоритма, в котором эти параметры фиксированы, адаптивные методы могут динамически корректировать их в зависимости от текущего состояния модели.

Адаптивные стратегии ранней остановки.

Метод ранней остановки (early stopping) — это одна из ключевых адаптивных стратегий, широко применяемая в градиентном бустинге для предотвращения переобучения. Идея заключается в том, чтобы прекратить обучение модели, когда ошибка на валидационной выборке перестаёт снижаться, несмотря на продолжающиеся улучшения на тренировочной выборке. Это позволяет избежать ситуации, когда модель чрезмерно подстраивается под тренировочные данные, теряя способность обобщать новые данные.

Процесс ранней остановки может быть формализован следующим образом: если ошибка на валидационной выборке не уменьшается в течение заданного числа итераций k ("tolerance"), обучение прекращается. Это даёт модели возможность обучаться до тех пор, пока есть улучшения, избегая необходимости фиксировать точное число итераций заранее.

В то же время существуют работы, которые предлагают более сложные методы ранней остановки, основанные на анализе сложности модели. Как правило, такие методы не требуют наличия отдельной валидационной выборки и опираются на такие показатели как AIC (Akaike Information Criterion) или BIC (Bayesian Information Criterion) [24], размерность Вапника-Червоненкиса (VC dimension) [25], сложность Радамахера [26] и другие [27]. С одной стороны, отсутствие необходимости в валидационной выборке позволяет модели обучаться на всех доступных данных, что может быть особенно полезно в случае малых выборок. С другой стороны, подобные методы не снискали популярности на

практике, так как получаемые оценки сложности модели довольно грубые, так как не зависят от распределения данных (distribution-agnostic).

Ранняя остановка является мощной регуляризирующей техникой, аналогичной методам pruning (обрезки) в других алгоритмах машинного обучения. Обрезка [28] часто относится к техникам компрессии моделей, направленным на уменьшение их размера и вычислительной сложности, что улучшает эффективность хранения и вывода модели. В случае ансамблей моделей, таких как градиентный бустинг, обрезка становится особенно важной, поскольку они часто содержат большое количество базовых моделей (деревьев решений). Это делает их потенциально избыточными, что открывает возможности для адаптивного сокращения их числа без потери качества.

В одной из ранних работ по данной теме [29] исследователи сравнивали пять различных методов обрезки, применённых к бустинговым алгоритмам. Было показано, что обрезка, даже несмотря на уменьшение количества моделей в ансамбле, может поддерживать или даже улучшать исходное качество модели. Это связано с тем, что многие деревья в ансамбле могут дублировать информацию о данных, и их удаление помогает избавиться от избыточности, что улучшает общую обобщающую способность модели.

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

Особый интерес вызывает поэлементный прунинг [31]. В этих методах каждая отдельная модель в ансамбле может быть остановлена в зависимости от конкретного объекта данных. Это позволяет уменьшить вычислительные затраты на предсказания, особенно когда модели уже близки к оптимальным предсказаниям для определённых объектов, что снижает необходимость в дальнейшем усложнении модели на этих примерах.

Применительно к градиентному бустингу, ранняя остановка рассматривается как важная регуляризирующая техника. Она основана на кросс-валидации и может значительно улучшить качество конечного ансамбля за счёт устранения недостатков, связанных с жадным обучением, присущим бустингу. Как показано в ряде исследований [28], ранняя остановка способна действовать как своего рода обрезка, удаляя "избыточные"деревья, которые не только не улучшают, но и могут ухудшить качество модели, если обучение продолжается слишком долго.

Другим важным аспектом обрезки в ансамблевых методах является устранение дублирования информации, что часто наблюдается в моделях с большим числом базовых предсказателей. Исследования [32] показали, что подобные дублирующие предсказатели могут быть исключены без ущерба для качества модели. Это объясняется тем, что деревья, обученные на тех же или схожих данных, часто выдают избыточные предсказания, не добавляя новой информации, и таким образом могут быть удалены из последовательности моделей. В результате ансамбль становится компактнее, менее подвержен переобучению и быстрее работает.

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

Список литературы диссертационного исследования кандидат наук Ибрагимов Булат Ленарович, 2024 год

Список литературы

[1] Jerome H Friedman. — «Greedy function approximation: a gradient boosting machine». — В: Annals of statistics (2001), с. 1189—1232.

[2] Byron P Roe и др. — «Boosted decision trees as an alternative to artificial neural networks for particle identification». — В: Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 543.2 (2005), с. 577—584.

[3] Christopher JC Burges. — «From ranknet to lambdarank to lambdamart: An overview». — В: Learning 11.23-581 (2010), с. 81.

[4] Rich Caruana и Alexandru Niculescu-Mizil. — «An empirical comparison of supervised learning algorithms». — В: Proceedings of the 23rd international conference on Machine learning. — ACM. 2006, — С. 161—168.

[5] Matthew Richardson, Ewa Dominowska и Robert Ragno. — «Predicting clicks: estimating the click-through rate for new ads». — В: Proceedings of the 16th international conference on World Wide Web. — ACM. 2007, — С. 521—530.

[6] Qiang Wu и др. — «Adapting boosting for information retrieval measures». — В: Information Retrieval 13.3 (2010), с. 254—270.

[7] Yanru Zhang и Ali Haghani. — «A gradient boosting method to improve travel time prediction». — В: Transportation Research Part C: Emerging Technologies 58 (2015), с. 308—324.

[8] David Mease и Abraham Wyner. — «Evidence contrary to the statistical view of boosting». — В: Journal of Machine Learning Research 9.Feb (2008), с. 131—156.

[9] Jerome H Friedman. — «Stochastic gradient boosting». — В: Computational Statistics & Data Analysis 38.4 (2002), с. 367—378.

[10] Guolin Ke и др. — «LightGBM: A highly efficient gradient boosting decision tree». — В: Advances in Neural Information Processing Systems. — 2017, — С. 3149—3157.

[11] Liudmila Prokhorenkova и др. — «CatBoost: unbiased boosting with categorical features». — В: Advances in neural information processing systems 31 (2018), с. 6638-6648.

[12] Tianqi Chen h Carlos Guestrin. — «Xgboost: A scalable tree boosting system». — B: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. — ACM. 2016, — C. 785—794.

[13] Leonid Iosipoi h Anton Vakhrushev. — «Sketchboost: Fast gradient boosted decision tree for multioutput problems». — B: Advances in Neural Information Processing Systems 35 (2022), c. 25422—25435.

[14] Pierre Gutierrez h Jean-Yves Gerardy. — «Causal inference and uplift modelling: A review of the literature». — B: International conference on predictive applications and APIs. — PMLR. 2017, — C. 1—13.

[15] Ilya Trofimov, Anna Kornetova h Valery Topinskiy. — «Using boosted trees for click-through rate prediction for sponsored search». — B: In Proceedings of the Sixth International Workshop on Data Mining for Online Advertising and Internet Economy. — 2012, — C. 1—6.

[16] Lei Deng h gp. — «PDRLGB: precise DNA-binding residue prediction using a light gradient boosting machine». — B: BMC bioinformatics 19.19 (2018), c. 135—145.

[17] Robert E Schapire. — «The strength of weak learnability». — B: Machine learning 5 (1990), c. 197—227.

[18] Leo Breiman. — «Bagging predictors». — B: Machine learning 24 (1996), c. 123—140.

[19] Yoav Freund, Robert E Schapire h gp. — «Experiments with a new boosting algorithm». — B: icml. — T. 96. — Citeseer. 1996, — C. 148—156.

[20] Anthony J Myles h gp. — «An introduction to decision tree modeling». — B: Journal of Chemometrics: A Journal of the Chemometrics Society 18.6 (2004), c. 275—285.

[21] Yong-Seok Jeon, Dong-Hyuk Yang h Dong-Joon Lim. — «FlexBoost: A flexible boosting algorithm with adaptive loss functions». — B: IEEE Access 7 (2019), c. 125054—125061.

[22] Leo Breiman. — «Random forests». — B: Machine learning 45 (2001), c. 5—32.

[23] Tin Kam Ho. — «The random subspace method for constructing decision forests». — B: IEEE transactions on pattern analysis and machine intelligence 20.8 (1998), c. 832—844.

[24] Yuan-Chin Ivan Chang, Yufen Huang h Yu-Pai Huang. — «Early stopping in L2Boosting». — B: Computational Statistics & Data Analysis 54.10 (2010), c. 2203—2213.

[25] Yoav Freund h Robert E Schapire. — «A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting». — B: Journal of Computer and System Sciences 55.1 (1997), c. 119—139.

[26] Corinna Cortes, Mehryar Mohri h Dmitry Storcheus. — «Regularized Gradient Boosting». — B: Advances in Neural Information Processing Systems. — nog peg. H. Wallach h gp. — T. 32. — Curran Associates, Inc., 2019.

[27] Yuan Yao, Lorenzo Rosasco h Andrea Caponnetto. — «On Early Stopping in Gradient Descent Learning». — B: Constructive Approximation 26 (aBr. 2007), c. 289—315.

[28] Wei Fan h gp. — «Pruning and dynamic scheduling of cost-sensitive ensembles». — B: AAAI/IAAI. — 2002, — C. 146—151.

[29] Dragos D Margineantu h Thomas G Dietterich. — «Pruning adaptive boosting». — B: ICML. — T. 97. — Citeseer. 1997, — C. 211—218.

[30] Victor Soto h gp. — «A double pruning scheme for boosting ensembles». — B: IEEE transactions on cybernetics 44.12 (2014), c. 2682—2695.

[31] Dayvid VR Oliveira, George DC Cavalcanti h Robert Sabourin. — «Online pruning of base classifiers for dynamic ensemble selection». — B: Pattern Recognition 72 (2017), c. 44—58.

[32] George DC Cavalcanti h gp. — «Combining diversity measures for ensemble pruning». — B: Pattern Recognition Letters 74 (2016), c. 38—45.

[33] Zhi-Hua Zhou h Wei Tang. — «Selective ensemble of decision trees». — B: International workshop on rough sets, fuzzy sets, data mining, and granular-soft computing. — Springer. 2003, — C. 476—483.

[34] Yi Zhang h gp. — «Ensemble Pruning Via Semi-definite Programming.» — B: Journal of machine learning research 7.7 (2006), c. 1315—1338.

[35] Xiaoming Liu h Ting Yu. — «Gradient feature selection for online boosting». — B: 2007 IEEE 11th International Conference on Computer Vision. — IEEE. 2007, — C. 1—8.

[36] Berent Ânund Str0mnes Lunde и Tore Selland Kleppe. — «agtboost: Adaptive and automatic gradient tree boosting computations». — В: arXiv preprint arXiv:2008.12625 (28 авг 2020).

[37] Clément Dombry и Youssef Esstafa. — «Behavior of linear L2-boosting algorithms in the vanishing learning rate asymptotic». — В: arXiv preprint arXiv:2012.14657 (29 дек 2020).

[38] Peter Btihlmann и Torsten Hothorn. — «Boosting algorithms: Regularization, prediction and model fitting». — В: Statistical Science 22.4 (2007).

[39] Takafumi Kanamori и др. — «Robust loss functions for boosting». — В: Neural computation 19.8 (2007), с. 2183—2244.

[40] Jiaqi Luo, Yuan Yuan и Shixin Xu. — «Improving GBDT Performance on Imbalanced Datasets: An Empirical Study of Class-Balanced Loss Functions». — В: arXiv preprint arXiv:2407.14381 (19 июля 2024).

[41] Y-S Shih. — «Families of splitting criteria for classification trees». — В: Statistics and Computing 9.4 (1999), с. 309—315.

[42] Daniel G Horvitz и Donovan J Thompson. — «A generalization of sampling without replacement from a finite universe». — В: Journal of the American statistical Association 47.260 (1952), с. 663—685.

[43] Hosam M Mahmoud, Reza Modarres и Robert T Smythe. — «Analysis of quickselect: An algorithm for order statistics». — В: RAIRO-Theoretical Informatics and Applications 29.4 (1995), с. 255—276.

[44] Pat Langley и Stephanie Sage. — «Oblivious decision trees and abstract cases». — В: Working notes oftheAAAI-94 workshop on case-based reasoning. — Seattle, WA. 1994, — С. 113—117.

[45] Sarang Narkhede. — «Understanding auc-roc curve». — В: Towards data science 26.1 (2018), с. 220—227.

[46] Mervyn Stone. — «Cross-validation: A review». — В: Statistics: A Journal of Theoretical and Applied Statistics 9.1 (1978), с. 127—139.

[47] John A Hartigan и Manchek A Wong. — «Algorithm AS 136: A k-means clustering algorithm». — В: Journal of the royal statistical society. series c (applied statistics) 28.1 (1979), с. 100—108.

[48] Todd K Moon. — «The expectation-maximization algorithm». — В: IEEE Signal processing magazine 13.6 (1996), с. 47—60.

[49] Daniel Mtillner. — «Modern hierarchical, agglomerative clustering algorithms». — В: arXivpreprint arXiv:1109.2378 (12 сен 2011).

[50] Toby Sharp. — «Implementing decision trees and forests on a GPU». — В: Computer Vision-ECCV2008:10th European Conference on Computer Vision, Marseille, France, October 12-18, 2008, Proceedings, Part IV10. — Springer. 2008, — С. 595—608.

[51] James Bergstra и др. — «Hyperopt: a python library for model selection and hyperparameter optimization». — В: Computational Science & Discovery 8.1 (2015), с. 014008.

[52] Leo Breiman. — «Out-of-bag estimation». — В: (1996). — URL: https://api. semanticscholar.org/CorpusID:17166335.

[53] James Heckman. — «Sample selection bias as a specification error». — В: Applied Econometrics 31.3 (2013), с. 129—137.

[54] Behram Hansotia и Brad Rukstales. — «Incremental value modeling». — В: Journal of Interactive Marketing - J INTERACT MARK 16 (июнь 2002), с. 35—46.

[55] Xiaogang Su и др. — «Subgroup analysis via recursive partitioning.» — В: Journal of Machine Learning Research 10.2 (2009), с. 141—158.

[56] Xiaogang Su и др. — «Facilitating Score and Causal Inference Trees for Large Observational Data». — В: Journal of Machine Learning Research 13 (окт. 2012), с. 2955—2994.

[57] Stefan Wager и Susan Athey. — «Estimation and inference of heterogeneous treatment effects using random forests». — В: Journal of the American Statistical Association 113.523 (2018), с. 1228—1242.

[58] Soren R Ktinzel и др. — «Metalearners for estimating heterogeneous treatment effects using machine learning». — В: Proceedings of the national academy of sciences 116.10 (2019), с. 4156—4165.

[59] Susan Athey и Guido W Imbens. — «Machine learning methods for estimating heterogeneous causal effects». — В: stat 1050.5 (2015), с. 1—26.

[60] Xinkun Nie h Stefan Wager. — «Quasi-oracle estimation of heterogeneous treatment effects». — B: Biometrika 108.2 (2021), c. 299—319.

[61] Edward H Kennedy. — «Towards optimal doubly robust estimation of heterogeneous causal effects». — B: Electronic Journal of Statistics 17.2 (2023), c. 3008-3049.

[62] Paul R Rosenbaum h Donald B Rubin. — «The central role of the propensity score in observational studies for causal effects». — B: Biometrika 70.1 (1983), c. 41—55.

[63] Floris Devriendt h gp. — «Learning to rank for uplift modeling». — B: IEEE Transactions on Knowledge and Data Engineering 34.10 (2020), c. 4888—4904.

[64] Kailiang Zhong h gp. — «Descn: Deep entire space cross networks for individual treatment effect estimation». — B: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. — 2022, — C. 4612—4620.

[65] Claudia Shi, David Blei h Victor Veitch. — «Adapting neural networks for the estimation of treatment effects». — B: Advances in neural information processing systems 32 (2019).

[66] Benolt Frenay h Michel Verleysen. — «Classification in the presence of label noise: a survey». — B: IEEE transactions on neural networks and learning systems 25.5 (2013), c. 845—869.

[67] Shahin Jabbari, Robert C Holte h Sandra Zilles. — «Pac-learning with general class noise models». — B: KI 2012: Advances in Artificial Intelligence: 35th Annual German Conference on AI, Saarbrücken, Germany, September 24-27, 2012. Proceedings 35. — Springer. 2012, — C. 73—84.

[68] Yoshihiko Ozaki h gp. — «Multiobjective tree-structured Parzen estimator». — B: Journal of Artificial Intelligence Research 73 (2022), c. 1209—1250.

Публикации автора по теме диссертации

[69] Bulat Ibragimov и Gleb Gusev. — «Minimal variance sampling in stochastic gradient boosting». — В: Advances in Neural Information Processing Systems 32 (2019).

[70] Bulat Ibragimov и Gleb Gusev. — «Learn Together Stop Apart: An Inclusive Approach to Ensemble Pruning». — В: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. — 2024, — С. 1166—1176.

[71] Bulat Ibragimov и Anton Vakhrushev. — «Uplift Modelling via Gradient Boosting». — В: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. — 2024, — С. 1177—1187.

[72] Булат Ибрагимов и Глеб Гусев. — «Оптимизация стохастического градиентного бустинга с помощью out-of-sample оценок качества». — В: Труды МФТИ 16.3(63) (2024), с. 49—56.

Список рисунков

2.1 Adult: величина logloss в зависимости от доли сэмлирования для алгоритмов GB, SGB, GOSS и MVS....................47

2.2 Amazon: величина logloss в зависимости от доли сэмлирования для алгоритмов GB, SGB, GOSS и MVS....................47

2.3 Click: величина logloss в зависимости от доли сэмлирования для алгоритмов GB, SGB, GOSS и MVS....................48

2.4 Kick: величина logloss в зависимости от доли сэмлирования для алгоритмов GB, SGB, GOSS и MVS....................48

2.5 KDD Churn: величина logloss в зависимости от доли сэмлирования

для алгоритмов GB, SGB, GOSS и MVS..................49

2.6 KDD Internet: величина logloss в зависимости от доли сэмлирования

для алгоритмов GB, SGB, GOSS и MVS..................49

2.7 KDD Upsel: величина logloss в зависимости от доли сэмлирования

для алгоритмов GB, SGB, GOSS и MVS..................50

3.1 Кривые обучения для различных кластеров при обучении

градиентного бустинга............................56

3.2 Примеры обучающих кривых для градиентного бустинга на тестовой выборке. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение логарифмической функции потерь. Каждая линия представляет собой обучающую кривую для отдельного объекта, иллюстрируя, как меняется функция потерь в

зависимости от числа итераций для отдельных данных..........60

3.3 Распределение относительного сдвига лучших предсказаний итераций. Горизонтальная ось представляет значения долей, а вертикальная ось — частоту этих значений.................61

3.4 Adult: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val) и фактические лучшие (test) моменты остановки.............66

3.5 Набор данных Marketing: сравнение величины ошибки на валидации в зависимости от числа кластеров для наивного подхода и подхода

предлагаемого в Секции 3.8.........................74

3.6 Набор данных Kick: сравнение величины ошибки на валидации в зависимости от числа кластеров для наивного подхода и подхода предлагаемого в Секции 3.8 ......................... 74

3.7 Adult: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............77

3.8 Amazon: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............77

3.9 Click: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............78

3.10 Default: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............78

3.11 KDD Churn: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............79

3.12 KDD Internet: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............79

3.13 KDD Upsel: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............80

3.14 Kick: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............80

3.15 Marketing: Результаты кластеризации полученные с помощью решающего дерева, обученного с использованием целевой функции из Уравнения 3.10. Горизонтальная ось представляет количество итераций бустинга, а вертикальная ось — значение logloss. Каждая линия показывает значение logloss для различных кластеров одного и того же набора данных. Жирные точки указывают на оцененные (val)

и фактические лучшие (test) моменты остановки.............81

4.1 Оценка качества ансамбля (logloss) и отдельных деревьев (В2,

косинусное сходство, юс-аис) в зависимости от итерации. Маркером

на первом графике выделена точка переобучения.............86

5.1 Визуализация двуступенчатого алгоритма uplift моделирования.....103

5.2 Визуализация синтетического набора данных, созданного для анализа компонент модели. Верхние диаграмы рассеяния показывают распределение исходов для контрольной группы и группы воздействия. Диаграмма рассеяния снизу показывает

распределение величины искомого uplift эффекта. Гистограмма демонстрирует распределение величин uplift в наборе данных......109

5.3 Предсказания компонент модели uplift для синтетического набора данных. Каждая точка на диаграмме слева отвечает за предсказание uplift на отдельном примере моделями GBDT Outcome и GBDT Uplift. Гистограмма справа показывает распределение предскааний компонент GBDT Outcome и GBDT Uplift.................111

5.4 Зависимость производительности модели (AUUC и MSE) от весов компонент GBDT Outcome и GBDT Uplift.................118

Список таблиц

1 Описания наборов данных для сравнения алгоритмов стохастического градиентного бустинга..................42

2 Результаты экспериментов с различными реализациями стохастического градиентного бустинга: относительное изменение 0-1 loss для SGB, GOSS, MVS по сравнению с классическим алгоритмом градиентного бустинга....................43

3 Зависимость изменения качества (по logloss) относительно классической реализации градиентного бустинга в зависимости от

доли сэмплирования для алгоритмов SGB, GOSS и MVS........45

4 Относительное ускорение обучения относительно бейзлайна для различных алгоритмов стохастического градиентного бустинга: SGB, GOSS и MVS.................................46

5 Средние значения 0-1 loss / logloss для реализации адаптивной

ранней остановки на базе LightGBM....................81

6 Средние значения 0-1 loss / logloss для реализации адаптивной

ранней остановки на базе CatBoost.....................82

7 Измерения временной и пространственной сложности классического алгоритма ранней остановки на основе кросс-валидации и алгоритма DSP.......................................82

8 Результаты сравнения качества моделей (logloss) при различных долях сэмплирования для классического SGB и предложенного метода на основе OOS. Жирным цветом выделены результаты со статзначимыми отличиями (p-value < 0.05) согласно парному тесту Уилкоксона..................................92

9 Результаты сравнения компонент двухэтапной модели на синтетическом наборе данных. Представлены значения качества предсказаний по метрике R2, а также общее число разбиений деревьями ансамбля с детализацией по признакам.............110

10 Обобщенные результаты сравнения качества работы uplift моделей

по AUUC для синтетического набора данных...............114

11 Обобщенные результаты сравнения качества работы uplift моделей

по MSE для синтетического набора данных................115

12 Обобщенные результаты сравнения качества работы uplift моделей

по AUUC для реальных наборов данных..................115

13 Обобщенные результаты сравнения качества работы uplift моделей по всем наборам данных. Представленные метрики: средний ранг (позиция модели в сортированном списке моделей по качеству

работы), среднее изменение в % относительно лидирующего алгоритма. 117