Монотонная коррекция
Материал из MachineLearning.
(статья № 600) |
(уточнение, ссылки) |
||
| Строка 1: | Строка 1: | ||
| - | '''Монотонная коррекция''' — это процесс построения по [[обучающая выборка|обучающей выборке]] монотонной [[алгоритмическая композиция|алгоритмической композиции]] — суперпозиции базовых | + | '''Монотонная коррекция''' — это процесс построения по [[обучающая выборка|обучающей выборке]] монотонной [[алгоритмическая композиция|алгоритмической композиции]] — суперпозиции базовых алгоритмов и монотонной агрегирующей функции (корректирующей операции). |
== Формальное определение == | == Формальное определение == | ||
| Строка 33: | Строка 33: | ||
== Обобщающая способность монотонных функций == | == Обобщающая способность монотонных функций == | ||
{{main|Обобщающая способность монотонных функций (виртуальный семинар)}} | {{main|Обобщающая способность монотонных функций (виртуальный семинар)}} | ||
| + | |||
| + | === Верхние оценки CCV (полного скользящего контроля) === | ||
| + | |||
| + | === Точная оценка CCV для монотонного классификатора ближайшего соседа === | ||
== Литература == | == Литература == | ||
| Строка 41: | Строка 45: | ||
*[[Бустинг]], [[Бэггинг]] | *[[Бустинг]], [[Бэггинг]] | ||
*[[Смесь алгоритмов]] | *[[Смесь алгоритмов]] | ||
| + | *[[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)]] | ||
[[Категория:Алгоритмические композиции]] | [[Категория:Алгоритмические композиции]] | ||
Версия 07:47, 13 апреля 2011
Монотонная коррекция — это процесс построения по обучающей выборке монотонной алгоритмической композиции — суперпозиции базовых алгоритмов и монотонной агрегирующей функции (корректирующей операции).
Содержание |
Формальное определение
Пусть — пространство объектов,
— пространство ответов,
— базовые алгоритмы.
Монотонная алгоритмическая композиция — это функция вида
где — монотонно неубывающая функция всех
своих аргументов, называемая корректирующей операцией или агрегирующей функцией.
В задачах классификации базовые алгоритмы, как правило, представляются в виде , где функцию
называют алгоритмическим оператором, а в случае
— вещественнозначным классификатором; функцию
называют решающим правилом.
В этом случае монотонную алгоритмическую композицию определяют немного иначе:
где — монотонно неубывающая функция всех
своих аргументов.
Введение вспомогательного пространства оценок
необходимо для того, чтобы расширить класс используемых корректирующих операций.
В задачах восстановления регрессии множество изначально достаточно богато, и в таком расширении нет необходимости. В регрессионных задачах решающие правила не используются.
Мотивация. Более распространённым видом алгоритмических композиций является взвешенное голосование — линейная комбинация базовых алгоритмов с неотрицательными коэффициентами :
Если коэффициенты ещё и нормированы на единицу, то говорят о выпуклой коррекции. Неотрицательность коэффициентов является очень естественным требованием, поскольку оно означает, что значение на выходе агрегирующей функции монотонно возрастает по выходам базовых алгоритмов. Действительно, базовые алгоритмы и агрегирующая функция обучаются решению одной и той же задачи, поэтому было бы странно, если бы при увеличении значений некоторых базовых алгоритмов значение на выходе агрегирующей функции уменьшалось. С другой стороны, линейность агрегирующей функции представляется менее естественным ограничением, чем более общее требование монотонности. Принцип взвешенного голосования имеет в машинном обучении долгую историю, развитую теорию и широкую практику применения. Линейные функции легче строить, и этим объясняется их популярность. Замена линейности на монотонность существенно расширяет класс агрегирующих функций. За счёт этого становится возможным, в частности, построение композиций из меньшего числа базовых алгоритмов, обладающих более высоким качеством.
Монотонные композиции в различных задачах машинного обучения
Задача классификации на два класса
Задача восстановления регрессии
Задача ранжирования
Монотонизация выборки
Изотонная регрессия (isotonic regression)
