Saya menganalisis beberapa data di mana saya ingin melakukan regresi linier biasa, namun ini tidak mungkin karena saya berurusan dengan pengaturan online dengan aliran input data yang berkelanjutan (yang dengan cepat akan terlalu besar untuk memori) dan perlu untuk memperbarui perkiraan parameter saat ini sedang dikonsumsi. yaitu saya tidak bisa hanya memuat semuanya ke dalam memori dan melakukan regresi linier pada seluruh kumpulan data.
Saya mengasumsikan model regresi multivariat linier sederhana, yaitu
Apa algoritme terbaik untuk membuat estimasi pembaruan berkelanjutan dari parameter regresi linier dan ?b
Idealnya:
- Saya ingin algoritma yang paling kompleksitas ruang dan waktu per pembaruan, di mana adalah dimensi dari variabel independen ( ) dan adalah dimensi dari variabel dependen ( ).N x M y
- Saya ingin dapat menentukan beberapa parameter untuk menentukan berapa banyak parameter diperbarui oleh setiap sampel baru, misalnya 0,000001 akan berarti bahwa sampel berikutnya akan memberikan sepersejuta estimasi parameter. Ini akan memberikan semacam peluruhan eksponensial untuk efek sampel di masa lalu yang jauh.
Jawaban:
Maindonald menjelaskan metode berurutan berdasarkan rotasi Givens . (Rotasi Givens adalah transformasi ortogonal dari dua vektor yang nol dari entri yang diberikan di salah satu vektor.) Pada langkah sebelumnya Anda telah mendekomposisi matriks desain menjadi matriks segitiga melalui sebuah transformasi orthogonal sehingga . (Cepat dan mudah untuk mendapatkan hasil regresi dari matriks segitiga.) Setelah berdampingan dengan baris baru bawah , Anda secara efektif memperluas dengan baris bukan nol , juga, katakanT Q Q X = ( T , 0 ) ′ v X ( T , 0 ) ′ t T T t T T QX T Q QX=(T,0)′ v X (T,0)′ t . Tugasnya adalah nol di luar baris ini sambil menjaga entri di posisi diagonal. Urutan rotasi Givens melakukan ini: rotasi dengan baris pertama nol elemen pertama ; lalu rotasi dengan baris kedua nol elemen kedua, dan seterusnya. Efeknya adalah premultiply oleh serangkaian rotasi, yang tidak mengubah ortogonalitasnya.T T t T Q
Ketika matriks desain memiliki kolom (yang merupakan kasus ketika melakukan regresi pada variabel ditambah konstanta), jumlah rotasi yang diperlukan tidak melebihi dan setiap rotasi mengubah dua vektor . Penyimpanan yang diperlukan untuk adalah . Jadi algoritma ini memiliki biaya komputasi baik dalam waktu dan ruang.p p + 1 p + 1 T O ( ( p + 1 ) 2 ) O ( ( p + 1 ) 2 )p+1 p p+1 p+1 T O((p+1)2) O((p+1)2)
Pendekatan serupa memungkinkan Anda menentukan efek pada regresi menghapus baris. Maindonald memberikan formula; begitu juga Belsley, Kuh, & Welsh . Jadi, jika Anda mencari jendela bergerak untuk regresi, Anda bisa menyimpan data untuk jendela dalam buffer melingkar, berdampingan dengan datum baru dan menjatuhkan yang lama dengan setiap pembaruan. Ini menggandakan waktu pembaruan dan membutuhkan penyimpanan tambahan untuk jendela lebar . Tampaknya akan menjadi analog dari parameter pengaruh.k 1 / kO(k(p+1)) k 1/k
Untuk peluruhan eksponensial, saya pikir (secara spekulatif) bahwa Anda dapat mengadaptasi pendekatan ini ke kuadrat terkecil berbobot, memberi setiap nilai baru bobot lebih besar dari 1. Tidak boleh ada kebutuhan untuk mempertahankan buffer nilai sebelumnya atau menghapus data lama apa pun.
Referensi
JH Maindonald, Perhitungan Statistik. J. Wiley & Sons, 1984. Bab 4.
DA Belsley, E. Kuh, RE Welsch, Diagnostik Regresi: Mengidentifikasi Data Berpengaruh dan Sumber Collinearity. J. Wiley & Sons, 1980.
sumber
Saya pikir menyusun kembali model regresi linier Anda menjadi model state-space akan memberi Anda apa yang Anda cari. Jika Anda menggunakan R, Anda mungkin ingin menggunakan paket dlm dan melihat buku pendamping oleh Petris et al.
sumber
Anda selalu dapat hanya melakukan gradient descent pada jumlah kuadrat biaya wrt parameter model . Ambil saja gradiennya tetapi jangan gunakan solusi form tertutup tetapi hanya untuk arahan pencarian.E W
Mari menjadi biaya sampel pelatihan i'th diberikan parameter . Pembaruan Anda untuk parameter j'th adalahE(i;W) W
di mana adalah tingkat langkah, yang harus Anda pilih melalui validasi silang atau ukuran yang baik.α
Ini sangat efisien dan cara jaringan saraf biasanya dilatih. Anda dapat memproses bahkan banyak sampel secara paralel (katakanlah, 100 atau lebih) secara efisien.
Tentu saja algoritma optimasi yang lebih canggih (momentum, gradien konjugat, ...) dapat diterapkan.
sumber
Terkejut tidak ada orang lain yang menyinggung ini sejauh ini. Regresi linier memiliki fungsi tujuan kuadratik. Jadi, langkah newton Raphson dari titik awal mana pun membawa Anda langsung ke optima. Sekarang, katakanlah Anda sudah melakukan regresi linier Anda. Fungsi obyektif adalah:
Sekarang, Anda mendapatkan beberapa data sebelumnya dan melakukan regresi linier dan duduk dengan parameter Anda ( ). Gradien pada titik ini adalah nol menurut definisi. Goni seperti yang diberikan di atas. Titik data baru ( ) tiba. Anda cukup menghitung gradien untuk titik baru melalui:β xnew,ynew
Tambahkan ini ke goni tua yang diberikan di atas. Kemudian, ambil langkah Newton Raphson.
Dan kamu sudah selesai.
sumber
Standar terkecil-kuadrat memberikan koefisien regresi
Misalnya, jika M = 1, maka koefisien satu adalah
jadi setiap kali Anda mendapatkan titik data baru Anda memperbarui kedua jumlah dan menghitung rasio dan Anda mendapatkan koefisien yang diperbarui.
sumber
Masalahnya lebih mudah dipecahkan ketika Anda menulis ulang sedikit hal:
Y = y
X = [x, 1]
kemudian
Y = A * X
Solusi satu kali ditemukan dengan menghitung
V = X '* X
dan
C = X '* Y
perhatikan V harus memiliki ukuran N-by-N dan C ukuran N-by-M. Parameter yang Anda cari kemudian diberikan oleh:
A = inv (V) * C
Karena V dan C dihitung dengan menjumlahkan data Anda, Anda dapat menghitung A di setiap sampel baru. Namun, ini memiliki kompleksitas waktu O (N ^ 3).
Karena V adalah kuadrat dan semi-pasti positif, dekomposisi LU ada, yang membuat pembalikan V secara numerik lebih stabil. Ada algoritma untuk melakukan pembaruan peringkat-1 ke kebalikan dari matriks. Temukan itu dan Anda akan memiliki implementasi efisien yang Anda cari.
Algoritma pembaruan peringkat-1 dapat ditemukan di "Perhitungan matriks" oleh Golub dan van Loan. Ini bahan yang sulit, tetapi memiliki ikhtisar yang komprehensif tentang algoritma tersebut.
Catatan: Metode di atas memberikan estimasi kuadrat-terkecil pada setiap langkah. Anda dapat dengan mudah menambahkan bobot ke pembaruan ke X dan Y. Ketika nilai X dan Y tumbuh terlalu besar, mereka dapat diskalakan dengan skalar tunggal, tanpa memengaruhi hasilnya.
sumber