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

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

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

Содержание

[убрать]

1 Обозначения
2 Метод настройки с возвращениями (backfitting)
3 Схема алгоритма настройки с возвращениями (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$ – число независимых переменных.

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

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

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

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

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

Проблемы

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