Популярное понимание kaggle game killer xgboost

            Популярное понимание xgboost, убийцы игр Kaggle

 

Примечание. Если некоторые изображения не отображаются нормально и мешают чтению, обратитесь к статье здесь:версия банка вопросов xgboost.
Время: 25 марта 2019 г.

 

0 Предисловие

xgboost всегда считался артефактом на соревновательной арене, например, в соревнованиях kaggle/tianchi время от времени кто-то использует xgboost, чтобы выиграть чемпионат среди тысяч солдат.

В нашем курсе по машинному обучению также необходимо преподавать xgboost, как сказал Хан: «RF и GBDT — это модели, которые любят в отрасли, Xgboost — это пакет убийц, и различные рейтинги Kaggle Top однажды показали, что Xgboost доминирует в реках и озер. , Кроме того, улучшение первого места в конкурсе Didi также связано с Xgboost».

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

Под влиянием ИИ в этом году особенно много друзей переключились с традиционной карьеры в сфере ИТ на ИИ. Многие друзья спрашивают, как переключиться на ИИ. Я обычно сосредотачиваюсь на изучении ИИ или поиске/изменении ИИ четырех больших королей:курс + Банк вопросов + OJ+ каггле/тяньчи. Выпускные оценки, включая тренировочные сборы, будут объединены с соревнованиями kaggle или Tianchi.

Учитывая важность конкурса Kaggle/Tianchi для математических наук, эта статья представляет xgboost, чтобы помочь вам быстро начать работу с xgboost и добиться отличных результатов в конкурсе.

В конце концов, xgboost не был изобретен мной в июле, но я позабочусь о том, чтобы эта статья представила его наиболее простым способом (и эта статья была рассмотрена доктором Ченом, главой онлайн-лаборатории искусственного интеллекта в июле). Кроме того, спасибо за все ссылки, перечисленные в конце статьи, если у вас есть какие-либо вопросы, пожалуйста, не стесняйтесь оставлять комментарии, спасибо.

1 Дерево решений

Например, в каком-то тренировочном лагере более 100 тренирующихся.Предположим, вам дали задание посчитать количество мальчиков и девочек.Когда один тренирующийся встанет перед вами один за другим, как вы отличите, кто мужчина от другой?Это женщина?

Очень быстро вы считаете, что волосы мальчиков, как правило, короткие, а волосы девочек, как правило, длиннее, поэтому вы делите всех учеников в этом классе на две группы в зависимости от длины их волос: длинные волосы — «женские», а короткие — «женские». волосы "мужские".

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

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

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

Существует множество способов количественной оценки эффекта классификации, например прирост информации (ID3), скорость прироста информации (C4.5), коэффициент Джини (CART) и так далее.

Показатели получения информации: энтропия

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

Что такое получение информации? Чтобы точно определить прирост информации, мы сначала определим метрику, широко используемую в теории информации, называемуюэнтропия(энтропия), характеризующая чистоту любого набора образцов. Для набора примеров S, содержащего положительные и отрицательные примеры целевого понятия, энтропия S по отношению к этой булевой классификации равна:

В приведенной выше формуле p+ представляет собой положительный пример, например, во втором примере в начале этой статьи p+ означает играть в бадминтон, а p- представляет отрицательный пример, а не играть (во всех расчетах энтропии мы определяем 0log0 равно 0).

Например, предположим, что S представляет собой набор из 14 примеров булевых понятий, включая 9 положительных примеров и 5 отрицательных примеров (мы используем обозначения [9+, 5-] для обобщения таких примеров данных). Тогда энтропия S по отношению к этот логический пример:

Энтропия([9+,5-])=-(9/14)log2(9/14)-(5/14)log2(5/14)=0,940.

Итак, согласно приведенной выше формуле, мы можем получить:

• Энтропия(S)=0, если все элементы S принадлежат к одному классу;
• Если количество положительных и отрицательных отсчетов S одинаково, то Entropy(S)=1;
• Если количество положительных и отрицательных примеров S не равно, энтропия находится между 0 и 1.

Как показано ниже:

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

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

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

 

2. Дерево регрессии и ансамблевое обучение

Если вы определяете xgboost в одном предложении, это очень просто: Xgboost интегрируется многими деревьями CART. Но что такое дерево CART?

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

1. Анализ дерева классификации означает, что результатом прогнозирования является класс, к которому принадлежат данные (например, смотреть фильм или нет).
2. Анализ дерева регрессии — это когда прогнозы можно считать реальными числами (например, цена дома или продолжительность пребывания пациента в больнице).

Анализ термина «Дерево классификации и регрессии» (CART, «Дерево классификации и регрессии») является общим термином, используемым для обозначения двух вышеупомянутых типов деревьев, впервые предложенных Breiman et al.

2.1 Дерево регрессии
На самом деле классификация и регрессия — это две очень близкие задачи.Цель классификации — определить, к какому известному классу выборок относится новая выборка на основе определенных характеристик известных выборок, а ее результатом является дискретное значение. Результатом регрессии является непрерывное значение. Конечно, суть та же, сопоставление между функциями и результатами/метками.

После выяснения того, что такое классификация и регрессия, нетрудно понять деревья классификации и деревья регрессии.

Образец вывода (то есть значение ответа) дерева классификации имеет форму класса, например, суждение о том, является ли это спасительное лекарство истинным или ложным, и стоит ли ходить в кино «Заклинание ветра» по выходным. . Пример выходных данных дерева регрессии представлен в виде числовых значений.Например, сумма выданного кому-либо жилищного кредита представляет собой конкретное числовое значение, которое может быть любым значением в диапазоне от 0 до 3 миллионов юаней.

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

Дерево регрессии CART предполагает, что дерево является бинарным деревом и непрерывно делит функции. Например, текущий узел дерева разбивается на основе j-го собственного значения, и выборки с собственным значением меньше s делятся на левое поддерево, а выборки больше s делятся на правое поддерево.

Дерево регрессии CART по существу делит выборочное пространство в измерении признаков, и оптимизация этого деления пространства является NP-трудной задачей, поэтому в модели дерева решений для ее решения используется эвристический метод. Целевая функция, созданная типичным деревом регрессии CART:

Поэтому, когда мы хотим решить оптимальный признак сегментации j и оптимальную точку сегментации s, это преобразуется в решение такой целевой функции:

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

2.2 Стимулирование интегрированного обучения

Так называемое ансамблевое обучение относится к созданию нескольких классификаторов (слабых классификаторов) для прогнозирования набора данных, а затем с использованием определенной стратегии для интеграции результатов, предсказанных несколькими классификаторами, в качестве окончательного результата прогнозирования. Популярная метафора - «три марионетки победили Чжугэ Ляна» или решения голосования директоров в совете директоров компании, которые требуют, чтобы каждый слабый классификатор имел определенную «точность» и «разницу» между классификаторами.

Обучение ансамблю делится на две основные школы, Boosting и Bagging, в зависимости от того, существует ли зависимость между каждым слабым классификатором:

1. Жанр бустинга, существуют зависимости между классификаторами и должны быть сериализованы, например, Adaboost, GBDT (Gradient Boosting Decision Tree), Xgboost
2. Жанр бэгинга, между классификаторами нет зависимости, их можно запускать параллельно, например Random Forest

Известный Adaboost — один из самых представительных методов в жанре бустинга, и в этом блоге он подробно представлен.

AdaBoost, сокращение от «Adaptive Boosting» на английском языке, был предложен Йоавом Фройндом и Робертом Шапиром в 1995 году. Его адаптация заключается в том, что выборки, неправильно классифицированные предыдущим базовым классификатором, будут усиливаться, а взвешенные суммарные выборки снова используются для обучения следующего базового классификатора. В то же время новый слабый классификатор добавляется в каждом раунде до тех пор, пока не будет достигнута заранее заданная достаточно малая частота ошибок или не будет достигнуто заранее заданное максимальное количество итераций.

В частности, весь итеративный алгоритм Adaboost состоит из трех шагов:

1. Инициализируйте распределение веса для обучающих данных. Если имеется N выборок, каждой обучающей выборке изначально присваивается одинаковый вес: 1/N.
2. Обучайте слабые классификаторы. В конкретном процессе обучения, если точка выборки была точно классифицирована, ее вес будет уменьшен при построении следующей обучающей выборки, и наоборот, если выборка не была точно классифицирована, ее вес будет уменьшен, улучшен. Затем набор выборок с обновленными весами используется для обучения следующего классификатора, и весь процесс обучения проходит итеративно.
3. Слабые классификаторы, полученные в результате каждого обучения, объединяются в сильный классификатор. После завершения процесса обучения каждого слабого классификатора увеличьте вес слабого классификатора с небольшой частотой ошибок классификации, чтобы он играл большую решающую роль в окончательной функции классификации, и уменьшите вес слабого классификатора с большой коэффициент ошибок классификации веса, чтобы они играли меньшую решающую роль в окончательной функции классификации. Другими словами, слабый классификатор с низкой частотой ошибок имеет больший вес в итоговом классификаторе, в противном случае он меньше.

Другой метод повышения, GBDT (Gradient Boost Decision Tree), отличается от AdaBoost.Каждый расчет GBDT заключается в уменьшении предыдущего остатка, а затем установлении нового в направлении уменьшения остатка (отрицательный градиент).Модель.

Повышающее ансамблевое обучение состоит из нескольких связанных деревьев решений для принятия совместных решений.Что такое ассоциация? Например

1. Существует образец [данные->метка], который: [(2, 4, 5)-> 4]
2. Первое дерево решений, обученное с помощью этой выборки, имеет прогноз 3,3.
3. Затем вход второго обучения дерева решений, этот образец становится: [(2, 4, 5) -> 0,7]
4. То есть входная выборка следующего дерева решений будет связана с обучением и прогнозированием предыдущего дерева решений.

Вскоре вы поймете, почему Xgboost также способствует интегрированному обучению.

Ключевыми моментами построения дерева регрессии являются:

• На чем основана точка разделения (как упоминалось ранее, среднеквадратическая ошибка является наименьшей, потеря);
• Каково прогнозируемое значение классифицированного узла (как упоминалось выше, нужно использовать среднее значение фактического значения каждой выборки в листовом узле в качестве прогнозируемой ошибки конечного узла или вычислить)

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

 

3.GBDT

Говоря о Xgboost, мы должны начать с GBDT (Gradient Boosting Decision Tree). Поскольку xgboost по сути является GBDT, но стремится к максимальной скорости и эффективности, он называется X (Extreme) GBoosted. Включая вышеупомянутое, оба являются методами повышения.

Принцип GBDT очень прост, то есть сумма результатов всех слабых классификаторов равна предсказанному значению, а затем следующий слабый классификатор должен подогнать градиент/остаток функции ошибок к предсказанному значению (это градиент/остаток — это прогнозируемое значение и истинное значение (ошибка между ними). Разумеется, слабые классификаторы в нем представлены деревьями. Как показано: Y = Y1 + Y2 + Y3.

Чтобы привести очень простой пример, например, мне 30 лет в этом году, но компьютер или модель GBDT не знает, сколько мне лет, так что насчет GBDT?

1. Он будет соответствовать случайному возрасту, например 20, в первом слабом классификаторе (или в первом дереве) и обнаружит, что ошибка составляет 10 лет;
2. Затем во втором дереве используйте 6 лет, чтобы соответствовать оставшейся потере, и обнаружите, что промежуток все еще составляет 4 года;
3. Затем поместите оставшийся промежуток в 3 года в третьем дереве и обнаружите, что промежуток составляет всего 1 год;
4. Наконец, подогнал оставшиеся остатки с 1-летним ребенком в четвертом дереве уроков, идеально.

В итоге сумма выводов четырех деревьев составляет 30 лет. В реальной инженерии gbdt вычисляет отрицательные градиенты и аппроксимирует остатки отрицательными градиентами.

Обратите внимание, почему gbdt аппроксимирует остатки отрицательными градиентами?

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

Затем отрицательный градиент в это время рассчитывается следующим образом.

Следовательно, когда функция потерь использует среднеквадратичную функцию потерь, значение каждой подгонки равно (истинное значение — значение, предсказанное текущей моделью), то есть остаток. В это время переменная, что является «значением текущей модели прогнозирования», то есть взять над ней отрицательный градиент.

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

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

Еще один пример предсказания возраста.

Для простоты предположим, что в обучающей выборке всего 4 человека: A, B, C, D, и их возраст 14, 16, 24 и 26 лет соответственно. Среди них A и B — учащиеся первого и третьего курсов средней школы соответственно; C и D — недавние выпускники и сотрудники, проработавшие два года.

Итак, теперь вопрос в том, что мы хотим предсказать возраст этих 4 человек, с чего нам начать? Это очень просто, сначала сопоставьте их с возрастом, например, 20 лет, а затем отрегулируйте их в соответствии с реальной ситуацией.

Если вы тренируетесь с традиционным деревом решений регрессии, вы получите результаты, показанные на следующем рисунке:

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

Мы получим результат, как показано ниже:

Первая ветвь дерева такая же, как на рисунке 1. Поскольку A и B относительно близки по возрасту, C и D относительно близки по возрасту, их делят на левую и правую группы, и средний возраст каждой группы используется как прогнозируемое значение.

• В этот момент вычисляются остатки (Остаточные средства: фактическое значение A - прогнозируемое значение A = остаток A.), поэтому остаток A равен фактическому значению 14 - прогнозируемому значению 15 = остаточному значению -1.
• Обратите внимание, что прогнозируемое значение A относится к накопленной сумме всех предыдущих деревьев.Перед ним находится только одно дерево, поэтому оно равно 15. Если деревья еще есть, их необходимо суммировать как прогнозируемое значение А.

Остатки в математической статистике - это разница между фактически наблюдаемым значением и оценочным значением (подобранным значением). «Остатки» содержат важную информацию о лежащих в основе допущениях модели. Если модель регрессии верна, мы можем думать об остатках как об ошибках в наблюдениях.

Тогда остатки A, B, C и D равны -1, 1, -1, 1 соответственно.

Затем используйте их остатки -1, 1, -1, 1, чтобы заменить исходные значения ABCD, и перейдите ко второму дереву для обучения.Второе дерево имеет только два значения 1 и -1, которые делятся напрямую на два узла, а именно оценки A и C слева, оценки B и D справа, после расчета (например, A, фактическое значение -1 - прогнозируемое значение -1 = остаток 0, например, C, фактическое значение -1 - прогнозируемое значение -1 = 0), это Остатки для всех равны 0.

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

Другими словами, предсказанные значения A, B, C и D теперь соответствуют реальному возрасту. Идеально!
A: 14-летний старшеклассник, меньше ходит по магазинам, часто задает вопросы старшим, предполагаемый возраст A = 15 – 1 = 14 лет.
B: 16-летний старшеклассник, учится в старшей школе, меньше ходит по магазинам, младшие школьники часто задают вопросы, предполагаемый возраст B = 15 + 1 = 16.

C: 24-летний выпускник, много ходит по магазинам, часто задает вопросы старшему поколению, предполагаемый возраст C = 25 – 1 = 24.
D: 26-летний сотрудник, который проработал два года, много ходит по магазинам, ему часто задают вопросы младшие школьники и учителя Прогнозируемый возраст D = 25 + 1 = 26

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

 

4.Xgboost

4.1 Определение дерева xgboost

Схематическая диаграмма в этом разделе в основном цитируется из раздаточного материала PPT оригинального автора xgboost Чена Тяньци.

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

Таким образом обучаются два дерева дерево 1 и дерево 2. Как и в предыдущем принципе gbdt, сумма выводов двух деревьев является окончательным выводом, поэтому прогнозируемая оценка ребенка - это узел, в котором ребенок попадает в Два дерева Сложите баллы: 2 + 0,9 = 2,9. Прогнозируемый балл дедушки такой же: -1 + (-0,9) = -1,9. В частности, как показано на рисунке ниже

Ну, вы можете хлопнуть по столу и воскликнуть, разве это не то же самое, что и gbdt, представленный выше?

На самом деле, если не учитывать некоторые различия в инженерной реализации и решении задач, большая разница между xgboost и gbdt заключается в определении целевой функции. Целевая функция xgboost показана на следующем рисунке:

в

• L, на которую указывает красная стрелка, — это функция потерь (например, квадратичная функция потерь:, или функция логистических потерь:)
• В красной рамке обозначен обычный термин (включая обычный термин L1, обычный L2).
• Красный кружок - постоянный член
• за, xgboost использует Тейлора для расширения трех членов, чтобы сделать приближение

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

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

4.2 Целевая функция xgboost

Идея основного алгоритма xgboost не сложна, в основном это

1. продолжайте добавлять деревья,Непрерывное разбиение функций для роста дерева, добавление дерева каждый раз фактически изучает новую функцию, чтобы соответствовать остатку последнего прогноза..

   

   Примечание: w_q(x) — оценка листового узла q,Соответствует набору всех K деревьев регрессии, а f(x) — одно из деревьев регрессии.

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

3. Наконец, вам нужно только сложить баллы, соответствующие каждому дереву, чтобы получить прогнозируемое значение выборки.

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

Следовательно, с математической точки зрения это задача функциональной оптимизации, поэтому целевая функция упрощается следующим образом:

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

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

T представляет количество конечных узлов, а w представляет количество конечных узлов. Интуитивно понятно, что цель требует, чтобы ошибка предсказания была как можно меньше, а количество конечных узлов T должно быть как можно меньше (γ управляет количеством конечных узлов), а значение узла w не должно быть как можно более экстремальным. (λ контролирует количество листовых узлов, чтобы оно не было слишком большим), чтобы предотвратить переоснащение объединения.

Вставьте предложение, общая целевая функция содержит следующие два

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

4.2.1 Обучение модели и ошибка обучения

В частности, в первой части целевой функцииозначает первыйобразцы, (−) означает первыйОшибка предсказания образцов, наша цель, конечно, в том, что чем меньше ошибка, тем лучше.

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

Но как мы выбираем, что добавлять в каждом раунде?Шерстяная ткань? Ответ очень прост, выберите одинминимизировать нашу целевую функцию.

Опять же, учитываяПрогнозы модели для раунда t = Прогнозы модели для первых раундов t-1  +  , поэтому функция ошибки записывается так:   ( ,  +  ), последний член является членом регуляризации.

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

Формула Obj выше может быть слишком абстрактной, мы можем рассмотреть, когдаслучай квадрата ошибки (эквивалентный), в это время наша цель может быть записана в виде следующей квадратичной функции (обведенная кружком часть на рисунке представляет собой невязку между прогнозируемым значением и истинным значением):

В более общем смысле, что, если функция потерь не является квадратичной функцией? Используя разложение Тейлора, подумайте о способах, которые не являются квадратичными, чтобы аппроксимировать квадратичный (как вы можете видеть, первая производная определяетсяи вторая производная).

Ну, обратите внимание! Многие люди могут застрять здесь, и в Интернете есть несколько статей, которые ясно объясняют это.После обсуждения с доктором Ченом из июльской онлайн-лаборатории искусственного интеллекта я обнаружил, что самое важное здесь — это на самом деле расширить условия второй статьи Тейлора. -порядок и целевая функция xgboost.Выяснено соответствующее соотношение, которое эквивалентно аппроксимации целевой функции, что мы можем использовать разложение Тейлора второго порядка.

Во-первых, это разложение Тейлора второго порядка

Соответствует целевой функции xgboost

Игнорировать функцию потерь середина(Не забывайте сказанное выше: «На шаге tявляется реальным значением, то есть известным», что не влияет на последующую пару целевых функцийРасчет частной производной), выполните следующее однозначное соответствие:

• X в разложении Тейлора второго порядка f соответствует x в целевой функции,
• f мильСоответствующая целевая функция,
• Следовательно, когда f берет производную от x, это соответствует паре целевой функцииИскать частную производную

получить:

в,,

Уууу, ясно! Однако откуда взялось квадратичное разложение Тейлора, ключ к этому процессу преобразования?

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

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

Теорема Тейлора:
Пусть n — целое положительное число. Если функция f, определенная на интервале, содержащем a, дифференцируема n+1 раз в точке a, то для любого x на этом интервале имеем:

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

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

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

Общие рекомендации сформулированы первым читателем Google crab6789:

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

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

4.2.2 Регулярные термины: сложность дерева

Сначала разберитесь со следующими правилами

• Представлен набором конечных узлов и оценкой конечных узлов.
• Каждый образец попадает на листовой узел
• q(x) указывает, что образец x находится на определенном концевом узле, а wq(x) — оценка узла, то есть предсказанное моделью значение образца

Поэтому, когда мы превращаем дерево вструктурная часть qиПосле части веса листа wСтруктурная функция q сопоставляет входные данные с номером индекса листа, а w дает оценку листа, соответствующую каждому номеру индекса.

Кроме того, как показано на рисунке ниже, сложность дерева xgboost состоит из двух частей:

1. Один - это количество T листовых узлов в дереве.
2. Один из них - квадрат L2 по модулю оценки w листовых узлов на дереве (регуляризация L2 w эквивалентна добавлению сглаживания L2 к оценке каждого листового узла, чтобы избежать переобучения)

В соответствии с этим новым определением мы можем преобразовать предыдущую целевую функцию следующим образом (кроме того, не забывайте:)

вопределяется как набор выборочных индексов над каждым конечным узлом j, g — первая производная, h — вторая производная. Этот шаг связан с добавлением двух обычных членов во вторую часть целевой функции xgboost, один из которых представляет собой количество конечных узлов (T), а другой — оценку конечных узлов (w).

Следовательно, есть два вида накопления в целевой функции с добавлением регулярного члена.

• один-> n (количество выборок)
• один-> T (количество листовых узлов)

Эта цель содержит T независимых одномерных квадратичных функций.

Что является ключом к пониманию этого вывода? После обсуждения с доктором Ченом из лаборатории искусственного интеллекта, на самом деле речь идет о понимании этого определения:определяется как набор выборочных индексов над каждым конечным узлом j, то, что q(xi) в этом определении хочет выразить, это то, что каждое выборочное значение xi может быть отображено на конечный узел дерева с помощью функции q(xi), так что два накопления объединяются посредством этого определения.

Далее мы можем определить

Окончательную формулу можно упростить до

через паруПроизводная равна 0, мы можем получить

тогда поставьОптимальное решение подставляется в:

4.3 Расчет функции оценки

Obj представляет, насколько мы можем уменьшить цель, когда указываем древовидную структуру. Мы можем назвать это показателем структуры

4.3.1 Разделенный узел

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

Чтобы узнать, как разделить листовой узел, автор xgboost дал два метода разделения узлов в своей оригинальной статье.

(1) Жадный метод для перечисления всех различных древовидных структур

Текущая ситуация такова, что пока вы знаете структуру дерева, вы можете получить лучший результат по структуре Как определить структуру дерева?

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

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

Помните формулу расчета, которую мы получили в конце раздела 4.2?

Другими словами, часть G/(H+λ) целевой функции представляет собой вклад каждого конечного узла в потери текущей модели.Объедините его, чтобы получить расчетное выражение усиления, как показано ниже:

Первое, что стоит отметить, это «для признака сначала отсортировать по значению в признаке», вот пример.

Например, установите значение a, а затем перечислите все условия, такие как x x представляет определенную характеристику, такую ​​как возраст, отсортируйте возраст от меньшего к большему: если он увеличивается слева направо, поместите те, которые меньше а, слева, а те, что больше а, справа.), для конкретного разбиения a мы хотим вычислить сумму производных слева и справа от a.

Например, всего человек пять.После сортировки по возрасту имеем в начале следующие четыре метода деления:

1. Отделите первого человека от следующих четырех
2. Отделите первые два от последних трех
3. Отделить первые три от последних двух
4. Отделить переднюю четверку от задней

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

Другими словами, для всех признаков x мы можем перечислить градиенты, GL и GR всех сегментаций, выполнив одно сканирование слева направо. Затем используйте формулу для расчета усиления, чтобы рассчитать оценку каждой схемы сегментации.

Затем продолжается разделение второго слоя, третьего слоя, четвертого слоя и N-го слоя в соответствии с этим методом разделения.

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

Другими словами, при введении сегментации оценка, полученная после результирующей сегментации — оценка, полученная без сегментации, слишком мала (например, меньше нашего минимального ожидаемого порога γ), но результирующая сложность слишком высока, тогда эквивалент не стоит потери, лучше не делить. Другими словами, польза от совершения определенного действия ненамного больше, чем вред, который оно приносит.Чтобы избежать сложного отношения, что чем больше вещей, тем хуже, чем меньше вещей, лучше их не совершать.

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

Ниже приведен алгоритм в статье

(2) Приблизительный алгоритм

В основном данные слишком велики, не могут быть рассчитаны напрямую

Читатель Crab6789, работающий в Google, прокомментировал:

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

4.4 Резюме: Алгоритм усиленного дерева

Подводя итог, как показано на рис.

Давайте еще раз рассмотрим весь процесс.

Если значение метки выборки равно 4, то первое дерево регрессии предсказывает 3, а второе предсказание равно 1; для другого набора деревьев регрессии одно предсказывает 2, а другое предсказывает 2, то оно стремится к последнему, почему? В первом случае первое дерево учится слишком многому и слишком близко к 4, что означает больший риск переобучения.

Хорошо, это звучит очень хорошо, но как этого добиться? Как приведенная выше целевая функция соотносится с фактическими параметрами? Помните, мы говорили, что параметры дерева регрессии:

1. Какой узел разделения функций выбрать?
2. Прогнозируемое значение узла (на такой грубый и необоснованный способ брать среднее нельзя полагаться, все-таки он более продвинутый)

Последняя стратегия такова: жадность + оптимизация (да, квадратичная оптимизация).

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

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

• Если здесь ошибка l(w−yi) представляет собой квадрат ошибки, то приведенная выше функция является квадратичной функцией w для нахождения минимального значения, точка, в которой берется минимальное значение, является предсказанным значением этого узла, а минимальное значение функции - функция потери минимального значения.
• По сути, это задача оптимизации квадратичной функции! Но что, если функция потерь не является квадратичной? Расширение Тейлора не является квадратичным, чтобы найти способ аппроксимировать квадратичное.

Далее выберите функцию, чтобы разделить на два узла и стать слабым саженцем, тогда вам нужно:

1. Определить признак, используемый для разделения, как? Самое простое — это грубое перебор/исчерпывание (ну, достаточно грубое), а затем выбрать тот, у которого лучшая функция потерь;
2. Как установить w узла и функцию минимума потерь, и подскажите как это сделать вслух? Да, максимальное значение квадратичной функции (вычисление квадратичного максимального значения вообще имеет фиксированную процедуру, то есть точку, где производная равна 0). Поэтому выберите разделение признаков, рассчитайте минимальное значение функции потерь, затем выберите другое разделение признаков и получите минимальное значение функции потерь.После перечисления найдите тот, который дает лучший эффект, разделите дерево и получите маленький саженец.

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

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

Ниже приведены установленные пороги

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

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

1. Когда выигрыш, принесенный введенным разделением, меньше установленного порога, мы можем игнорировать это разделение, поэтому не каждая функция потерь разделения будет увеличиваться в целом, что означает предварительную обрезку.(то есть коэффициент числа листовых узлов T в регулярном члене);
2. Когда дерево достигает максимальной глубины, прекратите построение дерева решений и установите гиперпараметр max_depth, чтобы дерево не было слишком глубоким для изучения локальных выборок и переобучения;
3. Когда сумма весов выборок меньше установленного порога, построение дерева прекращается. Что это значит, что включает в себя гиперпараметр - минимальный вес выборки и min_child_weight, которые аналогичны параметру min_child_leaf GBM, но не совсем такие же. Общая идея состоит в том, что существует слишком мало выборок конечного узла, и завершение также должно предотвратить переоснащение;
4. Кажется, здесь самое большое количество деревьев, которые я когда-либо видел...

 

6 ссылок и рекомендованной литературы

1. xgboost оригинальная статья:АР Вест V.org/PDF/1603.02…
2. Раздаточный материал автора xgboost PPT:домов.В это время.Вашингтон.Сумма/~ Подано Чен/PDF…
3. XGBoost и усиленное дерево
4. Принцип xgboost:blog.CSDN.net/ah819825294/…
5. Введение и практика xgboost (принцип):blog.CSDN.net/что угодно 19931201/…
6. Википедия ТЕЛЕГИ
7. ансамблевое обучение
8. Говоря об обучении ансамблем: бустинг и случайный лес
9. От обучения дереву решений к алгоритмам байесовской классификации
10. Дерево решений (3) — полная сводка (ID3, C4.5, CART, сокращение, замена) и анализ исходного кода.
11. Одна статья, чтобы понять принцип XGBoost, главного убийцы машинного обучения.
12. Почему gbdt и random forest так хорошо работают в реальных соревнованиях kaggle?
13. Напишите простую и логичную статью о принципе Xgboost для обсуждения и справки.
14. Июль, выпуск 8 по машинному обучению в Интернете, урок 4, деревья решений, случайные леса, GBDT, xgboost
15. Некоторые основные параметры xgboost
16. Как вообще понимать ряд Тейлора? :Ууху. Call.com/question/21…
17. Зачем xgboost требуется расширение Тейлора второго порядка:Woohoo.Расстояние также читайте.com/question/than…
18. Принцип наиболее популярного дерева повышения градиента (GBDT)
19. ID3, C4.5, CART, случайный лес, пакетирование, повышение, Adaboost, GBDT, сводка алгоритма xgboost
20. Вывод формулы расширения Тейлора второго порядка XGBoost
21. Википедия Тейлора
22. Заметки от xgboost, написанные студенткой Супер Мэри в июльском онлайн-эпизоде ​​6:Эта статья поможет вам понять принцип xgboost.
23. Редактируйте формулы LaTeX онлайн:private.code cogs.com/LaTeX/EQ как насчет D…

 

постскриптум

Наконец-то у меня есть общее понимание этого xgboost, который часто обновляет экран, что еще раз подтверждает то, что я сказал ранее: когда вы изучаете определенный пункт знаний и чувствуете, что не понимаете его, девять раз из десяти это не так. вы недостаточно умны, и в девяти случаях из десяти это вы. Информация, которую я читаю, недостаточно популярна или проста для понимания (если она все еще не работает, спросите кого-нибудь).

Надеюсь, вы, читающие эту статью, почувствуете то же самое.

Следующий процесс улучшения этой статьи предназначен для справки для понимания:

1. Первый выпуск утром 8.4 знакомит с gbdt через простой для понимания пример предсказания возраста, потому что gbdt — это основа для понимания xgboost;
2. Во втором издании во второй половине дня 8.4 есть много формул в выводе xgboost, и новичкам легко попасть в него.После понимания ядра xgboost: целевая функция, разберитесь с контекстной структурой xgboost;
3. Третье издание, выпущенное утром 8.5, оптимизировало вводную часть дерева решений, например, добавлено введение к получению информации;
4. Четвертое издание после обеда 8.5 оптимизировало отображение большинства формул, таких как отображение обычного текста раньше, и теперь оно заменено на отображение изображений LaTeX;
5. Пятое издание, выпущенное утром 8.6, оптимизировало введение загружаемого интегрированного обучения и сделало полный текст более постепенным;
6. Шестое издание вечером 8.6 стандартизирует формульное представление целевой функции xgboost и разбирает многие детали и формулы в полном тексте;
7. Редакция седьмая утром 9.1, для улучшения деления и деления дерева xgboost в разделе 4.3.1, чтобы было понятнее;
8. Восьмое издание 1.9, 2019 г., улучшило описание разделенных узлов в разделе 4.3.1, чтобы сделать логику более понятной, а написание более популярным;
9. 1.10 девятое издание 2019 г., часть 3 добавляет пример прогнозирования возраста для более популярного объяснения GBDT;
10. В десятом издании 1.14 в 2019 году соответствие между разложением Тейлора второго порядка и целевой функцией xgboost было написано четко, чтобы понимание было более гладким.

После прочтения полного текста вы обнаружите, что есть три ключевых момента в понимании xgboost: ① В разделе 4.2.1 поясните однозначное соответствие между терминами целевой функции xgboost и биномиальным разложением Тейлора; ② В разделе 4.2.1. Раздел 4.2.2, оценка w рассчитанного числа Математический прием, используемый, когда ③ алгоритм разделения дерева, показанный в разделе 4.3.1. После выяснения этих трех моментов больше нет препятствий для понимания xgboost.

Июль, вечер 6 августа 2018 г. ~ вечер 14 января 2019 г.