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

Итерационная процедура

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

Алгоритм

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

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

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

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

уход

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

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

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

 Инициализировать , выполнять до тех пор, пока не сойдутся: для каждого предиктора j : (a) (шаг обратной подгонки) (b) (среднее центрирование оценочной функции) ${\displaystyle {\hat {\alpha }}=1/N\sum _{i=1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}$ ${\displaystyle \forall j}$  ${\displaystyle {\hat {f_{j}}}}$  ${\displaystyle {\hat {f_{j}}}\leftarrow {\text{Smooth}}[\lbrace y_{i}-{\hat {\alpha }}-\sum _{k\neq j}{\hat {f_{k}}}(x_{ik})\rbrace _{1}^{N}]}$  ${\displaystyle {\hat {f_{j}}}\leftarrow {\hat {f_{j}}}-1/N\sum _{i=1}^{N}{\hat {f_{j}}}(x_{ij})}$

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

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

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

Мотивация

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle {\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 .

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

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

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

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

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

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

${\displaystyle {\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)}}$

и

${\displaystyle {\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)}}$

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

${\displaystyle {\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}$

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

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

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

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

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

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

Проблемы

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

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

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

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

 Инициализировать , , Делать до тех пор, пока не сойдутся: ${\displaystyle {\hat {\alpha }}=1/N\sum _{1}^{N}y_{i},{\hat {f_{j}}}\equiv 0}$ ${\displaystyle \forall i,j}$ ${\displaystyle {\hat {f_{+}}}=\alpha +{\hat {f_{1}}}+\dots +{\hat {f_{p}}}}$  ${\displaystyle {\hat {f_{j}}}}$ Регрессия в пространство , установка Для каждого предиктора j : ${\displaystyle y-{\hat {f_{+}}}}$ ${\displaystyle {\mathcal {V}}_{1}(S_{i})+\dots +{\mathcal {V}}_{1}(S_{p})}$ ${\displaystyle a=A(Y-{\hat {f_{+}}})}$  Примените обновление обратной подгонки к использованию оператора сглаживания , получив новые оценки для ${\displaystyle (Y-a)}$ ${\displaystyle (I-A_{i})S_{i}}$ ${\displaystyle {\hat {f_{j}}}}$

Рекомендации

1. Хасти, Тревор , Роберт Тибширани и Джером Фридман (2001). Элементы статистического обучения: интеллектуальный анализ данных, логический вывод и прогнозирование . Спрингер, ISBN  0-387-95284-5 .
2. Хердле, Вольфганг; и другие. (9 июня 2004 г.). «Обратное оснащение». Архивировано из оригинала 10 мая 2015 г. Проверено 19 августа 2015 г.

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

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

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