Penurunan solusi bentuk laso tertutup

52

Untuk masalah laso sedemikian rupa sehingga \ | \ beta \ | _1 \ leq t . Saya sering melihat hasil soft-thresholding \ beta_j ^ {\ text {lasso}} = \ mathrm {sgn} (\ beta ^ {\ text {LS}} _ j) (| \ beta_j ^ {\ text {LS}} | - \ gamma) ^ + untuk kasus X ortonormal . Dikatakan bahwa solusinya dapat "dengan mudah ditampilkan" menjadi seperti itu, tetapi saya belum pernah melihat solusi yang berhasil. Adakah yang melihat atau mungkin telah melakukan derivasi?minβ(YXβ)T(YXβ)β1t

βjlasso=sgn(βjLS)(|βjLS|γ)+
X
Gary
sumber
Ini agak membingungkan. Pada awalnya Anda menganggap t kendala tdan dalam solusi Anda memperkenalkan parameter γ . Saya kira Anda ingin keduanya berhubungan melalui masalah ganda, tapi mungkin Anda bisa memperjelas apa yang Anda cari.
kardinal
2
Sebagian menanggapi @ cardinal, menemukan β yang meminimalkan (YXβ)(YXβ) tunduk pada β1t sama dengan menemukan β yang meminimalkan (YXβ)(YXβ)+γj|βj|. Ada hubungan 1-1 antara t dan γ . Untuk 'mudah' melihat mengapa hasil soft-thresholding begitu, saya sarankan untuk menyelesaikan ekspresi kedua (dalam komentar saya).
2
Catatan lain, ketika menemukan β yang meminimalkan (YXβ)(YXβ)+γj|βj|, pisahkan masalahnya ke dalam case \ beta_j> 0βj>0 , βj<0 , dan β=0 .
2
@ kardinal Ah ya, 1-1 salah. Koreksi: untuk setiap t0 , Anda dapat menemukan γ0 .
3
Terima kasih atas diskusi yang luar biasa! Saya menemukan video ini di coursera - Turunkan pembaruan keturunan koordinat laso , yang sangat relevan dengan diskusi ini, dan berjalan melalui solusi dengan sangat elegan. Mungkin bermanfaat bagi pengunjung masa depan :-)
zorbar

Jawaban:

64

Ini dapat diserang dengan sejumlah cara, termasuk pendekatan yang cukup ekonomis melalui kondisi Karush – Kuhn – Tucker .

Di bawah ini adalah argumen alternatif yang cukup mendasar.

Solusi kuadrat terkecil untuk desain ortogonal

Misalkan terdiri dari kolom ortogonal. Kemudian, solusi kuadrat-terkecil adalah X

β^LS=(XTX)1XTy=XTy.

Beberapa masalah setara

Melalui formulir Lagrangian, mudah untuk melihat bahwa masalah yang setara dengan yang dipertimbangkan dalam pertanyaan adalah

minβ12yXβ22+γβ1.

Memperluas istilah pertama yang kita dapatkan dan karena tidak mengandung dari variabel yang diminati, kita dapat membuangnya dan mempertimbangkan masalah lain yang setara, 12yTyyTXβ+12βTβyTy

minβ(yTXβ+12β2)+γβ1.

Memperhatikan bahwa , masalah sebelumnya dapat ditulis ulang sebagai β^LS=XTy

minβi=1pβ^iLSβi+12βi2+γ|βi|.

Fungsi obyektif kami sekarang adalah jumlah tujuan, masing-masing terkait dengan variabel terpisah , sehingga masing-masing dapat diselesaikan secara individual.βi

Seluruhnya sama dengan jumlah bagian-bagiannya

Perbaiki tertentu . Kemudian, kami ingin meminimalkan i

Li=β^iLSβi+12βi2+γ|βi|.

Jika , maka kita harus memiliki karena jika tidak kita bisa membalikkan tandanya dan mendapatkan nilai yang lebih rendah untuk fungsi tujuan. Demikian juga jika , maka kita harus memilih .β^iLS>0βi0β^iLS<0βi0

Kasus 1 : . Karena , dan membedakannya dengan dan menetapkan sama dengan nol , kami mendapatkan dan ini hanya layak jika sisi kanannya tidak negatif, jadi dalam hal ini solusi sebenarnya adalah β^iLS>0βi0

Li=β^iLSβi+12βi2+γβi,
βiβi=β^iLSγ
β^ilasso=(β^iLSγ)+=sgn(β^iLS)(|β^iLS|γ)+.

Kasus 2 : . Ini menyiratkan kita harus memiliki dan karenanya Membedakan sehubungan dengan dan pengaturan sama dengan nol, kita mendapatkan . Tetapi, sekali lagi, untuk memastikan ini layak, kita memerlukan , yang dicapai dengan mengambil β^iLS0βi0

Li=β^iLSβi+12βi2γβi.
βiβi=β^iLS+γ=sgn(β^iLS)(|β^iLS|γ)βi0
β^ilasso=sgn(β^iLS)(|β^iLS|γ)+.

Dalam kedua kasus, kami mendapatkan formulir yang diinginkan, dan kami selesai.

Komentar akhir

Perhatikan bahwa seiring meningkatnya , maka masing-masingtentu berkurang, maka demikian juga . Ketika , kami memulihkan solusi OLS, dan, untuk, kami memperoleh untuk semua .γ|β^ilasso|β^lasso1γ=0γ>maxi|β^iLS|β^ilasso=0i

kardinal
sumber
2
Lelang hebat @ kardinal!
Gary
9
+1 Seluruh babak kedua dapat diganti dengan pengamatan sederhana bahwa fungsi objektif adalah penyatuan bagian dari dua parabola cembung dengan simpul di , di mana tanda negatif diambil untuk dan sebaliknya positif. Formula hanyalah cara mewah untuk memilih simpul bawah. β12β2+(±γβ^)β±γβ^β<0
whuber
Jika memungkinkan, saya ingin melihat derivasi menggunakan kondisi optimalitas KKT. Apa cara lain untuk memperoleh hasil ini?
user1137731
5
@ Cardinal: terima kasih untuk derivasi yang bagus. Satu pengamatan. Jika saya ingat, matriks dengan kolom ortogonal tidak sama dengan matriks ortogonal (alias orthonormal). Kemudian untuk beberapa matriks diagonal (tidak perlu matriks identitas). Dengan asumsi matriks ortogonal (seperti dalam pertanyaan asli), kita memiliki dan semua tampak hebat :)XX=DDXX=I
Oleg Melnikov
@ cardinal Saya tidak mengerti mengapa Anda mengatakan "karena kalau tidak kita bisa membalik tandanya dan mendapatkan nilai yang lebih rendah untuk fungsi tujuan". Kami mengambil turunan dari fungsi objektif. Jadi bagaimana jika fungsi objektifnya lebih tinggi atau lebih rendah, siapa yang peduli. Yang kami pedulikan adalah turunannya diatur ke nol, kami peduli tentang ekstrema. Apakah itu lebih tinggi atau lebih rendah oleh konstanta tidak mempengaruhi argmin.
user13985
7

Asumsikan bahwa kovariat , kolom , juga standar sehingga . Ini hanya untuk kenyamanan nanti: tanpanya, notasi semakin berat karena hanya diagonal. Lebih jauh berasumsi bahwa . Ini adalah asumsi yang diperlukan agar hasilnya bertahan. Tentukan estimator kuadrat terkecil . Kemudian, (bentuk Lagrangian dari) estimator laso xjXRn×pXTX=IXTXnpβ^OLS=argminβyXβ22

(defn.)β^λ=argminβ12nyXβ22+λβ1(OLS is projection)=argminβ12nXβ^OLSXβ22+λβ1(XTX=I)=argminβ12nβ^OLSβ22+λβ1(algebra)=argminβ12β^OLSβ22+nλβ1(defn.)=proxnλ1(β^OLS)(takes some work)=Snλ(β^OLS),
\ end {align *} di mana adalah operator proksimal dari fungsi dan ambang lunak dengan jumlahproxffSαα.

Ini adalah derivasi yang melewatkan derivasi terperinci dari operator proksimal yang berhasil dilakukan Cardinal, tetapi, saya harap, mengklarifikasi langkah-langkah utama yang memungkinkan bentuk tertutup.

pengguna795305
sumber