Читать онлайн «Лекции по алгоритмическим композициям»

Лекции по алгоритмическим композициям (черновик) К. В. Воронцов 19 мая 2005 г. Содержание 1 Композиции алгоритмов 2 1. 1 Последовательное обучение базовых алгоритмов . . . . . . . . . . . . . 4 1. 2 Метод комитетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 2. 1 Комитеты большинства . . . . . . . . . . . . . . . . . . . . . . . . 6 1. 2. 2 Комитеты старшинства . . . . . . . . . . . . . . . . . . . . . . . . 8 1. 3 Линейная коррекция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1. 3. 1 Бустинг в задачах классификации . . . . . . . . . . . . . . . . . . 11 1. 3. 2 Бустинг в задачах восстановления регрессии . . . . . . . . . . . 15 1. 3. 3 Баггинг . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1. 4 Квазилинейная коррекция (смеси алгоритмов) . . . . . . . . . . . . . . 16 1. 4. 1 Смесь двух алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . 17 1. 4. 2 Иерархические смеси алгоритмов . . . . . . . . . . . . . . . . . . 19 1. 5 Монотонная коррекция . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1. 5. 1 Вывод формул пересчета весов и ответов . . . . . . . . . . . . . . 20 1. 5. 2 Монотонизация выборки . . . . . . . . . . . . . . . . . . . . . . . 20 1. 5. 3 Бинарная монотонная корректирующая операция . . . . . . . . . 20 1. 5. 4 Кусочно-непрерывная монотонная корректирующая операция . 20 1. 6 Алгебраический подход . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1. 6. 1 Понятия разрешимости, регулярности и полноты . . . . . . . . . 21 1. 6. 2 Полнота линейных замыканий . . . . . . . . . . . . . . . . . . . . 21  –2– 1 Композиции алгоритмов При решении сложных задач классификации, регрессии и прогнозирования часто оказывается, что ни один из имеющихся эвристических алгоритмов не даёт желаемого качества обучения. В таких случаях имеет смысл строить композицию алгоритмов, в которой недостатки одних алгоритмов компенсировались бы достоин- ствами других. При определённых условиях качество композиции может оказаться заметно лучше, чем у отдельных составляющих её алгоритмов. Напомним основные обозначения. Рассматривается задача обучения по преце- дентам hX, Y, y ∗ , X ` i, где X — пространство объектов; Y — множество ответов; y ∗ : X → Y — неизвестная целевая зависимость; X ` = (x1 , . . . , x` ) — обучающая выборка; Y ` = (y1 , . . . , y` ) — вектор ответов на обучающих объектах, yi = y ∗ (xi ). Задача заключается в том, чтобы построить алгоритм a : X → Y , аппроксимирую- щий целевую зависимость.