Algoritma kuadrat terkecil teratur rekursif (online)

12

Adakah yang bisa mengarahkan saya ke arah algoritma online (rekursif) untuk Regulasi Tikhonov (kuadrat terkecil yang diatur)?

Dalam pengaturan offline, saya akan menghitung $\hat\beta=(X^TX+λI)^{−1}X^TY$ menggunakan set data asli saya di mana $λ$ ditemukan menggunakan validasi silang n-fold. Nilai baru $y$ dapat diprediksi untuk diberikan $x$ menggunakan $y=x^T\hat\beta$ .

Dalam pengaturan online saya terus menggambar titik data baru. Bagaimana saya bisa memperbarui $\hat\beta$ ketika saya menggambar sampel data tambahan baru tanpa melakukan perhitungan ulang penuh pada seluruh kumpulan data (asli + baru)?

regression machine-learning least-squares regularization online rnoodle
sumber

1

Kuadrat teregulasi Tikhonov Anda mungkin lebih sering disebut Levenberg-Marquardt dalam lingkaran statistik, bahkan ketika diterapkan pada masalah linier murni (seperti di sini). Ada makalah tentang Levenberg Marquardt online di sini . Saya tidak tahu apakah itu bisa membantu.

Glen_b -Reinstate Monica

11

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

Biarkan $M_n^{-1} = (XX^T+λI)^{−1}$ , lalu

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

$M_{n+1} - M_n = x_nx_n^T$ , kita bisa dapatkan

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

Menurut rumus Woodbury , kita punya

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

Hasil dari,

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

Rata-rata Polyak menunjukkan Anda dapat menggunakan untuk mendekati dengan berkisar dari ke . Anda dapat mencoba dalam kasus Anda untuk memilih terbaik untuk rekursi Anda. $\eta_n = n^{-\alpha}$ $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ $\alpha$ $0.5$ $1$ $\alpha$

Saya pikir ini juga berfungsi jika Anda menerapkan algoritma batch gradient:

$\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
sumber

Bagaimana jika saya memperbarui regresi saya setiap kali dengan sampel batch data baru, di mana setiap batch berturut-turut diambil dari distribusi yang sedikit berbeda? yaitu non IID. Dalam hal ini saya ingin regressor mempertimbangkan data baru, tetapi tidak mempengaruhi prediksi di lokasi data lama (batch sebelumnya)? Bisakah Anda mengarahkan saya ke literatur apa pun yang mungkin Anda rasa berguna?

rnoodle

Pertanyaan yang bagus, tapi maaf saat ini saya tidak bisa memberi tahu seberapa besar itu akan memengaruhi model Anda jika Anda masih menggunakan rumus batch gradient dalam jawabannya, atau mendekati dengan menerapkan bentuk matriks secara langsung: eta ^ (- alpha) * X (Y-X 'beta_n) dengan X, Y adalah sampel batch baru Anda

lennon310

hai, sepertinya koefisien regularisasi tidak terlibat dalam formula pembaruan rekursif? atau apakah itu hanya masalah dalam inisialisasi invers dari matriks M?

Peng Zhao

4

Suatu titik yang belum pernah ditangani sejauh ini adalah bahwa secara umum tidak masuk akal untuk menjaga parameter regularisasi konstan ketika titik data ditambahkan. Alasan untuk ini adalah bahwa biasanya akan tumbuh secara linier dengan jumlah titik data, sedangkan istilah regularisasi tidak akan. $\lambda$ $\| X \beta -y \|^{2}$ $\| \lambda\beta \|^{2}$

Brian Borchers
sumber

Itu poin yang menarik. Tapi persisnya mengapa itu "tidak masuk akal"? Menjaga konstan pasti secara matematis valid, jadi "tidak masuk akal" harus dipahami dalam semacam konteks statistik. Tapi konteks apa? Apa yang salah? Apakah akan ada semacam perbaikan yang mudah, seperti mengganti jumlah kuadrat dengan kuadrat rata-rata?

λ

$\lambda$

whuber

Mengganti jumlah kuadrat dengan versi skala (misalnya kesalahan kuadrat rata-rata) akan masuk akal, tetapi hanya menggunakan kuadrat terkecil rekursif tidak akan mencapai itu.

Brian Borchers

Mengenai apa yang salah, tergantung pada pilihan Anda , Anda akan mendapatkan solusi yang sangat tidak diregulasi dengan sejumlah besar titik data atau solusi yang sangat terlalu teratur dengan sejumlah kecil titik data.

λ

$\lambda$

Brian Borchers

Orang akan menduga itu, tetapi jika disetel pada awalnya setelah menerima titik data dan kemudian lebih banyak titik data ditambahkan, apakah solusi yang dihasilkan dengan lebih banyak titik data dan yang sama kelebihan atau kekurangan regulasi akan tergantung pada yang baru titik data. Hal ini dapat dianalisis dengan asumsi datapoints bertindak seperti sampel iid dari distribusi multivariat, dalam hal ini muncul harus ditetapkan untuk pada tahap . Ini akan mengubah formula pembaruan, tetapi dengan cara yang teratur dan sederhana sehingga perhitungan yang efisien masih mungkin dilakukan. (+1)

λ

$\lambda$

n

$n$

λ

$\lambda$

λ

$\lambda$

N / n

$N/n$

N

$N$

whuber

3

Mungkin sesuatu seperti keturunan gradien Stochastic dapat bekerja di sini. Hitung menggunakan persamaan Anda di atas pada dataset awal, yang akan menjadi taksiran awal Anda. Untuk setiap titik data baru Anda dapat melakukan satu langkah penurunan gradien untuk memperbarui estimasi parameter Anda. $\hat{\beta}$

Max S.
sumber

Sejak itu saya menyadari bahwa SGD (mungkin minibatch) adalah cara untuk mengatasi masalah online seperti ini yaitu memperbarui perkiraan fungsi.

rnoodle

1

Dalam regresi linier, satu kemungkinan adalah memperbarui dekomposisi QR secara langsung, seperti yang dijelaskan di sini . Saya kira itu, kecuali jika Anda ingin menaksir ulang setelah setiap titik data baru telah ditambahkan, sesuatu yang sangat mirip dapat dilakukan dengan regresi ridge. $X$ $\lambda$

Matteo Fasiolo
sumber

0

Berikut ini adalah pendekatan alternatif (dan kurang kompleks) dibandingkan dengan menggunakan rumus Woodbury. Perhatikan bahwa dan dapat ditulis sebagai penjumlahan . Karena kita menghitung hal-hal secara online dan tidak ingin jumlahnya meledak, kita juga dapat menggunakan cara ( dan ). $X^TX$ $X^Ty$ $X^TX/n$ $X^Ty/n$

Jika Anda menulis dan sebagai: $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},$

kita dapat menulis pembaruan online ke dan (dihitung hingga baris ke- ) sebagai: $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.$

Perkiraan online Anda menjadi $\beta$

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

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

Perhatikan bahwa ini juga membantu dengan interpretasi tetap konstan saat Anda menambahkan pengamatan! $\lambda$

Prosedur ini adalah bagaimana https://github.com/joshday/OnlineStats.jl menghitung estimasi online untuk regresi linier / ridge.

joshday
sumber

Algoritma kuadrat terkecil teratur rekursif (online)

Jawaban: