xgboost стал популярным среди специалистов по машинному обучению, и я уверен, что многие друзья использовали его. Чтобы полностью понять xgboost, вы должны понять принципы его внутренней модели. Только так каждый параметр может соответствовать внутренней части модели, чтобы понять значение параметров и настроить параметры по мере необходимости. Цель этой статьи — максимально облегчить вам понимание его внутренностей. Основной ссылкой является эта статья Чена Тяньци.introduction to xgboost. На мой взгляд, эта статья является введением в xgboost.лучший, нет. Учащимся, хорошо владеющим английским языком, рекомендуется читать непосредственно по-английски. Если вы что-то не очень хорошо понимаете, обратитесь к этой статье.
1. Что нужно знать заранее
1. Контролируемое обучение
Обучение с учителем — это обучение с помеченными обучающими данными. Скажем, у меня есть 100 000 фрагментов данных, каждый из которых имеет 100 функций и метку. Содержание метки зависит от задачи обучения.Если данные представляют собой результаты различных тестов, проведенных пациентом для диагностики рака, метка указывает на наличие у пациента рака. это 1, а не 0.
Обучение под наблюдением заключается в том, чтобы извлечь из этих 100 000 фрагментов данных знания о диагностике рака у пациента на основе результатов теста. Поскольку объем обучения ограничен этими 100 000 единицами данных, то есть полученные знания должны быть извлечены из этих 100 000 единиц данных. Чтобы понимать визуально, нужно учиться под «присмотром» этих 100 000 фрагментов размеченных данных. Отсюда и название «обучение с учителем».
2. Контролируемые результаты обучения
Как представлены знания, полученные в результате контролируемого обучения, и как они используются нами, людьми? Проще говоря, полученные знания представлены моделью, и мы, люди, используем эту модель, чтобы использовать полученные знания.
Итак, что такое модель?
Модель — это математическое выражение. Простейшей моделью является линейная модель, которая выглядит так: y^i=∑_j θ_j*x_ij. Используя наш пример выше, x_i — это i-й элемент в наших 100 000 фрагментах данных, а x_ij — j-й результат проверки в i-м фрагменте данных. y^i - результат прогноза модели для этих данных. Чем больше значение, тем выше вероятность того, что пациент заболеет раком. Обычно нам также нужно обработать y^i в значение от 0 до 1, чтобы более четко указать, что это прогноз вероятности.Метод обработки обычно представляет собой сигмоидальную функцию, а те, кто незнаком, могут ссылаться на другие материалы. θ_j — это «вклад» j-го результата теста в наличие у пациента рака Это параметр нашей модели, то есть знания, которые мы извлекли из 100 000 единиц данных.
Видно, что так называемое обучение с учителем состоит из двух шагов, один из которых заключается в определении параметров модели, а другой — в поиске наилучших значений параметров в соответствии с обучающими данными.Знания в данных, но от процесса нахождения параметров есть еще одно объяснение, которое будет подробно объяснено ниже.После нахождения наилучших параметров мы приходим к модели, параметры которой все известны.В это время знания Вот тут мы свободны использовать.
3. Как найти лучшие параметры
Если взять в качестве примера приведенную выше линейную модель, у пациента есть 100 результатов обследования, значит, имеется 100 параметров θ_j (j от 1 до 100). Возможные значения каждого параметра — действительные числа, и очевидно, что существует бесконечное количество комбинаций параметров 100. Как мы судим, является ли набор параметров оптимальным?
На данный момент нам нужна еще одна функция, которая поможет нам определить, оптимальны ли параметры, которая является целевой функцией.
Как определяется целевая функция? Используя наш пример выше, мы хотим судить, есть ли у пациента рак Предположим, мы обработали значение y^i приведенной выше линейной модели и уменьшили его до значений от 0 до 1. В наших 100 000 обучающих данных метка пациентов с раком равна 1, а метка пациентов без рака — 0. Очевидно, что лучший параметр должен иметь возможность прогнозировать всех пациентов с раком как 1, а всех пациентов без рака. быть 0. Это почти идеальный параметр! Следовательно, наша целевая функция может быть установлена как функция MSE: obj = ∑_i (sigmoid(∑_jθ_j*x_ij) - y_i)^2
Смысл вышеприведенной функции состоит в том, чтобы уменьшить значение, предсказанное моделью, от 0 до 1 для i-х данных, затем сделать разницу с истинным значением метки (0 и 1) данных, а затем возвести его в квадрат. Чем больше значение в квадрате, тем неточнее прогноз, который является ошибкой прогноза модели Наконец, мы суммируем ошибки прогноза модели для 100 000 единиц данных. Получается мера того, насколько хорошим или плохим является прогноз для определенного набора параметров.
Это действительно идеально? нет. Приведенная выше целевая функция оценивает только то, насколько хороши параметры для обучающих данных, и не оценивает эффективность этого набора параметров, когда мы используем модель для прогнозирования. То есть параметры, которые хороши для обучающих данных, могут не подходить для прогнозирования. Зачем?
- Во-первых, в 100 000 данных есть ошибки.
- Во-вторых, 100 000 единиц данных могут не охватывать все типы выборок.Для крайнего примера, если 100 000 единиц данных являются результатами осмотра людей старше 60 лет, мы можем использовать обученную модель для прогнозирования 10-летнего ребенка. , Может быть неточным.
Итак, как вы оцениваете, хорош или плох набор параметров для предсказания? Ответ - узнать!
Разве это не бессмысленно.
это правда. Верные предсказания — самые авторитетные суждения. Но есть еще кое-что, что мы можем сделать, и это регуляризация.
Так называемая регуляризация заключается в наложении определенного контроля на параметры, чтобы предотвратить их переход к крайним значениям. Возьмем приведенный выше пример, если из 100 000 единиц данных все пациенты с раком — это пожилые люди старше 60 лет, а пациенты, у которых нет рака, — молодые люди в возрасте до 30 лет, одним из результатов теста является плотность кости. , Обычно пожилые люди имеют низкую плотность костей, а молодые люди имеют высокую плотность костей. Тогда модель, которую мы изучили, вероятно, будет такой. Параметр θ_j, соответствующий плотности кости, установлен очень большим, а другие параметры очень маленькими. Короче говоря, модель имеет тенденцию использовать этот результат теста для оценки пациента. Заболеть ли раком, потому что это сведет к минимуму целевую функцию.
Любому проницательному глазу видно, что делать прогнозы с такими параметрами определенно нехорошо.
Регуляризация может помочь нам обойти такие проблемы.
Обычно используемой регуляризацией является регуляризация L2, которая представляет собой сумму квадратов всех параметров. Мы хотим этого и как можно меньше, пока модель имеет наилучшие прогнозы на обучающих данных.
Наконец, мы добавляем член регуляризации L2 к исходной целевой функции, чтобы получить окончательную целевую функцию:
Набор параметров, который минимизирует значение этой функции, является лучшим параметром, который мы ищем. Два элемента, содержащиеся в этом объекте, называютсяФункция потерь и срок регуляризации.
Обычный термин здесь в основном используется для контроля сложности модели.
Notes:
Выше мы намеренно опустили некоторые важные аспекты, чтобы все было как можно проще. Например, наш пример — классификация, но используемая функция потерь — MSE, которая обычно не используется.
Для задач регрессии нашей обычно используемой функцией потерь является MSE, то есть:
Для задач классификации нашей обычно используемой функцией потерь является логарифмическая функция потерь:
На первый взгляд, эта функция потерь странная, мы не можем не задаться вопросом, почему эта функция способна судить о качестве набора параметров на обучающих данных?
Мы используем приведенный выше пример, чтобы проиллюстрировать, что если есть выборка, метка которой равна 1, то есть y_i = 1, то в функции потерь этой выборки остается только левая часть, Поскольку y_i = 1, окончательная форма это:
yi с маленькой остроконечной шляпой на голове является прогнозируемым значением нашей модели.Очевидно, что чем больше значение, тем больше указанная выше функция стремится к 0. Когда yi стремится к бесконечности, значение потерь равно 0. Это соответствует нашим требованиям.
Точно так же аналогичный анализ можно провести и для образцов с yi=0.
Что касается того, как получается эта функция потерь, есть два способа: один — использовать LR, другой — использовать максимальную энтропию. Для конкретного процесса получения, пожалуйста, обратитесь к другим материалам.
2. хгбуст
Поскольку xgboost — это модель с учителем, наш первый вопрос: какова соответствующая модель xgboost?
Ответ — куча деревьев CART.
На этом этапе у нас могут снова возникнуть вопросы, что такое дерево CART? Пожалуйста, обратитесь к другой информации по этому вопросу, и в моем блоге есть соответствующие статьи. Тогда как группа деревьев делает предсказания? Ответ очень прост, то есть сложить предсказанные значения каждого дерева вместе как окончательное предсказанное значение, которое можно описать как простое и грубое.
На следующем изображении показан пример дерева CART и группы деревьев CART, используемых для оценки того, понравятся ли человеку компьютерные игры:
В нижней части второго рисунка показано, как делать прогнозы с помощью группы деревьев CART, просто складывая оценки прогнозов отдельных деревьев.
Почему xgboost использует дерево CART вместо обычного дерева решений? Проще говоря, для задач классификации, поскольку значение, соответствующее листовому узлу дерева CART, является фактическим показателем, а не определенной категорией, будет полезно реализовать эффективный алгоритм оптимизации. Одна из причин, по которой xgboost известен, заключается в том, что он точен, а другая — в том, что он быстрый Причина, почему он быстрый, заключается в том, что одной из причин выбора дерева CART является кредит.
Зная модель xgboost, нам нужно математически представить эту модель следующим образом:
Здесь K — количество деревьев, F — все возможные деревья CART, а f — конкретное дерево CART. Эта модель состоит из K деревьев CART. После того, как модель выражена, мы, естественно, хотим спросить, каковы параметры этой модели? Потому что мы знаем, что в параметрах содержится «знание». Во-вторых, какая целевая функция используется для оптимизации этих параметров?
Давайте сначала рассмотрим второй вопрос, целевую функцию модели, следующим образом:
Эта целевая функция также содержит две части: первая часть — функция потерь, а вторая часть — член регуляризации.Здесь член регуляризации получается путем добавления членов регуляризации деревьев K. Вам может быть любопытно, что регуляризация дерева Что такое предмет? Вы можете придержать свое любопытство на некоторое время, ответы будут позже. Сейчас кажется, что они все еще относительно абстрактны, не волнуйтесь, они будут конкретизированы один за другим позже.
3. Обучить xgboost
Выше мы получили модель xgboost и ее целевую функцию, далее задача обучения заключается в поиске наилучшей группы параметров путем минимизации целевой функции.
Вопрос где параметры?
Естественно думать, что модель xgboost состоит из деревьев CART, и параметры, естественно, существуют в каждом дереве CART. Итак, с точки зрения одного дерева CART, каковы его параметры? Согласно введению дерева CART выше, мы знаем, что для определения дерева CART необходимо определить две части. Первая часть - это структура дерева. Эта структура отвечает за сопоставление выборки с определенным конечным узлом, который по сути является функцией. Вторая часть — это оценка каждого конечного узла.
Вроде беда, надо сказать, что в качестве параметра используется оценка листового узла, это еще нормально, но как насчет структуры дерева в качестве параметра? А мы еще не дерево, а К деревьев!
Представим себе, что если структура K деревьев определена, то остальная часть всей модели представляет собой значение листовых узлов всех K деревьев, а член регуляризации модели также может быть задан суммой квадратов значений каждого листового узла. На данный момент вся целевая функция фактически является функцией значений всех листовых узлов K-дерева, и мы можем использовать градиентный спуск или стохастический градиентный спуск для оптимизации целевой функции. Теперь этот метод не работает, и мы должны найти другой путь.
4. Дополнительное обучение
Так называемое аддитивное обучение — это, по сути, метаалгоритм, применимый ко всем аддитивным моделям, и это эвристический алгоритм. По поводу этого алгоритма у меня есть подробное введение в другой статье про GBDT, которое здесь повторяться не буду, для незнакомых друзей можете глянуть. При аддитивном обучении наша цель больше не состоит в том, чтобы напрямую оптимизировать всю целевую функцию, которая, как мы показали, неработоспособна. Вместо этого целевая функция оптимизируется поэтапно, сначала оптимизируя первое дерево, а затем оптимизируя второе дерево, пока не будут оптимизированы K деревьев. Весь процесс показан на рисунке ниже:
На шаге t мы добавили оптимальное дерево CART f_t Откуда взялось это оптимальное дерево CART f_t? Очень просто, это дерево CART с наименьшей целевой функцией, основанное на существующем дереве t-1, как показано на следующем рисунке:
Константа на приведенном выше рисунке — это сложность первого дерева t-1. Если мы потерпим некоторое время, мы будем знать, как измерить сложность дерева. Пока игнорируем ее.
Если мы используем функцию потерь MSE, то приведенное выше выражение станет таким:
Эта формула очень красивая, потому что она содержит линейную и квадратичную формы f_t(x_i), а коэффициенты линейных членов являются остатками. Вам может быть интересно, почему линейные и квадратичные формулы красивы, потому что это обеспечит много удобства для нашей последующей оптимизации, и вы поймете, когда будете двигаться дальше.
Уведомление:Что такое f_t(x_i)? На самом деле это значение конечного узла f_t. Как мы упоминали ранее, значение конечного узла можно использовать в качестве параметра модели.
Но для других функций потерь мы, возможно, не сможем получить такую красивую формулу, поэтому для общей функции потерь нам нужно расширить ее до второго порядка Тейлора, как показано ниже:
в:
Здесь необходимо уточнить значение gi и hi. Как вы понимаете ги? Существует ли существующее дерево t-1? Модель, состоящая из t-1 деревьев, имеет прогнозируемое значение y^i для i-й обучающей выборки, верно? Между этим y^i и реальной меткой yi i-го образца должен быть разрыв, верно? Этот разрыв можно измерить функцией потерь l(yi, y^i), верно? Теперь вы уже знаете значение gi и hi, верно?
Если вы все еще чувствуете себя абстрактно, давайте рассмотрим конкретный пример Предположим, мы оптимизируем 11-е дерево CART, что означает, что были определены первые 10 деревьев CART. Прогнозируемое значение этих 10 деревьев для выборки (x_i, y_i=1) равно y^i=-1, если предположить, что сейчас мы проводим классификацию, наша функция потерь равна
Когда y_i=1, функция потерь становится
Мы можем найти градиент этой функции потерь по отношению к y^i следующим образом:
Подставьте y^i =-1 в приведенную выше формулу, чтобы вычислить -0,27. Это -0,27 и есть g_i. Значение отрицательное, то есть, если мы хотим уменьшить потери предсказания этих 10 деревьев в этой точке выборки, мы должны пойти в направлении, противоположном градиенту, то есть увеличить значение y^i , чтобы оно имеет тенденцию быть положительным, потому что наш y_i=1 положителен.
Давай, ответь на небольшой вопрос, сколько gi и hi нужно рассчитать при оптимизации t-го дерева? Ну да, их по N, где N — количество обучающих выборок. Если имеется 100 000 выборок, при оптимизации t-го дерева необходимо рассчитать 100 000 gi и hi. Это похоже на хлопоты, не так ли? Но подумайте еще раз, нет ли связи между этими 100 000 ги? Возможно ли параллельное вычисление? Умник, вы, должно быть, снова почувствовали, почему xgboost такой быстрый!
Хорошо, теперь давайте рассмотрим эту формулу, какие константы и какие переменные. В конце формулы есть постоянное слагаемое, как вы, наверное, догадались, это слагаемое регуляризации первых t-1 деревьев. l(yi, yi^t-1) также является постоянным членом. Остальные три переменных члена — это линейные и квадратичные члены t-го дерева CART и члены регуляризации всего дерева. Еще раз, так называемые линейное и квадратичное выражения дерева здесь на самом деле являются линейным и квадратным выражениями значения определенного листового узла.
Наша цель - минимизировать эту целевую функцию. Постоянные члены явно бесполезны. Удалим их и получится следующее:
Хорошо, теперь мы можем ответить на предыдущий вопрос, почему линейные и квадратичные формы выглядят так красиво. Потому что коэффициенты этих линейных и квадратных выражений равны gi и hi, а gi и hi можно вычислять параллельно. Более того, gi и hi не зависят от вида функции потерь, если функция потерь является квадратично дифференцируемой. Что хорошего в этом? Преимущество заключается в том, что xgboost может поддерживать пользовательские функции потерь, если он может удовлетворять квадратичной дифференцируемости. Сильнее моего брата, верно?
5. Срок регуляризации модели
Вышеупомянутая формула уже очень красивая, но Ω(ft) за ней все еще облачный покров, что неясно. Теперь давайте определим, как измерить член регуляризации дерева. В этом вопросе нет объективного стандарта, и мнения могут различаться. С этой целью мы сначала определим дерево CART другим способом, следующим образом:
Это определение необходимо объяснить.Во-первых, дерево имеет листовые узлы T. Значения этих конечных узлов T формируют T-мерный вектор w, а q(x) — это отображение, используемое для сопоставления выборок от 1 до T. Определенное значение, то есть присвоение его определенному конечному узлу, q(x) фактически представляет собой структуру дерева CART. w_q(x), естественно, является предсказанным значением дерева для выборки x.
В этом определении xgboost использует следующий термин регуляризации:
Уведомление:Здесь появляются γ и λ, которые определяются самим xgboost.При использовании xgboost можно задать их значения.Очевидно, чем больше γ, тем больше хочется получить дерево с простой структурой, т.к. больше листовых узлов, тем больше штраф для дерева. Чем больше λ, тем больше мы хотим получить дерево с простой структурой.
Почему xgboost выбирает такой термин регуляризации? Это просто, так легко использовать! Эффект действительно хороший.
6. Станьте свидетелем момента чуда
На данный момент наша цель оптимизации для t-го дерева очень ясна.Давайте сделаем следующую его деформацию.Пожалуйста, держите глаза открытыми и сконцентрируйтесь:
Вы должны остановиться здесь и испытать это тщательно. Что означает Ij? Он представляет набор, каждое значение в наборе представляет собой порядковый номер обучающей выборки, а весь набор представляет собой обучающую выборку, назначенную j-му листовому узлу t-м деревом CART. Поняв это, глядя на это преобразование, на самом деле это изменение порядка внутреннего и внешнего суммирования. Если у вас все еще есть трудности, пожалуйста, оставьте комментарий.
Далее, мы можем сделать следующее упрощение:
Среди них Gj и Hj не требуют пояснений.
Для некоторой структуры t-го CART-дерева (представленного q(x)) все Gj и Hj определены. Более того, значения wj каждого листового узла в приведенной выше формуле не зависят друг от друга. Приведенная выше формула на самом деле представляет собой простую квадратичную формулу, мы можем легко найти оптимальное значение каждого листового узла и значение целевой функции в это время. Следующее:
Что означает obj*? Он показывает, насколько хорошо устроена структура дерева, чем меньше значение, тем лучше структура! Другими словами, это мера качества структуры t-го дерева CART. Примечание~Примечание~Примечание~, это значение используется только для измерения качества структуры и не имеет ничего общего со значением конечного узла. Зачем? Пожалуйста, внимательно посмотрите на процесс получения obj*. obj* относится только к Gj, Hj и T, и они связаны только со структурой дерева (q(x)), и не имеют ничего общего со значением конечного узла. Как показано ниже:
Примечание. Здесь мы даем интуитивную интерпретацию w * _j, чтобы мы могли получить перцептивные знания. Предположим, что листовому узлу j назначена только одна выборка. Тогда w*_j становится таким:
Эта формула говорит нам, что оптимальное значение w * _j — это просто отрицательный градиент, умноженный на весовой коэффициент, что аналогично скорости обучения при стохастическом градиентном спуске. Наблюдая за этим весовым коэффициентом, мы обнаруживаем, что чем больше h_j, тем меньше коэффициент, то есть меньше скорость обучения. Что означает больший h_j? Это означает, что градиент изменяется очень резко вокруг этой точки.Возможно, градиент изменяется с небольшим изменением от 10000 до 1. Поэтому в это время, когда мы используем обратное обновление градиента, шаги должны быть маленькими и маленькими, то есть весовой коэффициент должен быть меньше.
7. Найдите оптимальную древовидную структуру
Что ж, с критериями оценки структуры дерева мы можем сначала найти лучшую структуру дерева.После того, как это определено, значение лучшего листового узла фактически было найдено выше.
Проблема в том, что структура дерева практически бесконечна, замерить качество их по одному, а потом выбрать лучшее, заведомо нереально. Итак, нам все еще нужно принять небольшую стратегию, которая заключается в постепенном изучении лучшей древовидной структуры. Это то же самое, как мы разлагаем модель K-дерева на дерево для обучения, но из дерева в слой узлов. Если вы все еще немного запутались в это время, не беда, давайте посмотрим на конкретный процесс обучения.
Возьмем пример оценки того, нравятся ли человеку компьютерные игры, упомянутые выше. Простейшей древовидной структурой является дерево узлов. Мы можем вычислить, насколько хорошим или плохим является это одноузловое дерево obj*. Допустим, теперь мы хотим разветвить это одноузловое дерево по возрасту, нам нужно знать:
1. Справедливо ли оно по возрасту, т. е. снижается ли значение obj
2. Если его можно разделить, какой возраст следует использовать для его разделения.
Чтобы ответить на два вышеуказанных вопроса, мы можем отсортировать эту семью из пяти человек по возрасту. Как показано ниже:
Сканируя слева направо по этому графику, мы можем найти все точки сегментации. Для каждой определенной точки сегментации мы измеряем качество сегментации следующим образом:
Это усиление на самом деле является obj* одного узла минус дерево obj* двух узлов после разделения.Если усиление положительно и значение больше, это означает, что obj* после разделения меньше, чем obj* из одного узла, то тем больше стоит разделить. В то же время мы также можем заметить, что если левая половина Gain меньше, чем γ справа, то Gain имеет отрицательное значение, что указывает на то, что obj становится больше после сегментации. γ здесь фактически является критическим значением, и чем больше его значение, тем строже требование к уменьшению obj после сегментации. Это значение также можно установить в xgboost.
После завершения сканирования мы можем определить, нужно ли разделять, и если разделить, рекурсивно вызвать процесс разделения для двух разделенных узлов, и мы можем получить относительно хорошую древовидную структуру.
Уведомление:Операция сегментации xgboost отличается от обычного процесса сегментации дерева решений. Обычные деревья решений не учитывают сложность дерева при разбиении, а полагаются на последующие операции сокращения для контроля. xgboost уже учел сложность дерева при разбиении, что является параметром γ. Поэтому он не требует отдельной операции обрезки.
8. Готово
После того, как оптимальная структура дерева найдена, легко определить оптимальный конечный узел. Мы успешно нашли t-е дерево! Рассыпать цветы! ! !