Apakah ada algoritma untuk menghitung "menjalankan" parameter regresi linier atau logistik?

Sebuah makalah " Menghitung varian berjalan secara akurat" di http://www.johndcook.com/standard_deviation.html menunjukkan cara menghitung rata-rata berjalan, varian, dan standar deviasi.

Apakah ada algoritma di mana parameter model regresi linier atau logistik dapat diperbarui "secara dinamis" dengan cara yang sama ketika setiap catatan pelatihan baru diberikan?

Koefisien regresi linier dari adalah dan .$y = ax + b$$a = cov(x,y)/var(x)$$b = mean(y) - a \cdot mean(x)$

Jadi yang Anda butuhkan hanyalah metode inkremental untuk menghitung . Dari nilai ini dan varians dari dan rata-rata dari kedua dan Anda dapat menghitung parameter dan . Seperti yang akan Anda lihat dalam kode pseudo yang diberikan di bawah ini, perhitungan tambahan sangat mirip dengan perhitungan inkremental dari . Ini seharusnya tidak mengejutkan karena .$cov(x,y)$$x$$y$$x$$a$$b$$cov(x,y)$$var(x)$$var(x) = cov(x,x)$

Berikut adalah kode semu yang mungkin Anda cari:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Saya menemukan pertanyaan ini ketika mencari algoritma yang setara secara bertahap menghitung regresi multi-variasi sebagai sehingga$R = (X'X)^{-1}X'Y$$XR = Y+\epsilon$

Untuk dua contoh spesifik Anda:

Regresi Linier Makalah “Regresi Linier Daring dan Penerapannya dalam Pembelajaran Penguatan Berbasis Model” oleh Alexander Strehl dan Michael Littman menjelaskan algoritma yang disebut "KWIK Regresi Linier" (lihat algoritme 1) yang memberikan perkiraan terhadap solusi regresi linier dengan menggunakan pembaruan tambahan. . Perhatikan bahwa ini tidak diatur (yaitu bukan Regresi Ridge). Saya cukup yakin bahwa metode Strehl & Littman tidak dapat diperluas ke pengaturan itu.

Regresi logistik

Utas ini memberi penjelasan tentang masalah ini. Mengutip:

Bahkan tanpa kendala regularisasi, regresi logistik adalah masalah optimisasi nonlinier. Sudah ini tidak memiliki solusi analitik, yang biasanya merupakan prasyarat untuk memperoleh solusi pembaruan. Dengan kendala regularisasi, itu menjadi masalah optimisasi terkendala. Ini memperkenalkan serangkaian komplikasi non-analitik yang sama sekali baru selain komplikasi yang sudah ada sebelumnya.

Namun ada metode online lain (atau tambahan) untuk regresi yang mungkin ingin Anda lihat, misalnya Regresi Proyeksi Tertimbang Lokal (LWPR)

Sebagai prinsip umum:

0) Anda menyimpan statistik yang cukup dan perkiraan ML saat ini

1) saat Anda mendapatkan data baru, perbarui statistik yang cukup dan taksiran

2) Ketika Anda tidak memiliki statistik yang cukup Anda harus menggunakan semua data.

3) Biasanya Anda tidak memiliki solusi bentuk tertutup; gunakan MLEs sebelumnya sebagai titik awal, gunakan beberapa metode optimasi yang mudah untuk menemukan optimal baru dari sana. Anda mungkin perlu bereksperimen sedikit untuk menemukan pendekatan mana yang membuat pengorbanan terbaik untuk jenis masalah khusus Anda.

Jika masalah Anda memiliki struktur khusus, Anda mungkin dapat memanfaatkannya.

Beberapa referensi potensial yang mungkin atau mungkin tidak memiliki nilai:

McMahan, HB dan M. Streeter (2012),
Masalah Terbuka: Batas Lebih Baik untuk Regresi Logistik Online ,
JMLR: Prosiding Workshop dan Konferensi , vol 23, 44.1-44.3

Penny, WD dan SJ Roberts (1999),
Regresi Logistik Dinamis ,
Prosiding IJCNN '99

Menambahkan ke jawaban tdc, tidak ada metode yang diketahui untuk menghitung estimasi tepat dari koefisien pada setiap titik waktu dengan hanya waktu konstan per iterasi. Namun, ada beberapa alternatif yang masuk akal dan menarik.

Model pertama yang harus dilihat adalah pengaturan pembelajaran online . Dalam pengaturan ini, dunia pertama kali mengumumkan nilai x, algoritme Anda memprediksi nilai untuk y, dunia mengumumkan nilai sebenarnya y ', dan algoritme Anda menderita kerugian l (y, y'). Untuk pengaturan ini diketahui bahwa algoritma sederhana (gradient descent dan gradient exponentiated, antara lain) mencapai penyesalan sublinear. Ini berarti bahwa ketika Anda melihat lebih banyak contoh jumlah kesalahan ekstra yang dibuat algoritma Anda (bila dibandingkan dengan prediktor linier terbaik) tidak bertambah dengan jumlah contoh. Ini berfungsi bahkan dalam pengaturan permusuhan. Ada sebuah makalah yang bagus menjelaskan satu strategi populer untuk membuktikan batasan penyesalan ini. Catatan kuliah Shai Shalev-Schwartz juga berguna.

Ada ekstensi pengaturan pembelajaran online yang disebut pengaturan bandit di mana algoritme Anda hanya diberi angka yang menunjukkan betapa salahnya (dan tidak ada pointer ke jawaban yang benar). Secara mengesankan, banyak hasil dari pembelajaran online terbawa ke pengaturan ini, kecuali di sini orang dipaksa untuk mengeksplorasi serta mengeksploitasi, yang mengarah ke segala macam tantangan menarik.

Jawaban lain menunjuk ke dunia pembelajaran mesin, dan itu jelas merupakan satu tempat di mana masalah ini telah diatasi.

Namun, pendekatan lain yang mungkin lebih sesuai dengan kebutuhan Anda adalah penggunaan faktorisasi QR dengan pembaruan peringkat rendah. Pendekatan untuk melakukan ini dan menggunakannya untuk memecahkan masalah kuadrat diberikan dalam:

Memperbarui faktorisasi QR dan masalah kuadrat terkecil oleh Hammerling dan Lucas.

Anda dapat menggunakan beberapa paket Filter Kalman standar dalam R untuk ini - sspir, dlm, kfas, dll. Saya merasa bahwa KF adalah area yang jauh lebih berkembang daripada pembelajaran online, jadi mungkin lebih praktis. Anda dapat menggunakan model untuk memungkinkan koefisien regresi Anda secara perlahan bervariasi sesuai dengan waktu dan KF akan mengestimasi ulang masing-masing langkah (dengan biaya waktu konstan) berdasarkan pada sebagian besar data terbaru. Atau, Anda dapat menetapkan mereka konstan dan KF masih akan mengestimasi ulang mereka pada setiap langkah tetapi kali ini dengan asumsi mereka konstan dan hanya memasukkan data yang diamati baru untuk menghasilkan perkiraan yang lebih baik dan lebih baik dari koefisien yang sama nilai-nilai.β t = β t -

Anda dapat merumuskan model serupa untuk regresi logistik, karena akan non-linear, Anda harus menggunakan metode penyaringan non-linear dari paket di atas - EKF atau UKF.

Ini untuk menambah jawaban @chmike.

Metode ini tampaknya mirip dengan algoritma online BP Welford untuk standar deviasi yang juga menghitung rata-rata. John Cook memberikan penjelasan yang bagus di sini . Tony Finch pada tahun 2009 menyediakan metode untuk rata-rata bergerak eksponensial dan standar deviasi:

diff := x – mean 
incr := alpha * diff 
mean := mean + incr 
variance := (1 - alpha) * (variance + diff * incr)

Mengintip jawaban yang diposting sebelumnya dan memperluasnya untuk memasukkan jendela bergerak eksponensial:

init(): 
    meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0,
    meanXY = 0, varY = 0, desiredAlpha=0.01 #additional variables for correlation

update(x,y):
    n += 1
    alpha=max(desiredAlpha,1/n) #to handle initial conditions

    dx = x - meanX
    dy = y - meanY
    dxy = (x*y) - meanXY #needed for cor

    varX += ((1-alpha)*dx*dx - varX)*alpha
    varY += ((1-alpha)*dy*dy - varY)*alpha #needed for corXY
    covXY += ((1-alpha)*dx*dy - covXY)*alpha

    #alternate method: varX = (1-alpha)*(varX+dx*dx*alpha)
    #alternate method: varY = (1-alpha)*(varY+dy*dy*alpha) #needed for corXY
    #alternate method: covXY = (1-alpha)*(covXY+dx*dy*alpha)

    meanX += dx * alpha
    meanY += dy * alpha
    meanXY += dxy  * alpha

getA(): return covXY/varX
getB(): return meanY - getA()*meanX
corXY(): return (meanXY - meanX * meanY) / ( sqrt(varX) * sqrt(varY) )

Dalam "kode" di atas ,Alpha yang diinginkan dapat diatur ke 0 dan jika demikian, kode akan beroperasi tanpa bobot eksponensial. Dapat disarankan untuk mengaturAlpha yang diinginkan ke 1 / diinginkanWindowSize seperti yang disarankan oleh Modified_moving_average untuk ukuran jendela bergerak.

Pertanyaan sampingan: dari perhitungan alternatif di atas, ada komentar yang lebih baik dari sudut pandang presisi?

Referensi:

chmike (2013) https://stats.stackexchange.com/a/79845/70282

Cook, John (nd) Secara akurat menghitung varian berjalan http://www.johndcook.com/blog/standard_deviation/

Finch, Tony. (2009) Kalkulasi tambahan dari rata-rata tertimbang dan varians. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Wikipedia. (nd) Algoritme online Welford https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm