Алгоритм обратной подгонки

В статистике алгоритм обратной подгонки представляет собой простую итерационную процедуру, используемую для подгонки обобщенной аддитивной модели . Она была представлена ​​в 1985 году Лео Брейманом и Джеромом Фридманом вместе с обобщенными аддитивными моделями. В большинстве случаев алгоритм обратного подгонки эквивалентен методу Гаусса–Зейделя — алгоритму, используемому для решения определенной линейной системы уравнений .

Алгоритм

Аддитивные модели — это класс непараметрических регрессионных моделей вида:

$Y_{i}=\alpha +\sum _{j=1}^{p}f_{j}(X_{j})+\epsilon _{i}$

где каждый $X_{1},X_{2},\ldots ,X_{p}$ это переменная в нашем $p$-мерный предиктор $X$, и $Y$ наша результирующая переменная. $\epsilon$ представляет нашу внутреннюю ошибку, которая, как предполагается, имеет нулевое среднее значение. $f_{j}$ представляют собой неуказанные гладкие функции одного $X_{j}$. Учитывая гибкость в $f_{j}$, у нас обычно нет уникального решения: $\alpha$ остается неидентифицируемым, поскольку к любому из элементов можно добавить любые константы. $f_{j}$ и вычтем это значение из $\alpha$. Обычно это можно исправить, ограничив

$\sum _{i=1}^{N}f_{j}(X_{ij})=0$ для всех $j$

уход

$\alpha =1/N\sum _{i=1}^{N}y_{i}$

обязательно.

Тогда алгоритм переоснащения следующий:

   Initialize ${\hat {\alpha }}=1/N\sum _{i=1}^{N}y_{i},{\hat {f_{j}}}\equiv 0$,$\forall j$
   Do until ${\hat {f_{j}}}$ converge:
       For each predictor j:
           (a) ${\hat {f_{j}}}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]$ (backfitting step)
           (b) ${\hat {f_{j}}}\leftarrow {\hat {f_{j}}}-1/N\sum _{i=1}^{N}{\hat {f_{j}}}(x_{ij})$ (mean centering of estimated function)

где ${\text{Smooth}}$ наш оператор сглаживания. Обычно это сглаживание кубического сплайна, но может быть любая другая подходящая операция подгонки, например:

• локальная полиномиальная регрессия
• сглаживания ядра методы
• более сложные операторы, такие как сглаживатели поверхности для взаимодействий второго и более высокого порядка.

Теоретически шаг (b) в алгоритме не требуется, поскольку суммы оценок функции ограничены нулевой суммой. Однако из-за численных проблем это может стать проблемой на практике.

Мотивация

Если рассмотреть задачу минимизации ожидаемой квадратичной ошибки:

$\min E[Y-(\alpha +\sum _{j=1}^{p}f_{j}(X_{j}))]^{2}$

Согласно теории проекций существует единственное решение, определяемое формулой:

$f_{i}(X_{i})=E[Y-(\alpha +\sum _{j\neq i}^{p}f_{j}(X_{j}))|X_{i}]$

для я = 1, 2, ..., п .

Это дает матричную интерпретацию:

${\begin{pmatrix}I&P_{1}&\cdots &P_{1}\\P_{2}&I&\cdots &P_{2}\\\vdots &&\ddots &\vdots \\P_{p}&\cdots &P_{p}&I\end{pmatrix}}{\begin{pmatrix}f_{1}(X_{1})\\f_{2}(X_{2})\\\vdots \\f_{p}(X_{p})\end{pmatrix}}={\begin{pmatrix}P_{1}Y\\P_{2}Y\\\vdots \\P_{p}Y\end{pmatrix}}$

где $P_{i}(\cdot )=E(\cdot |X_{i})$. В этом контексте мы можем представить более гладкую матрицу, $S_{i}$, что приблизительно соответствует нашему $P_{i}$ и дает оценку, $S_{i}Y$, из $E(Y|X)$

${\begin{pmatrix}I&S_{1}&\cdots &S_{1}\\S_{2}&I&\cdots &S_{2}\\\vdots &&\ddots &\vdots \\S_{p}&\cdots &S_{p}&I\end{pmatrix}}{\begin{pmatrix}f_{1}\\f_{2}\\\vdots \\f_{p}\end{pmatrix}}={\begin{pmatrix}S_{1}Y\\S_{2}Y\\\vdots \\S_{p}Y\end{pmatrix}}$

или в сокращенной форме

${\hat {S}}f=QY\,$

Точное решение этой задачи невозможно вычислить при больших np , поэтому используется итеративный метод обратной подгонки. Мы делаем первоначальные предположения $f_{j}^{(0)}$ и обновляйте каждый $f_{j}^{(\ell )}$ в свою очередь, это будет сглаженная аппроксимация остатков всех остальных:

${\hat {f_{j}}}^{(\ell )}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]$

Глядя на сокращенную форму, легко увидеть, что алгоритм обратного подгонки эквивалентен методу Гаусса–Зейделя для линейных операторов сглаживания S .

Явный вывод для двух измерений

Следующий, мы можем сформулировать алгоритм обратной подгонки явно для двумерного случая. У нас есть:

$f_{1}=S_{1}(Y-f_{2}),f_{2}=S_{2}(Y-f_{1})$

Если мы обозначим ${\hat {f}}_{1}^{(i)}$ как оценка $f_{1}$ на i- м этапе обновления этапы обратной подгонки:

${\hat {f}}_{1}^{(i)}=S_{1}[Y-{\hat {f}}_{2}^{(i-1)}],{\hat {f}}_{2}^{(i)}=S_{2}[Y-{\hat {f}}_{1}^{(i)}]$

По индукции получаем

${\hat {f}}_{1}^{(i)}=Y-\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})Y-(S_{1}S_{2})^{i-1}S_{1}{\hat {f}}_{2}^{(0)}$

и

${\hat {f}}_{2}^{(i)}=S_{2}\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})Y+S_{2}(S_{1}S_{2})^{i-1}S_{1}{\hat {f}}_{2}^{(0)}$

Если мы установим ${\hat {f}}_{2}^{(0)}=0$ тогда мы получим

${\hat {f}}_{1}^{(i)}=Y-S_{2}^{-1}{\hat {f}}_{2}^{(i)}=[I-\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y$

${\hat {f}}_{2}^{(i)}=[S_{2}\sum _{\alpha =0}^{i-1}(S_{1}S_{2})^{\alpha }(I-S_{1})]Y$

Где мы решили ${\hat {f}}_{1}^{(i)}$ путем прямого подключения от $f_{2}=S_{2}(Y-f_{1})$.

Мы имеем сходимость, если $\|S_{1}S_{2}\|<1$. В этом случае позволив ${\hat {f}}_{1}^{(i)},{\hat {f}}_{2}^{(i)}{\xrightarrow {}}{\hat {f}}_{1}^{(\infty )},{\hat {f}}_{2}^{(\infty )}$:

${\hat {f}}_{1}^{(\infty )}=Y-S_{2}^{-1}{\hat {f}}_{2}^{(\infty )}=Y-(I-S_{1}S_{2})^{-1}(I-S_{1})Y$

${\hat {f}}_{2}^{(\infty )}=S_{2}(I-S_{1}S_{2})^{-1}(I-S_{1})Y$

Мы можем проверить, что это решение проблемы, т. е. что ${\hat {f}}_{1}^{(i)}$ и ${\hat {f}}_{2}^{(i)}$ сходиться к $f_{1}$ и $f_{2}$ соответственно, подставив эти выражения в исходные уравнения.

Проблемы

Выбор момента остановки алгоритма произволен, и априори трудно предсказать, сколько времени займет достижение определенного порога сходимости. Кроме того, окончательная модель зависит от порядка, в котором переменные-предикторы $X_{i}$ подходят.

Кроме того, решение, найденное с помощью процедуры обратной подгонки, не является единственным. Если $b$ вектор такой, что ${\hat {S}}b=0$ сверху, то если ${\hat {f}}$ это решение, то так же ${\hat {f}}+\alpha b$ также является решением для любого $\alpha \in \mathbb {R}$. Модификация алгоритма обратной подгонки, включающая проекции на собственное пространство S, может решить эту проблему.

Модифицированный алгоритм

Мы можем изменить алгоритм обратной подгонки, чтобы упростить поиск уникального решения. Позволять ${\mathcal {V}}_{1}(S_{i})$ — пространство, охватываемое всеми собственными векторами Si _, соответствующими собственному значению 1. Тогда любой b, удовлетворяющий ${\hat {S}}b=0$ имеет $b_{i}\in {\mathcal {V}}_{1}(S_{i})\forall i=1,\dots ,p$ и $\sum _{i=1}^{p}b_{i}=0.$ Теперь, если мы возьмем $A$ быть матрицей, которая проектируется ортогонально на ${\mathcal {V}}_{1}(S_{1})+\dots +{\mathcal {V}}_{1}(S_{p})$, мы получаем следующий модифицированный алгоритм обратной подгонки:

   Initialize ${\hat {\alpha }}=1/N\sum _{1}^{N}y_{i},{\hat {f_{j}}}\equiv 0$,$\forall i,j$, ${\hat {f_{+}}}=\alpha +{\hat {f_{1}}}+\dots +{\hat {f_{p}}}$
   Do until ${\hat {f_{j}}}$ converge:
       Regress $y-{\hat {f_{+}}}$ onto the space ${\mathcal {V}}_{1}(S_{i})+\dots +{\mathcal {V}}_{1}(S_{p})$, setting $a=A(Y-{\hat {f_{+}}})$
       For each predictor j:
           Apply backfitting update to $(Y-a)$ using the smoothing operator $(I-A_{i})S_{i}$, yielding new estimates for ${\hat {f_{j}}}$

Ссылки

• Брейман Л. и Фридман Дж. Х. (1985). «Оценка оптимальных преобразований для множественной регрессии и корреляций (с обсуждением)». Журнал Американской статистической ассоциации . 80 (391): 580–619. дои : 10.2307/2288473 . JSTOR   2288473 .
• Хасти, ТиДжей и Тибширани, Р.Дж. (1990). «Обобщенные аддитивные модели». Монографии по статистике и прикладной теории вероятности . 43 .
• Хердле, Вольфганг; и др. (9 июня 2004 г.). «Обратное оснащение» . Архивировано из оригинала 10 мая 2015 г. Проверено 19 августа 2015 г.

Внешние ссылки

• Пакет R для дооснащения GAM
• Пакет R для дооснащения BRUTO