БраунBoost

BrownBoost — это алгоритм повышения , который может быть устойчив к зашумленным наборам данных. BrownBoost — это адаптивная версия алгоритма повышения по большинству . Как и все алгоритмы повышения , BrownBoost используется в сочетании с другими методами машинного обучения . BrownBoost был представлен Йоавом Фройндом в 2001 году. ^[1]

Мотивация

AdaBoost хорошо работает с различными наборами данных; однако можно показать, что AdaBoost не очень хорошо работает с наборами данных с шумом. ^[2] Это результат сосредоточения внимания AdaBoost на примерах, которые постоянно неправильно классифицируются. Напротив, BrownBoost фактически «отказывается» от примеров, которые неоднократно неправильно классифицируются. Основное предположение BrownBoost заключается в том, что зашумленные примеры будут неоднократно ошибочно маркироваться слабыми гипотезами, а нешумные примеры будут правильно маркироваться достаточно часто, чтобы от них «отказаться». Таким образом, «отказываются» только от шумных примеров, тогда как нешумные примеры будут участвовать в окончательном классификаторе. В свою очередь, если окончательный классификатор изучается на примерах без шума, ошибка обобщения окончательного классификатора может быть намного лучше, чем если бы он был изучен на примерах с шумом и без шума.

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

Описание алгоритма

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

Единственный параметр BrownBoost ( $c$ в алгоритме) — это «время», в течение которого работает алгоритм. Теория BrownBoost утверждает, что каждая гипотеза занимает разное количество времени ( $t$ в алгоритме), что напрямую связано с весом, придаваемым гипотезе $\alpha$ . Параметр времени в BrownBoost аналогичен количеству итераций. $T$ в АдаБост.

Большее значение $c$ означает, что BrownBoost будет обрабатывать данные так, как будто они менее зашумлены, и поэтому откажется от меньшего количества примеров. И наоборот, меньшее значение $c$ означает, что BrownBoost будет рассматривать данные как более зашумленные и откажется от большего количества примеров.

Во время каждой итерации алгоритма выбирается гипотеза с некоторым преимуществом перед случайным угадыванием. Вес этой гипотезы $\alpha$ и «количество прошедшего времени» $t$ в ходе итерации одновременно решаются в системе двух нелинейных уравнений (1. некоррелированная гипотеза относительно весов примера и 2. удержание потенциальной константы) с двумя неизвестными (вес гипотезы $\alpha$ и время прошло $t$ ). Эту проблему можно решить с помощью деления пополам (как это реализовано в программном пакете JBoost ) или метода Ньютона (как описано в оригинальной статье Фрейнда). После решения этих уравнений поля каждого примера ( $r_{i}(x_{j})$ в алгоритме) и количество оставшегося времени $s$ обновляются соответствующим образом. Этот процесс повторяется до тех пор, пока не останется времени.

Начальный потенциал определяется как ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ . Поскольку ограничение каждой итерации состоит в том, чтобы потенциал оставался постоянным, окончательный потенциал равен ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ . Таким образом, окончательная ошибка, вероятно , будет близка $1-{\mbox{erf}}({\sqrt {c}})$ . Однако окончательная потенциальная функция не является функцией ошибок потерь 0–1. Чтобы окончательная ошибка была именно $1-{\mbox{erf}}({\sqrt {c}})$ дисперсия функции потерь должна уменьшаться линейно во времени, чтобы сформировать функцию потерь 0–1 в конце итераций повышения. Это еще не обсуждается в литературе и не входит в определение приведенного ниже алгоритма.

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

Определение алгоритма обучения BrownBoost

Вход:

$m$ примеры обучения $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ где $x_{j}\in X,\,y_{j}\in Y=\{-1,+1\}$
Параметр $c$

Инициализировать:

$s=c$ . (Значение $s$ это количество времени, оставшееся в игре)
$r_{i}(x_{j})=0$ $\forall j$ . Стоимость $r_{i}(x_{j})$ это запас на итерации $i$ например $x_{j}$ .

Пока $s>0$ :

Установите веса каждого примера: $W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c}}}$ , где $r_{i}(x_{j})$ это граница примера $x_{j}$
Найти классификатор $h_{i}:X\to \{-1,+1\}$ такой, что $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$
Найти значения $\alpha ,t$ которые удовлетворяют уравнению:
$\sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}(x_{j})y_{j}+s-t)^{2}}{c}}}=0$ .
(Обратите внимание, что это похоже на условие $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ сформулированные Шапиром и Сингером. ^[3] В этой ситуации мы численно находим $W_{i+1}=\exp \left({\frac {\cdots }{\cdots }}\right)$ такой, что $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ .)
Это обновление подлежит ограничению
$\sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+s-t\right)-\Phi \left(r_{i}(x_{j})+s\right)\right)=0$ ,
где $\Phi (z)=1-{\mbox{erf}}(z/{\sqrt {c}})$ потенциальный убыток для пункта с маржой $r_{i}(x_{j})$
Обновите поля для каждого примера: $r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j}$
Обновите оставшееся время: $s=s-t$

Выход: $H(x)={\textrm {sign}}\left(\sum _{i}\alpha _{i}h_{i}(x)\right)$

Эмпирические результаты

В предварительных экспериментальных результатах с зашумленными наборами данных BrownBoost превзошел ; ошибку обобщения AdaBoost однако LogitBoost работал так же хорошо, как BrownBoost. ^[4] Реализацию BrownBoost можно найти в программном обеспечении с открытым исходным кодом JBoost .

См. также

Ссылки

^ Йоав Фройнд. Адаптивная версия алгоритма повышения по мажоритарности. Машинное обучение, 43(3):293–318, июнь 2001 г.
^ Дитерих, Т.Г., (2000). Экспериментальное сравнение трех методов построения ансамблей деревьев решений: пакетирование, повышение и рандомизация. Машинное обучение, 40 (2) 139–158.
^ Роберт Шапир и Йорам Сингер. Улучшенное повышение с использованием прогнозов с рейтингом достоверности. Журнал машинного обучения, том 37 (3), страницы 297–336. 1999 год
^ Росс А. Макдональд, Дэвид Дж. Хэнд, Идрис А. Экли. Эмпирическое сравнение трех алгоритмов повышения реальных наборов данных с искусственным классовым шумом. Множественные системы классификаторов, Серия конспектов лекций по информатике, страницы 35–44, 2003 г.

Внешние ссылки

JBoost

[Freund01-1] Йоав Фройнд. Адаптивная версия алгоритма повышения по мажоритарности. Машинное обучение, 43(3):293–318, июнь 2001 г.

[Dietterich00-2] Дитерих, Т.Г., (2000). Экспериментальное сравнение трех методов построения ансамблей деревьев решений: пакетирование, повышение и рандомизация. Машинное обучение, 40 (2) 139–158.

[Schapire99-3] Роберт Шапир и Йорам Сингер. Улучшенное повышение с использованием прогнозов с рейтингом достоверности. Журнал машинного обучения, том 37 (3), страницы 297–336. 1999 год

[McDonald03-4] Росс А. Макдональд, Дэвид Дж. Хэнд, Идрис А. Экли. Эмпирическое сравнение трех алгоритмов повышения реальных наборов данных с искусственным классовым шумом. Множественные системы классификаторов, Серия конспектов лекций по информатике, страницы 35–44, 2003 г.

[1]

[2]

[3]

[4]