В чем адаптивность алгоритма adaboost

Adaptive boosting

Здравствуйте, на Хабре уже была статья Indalo, посвященная AdaBoost, точнее, некоторому его применению. Я же хочу более детально остановиться на самом алгоритме, заглянуть в его реализацию и продемонстрировать его работу на примере моей программы.

Псевдокод алгоритма хорошо описан на Вики. Приведем его здесь.

Псевдокод

Дано: , где .

Инициализируем

Для каждого :

* Находим классификатор , который минимизирует взвешенную ошибку классификации:
, где

,
где Zt является нормализующим параметром (выбранным так, чтобы Dt + 1 являлось распределением вероятностей, то есть ).

Строим результирующий классификатор:

.

Далее будем придерживаться его в наших объяснениях.

Простой классификатор

Итак, простой классификатор. Как я уже говорил, это вертикальная или горизонтальная прямая, которая разделяет плоскость на две части, минимизируя ошибку классификации: (квадратные скобки от булевого выражения равны 1, ели true, и 0, если false). На языке С# процедуру такого обучения можно написать следующим образом:

//Обучение простого классификатора

// Цикл по всем координатам пространства
for ( int d = 0; d // Для оптимизации в случае, если пространство огромной размерности
if (rnd.NextDouble() continue ;

// Если идут одинаковые данные, то порог не ищем
if (data[i] == data[i + 1])
continue ;

// Определяем потенциально возможное значение для threshold
double testThreshold = (data[i] + data[i + 1]) / 2.0;

Если Вы заметили, то процедура обучения простого классификатора написана таким образом, что если ему передать веса, которые получаются на протяжении работы алгоритма AdaBoost, то тогда будет искаться тот классификатор, который минимизирует взвешенную ошибку классификации п.1. Тогда сам алгоритм на С# будет выглядеть следующим образом:

«Сложный» классификатор

//Обучение с помощью AdaBoost

public override void Train(LabeledDataSet double > trainingSet)
<
// Инициализируем веса D_i
if (_weights == null )
<
_weights = new double [trainingSet.Count];
for ( int i = 0; i // Делаем непосредственно обучение простых классификаторов
for ( int t = _h.Count; t // Создаем простой классификатор и обучаем его
WeakLearner h = _factory();
h.Weights = _weights;
h.Train(trainingSet);

//Вычисляем ввзвешенную ошибку классификации
int [] hClassification = new int [trainingSet.Count];
double epsilon = 0.0;
for ( int i = 0; i // Если величина epsilon >= 0.5, то останавливаемся
if (epsilon >= 0.5)
break ;

// Обновляем коэффициенты D_i
double weightsSum = 0.0;
for ( int i = 0; i // Нормируем полученные коэффициенты
for ( int i = 0; i // Запоминаем классификатор с найденным коэффициентом
_h.Add(h);
_alpha.Add(alpha);

// Останавливаем обучение, если ошибка равна нулю
if (epsilon == 0.0)
break ;
>
>

Таким образом, после выбора оптимального классификатора h_\, для распределения D_i, объекты x_ \,, которые классификатор h_\, идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении D_, он будет выбирать классификатор, который лучше идентифицирует объекты, неверно распознаваемые предыдущим классификатором.

Пример

В случае классификации таких данных:

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

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

Заключение

Как видим, алгоритм, построенный с помощью AdaBoost, классифицирует намного лучше, чем один классификатор, но и он имеет ошибки. Но простота и изящность алгоритма позволила ему войти в Top 10 algorithms in data mining. Надеюсь, код, приведенный в статье, помог вам разобраться с этим алгоритмом.

Источник

Бустинг, AdaBoost

Содержание

Описание [ править ]

Бустинг (англ. boosting) — мета-алгоритм машинного обучения. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, хорошо коррелирующим с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как бэггинг (англ. bagging) и стэкинг [1] (англ. stacking). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.

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

Алгоритмы бустинга [ править ]

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

Основное расхождение между многими алгоритмами бустинга заключается в методах определения весовых коэффициентов точек тренировочных данных и гипотез. Первым алгоритмом, который смог адаптироваться к слабому обучению был AdaBoost [2] (сокр. Adaptive Boosting), предложенный Шапире и Фройндом.

Прикладное использование алгоритмов бустинга [ править ]

Задача классификации объектов [ править ]

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

Задача ранжирования выдачи поисковых систем [ править ]

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

AdaBoost [ править ]

Описание [ править ]

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

Описание алгоритма [ править ]

Выражение для обновления распределения [math]D^t[/math] должно быть сконструировано таким образом, чтобы выполнялось условие:

Пример работы [ править ]

Для всех ошибочно классифицированных объектов увеличим веса, а для верно классифицированных уменьшим

Теперь у нас все объекты классифицируются верно и число ошибок на выборке равно нулю.

Достоинства и недостатки [ править ]

Пример кода [ править ]

Пример кода на python для scikit-learn [ править ]

Классификатор sklearn.ensemble.AdaBoostClassifier [6] имеет 5 параметров: base_estimator, n_estimators, learning_rate, algorithm, random_state. Наиболее важными являются:

Теперь рассмотрим алгоритм с SVC в качестве базы:

Источник

Алгоритм AdaBoost

Введение

Что такое алгоритм AdaBoost?

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

AdaBoost означает «Adaptive Boosting» или адаптивный бустинг. Он превращает слабые обучающие алгоритмы в сильные для решения проблем классификации.

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

Здесь f_m – это m-ый слабый классификатор, где _m отвечает за соответствующий ему вес.

Как работает алгоритм AdaBoost?

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

Если у нас есть набор данных, в котором n – количество точек и

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

Затем посчитаем вес m-ого слабого классификатора, как показано ниже:

Вес положителен для любого классификатора с точностью выше 50%. Чем больше вес, тем точнее классификатор. Вес становится отрицательным, когда точность падает ниже 50%. Предсказания можно объединять, инвертируя знак. Таким образом классификатор с точность в 40% можно преобразовать в классификатор с точностью в 60%. Так классификатор будет вносить вклад в итоговое предсказание, даже если он работал хуже, чем случайное угадывание. Однако окончательный результат никак не изменится под влиянием классификатора, точность которого равна 50%.

Экспонента в числителе всегда будет больше 1 в случае неверной классификации из классификатора с положительным весом. После итерации вес неверно классифицированных объектов возрастет. Классификаторы с отрицательным весом поведут себя аналогичным образом. Здесь есть разница в инверсии знака: правильная классификация станет неправильной. Окончательный прогноз можно рассчитать путем учета вклада каждого классификатора и вычисления суммы их взвешенных прогнозов.

Вес для каждой точки будет обновляться следующим образом:

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

Где используется алгоритм AdaBoost?

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

Преимущества и недостатки алгоритма AdaBoost

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

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

Пример алгоритма AdaBoost

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

Заключение

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

Источник

Русские Блоги

Адаптивное улучшение машинного обучения (Adaboost)

1. Введение в Adaboost

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

1.1 Повышение уровня интегрированного обучения

Как видно из приведенного выше рисунка, рабочий механизм алгоритма повышения заключается в обучении слабого учащегося 1 с начальными весами из обучающего набора и обновлении веса обучающей выборки в соответствии с частотой ошибок обучения слабого учащегося, чтобы предыдущий слабый учащийся 1 учился Вес точек обучающей выборки с высоким уровнем ошибок становится выше. Затем эти точки с высоким процентом ошибок привлекают больше внимания у слабого учащегося 2, а слабый учащийся 2 обучается с использованием обучающего набора после корректировки веса. Это повторяется до тех пор, пока количество слабых учеников не достигнет заранее заданного числа T, и, наконец, эти T слабых учеников интегрируются через заданную стратегию для получения окончательного сильного ученика.

1.2 Адаптивный

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

1.3 Процесс Adaboost

ОбъединитьАдаптивныйсBoost (улучшенный)Концепция, давайте познакомимся с ней подробнееAdaboostИтерационный алгоритм потока.

2. Алгоритм классификации Adaboost

Предположим, наша обучающая выборка

Из формулы расчета wk + 1, i видно, что если i-я выборка неправильно классифицирована, yiGk (xi)

3. Алгоритм регрессии Adaboost

Предположим, наша обучающая выборка

Наконец получить k-го слабого ученикаЧастота ошибок обучения

Наконец, проблема регрессии Adaboost принимаетКомбинированная стратегия метода средневзвешенного значения, Последний сильный регрессор

4. Функция потерь Adaboost

Предположим, что k-1 и k-я сильные ученики

Итак, мы можем получить

5. Регуляризация алгоритма Adaboost.

Чтобы предотвратить переоснащение Adaboost, обычно добавляется термин регуляризации, который обычно называется скоростью обучения. Определяется как ν для повторения предыдущего слабого ученика

6.Sklearn реализует алгоритм Adaboost

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

7. Преимущества и недостатки алгоритма Adaboost.

7.1 Преимущества Adaboost

7.2 Недостатки Adaboost

8. Продвижение

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

Интеллектуальная рекомендация

Измените имя хоста, сопоставьте IP-адрес и имя хоста, закройте вход в систему без пароля и пароля по selinux и SSH.

После изменения перезапустите виртуальный, и все будет в порядке. Чтобы мы могли соединяться друг с другом, не вводя IP-адрес в каждой виртуальной машине, мы должны сопоставить IP-адрес и имя хоста. З.

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

Предисловие НедавниеПолучить COVID-19(Новая коронавирусная пневмония) Пострадавшие от эпидемии научные круги и промышленность последовательно использовали технологии искусственного интеллекта, чтобы п.

Источник

Русские Блоги

Подробные параметры Sklearn-Adaboost

предисловие

Примечание: нечисть здесь не имеет намерения, пожалуйста, не переусердствуйте.

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

Теоретические знания

Во-первых, все слабые ученики относятся к одному типу, например, к моделям дерева решений.

Другая причина заключается в том, что все слабые учащиеся не совсем одинаковы. Вы можете использовать LR для прогнозирования одного результата, затем использовать байесовский метод для прогнозирования одного, а затем использовать SVM для прогнозирования одного, а затем голосовать за результаты прогнозирования трех моделей. Существует много голосов. Как конечный результат.

Мы используем тех же самых слабых учеников, чтобы сформировать сильного ученика.

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

AdaBoost-модель

После разговора об обучении ансамблям давайте поговорим о модели Adaboost в Sklearn, кстати. Принцип работы модели Adaboost см. В следующих статьях:Подъемный метод-алгоритм Adaboost。

AdaBoost-параметры

AdaBoost-объекта

Сначала сгенерируйте классификатор

estimators_ : Вернуть все классификаторы в виде списка.

результат операции
Длина списка
Вы можете видеть, что длина списка, полученного этим объектом, равна 100, что соответствует числу настраиваемых нами базовых классификаторов.
classes_ : Ярлык категории
результат операции
estimator_weights_ Вес каждого классификатора.

estimator_errors_ : Коэффициент ошибок каждого классификатора соответствует весу классификатора.

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

AdaBoost-метод

decision_function(X) Возвращает значение функции принятия решения (например, расстояние принятия решения в SVM)
fit(X,Y) : Обучить модель на наборе данных (X, Y).
get_parms() : Получить параметры модели
predict(X) : Предсказать результат набора данных X.
predict_log_proba(X) : Предсказать логарифмическую вероятность набора данных X.
predict_proba(X) : Предсказать значение вероятности набора данных X.
score(X,Y) Точность набора выходных данных (X, Y) на модели.
staged_decision_function(X) Возвращает значение решающей функции каждого базового классификатора.
staged_predict(X) Возвращает результат набора данных прогнозирования X каждого базового классификатора.
staged_predict_proba(X) Возвращает результат вероятности набора данных прогнозирования X каждого базового классификатора.
staged_score(X, Y) Возвращает точность прогнозирования каждого базового классификатора.

Большинство методов Adaboost в основном такие же, как и у других моделей, несколько больше, чем у других моделей. staged метод. Постановочный возвращает результаты каждой базовой классификации.

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

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

Источник