http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=46.166.104.71&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T08:08:37ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B8%D0%B4%D1%8B_%D0%B0%D0%BD%D1%81%D0%B0%D0%BC%D0%B1%D0%BB%D0%B5%D0%B9&diff=74396Виды ансамблей2020-06-06T08:48:28Z<p>46.166.104.71: /* Реализации и применения бустинга */ Видимо, перепутали местами описание LightGBM и CatBoost</p>
<hr />
<div>== Ансамбль == <br />
<br />
Ансамбль алгоритмов (методов) — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности.<br />
<br />
Рассмотрим задачу классификации на <tex> K </tex> классов: <tex>Y = \{1, 2, ..., K\}</tex>. <br><br />
Пусть имеется <tex> M </tex> классификаторов ("экспертов"): <tex> f_1, f_2, ..., f_M </tex>. <br> <br />
<tex> f_m : X \rightarrow Y, f_m \in F, m = (1 ... M) </tex>. <br><br />
<br />
Тогда давайте посмотрим новый классификатор на основе данных:<br />
<br />
Простое голосование: <tex> f(x) = \max \limits_{k = 1 .. K} \sum \limits_{i = 1}^M I(f_i(x) = k) </tex>. <br><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>. <br><br />
Где <tex> \begin{equation*}<br />
I(x) = \begin{cases}<br />
1 &\text{x = true}\\<br />
0 &\text{x = false}<br />
\end{cases}<br />
\end{equation*}<br />
</tex><br />
<br />
== Теорема Кондорсе о присяжных ==<br />
<br />
{{Теорема<br />
|statement=<br />
Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри, и стремится к единице. <br><br />
Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных.<br />
}}<br />
<br />
Пусть <tex>M</tex> — количество присяжных, <tex>p</tex> — вероятность правильного решения одного эксперта, <tex>R</tex> — вероятность правильного решения всего жюри,<br />
<tex>m</tex> — минимальное большинство членов жюри <tex> = \lfloor \frac N 2 \rfloor + 1 </tex>.<br />
<br />
Тогда <tex> R = \sum \limits_{i = m}^M C_M^i p ^ i (1 - p) ^ {M - i} </tex><br />
<br />
[[Файл:Виды_Ансамблей_2.png|none|400px|thumb|Вероятность правильного решения всего жюри (R) в зависимости от вероятности правильного решения одного эксперта (p) при разном количестве экспертов(M)]]<br />
<br />
== Бэггинг ==<br />
<br />
Пусть имеется выборка <tex>X</tex> размера <tex>N</tex>. Количество классификаторов <tex>M</tex>.<br />
<br />
Алгоритм использует метод бутстрэпа (англ. ''bootstrap''):<br />
<br />
Из всего множества объектов равновероятно выберем N объектов с возвращением. Это значит, что после выбора каждого из объектов мы будем возращать его в множество для выбора. Отметим, что из-за возвращения некоторые объекты могут повторяться в выбранном множестве.<br> Обозначим новую выборку через <tex>X_1</tex>. Повторяя процедуру <tex>M</tex> раз, сгенерируем <tex>M</tex> подвыборок <tex>X_1 ... X_M</tex>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.<br />
<br />
Шаги алгоритма бэггинг:<br />
<ul><br />
<li> Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.<br />
<li> Производится независимое обучения каждого элементарного классификатора (каждого алгоритма, определенного на своем подпространстве).<br />
<li> Производится классификация основной выборки на каждом из подпространств (также независимо).<br />
<li> Принимается окончательное решение о принадлежности объекта одному из классов. Это можно сделать несколькими разными способами, подробнее описано ниже.<br />
</ul><br />
<br />
<br />
Окончательное решение о принадлежности объекта классу может приниматься, например, одним из следующих методов:<br />
<ul><br />
<li> Консенсус: если все элементарные классификаторы присвоили объекту одну и ту же метку, то относим объект к выбранному классу.<br />
<li> Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.<br />
<li> Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для экспертов одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес. <br />
</ul><br />
<br />
[[Файл:Виды_ансамблей_Бэггинг_рус.png|none|800px]]<br />
<br />
<br />
Рассмотрим задачу регрессии с базовыми алгоритмами <tex>b_1, b_2, ..., b_m</tex>. Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:<br />
<br />
<tex> \epsilon_i(x) = b_i(x) - y(x), y = 1, ..., n </tex><br />
<br />
и записать матожидание среднеквадратичной ошибки:<br />
<br />
<tex>E_x(b_i(x) - y(x))^2 = E_x \epsilon_i^2(x) </tex><br />
<br />
Средняя ошибка построенных функций регрессии имеет вид: <br />
<br />
<tex>E_1 = \frac 1 n E_x \sum \limits_{i = 1}^n \epsilon_i^2(x) </tex><br />
<br />
Предположим, что ошибки несмещены и некоррелированы: <br />
<br />
<tex> E_x\epsilon_i(x) = 0, E_x\epsilon_i(x)\epsilon_j(x) = 0, i ≠ j </tex><br />
<br />
Построим теперь новую функцию регрессии, усредняющую ответы уже построенных:<br />
<br />
<tex> a(x) = \frac 1 n \sum \limits_{i = 1}^n b_i(x) </tex><br />
<br />
Найдем ее среднеквадратичную ошибку:<br />
<br />
<tex> E_n = E_x(\frac 1 n \sum \limits_{i = 1}^n (b_i(x) - y(x))^2<br />
= E_x(\frac 1 n \sum \limits_{i = 1}^n \epsilon_i)^2<br />
= \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)) <br />
= \frac 1 n E_1 </tex><br />
<br />
Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в <tex>n</tex> раз.<br />
<br />
== Бустинг ==<br />
<br />
[[Бустинг, AdaBoost|'''Бустинг''']] (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.<br />
<br />
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.<br />
<br />
Задача состоит в том, чтоб найти такой алгоритм <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> — функция потерь.<br />
<br />
Очевидно, что сложно найти сразу <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>.<br />
<br />
Алгоритмы бустинга:<br />
<br />
<ul><br />
<li>[[Бустинг, AdaBoost|AdaBoost]] — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.<br />
<li>BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных<br />
<li>GradientBoost — алгоритм бустинга, использующий идеи линейной регресии<br />
<li>LogitBoost — алгоритм бустинга, использующий идеи логистической регресси<br />
</ul><br />
<br />
== Реализации и применения бустинга ==<br />
<br />
Реализации бустинга:<br />
<br />
* [[XGBoost|XGBoost]] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год. <br />
* [[CatBoost|CatBoost]] — открытая программная библиотека, разработанная компанией Яндекс.<br />
* LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).<br />
<br />
<br />
Применение бустинга:<br />
* поисковые системы<br />
* ранжирования ленты рекомендаций<br />
* прогноз погоды<br />
* оптимизации расхода сырья<br />
* предсказания дефектов при производстве.<br />
* исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.<br />
<br />
== Различия между алгоритмами == <br />
<br />
<ul><br />
<li> Оба алгоритма используют N базовых классификаторов<br />
<ul><br />
<li> Бустинг использует последовательное обучение </li><br />
<li> Бэггинг использует параллельное обучение </li><br />
</ul><br />
</li><br />
<li> Оба генерируют несколько наборов данных для обучения путем случайной выборки<br />
<ul><br />
<li> Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи </li><br />
<li> Бэггинг имеет невзвешенные данные </li><br />
</ul><br />
</li><br />
<li> Оба принимают окончательное решение, усредняя N классификаторов<br />
<ul> <br />
<li> В бустинге определяются веса для них </li><br />
<li> В бэггинге они равнозначны </li><br />
</ul><br />
</li><br />
<li> Оба уменьшают дисперсию и обеспечивают более высокую стабильность<br />
<ul><br />
<li> Бэггинг может решить проблему переобучения </li><br />
<li> Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения </li><br />
</ul><br />
</li> <br />
</ul><br />
<br />
== Примеры кода ==<br />
<br />
'''Инициализация'''<br />
<br />
from pydataset import data<br />
<br />
<font color="green">#Считаем данные The Boston Housing Dataset<ref>[http://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html The Boston Housing Dataset]</ref> </font><br />
df = data('Housing')<br />
<br />
<font color="green">#Проверим данные</font><br />
df.head().values<br />
array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'],<br />
[38500.0, 4000, 2, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'],<br />
[49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...<br />
<br />
<font color="green"># Создадим словарь для слов 'no', 'yes'</font><br />
d = dict(zip(['no', 'yes'], range(0,2)))<br />
for i in zip(df.dtypes.index, df.dtypes):<br />
if str(i[1]) == 'object':<br />
df[i[0]] = df[i[0]].map(d)<br />
df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes<br />
<br />
<font color="green"># Разделим множество на два</font><br />
y = df['price'] <br />
X = df.drop('price', 1)<br />
<br />
'''Бэггинг'''<br />
<br />
<font color="green"># Импорты классификаторов</font><br />
from sklearn.model_selection import cross_val_score<br />
from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier<br />
from sklearn.neighbors import KNeighborsClassifier<br />
from sklearn.linear_model import RidgeClassifier<br />
from sklearn.svm import SVC<br />
<br />
seed = 1075<br />
np.random.seed(seed)<br />
<font color="green"># Инициализуруем классификаторы</font><br />
rf = RandomForestClassifier()<br />
et = ExtraTreesClassifier()<br />
knn = KNeighborsClassifier()<br />
svc = SVC()<br />
rg = RidgeClassifier()<br />
clf_array = [rf, et, knn, svc, rg]<br />
<br />
for clf in clf_array:<br />
vanilla_scores = cross_val_score(clf, X, y, cv=10, n_jobs=-1)<br />
bagging_clf = BaggingClassifier(clf, max_samples=0.4, max_features=10, random_state=seed)<br />
bagging_scores = cross_val_score(bagging_clf, X, y, cv=10, n_jobs=-1)<br />
print "Mean of: {1:.3f}, std: (+/-) {2:.3f [{0}]" <br />
.format(clf.__class__.__name__, <br />
vanilla_scores.mean(), vanilla_scores.std())<br />
print "Mean of: {1:.3f}, std: (+/-) {2:.3f} [Bagging {0}]\n"<br />
.format(clf.__class__.__name__, <br />
bagging_scores.mean(), bagging_scores.std())<br />
<br />
<font color="green">#Результат</font><br />
Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier]<br />
Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier]<br />
<br />
Mean of: 0.636, std: (+/-) 0.080 [ExtraTreesClassifier]<br />
Mean of: 0.654, std: (+/-) 0.073 [Bagging ExtraTreesClassifier]<br />
<br />
Mean of: 0.500, std: (+/-) 0.086 [KNeighborsClassifier]<br />
Mean of: 0.535, std: (+/-) 0.111 [Bagging KNeighborsClassifier]<br />
<br />
Mean of: 0.465, std: (+/-) 0.085 [SVC]<br />
Mean of: 0.535, std: (+/-) 0.083 [Bagging SVC]<br />
<br />
Mean of: 0.639, std: (+/-) 0.050 [RidgeClassifier]<br />
Mean of: 0.597, std: (+/-) 0.045 [Bagging RidgeClassifier]<br />
<br />
'''Бустинг'''<br />
<br />
ada_boost = AdaBoostClassifier()<br />
grad_boost = GradientBoostingClassifier()<br />
xgb_boost = XGBClassifier()<br />
boost_array = [ada_boost, grad_boost, xgb_boost]<br />
eclf = EnsembleVoteClassifier(clfs=[ada_boost, grad_boost, xgb_boost], voting='hard')<br />
<br />
labels = ['Ada Boost', 'Grad Boost', 'XG Boost', 'Ensemble']<br />
for clf, label in zip([ada_boost, grad_boost, xgb_boost, eclf], labels):<br />
scores = cross_val_score(clf, X, y, cv=10, scoring='accuracy')<br />
print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))<br />
<br />
<font color="green"># Результат</font><br />
Mean: 0.641, std: (+/-) 0.082 [Ada Boost]<br />
Mean: 0.654, std: (+/-) 0.113 [Grad Boost]<br />
Mean: 0.663, std: (+/-) 0.101 [XG Boost]<br />
Mean: 0.667, std: (+/-) 0.105 [Ensemble]<br />
<br />
== См. также ==<br />
* [[:Бустинг, AdaBoost|Бустинг, AdaBoost]]<br />
* [[:XGBoost|XGBoost]]<br />
* [[:CatBoost|CatBoost]]<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
== Источники информации ==<br />
<br />
* https://github.com/Microsoft/LightGBM<br />
* https://github.com/dmlc/xgboost<br />
* https://ru.wikipedia.org/wiki/CatBoost<br />
* https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/<br />
* https://medium.com/@rrfd/boosting-bagging-and-stacking-ensemble-methods-with-sklearn-and-mlens-a455c0c982de<br />
<br />
[[Категория: Машинное обучение]]<br />
[[Категория: Ансамбли]]</div>46.166.104.71