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

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

(Различия между версиями)
Перейти к: навигация, поиск
(дополнение)
м («Backfitting» переименована в «Метод настройки с возвращениями» поверх перенаправления: перевод названия на русский язык)

Версия 20:29, 11 января 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 – число независимых переменных (число признаков). Через 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)

Описание

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

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 – вектор коэффициентов линейной комбинации.
  • \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)).

Проблемы

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

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

История

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

Литература

  1. Воронцов К.В. Лекции по алгоритмам восстановления регрессии. — 2007.
  2. Wolfgang Härdle, Marlene Müller, Stefan Sperlich, Axel Werwatz Nonparametric and Semiparametric Models. — 2004.
  3. Hastie, T., Tibshirani, R., Friedman, J. The Elements of Statistical Learning. — 2001. — 533 с.
  4. Craig F. Ansley and Robert Kohn Convergence of the Backfitting Algorithm for Additive Models // Australian Mathematical Society. — 1994 T. Ser A 57. — С. 316-329.
  5. John Fox Introduction to Nonparametric Regression. — 2005.


См. также

Ссылки

Источник — «http://www.recognition.su/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»