Изменения

Ансамбль алгоритмов (методов) — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности. Рассмотрим задачу классификации на 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>. == Теорема Кондорсе о присяжных ==

{{Теорема|statement== Вероятность ошибки ==Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри, и стремиться к единице. <br>Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных.}}

Пусть <tex>M</tex> - — количество присяжный, <tex>p</tex> - — вероятность правильного решения одного эксперта, <tex>R</tex> - — вероятность правильного решения всего жюри,<tex>m</tex> - — минимальное большинство членов жюри <tex> = floor(\lfloor \frac N / 2) \rfloor + 1 </tex>.

https[[Файл://yadiВиды_Ансамблей_2.sk/i/4GVy9FPDJnL-cQpng|none|400px|thumb|Вероятность правильного решения всего жюри (R) в зависимости от вероятности правильного решения одного эксперта (p) при разном количестве экспертов(M)]]https://yadi.sk/i/Tjwyk4Bkc2Ck3g== Бэггинг ==

== Бутстрэп ==Метод бутстрэпа (англПусть имеется выборка <tex>X</tex> размера <tex>N</tex>. ''bootstrap'') — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений. Этот алгоритм применяется для классификации многомерных объектов. Рассматриваемый алгоритм помогает добиться качественной классификации в условиях, когда разделить объекты на группы на всем пространстве параметров не представляется возможнымКоличество классификаторов <tex>M</tex>.

Пусть имеется выборка Для алгоритма нам понадобится метод бутстрэпа (англ. ''bootstrap''):  Равномерно возьмем из выборки <tex>XN</tex> размера объектов с возвращением. Это означает, что мы будем <tex>N</tex> раз равновероятно выбирать произвольный объект выборки, причем каждый раз мы выбираем из всех исходных <tex>N</tex> объектов. Отметим, что из-за возвращения среди них окажутся повторы. <br>Обозначим новую выборку через <tex>X_1</tex>. Количество классификаторов Повторяя процедуру <tex>M</tex>раз, сгенерируем <tex>M</tex> подвыборок <tex>X_1 ... X_M</tex>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.

<li> Равномерно берется из выборки <tex>N</tex> объектов Генерируется с возвращением. Это означает, что <tex>помощью бутстрэпа M выборок размера N</tex> раз выбирается произвольный объект выборки (считается, что каждый объект «достается» с одинаковой вероятностью), причем каждый раз из всех исходных объектов. Повторяется данная процедура <tex>M</tex> раз, получая для каждого классификатора свою выборку.

== Бэггинг ==[[Файл:Виды_ансамблей_Бэггинг.png]] Рассмотримзадачу регрессии с базовыми алгоритмами <tex>b_1, b_2, ..., b_m</tex>. Предположим, что существует истинная функция ответа для всех объектов y(x), следующий вид ансамбля — бэггинг а также задано распределение p(англx) на объектах. ''bootstrap aggregation''В этом случае мы можем записать ошибку каждой функции регрессии: <tex> \epsilon_i(x) = b_i(x) - y(x), y = 1, . Пусть имеется обучающая выборка .., n </tex> и записать матожидание среднеквадратичной ошибки: <tex>XE_x(b_i(x) - y(x))^2 = E_x \epsilon_i^2(x) </tex>. С помощью бутстрэпа сгенерируем из неё выборки  Средняя ошибка построенных функций регрессии имеет вид:  <tex>X_1 ... X_ME_1 = \frac 1 n E_x \sum \limits_{i = 1}^n \epsilon_i^2(x) </tex>. Теперь на каждой выборке обучим свой классификатор  Предположим, что ошибки несмещены и некоррелированы:  <tex>a_iE_x\epsilon_i(x) = 0, E_x\epsilon_i(x)\epsilon_j(x) = 0, i ≠ j </tex>. Итоговый классификатор  Построим теперь новую функцию регрессии, которая будет усреднять ответы всех этих алгоритмов построенных нами функций: <tex>a(x) = \frac1 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_{Mi = 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_{Mt — 1} a_i(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> == Примеры кода == '''Инициализация'''  from pydataset import data #Считаем данные The Boston Housing Dataset df = data('Housing')  #Проверим данные df.head().values array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'], [38500.0, 4000, 2, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], [49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...  # Создадим словарь для слов 'no', 'yes' d = dict(zip(['no', 'yes'], range(0,2))) for i in zip(df.dtypes.index, df.dtypes): if str(i[1]) == 'object': df[i[0]] = df[i[0]].map(d) df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes # Разделим множество на два y = df['price'] X = df.drop('price', 1) '''Бэггинг'''  # Импорты классификаторов from sklearn.model_selection import cross_val_score from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier from sklearn.neighbors import KNeighborsClassifier from sklearn.linear_model import RidgeClassifier from sklearn.svm import SVC seed = 1075 np.random.seed(seed) # Инициализуруем классификаторы rf = RandomForestClassifier() et = ExtraTreesClassifier() knn = KNeighborsClassifier() svc = SVC() rg = RidgeClassifier() clf_array = [rf, et, knn, svc, rg] for clf in clf_array: vanilla_scores = cross_val_score(clf, X, y, cv=10, n_jobs=-1) bagging_clf = BaggingClassifier(clf, max_samples=0.4, max_features=10, random_state=seed) bagging_scores = cross_val_score(bagging_clf, X, y, cv=10, n_jobs=-1) print "Mean of: {1:.3f}, std: (+/-) {2:.3f [{0}]" .format(clf.__class__.__name__, vanilla_scores.mean(), vanilla_scores.std()) print "Mean of: {1:.3f}, std: (+/-) {2:.3f} [Bagging {0}]\n" .format(clf.__class__.__name__, bagging_scores.mean(), bagging_scores.std())  #Результат Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier] Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier] Mean of: 0.636, std: (+/-) 0.080 [ExtraTreesClassifier] Mean of: 0.654, std: (+/-) 0.073 [Bagging ExtraTreesClassifier] Mean of: 0.500, std: (+/-) 0.086 [KNeighborsClassifier] Mean of: 0.535, std: (+/-) 0.111 [Bagging KNeighborsClassifier] Mean of: 0.465, std: (+/-) 0.085 [SVC] Mean of: 0.535, std: (+/-) 0.083 [Bagging SVC] Mean of: 0.639, std: (+/-) 0.050 [RidgeClassifier] Mean of: 0.597, std: (+/-) 0.045 [Bagging RidgeClassifier] '''Бустинг'''  ada_boost = AdaBoostClassifier() grad_boost = GradientBoostingClassifier() xgb_boost = XGBClassifier() boost_array = [ada_boost, grad_boost, xgb_boost] eclf = EnsembleVoteClassifier(clfs=[ada_boost, grad_boost, xgb_boost], voting='hard') labels = ['Ada Boost', 'Grad Boost', 'XG Boost', 'Ensemble'] for clf, label in zip([ada_boost, grad_boost, xgb_boost, eclf], labels): scores = cross_val_score(clf, X, y, cv=10, scoring='accuracy') print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))  # Результат Mean: 0.641, std: (+/-) 0.082 [Ada Boost] Mean: 0.654, std: (+/-) 0.113 [Grad Boost] Mean: 0.663, std: (+/-) 0.101 [XG Boost] Mean: 0.667, std: (+/-) 0.105 [Ensemble] == Источники информации == * 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