Mengapa derivasi saya dari solusi laso bentuk tertutup salah?

28

Masalah laso

βlasso=argminβyXβ22+αβ1
memiliki solusi bentuk tertutup:
βjlasso=sgn(βjLS)(|βjLS|α)+
jika X memiliki kolom ortonormal. Ini ditunjukkan di utas ini: Penurunan solusi bentuk laso tertutup .

Namun saya tidak mengerti mengapa tidak ada solusi formulir tertutup pada umumnya. Menggunakan subdifferensial saya memperoleh yang berikut.

( X adalah n×p Matriks)

f(β)=yXβ22+αβ1
=i=1n(yiXiβ)2+αj=1p|βj|
( Xi adalah baris ke- X dari XX )
=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|
fβj=2i=1nyiXij+2i=1nXij2βj+βj(α|βj|)
={2i=1nyiXij+2i=1nXij2βj+α for βj>02i=1nyiXij+2i=1nXij2βjα for βj<0[2i=1nyiXijα,2i=1nyiXij+α] for βj=0
Dengan fβj=0 kita dapatkan

βj={(2(i=1nyiXij)α)/2i=1nXij2for i=1nyiXij>α(2(i=1nyiXij)+α)/2i=1nXij2for i=1nyiXij<α0 for i=1nyiXij[α,α]

Adakah yang melihat kesalahan saya?

Menjawab:

Jika kita menulis masalah dalam bentuk matriks, kita dapat dengan mudah melihat mengapa solusi bentuk tertutup hanya ada dalam kasus ortonormal dengan XTX=I :

f(β)=yXβ22+αβ1
=yTy2βTXTy+βTXTXβ+αβ1
f(β)=2XTy+2XTXβ+(α|β1)
(saya telah mengambil banyak langkah sekaligus di sini. Namun, hingga titik ini sepenuhnya analog dengan derivasi dari solusi kuadrat terkecil. Jadi Anda harus dapat menemukan langkah-langkah yang hilang di sana.)
fβj=2XjTy+2(XTX)jβ+βj(α|βj|)

Dengan fβj=0 kita dapatkan

2(XTX)jβ=2XjTyβj(α|βj|)
2(XTX)jjβj=2XjTyβj(α|βj|)2i=1,ijp(XTX)jiβi

Kita dapat melihat sekarang bahwa solusi kami untuk satu bergantung pada semua yang lain sehingga tidak jelas bagaimana untuk melanjutkan dari sini. Jika adalah ortonormal, kami memiliki sehingga pasti ada solusi bentuk tertutup dalam kasus ini.βjβijX2(XTX)jβ=2(I)jβ=2βj

Terima kasih kepada Guðmundur Einarsson untuk jawabannya, yang saya uraikan di sini. Saya harap kali ini benar :-)

Norbert
sumber
3
Selamat datang di CrossValidated, dan selamat atas posting pertama yang sangat bagus!
S. Kolassa - Reinstate Monica

Jawaban:

16

Ini biasanya dilakukan dengan regresi sudut terkecil, Anda dapat menemukan makalah di sini .

Maaf tentang kebingungan saya di awal, saya akan melakukan upaya lain untuk ini.

Jadi setelah perluasan fungsi Anda Anda dapatkanf(β)

f(β)=i=1nyi22i=1nyiXiβ+i=1nβTXiTXiβ+αj=1p|βj|

Kemudian Anda menghitung turunan parsial sehubungan dengan . Perhatian saya adalah dalam perhitungan Anda tentang turunan parsial dari suku terakhir sebelum 1-norma, yaitu suku kuadrat. Mari kita periksa lebih lanjut. Kami memiliki itu:βj

Xiβ=βTXiT=(β1Xi1+β2Xi2++βpXip)
Jadi pada dasarnya Anda dapat menulis ulang istilah kuadratik Anda sebagai: Sekarang kita dapat menggunakan aturan rantai untuk menghitung turunan dari wrt ini :
i=1nβTXiTXiβ=i=1n(Xiβ)2
βj
βji=1n(Xiβ)2=i=1nβj(Xiβ)2=i=1n2(Xiβ)Xij

Jadi sekarang masalah Anda tidak disederhanakan dengan mudah, karena Anda memiliki semua koefisien ada di setiap persamaan.β

Ini tidak menjawab pertanyaan Anda tentang mengapa tidak ada solusi bentuk tertutup dari Lasso, saya mungkin menambahkan sesuatu nanti.

Gumeo
sumber
1
Terima kasih banyak. Saya sebenarnya bisa melihat sekarang mengapa tidak ada solusi form tertutup (lihat edit saya).
Norbert
Manis! Kerja bagus :)
Gumeo