68
правок
Изменения
→Источники информации
== Ансамбль ==
Ансамбль алгоритмов (методов) - — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности.
Рассмотрим задачу классификации на K классов: <tex>Y = \{1, 2, ..., K\}</tex> . <br>Пусть имеется M классификатор ("экспертов"): <tex> f_1, f_2, ..., f_M </tex> . <br> <tex> f_m : X \leftarrow Y, f_m \in F, m = (1 ... M) </tex> . <br>
Тогда давайте посмотрим новый классификатор на основе данных:
Простое голосование: <tex> f(x) = \max \limits_{k = 1 .. K} \sum \limits_{i = 1}^M I(f_i(x) = k) </tex> . <br>Взвешенное голосование: <tex> f(x) = \max \limits_{k = 1 .. K} \sum \limits_{i = 1}^M \alpha_i I(f_i(x) = k), \sum \limits_i \alpha_i = 1, \alpha_i > 0</tex>.
== Теорема Кондорсе о присяжных ==
}}
Пусть <tex>M</tex> - — количество присяжный, <tex>p</tex> - — вероятность правильного решения одного эксперта, <tex>R</tex> - — вероятность правильного решения всего жюри,<tex>m</tex> - — минимальное большинство членов жюри <tex> = \lfloor \frac N 2 \rfloor + 1 </tex>.
Тогда <tex> R = \sum \limits_{i = m}^M C_M^i p ^ i (1 - p) ^ {M - i} </tex>
== Бэггинг ==
Пусть имеется выборка <tex>X</tex> размера <tex>N</tex>. Количество классификаторов <tex>M</tex>. Для алгоритма нам понадобится метод бутстрэпа (англ. ''bootstrap''): Равномерно возьмем из выборки <tex>N</tex> объектов с возвращением. Это означает, что мы будем <tex>N</tex> раз равновероятно выбирать произвольный объект выборки, причем каждый раз мы выбираем из всех исходных <tex>N</tex> объектов. Отметим, что из-за возвращения среди них окажутся повторы. <br>Обозначим новую выборку через <tex>X_1</tex>. Повторяя процедуру <tex>M</tex> раз, сгенерируем <tex>M</tex> подвыборок <tex>X_1 ... X_M</tex>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
Алгоритм классификации в технологии бэггинг на подпространствах:
<ul>
<li> Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.
<li> Производится независимое обучения каждого элементарного классификатора (каждого алгоритма, определенного на своем подпространстве).
<li> Производится классификация основной выборки на каждом из подпространств (также независимо).
<li> Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.
<li> Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для эксперты одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес.
</ul>
[[Файл:Виды_ансамблей_Бэггинг.png]]
Рассмотрим задачу регрессии с базовыми алгоритмами <tex>b_1, b_2, ..., b_m</tex>. Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:
<tex> \epsilon_i(x) = b_i(x) - y(x), y = 1, ..., n </tex>
и записать матожидание среднеквадратичной ошибки:
<tex>E_x(b_i(x) - y(x))^2 = E_x \epsilon_i^2(x) </tex>
Средняя ошибка построенных функций регрессии имеет вид:
<tex>E_1 = \frac 1 n E_x \sum \limits_{i = 1}^n \epsilon_i^2(x) </tex>
Предположим, что ошибки несмещены и некоррелированы:
<tex> E_x\epsilon_i(x) = 0, E_x\epsilon_i(x)\epsilon_j(x) = 0, i ≠ j </tex>
Построим теперь новую функцию регрессии, которая будет усреднять ответы построенных нами функций:
<tex> a(x) = \frac 1 n \sum \limits_{i = 1}^n b_i(x) </tex>
Найдем ее среднеквадратичную ошибку:
<tex> E_n = E_x(\frac 1 n \sum \limits_{i = 1}^n (b_i(x) - y(x))^2
= E_x(\frac 1 n \sum \limits_{i = 1}^n \epsilon_i)^2
= \frac 1 {n^2} E_x(\sum \limits_{i = 1}^n \epsilon_i^2(x) + \sum \limits_{i ≠ j} \epsilon_i(x)\epsilon_j(x))
= \frac 1 n E_1 </tex>
Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в <tex>n</tex> раз.
== Бустинг ==
'''Бустинг''' (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.
Задача состоит в том, чтоб найти такой алгоритм <tex>H_T(x) = \sum_{t=1}^T b_t h(x, a),</tex> где <tex>b_t \in \mathbb{R}</tex> — коэффиценты, такие, чтобы минимизировать эмпирический риск <tex>Q = \sum_i L(H_T(x_i), y_i) \rightarrow min</tex>, где <tex>L(H_T(x_i), y_i)</tex> — функция потерь.
Очевидно, что сложно найти сразу <tex>\{(a_t, b_t)\}_{t=1}^T.</tex> Основная идея в том, чтоб найти решение пошагово <tex>H_t(x) = H_{t — 1}(x) + b_t h(x, a_t)</tex>. Таким образом мы сможем постепенно оценивать изменение эмпирического риска <tex>Q^{(t)} = \sum_{i = 1}^l L(H_t(x_i), y_i) </tex>.
Алгоритмы бустинга:
<li>[[Бустинг, AdaBoost|AdaBoost]] — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
<li>BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
<li>GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
<li>LogitBoost — алгоритм бустинга, использующий идеи логистической регресси
== Реализации и применения бустинга ==
Реализации бустинга:
<ul>
<li> CatBoost — открытая программная библиотека разработанная компанией Яндекс
<li> XGBoost — изначально исследовательский проект Tianqi Chen, сейчас открытая программная библиотека, поддерживая сообществом
<ul>
<li> Rapids — проект NVIDIA, созданный для использования GPU с XGBooost
</ul>
<li> LightGBM — открытая программная библиотека разработанная компанией Яндекс
</ul>
Применение бустинга:
<ul>
<li> поисковые системы
<li> ранжирования ленты рекомендаций
<li> прогноз погоды
<li> оптимизации расхода сырья
<li> предсказания дефектов при производстве.
<li> исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
</ul>
== Различия между алгоритмами ==
<ul>
<li> Оба алгоритма используют N базовых классификаторов
<ul>
<li> Бустинг использует последовательное обучение </li>
<li> Бэггинг использует параллельное обучение </li>
</ul>
</li>
<li> Оба генерируют несколько наборов обучающих данных путем случайной выборки
<ul>
<li> Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи </li>
<li> Бэггинг имеет невзвешенные данные </li>
</ul>
</li>
<li> Оба принимают окончательное решение, усредняя N учеников
<ul>
<li> В бустинге определяются веса классификаторов </li>
<li> В бэггинге все классификаторы равнозначны </li>
</ul>
</li>
<li> Оба уменьшают дисперсию и обеспечивают более высокую стабильность
<ul>
<li> Бэггинг может решить проблему переобучение </li>
<li> Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения </li>
</ul>
</li>
</ul>
== Источники информации ==
* https://github.com/Microsoft/LightGBM
* https://github.com/dmlc/xgboost
* https://ru.wikipedia.org/wiki/CatBoost
* https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/
* https://medium.com/@rrfd/boosting-bagging-and-stacking-ensemble-methods-with-sklearn-and-mlens-a455c0c982de
* https://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html
