Алгоритм подгонки - Backfitting algorithm

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

Алгоритм

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

${ Displaystyle Y_ {я} = альфа + сумма _ {j = 1} ^ {p} f_ {j} (X_ {ij}) + 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 сумма _ {я = 1} ^ {N} f_ {j} (X_ {ij}) = 0}$ для всех ${ displaystyle j}$

уход

${ Displaystyle альфа = 1 / N сумма _ {я = 1} ^ {N} y_ {я}}$

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

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

   Инициализировать ${ displaystyle { hat { alpha}} = 1 / N  sum _ {i = 1} ^ {N} y_ {i}, { hat {f_ {j}}}  Equiv 0}$,${ displaystyle  forall j}$   Делать до того как ${ displaystyle { hat {f_ {j}}}}$ сходятся: За каждый предсказатель j:           (а) ${ displaystyle { hat {f_ {j}}}  leftarrow { text {Smooth}} [ lbrace y_ {i} - { hat { alpha}} -  sum _ {k  neq j} { шляпа {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}}}$ - наш сглаживающий оператор. Обычно это выбирается кубический шлиц более гладкий но может быть любая другая подходящая операция подгонки, например:

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

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

Мотивация

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

${ Displaystyle мин Е [Y - ( альфа + сумма _ {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_ {я} ( 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}} е = QY ,}$

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

${ displaystyle { hat {f_ {i}}} ^ {(j)} 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})}$

Если обозначить ${ Displaystyle { шляпа {f}} _ {1} ^ {(я)}}$ как оценка ${ 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 { шляпа {f}} _ {1} ^ {(я)}}$ путем прямого отключения от ${ 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 { шляпа {f}} _ {1} ^ {(я)}}$ и ${ displaystyle { hat {f}} _ {2} ^ {(i)}}$ сходиться к ${ displaystyle f_ {1}}$ и ${ displaystyle f_ {2}}$ соответственно, подставляя эти выражения в исходные уравнения.

вопросы

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

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

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

Мы можем изменить алгоритм подбора, чтобы упростить предоставление уникального решения. Позволять ${ Displaystyle { mathcal {V}} _ {1} (S_ {я})}$ - пространство, порожденное всеми собственными векторами S_я соответствующих собственному значению 1. Тогда любое б удовлетворение ${ 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}}}}$ сходиться: Регресс ${ displaystyle y - { hat {f _ {+}}}}$ в космос ${ displaystyle { mathcal {V}} _ {1} (S_ {i}) +  dots + { mathcal {V}} _ {1} (S_ {p})}$, параметр ${ Displaystyle а = А (Y - { шляпа {е _ {+}}})}$       За каждый предсказатель j: Применить обновление подгонки к ${ displaystyle (Y-a)}$ с помощью оператора сглаживания ${ displaystyle (I-A_ {i}) S_ {i}}$, давая новые оценки для ${ displaystyle { hat {f_ {j}}}}$

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Декабрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

внешняя ссылка

• Пакет R для переоборудования GAM
• Пакет R для переоборудования BRUTO