Метод настройки с возвращениями
Материал из MachineLearning.
м (опечатка) |
м (формулы) |
||
Строка 20: | Строка 20: | ||
* На первом шаге фиксируются функции <tex>\varphi_j</tex>, и ''[[многомерная линейная регрессия| методами многомерной линейной регрессии]]'' вычисляются коэффициенты <tex>\theta_j</tex>. | * На первом шаге фиксируются функции <tex>\varphi_j</tex>, и ''[[многомерная линейная регрессия| методами многомерной линейной регрессии]]'' вычисляются коэффициенты <tex>\theta_j</tex>. | ||
* На втором шаге фиксируются коэффициенты <tex>\theta_j</tex> и все функции <tex>\{\varphi_k\}_{k \neq j}</tex> кроме одной <tex>\varphi_j</tex>, которая настраивается ''методами одномерной [[непараметрическая регрессия| непараметрической регрессии]]''. На втором шаге решается задача минимизации функционала | * На втором шаге фиксируются коэффициенты <tex>\theta_j</tex> и все функции <tex>\{\varphi_k\}_{k \neq j}</tex> кроме одной <tex>\varphi_j</tex>, которая настраивается ''методами одномерной [[непараметрическая регрессия| непараметрической регрессии]]''. На втором шаге решается задача минимизации функционала | ||
- | :: <tex> Q(\varphi_j, X^n) = \sum_{i=1}^n \ | + | :: <tex> Q(\varphi_j, X^n) = \sum_{i=1}^n \biggl(\theta_j \cdot \varphi_j(f_j (x_i)) \;+\! \underbrace{\sum_{l=1,\; l \neq j }^k \theta_l \cdot \varphi_l(f_l (x_i)) - y_i}_{z_i = \mathrm{const}(\varphi_j)} \biggr)^2 \rightarrow \min_{\varphi_j}</tex>. |
- | Здесь коэффициенты <tex>\theta_j</tex> и функции <tex>\{\varphi_k\}_{k \neq j}</tex> фиксированы и не зависят от <tex>\varphi_j</tex>. Благодаря этому настройка <tex>\varphi_j</tex> сводится к стандартной [[задача наименьших квадратов| задаче наименьших квадратов]] с обучающей выборкой <tex>\ | + | Здесь коэффициенты <tex>\theta_j</tex> и функции <tex>\{\varphi_k\}_{k \neq j}</tex> фиксированы и не зависят от <tex>\varphi_j</tex>. Благодаря этому настройка <tex>\varphi_j</tex> сводится к стандартной [[задача наименьших квадратов| задаче наименьших квадратов]] с обучающей выборкой <tex>\tilde{X}_j^n = \Bigl(f_j(x_i),\; y_i \;- \!\sum_{s=1,\; s \neq j }^k\! \theta_s \hat{\varphi}_{is}\Bigr)_{i=1}^n</tex>. Для ее решения годятся любые одномерные методы: [[ядерное сглаживание]], [[сплайны]], полиномиальная или Фурье-аппроксимация. Для [[ядерное сглаживание| ядерного сглаживания]] с фиксированной шириной окна этап настройки функции <tex>\varphi_j</tex> фактически отсутствует; чтобы вычислять значения <tex>\varphi_j(f)</tex> по [[формула Надарая-Ватсона| формуле Надарая-Ватсона]], достаточно просто запомнить выборку <tex>\tilde{X}_j^n</tex>. |
После настройки всех функций <tex>\varphi_j</tex> происходит возврат к первому шагу, и снова решается задача [[многомерная линейная регрессия| многомерной линейной регрессии]] для определения <tex>\theta_j</tex>. Отсюда происходит и название метода – '''настройка с возвращениями''' (backfitting). | После настройки всех функций <tex>\varphi_j</tex> происходит возврат к первому шагу, и снова решается задача [[многомерная линейная регрессия| многомерной линейной регрессии]] для определения <tex>\theta_j</tex>. Отсюда происходит и название метода – '''настройка с возвращениями''' (backfitting). |
Текущая версия
На практике встречаются ситуации, когда линейная модель регрессии представляется необоснованной, но предложить адекватную нелинейную модель также не удается. Тогда в качестве альтернативы строится модель вида
-
,
-
где - некоторые преобразования исходных признаков, в общем случае нелинейные. Задача состоит в том, чтобы одновременно подобрать и коэффициенты линейной модели
, и неизвестные одномерные преобразования
, при которых достигается минимум квадратичного функционала RSS – остаточная сумма квадратов.
Суть метода заключается в том, что в линейную модель добавляются нелинейные преобразования исходных признаков. Другими словами метод настройки с возвращениями (backfitting) совмещает многомерную линейную регрессию и одномерное сглаживание. Таким образом, нелинейная задача сводится к решению последовательности линейных задач.
Содержание |
Обозначения
Дана выборка ;
– длина выборки.
При этом
;
– число независимых переменных (число признаков).
Через
будем обозначать
-тый признак
-го объекта выборки.
Значение целевой зависимости для -го объекта
.
Обозначим через оценку
.
Метод настройки с возвращениями (backfitting)
Описание
Метод настройки с возвращениями в традиционной форме основан на итерационном повторении двух шагов:
- На первом шаге фиксируются функции
, и методами многомерной линейной регрессии вычисляются коэффициенты
.
- На втором шаге фиксируются коэффициенты
и все функции
кроме одной
, которая настраивается методами одномерной непараметрической регрессии. На втором шаге решается задача минимизации функционала
-
.
-
Здесь коэффициенты и функции
фиксированы и не зависят от
. Благодаря этому настройка
сводится к стандартной задаче наименьших квадратов с обучающей выборкой
. Для ее решения годятся любые одномерные методы: ядерное сглаживание, сплайны, полиномиальная или Фурье-аппроксимация. Для ядерного сглаживания с фиксированной шириной окна этап настройки функции
фактически отсутствует; чтобы вычислять значения
по формуле Надарая-Ватсона, достаточно просто запомнить выборку
.
После настройки всех функций происходит возврат к первому шагу, и снова решается задача многомерной линейной регрессии для определения
. Отсюда происходит и название метода – настройка с возвращениями (backfitting).
Схема алгоритма настройки с возвращениями (backfitting)
Входные параметры:
-
– матрица «объекты-признаки»;
-
– вектор ответов;
Выход:
-
– вектор коэффициентов линейной комбинации.
-
– преобразования исходных признаков.
Алгоритм 1. |
1: нулевое приближение: 2: повторять |
Упрощенный вариант метода настройки с возвращениями (backfitting)
Описание
Предлагается отказаться от решения задачи многомерной линейной регрессии на каждом шаге алгоритма, существенно упростив метод решения. В этом случае процедура настройки будет состоять из двух этапов:
- На первом этапе решается задача многомерной линейной регрессии:
-
.
-
Линейные коэффициенты определяются как МНК-решение данной линейной задачи.
- На втором этапе настраиваем функции
. В качестве начального приближения
берем функции:
.
А далее выполняется циклический процесс настройки с помощью ядерного сглаживания.
Схема алгоритма упрощенного метода настройки с возвращениями (backfitting)
Входные параметры:
-
– матрица «объекты-признаки»;
-
– вектор ответов;
Выход:
-
– вектор коэффициентов линейной комбинации.
-
– преобразования исходных признаков.
Алгоритм 2. |
1: нулевое приближение:
|
В итоге получаем модель вида
-
.
-
Проблемы
- Выбор признака
на шаге 4 Алгоритма 1. Правильней, наверное, выбирать признак, для которого функционал RSS (Остаточная сумма квадратов) больше.
- Выбор ширины окна
при ядерном сглаживании на шаге 7 Алгоритма 1.
- Критерий останова на шаге 8 Алгоритма 1.
Проблемы 1)-3) можно решить, воспользовавшись анализом регрессионных остатков.
История
Метод настройки с возвращениями (backfitting) предложен Хасти и Тибширани в 1986 году.
Литература
- Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
- Wolfgang Härdle, Marlene Müller, Stefan Sperlich, Axel Werwatz Nonparametric and Semiparametric Models. — 2004.
- Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning. — 2001. — 533 с.
- Craig F. Ansley and Robert Kohn Convergence of the Backfitting Algorithm for Additive Models // Australian Mathematical Society. — 1994 T. Ser A 57. — С. 316-329.
- John Fox Introduction to Nonparametric Regression. — 2005.
См. также
- Статистический анализ данных (курс лекций, К.В.Воронцов)
- Непараметрическая регрессия
- Многомерная линейная регрессия
- Ядерное сглаживание