Виды ансамблей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема Кондорсе о присяжных)
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 4 участников)
Строка 3: Строка 3:
 
Ансамбль алгоритмов (методов) — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности.
 
Ансамбль алгоритмов (методов) — метод, который использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем можно было бы получить от каждого обучающего алгоритма по отдельности.
  
Рассмотрим задачу классификации на K классов: <tex>Y = \{1, 2, ..., K\}</tex> <br>
+
Рассмотрим задачу классификации на <tex> K </tex> классов: <tex>Y = \{1, 2, ..., K\}</tex>. <br>
Пусть имеется M классификатор ("экспертов"): <tex> f_1, f_2, ..., f_M </tex> <br>  
+
Пусть имеется <tex> M </tex> классификаторов ("экспертов"): <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_m : X \rightarrow 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 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> 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>
 +
Где <tex> \begin{equation*}
 +
I(x) = \begin{cases}
 +
  1 &\text{x = true}\\
 +
  0 &\text{x = false}
 +
\end{cases}
 +
\end{equation*}
 +
</tex>
  
 
== Теорема Кондорсе о присяжных ==
 
== Теорема Кондорсе о присяжных ==
Строка 16: Строка 23:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри, и стремиться к единице. <br>
+
Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри, и стремится к единице. <br>
 
Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных.
 
Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных.
 
}}
 
}}
  
Пусть <tex>M</tex> — количество присяжный, <tex>p</tex> — вероятность правильного решения одного эксперта, <tex>R</tex> — вероятность правильного решения всего жюри,
+
Пусть <tex>M</tex> — количество присяжных, <tex>p</tex> — вероятность правильного решения одного эксперта, <tex>R</tex> — вероятность правильного решения всего жюри,
<tex>m</tex> — минимальное большинство членов жюри <tex> = \lfloor \frac N  2 \rfloor + 1 </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> R = \sum \limits_{i = m}^M C_M^i  p ^ i (1 - p) ^ {M - i} </tex>
  
[[Файл:Виды_Ансамблей_1.png]][[Файл:Виды_Ансамблей_2.png]]
+
[[Файл:Виды_Ансамблей_2.png|none|400px|thumb|Вероятность правильного решения всего жюри (R) в зависимости от вероятности правильного решения одного эксперта (p) при разном количестве экспертов(M)]]
  
 
== Бэггинг ==
 
== Бэггинг ==
  
Пусть имеется выборка <tex>X</tex> размера <tex>N</tex>. Количество классификаторов <tex>M</tex>
+
Пусть имеется выборка <tex>X</tex> размера <tex>N</tex>. Количество классификаторов <tex>M</tex>.
  
Для алгоритма нам понадобится метод бутстрэпа (англ. ''bootstrap''):
+
Алгоритм использует метод бутстрэпа (англ. ''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>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
+
     Из всего множества объектов равновероятно выберем N объектов с возвращением. Это значит, что после выбора каждого из объектов мы будем возращать его в множество для выбора. Отметим, что из-за возвращения некоторые объекты могут повторяться в выбранном множестве.<br>   Обозначим новую выборку через <tex>X_1</tex>. Повторяя процедуру <tex>M</tex> раз, сгенерируем <tex>M</tex> подвыборок <tex>X_1 ... X_M</tex>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
  
Алгоритм классификации в технологии бэггинг на подпространствах:
+
Шаги алгоритма бэггинг:
 
<ul>
 
<ul>
 
<li> Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.
 
<li> Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.
Строка 48: Строка 55:
 
<li> Консенсус: если все элементарные классификаторы присвоили объекту одну и ту же метку, то относим объект к выбранному классу.
 
<li> Консенсус: если все элементарные классификаторы присвоили объекту одну и ту же метку, то относим объект к выбранному классу.
 
<li> Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.
 
<li> Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.
<li> Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для эксперты одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес.  
+
<li> Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для экспертов одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес.  
 
</ul>
 
</ul>
  
[[Файл:Виды_ансамблей_Бэггинг.png]]
+
[[Файл:Виды_ансамблей_Бэггинг_рус.png|none|800px]]
 +
 
  
 
Рассмотрим задачу регрессии с базовыми алгоритмами <tex>b_1, b_2, ..., b_m</tex>. Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:
 
Рассмотрим задачу регрессии с базовыми алгоритмами <tex>b_1, b_2, ..., b_m</tex>. Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:
Строка 69: Строка 77:
 
<tex> E_x\epsilon_i(x) = 0, E_x\epsilon_i(x)\epsilon_j(x) = 0, i ≠ j </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> a(x) = \frac 1 n \sum \limits_{i = 1}^n b_i(x) </tex>
Строка 80: Строка 88:
 
= \frac 1 n E_1 </tex>
 
= \frac 1 n E_1 </tex>
  
Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в <tex>n</tex> раз
+
Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в <tex>n</tex> раз.
  
 
== Бустинг ==
 
== Бустинг ==
  
Бустинг (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов
+
[[Бустинг, AdaBoost|'''Бустинг''']] (англ. 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>.
  
=== AdaBoost ===
+
Алгоритмы бустинга:
 +
 
 +
<ul>
 +
<li>[[Бустинг, AdaBoost|AdaBoost]]  — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
 +
<li>BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
 +
<li>GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
 +
<li>LogitBoost — алгоритм бустинга, использующий идеи логистической регресси
 +
</ul>
  
Алгоритм AdaBoost (сокр. от adaptive boosting) — алгоритм машинного обучения, предложенный Йоавом Фройндом (Yoav Freund) и Робертом Шапиром (Robert Schapire). Является мета-алгоритмом, в процессе обучения строит композицию из базовых алгоритмов обучения для улучшения их эффективности. AdaBoost является алгоритмом адаптивного бустинга в том смысле, что каждый следующий классификатор строится по объектам, которые плохо классифицируются предыдущими классификаторами.
+
== Реализации и применения бустинга ==
  
AdaBoost вызывает слабый классификатор в цикле. После каждого вызова обновляется распределение весов, которые отвечают важности каждого из объектов обучающего множества для классификации. На каждой итерации веса каждого неверно классифицированного объекта возрастают, таким образом новый классификатор «фокусирует своё внимание» на этих объектах.
+
Реализации бустинга:
  
 +
* [[XGBoost|XGBoost]] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.
 +
* [[CatBoost|CatBoost]] — открытая программная библиотека, разработанная компанией Яндекс.
 +
* LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).
  
  
'''Достоинства'''
+
Применение бустинга:
 +
* поисковые системы
 +
* ранжирования ленты рекомендаций
 +
* прогноз погоды
 +
* оптимизации расхода сырья
 +
* предсказания дефектов при производстве.
 +
* исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
  
<li> Хорошая обобщающая способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов.
+
== Различия между алгоритмами ==
<li> Простота реализации.
 
<li> Собственные накладные расходы бустинга невелики. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
 
<li> Возможность идентифицировать объекты, являющиеся шумовыми выбросами.
 
  
'''Недостатки'''
+
<ul>
<li> AdaBoost склонен к переобучению при наличии значительного уровня шума в данных. Экспоненциальная функция потерь слишком сильно увеличивает веса наиболее трудных объектов, на которых ошибаются многие базовые алгоритмы. Однако именно эти объекты чаще всего оказываются шумовыми выбросами. В результате AdaBoost начинает настраиваться на шум, что ведёт к переобучению. Проблема решается путём удаления выбросов или применения менее агрессивных функций потерь.
+
<li> Оба алгоритма используют N базовых классификаторов
<li> AdaBoost требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
+
  <ul>
<li>Жадная стратегия последовательного добавления приводит к построению неоптимального набора базовых алгоритмов. Для улучшения композиции можно периодически возвращаться к ранее построенным алгоритмам и обучать их заново. Для улучшения коэффициентов можно оптимизировать их ещё раз по окончании процесса бустинга с помощью какого-нибудь стандартного метода построения линейной разделяющей поверхности. Рекомендуется использовать для этой цели SVM (машины опорных векторов).
+
    <li> Бустинг использует последовательное обучение </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>
  
 
== Примеры кода ==
 
== Примеры кода ==
Строка 113: Строка 161:
 
     from pydataset import data
 
     from pydataset import data
 
      
 
      
     #Считаем данные The Boston Housing Dataset
+
     <font color="green">#Считаем данные The Boston Housing Dataset<ref>[http://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html The Boston Housing Dataset]</ref> </font>
 
     df = data('Housing')
 
     df = data('Housing')
  
     #Проверим данные
+
     <font color="green">#Проверим данные</font>
 
     df.head().values
 
     df.head().values
 
     array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'],
 
     array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'],
Строка 122: Строка 170:
 
           [49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...
 
           [49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...
  
     # Создадим словарь для слов 'no', 'yes'
+
     <font color="green"># Создадим словарь для слов 'no', 'yes'</font>
 
     d = dict(zip(['no', 'yes'], range(0,2)))
 
     d = dict(zip(['no', 'yes'], range(0,2)))
 
     for i in zip(df.dtypes.index, df.dtypes):
 
     for i in zip(df.dtypes.index, df.dtypes):
Строка 129: Строка 177:
 
     df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes
 
     df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes
 
      
 
      
     # Разделим множество на два
+
     <font color="green"># Разделим множество на два</font>
 
     y = df['price']  
 
     y = df['price']  
 
     X = df.drop('price', 1)
 
     X = df.drop('price', 1)
Строка 135: Строка 183:
 
'''Бэггинг'''
 
'''Бэггинг'''
  
     # Импорты классификаторов
+
     <font color="green"># Импорты классификаторов</font>
 
     from sklearn.model_selection import cross_val_score
 
     from sklearn.model_selection import cross_val_score
 
     from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier
 
     from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier
Строка 144: Строка 192:
 
     seed = 1075
 
     seed = 1075
 
     np.random.seed(seed)
 
     np.random.seed(seed)
     # Инициализуруем классификаторы
+
     <font color="green"># Инициализуруем классификаторы</font>
 
     rf = RandomForestClassifier()
 
     rf = RandomForestClassifier()
 
     et = ExtraTreesClassifier()
 
     et = ExtraTreesClassifier()
Строка 163: Строка 211:
 
                             bagging_scores.mean(), bagging_scores.std())
 
                             bagging_scores.mean(), bagging_scores.std())
  
     #Результат
+
     <font color="green">#Результат</font>
 
     Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier]
 
     Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier]
 
     Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier]
 
     Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier]
Строка 192: Строка 240:
 
         print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))
 
         print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))
  
     # Результат
+
     <font color="green"># Результат</font>
 
     Mean: 0.641, std: (+/-) 0.082 [Ada Boost]
 
     Mean: 0.641, std: (+/-) 0.082 [Ada Boost]
 
     Mean: 0.654, std: (+/-) 0.113 [Grad Boost]
 
     Mean: 0.654, std: (+/-) 0.113 [Grad Boost]
 
     Mean: 0.663, std: (+/-) 0.101 [XG Boost]
 
     Mean: 0.663, std: (+/-) 0.101 [XG Boost]
 
     Mean: 0.667, std: (+/-) 0.105 [Ensemble]
 
     Mean: 0.667, std: (+/-) 0.105 [Ensemble]
 +
 +
== См. также ==
 +
* [[:Бустинг, AdaBoost|Бустинг, AdaBoost]]
 +
* [[:XGBoost|XGBoost]]
 +
* [[:CatBoost|CatBoost]]
 +
 +
== Примечания ==
 +
<references/>
  
 
== Источники информации ==
 
== Источники информации ==
  
 +
* 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://medium.com/@rrfd/boosting-bagging-and-stacking-ensemble-methods-with-sklearn-and-mlens-a455c0c982de
* https://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html
+
 
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Ансамбли]]

Текущая версия на 19:15, 4 сентября 2022

Ансамбль

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

Рассмотрим задачу классификации на [math] K [/math] классов: [math]Y = \{1, 2, ..., K\}[/math].
Пусть имеется [math] M [/math] классификаторов ("экспертов"): [math] f_1, f_2, ..., f_M [/math].
[math] f_m : X \rightarrow Y, f_m \in F, m = (1 ... M) [/math].

Тогда давайте посмотрим новый классификатор на основе данных:

Простое голосование: [math] f(x) = \max \limits_{k = 1 .. K} \sum \limits_{i = 1}^M I(f_i(x) = k) [/math].
Взвешенное голосование: [math] 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 \gt 0[/math].
Где [math] \begin{equation*} I(x) = \begin{cases} 1 &\text{x = true}\\ 0 &\text{x = false} \end{cases} \end{equation*} [/math]

Теорема Кондорсе о присяжных

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

Пусть [math]M[/math] — количество присяжных, [math]p[/math] — вероятность правильного решения одного эксперта, [math]R[/math] — вероятность правильного решения всего жюри, [math]m[/math] — минимальное большинство членов жюри [math] = \lfloor \frac N 2 \rfloor + 1 [/math].

Тогда [math] R = \sum \limits_{i = m}^M C_M^i p ^ i (1 - p) ^ {M - i} [/math]

Вероятность правильного решения всего жюри (R) в зависимости от вероятности правильного решения одного эксперта (p) при разном количестве экспертов(M)

Бэггинг

Пусть имеется выборка [math]X[/math] размера [math]N[/math]. Количество классификаторов [math]M[/math].

Алгоритм использует метод бутстрэпа (англ. bootstrap):

   Из всего множества объектов равновероятно выберем N объектов с возвращением. Это значит, что после выбора каждого из объектов мы будем возращать его в множество для выбора. Отметим, что из-за возвращения некоторые объекты могут повторяться в выбранном множестве.
Обозначим новую выборку через [math]X_1[/math]. Повторяя процедуру [math]M[/math] раз, сгенерируем [math]M[/math] подвыборок [math]X_1 ... X_M[/math]. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.

Шаги алгоритма бэггинг:

  • Генерируется с помощью бутстрэпа M выборок размера N для каждого классификатора.
  • Производится независимое обучения каждого элементарного классификатора (каждого алгоритма, определенного на своем подпространстве).
  • Производится классификация основной выборки на каждом из подпространств (также независимо).
  • Принимается окончательное решение о принадлежности объекта одному из классов. Это можно сделать несколькими разными способами, подробнее описано ниже.


Окончательное решение о принадлежности объекта классу может приниматься, например, одним из следующих методов:

  • Консенсус: если все элементарные классификаторы присвоили объекту одну и ту же метку, то относим объект к выбранному классу.
  • Простое большинство: консенсус достижим очень редко, поэтому чаще всего используют метод простого большинства. Здесь объекту присваивается метка того класса, который определило для него большинство элементарных классификаторов.
  • Взвешивание классификаторов: если классификаторов четное количество, то голосов может получиться поровну, еще возможно, что для экспертов одна из групп параметров важна в большей степени, тогда прибегают к взвешиванию классификаторов. То есть при голосовании голос классификатора умножается на его вес.
Виды ансамблей Бэггинг рус.png


Рассмотрим задачу регрессии с базовыми алгоритмами [math]b_1, b_2, ..., b_m[/math]. Предположим, что существует истинная функция ответа для всех объектов y(x), а также задано распределение p(x) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:

[math] \epsilon_i(x) = b_i(x) - y(x), y = 1, ..., n [/math]

и записать матожидание среднеквадратичной ошибки:

[math]E_x(b_i(x) - y(x))^2 = E_x \epsilon_i^2(x) [/math]

Средняя ошибка построенных функций регрессии имеет вид:

[math]E_1 = \frac 1 n E_x \sum \limits_{i = 1}^n \epsilon_i^2(x) [/math]

Предположим, что ошибки несмещены и некоррелированы:

[math] E_x\epsilon_i(x) = 0, E_x\epsilon_i(x)\epsilon_j(x) = 0, i ≠ j [/math]

Построим теперь новую функцию регрессии, усредняющую ответы уже построенных:

[math] a(x) = \frac 1 n \sum \limits_{i = 1}^n b_i(x) [/math]

Найдем ее среднеквадратичную ошибку:

[math] 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 [/math]

Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в [math]n[/math] раз.

Бустинг

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

Пусть [math]h(x, a)[/math] — базовый классификатор, где [math]a[/math] — вектор параметров.

Задача состоит в том, чтоб найти такой алгоритм [math]H_T(x) = \sum_{t=1}^T b_t h(x, a),[/math] где [math]b_t \in \mathbb{R}[/math] — коэффиценты, такие, чтобы минимизировать эмпирический риск [math]Q = \sum_i L(H_T(x_i), y_i) \rightarrow min[/math], где [math]L(H_T(x_i), y_i)[/math] — функция потерь.

Очевидно, что сложно найти сразу [math]\{(a_t, b_t)\}_{t=1}^T.[/math] Основная идея в том, чтоб найти решение пошагово [math]H_t(x) = H_{t — 1}(x) + b_t h(x, a_t)[/math]. Таким образом мы сможем постепенно оценивать изменение эмпирического риска [math]Q^{(t)} = \sum_{i = 1}^l L(H_t(x_i), y_i) [/math].

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

  • AdaBoost — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
  • BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
  • GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
  • LogitBoost — алгоритм бустинга, использующий идеи логистической регресси

Реализации и применения бустинга

Реализации бустинга:

  • XGBoost — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.
  • CatBoost — открытая программная библиотека, разработанная компанией Яндекс.
  • LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).


Применение бустинга:

  • поисковые системы
  • ранжирования ленты рекомендаций
  • прогноз погоды
  • оптимизации расхода сырья
  • предсказания дефектов при производстве.
  • исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.

Различия между алгоритмами

  • Оба алгоритма используют N базовых классификаторов
    • Бустинг использует последовательное обучение
    • Бэггинг использует параллельное обучение
  • Оба генерируют несколько наборов данных для обучения путем случайной выборки
    • Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи
    • Бэггинг имеет невзвешенные данные
  • Оба принимают окончательное решение, усредняя N классификаторов
    • В бустинге определяются веса для них
    • В бэггинге они равнозначны
  • Оба уменьшают дисперсию и обеспечивают более высокую стабильность
    • Бэггинг может решить проблему переобучения
    • Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения

Примеры кода

Инициализация

   from pydataset import data
   
   #Считаем данные The Boston Housing Dataset[1] 
   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]

См. также

Примечания

Источники информации