Введение в методологию повышения и алгоритм AdaBoost

Введение в методологию повышения и алгоритм AdaBoost

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

Бэгинг

Бэггинг (или иногда его называют «самозагрузкой») — это стратегия в машинном обучении, которая в основном использует несколько алгоритмов обучения вместо одного. На самом деле это своего рода метод выборки, используемый для обучения нескольких алгоритмов обучения с использованием одного набора данных. В этой стратегии создается меньшее подмножество данных путем выборки всего набора данных с помощью метода замены. Затем для каждого меньшего подмножества данных мы обучаем классификатор и объединяем результаты этих классификаторов с помощью простой функции усреднения. Например, эти классификаторы могут представлять собой набор различных алгоритмов, таких как логистическая регрессия, SVM, нейронные сети, дерево решений и т. д., или набор классификаторов того же типа, например набор деревьев решений. Однако логика та же: вместо того, чтобы получать результат только от одного классификатора, теперь мы используем преимущества голосов нескольких классификаторов и создаем один совместный результат. Одним из самых известных алгоритмов, использующих стратегию мешков, является Random Forest. Фактически, RF-алгоритм делает шаг вперед по сравнению со стратегией упаковки, которая представляет собой случайную подвыборку по столбцам для выбора разделенных признаков-кандидатов для каждого листового узла. Это украшает деревья в лесу и повышает успеваемость. (Вид решения возможной проблемы переобучения в одном дереве решений)

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

Повышение

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

Различия:

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

P.S Платформы распределенных вычислений, такие как Spark или H2O, имеют в своих списках алгоритмов как Random Forest (пакеты), так и Gradient Boosting Model (GBM) (Boosting). Однако из-за различия № 5 логика распараллеливания этих двух алгоритмов отличается. При построении модели RF каждое поколение дерева может выполняться на разных узлах одновременно, тогда как распределенный GBM имеет параллельные задачи, такие как поиск оптимальных функций разделения для конечных узлов одного дерева. Более подробную информацию читайте в статье H2O по этой ссылке.

Конечно, между стратегиями «Бэгинг» и «Боинг» есть некоторое сходство:

Сходства:

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

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

Типы алгоритмов повышения

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

1. AdaBoost (адаптивное повышение)
2. Деревья, повышающие градиент
3. XGBoost

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

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

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

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

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

Алгоритм AdaBoost

AdaBoost — это первая реализация алгоритмов повышения в 1996 году компанией Freund & Schapire. Этот алгоритм повышения предназначен только для бинарной классификации, и его базовым классификатором является штамп решения. Помните, что базовый классификатор в алгоритме повышения называется «базовым классификатором». Этот базовый базовый классификатор для AdaBoost представляет собой штамп решения, который представляет собой дерево решений с одним уровнем. Основная цель алгоритма AdaBoost состоит в том, чтобы объединить эти действительно слабые одноуровневые классификаторы штампов решений и создать в конце сильный классификатор.

Помните, что повышающие алгоритмы придают больший вес экземплярам, ​​которые были неправильно классифицированы предыдущей моделью, и пытаются исправить прогнозы для этих экземпляров. Придание большего веса некоторым экземплярам означает, что применяемый штраф за неправильную классификацию в потерях при обучении для этих экземпляров намного выше. На рисунке ниже каждый раз, когда в систему добавляется штамп решения D1, D2 и D3, он фокусируется на неправильно классифицированных экземплярах на предыдущем этапе. Эти экземпляры показаны на рисунке крупнее, и каждая линия штампа решения нарисована, чтобы исправить прогнозы этих экземпляров в текущем раунде алгоритма повышения. В конце все штампы решений (Box1, Box2 и Box3) собираются и формируется окончательная модель (Box4).

Позвольте мне сначала дать псевдокод алгоритма, а затем объяснить технические детали.

Следовательно, на шаге 1 приведенного выше псевдокода изначально все веса экземпляров устанавливаются равными. Этот вес равен 1/N, где N — количество экземпляров в нашем обучающем наборе.

Все обучение выполняется на шаге 2 псевдокода. Цикл генерирует каждое дерево поэтапно, используя взвешенные экземпляры из предыдущего этапа. На шаге 2а во время подгонки классификатора к взвешенным обучающим данным штамп решения делит данные на два класса, фокусируясь на ранее неправильно классифицированных экземплярах. На шаге 2b вычисляется взвешенная ошибка самого нового дерева по неправильно классифицированным экземплярам. Это из-за функции «I» в формуле. Он дает 1 для неправильно классифицированных экземпляров и возвращает 0 для правильно классифицированных.

На шаге 2c мы вычисляем другое значение веса, но это вес не для экземпляров, а на самом деле вес самого нового дерева в формуле последнего шага, которая предназначена для комбинации классификаторов. Он рассчитывается с использованием взвешенной ошибки из шага 2b. Как видите, чем выше ошибка классификации дерева, тем ниже его вес. Это более разумный способ объединения голосов нескольких классификаторов для получения окончательного результата. Наконец, поскольку AdaBoost — это алгоритм, специально разработанный для бинарной классификации (1 или -1), знак взвешенной суммы голосов классификаторов вычисляется на шаге 3. Прогнозы делаются путем вычисления взвешенной суммы слабых классификаторов.

Поясню на примере, почему важна взвешенная сумма. Предположим, что у нас есть пять разных слабых классификаторов в нашем алгоритме AdaBoost, и они предсказывают 1,0, 1,0, -1,0, 1,0 и -1,0. Даже если окончательный прогноз кажется равным 1.0 по большинству голосов, он может быть получен иначе, если мы используем взвешенную сумму голосов. Предположим, что весовые коэффициенты (или иногда их называют «стадийными значениями») классификаторов равны 0,2, 0,5, 0,8, 0,2 и 0,9 соответственно. Когда мы вычисляем взвешенную сумму, она дает -0,8, что будет предсказанием ансамбля класса -1,0 для окончательного классификатора.

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

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

Однако система в целом должна минимизировать функцию потерь: L(y,f(x)) = exp(-yf(x)) Поскольку это поэтапный алгоритм, модель (m) полностью зависит от модели (m-1) . Следовательно, функция потерь может быть переписана в деталях, как показано ниже:

Наше новое аддитивное дерево-кандидат — G_m. Пока у нас есть m-1 деревьев в нашем алгоритме повышения, и теперь мы должны добавить дерево G_m с коэффициентом beta_m и попытаться минимизировать нашу функцию потерь. Фактически, этот бета-параметр совпадает с 'весом классификатора', который мы упоминаем в пояснительной части псевдокода.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

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

В этот момент у вас могут возникнуть некоторые вопросы. Если мы постепенно исправим ошибку неправильной классификации предыдущих моделей, то почему бы не получить точность, близкую к 100%. Если это возможно, означает ли это «переоснащение»? Итак, мы поговорим о факторе скорости обучения в следующей статье, которая отвечает на вопросы. В следующей статье я расскажу о модели повышения градиента, алгоритме XGBoost, о том, что происходит внутри этих алгоритмов и как настраивать параметры при использовании версии этих алгоритмов для R/Python.