Стохастические методы построения композиций

Стохастические методы построения композиций 

Бименова Жанат

             Группа 7205

План 

1 Стохастические  методы построения композиций

• 1.1 Бэггинг
• 1.2 Метод случайных подпространств
• 1.3 Кооперативная коэволюция

     Алгоритмы в композиции должны быть различными

1.1 Бэггинг 
 

• Метод бэггинга (bagging, bootstrap aggregation) был предложен Л. Брейманом в 1996 году
• Формируются различные подвыборки, с помощью бутстрепа – случайного выбора  с возвращением
• Доля объектов, оказавшихся в каждой подвыборке, стремится к 1-e^-1=0.632
• Базовые  алгоритмы, обученные по подвыборкам, объединяются в композицию с помощью простого голосования

Эффективность бэггинга 

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

1.2 RSM 

• В методе  случайных подпространств (random subspace method, RSM) базовые алгоритмы обучаются на различных подмножествах признакового описания,

    которые также выделяются случайным образом

Алгоритм. Бэггинга и RSM

Сравнение: boosting bagging RSM 

• Бустинг лучше  для больших обучающих выборок

и для классов  с границами сложной формы.

• Бэггинг и RSM лучше для коротких обучающих выборок.
• RSM лучше в тех случаях, когда признаков больше, чем

объектов, или когда  много неинформативных

признаков.

• Бэггинг и RSM эффективно распараллеливаются,

бустинг выполняется  строго последовательно.

1.3 Кооперативная  коэволюция 

• Применение  генетических алгоритмов для глобальной оптимизации функционала качества Q(a)
• Для построения композиции обучаемых алгоритмов хорошо подходит специфическая модель эволюции, называемая кооперативной коэволюцией

• На t-м поколении  строится не одна, а p(t) популяций  П1(t), . . . ,Пp(t)(t). Каждая популяция j(t) представляет собой множество  индивидов. Каждый индивид кодируется (ℓ + n)-мерным бинарным вектором, составленным из характеристических  векторов подмножества объектов X′ ⊆ {x1, . . . , xℓ} и подмножества  признаков G′ ⊆ {g1, . . . , gn}. Таким образом, каждому индивиду vj ∈П j(t) соответствует  пара подмножеств (G′,X′), к которой  можно применить метод обучения  и получить базовый алгоритм  bj = μ(G′,X′) ≡ μ(vj).
• Оценка адаптивности
• Адаптивность оценивается для каждого вида индивида в каждой популяции
• Смена поколений

CCEL   Cooperative Coevolution Ensemble Learner 

• Инициализация(N0)
• Селекция(П,N)
• Рекомбинация(П,N1)
• Мутация(П)
• Вклад(Пj)
• Стагнация(Q, t)
• Останов(Q, t)

Преимущества метода CCEL 

• Высокая обобщающая  способность
• Короткие композиции
• Широкая применимость
• Автоматически отбираются информативные объекты и признаки
• Алгоритмом с произвольным временем работы

Недостатки метода CCEL 

• Сложность  реализации
• Время работы (если не использовать распараллеливания)

Алгоритм

Спасибо за внимание!!!