Введение в повышение и AdaBoost

AdaBoost относится к ансамблевым методам обучения и имитирует принцип «Мудрости толпы»: модели, которые по отдельности показывают низкую эффективность, могут образовывать сильную модель при объединении.

Исследование Массачусетского технологического института [Diz21], опубликованное в 2021 году, описывает, как толпа способна распознавать фейковые новости. Без фоновых знаний или проверки фактов людям часто бывает трудно надежно идентифицировать фальшивые новости. Тем не менее, основываясь на нашем опыте, мы обычно можем, по крайней мере, указать тенденцию, которая обычно работает лучше, чем случайное угадывание. Если мы хотим знать, описывает ли данный заголовок правду или содержит фальшивые новости, мы можем просто опросить 100 случайных людей. Если более 50 говорят, что заголовок содержит фейковую новость, мы классифицируем ее как фейковую.

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

В ансамблевом обучении мы имитируем эту концепцию

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

В процессе обучения алгоритм AdaBoost также присваивает вес каждому слабому ученику. Таким образом, не каждый слабый ученик оказывает одинаковое влияние на предсказание модели ансамбля. Эта процедура расчета прогноза общей модели называется мягким голосованием. Если бы, с другой стороны, результаты каждого слабого ученика были бы одинаково взвешены, мы бы говорили об жестком голосовании.[Kum21]

Наряду с бэггингом, бустирование является наиболее известным ансамблевым методом.

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

Эта статья предназначена для того, чтобы шаг за шагом объяснить концепцию алгоритма AdaBoost. Для этой цели я искал простой набор данных классификации и нашел его с набором данных Взрослый. [Кох96]

Используемый набор данных

Набор данных «Взрослый» (также известный как набор данных «Доход переписи») используется для задач бинарной классификации. Набор данных содержит данные, описывающие людей, живущих в США, такие атрибуты, как пол, возраст, семейное положение и образование. Целевая переменная различает доходы ниже и выше 50 000 долларов в год.

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

https://github.com/polzerdo55862/Ada-Boost-Tutorial

Загрузите набор данных

Подготовьте набор данных

Я загружаю набор данных непосредственно из UCI и готовлю 3 простых бинарных функции:

  • Мужчина (да или нет)
  • ›40 часов в неделю (да или нет)
  • ›50 лет (да или нет)

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

1. Создайте первый WeakLearner: найдите пень с лучшей производительностью

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

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

Небольшое напоминание:

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

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



7 наиболее часто используемых алгоритмов регрессии и как выбрать правильный
Линейная и полиномиальная регрессия, RANSAC, дерево решений, случайный лес, гауссовский процесс и регрессия опорных векторов
em>в сторону datascience.com



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



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



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

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

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

Если подмножество (например, D_1) содержит k различных классов, вероятность того, что запись принадлежит классу i, может быть описана как p_i. [Kar22] На следующем изображении я описываю, как вычислить примесь Джинидля левого конечного узла.

Простой набор данных, который мы используем ниже, содержит только 10 экземпляров, 6 экземпляров описывают мужчин, 4 описывают женщин. Если мы посмотрим на подмножество D_1 с 6 «мужскими» образцами данных, мы увидим, что для 4 из 6 человек доход составляет 50 тысяч или меньше. Только за 2 записи доход выше 50к.

Таким образом, вероятность того, что случайная выборка из подмножества D_1 показывает доход выше 50 000, составляет 2/6 или 1/3, а вероятность того, что выборка показывает доход ниже 50 000 составляет 4/6 или 2/3. Таким образом, примесь Джини для выхода 1 (подмножество D_1) составляет 0,444.

Если мы сделаем то же самое для Листа 2, мы получим примесь 0,375.

Поскольку мы хотим сравнить производительность/индекс Джини культей с корневыми узлами «мужской», «> 40 часов» и «> 50 лет», мы сначала вычисляем взвешенную примесь Джини для корневого узла «мужской» как взвешенный сумма отдельных листьев.

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

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

Пень с характеристикой рабочего времени «>40 часов» показывает самый высокий коэффициент Джини и, таким образом, используется для построения первого пня.

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

2. Вычисление ошибки культи

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

Для расчета значения ошибки мы вводим веса для каждой записи набора данных. До формирования первого пня вес w каждого экземпляра равен w=1/n, где n соответствует размеру набора данных. Таким образом, сумма всех весов составляет 1.

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

Функция «calculate_error_for_chosen_stump» вычисляет взвешенную ошибку пня с элементом, который я выбрал в качестве корневого узла (selected_root_node_attribute).

3. Рассчитайте вес культи, «количество слов».

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

Мы рассчитываем количество скажем альфа следующим образом:

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

4. Регулировка веса образцов

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

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

  1. На левом графике показано масштабирование правильно классифицированных выборок.
  2. На правом графике показано масштабирование неправильно классифицированных выборок.
  3. После этого новые веса выборки нормализуются.

Рассчитайте и постройте новую шкалу весов:

Используйте только что определенную функцию для обновления весов выборки:

5. 2-й запуск: сформируйте новый загрузочный набор данных

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

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

Вы можете увидеть диапазон бинов на изображении, описанном как «cum_sum_low» — «cum_sum_upper».

Затем я выбираю случайное число от 0 до 1 и ищу диапазон/ячейку, в который попадает число. Я копирую идентифицированную запись и добавляю ее в новый набор данных.

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

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

С новым набором данных мы повторяем первые шаги:

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

Найдите корневой узел для второго пня:

6. Повторяйте процесс, пока не будет достигнуто условие завершения.

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

Сводка

Для t в 1….T:

  1. Найдите слабого ученика h_t(x), который максимизирует выигрыш Джини (в качестве альтернативы минимизирует ошибку неправильно классифицированных экземпляров)
  2. Рассчитайте взвешенную ошибку слабого ученика как сумму весов неправильно классифицированных образцов.
  3. Добавьте классификатор в модель ансамбля. Результатом модели является сводка результатов отдельных слабых учащихся. Слабые учащиеся взвешиваются с использованием «Количества высказываний»/взвешенной альфа-частоты ошибок, определенных выше.
  4. Обновить веса: с помощью ошибки взвешенной суммы мы рассчитываем альфа как «количество слов» только что сформированного слабого ученика.
  5. Мы используем эту альфу для масштабирования выборочных весов.
  6. Веса новой выборки нормализуются так, чтобы сумма весов снова равнялась 1.
  7. Используя новые веса, мы создаем новый набор данных, выбирая случайное число от 0 до 1 N раз, а затем добавляем образец данных в новый набор данных, который представляет набор данных.

7. Объедините слабых учеников в ансамблевую модель

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

  • Сделайте прогноз для каждого пня.

Для нашего простого примера 30-летнего человека, работающего 42 часа в неделю, результат первого пня — доход выше 50 тысяч, результат второго пня — доход ниже 50 тысяч.

  • Суммируйте количество слов для каждого выходного значения.

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

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

Краткое содержание

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

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

Спасибо за чтение!

Рекомендации

[Diz21] Питер Дизикес: Новости MIT, 2021. https://news.mit.edu/2021/crowd-source-fact-checking-0901

[Kar22] Фатих Карабибер: Gini Impurity, 2022. https://www.learndatasci.com/glossary/gini-impurity/

[Kum21] Аджитеш Кумар: Пример жесткого и мягкого классификатора голосования на Python, 2021 г. https://vitalflux.com/hard-vs-soft-voting-classifier-python-example/

[Koh96] Кохави, Ронни и Беккер, Барри: набор данных для взрослых, 1996 г. https://archive.ics.uci.edu/ml/datasets/adult (CC BY 4.0)

[Wiq20] Wiqaas: повышение уровня решения, 2020 г. https://github.com/wiqaaas/youtube/blob/master/Machine_Learning_from_Scratch/AdaBoosting/AdaBoosting_Decision_Tree.ipynb