Эта статья подготовлена технической командой OPPO Internet, укажите автора для перепечатки. В то же время приглашаем обратить внимание на нашу общедоступную учетную запись: OPPO_tech, чтобы поделиться с вами передовыми интернет-технологиями и деятельностью OPPO.
Gradient Boosting — это метод решения задач классификации и регрессии в машинном обучении. Как и другие члены семейства Boosting, его прогностическая модель также состоит из ряда слабых прогностических моделей.
В последние годы XGBoost, LightGBM и CatBoost блестяще показали себя в таких соревнованиях, как Kaggle, что полностью доказывает практичность технологии Gradient Boosting, поэтому нам необходимо попытаться использовать эту технологию при производстве тегов интересов пользователей.
В этой статье исследуется текущий основной алгоритм повышения градиента и представлена технология со следующих аспектов: В первом разделе сначала представлены знания о повышении, а затем представлена структура GBM. В разделах 2, 3 и 4 представлены GBDT, XGBoost и LightGBM соответственно. В разделе 5 представлен алгоритм CatBoost с помощью функций классификации. Последний раздел содержит краткое изложение полного текста.
1. Gradient Boosting Machine
1.1 Boosting
Чтобы произвести впечатление на Boosting, в этой статье мы сравним Bagging для ознакомления. Как показано на рисунке 1 [1], и бэггинг, и бустинг относятся к ансамблевому обучению, но каждый учащийся бэггинга обучается параллельно, в то время как бустинг выполняется последовательно, то есть учащийся обрабатывает результат предыдущего, и этот результат равен часто отличающееся от исходного распределения выборки непостоянно.
Рисунок 1. Бэггинг против бустинга
Возьмем в качестве примера AdaBoost, как показано на рисунке 2 [2]: D1 неправильно классифицирует 3 положительных образца, D2 увеличивает вес неправильно классифицированных образцов во время обучения, а D3 увеличивает вес неправильно классифицированных отрицательных образцов из D2 для повторного обучения. и, наконец, средневзвешенное значение трех базовых учеников (каждый базовый ученик также имеет вес), чтобы получить модель с хорошей способностью к различению.
Рисунок 2. AdaBoost: Box1~Box3 — это 3 учащегося, выполняемые последовательно, D1~D3 — границы решений каждого блока, «+-» представляет положительные и отрицательные образцы, Box4 объединяет границы решений базового учащегося и может разделять положительные и отрицательные значения. отрицательные образцы
1.2 Gradient Descent
Gradient Boosting аналогичен AdaBoost в том, что каждый базовый учащийся изучается последовательно, но особенность первого заключается в том, что он использует градиенты, то есть связывает базовых учащихся и градиенты. Прежде чем представить GBM, давайте рассмотрим алгоритм градиентного спуска в численной оптимизации:
Предполагать
где P — параметр, x — выборка,
делать
Наименьшее значение, но эта формула часто неразрешима, поэтому идея численной оптимизации заключается в использовании нескольких итераций для аппроксимации оптимального решения, чтобы
, нам просто нужно найти на каждой итерации
Вот и все.
Конкретный метод заключается в том, чтобы задать начальный параметр
, затем поставьте
Введите формулу, а затем рассчитайте градиент, обновите его с помощью информации о градиенте.
получить
и так далее: пусть градиент равен g, m представляет собой m-ю итерацию, тогда формула (1):
На рис. 3 наглядно показан принцип работы алгоритма с одномерными параметрами.
Рис. 3. Метод градиентного спуска: w обновляется в направлении отрицательного градиента
Возможно, вы заметили сходство между численной оптимизацией и бустингом:
-
аддитивная модель
-
Последовательное выполнение, то есть текущая сессия должна основываться на результатах предыдущей сессии
-
Каждая итерация численной оптимизации накапливается для получения оптимальных параметров, а каждая итерация бустинга накапливается для получения оптимальной функции
Поскольку это так похоже, то напрямую замените пространство параметров пространством функций, а затем напрямую используйте градиентный спуск для решения проблемы, не получится ли оптимальная модельная функция? Да, идея GBM такова, но в градиенте нужно сделать больше, и GBM будет подробно представлен ниже.
1.3 Gradient Boosting Machine
Как упоминалось ранее, пространство функций используется для замены пространства параметров, то есть функция F(x) используется для замены параметра P в формуле (1), как показано в формуле (2):
Вроде бы все логично, и модель готова к выходу, но не забывайте, что градиент здесь и есть настоящий градиент, то есть градиент, который нужно знать полный набор можно рассчитать.В реальности мы часто не может получить полный набор или даже знать распределение полного набора, так что возьми. Способность модели к обобщению, полученная прямым применением уравнения (2) с ограниченными выборками, вызывает беспокойство.
К счастью, Фридман предложил структуру Gradient Boosting Machine: в каждой итерации базовый обучаемый обучается на ограниченных выборках, чтобы соответствовать реальному градиенту, что хорошо решает проблему обобщения, как показано на рисунке 4 [3].
Рисунок 4. Общая схема Gradient Boosting Machine. L представляет функцию потерь, F представляет параметр модели, y представляет градиент выборки, hx представляет собой базовый обучаемый, α представляет параметр hx, а ρ представляет оптимальный параметр во время линейного поиска.
На рисунке 4 представлена только общая структура.Разные функции потерь и разные базовые обучающиеся могут выводить разные алгоритмы.Например, если выбрана квадратичная функция потерь, можно получить формулу на рисунке 5: Градиент эквивалентен прогнозируемому значению текущая модель и разница между истинными значениями (также называемыми остатками) и β=ρ .
Рисунок 5 GBM при квадратичной функции потерь
2. GBDT
Когда базовым учащимся в GBM является дерево регрессии [4] (подогнанный градиент следует рассматривать как непрерывное значение, поэтому используется дерево регрессии), это классический алгоритм GBDT.
Для преобразования формулы и других подробностей, пожалуйста, обратитесь к Справке 4. В этой статье мы не будем вдаваться в подробности, Далее мы будем использовать пример, чтобы более интуитивно почувствовать принцип GBDT: Допустим, наша задача - предсказать возраст, т.е. , задача регрессии, поэтому мы выбираем функцию квадрата потерь. Теперь есть четыре человека, A, B, C и D, возраст которых составляет 14, 16, 24 и 26 лет соответственно, и они характеризуются суммой покупок и ответами. вопросы.
Как показано на рисунке 6, каждое дерево будет выбирать оптимальную функцию и ее оптимальную точку разделения; обучающая выборка последнего дерева является остатком предыдущего дерева (также называемым остаточным деревом), когда остаток Завершить обучение, когда он 0.
Рис. 6. Пример GBDT с квадратичной функцией потерь
Приведенные выше примеры идеальны, и недостатки деревьев решений, такие как простота переобучения и большие временные затраты на поиск точек разделения, не отражены. Для переобучения, помимо некоторых средств дерева решений [5], GBM также принимает следующие меры:
-
Установите максимальное количество итераций (maxIter): причина в том, что чем больше итераций, тем легче переобучить модель.
-
Увеличьте коэффициент сжатия (скорость обучения):
В формуле количество итераций для достижения сходимости контролируется скоростью обучения v, и влияние следующих деревьев на модель может быть уменьшено.
- SGB (Stochastic Gradient Boosting): Обучение после выборки (без замены) из полного объема данных в каждой итерации, этот метод не только уменьшает объем вычислений, но и эффективно предотвращает переобучение, убивая двух зайцев одним выстрелом.
Что касается задачи поиска наилучшей точки разделения, давайте сначала посмотрим, почему это так трудоемко: как показано на рисунке 7, сначала нам нужно предварительно отсортировать значения, соответствующие каждому признаку, а затем использовать эти значения. как точка разделения. Вычислите примесь (примесь, которая представлена квадратом ошибки дерева регрессии) индивидуально, чтобы определить оптимальную точку. Очевидно, что этот метод подходит только для сценариев с небольшим объемом данных и относительно низкой функцией измерение.
Поэтому то, как улучшить алгоритм поиска оптимальной точки разделения, является основной темой GBDT. XGBoost и LightGBM, которые будут представлены далее в этой статье, также проделали большую работу в этой области.
Рисунок 7 Точные жадные алгоритмы — сначала предварительно отсортируйте значения каждой функции, а затем пройдите пороговое значение, чтобы определить наилучшую точку разделения. Примесь на рисунке использует дисперсию, а критерием наилучшей точки разделения является наименьшая сумма примесей левого и правого потомков. Когда количество признаков увеличивается, диапазон значений в признаках становится шире или глубина дерева становится глубже, время обучения дерева становится очень медленным.
GBDT подходит к концу, резюмируем его основные моменты:
-
Используйте дерево регрессии в качестве базового учащегося
-
Задача дерева регрессии состоит в том, чтобы соответствовать градиенту, но процесс разделения узлов дерева принимает критерий дерева регрессии --- квадрат ошибки
-
Поиск оптимальной точки разделения выполняется медленно и подвержен переоснащению.
3. XGBoost
Появление XGBoost позволяет применять GBDT в больших масштабах: XGBoost предоставляет масштабируемую систему сквозного повышения дерева.
Он не только вводит обычный член в функцию потерь, но также определяет критерий разделения узлов дерева — используя для определения оптимальной точки разделения градиенты 1 и 2. Плохое ускорение закладывает основу.
Как показано на рисунке 8, после разложения второго порядка регулярного члена в ряд Тейлора решается «Оценка структуры» [6] дерева, которая напрямую связана с «суммой градиентов» всех выборок текущего node, если вы используете конечный узел гистограммы, вам нужно подсчитать только один дочерний узел, а другой можно получить, вычитая текущий дочерний элемент напрямую из родительского узла.
Мало того, XGBoost также улучшил точный алгоритм на рисунке 7 — алгоритм квантильной аппроксимации, которому не нужно использовать все значения в признаке, чтобы попытаться создать точки разделения, а только принимает значение квантиля. Конкретную формулу вывода, упомянутую выше, см. в Ссылке 6. В этой статье они не повторяются, далее в виде сводки будут перечислены основные вклады XGBoost:
-
В функцию потерь вводится обычный член, и анализируется "оценка структуры", используемая для разделения дерева. "Оценка структуры" может быть ускорена в гистограмме.
-
Алгоритм квантильной аппроксимации при нахождении оптимальной точки разделения уменьшает количество порогов
-
Выборка столбцов (выборка признаков), в которой используется выборка столбцов случайного леса для уменьшения переобучения.
-
Поддержка разреженных данных, добавление направления по умолчанию для работы с некоторыми отсутствующими значениями при разделении узлов дерева.
-
Блочная структура используется для сокращения времени сортировки и оптимизации кэш-памяти.
Рис. 8 Критерий расщепления после добавления регулярного члена, g — градиент, h — градиент второго порядка
4. LightGBM
Основанный на XGBoost, LightGBM оптимизирован для больших данных и сверхвысоких размеров. Конкретные меры:
-
Используйте гистограмму признаков, то есть бинируйте значения, которым принадлежит признак.
-
GOSS (односторонняя выборка на основе градиента): выборка в соответствии с весами градиента
-
EFB (эксклюзивное объединение функций): объединение функций
Гистограмма хорошо понятна - это дискретизация корзин.Сначала выборки положительно сортируются по собственным значениям, а затем определяется отношение между выборками и корзинами в соответствии со стратегией (общие стратегии включают эквидистантную и равночастотную [7]. ]), а значение признака Диапазон будет не больше, чем количество сегментов.
Это дает много преимуществ: предполагается, что функция F имеет n значений, максимальное количество сегментов равно k и k
Как показано на рисунке 9, гистограмма состоит из двух элементов: общего количества выборок в ведре и суммы градиентов всех выборок в ведре.В качестве примера мы используем метод равноудаленного рассеяния, чтобы разделить значение веса на два сегмента — Bin0={1,3}, Bin1={0,2}, формула на рисунке представляет собой метрику (с GOSS), используемую lightGBM для нахождения оптимальной точки разделения, за исключением гиперпараметра, это полностью состоит из градиентов 1-го порядка, поэтому мы вычисляем только сумму градиентов первого порядка левого дочернего узла, сумма градиентов правого дочернего узла = сумма градиентов родительского узла - сумма градиентов левого дочернего узла, которое называется дифференциальным ускорением гистограммы.
Конечно, когда мы также сохраняем двухступенчатый градиент, xgboost также может добиться дифференциального ускорения гистограммы (см. формулу на рисунке 8).
Рисунок 9 Структура гистограммы и принцип ускорения разности гистограмм
GOSS на самом деле является методом выборки по весу. Хотя веса всех выборок GBDT одинаковы, градиенты, соответствующие каждой выборке, различаются по размеру, поэтому можно считать, что чем больше градиент выборки, тем важнее выборка.GOSS установит порог градиента, и выборки больше порогового значения Требуются все, в то время как остальная часть выборки пропорционально выбирается случайным образом.
Хотя GOSS уменьшает количество обучающих выборок, размерность функций в реальных проектах, как правило, очень высока, поэтому можно ли ее оптимизировать, уменьшив количество функций?
Прежде всего, следует признать, что сверхвысокая размерность в практических проектах часто вызвана горячим кодированием, то есть пространство признаков велико и разрежено.Известно, что в разреженном пространстве многие признаки являются взаимоисключающими (например, Гендерные признаки после горячего кодирования не могут быть равны 1 одновременно, поэтому мы можем объединить эти взаимоисключающие признаки вместе. Что касается того, как их связать, EFB уже дал ответ.
Как показано на рисунке 10: Мы строим граф признаков и отношения между признаками, вершины которого являются признаками, а ребра представляют конфликты (конфликты можно понимать как два признака, которые существуют по крайней мере в определенной выборке и не равны 0 в то же время ) , но установлено, что минимальное количество цветов в графе является NP-трудным, поэтому идеальной ситуацией является рисунок 10. Фактически жадный алгоритм, заданный EFB, показан на рисунке 11 [8]: ребро граф имеет значение, указывающее степень конфликтности.Вес, установите порог γ, если степень конфликтности меньше γ, функции будут объединены вместе, и так до конца этого связывания, и повторите вышеописанные шаги для следующей комплектации.
Рис. 10. Объединение функций с использованием принципов разреженности функций и раскраски графа (идеальный сценарий)
Рис. 11 Алгоритм жадного связывания
5. CatBoost
CatBoost специально оптимизирует функции классификации. Поскольку мы используем двоичное дерево регрессии, функции классификации нельзя использовать напрямую. В настоящее время существует два метода обработки функций классификации:
-
однократное кодирование
-
Кодировка тега
Среди них в наших проектах маркировки больше используется одногорячее кодирование, а GBDT в spark ML использует кодирование меток по умолчанию — то есть каждая категория соответствует бину, а затем использует центр бина (в задаче классификации, статистическая метка = 1 Однако, когда размер выборки, соответствующий определенному классу, мал, кодирование метки склонно к переоснащению.
Кстати, в maxBin на данный момент зарезервировано 8 бит, то есть максимальное число всего 255, но характеристики реального проекта, например типа APP, могут достигать десятков тысяч. Для функции классификации в GBDT категория соответствует корзине.Очевидно, что если мы напрямую введем функцию типа APP в GBDT, в обучении будет участвовать только 255 APP (на самом деле SparkML сообщит в этом случае напоминание об ошибке ), то тогда нужно подумать, как сузить круг категориальных признаков или использовать другие способы кодирования.
Далее давайте посмотрим, какие улучшения CatBoost внес в функции классификации [9]:
-
Улучшите кодирование меток — добавьте предыдущие значения, чтобы уменьшить шум, вызванный низкочастотными функциями (задача регрессии: вычислить среднее значение метки, задача классификации: подсчитать метку = 1 число), а кодирование каждой выборки основано на ранжировании перед выборкой. , Среднее значение меток класса.
-
Комбинация функций. Можно использовать связи между функциями.
-
Adversarial Gradient Biased Estimation — реализованы некоторые методы для решения проблемы градиентной оценки.
Эта статья лишь кратко представляет CatBoost, и заинтересованные читатели могут обратиться к ссылкам 9 и 10 для более глубокого понимания.
6. Резюме
Эта статья первоначально следовала идеям статьи Фридмана от бустинга и численной оптимизации до GBM, а затем представила деревья решений для получения GBDT. Дерево в GBDT используется только для соответствия градиенту. Когда узел разделен, примесь дерева решений используется в качестве метрики. Позже градиент вводится в примесь, которая называется «оценкой структуры». Это в статьях 6 и 8. Было упомянуто, что, поскольку структурные точки состоят только из градиентов (или градиентов второго порядка), использование гистограмм может не только повысить надежность алгоритма, но и ускорить при разделении узлов.
Наконец, GBDT является одновременно повышением градиента и повышением дерева, поэтому нам нужно знать, улучшает ли каждый алгоритм повышение градиента или повышение дерева. Например, оптимизация алгоритма поиска оптимальной точки разбиения дерева на самом деле является оптимизацией в категории Tree Boosting, а предвзятая оценка градиента конфронтации в CatBoost — это скорее оптимизация для Gradient Boosting.
Из экспериментальных данных в статье CatBoost> LightGBM> XGBoost> GBDT, но в производственной среде этот вид не рекомендуется для справки, вы должны выбрать наиболее подходящий алгоритм для ваших данных.
использованная литература
1.What is the difference between bagging and boosting
2.A Quick Guide to Boosting in ML
medium.com/GRE принимает атом/ах-…
3.Greedy Function Approximation: A Gradient Boosting Machine
статистика Web.Stanford.quote/~monsoon/ftp/suddenly…
4.Decision_tree_learning
En. Wikipedia.org/wiki/Dec ISI…
5.medium.com/GRE берет атом/ из…
6.XGBoost: A Scalable Tree Boosting System
Авторизуйтесь ACM.org/citation.Eat…
7. Дискретность - равночастотный равный интервал
blog.CSDN.net/Температура на севере лучше, чем в самолете/Ах…
8.Бумаги.Грязевой Бодхисаттва.Цао Цао/бумага/6907-…
9.обучение sys.org/mudbodhisattva17/as-color…
10.medium.com/@harney сказал, что умер...
Наконец-то настал момент~
Команда маркировки данных OPPO Business Center набирает сотрудников на несколько вакансий, мы стремимся проникать в большие данные, чтобы понять бизнес-интересы каждого пользователя OPPO. В процессе быстрого расширения данных и глубокого изучения мы искренне приглашаем вас, имеющих более двух лет опыта в области анализа данных, обработки больших данных, машинного обучения/глубокого обучения, НЛП и т. д., присоединиться к нам и расти вместе с нашей командой и бизнес! Возобновление доставки: ping.wang#oppo.com