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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Литература == == См. также == == Ссылки == Категория: Прикладная статистика)
(дополнение)
Строка 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>i</tex>-го объекта <tex>y_i \in \mathbb{R},\; i = 1,...,n</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 \left(\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 = const(\varphi_j)} \right)^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>\widetilde{X}_j^n = (f_j(x_i),\; y_i - \sum_{s=1,\; s \neq j }^k \theta_s \widehat{\varphi}_{is})_{i=1}^n</tex>. Для ее решения годятся любые одномерные методы: [[ядерное сглаживание]], [[сплайны]], полиномиальная или Фурье-аппроксимация. Для [[ядерное сглаживание| ядерного сглаживания]] с фиксированной шириной окна этап настройки функции <tex>\varphi_j</tex> фактически отсутствует; чтобы вычислять значения <tex>\varphi_j(f)</tex> по [[формула Надарая-Ватсона| формуле Надарая-Ватсона]], достаточно просто запомнить выборку <tex>\widetilde{X}_j^n</tex>.
 +
 +
После настройки всех функций <tex>\varphi_j</tex> происходит возврат к первому шагу, и снова решается задача [[многомерная линейная регрессия| многомерной линейной регрессии]] для определения <tex>\theta_j</tex>. Отсюда происходит и название метода – '''настройка с возвращениями''' (backfitting).
 +
 +
== Алгоритм. Метод настройки с возвращениями (backfitting) ==
 +
Входные параметры:
 +
* <tex>X</tex> – матрица «объекты-признаки»;
 +
* <tex>y</tex> – вектор ответов;
 +
Выход:
 +
* <tex>\theta</tex> – вектор коэффициентов линейной комбинации.
 +
 +
 +
{| border=1
 +
|1: нулевое приближение: <tex>\varphi_j (u) \equiv u, j = 1,...,n</tex>;
 +
2: '''повторять''' <br/>
 +
3: <tex>\;\;\;</tex>''{1 шаг}'' <tex>\theta</tex> := решение задачи [[многомерная линейная регрессия| МЛР]] с признаками <tex>\varphi_j(f_j(x))</tex>;<br/>
 +
4: <tex>\;\;\;</tex>''{2 шаг}'' '''для''' <tex> j = 1,...,k</tex><br/>
 +
5: <tex>\;\;\;\;\;\;</tex><tex> \widetilde{x_i}:= f_j(x_i), i = 1,...,n</tex>;<br/>
 +
6: <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/>
 +
7: <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/>
 +
8: '''пока''' [[остаточная сумма квадратов]] <tex>RSS = \sum_{i=1}^n (y(x_i) - y_i)^2</tex> уменьшается.
 +
|}
 +
 +
 +
== Проблемы ==
 +
# Выбор признака <tex>j</tex> на шаге 4. Правильней, наверное, выбирать признак, для которого функционал RSS ([[Остаточная сумма квадратов]]) больше.
 +
# Выбор ширины окна <tex>h</tex> при ядерном сглаживании на шаге 7.
 +
# Критерий останова на шаге 8.
 +
 +
Проблемы 1)-3) можно решить, воспользовавшись [[анализ регрессионных остатков| анализом регрессионных остатков]].
 +
 +
== История ==
 +
Метод настройки с возвращениями (backfitting) предложен Хасти и Тибширани в 1986 году.
 +
== Литература ==
== Литература ==
 +
# {{книга
 +
|автор = Воронцов К.В.
 +
|заглавие = Лекции по алгоритмам восстановления регрессии
 +
|год = 2007
 +
|ссылка = http://www.ccas.ru/voron/download/Regression.pdf
 +
}}
 +
# {{книга
 +
|автор = Hastie, T., Tibshirani, R., Friedman, J.
 +
|заглавие = The Elements of Statistical Learning
 +
|год = 2001
 +
|ссылка = http://www-stat.stanford.edu/~tibs/ElemStatLearn
 +
|страниц = 533
 +
}}
== См. также ==
== См. также ==
 +
* [[Статистический анализ данных (курс лекций, К.В.Воронцов)]]
 +
* [[Непараметрическая регрессия]]
 +
* [[Ядерное сглаживание]]
== Ссылки ==
== Ссылки ==
 +
* [http://citeseer.ist.psu.edu/hastie95generalized.html Generalized additive models]
[[Категория: Прикладная статистика]]
[[Категория: Прикладная статистика]]

Версия 20:49, 9 января 2009

На практике встречаются ситуации, когда линейная модель регрессии представляется необоснованной, но предложить адекватную нелинейную модель 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) совмещает многомерную линейную регрессию и одномерное сглаживание. Таким образом, нелинейная задача сводится к решению последовательности линейных задач.

Содержание

Обозначения

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

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

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

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

 Q(\varphi_j, X^n) = \sum_{i=1}^n \left(\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 = const(\varphi_j)} \right)^2 \rightarrow \min_{\varphi_j}.

Здесь коэффициенты \theta_j и функции <\{\varphi_k}\}_{k \neq j} фиксированы и не зависят от \varphi_j. Благодаря этому настройка \varphi_j сводится к стандартной задаче наименьших квадратов с обучающей выборкой \widetilde{X}_j^n = (f_j(x_i),\; y_i - \sum_{s=1,\; s \neq j }^k \theta_s  \widehat{\varphi}_{is})_{i=1}^n. Для ее решения годятся любые одномерные методы: ядерное сглаживание, сплайны, полиномиальная или Фурье-аппроксимация. Для ядерного сглаживания с фиксированной шириной окна этап настройки функции \varphi_j фактически отсутствует; чтобы вычислять значения \varphi_j(f) по формуле Надарая-Ватсона, достаточно просто запомнить выборку \widetilde{X}_j^n.

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

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

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

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

Выход:

  • \theta – вектор коэффициентов линейной комбинации.


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 уменьшается.


Проблемы

  1. Выбор признака j на шаге 4. Правильней, наверное, выбирать признак, для которого функционал RSS (Остаточная сумма квадратов) больше.
  2. Выбор ширины окна h при ядерном сглаживании на шаге 7.
  3. Критерий останова на шаге 8.

Проблемы 1)-3) можно решить, воспользовавшись анализом регрессионных остатков.

История

Метод настройки с возвращениями (backfitting) предложен Хасти и Тибширани в 1986 году.

Литература

  1. Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
  2. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning. — 2001. — 533 с.

См. также

Ссылки

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