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

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

Версия от 09:36, 12 апреля 2011; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Содержание

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

Пусть 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)

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

Литература

См. также

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