Цель состоит в том, чтобы дать подробное представление о реализации алгоритма XGBoost с минимальными математическими расчетами
XGBoost — один из наиболее часто используемых вариантов Gradient Boosting Machines, основанный на методе усиления ансамбля. Он был разработан Tianqi Chen и выпущен в 2014 году.
Многие начинающие аспиранты в области науки о данных недостаточно хорошо понимают реализацию XGBoost, чтобы использовать ее эффективно. Я постараюсь дать подробное объяснение того, как работает этот алгоритм.
Разница между бэггингом и бустингом
Фундаментальное различие между бэггингом (например, Random Forest) и методом бустинга заключается в том, что при бустинге на каждом этапе мы прогнозируем псевдоостатки (градиент потерь) вместо целевых значений (y).
В двух словах, на каждом этапе дерево строится жадно, остаток (разница целевого и прогнозируемого значения) вычисляется и передается следующему дереву как новое целевое значение, этот процесс повторяется ни разу. . итераций и окончательного прогноза является суммой всех прогнозируемых значений всех деревьев. Для лучшего понимания см. пункт № 4 в разделе «Важные аспекты, которые следует помнить».
Целевая функция
XGBoost пытается оптимизировать приведенную ниже целевую функцию, которая представляет собой сумму потери при обучении и регуляризации.
l — функция потерь, такая как среднеквадратическая ошибка (MSE) для регрессии или логит-потери для классификации, K — общее количество деревьев, n обозначает количество строк в данных, Ωявляется термином регуляризации, а f это дерево (ТЕЛЕГА).
Здесь потери при обучении оптимизируются для получения хороших прогностических моделей, а компромисс между смещением и дисперсией достигается с помощью регуляризации. Термин регуляризации определяет сложность модели, что помогает нам избежать переобучения и получить более простую модель.
Теперь, когда мы знаем общий подход к алгоритму, давайте углубимся в детали того, как строится дерево и как обрабатываются отсутствующие значения/разреженные данные.
Сначала я подытожу построение дерева, чтобы можно было ознакомиться с процессом в целом, а затем мы углубимся в детали некоторых его частей.
Строительство дерева
- Инициализируйте предсказанный y_hat некоторой константой, такой как среднее или медиана целевого значения (y)
- Начните строить дерево с глубины 0, т.е. с корневого узла
- Теперь найдите узел с лучшим разделением. Для этого из всех переменных/функций-предикторов берите каждую функцию за раз. Псевдокод, как показано ниже:
Для объектов от m=1 до Mвнутри этого объекта отсортируйте значения объекта. Попробуйте найти наилучшее разделение, используя линейное сканирование слева направо с макс. выигрыш/счет:
В приведенной выше скобке 3 компонента: L – оценка нового разделения на левом дочернем элементе, R – оценка нового разделения на правом дочернем элементе, третий компонент – оценка, если разделение не выполняется. выполненный.
Выберите эту функцию и ее точку останова, где указанный выше Прирост был максимальным. Это известно как точный жадный алгоритм для разделения
gⱼₖ = Частная производная первого порядка экземпляра 'k' в листе j,hⱼₖ = Частная производная второго порядка экземпляра 'k' в листе j
4. После того, как все разделение завершено, определяется окончательная структура дерева, которая минимизирует новую цель, указанную ниже:
где T= нет. листьев в дереве, j=номер узла, λ = параметр L2-регуляризации для листа, γ = еще больше снижает сложность дерева и помогает в сокращении (см. пункт № 2 в разделе 'Важные аспекты, которые следует помнить').
5. После того, как дерево выращено до максимальной глубины и обрезано, добавьте прогнозируемый псевдоостаток текущей итерации к прогнозам предыдущей итерации, как указано в формуле Рис. 1.
Важные аспекты, о которых следует помнить
- Параметр усадки/размера шага (η)
Этот параметр масштабирует текущий прогноз дерева и резервирует шанс для будущих раундов улучшить прогнозы. Это помогает предотвратить переоснащение. η обратно пропорционально количеству итераций. Понизить η, больше нет. итераций требуется для построения оптимальной модели.
2. Стоимость сложности (γ)
Если вы посмотрите на разделенную оценку (рис. 3), которая равна [левая оценка + правая оценка + оценка без разделения] - γ. Если после разделения компонент скобок ниже γ, то общая оценка будет отрицательный и разделения не произойдет. Это предварительная остановка. Однако разделение будет продолжаться до тех пор, пока дерево не будет построено до максимальной глубины, после чего начнется пост-обрезка. Это делается потому, что разделение на более глубоком уровне (внизу) может иметь положительное усиление, а разделение на верхнем уровне может иметь отрицательное усиление, поэтому общее усиление может быть положительным. Следовательно, постобрезка сохранит листья и даст возможность получить более чистое расщепление.
3. Когда функция потерь в регрессии составляет 1/2 квадрата ошибки, тогда значением листа является среднее значение остатков экземпляров в этом листе.
4. Аналогия с гольфом, чтобы лучше понять подход повышения градиента
Подход Gradient Boosting определяется как Fₙ = Fₙ₋₁ + η.Δₙ
Fₙ — это окончательное прогнозируемое целевое значение на итерации 'n', Fₙ₋₁ — это прогнозируемое значение на итерации 'n-1', Δₙ прогнозируется псевдоостаток на итерации 'n', а η — параметр усадки.
Сделайте паузу и посмотрите на диаграмму выше. Рассмотрим η=1, на каждом этапе GBM прогнозирует y - Fₙ₋₁ (остаток или градиент потерь), который представляет собой разницу в расстоянии от шеста до мяча для гольфа. Таким образом, на каждой итерации GBM пытается предсказать это расстояние, что похоже на игрока в гольф, стремящегося к полюсу перед каждым ударом. А иногда мяч может даже пересечь полюс (например, Δ₂), поэтому при использовании градиентного спуска при расчете Δ применяется правильный знак. Поэтому рекомендуется использовать меньшее η, чтобы не пропустить минимумы потерь или полюс.
Обработка отсутствующего значения
Отсутствующие значения/разреженные данные могут быть легко обработаны XGBoost. Для отсутствующих значений или разреженных данных (One Hot Encoding) XGBoost использует алгоритм разделения с учетом разреженности. Направление по умолчанию устанавливается для каждого экземпляра в узле, который содержит пропущенное значение. Следовательно, время вычислений значительно сокращается, когда для категориальных признаков используется разреженная матрица. Ниже приведены общие шаги алгоритма:
а) Возьмите набор экземпляров (строк) текущего узла и рассмотрите только те экземпляры (строки), которые содержат непропущенные значения.
b) Для каждой функции, взятой по одной, рассчитайте усиление в левом и правом направлениях разделения.
c) Направления разделения и по умолчанию имеют максимальное усиление.
Эпилог
Я изо всех сил старался подробно представить этот красивый алгоритм GBM, предоставляя более мелкие детали по мере необходимости, сохраняя простой язык и используя минимум математики. Большинство современных соревнований по машинному обучению выигрываются с использованием XGBoost. Понимание любого алгоритма в деталях дает вам дополнительные возможности для его правильной реализации, такой как настройка гиперпараметров, вменение пропущенных значений и т. д.
Ссылки
