Boosting

Введение

Бустинг (повышение, поднятие) - это класс методов машинного обучения, основанный на идее, что комбинация простых классификаторов (полученных слабым учеником) может работать лучше, чем любой из простых классификаторов. Слабый ученик (WL) - это алгоритм обучения, способный производить классификаторы с вероятностью ошибки строго (но незначительно) меньше случайного угадывания (0.5, в двоичном случае). С другой стороны, сильный ученик (SL) способен (учитывая достаточное количество обучающих данных) давать классификаторы с произвольно малой вероятностью ошибки.
Ансамбль (или комитет) классификаторов - это классификатор, построенный на некой комбинации слабых учеников. Стратегия повышения и ансамбли классификаторов, состоит в том, чтобы обучить много слабых классификаторов и каким-то образом объединить их, вместо того, чтобы пытаться получить один сильный классификатор.
Пусть \(H_m: \mathfrak{X} \to \{−1, + 1\}\) \(m\)-й слабый двоичный классификатор (для \(m = 1, ..., M\)), и \(x \in \mathfrak{X}\) некоторый входной шаблон для классификации. Существует много способов объединить \(\{H_m\}_{m=1}^M\) в единый прогноз класса. Например, предполагая, что классификаторы ошибаются независимо друг от друга, комбинация большинства голосов должна давать более низкую вероятность ошибки, чем любой из отдельных классификаторов. Если взять взвешенную линейную комбинацию выходов слабых классификаторов, то функция прогнозирования ансамбля \(H: \mathfrak{X} \to \{−1, + 1\}\) задается следующим образом \begin{equation}\label{1} H(x)=\textrm{sign} \left(\sum_{m=1}^M\alpha_m H_m(x)\right), \end{equation} где \(\alpha_1,...,\alpha_M\) - набор весов (использование простого большинства голосов получается, если все веса равны между собой).
По сути, бустинг (повышение) состоит в многократном использовании слабых алгоритмов обучения на разно взвешенных версиях обучающих данных. Вес каждого метода на каждом раунде алгоритма зависит от точности предыдущих классификаторов, что позволяет алгоритму сосредоточить свои внимание на те примеры, которые все еще неправильно классифицированы.
Интерес к бустингу порожден алгоритмом AdaBoost (адаптивное повышение), предложенным в работах Фрейнда и Шапире (Freund,Schapire).
Данный раздел написан по мотивам книги "Ensemble Machine Learning".

Вспомогательная информация.

Сильные и слабые ученики

Слабое и сильное обучение являются фундаментальными понятиями в основе усиления алгоритмов, поэтому кратко рассмотрим их формальные определения.
Рассмотрим правило классификации \(f: \mathfrak{X}\to \{−1, + 1\}\), такое, что \(f \in F\), где \(F\) - некоторый класс функций из \(\mathfrak{X} \to \{-1, + 1\}\). Рассмотрим также набор пар \(\{(x_i, y_i), i = 1, ..., N\}\), такой что \(y_i = f (x_i)\) и \(x_i\) являются выборками некоторого распределения \(P\).
Сильный ученик, учитывая достаточное число данных, способен реализовать произвольно хороший классификатор с высокой вероятностью, то есть для каждого \(P, f \in F,\) ε ≥0 и δ ≤ 1/2, он выводит с вероятностью не менее 1 −δ классификатор \(h:\mathfrak{X} \to \{−1, + 1\}\), удовлетворяющий условию \(\mathbb{P}_P [h (x) \ne f (x)] ≤ ε\) с полиномивльной сложностью по времени.
Слабый ученик определяется так же, как сильный, но с более слабыми условиями по ε и δ. Для конкретной пары (а не для всех) \(\varepsilon_0 \ge 0\) и \(\delta_0 \le 1/2\), слабый ученик реализует, с вероятностью не меньше чем 1 −δ, классификатор \(h: \mathfrak{X} \to \{-1, + 1\}\), удовлетворяющий условию \(\mathbb{P}_P [h (x) \ne f (x)] \le \varepsilon_0\).
В основе идеи бустинга лежит доказанный Шапире факт, что сильного ученика возможно получить путем объединения слабых учеников.

В качестве иллюстрации приведем простой пример бустинга линейной регрессии для множества \((x_i,y_i) i=1,...,N\).

  1. Инициализация весов \(\omega^{(1)}_i=1/N,i\in\{1,...,N\}\) и \(m=1.\)
  2. while \(m\le M\) do
  3. end while
  4. В результате получаем прогноз \[ Y_i=\frac{\sum_{m=1}^M\omega_i^{(m)}(x_i)\tilde{y}^{(m)}_i}{\sum_{m=1}^M\omega_i^{(m)}}. \]

Алгоритмы бустинга

Вначале приведем классический алгоритм Шапире.

Процедура Boosting для задачи классификации.

Ввод. Исходные данные: выборка размером N: \(Z = \{z_1, z_2, ..., z_N\}\), где \(z_i = (x_i, y_i)\), \(x_i\in \mathfrak{X}\) и \(y_i\in \{-1,+1\}\).
Вывод: Классификатор \(H:\mathfrak{X}\to \{-1,+1\}\).

Как видно из алгоритма Шапире, обучающий набор случайным образом делится без замены на три множества, \(Z^*_1,Z^*_2,Z^*_3\). Если при определении принадлежности элемента, первые два классификатора (\(H_1\) и \(H_2\)) согласны с меткой класса, то это окончательное решение. Множество примеров, по которым они не согласны, определяет разбиение \(Z^*_3\), 3 который используется для изучения \(H_3\). Шапире показал, что этот метод обучения позволяет построить сильный классификатор. В дальнейшем, опираясь на идеи Шапире Фрейнд предложил новый алгоритм, который значительно эффективней первоначального.

Связь между бустингом, бэггингом и бутстрепом

Алгоритм AdaBoost

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

Алгоритм AdaBoost для бинарной классификации

Ввод. Исходные данные: выборка размером N: \(Z = \{z_1, z_2, ..., z_N\}\), где \(z_i = (x_i, y_i)\), \(x_i\in \mathfrak{X}\) и \(y_i\in \{-1,+1\}\), М - максимальное количество классификаторов.
Вывод: Классификатор \(H:\mathfrak{X}\to \{-1,+1\}\).
  1. Инициализация весов \(\omega^{(1)}_i=1/N,i\in\{1,...,N\}\) и \(m=1.\)
  2. while \(m\le M\) do
  3. end while
  4. Результирующий классификатор: \(H(x)=\mathrm{sign}\left(\sum_{j=1}^M\alpha_jH_j(x)\right)\).
Функция \(h: R \to \{0, 1\}\), назывется ступенькой Хевисайда и определяется следующим образом \[ h(x)=\left\{ \begin{array}{ll} 1, & \hbox{ если }x\ge 0 \\ 0, & \hbox{ если }x\lt 0. \end{array} \right. \] Следовательно, так как и \(y_i,\) и \(H_m(x_i)\) принимают значения из {−1, + 1}, имеем \(h (−y_i H_m (x_i)) = 1\), если \(y_i\ne H_m(x_i)\) и \(h (−y_i H_m (x_i)) = 0\) в случае \(y_i= H_m(x_i)\), соответственно, \(\varepsilon_m\) представляет собой взвешенную ошибку \(m\)-го классификатора.
По сути, AdaBoost является жадным алгоритмом, который создает «сильный классификатор», путем оптимизации весов и добавления одного слабого классификатора за раз.

Простая иллюстрация работы AdaBoost.


Иллюстрация шагов алгоритма AdaBoost
Шаг 1. На первом шаге присвоили равные веса каждой точке данных и применили линейный классификатор, с целью разделения их на множества точек с "плюсами" и, соответственно, с "минусами". Первый классфикатор (D1) сгенерировал вертикальную линию с левой стороны, разделяя точки данных. Как видим, эта вертикальная линия неправильно предсказала три значения "+" (плюс).
В таком случае назначим более высокие веса этим трем точкам "+" (плюс) и применим другой классификатор. На приведенной иллюстрации это соотносится с размером соответствующей точки, то есть, размер трех неправильно предсказанных точек "+" (плюс) больше по сравнению с остальными точками данных.
Шаг 2. Второй классификатор (D2) попытается предсказать эти точки правильно. Теперь вертикальная линия (D2) с правой стороны поля правильно классифицировала три то этого неправильно классифицированных точки "+" (плюс).
Но опять же, это вызвало ошибки полученной классификации. На этот раз это три точки "-" (минус). Опять же, назначим более высокий вес на эти три "-" (минус) и применим еще один классификатор.
Шаг 3. Третий классификатор (D3) применяется для правильного прогнозирования этих ошибочно классифицированных наблюдений. На этот раз горизонтальная линия генерируется для классификации "+" (плюс) и "-" (минус) на основе более высокого веса неправильно классифицированных наблюдений.
Шаг 4. Теперь, когда процесс разделения классов прошел успешно, остается объединить методы D1, D2 и D3, чтобы сформировать сильный прогноз, имеющий более сложное правило по сравнению с каждым индивидуальным слабым классификатором (учеником).

Варианты AdaBoost

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

Real AdaBoost

Ввод. Исходные данные: выборка размером N: \(Z = \{z_1, z_2, ..., z_N\}\), где \(z_i = (x_i, y_i)\), \(x_i\in \mathfrak{X}\) и \(y_i\in \{-1,+1\}\), М - максимальное количество классификаторов.
Вывод: Классификатор \(H:\mathfrak{X}\to \{-1,+1\}\).
  1. Инициализация весов \(\omega^{(1)}_i=1/N,i\in\{1,...,N\}\) и \(m=1.\)
  2. while \(m\le M\) do
  3. end while
  4. Результирующий классификатор: \(H(x)=\mathrm{sign}\left(\sum_{j=1}^MH_j(x)\right)\).

Logit Boost

Ввод. Исходные данные: выборка размером N: \(Z = \{z_1, z_2, ..., z_N\}\), где \(z_i = (x_i, y_i)\), \(x_i\in \mathfrak{X}\) и \(y_i\in \{-1,+1\}\), М - максимальное количество классификаторов.
Вывод: Классификатор \(H:\mathfrak{X}\to \{-1,+1\}\).
  1. Инициализация \(\omega^{(1)}_i=1/N, p(x_i)=\frac{1}{2}, i\in\{1,...,N\}\), \(H(x)=0\) и \(m=1.\)
  2. for \(m=1 \) to \(M\) and while \(H_m\ne 0\) do
  3. end for
  4. Результирующий классификатор: \(H(x)=\mathrm{sign}\left(\sum_{j=1}^MH_j(x)\right)\).
Существует много разных алгоритмов бустинга, среди которых, алгоритм Gentle AdaBoost, который является улучшением Real AdaBoost за счет использования шагов Ньютона, обеспечивая тем самым более надежный и стабильный ансамбль, Modest AdaBoost который дает меньшую по сравнению с Real AdaBoost и Gentle AdaBoost, и многие другие.
В заключение приведем примеры алгоритмов бустинга для случая многих классов.

AdaBoost.MH

Ввод. Исходные данные: выборка \(Z = \{z_{i,j}\}\) размером N из \(N\times k\) пар, где \(z_{i,j} = ((x_i,j), y_i)\), \((x_i,j)\in \mathfrak{X}\) и \(y_{i,j}\in \{-1,+1\}\) признак соответствия классу \(j\) при наблюдении \(i\), где \(i=1,...,N\) и \(j=1,...,k\).
  1. Последовательно применяя Real AdaBoost к проекциям исходным данных, получаем функцию \[ H:\mathfrak{X}\times (1,...,k)\to \mathbb{R}, H(x,j)=\sum_mH_m(x,j). \]
  2. Вывод: Классификатор \( \textrm{arg} \max_j H(x,j)\).

Logit Boost (k классов)

  1. Инициализация \(\omega^{(1)}_{i,j}=1/N, p_j(x_i)=\frac{1}{k}, H_j(x)=0, i\in\{1,...,N\}, j\in\{1,...,k\}\) и \(m=1.\)
  2. for \(m=1 \) to \(M\) do
  3. for \(j=1 \) to \(k\) do
  4. end for
  5. Результирующий классификатор: \( \textrm{arg} \max_j H_j(x)\).

Градиентный бустинг

Вначале рассмотрим общую задачу обучения с учителем.
По имеющейся выборке \(\{(x_i,y_i)\}_{i=1}^n\) нужно восстановить зависимость \(y=f(x)\). Решение \(\hat{f}\) будем искать из условия минимизации средней ошибки \[ \varepsilon(f)=\frac{1}{n}\sum_{i=1}^nL(y_i,f(x_i)), \] где \(L(\cdot)\) - функция потерь (например, среднеквадратическая ошибка), тогда \[ \hat{f}=\textrm{arg}\min_{f\in \mathcal{F}}\varepsilon(f), \] здесь \(\mathcal{F}\) некий класс функций, называемый классом модели, что может быть линейными методами, методами локальной регрессии ( k-ближайших соседей, ядерная регрессия и др.), сплайны и пр.
Среди методов решения оптимизационных задач, одними из наиболее популярных являются градиентный спуск и метод Ньютона. Рассмотрим как эти методы можно адаптировать для задачи бустинга.
Рассмотрим ансамбль моделей \[ f(x)=\sum_{m=0}^Mf_m(x), \] которые могут быть представлены как модели адаптивных базисных функций \[ f(x)=\theta_0+\sum_{m=1}^M\theta_m\phi_m(x), \] где \(f_0(x)=\theta_0\), \(f_m(x)=\theta_m\phi_m(x), m=1,...,M\) и \(\phi_m-\) последовательное добавление базисных функций для улучшения соответствия текущей модели. В используемых терминах это множество слабых классификаторов (учеников).
Остается только применить подходящий алгоритм для минимизации ошибки. Вначале для этой цели используем градиентный спуск, то есть, найдем градиент ошибки и используя итерационные оценки \(\theta_m\) будем двигаться вдоль него (заметим, что так как нашей целью является не увеличение, а уменьшение ошибки, то градиент будем брать со знаком минус "-").

Gradient boosting.

Ввод. Исходные данные: \(\mathcal{D}\).
Функция потерь: \(L\).
Число итераций:\(M\).
Характеристика скорости обучения:\(\eta\).
  1. Инициализация \[\hat{f}^{(0)}(x)=\hat{f}_0=\theta_0=\textrm{arg}\min_\theta\sum_{i=1}^nL(y_i,\theta).\]
  2. for \(m=1 \) to \(M\) do

    Вычислим \[ \hat{g}_m(x_i)=\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right]_{f(x)=\hat{f}^{(m-1)}(x)}, \] \[ \hat{\phi}_m=\textrm{arg}\min_{\phi\in\Phi,\beta}\sum_{i=1}^n\left[(-\hat{g}_m(x_i))-\beta\phi(x_i)\right]^2, \] \[ \hat{\rho}_m=\textrm{arg}\min_{\rho}\sum_{i=1}^nL\left(y_i,\hat{f}^{(m-1)}(x_i)+\rho\hat{\phi}_m(x_i)\right), \] \[ \hat{f}_m(x)=\eta\hat{\rho}_m\hat{\phi}_m(x), \] \[ \hat{f}^{(m)}(x)=\hat{f}^{(m-1)}(x)+\hat{f}_{m}(x). \]

  3. end for
  4. Результирующий классификатор: \( \hat{f}(x)=\hat{f}^{(M)}(x)=\sum_{m=0}^M\hat{f}_m(x)\).

Здесь \(\hat{g}_m(x_i)-\) отрицательный градиент,
\(\hat{\phi}_m\) слабый классификатор,
\(\hat{\rho}_m-\) длина шага градиентного спуска.

Newton boosting.

Ввод. Исходные данные: \(\mathcal{D}\).
Функция потерь: \(L\).
Число итераций:\(M\).
Характеристика скорости обучения:\(\eta\).
  1. Инициализация \[\hat{f}^{(0)}(x)=\hat{f}_0=\theta_0=\textrm{arg}\min_\theta\sum_{i=1}^nL(y_i,\theta).\]
  2. for \(m=1 \) to \(M\) do

    Вычислим \[ \hat{g}_m(x_i)=\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\right]_{f(x)=\hat{f}^{(m-1)}(x)}, \] \[ \hat{h}(x_i)=\left[\frac{\partial^2 L(y_i,f(x_i))}{\partial f(x_i)^2}\right]_{f(x)=\hat{f}^{(m-1)}(x)}, \] \[ \hat{\phi}_m=\textrm{arg}\min_{\phi\in\Phi}\sum_{i=1}^n\frac{1}{2}\hat{h}_m(x_i)\left[\left(-\frac{\hat{g}_m(x_i)}{\hat{h}_m(x_i)}\right)-\phi(x_i)\right]^2, \] \[ \hat{f}_m(x)=\eta\hat{\phi}_m(x), \] \[ \hat{f}^{(m)}(x)=\hat{f}^{(m-1)}(x)+\hat{f}_{m}(x). \] Здесь \(\hat{h}_m\) эмпирический гессиан.

  3. end for
  4. Результирующий классификатор: \( \hat{f}(x)=\hat{f}^{(M)}(x)=\sum_{m=0}^M\hat{f}_m(x)\).

Здесь \(\hat{g}_m(x_i)-\) отрицательный градиент,

Характеристика обучения \(\eta\) имеет тенденцию изменять скорость сходимости.

Boosted Trees.

Одним из наиболее популярных сфер использования бустинга является его применение для построения деревьев. Вот, например, простая иллюстрация этого подхода.

Полезная литература. Книги.

  1. Didrik N. Tree Boosting With XGBoost / N.Didrik .— Trondheim: Norwegian University of Science and Technology, 2016 .— 110 p.
  2. Cha Zhang. Ensemble Machine Learning. Methods and Applications / Cha Zhang, Yunqian Ma .— New York Dordrecht Heidelberg London: Springer, 2012 .— 329 p.
  3. Lemmens A. Bagging and boosting classification trees to predict churn / A.Lemmens, C.Croux .— Leuven: Katholieke Universiteit, 2000 .— 40 p.
  4. The Top Ten Algorithms in DataMining; Vipin Kumar (Editor) .— Taylor & Francis Group, LLC, 2009 .— 2006 p.
  5. Воронцов К.В. Лекции по алгоритмическим композициям / К.В.Воронцов, 2007 .— 45 с.
  6. Марманис Х. Алгоритмы интеллектуального интернета. Передовые методики сбора, анализа и обработки данных. / Х.Марманис, Д.Бабенко .— Сб-П, М: Символ, 2011 .— 468 с.
  7. Флах П. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных / П.Флах .— М: ДМК, 2015 .— 399 с.

Полезная литература. Статьи.

  1. Chen T. XGBoost: A scalable tree boosting system / T.Chen, C.Guestrin // 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining .— San Francisco, CA, 2016 .— P.785–794.
  2. Cooper J. Improved Algorithms for Distributed Boosting / J.Cooper, L.Reyzin // 55th Annual Allerton Conference on Communication, Control, and Computing .— Allerton, 2017 .— P.1-9.
  3. Dekel Shai. Wavelet Decomposition of Gradient Boosting / Dekel Shai, Oren Elisha, Ohad Morgan // CoRR abs/1805.02642 .— 2018 .— P.1-13.
  4. Dorogush A. CatBoost: gradient boosting with categorical features support / A.Dorogush, V.Ershov, A.Gulin .— Yandex, 2018 .— 1-7 p.
  5. Freund Y. Experiments with a New Boosting Algorithm / Y.Freund, R.E.Schapire // Machine Learning: Proceedings of the Thirteenth International Conference, 1996 .— P.1-9.
  6. Freund Y. A Short Introduction to Boosting / Y.Freund, R.Schapire // Journal of Japanese Society for Artificial Intelligence .— 1999 .— №14(5) .— P.771-780.
  7. Friedman J. Additive logistic regression: astatistical view of boosting / J.Friedman, T.Hastie, R.Tibshirani // The Annals of Statistics .— 2000 .— №2(28) .— P.337-407.
  8. Natekin A. Gradient boosting machines,a tutorial / A.Natekin, A.Knoll // Frontiers in Neurorobotics .— 2013 .— №7 .— P.1-21.
  9. Harsh Pareek. Human Boosting / Harsh Pareek, Pradeep Ravikumar // 30 th International Conference on Machine Learning .— Atlanta, Georgia, USA, 2013 .— P.1-9.
  10. Tieu K. Boosting Image Retrieval / K.Tieu, P.Viola // IEEE Conference on Computer Vision and Pattern Recognition, 2000 .— P.1-8.
  11. Using LogitBoost classifier to predict protein structural classes / .Yu-DongCai, .Kai-YanFeng, .Wen-CongLu, .Kuo-ChenChou // Journal of Theoretical Biology .— 2006 .— №1(238) .— P.172-176.
  12. Weiming Hu. AdaBoost-Based Algorithm for Network Intrusion Detection / Weiming Hu, Wei Hu, S.Maybank // IEEE Transaction on Systems, MAN, and Cybernetics—Part B: Cybernetics .— 2008 .— №2(38) .— P.577-583.
  13. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации / Ю.И.Журавлев // Проблемы кибернетики .— 1978 .— №33 .— C.5-68.
  14. Казаков А. Быстрый Алгоритм Обнаружения Пешеходов по Видеоданным / А.Казаков, А.Бовырин // The 22nd International Conference on Computer Graphics and Vision .— GraphiCon’2012, 2012 .— C.144-148.
  15. Мурыгин К.В. Особенности реализации алгоритма AdaBoost для обнаружения объектов на изображениях / К.В.Мурыгин // Штучний інтелект .— 2009 .— №3 .— C.573-581.

Вопрос-ответ.

Задать вопрос: