Метод настройки с возвращениями

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

(Различия между версиями)

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

На практике встречаются ситуации, когда линейная модель регрессии представляется необоснованной, но предложить адекватную нелинейную модель $f(x, \theta),\; \theta \in \mathbb{R}^k$ также не удается. Тогда в качестве альтернативы строится модель вида

$y(x) = f(x, \theta) = \sum_{j=1}^k \theta_j \cdot \varphi_j(f_j (x))$ ,

где $\varphi_j: \mathbb{R} \rightarrow \mathbb{R}$ - некоторые преобразования исходных признаков, в общем случае нелинейные. Задача состоит в том, чтобы одновременно подобрать и коэффициенты линейной модели $\theta_j$ , и неизвестные одномерные преобразования $\varphi_j$ , при которых достигается минимум квадратичного функционала RSS – остаточная сумма квадратов.

Суть метода заключается в том, что в линейную модель добавляются нелинейные преобразования исходных признаков. Другими словами метод настройки с возвращениями (backfitting) совмещает многомерную линейную регрессию и одномерное сглаживание. Таким образом, нелинейная задача сводится к решению последовательности линейных задач.

Содержание

1 Обозначения
2 Метод настройки с возвращениями (backfitting)
- 2.1 Описание
- 2.2 Схема алгоритма настройки с возвращениями (backfitting)
3 Упрощенный вариант метода настройки с возвращениями (backfitting)
- 3.1 Описание
- 3.2 Схема алгоритма упрощенного метода настройки с возвращениями (backfitting)
4 Проблемы
5 История
6 Литература
7 См. также
8 Ссылки

Обозначения

Дана выборка $X^n = (x_i,\; y_i)_{i=1}^n$ ; $n$ – длина выборки. При этом $x_i \in \mathbb{R}^k,\; i = 1,...,n$ ; $k$ – число независимых переменных (число признаков). Через $f_j(x_i),\; i = 1,...,n; \; j = 1,...,k$ будем обозначать $j$ -тый признак $i$ -го объекта выборки.

Значение целевой зависимости для $i$ -го объекта $y_i \in \mathbb{R},\; i = 1,...,n$ .

Обозначим через $\widehat{\varphi}_{ij}$ оценку $\varphi_j(f _j(x_i))$ .

Метод настройки с возвращениями (backfitting)

Описание

Метод настройки с возвращениями в традиционной форме основан на итерационном повторении двух шагов:

На первом шаге фиксируются функции $\varphi_j$ , и методами многомерной линейной регрессии вычисляются коэффициенты $\theta_j$ .
На втором шаге фиксируются коэффициенты $\theta_j$ и все функции $\{\varphi_k\}_{k \neq j}$ кроме одной $\varphi_j$ , которая настраивается методами одномерной непараметрической регрессии. На втором шаге решается задача минимизации функционала

$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}$ .

Здесь коэффициенты $\theta_j$ и функции $\{\varphi_k\}_{k \neq j}$ фиксированы и не зависят от $\varphi_j$ . Благодаря этому настройка $\varphi_j$ сводится к стандартной задаче наименьших квадратов с обучающей выборкой $\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$ . Для ее решения годятся любые одномерные методы: ядерное сглаживание, сплайны, полиномиальная или Фурье-аппроксимация. Для ядерного сглаживания с фиксированной шириной окна этап настройки функции $\varphi_j$ фактически отсутствует; чтобы вычислять значения $\varphi_j(f)$ по формуле Надарая-Ватсона, достаточно просто запомнить выборку $\tilde{X}_j^n$ .

После настройки всех функций $\varphi_j$ происходит возврат к первому шагу, и снова решается задача многомерной линейной регрессии для определения $\theta_j$ . Отсюда происходит и название метода – настройка с возвращениями (backfitting).

Схема алгоритма настройки с возвращениями (backfitting)

Входные параметры:

$X$ – матрица «объекты-признаки»;
$y$ – вектор ответов;

Выход:

$\theta$ – вектор коэффициентов линейной комбинации.
$\varphi_j, j = 1,...,n$ – преобразования исходных признаков.

Алгоритм 1.

1: нулевое приближение: $\varphi_j (u) \equiv u, j = 1,...,n$ ;

2: повторять
3: $\;\;\;$ {1 шаг} $\theta$ := решение задачи МЛР с признаками $\varphi_j(f_j(x))$ ;
4: $\;\;\;$ {2 шаг} для $j = 1,...,k$
5: $\;\;\;\;\;\;$ $\widetilde{x_i}:= f_j(x_i), i = 1,...,n$ ;
6: $\;\;\;\;\;\;$ $\widetilde{y_i}:= y_i - \sum_{s=1,\; s \neq j }^k \theta_s \widehat{\varphi}_{is}, i = 1,...,n$ ;
7: $\;\;\;\;\;\;$ Ядерное сглаживание: $\widehat{\varphi}_{ij}:= \frac {\sum_{t=1}^n W_t(\widetilde{x_i}) \widetilde{y_t} }{\sum_{t=1}^n W_t(\widetilde{x_i}) }$ , где $W_t(\widetilde{x_i}) = K\left( \frac{\widetilde{x_i} - \widetilde{x_t}}{h} \right) i = 1,...,n$
8: пока остаточная сумма квадратов $RSS = \sum_{i=1}^n (y(x_i) - y_i)^2$ уменьшается.

Упрощенный вариант метода настройки с возвращениями (backfitting)

Описание

Предлагается отказаться от решения задачи многомерной линейной регрессии на каждом шаге алгоритма, существенно упростив метод решения. В этом случае процедура настройки будет состоять из двух этапов:

На первом этапе решается задача многомерной линейной регрессии:

$y(x_i) = f(x_i, \theta) = \sum_{j=1}^k \theta_j \cdot f_j (x_i) , i = 1,...,n$ .

Линейные коэффициенты $\theta_j$ определяются как МНК-решение данной линейной задачи.

На втором этапе настраиваем функции $\varphi_j$ . В качестве начального приближения $\varphi_j$ берем функции: $\widehat{\varphi}_{ij} = \widehat{\theta}_j \cdot f_j(x_i)$ .

А далее выполняется циклический процесс настройки с помощью ядерного сглаживания.

Схема алгоритма упрощенного метода настройки с возвращениями (backfitting)

Входные параметры:

$X$ – матрица «объекты-признаки»;
$y$ – вектор ответов;

Выход:

$\theta$ – вектор коэффициентов линейной комбинации.
$\varphi_j, j = 1,...,n$ – преобразования исходных признаков.

Алгоритм 2.

1: нулевое приближение: $\theta$ := МНК-решение задачи $y(x_i) = f(x_i, \theta) = \sum_{j=1}^k \theta_j \cdot f_j (x_i) , i = 1,...,n$ ;

$\;\;\;$ $\widehat{\varphi}_{ij} = \widehat{\theta}_j \cdot f_j(x_i)$
2: повторять
3: $\;\;\;$ для $j = 1,...,k$
4: $\;\;\;\;\;\;$ $\widetilde{x_i}:= f_j(x_i), i = 1,...,n$ ;
5: $\;\;\;\;\;\;$ $\widetilde{y_i}:= y_i - \sum_{s=1,\; s \neq j }^k \theta_s \widehat{\varphi}_{is}, i = 1,...,n$ ;
6: $\;\;\;\;\;\;$ Ядерное сглаживание: $\widehat{\varphi}_{ij}:= \frac {\sum_{t=1}^n W_t(\widetilde{x_i}) \widetilde{y_t} }{\sum_{t=1}^n W_t(\widetilde{x_i}) }$ , где $W_t(\widetilde{x_i}) = K\left( \frac{\widetilde{x_i} - \widetilde{x_t}}{h} \right) i = 1,...,n$
7: пока остаточная сумма квадратов $RSS = \sum_{i=1}^n (y(x_i) - y_i)^2$ уменьшается.

В итоге получаем модель вида

$y(x) = \sum_{j=1}^k \theta_j \cdot \varphi_j(f_j (x))$ .

Проблемы

Выбор признака $j$ на шаге 4 Алгоритма 1. Правильней, наверное, выбирать признак, для которого функционал RSS (Остаточная сумма квадратов) больше.
Выбор ширины окна $h$ при ядерном сглаживании на шаге 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.

См. также

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D1%81%D1%82%D1%80%D0%BE%D0%B9%D0%BA%D0%B8_%D1%81_%D0%B2%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%89%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8»

Категории: Прикладная статистика | Регрессионный анализ | Энциклопедия анализа данных

@@ Строка 1: / Строка 1: @@
+На практике встречаются ситуации, когда [[многомерная линейная регрессия| линейная модель регрессии]] представляется необоснованной, но предложить адекватную [[нелинейная регрессия| нелинейную модель]] <tex>f(x, \theta),\; \theta  \in \mathbb{R}^k</tex> также не удается. Тогда в качестве альтернативы строится модель вида
+:: <tex>y(x) = f(x, \theta) = \sum_{j=1}^k \theta_j  \cdot \varphi_j(f_j (x))</tex>,
+где <tex>\varphi_j: \mathbb{R} \rightarrow \mathbb{R}</tex> - некоторые преобразования исходных признаков, в общем случае нелинейные. Задача состоит в том, чтобы одновременно подобрать и коэффициенты линейной модели <tex>\theta_j</tex>, и неизвестные одномерные преобразования <tex>\varphi_j</tex>, при которых достигается минимум квадратичного функционала RSS – [[остаточная сумма квадратов]].
+Суть метода заключается в том, что в линейную модель добавляются нелинейные преобразования исходных признаков. Другими словами '''метод настройки с возвращениями''' ('''backfitting''') совмещает [[многомерная линейная регрессия | многомерную линейную регрессию]] и [[ядерное сглаживание| одномерное сглаживание]].
+Таким образом, нелинейная задача сводится к решению последовательности линейных задач.
+== Обозначения ==
+Дана [[выборка]] <tex>X^n = (x_i,\; y_i)_{i=1}^n</tex>; <tex>n</tex> – длина выборки.
+При этом <tex>x_i \in \mathbb{R}^k,\; i = 1,...,n</tex>; <tex>k</tex> – число независимых переменных (число признаков).
+Через <tex>f_j(x_i),\; i = 1,...,n; \; j = 1,...,k</tex> будем обозначать <tex>j</tex>-тый признак <tex>i</tex>-го объекта выборки.
+Значение [[Целевая зависимость| целевой зависимости]] для <tex>i</tex>-го объекта <tex>y_i \in \mathbb{R},\; i = 1,...,n</tex>.
+Обозначим через <tex>\widehat{\varphi}_{ij}</tex> оценку <tex>\varphi_j(f _j(x_i))</tex>.
+== Метод настройки с возвращениями (backfitting) ==
+=== Описание ===
+Метод настройки с возвращениями в традиционной форме основан на итерационном повторении двух шагов:
+* На первом шаге фиксируются функции <tex>\varphi_j</tex>, и ''[[многомерная линейная регрессия| методами многомерной линейной регрессии]]'' вычисляются коэффициенты <tex>\theta_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 \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>\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).
+=== Схема алгоритма настройки с возвращениями (backfitting)  ===
+Входные параметры:
+* <tex>X</tex> – матрица «объекты-признаки»;
+* <tex>y</tex> – вектор ответов;
+Выход:
+* <tex>\theta</tex> – вектор коэффициентов линейной комбинации.
+* <tex>\varphi_j, j = 1,...,n</tex> – преобразования исходных признаков.
+{| border=1
+|Алгоритм 1.
+|-
+|1: нулевое приближение: <tex>\varphi_j (u) \equiv u, j = 1,...,n</tex>;
+: '''повторять''' <br/>
+: <tex>\;\;\;</tex>''{1 шаг}'' <tex>\theta</tex> := решение задачи [[многомерная линейная регрессия| МЛР]] с признаками <tex>\varphi_j(f_j(x))</tex>;<br/>
+: <tex>\;\;\;</tex>''{2 шаг}'' '''для''' <tex> j = 1,...,k</tex><br/>
+: <tex>\;\;\;\;\;\;</tex><tex> \widetilde{x_i}:=  f_j(x_i), i = 1,...,n</tex>;<br/>
+: <tex>\;\;\;\;\;\;</tex><tex> \widetilde{y_i}:=  y_i - \sum_{s=1,\; s \neq j }^k \theta_s  \widehat{\varphi}_{is}, i = 1,...,n</tex>;<br/>
+: <tex>\;\;\;\;\;\;</tex> [[Ядерное сглаживание]]: <tex> \widehat{\varphi}_{ij}:= \frac {\sum_{t=1}^n W_t(\widetilde{x_i}) \widetilde{y_t} }{\sum_{t=1}^n W_t(\widetilde{x_i}) }</tex>, где <tex>W_t(\widetilde{x_i}) = K\left( \frac{\widetilde{x_i} - \widetilde{x_t}}{h} \right) i = 1,...,n</tex><br/>
+: '''пока''' [[остаточная сумма квадратов]] <tex>RSS = \sum_{i=1}^n (y(x_i) - y_i)^2</tex> уменьшается.
+|}
+== Упрощенный вариант метода настройки с возвращениями (backfitting) ==
+=== Описание ===
+Предлагается отказаться от решения задачи [[многомерная линейная регрессия| многомерной линейной регрессии]] на каждом шаге алгоритма, существенно упростив метод решения. В этом случае процедура настройки будет состоять из двух этапов:
+* На первом этапе решается задача [[многомерная линейная регрессия| многомерной линейной регрессии]]:
+:: <tex>y(x_i) = f(x_i, \theta) = \sum_{j=1}^k \theta_j  \cdot f_j (x_i) , i = 1,...,n </tex>.
+Линейные коэффициенты <tex>\theta_j</tex> определяются как [[многомерная линейная регрессия| МНК-решение]] данной линейной задачи.
+* На втором этапе настраиваем функции <tex>\varphi_j</tex>. В качестве начального приближения <tex>\varphi_j</tex> берем функции: <tex>\widehat{\varphi}_{ij} = \widehat{\theta}_j \cdot f_j(x_i)</tex>.
+А далее выполняется циклический процесс настройки с помощью ядерного сглаживания.
+=== Схема алгоритма упрощенного метода настройки с возвращениями (backfitting)  ===
+Входные параметры:
+* <tex>X</tex> – матрица «объекты-признаки»;
+* <tex>y</tex> – вектор ответов;
+Выход:
+* <tex>\theta</tex> – вектор коэффициентов линейной комбинации.
+* <tex>\varphi_j, j = 1,...,n</tex> – преобразования исходных признаков.
+{| border=1
+|Алгоритм 2.
+|-
+ |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/>
+: '''повторять''' <br/>
+: <tex>\;\;\;</tex>'''для''' <tex> j = 1,...,k</tex><br/>
+: <tex>\;\;\;\;\;\;</tex><tex> \widetilde{x_i}:=  f_j(x_i), i = 1,...,n</tex>;<br/>
+: <tex>\;\;\;\;\;\;</tex><tex> \widetilde{y_i}:=  y_i - \sum_{s=1,\; s \neq j }^k \theta_s  \widehat{\varphi}_{is}, i = 1,...,n</tex>;<br/>
+: <tex>\;\;\;\;\;\;</tex> [[Ядерное сглаживание]]: <tex> \widehat{\varphi}_{ij}:= \frac {\sum_{t=1}^n W_t(\widetilde{x_i}) \widetilde{y_t} }{\sum_{t=1}^n W_t(\widetilde{x_i}) }</tex>, где <tex>W_t(\widetilde{x_i}) = K\left( \frac{\widetilde{x_i} - \widetilde{x_t}}{h} \right) i = 1,...,n</tex><br/>
+: '''пока''' [[остаточная сумма квадратов]] <tex>RSS = \sum_{i=1}^n (y(x_i) - y_i)^2</tex> уменьшается.
+|}
+В итоге получаем модель вида
+:: <tex>y(x) = \sum_{j=1}^k \theta_j  \cdot \varphi_j(f_j (x))</tex>.
+== Проблемы ==
+# Выбор признака <tex>j</tex> на шаге 4 Алгоритма 1. Правильней, наверное, выбирать признак, для которого функционал RSS ([[Остаточная сумма квадратов]]) больше.
+# Выбор ширины окна <tex>h</tex> при ядерном сглаживании на шаге 7 Алгоритма 1.
+# Критерий останова на шаге 8 Алгоритма 1.
+Проблемы 1)-3) можно решить, воспользовавшись [[анализ регрессионных остатков| анализом регрессионных остатков]].
+== История ==
+Метод настройки с возвращениями (backfitting)  предложен Хасти и Тибширани в 1986 году.
 == Литература ==
+# {{книга
+|автор        = Воронцов К.В.
+|заглавие  = Лекции по алгоритмам восстановления регрессии
+|год          = 2007
+|ссылка       = http://www.ccas.ru/voron/download/Regression.pdf
+}}
+# {{книга
+|автор        = Wolfgang Härdle, Marlene Müller, Stefan Sperlich, Axel Werwatz
+|заглавие  = Nonparametric and Semiparametric Models
+|год          = 2004
+|ссылка       = http://fedc.wiwi.hu-berlin.de/xplore/ebooks/html/spm/
+}}
+# {{книга
+|автор        = Hastie, T., Tibshirani, R., Friedman, J.
+|заглавие  = The Elements of Statistical Learning
+|год          = 2001
+|ссылка       = http://www-stat.stanford.edu/~tibs/ElemStatLearn
+|страниц      = 533
+}}
+# {{книга
+|автор        =Craig F. Ansley and Robert Kohn
+|часть        = Convergence of the Backfitting Algorithm for Additive Models
+|заглавие     = Australian Mathematical Society
+|год          = 1994
+|том          = Ser A 57
+|страницы     = 316-329
+|ссылка       = http://anziamj.austms.org.au/JAMSA/V57/Part3/Ansley.html
+}}
+# {{книга
+|автор        = John Fox
+|заглавие  = Introduction to Nonparametric Regression
+|год          = 2005
+|ссылка       = http://socserv.mcmaster.ca/jfox/Courses/Oxford-2005/slides-handout.pdf
+}}
 == См. также ==
+* [[Статистический анализ данных (курс лекций, К.В.Воронцов)]]
+* [[Непараметрическая регрессия]]
+* [[Многомерная линейная регрессия]]
+* [[Ядерное сглаживание]]
 == Ссылки ==
+* [http://209.85.129.132/search?q=cache:5CXZUCaGtdUJ:support.sas.com/rnd/app/da/new/802ce/stat/chap5/sect15.htm+backfitting&hl=ru&ct=clnk&cd=1&gl=ru Backfitting and Local Scoring Algorithms]
+* [http://fedc.wiwi.hu-berlin.de/xplore/ebooks/html/spm/spmhtmlnode37.html#s-back Backfitting]
+* [http://citeseer.ist.psu.edu/hastie95generalized.html Generalized additive models]
 [[Категория: Прикладная статистика]]
+[[Категория:Регрессионный анализ]]
+[[Категория:Энциклопедия анализа данных]]

Метод настройки с возвращениями

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

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

Содержание

Обозначения

Метод настройки с возвращениями (backfitting)

Описание

Схема алгоритма настройки с возвращениями (backfitting)

Упрощенный вариант метода настройки с возвращениями (backfitting)

Описание

Схема алгоритма упрощенного метода настройки с возвращениями (backfitting)

Проблемы

История

Литература

См. также

Ссылки

Просмотры

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

Навигация

Поиск

Инструменты