Виды ансамблей

Материал из Викиконспекты
Версия от 17:28, 12 марта 2019; GarikCarrot (обсуждение | вклад) (Измененн порядок)
Перейти к: навигация, поиск

Ансамбль

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

Рассмотрим задачу классификации на K классов: [math]Y = \{1, 2, ..., K\}[/math].
Пусть имеется M классификатор ("экспертов"): [math] f_1, f_2, ..., f_M [/math].
[math] f_m : X \leftarrow 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].

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

Теорема:
Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 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):

   Равномерно возьмем из выборки [math]N[/math] объектов с возвращением. Это означает, что мы будем [math]N[/math] раз равновероятно выбирать произвольный объект выборки, причем каждый раз мы выбираем из всех исходных [math]N[/math] объектов. Отметим, что из-за возвращения среди них окажутся повторы. 
Обозначим новую выборку через [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 — алгоритм бустинга, использующий идеи логистической регресси

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

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

    • CatBoost — открытая программная библиотека разработанная компанией Яндекс
    • XGBoost — изначально исследовательский проект Tianqi Chen, сейчас открытая программная библиотека, поддерживая сообществом
      • Rapids — проект NVIDIA, созданный для использования GPU с XGBooost
    • LightGBM — открытая программная библиотека разработанная компанией Яндекс

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

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

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

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

    Примеры кода

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

       from pydataset import data
       
       #Считаем данные The Boston Housing Dataset
       df = data('Housing')
    
       #Проверим данные
       df.head().values
       array([[42000.0, 5850, 3, 1, 2, 'yes', 'no', 'yes', 'no', 'no', 1, 'no'],
              [38500.0, 4000, 2, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'],
              [49500.0, 3060, 3, 1, 1, 'yes', 'no', 'no', 'no', 'no', 0, 'no'], ...
    
       # Создадим словарь для слов 'no', 'yes'
       d = dict(zip(['no', 'yes'], range(0,2)))
       for i in zip(df.dtypes.index, df.dtypes):
           if str(i[1]) == 'object':
               df[i[0]] = df[i[0]].map(d)
       df[‘price’] = pd.qcut(df[‘price’], 3, labels=[‘0’, ‘1’, ‘2’]).cat.codes
       
       # Разделим множество на два
       y = df['price'] 
       X = df.drop('price', 1)
    

    Бэггинг

       # Импорты классификаторов
       from sklearn.model_selection import cross_val_score
       from sklearn.ensemble import BaggingClassifier, ExtraTreesClassifier, RandomForestClassifier
       from sklearn.neighbors import KNeighborsClassifier
       from sklearn.linear_model import RidgeClassifier
       from sklearn.svm import SVC
       
       seed = 1075
       np.random.seed(seed)
       # Инициализуруем классификаторы
       rf = RandomForestClassifier()
       et = ExtraTreesClassifier()
       knn = KNeighborsClassifier()
       svc = SVC()
       rg = RidgeClassifier()
       clf_array = [rf, et, knn, svc, rg]
       
       for clf in clf_array:
           vanilla_scores = cross_val_score(clf, X, y, cv=10, n_jobs=-1)
           bagging_clf = BaggingClassifier(clf, max_samples=0.4, max_features=10, random_state=seed)
           bagging_scores = cross_val_score(bagging_clf, X, y, cv=10, n_jobs=-1)
           print "Mean of: {1:.3f}, std: (+/-) {2:.3f [{0}]"  
                              .format(clf.__class__.__name__, 
                              vanilla_scores.mean(), vanilla_scores.std())
           print "Mean of: {1:.3f}, std: (+/-) {2:.3f} [Bagging {0}]\n"
                              .format(clf.__class__.__name__, 
                               bagging_scores.mean(), bagging_scores.std())
    
       #Результат
       Mean of: 0.632, std: (+/-) 0.081 [RandomForestClassifier]
       Mean of: 0.639, std: (+/-) 0.069 [Bagging RandomForestClassifier]
       
       Mean of: 0.636, std: (+/-) 0.080 [ExtraTreesClassifier]
       Mean of: 0.654, std: (+/-) 0.073 [Bagging ExtraTreesClassifier]
       
       Mean of: 0.500, std: (+/-) 0.086 [KNeighborsClassifier]
       Mean of: 0.535, std: (+/-) 0.111 [Bagging KNeighborsClassifier]
       
       Mean of: 0.465, std: (+/-) 0.085 [SVC]
       Mean of: 0.535, std: (+/-) 0.083 [Bagging SVC]
       
       Mean of: 0.639, std: (+/-) 0.050 [RidgeClassifier]
       Mean of: 0.597, std: (+/-) 0.045 [Bagging RidgeClassifier]
    

    Бустинг

       ada_boost = AdaBoostClassifier()
       grad_boost = GradientBoostingClassifier()
       xgb_boost = XGBClassifier()
       boost_array = [ada_boost, grad_boost, xgb_boost]
       eclf = EnsembleVoteClassifier(clfs=[ada_boost, grad_boost, xgb_boost], voting='hard')
       
       labels = ['Ada Boost', 'Grad Boost', 'XG Boost', 'Ensemble']
       for clf, label in zip([ada_boost, grad_boost, xgb_boost, eclf], labels):
           scores = cross_val_score(clf, X, y, cv=10, scoring='accuracy')
           print("Mean: {0:.3f}, std: (+/-) {1:.3f} [{2}]".format(scores.mean(), scores.std(), label))
    
       # Результат
       Mean: 0.641, std: (+/-) 0.082 [Ada Boost]
       Mean: 0.654, std: (+/-) 0.113 [Grad Boost]
       Mean: 0.663, std: (+/-) 0.101 [XG Boost]
       Mean: 0.667, std: (+/-) 0.105 [Ensemble]
    

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