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

CatBoost - «относительно» новый пакет, разработанный исследователями Яндекса. Сейчас он довольно популярен, особенно в соревнованиях Kaggle, где он обычно превосходит другие библиотеки повышения градиентного дерева.

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

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

Вступление

Gradient Tree Boosting - один из лучших алгоритмов для работы со структурированными данными. Это семейство алгоритмов возникло на основе метода повышения, который является одной из самых мощных идей обучения, представленных за последние 25 лет. AdaBoost, представленный Йоавом Фройндом и Робертом Шапиром в 1997 году, был первым примером этого метода. Позже в том же году Лео Брейман понял, что повышение может быть переформулировано как задача оптимизации с соответствующей функцией стоимости, что породило градиентное повышение Джеромом Фридманом в 2001 году. С тех пор методы повышения с помощью деревьев увидели много новичков. , а именно и в порядке появления, XGBoost - eXtreme Gradient Boosting (2014), lightGBM (2016) и CatBoost (2017).

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

Кодирование категориальных переменных

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

Как вы, наверное, уже знаете, алгоритмы машинного обучения обрабатывают только числовые функции. Допустим, вы пытаетесь спрогнозировать отпускную цену подержанного автомобиля. Среди доступных функций у вас есть марка автомобиля (Toyota, Honda, Ford…). Теперь, чтобы использовать эту функцию (которая определенно повлияет на цену плавания) в вашем любимом алгоритме повышения градиента, вам нужно преобразовать бренд в числовое значение, потому что алгоритм должен отсортировать бренды, чтобы перечислить разделение возможности и найдите лучший.

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

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

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

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

Быстрое кодирование

Идея довольно проста. Вы заменяете категориальный объект фиктивными переменными (по одной для каждой отдельной категории). Фиктивная переменная - это переменная, которая указывает, присутствует ли определенный фактор (значение 1) или отсутствует (значение 0). Вы также можете решить не включать фиктивную переменную для одного из факторов.

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

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

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

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

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

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

Теперь давайте посмотрим, что произойдет, если мы остановимся только на 2 брендах (придерживаясь случая, когда отпускные цены распределены равномерно). Мы отображаем 3 разных сценария от одной крайности до другой:

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

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

Статистика градиента

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

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

Обратите внимание, что мы считаем остатки (y-) равными градиентам. Это справедливо только при выполнении регрессии с квадратом потерь ошибок. Если используется другой убыток, мы не можем сделать то же предположение (мы полагаемся на псевдо-остатки), но идея в точности та же.

Итак, давайте наглядно объясним, что происходит. Допустим, мы строим слабого ученика (дерево регрессии) и уже выбрали числовой признак «Пробег» для первого разбиения:

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

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

Давайте увеличим левую часть, чтобы увидеть, что произошло:

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

(i) время вычисления, так как он вычисляет статистику для каждого категориального значения на каждом шаге
(ii) потребление памяти для хранения, какая категория принадлежит какому узлу для каждого разбиения на основе категориальной особенности

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

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

Целевая статистика

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

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

В нашем примере (регрессия) это даст:

Итак, допустим, у нас есть следующие наблюдения:

Кодирование произведет следующие вычисления:

Что в свою очередь даст следующий результат:

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

Этот метод является статистически надежным и сохраняет большую часть предсказательной силы категориальной переменной. Но это не идеально. Одна из распространенных проблем заключается в том, что оценка недостаточно надежна для категорий с низкой мощностью. Чтобы решить эту проблему, мы обычно добавляем взвешенное априорное значение. Категория k конкретной категориальной переменной x затем заменяется следующим значением:

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

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

Но этот метод страдает от состояния, известного как утечка цели. Использование только цели для кодирования переменной обязательно приводит к ситуации, когда усвоенная взаимосвязь переоценивается идиосинкразиями обучающего набора. Распределение категориальной переменной, обусловленное целевым значением (x | y), вычисленным с использованием обучающего набора, не обязательно будет таким же, если вычислено с использованием тестового набора. Это приводит к сдвигу прогноза. Чтобы проиллюстрировать эту проблему, мы воспользуемся крайним примером из статьи CatBoost.

Допустим, мы пытаемся решить проблему бинарной классификации (будет ли эта машина продана в следующем месяце?). У нас есть только один предсказатель - марка автомобиля. Чтобы гарантировать, что между целью и объектом нет абсолютно никакой связи, мы присваиваем метку (0 или 1) случайно с помощью испытаний Бернулли с вероятностью p = 0,5. Кроме того, мы гарантируем, что для каждого наблюдения существует один уникальный бренд. Ясно, что нет абсолютно никакого способа придумать модель прогнозирования лучше, чем случайное предположение. Давайте посмотрим, что произойдет с, скажем, 10 наблюдениями:

Чтобы упростить наш пример, мы не использовали априорную схему кодирования. Закодированный объект получает значение 0 или 1 в зависимости от связанной цели. Но что случилось? Что ж, у нас получился идеальный раскол. Снижение примесей (энтропии) было максимальным, потому что все наблюдения в листьях имеют одну и ту же целевую метку. Таким образом, точность предсказания на обучающем наборе составляет 1,0 (мы всегда предсказывали правильную метку). Но как только мы переключимся на тестовый набор, учитывая тот факт, что целевые метки назначаются случайным образом, частота ошибок будет намного выше и, вероятно, будет равна случайному угадыванию.

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

K-кратное целевое кодирование

Этот метод, введенный для смягчения проблемы утечки функций, уходит своими корнями в хорошо известную процедуру перекрестной проверки (которая была изобретена для борьбы с переобучением). Итак, мы делим набор данных на K складок. Мы перебираем каждую свертку и вычисляем целевую статистику для текущей свертки, используя данные из оставшейся свертки K-1. Частный случай этого метода называется целевым кодированием Holdout, когда K = 2. Недостатки этого метода заключаются в том, что он может значительно увеличить время обучения, и мы не используем полный набор данных для вычисления статистики, которая увеличивает смещение.

Целевая кодировка с исключением одного

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

Можно было подумать, что этот метод предотвращает утечку цели. Но на самом деле это не так. Продемонстрируем это на простом примере. Итак, предположим, что мы вернулись к нашей проблеме бинарной классификации с 10 наблюдениями. На этот раз у нас есть 7 положительных наблюдений и 3 отрицательных, но, что наиболее важно, категориальная переменная имеет только один уникальный бренд. Мы знаем, что такая функция бесполезна, потому что у нее нет предсказательной силы. Проблема здесь в том, что когда мы вычисляем статистику, у нас есть только два разных случая: либо мы оставляем 1, либо 0. Таким образом, единственными двумя возможными значениями для закодированных функций являются: (7–1) / 10, когда мы оставляем 1, и (7–0) / 10, когда мы оставляем 0. Получаем следующий результат:

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

Анализ утечки

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

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

Упорядоченная статистика цели

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

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

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

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

Теперь, когда перестановка выполнена, как вычисляется категориальная статистика?

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

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

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

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

  • curCount - общее количество объектов в наборе обучающих данных с текущим значением категориальной характеристики.
  • maxCount - количество объектов в наборе обучающих данных с наиболее частым значением функции.
  • Prior - число (константа), определяемое начальными параметрами.

Определение curCount из документации, на мой взгляд, не очень ясное, поэтому мы рассмотрим пример, чтобы понять его (мы установили до 0,05).

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

  • countInClass = 1 (количество раз, в прошлых обучающих данных, цель была равна 1, когда категориальный признак был равен Toyota)
  • maxCount = 2 (общее количество брендов Toyota в прошлых данных обучения)

Тогда статистика для этого пятого наблюдения равна (1 + 0,05) / (2 + 1) = 0,35.

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

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

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

Авторы пришли к выводу, что количество перестановок влияет на эффективность кодирования, но улучшение, которое мы получаем при увеличении количества перестановок, незначительно.

Заключение

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

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

Заключительное примечание: вы можете найти реализации описанных выше процедур кодирования (включая CatBoost) с помощью этого пакета scitkit-learn contrib.

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