Стохастические методы построения композиций
Бименова Жанат
Группа 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
- Сложность
реализации
- Время работы
(если не использовать распараллеливания)
Алгоритм
Спасибо за внимание!!!