BrownBoost

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

Мотивация [ править ]

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

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

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

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

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

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

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

Начальный потенциал определяется как . Поскольку ограничение каждой итерации состоит в том, что потенциал должен оставаться постоянным, конечный потенциал равен . Таким образом, последняя ошибка, вероятно, будет рядом . Однако конечная потенциальная функция не является функцией ошибок потерь 0-1. Чтобы окончательная ошибка была точной , дисперсия функции потерь должна линейно уменьшаться по времени, чтобы сформировать функцию потерь 0-1 в конце итераций повышения. Это еще не обсуждается в литературе и не входит в определение алгоритма ниже. ${\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}})$ $1-{\mbox{erf}}({\sqrt {c}})$

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

Определение алгоритма обучения 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$
Найти значения , которые удовлетворяют уравнению: . (Обратите внимание, что это похоже на условие, сформулированное Шапиром и Сингером. ^[3] В этой настройке мы численно находим такое, что .) Это обновление подчиняется ограничению , где - потенциальные убытки для точки с запасом $\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$ $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 г.
^ Dietterich, TG, (2000). Экспериментальное сравнение трех методов построения ансамблей деревьев решений: бэггинг, бустинг и рандомизация. Машинное обучение, 40 (2) 139-158.
^ Роберт Шапир и Йорам Сингер. Улучшенный рост с использованием уверенных прогнозов. Журнал машинного обучения, том 37 (3), страницы 297-336. 1999 г.
^ Росс А. Макдональд, Дэвид Дж. Хэнд, Идрис А. Экли. Эмпирическое сравнение трех алгоритмов повышения на реальных наборах данных с искусственным классовым шумом. Множественные системы классификаторов, Серийные конспекты лекций по информатике, страницы 35-44, 2003.

См. Также [ править ]

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

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

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

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

[1]