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

Реализация алгоритма AdaBoost

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

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

Если вы не хотите сами писать код, а лишь запустить его, то отыщите в репозитарии файл adaboost.py. В довесок к простому созданию и запуску алгоритма AdaBoost у нас будет и другая цель – понаблюдать за поведением ошибки и функции потерь проверочного набора при добавлении новых деревьев. Мы видели, что в случае случайного леса и бэггинга даже добавление новых деревьев не приводило к переобученности, и мы хотим узнать, обладает ли алгоритм AdaBoost этим же свойством. В отличие от метода случайного леса, AdaBoost не требует от нас переписывания части кода деревьев решений, поскольку API библиотеки SciKit Learn позволяет вставлять весовые коэффициенты примеров в функцию fit.

Итак, вначале идут наши обычные импорты: Numpy, Matplotlib, конечно же, DecisionTreeClassifier из SciKit Learn и функция get_data из файла rf_classification.

import numpy as np

import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier

from rf_classification import get_data

Далееопределим наш класс AdaBoost. Как можновидеть, в конструкторе только один параметр – количество учеников M.

class AdaBoost:

  def __init__(self, M):

    self.M = M

Следующей идёт функция fit. Мы определяем две переменные – models и alphas, хранящие пни решений и соответствующие им α. При этом используются списки, поскольку массивы Numpy предназначены прежде всего для хранения чисел, и нет никакого смысла сохранять в них объекты типа пней решений. Количество примеров у нас равно N, и мы равномерно распределяем наши весовые коэффициенты путём деления единицы на N. Далее мы запускаем цикл, работающий M раз. Ещё раз повторюсь, что этот код был бы невозможен, если бы библиотека SciKit Learn не предоставляла возможности вставлять весовые коэффициенты примеров. Если не эта возможность, нам бы пришлось  писать собственный код для алгоритма деревьев решений, и в таком случае, конечно же, код был бы намного сложнее.

Следующее– получение прогноза, поскольку необходимо вычислить наши взвешенные ошибки.Напомню, что нам нет нужды делить на сумму w, поскольку мы уже их нормализовали. Затем мывычисляем α. Данное решение несколькоотличается от того, что было приведено в псевдокоде, но, согласно правиламлогарифмирования, тоже правильно. Далее обновляем w. Проделав все вычисления, мы сохраняем их в models и alphas.

  def fit(self, X, Y):

    self.models= []

    self.alphas= []

    N, _ =X.shape

    W =np.ones(N) / N

    for m in xrange(self.M):

      tree =DecisionTreeClassifier(max_depth=1)

     tree.fit(X, Y, sample_weight=W)

      P =tree.predict(X)

      err =W.dot(P != Y)

      alpha =0.5*(np.log(1 – err) – np.log(err))

      W =W*np.exp(-alpha*Y*P) # vectorized form

      W = W /W.sum() # normalize so it sums to 1

     self.models.append(tree)

     self.alphas.append(alpha)

Далееидёт функция predict. Она не похожа на API библиотеки SciKitLearn, поскольку возвращает сразу две величины. Этосвязано с тем обстоятельством, что мы хотим одновременно увидеть и графикточности, и график экспоненциальной функции потерь. Для вычисления точности намдостаточно знака f(x), но для вычисления функции потерь намнужно само f(x), поэтому функция predict возвращает их обоих.

  def predict(self, X):

    # NOT likeSKLearn API

    # we wantaccuracy and exponential loss for plotting purposes

    N, _ =X.shape

    FX =np.zeros(N)

    for alpha,tree in zip(self.alphas, self.models):

      FX +=alpha*tree.predict(X)

    returnnp.sign(FX), FX

Следующей идёт функция score. Она похожа на функцию predict и даже на APIбиблиотеки SciKit Learn,но возвращает дополнительную величину, а именно значение потерь в дополнение кточности. Обратите внимание, что потери нормализованы по количеству примеров.Другими словами, мы берём среднее значение, а не сумму, что гарантирует, что изначение потерь, и точность будут иметь одинаковый масштаб, где-то между 0 и 1.

  def score(self, X, Y):

    # NOT likeSKLearn API

    # we wantaccuracy and exponential loss for plotting purposes

    P, FX =self.predict(X)

    L =np.exp(-Y*FX).mean()

    returnnp.mean(P == Y), L

Переходимк разделу main. Прежде всего мы получаем данные. Но не забывайте,что AdaBoost требует целевые переменные, равные -1 и+1, соответственно, нам необходимо преобразовать все нули и единицы в -1 и +1. Далеемы разбиваем данные так, чтобы 80% их были учебными данными, а 20% –проверочными.

Затеммы запускаем цикл. Мы проверим результаты на количестве деревьев от 1 до 200,чего более чем достаточно. Как вы сможете убедиться, AdaBoostтакже не подвержена переобученности даже при увеличении количества деревьев –при достижении минимальной ошибки проверочного набора она не увеличивается дажепри добавлении деревьев.

Циклмы запускаем T раз. Мы пропускаем случай, когда количестводеревьев равно нулю, поскольку не бывает ансамблей с нулевым количествоммоделей. Как и в случае примера со случайным лесом и бэггингом, даннаяпрограмма работает очень медленно, поэтому вам понадобится много времени, еслизахотите запустить её самостоятельно.

if __name__ == ‘__main__’:

  X, Y =get_data()

  Y[Y == 0] = -1# make the targets -1,+1

  Ntrain = int(0.8*len(X))

  Xtrain, Ytrain= X[:Ntrain], Y[:Ntrain]

  Xtest, Ytest =X[Ntrain:], Y[Ntrain:]

  T = 200

  train_errors =np.empty(T)

  test_losses =np.empty(T)

  test_errors =np.empty(T)

  for num_treesin xrange(T):

    if num_trees== 0:

     train_errors[num_trees] = None

     test_errors[num_trees] = None

     test_losses[num_trees] = None

      continue

    if num_trees% 20 == 0:

      printnum_trees

    model =AdaBoost(num_trees)

   model.fit(Xtrain, Ytrain)

    acc, loss =model.score(Xtest, Ytest)

    acc_train, _= model.score(Xtrain, Ytrain)

   train_errors[num_trees] = 1 – acc_train

   test_errors[num_trees] = 1 – acc

   test_losses[num_trees] = loss

    if num_trees== T – 1:

      print“final train error:”, 1 – acc_train

      print “final testerror:”, 1 – acc

Инаконец, когда цикл завершается, мы выводим всё на экран.

  plt.plot(test_errors,label=’test errors’)

 plt.plot(test_losses, label=’testlosses’)

  plt.legend()

  plt.show()

 plt.plot(train_errors, label=’trainerrors’)

 plt.plot(test_errors, label=’testerrors’)

  plt.legend()

  plt.show()

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

Сравнение с пакетированием

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

Напомню,что в нашем введении в пакетирование мы говорили о взвешенных моделях. В этомотношении AdaBoost и пакетирование одинаковы:

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

Оставимпока в стороне функцию потерь, ведь уже сейчас видна разница между этими двумяметодами. В алгоритме AdaBoost у нас естьнекоторый базовый классификатор fm, который обучается с учётом некоторыхвесовых коэффициентов примеров W(m). Припакетировании же базовый классификатор похож на классификатор перекрёстнойпроверки с исключением (напомню, –i значит, что fm обучается на всех примерах, кроме i-го):

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

Оставимпока в стороне функцию потерь, ведь уже сейчас видна разница между этими двумяметодами. В алгоритме AdaBoost у нас естьнекоторый базовый классификатор fm, который обучается с учётом некоторыхвесовых коэффициентов примеров W(m). Припакетировании же базовый классификатор похож на классификатор перекрёстнойпроверки с исключением (напомню, –i значит, что fm обучается на всех примерах, кроме i-го):

Такимобразом, функции затрат не то чтобы очень сильно, но всё же отличаются.

Теперьпоговорим о том, как находить α,которые являются весовыми коэффициентами моделей. Задумаемся об общем методеобучения пакетированного ансамбля. Главное здесь – необходимость построитьфункцию затрат, а затем оптимизировать её относительно α. Для этого нам необходимо найти все fmi. Другимисловами, необходимо знать, как построить всю функцию затрат даже до того, какначать оптимизировать α. Поскольку fmi имеет индексы m и i, то этизначения будут храниться в матрице размерности NxM, а следовательно, число моделей,которое необходимо обучить, равно O(NM). Это квадратичная сложность, а поскольку обучениемоделей – процесс не быстрый, то это не гибкое решение.

Отойдём теперь на секунду от машинного обучения и подумаем об этом с точки зрения алгоритмов. То, что делает AdaBoost, – это, по сути, жадный алгоритм. Он не пытается оптимизировать все α одновременно. Можно подумать, что жадный алгоритм не даёт оптимального решения, но вы уже видели, что AdaBoost очень хорошо работает. AdaBoost является жадным, потому что использует только текущие весовые коэффициенты W(m) для обучения модели, нахождения взвешенной ошибки и вычисления αm. При этом на каждой последующей итерации αm не меняется. Следовательно, при построении классификатора аддитивным или жадным способом нам нужно только обучить O(M) моделей. Это значит, что вместо задачи квадратичной сложности у нас получается задача линейной сложности.

Связь с глубоким обучением

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

Однойиз распространённых функций активации является гиперболический тангенс tanh, изменяющийся от -1 до +1 и имеющий S-образную форму. Его можно рассматривать как «мягкуюфункцию знака»: если подставить в него положительное число, то всегда получимположительное число между 0 и 1, а если подставить отрицательное – то всегдабудет отрицательное число между -1 и 0. Если нужно, чтобы результат был между-1 и +1, можно использовать гиперболический тангенс в последнем слое. Вкачестве альтернативы можно сразу взять функцию знака или даже взять функциюзнака после гиперболического тангенса.

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

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

Главноеотличие в том, что алгоритм AdaBoost используетбазовые классификаторы с жёсткими выходными значениями, в том смысле, чтодействительные прогнозы равны -1 или +1, вместо гибких, когда можно получитьчисло между -1 и +1.

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

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

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

Как видим, и здесь наблюдается та же форма: сумма α, умноженных на некоторую функцию данных.

Подведение итогов и что дальше

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

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

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

Этоуравнение показывает, что когда корреляция между выборками бутстрепа равно 1,то мы не получаем какого-либо уменьшения дисперсии, но когда корреляция междувыборками бутстрепа равна 0, то имеет место наибольшее уменьшение дисперсии,равное 1/B.

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

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

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

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

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

Этоуравнение показывает, что когда корреляция между выборками бутстрепа равно 1,то мы не получаем какого-либо уменьшения дисперсии, но когда корреляция междувыборками бутстрепа равна 0, то имеет место наибольшее уменьшение дисперсии,равное 1/B.

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

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

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

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

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

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

Спасибо за изучение этого курса и до следующих встреч!

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: