Рекурсивный (онлайн) регуляризованный алгоритм наименьших квадратов

Может ли кто-нибудь указать мне направление онлайнового (рекурсивного) алгоритма регуляризации Тихонова (регуляризованных наименьших квадратов)?

В автономном режиме я вычисляю $\hat\beta=(X^TX+λI)^{−1}X^TY$ используя мой исходный набор данных, где $λ$ находится с помощью n-кратной перекрестной проверки. Новое значение $y$ можно предсказать для данного $x$ используя $y=x^T\hat\beta$ .

В режиме онлайн я постоянно рисую новые точки данных. Как я могу обновить $\hat\beta$ когда я рисую новые дополнительные образцы данных, не выполняя полный пересчет всего набора данных (оригинал + новый)?

$\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i$

Пусть $M_n^{-1} = (XX^T+λI)^{−1}$ , тогда

$\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n)$ и

$M_{n+1} - M_n = x_nx_n^T$ , мы можем получить

$\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n - x_n^T\hat\beta_{n})$

Согласно формуле Вудбери мы имеем

$M_{n+1}^{-1} = M_{n}^{-1} - \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}$

Как результат,

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n - x_n^T\hat\beta_{n})$

Полякское усреднение показывает, что вы можете использовать для аппроксимации с диапазонами от до . Вы можете попробовать в вашем случае выбрать лучший для вашей рекурсии.M - 1 $\eta_n = n^{-\alpha}$ α0,51$\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$$\alpha$$0.5$$1$$\alpha$

Я думаю, что это также работает, если вы применяете алгоритм пакетного градиента:

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i - x_i^T\hat\beta_{n})$

До сих пор никто не обращал внимания на то, что обычно не имеет смысла сохранять параметр регуляризации постоянным при добавлении точек данных. Причина этого в том, что , как правило, будет расти линейно с количеством точек данных, тогда как член регуляризации не будет. ‖ X β - y ‖ 2 ‖ λ β ‖ $\lambda$$\| X \beta -y \|^{2}$$\| \lambda\beta \|^{2}$

Возможно, что-то вроде стохастического градиентного спуска могло бы сработать здесь. Вычислите используя приведенное выше уравнение для начального набора данных, которое будет вашей начальной оценкой. Для каждой новой точки данных вы можете выполнить один шаг градиентного спуска, чтобы обновить оценку параметров.$\hat{\beta}$

В линейной регрессии одной из возможностей является непосредственное обновление QR-разложения , как описано здесь . Я предполагаю, что, если вы не хотите переоценивать после добавления каждого нового элемента данных, нечто очень похожее можно сделать с регрессией гребня.$X$$\lambda$

Вот альтернативный (и менее сложный) подход по сравнению с использованием формулы Вудбери. Обратите внимание, что и могут быть записаны как суммы . Так как мы вычисляем вещи онлайн и не хотим, чтобы сумма взорвалась, мы можем альтернативно использовать средства ( и ).$X^TX$$X^Ty$$X^TX/n$$X^Ty/n$

Если вы напишите и как:$X$$y$

мы можем записать онлайн-обновления для и (рассчитанные до строки) как:$X^TX/n$$X^Ty/n$$t$

Ваша онлайн оценка становится$\beta$

Обратите внимание, что это также помогает интерпретировать оставаясь постоянным, когда вы добавляете наблюдения!$\lambda$

С помощью этой процедуры https://github.com/joshday/OnlineStats.jl вычисляет онлайн-оценки линейной / ребристой регрессии.