Монотонная коррекция

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(уточнение, ссылки)
(См. также: уточнил ссылку)
 
Строка 45: Строка 45:
*[[Бустинг]], [[Бэггинг]]
*[[Бустинг]], [[Бэггинг]]
*[[Смесь алгоритмов]]
*[[Смесь алгоритмов]]
-
*[[Теория надёжности обучения по прецедентам (курс лекций, К.В.Воронцов)]]
+
*[[Теория надёжности обучения по прецедентам (курс лекций, К. В. Воронцов)]]
[[Категория:Алгоритмические композиции]]
[[Категория:Алгоритмические композиции]]

Текущая версия

Монотонная коррекция — это процесс построения по обучающей выборке монотонной алгоритмической композиции — суперпозиции базовых алгоритмов и монотонной агрегирующей функции (корректирующей операции).

Содержание

Формальное определение

Пусть X — пространство объектов, Y — пространство ответов, a_t:\; X\to Y — базовые алгоритмы. Монотонная алгоритмическая композиция — это функция вида

a(x) = F\bigl( a_1(x),\dots, a_T(x) \bigr), \quad \forall x\in X

где F:\; Y^T \to Y — монотонно неубывающая функция всех T своих аргументов, называемая корректирующей операцией или агрегирующей функцией.

В задачах классификации базовые алгоритмы, как правило, представляются в виде a_t(x) = C(b_t(x)), где функцию b_t:\; X\to R называют алгоритмическим оператором, а в случае R=\mathbb{R}вещественнозначным классификатором; функцию C:\; R\to Y называют решающим правилом. В этом случае монотонную алгоритмическую композицию определяют немного иначе:

a(x) = F\bigl( b_1(x),\dots, b_T(x) \bigr), \quad \forall x\in X

где F:\; R^T \to Y — монотонно неубывающая функция всех T своих аргументов. Введение вспомогательного пространства оценок R необходимо для того, чтобы расширить класс используемых корректирующих операций.

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

Мотивация. Более распространённым видом алгоритмических композиций является взвешенное голосование — линейная комбинация базовых алгоритмов с неотрицательными коэффициентами \alpha_t:

a(x) = C\bigl( \alpha_1 b_1(x) +\dots+ \alpha_T b_T(x) \bigr), \quad \forall x\in X.

Если коэффициенты ещё и нормированы на единицу, то говорят о выпуклой коррекции. Неотрицательность коэффициентов является очень естественным требованием, поскольку оно означает, что значение на выходе агрегирующей функции монотонно возрастает по выходам базовых алгоритмов. Действительно, базовые алгоритмы и агрегирующая функция обучаются решению одной и той же задачи, поэтому было бы странно, если бы при увеличении значений некоторых базовых алгоритмов значение на выходе агрегирующей функции уменьшалось. С другой стороны, линейность агрегирующей функции представляется менее естественным ограничением, чем более общее требование монотонности. Принцип взвешенного голосования имеет в машинном обучении долгую историю, развитую теорию и широкую практику применения. Линейные функции легче строить, и этим объясняется их популярность. Замена линейности на монотонность существенно расширяет класс агрегирующих функций. За счёт этого становится возможным, в частности, построение композиций из меньшего числа базовых алгоритмов, обладающих более высоким качеством.

Монотонные композиции в различных задачах машинного обучения

Задача классификации на два класса

Задача восстановления регрессии

Задача ранжирования

Монотонизация выборки

Изотонная регрессия (isotonic regression)

Обобщающая способность монотонных функций

Верхние оценки CCV (полного скользящего контроля)

Точная оценка CCV для монотонного классификатора ближайшего соседа

Литература

См. также

Личные инструменты