Bagaimana menjalankan regresi linier secara paralel / terdistribusi untuk pengaturan data besar?

Saya sedang mengerjakan masalah regresi linier yang sangat besar, dengan ukuran data yang sangat besar sehingga harus disimpan pada sekelompok mesin. Akan terlalu besar untuk menggabungkan semua sampel ke dalam memori satu mesin (bahkan disk)

Untuk melakukan regresi data ini, saya berpikir tentang pendekatan paralel, yaitu menjalankan regresi pada setiap kotak individual, dan kemudian menghitung beta berdasarkan statistik masing-masing beta individu (mungkin rata-rata atau median)

apakah ini masuk akal? jika demikian, bagaimana saya harus mendapatkan total diharapkan $R^2$dari masing-masing individu $R^2$ ?

Jawaban singkat:

Ya, menjalankan regresi linier secara paralel telah dilakukan. Sebagai contoh, Xiangrui Meng et al. (2016) untuk Pembelajaran Mesin di Apache Spark. Cara kerjanya menggunakan stochastic gradient descent (SGD). Di bagian 3, fitur inti, penulis menyebutkan:

Model linier umum dipelajari melalui algoritma optimasi yang memparalelkan perhitungan gradien, menggunakan pustaka aljabar linier berbasis C ++ yang cepat untuk perhitungan pekerja.

Contoh tentang cara kerja SGD dapat ditemukan dalam jawaban saya di sini: Bagaimana penurunan gradien stokastik dapat menghemat waktu dibandingkan dengan penurunan gradien standar?

Jawaban panjang:

Catatan, notasi tidak konsisten dengan tautan yang saya berikan, saya merasa notasi matriks lebih baik dalam pertanyaan ini.

Untuk melakukan regresi linier, kami coba lakukan

Derivatifnya adalah

Dalam pengaturan data kecil, kita dapat mengatur turunan ke dan menyelesaikannya secara langsung. (misalnya, dekomposisi QR dalam R.) Dalam pengaturan data besar, matriks data terlalu besar untuk disimpan dalam memori, dan mungkin sulit untuk dipecahkan secara langsung. (Saya tidak terbiasa dengan cara melakukan dekomposisi QR atau dekomposisi Cholesky untuk matriks besar).$0$$X$

Salah satu cara untuk memparalelkan ini adalah dengan mencoba menggunakan metode iteratif: stochastic gradient descent, di mana kita dapat memperkirakan gradien menggunakan subset data. (Jika kita menggunakan , untuk mewakili bagian dari data, gradien dapat didekati dengan , dan kita dapat memperbarui dengan gradien yang didekati).y s 2 X T s ( X s β - y s ) $X_s$$y_s$$2X_s^T(X_s\beta-y_s)$$\beta$

Selain itu, untuk statistik , kita dapat menghitung untuk semua data secara paralel atau memperkirakannya dengan menggunakan subset data.R $R^2$$R^2$

Intuisi tentang cara kerjanya (paradigma mapreduce):

Saya terus mengatakan perkiraan menggunakan subset; intuisi mengapa ini bekerja dapat dijelaskan dalam contoh berikut: misalkan saya memiliki 100 miliar titik data dan kami ingin menghitung rata-rata semua titik data. Misalkan melakukan operasi seperti itu membutuhkan waktu yang sangat lama, dan selanjutnya seluruh data tidak dapat disimpan dalam memori.

Apa yang dapat kita lakukan adalah hanya mengambil satu bagian, katakan 1 miliar item, dan menghitung rata-rata dari semuanya. Perkiraan yang dihasilkan seharusnya tidak jauh dari kebenaran (yaitu, menggunakan seluruh data).

Untuk memparalelkan, kita dapat menggunakan 100 komputer, dengan masing-masing dari mereka mengambil subset berbeda dari 1 miliar titik data dan menghitung rata-rata dari ini. (Umumnya disebut sebagai langkah MAP). Terakhir, jalankan rata-rata lain pada 100 angka ini (alias langkah REDUCE).

Perhatikan "paradigma mapreduce" akan bekerja dengan baik dalam beberapa kasus, tetapi tidak baik dalam kasus lain. Sebagai contoh, operasi "rata-rata" yang disebutkan sebelumnya sangat mudah, karena kita tahu , ( dengan asumsi panjang dan adalah sama). Untuk beberapa metode berulang, yaitu iterasi saat ini tergantung pada hasil iterasi sebelumnya, sulit untuk diparalelkan. Stochastic gradient descent menyelesaikan masalah ini dengan memperkirakan gradien menggunakan subset data. Dan detail dapat ditemukan dalam jawaban @ user20160.x $\text{mean}(<x,y>)=\text{mean}(x)+\text{mean(y)}$$x$$y$

Referensi:

Xiangrui Meng et al. (2016) . MLlib: Pembelajaran Mesin di Apache Spark

Seperti @ hxd1011 sebutkan, satu pendekatan adalah merumuskan regresi linier sebagai masalah optimisasi, kemudian menyelesaikannya dengan menggunakan algoritma iteratif (mis. Penurunan gradien stokastik). Pendekatan ini dapat diparalelkan tetapi ada beberapa pertanyaan penting: 1) Bagaimana seharusnya masalah dipecah menjadi submasalah? 2) Mengingat algoritma pengoptimalan seperti SGD secara inheren berurutan, bagaimana seharusnya solusi untuk subproblem digabungkan untuk mendapatkan solusi global?

Zinkevich et al. (2010) menjelaskan beberapa pendekatan sebelumnya untuk memparalelkan antar beberapa mesin:

• 1) Paralelkan SGD sebagai berikut: Membagi data di beberapa mesin. Pada setiap langkah, setiap mesin lokal memperkirakan gradien menggunakan subset data. Semua perkiraan gradien diteruskan ke mesin pusat, yang menggabungkannya untuk melakukan pembaruan parameter global. Kelemahan dari pendekatan ini adalah membutuhkan komunikasi jaringan yang berat, yang mengurangi efisiensi.

• 2) Partisi data secara merata di seluruh mesin lokal. Setiap mesin menyelesaikan masalah dengan tepat untuk subset datanya sendiri, menggunakan batch solver. Estimasi parameter akhir dari mesin lokal dirata-rata untuk menghasilkan solusi global. Manfaat dari pendekatan ini adalah membutuhkan sangat sedikit komunikasi jaringan, tetapi downside adalah bahwa estimasi parameter dapat suboptimal.

Mereka mengusulkan pendekatan baru:

• 3) Izinkan setiap mesin lokal untuk menggambar titik data secara acak. Jalankan SGD di setiap mesin. Akhirnya, rata-rata parameter di seluruh mesin untuk mendapatkan solusi global. Seperti (2), metode ini membutuhkan sedikit komunikasi jaringan. Tapi, estimasi parameter lebih baik karena setiap mesin diperbolehkan mengakses sebagian besar data.

Pendekatan optimisasi paralel sangat umum, dan berlaku untuk banyak algoritma pembelajaran mesin (bukan hanya regresi linier).

Alternatif lain adalah dengan menggunakan algoritma dekomposisi matriks paralel / terdistribusi atau pemecah linear. Regresi linear kuadrat terkecil memiliki struktur khusus yang memungkinkannya diselesaikan dengan menggunakan metode dekomposisi matriks. Ini adalah bagaimana Anda biasanya akan menyelesaikannya dalam kasus kumpulan data yang lebih kecil yang sesuai dengan memori. Ini dapat diparalelkan dengan mendistribusikan blok matriks di beberapa mesin, kemudian menyelesaikan masalah menggunakan komputasi matriks paralel / terdistribusi. Mengingat bahwa pendekatan ini lebih khusus untuk menyelesaikan sistem linier, akan menarik untuk melihat bagaimana kinerjanya dibandingkan dengan pendekatan optimisasi yang lebih umum. Jika ada yang bisa memberikan informasi lebih lanjut tentang ini, saya akan senang mendengarnya.

Referensi:

Zinkevich et al. (2010) . Keturunan Gradien Stokastik Paralel.

Lama, lama, sebelum peta berkurang, saya memecahkan ini. Di bawah ini adalah rujukan pada makalah lama saya di Journal of Econometrics 1980. Itu untuk kemungkinan maksimum paralel nonlinier dan akan bekerja untuk estimasi-M.

Metode ini tepat untuk regresi. Membagi data menjadi k himpunan bagian pada k prosesor / unit (bisa dilakukan secara berurutan juga.) Apakah k regresi menjaga koefisien regresi dan matriks X'X untuk masing-masing. Sebut b1 ini, ..., bk dan W1, ..., Wk masing-masing kemudian koefisien regresi keseluruhan diberikan oleh b = terbalik (W1 + .. Wk) * (W1 * b1 + ... + Wk * bk) satu perlu melewati data untuk menghitung residu menggunakan b untuk parameter untuk mendapatkan sigma ^ 2 varians kesalahan yang diperkirakan, R ^ 2 F keseluruhan dan sejenisnya. Kemudian matriks kovarians dari b diberikan persis oleh sigma ^ 2 (kebalikan (W1 + .. + Wk)). Di atas * menunjukkan perkalian matriks.

https://www.sciencedirect.com/science/article/pii/0304407680900950