Метод настройки с возвращениями
Материал из MachineLearning.
(дополнение) |
м (формулы) |
||
(2 промежуточные версии не показаны) | |||
Строка 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). | ||
Строка 70: | Строка 70: | ||
|- | |- | ||
|1: нулевое приближение: <tex>\theta</tex> := [[многомерная линейная регрессия| МНК-решение]] задачи <tex>y(x_i) = f(x_i, \theta) = \sum_{j=1}^k \theta_j \cdot f_j (x_i) , i = 1,...,n </tex>; | |1: нулевое приближение: <tex>\theta</tex> := [[многомерная линейная регрессия| МНК-решение]] задачи <tex>y(x_i) = f(x_i, \theta) = \sum_{j=1}^k \theta_j \cdot f_j (x_i) , i = 1,...,n </tex>; | ||
- | <tex>\;\;\;</tex><tex>\widehat{\varphi}_{ij} = \widehat{\ theta}_j \cdot f_j(x_i)</tex><br/> | + | <tex>\;\;\;</tex><tex>\widehat{\varphi}_{ij} = \widehat{\theta}_j \cdot f_j(x_i)</tex><br/> |
2: '''повторять''' <br/> | 2: '''повторять''' <br/> | ||
3: <tex>\;\;\;</tex>'''для''' <tex> j = 1,...,k</tex><br/> | 3: <tex>\;\;\;</tex>'''для''' <tex> j = 1,...,k</tex><br/> |
Текущая версия
На практике встречаются ситуации, когда линейная модель регрессии представляется необоснованной, но предложить адекватную нелинейную модель также не удается. Тогда в качестве альтернативы строится модель вида
- ,
где - некоторые преобразования исходных признаков, в общем случае нелинейные. Задача состоит в том, чтобы одновременно подобрать и коэффициенты линейной модели , и неизвестные одномерные преобразования , при которых достигается минимум квадратичного функционала 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.
См. также
- Статистический анализ данных (курс лекций, К.В.Воронцов)
- Непараметрическая регрессия
- Многомерная линейная регрессия
- Ядерное сглаживание