Введение

Алгоритм классификации на основе адаптивного повышения (boosting)
AdaBoost, сокращение от Adaptive Boosting, – это мета-алгоритм статистической классификации, разработанный Йоавом Фрейндлом и Робертом Шапиром в 1995 году, удостоенный премии Гёделя в 2003 году за эту работу. Его можно использовать совместно со многими другими типами алгоритмов обучения для повышения эффективности. Результаты работы других алгоритмов обучения («слабых учеников») объединяются в виде взвешенной суммы, представляющей собой конечный результат усиленного классификатора. Обычно AdaBoost рассматривается для бинарной классификации, хотя его можно обобщить на несколько классов или ограниченные интервалы на вещественной прямой. AdaBoost адаптивен в том смысле, что последующие слабые ученики корректируются с учетом экземпляров, которые были неправильно классифицированы предыдущими классификаторами. В некоторых задачах он может быть менее подвержен переобучению, чем другие алгоритмы обучения. Отдельные ученики могут быть слабыми, но пока производительность каждого из них незначительно превосходит случайное угадывание, можно доказать, что итоговая модель сходится к сильному ученику. Хотя AdaBoost обычно используется для объединения слабых базовых учеников (например, деревьев решений глубины 1), было показано, что он также может эффективно объединять сильных базовых учеников (например, глубокие деревья решений), создавая еще более точную модель. Каждый алгоритм обучения, как правило, лучше подходит для определенных типов задач и обычно имеет множество различных параметров и конфигураций, которые необходимо настроить для достижения оптимальной производительности на наборе данных. AdaBoost (с деревьями решений в качестве слабых учеников) часто называют лучшим классификатором, готовым к использованию из коробки. При использовании с обучением деревьев решений информация, собранная на каждом этапе алгоритма AdaBoost об относительной «сложности» каждого обучающего примера, передается в алгоритм построения деревьев таким образом, что последующие деревья, как правило, сосредотачиваются на более сложных для классификации примерах.

Обучение

AdaBoost относится к конкретному методу обучения бустированного классификатора. Бустированный классификатор – это классификатор вида

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

Коэффициенты

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

Настоящий AdaBoost

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

Нежное AdaBoost

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

Преждевременное прекращение

Техника ускорения обработки бустированных классификаторов, известная как раннее завершение, заключается в тестировании каждого потенциального объекта лишь с тем количеством слоев финального классификатора, которое необходимо для достижения определенного порога уверенности. Это ускоряет вычисления в случаях, когда класс объекта можно легко определить. Одним из примеров такой схемы является фреймворк обнаружения объектов, предложенный Виолой и Джонсом: в задачах, где количество отрицательных примеров значительно превышает количество положительных, обучается каскад отдельных бустированных классификаторов. Выход каждого этапа каскада настроен таким образом, чтобы допустимая небольшая доля положительных примеров ошибочно классифицировалась как отрицательная, а все примеры, помеченные как отрицательные после каждого этапа, отбрасываются. Если на каждом этапе отфильтровывается 50% отрицательных примеров, то через весь классификатор проходит лишь небольшое количество объектов, что снижает вычислительные затраты. Этот метод впоследствии был обобщен, и была разработана формула для выбора оптимальных порогов на каждом этапе, позволяющая достичь желаемого уровня ложноположительных и ложноотрицательных срабатываний. В статистике, где AdaBoost чаще применяется к задачам умеренной размерности, ранняя остановка используется как стратегия для предотвращения переобучения. Для этого из обучающего набора выделяется отдельный валидационный набор, сравнивается производительность классификатора на обучающем и валидационном наборах, и обучение прекращается, если производительность на валидационном наборе начинает снижаться, даже если производительность на обучающем наборе продолжает улучшаться.

Полностью корректирующие алгоритмы

Для версий AdaBoost с методом наискорейшего спуска, где αt выбирается на каждом слое t для минимизации ошибки на тестовых данных, следующий добавленный слой считается максимально независимым от слоя t: маловероятно выбрать слабый классификатор t+1, похожий на классификатор t. Однако остаётся возможность того, что t+1 выдаёт информацию, аналогичную информации, полученной на каком-либо более раннем слое. Полностью корректирующие алгоритмы, такие как LPBoost, оптимизируют значение каждого коэффициента после каждого шага, так что новые добавленные слои всегда максимально независимы от каждого предыдущего слоя. Этого можно достичь с помощью обратной подгонки, линейного программирования или другим методом.

Обрезка

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