Algoritmo de mínimos quadrados regularizado recursivo (online)

12

Alguém pode me apontar na direção de um algoritmo online (recursivo) para a regularização de Tikhonov (mínimos quadrados regularizados)?

Em uma configuração offline, eu calcularia $\hat\beta=(X^TX+λI)^{−1}X^TY$ usando meu conjunto de dados original, onde $λ$ é encontrado usando a validação cruzada n vezes. Um novo valor de $y$ pode ser previsto para um determinado $x$ usando $y=x^T\hat\beta$ .

Em uma configuração on-line, continuamente desenho novos pontos de dados. Como posso atualizar quando desenho novas amostras de dados adicionais sem fazer um recálculo completo de todo o conjunto de dados (original + novo)? $\hat\beta$

regression machine-learning least-squares regularization online rnoodle
fonte

1

Seus mínimos quadrados regularizados por Tikhonov são talvez mais comumente chamados Levenberg-Marquardt nos círculos estatísticos, mesmo quando aplicados a problemas lineares puros (como aqui). Há um artigo sobre o Levenberg Marquardt online aqui . Não sei se isso ajuda.

Glen_b -Reinstala Monica

11

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

Seja , então $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)$ e

$M_{n+1} - M_n = x_nx_n^T$ , podemos obter

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

De acordo com a fórmula de Woodbury , temos

$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)}$

Como um resultado,

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

A média da Polyak indica que você pode usar para aproximar com intervalos de de para . Você pode tentar, no seu caso, selecionar o melhor para sua recursão. $\eta_n = n^{-\alpha}$ $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $\alpha$ $0.5$ $1$ $\alpha$

Eu acho que também funciona se você aplicar um algoritmo de gradiente em lote:

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

lennon310
fonte

E se eu atualizar meu regressor sempre com amostras de lotes de novos dados, onde cada lote sucessivo é extraído de uma distribuição ligeiramente diferente? ou seja, não IID. Nesse caso, eu gostaria que o regressor levasse em conta os novos dados, mas não afetasse suas previsões na localidade dos dados antigos (lotes anteriores)? Você pode me indicar alguma literatura que possa parecer útil?

Rnoodle

Boa pergunta, mas desculpe atualmente, não posso dizer o quanto isso afetaria seu modelo se você ainda estivesse usando a fórmula de gradiente de lote na resposta ou aproximando aplicando o formulário da matriz diretamente: eta ^ (- alpha) * X (Y-X 'beta_n) onde X, Y são suas novas amostras de lote

lennon310 15/01

oi, parece que o coeficiente de regularização não está envolvido na fórmula de atualização recursiva? ou isso importa apenas na inicialização da inversa da matriz M?

Peng Zhao

4

Um ponto que ninguém abordou até agora é que geralmente não faz sentido manter o parâmetro de regularização constante à medida que os pontos de dados são adicionados. A razão para isso é que normalmente cresce linearmente com o número de pontos de dados, enquanto o termo de regularização não. $\lambda$ $\| X \beta -y \|^{2}$ $\| \lambda\beta \|^{2}$

Brian Borchers
fonte

Esse é um ponto interessante. Mas exatamente por que "não faz sentido"? Manter constante certamente é matematicamente válido; portanto, "não faz sentido" deve ser entendido em algum tipo de contexto estatístico. Mas que contexto? O que deu errado? Haveria algum tipo de solução fácil, como substituir as somas de quadrados por quadrados médios?

λ

$\lambda$

whuber

Substituir a soma dos quadrados por uma versão em escala (por exemplo, o erro médio quadrático) faria sentido, mas o simples uso de mínimos quadrados recursivos não fará isso.

Brian Borchers

λ

$\lambda$

λ

$\lambda$

n

$n$

λ

$\lambda$

λ

$\lambda$

N / n

$N/n$

N

$N$

3

$\hat{\beta}$

Max S.
fonte

Desde então, percebi que o SGD (talvez minibatch) é o caminho a seguir para problemas on-line como este, ou seja, atualizar aproximações de funções.

Rnoodle

1

$X$ $\lambda$

Matteo Fasiolo
fonte

0

$X^TX$ $X^Ty$ $X^TX/n$ $X^Ty/n$

$X$ $y$

X = (\begin{matrix} x_{1}^{T} \\ ⋮ \\ x_{n}^{T} \end{matrix}), y = (\begin{matrix} y_{1} \\ ⋮ \\ y_{n} \end{matrix}),

$X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}, \quad y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix},$

$X^TX/n$ $X^Ty/n$ $t$

A_{t} = (1 - \frac{1}{t}) A_{t - 1} + \frac{1}{t} x_{t} x_{t}^{T},

$A_t = \left(1 - \frac{1}{t}\right) A_{t-1} + \frac{1}{t}x_t x_t^T,$

b_{t} = (1 - \frac{1}{t}) b_{t - 1} + \frac{1}{t} x_{t} y_{t} .

$b_t = \left(1 - \frac{1}{t}\right) b_{t-1} + \frac{1}{t}x_t y_t.$

$\beta$

{\hat{β}}_{t} = (A_{t} + λ I)^{- 1} b_{t} .

$\hat\beta_t = (A_t + \lambda I)^{-1}b_t.$

$\lambda$

Este procedimento é como https://github.com/joshday/OnlineStats.jl calcula estimativas on-line de regressão linear / de crista.

joshday
fonte

Algoritmo de mínimos quadrados regularizado recursivo (online)

Respostas: