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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Различия между алгоритмами)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 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>.
  
Строка 31: Строка 38:
 
Пусть имеется выборка <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>
Строка 84: Строка 92:
 
== Бустинг ==
 
== Бустинг ==
  
'''Бустинг''' (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
+
[[Бустинг, AdaBoost|'''Бустинг''']] (англ. boosting — улучшение) — это процедура последовательного построения композиции алгоритмов машинного обучения, когда каждый следующий алгоритм стремится компенсировать недостатки композиции всех предыдущих алгоритмов. Бустинг представляет собой жадный алгоритм построения композиции алгоритмов.
  
 
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.
 
Пусть <tex>h(x, a)</tex> — базовый классификатор, где <tex>a</tex> — вектор параметров.
Строка 94: Строка 102:
 
Алгоритмы бустинга:
 
Алгоритмы бустинга:
  
 +
<ul>
 
<li>[[Бустинг, AdaBoost|AdaBoost]]  — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
 
<li>[[Бустинг, AdaBoost|AdaBoost]]  — адаптивный алгоритм бустинга, усиливающий классификаторы, объединяя их в «комитет». Чувствителен к шуму.
 
<li>BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
 
<li>BrownBoost — алгоритм бустинга, эффективный на зашумленных наборах данных
 
<li>GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
 
<li>GradientBoost — алгоритм бустинга, использующий идеи линейной регресии
 
<li>LogitBoost — алгоритм бустинга, использующий идеи логистической регресси
 
<li>LogitBoost — алгоритм бустинга, использующий идеи логистической регресси
 +
</ul>
  
 
== Реализации и применения бустинга  ==
 
== Реализации и применения бустинга  ==
Строка 103: Строка 113:
 
Реализации бустинга:
 
Реализации бустинга:
  
<ul>
+
* [[XGBoost|XGBoost]] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.
<li> CatBoost — открытая программная библиотека разработанная компанией Яндекс
+
* [[CatBoost|CatBoost]] — открытая программная библиотека, разработанная компанией Яндекс.
<li> XGBoost изначально исследовательский проект Tianqi Chen, сейчас открытая программная библиотека, поддерживая сообществом
+
* LightGBM — библиотека для метода машинного обучения, основанная на градиентном бустинге (англ. gradient boosting).
    <ul>
+
 
    <li> Rapids — проект NVIDIA, созданный для использования GPU с XGBooost
 
    </ul>
 
<li> LightGBM — открытая программная библиотека разработанная компанией Яндекс
 
</ul>
 
  
 
Применение бустинга:
 
Применение бустинга:
<ul>
+
* поисковые системы
<li> поисковые системы
+
* ранжирования ленты рекомендаций
<li> ранжирования ленты рекомендаций
+
* прогноз погоды
<li> прогноз погоды
+
* оптимизации расхода сырья
<li> оптимизации расхода сырья
+
* предсказания дефектов при производстве.
<li> предсказания дефектов при производстве.
+
* исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
<li> исследованиях на Большом адронном коллайдере (БАК) для объединения информации с различных частей детектора LHCb в максимально точное, агрегированное знание о частице.
 
</ul>
 
  
 
== Различия между алгоритмами ==  
 
== Различия между алгоритмами ==  
Строка 126: Строка 130:
 
<ul>
 
<ul>
 
<li> Оба алгоритма используют N базовых классификаторов
 
<li> Оба алгоритма используют N базовых классификаторов
   <ul>  
+
   <ul>
 
     <li> Бустинг использует последовательное обучение </li>
 
     <li> Бустинг использует последовательное обучение </li>
 
     <li> Бэггинг использует параллельное обучение </li>
 
     <li> Бэггинг использует параллельное обучение </li>
 
   </ul>
 
   </ul>
 
</li>
 
</li>
<li> Оба генерируют несколько наборов обучающих данных путем случайной выборки
+
<li> Оба генерируют несколько наборов данных для обучения путем случайной выборки
 
   <ul>
 
   <ul>
 
     <li> Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи </li>
 
     <li> Бустинг определяет вес данных, чтоб утяжелить тяжелые случаи </li>
Строка 137: Строка 141:
 
   </ul>
 
   </ul>
 
</li>
 
</li>
<li> Оба принимают окончательное решение, усредняя N учеников
+
<li> Оба принимают окончательное решение, усредняя N классификаторов
 
   <ul>  
 
   <ul>  
     <li> В бустинге определяются веса классификаторов </li>
+
     <li> В бустинге определяются веса для них </li>
     <li> В бэггинге все классификаторы равнозначны </li>
+
     <li> В бэггинге они равнозначны </li>
 
   </ul>
 
   </ul>
 
</li>
 
</li>
 
<li> Оба уменьшают дисперсию и обеспечивают более высокую стабильность
 
<li> Оба уменьшают дисперсию и обеспечивают более высокую стабильность
 
   <ul>
 
   <ul>
     <li> Бэггинг может решить проблему переобучение </li>
+
     <li> Бэггинг может решить проблему переобучения </li>
 
     <li> Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения </li>
 
     <li> Бустинг пытается уменьшить смещение, но может увеличить проблему переобучения </li>
 
   </ul>
 
   </ul>
Строка 157: Строка 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'],
Строка 166: Строка 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):
Строка 173: Строка 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)
Строка 179: Строка 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
Строка 188: Строка 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()
Строка 207: Строка 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]
Строка 236: Строка 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]

См. также

Примечания

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