Apa yang menyebabkan laso menjadi tidak stabil untuk pemilihan fitur?

12

Dalam penginderaan terkompresi, ada jaminan teorema bahwa memiliki solusi jarang yang unik c (Lihat lampiran untuk detail lebih lanjut).

argminc1subject to y=Xc
c

Apakah ada teorema yang serupa untuk laso? Jika ada teorema seperti itu, tidak hanya akan menjamin stabilitas laso, tetapi juga akan memberikan laso dengan interpretasi yang lebih bermakna:

laso dapat mengungkap vektor koefisien regresi jarang c yang digunakan untuk menghasilkan respon y oleh y=Xc .

Ada dua alasan mengapa saya mengajukan pertanyaan ini:

  1. Saya pikir 'laso nikmat solusi jarang' bukan jawaban mengapa menggunakan laso untuk pemilihan fitur karena kita bahkan tidak tahu apa kelebihan fitur yang kita pilih.

  2. Saya belajar laso terkenal karena tidak stabil untuk pemilihan fitur. Dalam praktiknya, kita harus menjalankan sampel bootstrap untuk mengevaluasi stabilitasnya. Apa alasan paling penting yang menyebabkan ketidakstabilan ini?


Lampiran:

Diberikan XN×M=(x1,,xM) . c adalah vektor Ω sparse ( ΩM ). Proses y=Xc menghasilkan respons y . Jika X memiliki NSP (null space property) of order Ω dan matriks kovarians X tidak memiliki nilai eigen mendekati nol, akan ada solusi unik untuk

argminc1subject to y=Xc
yang persis c yang memberi y .

Teorema ini juga mengatakan juga jika tidak memiliki NSP of order , tidak ada harapan untuk menyelesaikan .XΩargminc:y=Xcc1


EDIT:

Setelah menerima jawaban yang luar biasa ini, saya menyadari bahwa saya bingung ketika mengajukan pertanyaan ini.

Mengapa pertanyaan ini membingungkan:

Saya membaca makalah penelitian di mana kita harus memutuskan berapa banyak fitur (kolom) yang akan dimiliki matriks desain (fitur tambahan dibuat dari fitur utama). Karena ini adalah masalah khas , diharapkan dibangun dengan baik sehingga solusi untuk laso dapat menjadi pendekatan yang baik dari solusi jarang nyata.XN×Mn<pD

Alasannya dibuat dari teorema yang saya sebutkan dalam lampiran: Jika kita bertujuan untuk menemukan solusi ombak , lebih baik memiliki NSP of order .ΩcXΩ

Untuk matriks , jika dilanggar, makaN×MN>CΩlnM

tidak ada yang stabil dan pemulihan yang kuat dari dari dan adalah mungkincDP

D berkorespondensi dengan , berkorespondensi denganXPy

... seperti yang diharapkan dari hubungan , pemilihan deskriptor menjadi lebih tidak stabil, yaitu, untuk set pelatihan yang berbeda, deskriptor yang dipilih sering berbeda ...N=CΩlnM

Kutipan kedua adalah bagian yang membingungkan saya. Tampak bagi saya ketika ketimpangan dilanggar itu bukan hanya solusi mungkin non-unik (tidak disebutkan), tetapi deskriptor juga akan menjadi lebih tidak stabil.

meTchaikovsky
sumber
2
Hanya untuk konteksnya, masalah optimisasi yang Anda tulis di awal Q Anda disebut "basis pengejaran". Jika Anda mengganti kesetaraan dengan perkiraan kesetaraan (hingga beberapa kesalahan L2) maka itu disebut "basis pengejaran denoising". Pengejaran dasar denoising secara matematis setara dengan laso. y=XcyXc
Amuba mengatakan Reinstate Monica
Satu set slide yang bermanfaat (tapi bukan yang mudah) ditemukan di sini: pages.iu.edu/~dajmcdon/research/talks/lasso.pdf dan teorema makan siang gratis users.ece.utexas.edu/~cmcaram/pubs/ XuCaramanisMannor.NFL.pdf
Xavier Bourret Sicotte
Teorema yang Anda kutip adalah tentang keunikan. Pertanyaan Anda membingungkan karena keunikan belum tentu terkait dengan stabilitas.
Amuba mengatakan Reinstate Monica
2
Ya saya percaya OP agak bingung dan pertanyaannya tidak jelas, maka kemungkinan jawaban berbeda ... Keunikan adalah untuk satu set titik data, stabilitas berlaku untuk validasi silang, atau bootstrap, atau titik data baru
Xavier Bourret Sicotte

Jawaban:

7

MEMPERBARUI

Lihat posting kedua ini untuk umpan balik McDonald's pada jawaban saya di mana gagasan tentang konsistensi risiko terkait dengan stabilitas.


1) Keunikan vs Stabilitas

Pertanyaan Anda sulit dijawab karena menyebutkan dua topik yang sangat berbeda: keunikan dan stabilitas .

  • Secara intuitif, suatu solusi adalah unik jika diberi set data tetap, algoritma selalu menghasilkan hasil yang sama. Jawaban Martin mencakup hal ini dengan sangat rinci.

  • Stabilitas di sisi lain dapat dipahami secara intuitif sebagai prediksi yang tidak banyak berubah ketika data pelatihan sedikit dimodifikasi.

Stabilitas berlaku untuk pertanyaan Anda karena pemilihan fitur Lasso (sering) dilakukan melalui Validasi Silang, oleh karena itu algoritma Lasso dilakukan pada lipatan data yang berbeda dan dapat menghasilkan hasil yang berbeda setiap kali.

Stabilitas dan Teorema Tanpa Makan Siang Gratis

Menggunakan definisi dari sini jika kita mendefinisikan stabilitas Seragam sebagai:

Algoritma memiliki stabilitas seragam sehubungan dengan fungsi kerugian jika yang berikut ini berlaku:βV

SZm  i{1,...,m},  sup|>V(fs,z)V(fS|i,z)|  β

Dianggap sebagai fungsi , istilah dapat ditulis sebagai . Kami mengatakan algoritma ini stabil ketika berkurang sebagai .mββmβm1m

maka "No Free Lunch Theorem, Xu and Caramis (2012)" menyatakan hal itu

Jika suatu algoritma jarang , dalam arti bahwa itu mengidentifikasi fitur yang berlebihan, maka algoritma itu tidak stabil (dan batas stabilitas seragam tidak pergi ke nol). [...] Jika suatu algoritma stabil, maka tidak ada harapan bahwa itu akan jarang. (halaman 3 dan 4)β

Misalnya, regresi teratur stabil dan tidak mengidentifikasi fitur yang berlebihan, sedangkan regresi reguler (Lasso) tidak stabil. L2L1

Upaya menjawab pertanyaan Anda

Saya pikir 'laso nikmat solusi jarang' bukan jawaban mengapa menggunakan laso untuk pemilihan fitur

  • Saya tidak setuju, alasan Lasso digunakan untuk pemilihan fitur adalah karena ia menghasilkan solusi yang jarang dan dapat ditunjukkan memiliki properti IRF, yaitu Mengidentifikasi Fitur yang Berlebihan.

Apa alasan paling penting yang menyebabkan ketidakstabilan ini

  • Teorema Makan Siang Gratis

Melangkah lebih jauh

Ini bukan untuk mengatakan bahwa kombinasi Cross Validation dan Lasso tidak berfungsi ... pada kenyataannya telah ditunjukkan secara eksperimental (dan dengan banyak teori pendukung) untuk bekerja dengan sangat baik dalam berbagai kondisi. Kata kunci utama di sini adalah konsistensi , risiko, ketidaksetaraan nubuat dll.

Slide dan kertas berikut oleh McDonald dan Homrighausen (2013) menggambarkan beberapa kondisi di mana pemilihan fitur Lasso berfungsi dengan baik: slide dan kertas: " Lasso , kegigihan, dan validasi silang, McDonald dan Homrighausen (2013)" . Tibshirani sendiri juga memposting serangkaian catatan tentang sparcity , regresi linier

Berbagai kondisi untuk konsistensi dan dampaknya pada Lasso adalah topik penelitian aktif dan jelas bukan pertanyaan sepele. Saya dapat mengarahkan Anda ke beberapa makalah penelitian yang relevan:

Xavier Bourret Sicotte
sumber
1
Terima kasih atas jawaban komprehensif Anda! Set slide yang Anda berikan sangat bagus!
meTchaikovsky
1
Saya masih mencoba memproses definisi stabilitas ini. Terjemahan saya adalah bahwa "suatu algoritma stabil jika perubahan fungsi kesalahan / kehilangan di biarkan satu validasi silang memiliki batas atas yang berkurang sebagai " ketika kita menambah jumlah lipatan / set-tes "β1m , saya harap saya mendapatkan yang benar. Saya bertanya-tanya mengapa itu adalah properti yang diinginkan untuk membuat laso bekerja dengan baik (atau lebih tepatnya saya bertanya-tanya apakah itu adalah properti yang diperlukan).
Sextus Empiricus
1
Ya, kecuali m adalah jumlah titik data. lihat di sini halaman 7 untuk batas probabilistik: math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf - intinya adalah bahwa tidak ada batasan pada kemampuan yang disediakan dengan meningkatkan ukuran kumpulan data, yang berarti algoritma dapat melompat untuk fungsi hipotesis jauh tergantung pada set data tertentu. Inilah sebabnya mengapa kondisi alternatif diusulkan, yang berhubungan dengan distribusi dan struktur korelasi yang mendasarinya (saya pikir) - tetapi akan membutuhkan bantuan untuk membuatnya lebih jelas
Xavier Bourret Sicotte
Gagasan penting lainnya adalah konsistensi seperti yang dijelaskan di sini sebagai contoh: stat.ethz.ch/~nicolai/stability.pdf - bagaimana stabilitas dan konsistensi terkait tidak jelas tetapi tampaknya menjadi subjek penelitian aktif misalnya cbcl.mit.edu/publications /ps/mukherjee-AImemoOctNov.pdf
Xavier Bourret Sicotte
Jawaban bagus! Bisakah Anda juga memperbarui beberapa tautan dengan deskripsi yang lebih rinci seandainya tautan itu sendiri mati di masa mendatang? (Saya sudah melakukan satu untuk Anda.)
Richard Hardy
7

Komentar dari Daniel J. McDonald

Asisten profesor di Indiana University Bloomington, penulis dua makalah yang disebutkan dalam tanggapan asli dari Xavier Bourret Sicotte .

Penjelasan Anda, secara umum, cukup benar. Beberapa hal yang akan saya tunjukkan:

  1. Tujuan kami dalam serangkaian makalah tentang CV dan laso adalah untuk membuktikan bahwa "Lasso + Cross Validation (CV)" tidak sebaik "Lasso + optimal "λ . Secara khusus, kami ingin menunjukkan bahwa prediksi juga baik (model-free). Untuk membuat pernyataan tentang pemulihan koefisien yang benar (menemukan yang non-sparse yang tepat), kita perlu mengasumsikan kebenaran yang jarang, yang tidak ingin kita lakukan.

  2. Stabilitas algoritmik menyiratkan konsistensi risiko (pertama kali dibuktikan oleh Bousquet dan Elisseeff, saya percaya). Dengan konsistensi risiko, maksud saya bahwapergi ke nol di mana f adalah atau prediktor terbaik dalam beberapa kelas jika kelas tersebut tidak ditentukan dengan benar. Namun ini hanya kondisi yang cukup. Disebutkan pada slide yang Anda tautkan sebagai “teknik pembuktian yang mungkin tidak akan berhasil, karena laso tidak stabil”.||f^(X)f(X)||E[Y|X]

  3. Stabilitas hanya cukup tetapi tidak perlu. Kami dapat menunjukkan, bahwa dalam beberapa kondisi, "laso + CV" memprediksi serta "laso + optimal ". Makalah yang Anda kutip memberikan asumsi terlemah yang mungkin (yang ada di slide 16, yang memungkinkan ), tetapi menggunakan bentuk laso yang dibatasi daripada versi Lagrangian yang lebih umum. Makalah lain ( http://www3.stat.sinica.edu.tw/statistica/J27N3/J27N34/J27N34.html ) menggunakan versi Lagrangian. Ini juga menunjukkan bahwa di bawah kondisi yang lebih kuat, pemilihan model juga akan berfungsi. Makalah yang lebih baru ( https://arxiv.org/abs/1605.02214 ) oleh orang lain mengklaim untuk meningkatkan hasil ini (saya belum membacanya dengan cermat).λp>n

  4. Secara umum, karena laso (atau algoritma pemilihan apa pun) tidak stabil, kita perlu analisis yang lebih cermat dan / atau asumsi yang kuat untuk menunjukkan bahwa "algoritma + CV" akan memilih model yang benar. Saya tidak mengetahui kondisi yang diperlukan, meskipun ini umumnya sangat menarik. Tidak terlalu sulit untuk menunjukkan bahwa untuk lambda tetap, prediktor laso secara lokal Lipschitz dalam vektor (saya percaya bahwa satu atau lebih makalah Ryan Tibshirani melakukan ini). Jika orang juga bisa berpendapat bahwa ini berlaku di , ini akan sangat menarik, dan relevan di sini.YXi

Hasil utama yang akan saya tambahkan ke respons Anda: "stabilitas" menyiratkan "risiko-konsistensi" atau "akurasi prediksi". Hal ini juga dapat menyiratkan "konsistensi estimasi parameter" di bawah asumsi yang lebih banyak. Tetapi teorema tanpa makan siang gratis berarti "seleksi" "not stable". Lasso tidak stabil bahkan dengan fixed lambda. Karena itu tentu saja tidak stabil ketika dikombinasikan dengan CV (dari jenis apa pun) .Namun, terlepas dari kurangnya stabilitas, ia masih konsisten dengan risiko dan seleksi konsisten dengan atau tanpa CV. Keunikan tidak penting di sini.

Xavier Bourret Sicotte
sumber
5

Lasso, tidak seperti regresi Ridge (lihat misalnya Hoerl dan Kennard, 1970; Hastie et al., 2009) tidak selalu memiliki solusi yang unik, meskipun biasanya memiliki. Itu tergantung pada jumlah parameter dalam model, apakah variabelnya kontinu atau diskrit, dan pangkat matriks desain Anda. Kondisi untuk keunikan dapat ditemukan di Tibshirani (2013).

Referensi:

Hastie, T., Tibshirani, R., dan Friedman, J. (2009). Unsur-unsur pembelajaran statistik . Seri springer dalam statistik. Springer, New York, cetakan ke-11, edisi ke-2.

Hoerl, AE, dan Kennard, RW (1970). Regresi punggungan: Estimasi bias untuk masalah-masalah nonorthogonal Technometrics , 12 (1), 55-67.

Tibshirani, RJ (2013). Masalah laso dan keunikan. Jurnal Elektronik Statistik , 7, 1456-1490.

Phil
sumber
@ Terima kasih! Bisakah Anda menambahkan ringkasan singkat dari referensi yang Anda berikan?
meTchaikovsky
Hasite et al. (2009) adalah buku yang mencakup banyak topik, regresi Lasso dan Ridge di antara mereka. Ini layak dibaca dan dapat diunduh dari beranda Hastie: web.stanford.edu/ ~astie / ElemStatLearn / download.html Hoerl & Kennard (1970) adalah referensi regresi Ridge klasik dan kemungkinan tidak relevan untuk pertanyaan Anda secara langsung, lainnya daripada membaca tentang Regresi Ridge. Tibshirani (2013) berisi informasi tentang kapan Lasso memiliki solusi unik (dan ketika ia memiliki sejumlah solusi tak terbatas).
Phil
3

Apa yang menyebabkan non-keunikan.

Untuk vektor (di mana adalah tanda yang menunjukkan apakah perubahan akan meningkat atau menurun ), setiap kali mereka bergantung erat:sixisicic1

αisixi=0andαi=0

lalu ada kombinasi tak terhingga yang tidak mengubah solusi dan norma .ci+γαiXcc1

Sebagai contoh:

y=[11]=[210111][c1c2c3]=Xc

miliki untuk solusinya:c1=1

[c1c2c3]=[010]+γ[121]

dengan0γ12

Kita dapat mengurutkan menggantikan vektor dengan menggunakanx2x2=0.5x1+0.5x3


Situasi tanpa kondisi ini

Dalam artikel dari Tibshirani (dari jawaban Phil) tiga kondisi yang cukup dijelaskan untuk laso untuk memiliki solusi yang unik.

  1. Independen linier Ketika ruang nol adalah nol atau setara ketika peringkat sama dengan jumlah kolom (M). Dalam hal ini Anda tidak memiliki kombinasi linier seperti di atas.XX
  2. Cukup independen Ketika kolom berada pada posisi umum.Xs

    Artinya, tidak ada kolom mewakili titik dalam bidang dimensi. Bidang k-2 dimensi dapat diparameterisasi dengan titik apa pun sebagai dengan . Dengan titik -th di bidang yang sama ini Anda akan memiliki kondisi dengankk2k1αisixiαi=1ksjxjαisixiαi=0

    Perhatikan bahwa pada contoh kolom , dan berada pada satu baris. (Namun agak canggung di sini karena tanda-tanda bisa negatif, misalnya matriks baru saja juga tidak ada solusi unik)x1x2x3[[21][11][01]]

  3. Ketika kolom berasal dari distribusi kontinu maka tidak mungkin (probabilitas hampir nol) bahwa Anda akan memiliki kolom tidak pada posisi umum.XX

    Berbeda dengan ini, jika kolom adalah variabel kategori maka probabilitas ini tidak selalu hampir nol. Probabilitas untuk variabel kontinu sama dengan beberapa himpunan bilangan (yaitu bidang yang sesuai dengan rentang afin dari vektor lain) adalah 'hampir' nol. Tapi, ini bukan kasus untuk variabel diskrit.X

Sextus Empiricus
sumber
+1 tetapi saya pikir apa yang dimaksud dengan tidak stabil dalam diskusi baru-baru ini terkait dengan pemilihan fitur melalui validasi silang di hadapan fitur yang berkorelasi
Xavier Bourret Sicotte
@XavierBourretSicotte maksud Anda bahwa meskipun ada solusi unik, proses seleksi dapat menjadi tidak stabil karena fitur berkorelasi menambah masalah (secara numerik) menemukan solusi unik tersebut? Agak membingungkan karena pertanyaan di satu sisi tentang stabilitas dan di sisi lain tentang keunikan.
Sextus Empiricus
Ya itulah yang saya maksud, tidak harus karena ketidakstabilan numerik tetapi karena perbedaan inheren dalam lipatan data (selama CV) yang mengarah pada solusi berbeda untuk nilai berbeda di seluruh lipatan. Di bisa lebih buruk lagi ketika bootstrapλ
Xavier Bourret Sicotte
@XavierBourretSicotte Saat ini saya tidak memiliki gambaran intuitif yang jelas mengapa ini (solusi berbeda untuk dan set pelatihan yang berbeda) seharusnya tidak stabil. Saya kira Anda dapat memposting ini sebagai jawaban dan menjelaskannya. λ
Sextus Empiricus
@Martijn Weterings Terima kasih! Saya masih memiliki tiga pertanyaan: 1. bagaimana cara saya mendeteksi ketergantungan yang kuat? Haruskah saya mencari tahu apakah bersifat independen ( math.stackexchange.com/q/82189 )? 2. bagaimana saya harus menentukan dalam praktek? 3. apa yang dimaksud dengan 'posisi umum' ? {v1v0,v2v0,,vkv0}siX
meTchaikovsky