BrownBoost - BrownBoost

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

Мотивация

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

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

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

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

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

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

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

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

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

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

Вход:

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

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

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

Пока ${displaystyle s> 0}$ :

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

Выход: ${displaystyle H (x) = {extrm {sign}} left (sum _ {i} alpha _ {i} h_ {i} (x) ight)}$

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

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