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

Материал из Викиконспекты
Версия от 10:44, 19 февраля 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]

Виды Ансамблей 1.pngВиды Ансамблей 2.png

Бутстрэп

Метод бутстрэпа (англ. bootstrap) — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и заключается в следующем. Пусть имеется выборка [math]X[/math] размера [math]N[/math]. Равномерно возьмем из выборки [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]. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.

Бутстрэп используется в статистике, в том числе для:

  • Аппроксимация стандартной ошибки выборочной оценки
  • Байесовская коррекция с помощью Бутстрэп метода
  • Доверительные интервалы
  • Метод процентилей

Бэггинг

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

Алгоритм классификации в технологии бэггинг на подпространствах:

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


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

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