Parameter regularisasi LASSO dari algoritma LARS

9

Dalam makalah seminal mereka 'Least Angle Regression' , Efron dkk menjelaskan modifikasi sederhana dari algoritma LARS yang memungkinkan untuk menghitung jalur regularisasi LASSO penuh.

Saya telah mengimplementasikan varian ini dengan sukses dan biasanya memplot jalur output baik terhadap jumlah langkah (iterasi berurutan dari algoritma LARS) atau -norm dari koefisien regresi ( ).l1β1

Namun, sepertinya sebagian besar paket yang tersedia di luar sana menyediakan jalur regularisasi dalam hal koefisien hukuman LASSO λ (misalnya LARS dalam R, di mana Anda dapat bermain dengan argumen 'mode' untuk beralih di antara representasi yang berbeda).

Pertanyaan saya adalah: apa mekanisme yang digunakan untuk beralih dari satu representasi ke yang lain (s). Saya telah melihat berbagai pertanyaan terkait dengan itu (atau lebih khusus masalah pemetaan kendala ketimpangan β1t ke istilah hukuman yang sesuai λβ1 ), tetapi tidak menemukan jawaban yang memuaskan.


[Sunting]

Saya telah melihat ke dalam beberapa kode MATLAB yang melakukan transformasi yang diperlukan dan, untuk setiap langkah LARS k , ini adalah bagaimana λ tampaknya dikomputasi:

λ(k)=max(2|XTy|),   for k=1
λ(k)=median(2|XAkTrAk|),   k>1

di mana X (ukuran n×p ) dan y (ukuran n×1 ) menunjukkan input / respons terstandarisasi, Ak mewakili set prediktor aktif pada langkah k dan r menunjukkan sisa regresi saat ini pada langkah k .

Saya tidak bisa memahami logika di balik perhitungan itu. Bisakah seseorang membantu?

Jumlah
sumber

Jawaban:

4

Saya telah menemukan cara untuk melakukan konversi yang diperlukan.

Asumsikan bahwa input distandarisasi (rata-rata nol, varian unit) dan respons terpusat.Xy

Kita tahu bahwa algoritma LARS yang dimodifikasi menyediakan jalur regularisasi penuh LASSO, lih. makalah asli oleh Efron et al .

Ini berarti bahwa, pada setiap iterasi , algoritma sebelumnya menemukan pasangan optimal meminimalkan fungsi kerugian yang diatur: k(β,λ)

(β,λ)=argmin(β,λ)L(β,λ)L(β,λ)=yXβ22+λβ1=i=1N(yij=1pβjXij)2+λj=1p|βj|

Untuk semua komponen aktif di set aktif pada akhir langkah , menerapkan kondisi stasioneritas KKT memberi a={1,...,q}Akk

0=Lβa(β,λ)=2i=1NXia(yij=1qβjXij)+λ sign(βa)

Dengan kata lain atau dalam notasi matriks (mencatat bahwa membagi / mengalikan dengan adalah sama) persamaan berikut ini terpenuhi untuk setiap komponen aktif :

λ=2i=1NXia(yij=1qβjXij)sign(βa)
sign(x)a
λ=2 sign(βa)XaTr

Dalam makalah asli, penulis menyebutkan bahwa untuk setiap solusi untuk masalah LASSO, tanda bobot regresi aktif ( ) harus identik dengan tanda korelasi prediktor aktif yang sesuai dengan sisa regresi saat ini ( ), yang hanya logika karena harus positif. Jadi kita juga bisa menulis:βaXaTrλ

λ=2|XaTr|

Selain itu, kita melihat bahwa pada langkah terakhir (kecocokan OLS, ), kita mendapatkan karena lemma ortogonal. Penggunaan median dalam implementasi MATLAB yang saya temukan IMHO sepertinya merupakan upaya untuk 'rata-rata' kesalahan numerik atas semua komponen aktif:kβ=(XTX)1XTyλ=0

λ=median(2|XAkTrAk|),   k>1

Untuk menghitung nilai ketika tidak ada komponen aktif (langkah ), seseorang dapat menggunakan trik yang sama seperti di atas tetapi dalam batas sangat kecil di mana semua bobot regresi adalah nol dan hanya tanda komponen pertama yang menjadi aktif (pada langkah ) penting. Ini menghasilkan:λk=1bk=2

λ=2 sign(βb)XbTy
yang secara ketat setara dengan

λ=max(2|XTy|), for k=1

karena (i) komentar yang sama seperti sebelumnya tentang tanda bobot regresi; (ii) algoritma LARS menentukan komponen berikutnya untuk memasuki set aktif sebagai komponen yang paling berkorelasi dengan residu saat ini , yang pada langkah hanyalah .bk=1y

Jumlah
sumber
2
Ini adalah sesuatu yang disebutkan dalam setiap karya LASSO namun tidak ada yang peduli untuk menjelaskannya (saya tidak tahu apakah itu sangat mendasar atau apa, tapi saya butuh banyak waktu untuk mengetahuinya). Saya hanya ingin menekankan bahwa, meskipun "setara", Anda hanya dapat beralih dari satu formulasi ke formulasi lainnya (dibatasi menjadi tidak dibatasi dan sebaliknya) setelah Anda menyelesaikan masalah optimisasi dan Anda memiliki bobot optimal.
skd
2
Saya merasakan hal yang sama! Sejauh menyangkut komentar Anda, ya memang. Di sini, ini tercermin dalam sisa , yang hanya dapat dihitung begitu bobot regresi optimal telah diperoleh pada akhir langkah . rAkβkk
Quantuple