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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Бэггинг)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 4 участников)
Строка 40: Строка 40:
 
Алгоритм использует метод бутстрэпа (англ. ''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>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
  
 
Шаги алгоритма бэггинг:
 
Шаги алгоритма бэггинг:
Строка 58: Строка 58:
 
</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) на объектах. В этом случае мы можем записать ошибку каждой функции регрессии:
Строка 91: Строка 92:
 
== Бустинг ==
 
== Бустинг ==
  
'''Бустинг''' (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
+
[[Бустинг, AdaBoost|'''Бустинг''']] (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
  
 
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.
 
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.
Строка 112: Строка 113:
 
Реализации бустинга:
 
Реализации бустинга:
  
<ul>
+
* [[XGBoost|XGBoost]] одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.
<li> XGBoost — изначально исследовательский проект Tianqi Chen, сейчас открытая программная библиотека, поддерживая сообществом
+
* [[CatBoost|CatBoost]] — открытая программная библиотека, разработанная компанией Яндекс.
<li> CatBoost — открытая программная библиотека разработанная компанией Яндекс
+
* LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).
<li> LightGBM — открытая программная библиотека разработанная компанией Яндекс
+
 
</ul>
 
  
 
Применение бустинга:
 
Применение бустинга:
<ul>
+
* поисковые системы
<li> поисковые системы
+
* ранжирования ленты рекомендаций
<li> ранжирования ленты рекомендаций
+
* прогноз погоды
<li> прогноз погоды
+
* оптимизации расхода сырья
<li> оптимизации расхода сырья
+
* предсказания дефектов при производстве.
<li> предсказания дефектов при производстве.
+
* исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
<li> исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
 
</ul>
 
  
 
== Различия между алгоритмами ==  
 
== Различия между алгоритмами ==  
Строка 132: Строка 130:
 
<ul>
 
<ul>
 
<li> Оба алгоритма используют N базовых классификаторов
 
<li> Оба алгоритма используют N базовых классификаторов
   <ul>  
+
   <ul>
 
     <li> Бустинг использует последовательное обучение </li>
 
     <li> Бустинг использует последовательное обучение </li>
 
     <li> Бэггинг использует параллельное обучение </li>
 
     <li> Бэггинг использует параллельное обучение </li>
Строка 163: Строка 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'],
Строка 172: Строка 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):
Строка 179: Строка 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)
Строка 185: Строка 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
Строка 194: Строка 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()
Строка 213: Строка 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]
Строка 242: Строка 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/>
  
 
== Источники информации ==
 
== Источники информации ==
Строка 255: Строка 261:
 
* https://quantdare.com/what-is-the-difference-between-bagging-and-boosting/
 
* 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]

См. также

Примечания

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