Kecepatan, biaya komputasi PCA, LASSO, jaring elastis

18

Saya mencoba membandingkan kompleksitas komputasi / perkiraan kecepatan tiga kelompok metode untuk regresi linier sebagaimana dibedakan dalam Hastie et al. "Elemen Pembelajaran Statistik" (edisi kedua), Bab 3:

  1. Pilihan subset
  2. Metode penyusutan
  3. Metode menggunakan arah input yang diturunkan (PCR, PLS)

Perbandingannya bisa sangat kasar, hanya untuk memberikan beberapa ide. Saya mengumpulkan bahwa jawabannya mungkin tergantung pada dimensi masalah dan bagaimana itu cocok dengan arsitektur komputer, jadi untuk contoh konkret orang dapat mempertimbangkan ukuran sampel 500 dan 50 kandidat regressor. Saya sebagian besar tertarik pada motivasi di balik kompleksitas komputasi / perkiraan kecepatan tetapi tidak dalam berapa lama waktu yang dibutuhkan prosesor tertentu untuk contoh yang diberikan.

Richard Hardy
sumber
Saat menggunakan PCR atau PLS, jumlah komponen adalah parameter tuning (mirip dengan dalam regresi ridge). Jadi metode ini juga perlu divalidasi silang untuk menemukan jumlah komponen yang optimal. LASSO juga memiliki satu parameter regularisasi, tetapi jaring elastis memiliki dua (jaring elastis = punggungan + LASSO) sehingga validasi silang lebih mahal. Terlepas dari itu, LASSO mungkin lebih lambat untuk muat daripada semua model lain, karena tidak memiliki solusi bentuk tertutup. λ
Amoeba berkata Reinstate Monica
Terima kasih! Anda berkomentar akan membuat jawaban yang bagus jika Anda memasukkan dua perincian lagi: (1) seberapa mahal satu iterasi PCR dan PLS dibandingkan dengan satu OLS yang menjalankan regresi reguler; (2) mengkuantifikasi kecepatan LASSO lebih tepatnya untuk membuatnya sebanding dengan kecepatan regresi reguler (apakah secara polinomi, eksponensial, atau linear lebih mahal, dan mengapa).
Richard Hardy
Sayangnya, saya tidak memiliki jawaban yang siap untuk ini, terutama untuk (2). Itu sebabnya saya hanya meninggalkan komentar. +1, omong-omong, dan selamat dengan perwakilan 5k!
Amuba mengatakan Reinstate Monica
1
@amoeba, terima kasih! Saya tidak bisa berharap mencapai 5k ketika saya mulai (sangat lambat) tahun lalu. Tetapi sangat menyenangkan dan bermanfaat menjadi anggota aktif di sini di Cross Validated!
Richard Hardy
@amoeba, saya pikir saya mendapatkan kompleksitas LASSO jika algoritma LARS digunakan; Saya memperbarui posting saya sesuai. Tetapi saya tidak membaca koran LARS dengan hati-hati, jadi saya tidak sepenuhnya yakin itu benar ...
Richard Hardy

Jawaban:

5

Grup 1 :
Kompleksitas / kecepatan grup 1. tampaknya tidak terlalu sulit untuk menentukan apakah algoritma brute force digunakan (walaupun mungkin ada alternatif yang lebih efisien seperti algoritma "lompatan dan batas"). Misalnya, pemilihan subset penuh akan membutuhkan regresi agar sesuai dengan kumpulan fitur kandidat K. Kesesuaian OLS dari satu regresi linier memiliki kompleksitas O ( K 2 n ) (sesuai posting ini ) di mana n adalah ukuran sampel. Oleh karena itu, kompleksitas total brute-force seleksi bagian penuh harus O ( 2 K K 22KKO(K2n)n .O(2KK2n)

Kelompok 2 :
Kompleksitas / kecepatan kelompok 2. dibahas dalam bagian 3.8 dan 3.9 buku ini. Sebagai contoh, regresi ridge dengan penalti yang diberikan memiliki kompleksitas komputasi yang sama dengan regresi reguler. Karena λ perlu ditemukan menggunakan validasi silang, beban komputasi meningkat secara linier dalam jumlah pemisahan data yang digunakan dalam validasi silang (katakanlah, S ). Jika λ grid memiliki poin L , kompleksitas total regresi ridge dengan tuning parameter λ akan menjadi O ( L S K 2 n ) .λλSλLλO(LSK2n)
Ada beberapa pembicaraan tentang LASSO dalam buku ini, tetapi saya tidak dapat menemukan apa yang saya butuhkan. Namun, saya temukan di hlm. 443 dari Efron et al. "Least Angle Regression" (2004) bahwa kompleksitas LASSO untuk diberikan sama dengan kompleksitas OLS yang sesuai dengan regresi linier jika metode LARS digunakan. Kemudian kompleksitas total LASSO dengan tuning parameter λ akan menjadi O ( L S K 2 n ) . (Saya tidak membaca makalah itu dengan hati-hati, jadi tolong perbaiki saya jika saya salah.) Jaring elastis menggabungkan ridge dan LASSO; keduanya memiliki kompleksitas komputasi yang sama; karenanya, kompleksitas jaring elastis seharusnyaλλO(LSK2n)
mana A adalah ukuran grid dari parameter tuning α yang menyeimbangkan bobot bubungan versus LASSO.O(ALSK2n)Aα

Grup 3 :
Saya masih ketinggalan catatan tentang kompleksitas / kecepatan untuk grup 3. yang terdiri dari regresi komponen utama (PCR) dan partial least square (PLS).

Richard Hardy
sumber
2

Ini hanya untuk satu bagian dari pertanyaan 2 pada grup 3 di atas (yaitu PLS), tetapi tetap informatif: Srinivasan et al (2010, laporan teknis; lihat https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) melakukan beberapa pengukuran pada PLS menggunakan algoritma NIPALS - menyatakan bahwa kompleksitas waktu (dan ruang) dari algoritma ini menjadi O (dN) - untuk ekstraksi dan termasuk dalam model yang berbeda untuk a) deteksi manusia dalam gambar, dan b ) pengenalan wajah. Pengukuran dilakukan dengan menggunakan implementasi berbasis GPU mereka sendiri.

jf1
sumber