Ансамблирование классификаторов


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.



Ансамблирование
классификаторов


Алексей Целых

Как выбрать лучший
классификатор
?


Одна голова


хорошо,

две


лучше,

а три


Змей Горыныч…




Если взять несколько моделей с
некоррелированными ошибками, их
комбинация может работать
значительно лучше.


Распространенные подходы


Бэггинг


Бустинг


Стекинг

1.
Bagging

(
Bootstrapped
aggregation
)


Предложен в 1994 году Лео
Брейнманом.


Использует случайные выборки с
возвратом (бутстреп).


Результаты классификации
агрегируются путем голосования или
усреднения.

Метод бутстрепа для выборки


Предложен в 1977 году Б. Эфроном.


Удаляем несколько прецедентов и
реплицируем другие.


Полученные выборки имеют различное
распределение данных.


Алгоритм бэггинга

Генерация модели


Пусть
N



число наблюдений в обучающей выборке


На каждой из
t

итераций
:


Выбрать
M ≤ N

прецедентов с возвратом (бутстреп
-
выборка)
.



Обучить модель


Классификация


t

раз применить модель.


Вернуть класс, который предсказывался чаще всего
:


Сколько прецедентов
реплицировать
?


Вероятность того, что прецедент
появится в бутстреп
-
выборке
составляет
1


(1


1/
n
)
n

≈ .632 (
n

� 40)


.368

n

прецедентов реплицируются

Выводы


Бэггинг

повышает качество обучения при
нестабильности методов обучения. В
противном случае качество может снижаться
за счет искажения истинного распределения
выборки.


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



Рандомизация


Прогноз классификатора варьируется с
изменением значения инициализатора
генератора случайных чисел (
seed).



Практически каждая обучающая модель
имеет свой собственный рычаг случайности.


Бывает полезным комбинировать бэггинг и
рандомизацию, поскольку они рассматривают
«случайность» с разных и, возможно,
комплиментарных аспектов.



2.
Boosting


Адаптивный подход, предложен в конце
80
-
х Робертом Шапейре.


Подразумевает «усиление» «слабых»
моделей.


Построение цепочки классификаторов,
каждый из которых обучается на
ошибках предыдущего.


Результат определяется путем простого
голосования классификаторов.

Расчет ошибки
классификатора


Прецеденты взвешены положительным
числом.


Ошибка вычисляется как отношение
суммы весов некорректно
классифицированных прецедентов к
сумме весов всех прецедентов.

Алгоритм
AdaBoost

Генерация модели


Присвоить одинаковый вес каждому из обучающих прецедентов.


На каждой из
t

итераций
:


Применить обучающую модель к взвешенному набору данных.


Вычислить ошибку обучающей модели
e
.


Если ошибка равна нулю или ≥ 0.5,

завершить генерацию модели.


Для каждого прецедента в наборе данных
:

если прецедент корректно классифицируется моделью
:


умножить вес прецедента на
e

/ (1

-

e
).


Нормализовать вес всех прецедентов.

Алгоритм
AdaBoost (
продолж.)

Классификация


Присвоить нулевой вес всем классам.


Для каждой из
t

моделей
:

прибавить значение

log(
e
/(1
-
e
))
к весу класса, предсказанного моделью.


Вернуть класс с максимальным весом.

Выводы


Для построения хорошего ансамбля
классификаторов на основе бустинга
достаточно, чтобы базовые методы
классификации были чуть лучше гадания
.


В отличие от бэггинга, бустинг может
построить классификатор, значительно
менее точный, чем одиночный
классификатор (проблема переобучения).


Bias
-
Variance Dilemma


Часть ошибки
(bias



смещение
)
связана с
аппроксимирующей способностью обучающей
модели.


Другая составляющая
(variance



дисперсия
)

обусловлена вариациями решения ввиду конечности
числа примеров, и потому не полной
репрезентативности
.


Дилемма состоит в оптимизации этих двух
составляющих.


Ансамблирование классификаторов снижает
дисперсионную компоненту ошибки. Для уменьшения
ошибки смещения необходимо применять
классификаторы различной природы.


3.
Stacking


Предложен Дэвидом Вулпертом

(1992)
.


Метаклассификатор вместо процедуры
голосования.


На 0
-
уровне работают простые
алгоритмы, более сложный алгоритм на
1
-
уровне выступает в роли арбитра.

Выводы


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


Результаты классификации служат
входными переменными для
метаклассификатора.


Выводы по лекции


Полагаться на «лучшую» модель


не
всегда мудрое решение. Иногда
комбинация «слабых» моделей может
дать неожиданно хороший результат.


Приложенные файлы

  • pdf 9448384
    Размер файла: 641 kB Загрузок: 0

Добавить комментарий