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

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

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

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

Основные терминологии

Во-первых, давайте рассмотрим некоторые основные термины.

Повышение: объединение множества слабых (простых) учащихся для создания высокоточного прогноза.

Слабые ученики: классификаторы, которые дают предсказание, которое немного лучше, чем случайное предположение. Случайное угадывание эквивалентно 50%, как подбрасывание монеты. Это будет знакомо тем, кто знаком с теорией информации, особенно с идеей энтропии Шеннона.

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

Adaboost: первый практический алгоритм повышения, изобретенный Фройндом и Шапиром (1995). Он основан на идее Вапника и Червонекиса, что для того, чтобы обученный классификатор был эффективным и точным в своих прогнозах, он должен удовлетворять этим трем условиям:

1) классификатор должен быть обучен на «достаточных» обучающих примерах

2) он должен хорошо соответствовать этим примерам за счет низкой ошибки обучения

3) он должен быть простым (более простые модели лучше, чем чрезмерно сложные)

Объясняя Adaboost, шаг за шагом

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

1) Дано (x_1, y_1),… .., (x_m, y_m), где x_i ∈ X, y_i ∈ {-1, +1}

Полезные обозначения

∈: «элемент»

{}: установленный

ex: if A = {1,2,3,7}, 2 ∈ A

(x_1, y_1): первая обучающая выборка, (x_m, y_m) = m-я обучающая выборка

Теперь, когда у нас есть все обозначения, мы можем прочитать первую часть формулы как:

«Учитывая обучающий набор, содержащий m выборок, где все x входов являются элементом общего набора X, а выходы y являются элементом набора, состоящего только из двух значений, -1 (отрицательный класс) и 1 (положительный класс)…»

2) Инициализировать: D1 (i) = 1 / m для i = 1,…, m.

Здесь D = веса выборок, а i = i-я обучающая выборка. В других статьях буква D будет записана как W. Таким образом, следующее утверждение гласит:

«… Инициализируйте все веса ваших выборок до 1, разделенного на количество обучающих выборок…»

3) Для t = 1,…, T:

* обучать слабых учеников с помощью распределения Dt.

* Получите слабую гипотезу h_t: X - ›{-1, +1}

* Цель: выбрать h_t с маловзвешенной ошибкой:

ε = Pr_i ~ Dt [h_t (xi) не равно y_i]

* Выберите α_t = 1/2 * ln (1-ε / ε)

* Обновить, для i = 1,…, m:

Dt + 1 (i) = Dt (i) exp (-αt * y_i * h_t (x_i) / Zt

Полезные обозначения

Pr = вероятность

h_t = гипотеза / классификатор

ε = минимальная ошибка ошибочной классификации для модели

α = вес для классификатора

exp = euler’s e: 2,71828

Zt = коэффициент нормализации, используемый для гарантии того, что веса представляют истинное распределение.

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

«Для классификаторов от t = от 1 до T подгоните его к обучающим данным (где каждый прогноз равен либо -1, либо 1) и выберите классификатор с наименьшей взвешенной ошибкой классификации».

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

Давайте разберемся с этой конкретной моделью.

Полезные обозначения

Σ = сумма

y_i не равно h_j = 1, если классифицировано неправильно, и 0, если классифицировано правильно

w_i = вес

Таким образом, формула гласит: «Ошибка равна сумме коэффициента ошибочной классификации, где вес для обучающей выборки i и y_i не равен нашему прогнозу h_j (который равен 1, если классифицировано неправильно, и 0, если классифицировано правильно)».

Давайте применим простую математику, чтобы понять формулу. Подумайте о наличии 4 разных образцов с весом 0,5, 0,2, 0,1 и 0,04. Представьте, что наш классификатор h предсказал значения 1, 1, -1 и -1, но фактическое выходное значение y было -1, 1, -1, 1.

предсказано: 1 1 -1 -1

фактическое: -1 1 -1 1

вес: 0,5 0,2 0,1 0,04

1 or 0: 1 0 0 1

Это приводит к следующему вычислению коэффициента ошибочной классификации:

коэффициент ошибочной классификации / ошибка = (0,5 * 1 + 0,2 * 0 + 0,1 * 0 + 0,04 * 1) / (0,5 + 0,2 + 0,1 + 0,04)

ошибка = 0,64285714285

Затем выберите наш вес для классификатора α по формуле 1/2 * ln (1- ошибка / ошибка).

Простая математика могла бы объяснить лучше, чем слова здесь. Предположим, например, что у нас есть ошибки 0,30, 0,70, 0,5.

Вес нашего классификатора будет рассчитываться следующим образом:

ε = 0.3

α = 1/2 * ln(1- 0.3 / 0.3) = 0.42365

ε = 0.7

α = 1/2 * ln(1- 0.7 / 0.7) = -0.42365

ε = 0.5

α = 1/2 * ln(1- 0.5 / 0.5) = 0

Обратите внимание на три интересных наблюдения: 1) классификатор с точностью выше 50% дает положительный вес для классификатора (другими словами, α ›0, если ε‹ = 0,5), 2) классификатор с точными 50 % точности равен 0 и, таким образом, не влияет на окончательный прогноз, и 3) ошибки 0,3 и 0,7 приводят к весам классификатора с обратными знаками.

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

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

И вот оно! В случае неправильной классификации член опыта стал больше 1, а в случае правильной классификации член опыта стал меньше 1. Следовательно, неправильная классификация получит более высокие веса, что побуждает наши классификаторы уделять им больше внимания в следующая итерация, в то время как противоположный случай правильной классификации приведет к обратному.

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

Резюме

Мы увидели, как Adaboost работает на детальном уровне, разбив все обозначения в формуле. Затем мы применили простую математику, чтобы понять, как работает каждый компонент формулы. Такой подход к формулам через разложенные части может быть полезен для понимания алгоритмов машинного обучения.