Алгоритм машинного обучения AdaBoost. Часть 1

Алгоритм AdaBoost

Здравствуйте и вновь добро пожаловать на занятия по теме «Машинное обучение с учителем на языке Python: ансамблевые методы».

В этой статье мы поговорим о бустинге (boosting) и познакомимся с одной из реализаций идеи бустинга – алгоритмом AdaBoost, рассмотрим аддитивное моделирование и функцию потерь.

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

Идея,лежащая в основе бустинга, очень отличается от бэггинга и метода случайноголеса. Напомним, что в этих случаях нам требовалась модель с малым смещением ивысокой дисперсией. При бустинге же мы в действительности используем модели свысоким смещением, в терминах бустинга – «слабых учеников». Слабые ученики –это те, у которых точность классификации не намного выше случайного угадывания,порядка 50-60%. Позже мы покажем эмпирическим путём, что даже после ансамблированиядисперсия остаётся малой (другими словами, остаётся малая ошибка проверки), аансамбль не скатывается в переобученность даже при добавлении деревьев.

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

Какже создать или найти «слабых учеников»? Типичный способ в бустинге –использовать деревья решений с максимальной глубиной, равной 1, – их ещёназывают «пнями решений». Пень решений может иметь только один разделитель содной размерностью. Другими словами, в этом случае мы просто делим пространствопополам для каждого дерева, и на самом деле потрясающе, что их комбинация можетв итоге дать очень хороший классификатор. Другой способ – использовать линейныйклассификатор вроде логистической регрессии. Дополнительным бонусом отиспользования столь простых моделей является то обстоятельство, что ониневероятно быстро обучаются, а потому можно быстро обучить ансамбль из тысячдеревьев.

Валгоритме AdaBoost, к которому мы вскоре перейдём, естьпара деталей, которые необходимо отметить. Прежде всего в AdaBoost в качестве целевых переменныхиспользуются +1 и -1, а не 0 и 1. Почему так, станет ясно, когда мыпознакомимся с алгоритмом. Таким образом, если мы будем использоватьлогистическую регрессию, нам придётся переформатировать результат, умножив егона 2 и вычтя 1. Конечный результат работы AdaBoostимеет вид

Какже создать или найти «слабых учеников»? Типичный способ в бустинге –использовать деревья решений с максимальной глубиной, равной 1, – их ещёназывают «пнями решений». Пень решений может иметь только один разделитель содной размерностью. Другими словами, в этом случае мы просто делим пространствопополам для каждого дерева, и на самом деле потрясающе, что их комбинация можетв итоге дать очень хороший классификатор. Другой способ – использовать линейныйклассификатор вроде логистической регрессии. Дополнительным бонусом отиспользования столь простых моделей является то обстоятельство, что ониневероятно быстро обучаются, а потому можно быстро обучить ансамбль из тысячдеревьев.

Валгоритме AdaBoost, к которому мы вскоре перейдём, естьпара деталей, которые необходимо отметить. Прежде всего в AdaBoost в качестве целевых переменныхиспользуются +1 и -1, а не 0 и 1. Почему так, станет ясно, когда мыпознакомимся с алгоритмом. Таким образом, если мы будем использоватьлогистическую регрессию, нам придётся переформатировать результат, умножив егона 2 и вычтя 1. Конечный результат работы AdaBoostимеет вид

где FM – ансамблевая модель с M базовыхучеников, а fMM-йученик. Поскольку целевыми переменными являются -1 и +1, то граница принятиярешения лежит в нуле, поэтому мы берём знак, чтобы определить окончательныйпрогноз. Кроме того, для обозначения весовых коэффициентов каждого изклассификаторов обычно используется символ α,поскольку wнам понадобится для другого, в частности, для того чтобы показать, наскольковажен тот или иной пример.

Перейдёмтеперь к собственно алгоритму AdaBoost. Суть его втом, что мы каждый раз добавляем по одной базовой модели – это называетсяаддитивным моделированием. Мы обучаем базовую модель на всём объёме учебныхданных, что значит, что тут нет никаких повторных выборок или бутстрепа.Разница между этим и другими изучавшимися нами алгоритмами в том, что мыпридадим весовой коэффициент каждому примеру, обозначив его через wi, где i пробегаетзначения от 1 до N.При этом после каждого выполнения цикла мы модифицируем wi. Изначально всеwi равны, но еслидля пары (xi,yi) прогноз будетошибочным, то wiв этом прогоне увеличивается. Таким образом базовая модель «узнаёт», какой изпримеров является более важным.

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

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

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

Рассмотримтеперь алгоритм AdaBoost подробнее, вчастности, как вычислить всё то, о чём говорилось ранее. Первый этап – дать wi равномерноераспределение, чтобы каждый пример имел одинаковую важность. Затем мы запускаемцикл, в котором создаём базовую модель fM(x):

инициируем w[i] = 1/N для i=1..N

for m=1..M:

    установить f_m(x) с весовымикоэффициентами примеров w[i]

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

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

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

Такимобразом, по сути если модель более правильная, то она получит больший весовой коэффициент α. Обратите внимание, что суммированиепо wпри вычислении ошибки ε, не являетсянеобходимым, если при этом проводится нормализация w, как это показано на предпоследнем этапе. Я оставилего для полноты картины, но вы должны помнить, что ошибка всегда будет числоммежду 0 и 1.

Далее мы обновляем w:

Какможно видеть, если ответ правильный, то yi и fm(xi) имеют одинаковый знак, поэтому wi уменьшается.Если же ответ неправильный, то yi и fm(xi) имеют разные знаки, а потому wi увеличивается.Именно поэтому необходимо, чтобы целевые переменные были равны либо -1, либо+1. Нам также необходимо нормализовать w, поскольку рассматриваем его как распределениевероятностей:

Ипоследний этап – это, конечно, сохранить αm и fm(x).

Каквы могли заметить, алгоритм AdaBoost узкоспециализирован для двоичной классификации, поскольку требует двух классов созначениями -1 и +1. Есть литература, в которой обсуждается видоизменение AdaBoost для мультиклассовой классификации ирегрессии, но, как обычно, наша цель состоит в том, чтобы понять главную идею.Если же вы в конце концов пожелаете использовать AdaBoostдля мультиклассовой классификации или регрессии, то в библиотеке SciKit Learnуже содержится соответствующий инструмент.

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

Аддитивное моделирование

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

Итак, общий алгоритм прямого ступенчатого аддитивного моделирования состоит в следующем. При рассмотрении я советую попытаться найти связь с тем, что делает алгоритм AdaBoost. Итак, первый этап – цикл от 1 до M. Далее мы создаём базовую модель и находим лучшее α и лучшие параметры модели, чтобы минимизировать полную модель:

Ипоследний этап – это, конечно, сохранить αm и fm(x).

Каквы могли заметить, алгоритм AdaBoost узкоспециализирован для двоичной классификации, поскольку требует двух классов созначениями -1 и +1. Есть литература, в которой обсуждается видоизменение AdaBoost для мультиклассовой классификации ирегрессии, но, как обычно, наша цель состоит в том, чтобы понять главную идею.Если же вы в конце концов пожелаете использовать AdaBoostдля мультиклассовой классификации или регрессии, то в библиотеке SciKit Learnуже содержится соответствующий инструмент.

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

Аддитивное моделирование

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

Итак, общий алгоритм прямого ступенчатого аддитивного моделирования состоит в следующем. При рассмотрении я советую попытаться найти связь с тем, что делает алгоритм AdaBoost. Итак, первый этап – цикл от 1 до M. Далее мы создаём базовую модель и находим лучшее α и лучшие параметры модели, чтобы минимизировать полную модель:

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

Последнийэтап в цикле – добавить данную взвешенную модель к полной модели.

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

И последнее замечание. Под F понимается полный ансамбль, а под f – одна базовая модель.

Функция потерь AdaBoost. Экспоненциальная функция потерь

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

Итак,определим экспоненциальную функцию потерь. У неё два аргумента – y, представляющеесобой целевую переменную, и f(x), являющуюся моделью. Сама функция имеетвид

Какможно видеть, если y и f(x) имеют одинаковые знаки, то функциябудет малой, тогда как если разные – то большой.

Крометого, она имеет тот же «асимптотический эффект», что и кросс-энтропийнаяфункция. Рассмотрим положительный класс, то есть когда y = 1 в случаекросс-энтропийной функции. Напомним, что в случае кросс-энтропийной функции илогистической регрессии входной аргумент сигмоиды, который называется логитом, равенбесконечности, если значение сигмоиды равно 1. В противном случае мы можемподобраться очень близко к единице, но не достичь её.

Пусть,например, результатом логистической регрессии является f(x) = 0,9. Этозначит, что логит будет равен

Какможно видеть, если y и f(x) имеют одинаковые знаки, то функциябудет малой, тогда как если разные – то большой.

Крометого, она имеет тот же «асимптотический эффект», что и кросс-энтропийнаяфункция. Рассмотрим положительный класс, то есть когда y = 1 в случаекросс-энтропийной функции. Напомним, что в случае кросс-энтропийной функции илогистической регрессии входной аргумент сигмоиды, который называется логитом, равенбесконечности, если значение сигмоиды равно 1. В противном случае мы можемподобраться очень близко к единице, но не достичь её.

Пусть,например, результатом логистической регрессии является f(x) = 0,9. Этозначит, что логит будет равен

Еслиже f(x) = 0,99, то логитравен 4,6.

Именнопоэтому для классификации и не используется функция квадратов ошибок. Если f(x) находится вправильной стороне от y, то совершенно не важно, насколько оно далеко от y, – всё равноэто приводит к правильному прогнозу. В этом отличие от функции квадратовошибок, для которой не существенно, по какую сторону от y находится f(x) – чем дальше отy, тем большеошибка.

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

Начнёмс аддитивной функции затрат, показанной в предыдущей лекции. Напомню, что Fm означает полнуюансамблевую модель с m базовых моделей, а fm означает m-ю базовую модель.Имеем:

Подставиввыражение для L,получим

Далеераскроем члены в экспоненте:

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

Чтобыпоказать, что это так, необходимо вспомнить правило обновления wi. Действительно,wi на m-й итерации равно

Чтобыпоказать, что это так, необходимо вспомнить правило обновления wi. Действительно,wi на m-й итерации равно

Итак,мы воспроизвели наше первое правило обновления алгоритма AdaBoost – мы теперь знаем, как обновлять wi, исходя из егопредыдущего значения. Вернёмся теперь к функции затрат

Следующийфокус заключается в том, чтобы понять, что y*f всегда будетравно +1 или -1 – в зависимости от того, правильным является прогноз или нет.Тогда мы можем разделить сумму на два члена с правильными и неправильнымиответами:

Следующийфокус заключается в том, чтобы понять, что y*f всегда будетравно +1 или -1 – в зависимости от того, правильным является прогноз или нет.Тогда мы можем разделить сумму на два члена с правильными и неправильнымиответами:

Упростимвыражение, введя новые обозначения. Обозначим первую сумму, представляющуювзвешенное число правильных ответов, через A, а вторую сумму, представляющую взвешенное числоошибок, – через B.Кроме того, уберём индекс m, поскольку он тут только мешает. Получим новуюфункцию затрат:

Что дальше? Дальше идёт мой любимый этап, без которого никогда не обходится: мы берём производную, приравниваем её к нулю и решаем относительно α. В результате получаем

Что дальше? Дальше идёт мой любимый этап, без которого никогда не обходится: мы берём производную, приравниваем её к нулю и решаем относительно α. В результате получаем

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

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

Мы рассмотрели экспоненциальную функцию потерь как правомерную функцию потерь для алгоритма AdaBoost, где целевые переменные принимают значения -1 и +1. Затем мы подставили её в уравнение аддитивного моделирования для нахождения следующих α. Преобразовывая функцию потерь, мы воспроизвели уравнение обновления для wi – весовых коэффициентов примеров, показывающих, насколько важным является каждый пример для каждой базовой модели. К тому же мы увидели, что рекурсивное определение wi целиком вписывается в эту структуру. Затем мы оптимизировали функцию потерь относительно α, для воспроизведения нашего уравнения для αm. Я нахожу последний этап – нахождение производной и приравнивание её к нулю для нахождения оптимальных параметров – наиболее интеллектуально увлекательным, поскольку он воспроизводит ту же структуру, что и многие другие модели, с которыми мы работали ранее, особенно перцептрон, линейная и логистическая регрессии и нейронные сети.

Андрей Никитенко
Андрей Никитенко
Задать вопрос эксперту
Понравилась статья? Поделить с друзьями:
Комментариев: 1
  1. Евгений

    Некоторые слова слиты – неудобночитать. а так – хорошо!