Mengapa norma L1 untuk model jarang

97

Saya membaca buku-buku tentang regresi linier. Ada beberapa kalimat tentang norma L1 dan L2. Saya tahu mereka, hanya tidak mengerti mengapa norma L1 untuk model jarang. Bisakah seseorang menggunakan memberikan penjelasan sederhana?

Yongwei Xing
sumber
4
Pada dasarnya, sparsity diinduksi oleh tepi tajam yang terletak pada poros permukaan isosur. Penjelasan grafis terbaik yang saya temukan sejauh ini ada di video ini: youtube.com/watch?v=sO4ZirJh9ds
felipeduque
1
Ada artikel blog di chioka.in/… yang
prashanth
Periksa posting Medium berikut. Mungkin membantu medium.com/@vamsi149/…
solver149

Jawaban:

111

Pertimbangkan vektor mana ε > 0 kecil. The l 1 dan l 2 norma-norma x , masing-masing, diberikan olehx=(1,ε)R2ε>0l1l2x

||x||1=1+ε,  ||x||22=1+ε2

Sekarang katakan bahwa, sebagai bagian dari beberapa prosedur regularisasi, kita akan mengurangi besarnya salah satu elemen oleh δ ε . Jika kita mengubah x 1 ke 1 - δ , norma yang dihasilkan adalahxδεx11δ

||x(δ,0)||1=1δ+ε,  ||x(δ,0)||22=12δ+δ2+ε2

Di sisi lain, mengurangi oleh δ memberikan normax2δ

||x(0,δ)||1=1δ+ε,  ||x(0,δ)||22=12εδ+δ2+ε2

Hal yang perlu diperhatikan di sini adalah bahwa, untuk penalti, regularizing jangka yang lebih besar x 1 hasil dalam pengurangan lebih besar dalam norma daripada melakukannya dengan istilah yang lebih kecil x 20 . Untuk l 1 penalti, namun, pengurangan adalah sama. Jadi, ketika menghukum model menggunakan l 2 norma, sangat tidak mungkin bahwa apa pun akan pernah diatur ke nol, karena penurunan l 2 norma pergi dari ε ke 0 hampir tidak ada ketika ε kecil. Di sisi lain, pengurangan l 1l2x1x20l1l2l2ε0εl1norma selalu sama dengan , terlepas dari jumlah yang dihukum.δ

Cara lain untuk memikirkannya: bukan hanya hukuman mendorong sparsity, tetapi hukuman l 2 dalam beberapa hal mencegah kekecilan dengan menghasilkan pengembalian yang semakin berkurang ketika elemen-elemen bergerak mendekati nol.l1l2

bnaul
sumber
3
Terima kasih atas jawaban anda! Tapi saya tidak yakin dengan poin terakhir. Jika Anda menjalankan regresi linier tanpa sanksi, Anda hampir tidak akan pernah mendapatkan solusi yang jarang (sedangkan menambahkan penalti L1 sering memberi Anda sparsity). Jadi hukuman L1 sebenarnya mendorong sparsity dengan mengirimkan koefisien yang mulai mendekati nol hingga nol.
Stefan Taruhan
2
l1lαα1l0
1
Ya - itu benar. Ada banyak norma yang mengarah ke sparsity (misalnya, seperti yang Anda sebutkan, norma Lp dengan p <= 1). Secara umum, norma apa pun dengan sudut tajam di nol menyebabkan sparsity. Jadi, kembali ke pertanyaan awal - norma L1 menginduksi sparsity dengan memiliki gradien diskontinyu pada nol (dan hukuman lain dengan properti ini akan melakukannya juga).
Stefan Taruhan
3
Jika ada yang ingin membaca lebih lanjut, ada literatur aktif tentang fungsi penalti non-cembung yang merupakan alternatif dari norma L1 (misalnya, baru-baru ini, papers.nips.cc/paper/… ).
Stefan Taruhan
1
jawaban yang bagus saya telah bertanya-tanya di sekitar untuk sementara waktu sampai saya menemukan ini.
Hady Elsahar
73

Dengan model yang jarang, kami memikirkan model di mana banyak bobotnya adalah 0. Karena itu, mari kita beralasan tentang bagaimana L1-regularisasi lebih mungkin menciptakan 0-weight.

(w1,w2,,wm)

L1(w)Σi|wi|

L2(w)12Σiwi2

η

dL1(w)dw=sign(w)sign(w)=(w1|w1|,w2|w2|,,wm|wm|)

dL2(w)dw=w

Jika kita memplot fungsi kerugian dan turunannya untuk model yang hanya terdiri dari satu parameter, sepertinya ini untuk L1:

masukkan deskripsi gambar di sini

Dan seperti ini untuk L2:

masukkan deskripsi gambar di sini

L1w1=0L2

w1=5η=12w1:=w1ηdL1(w)dw=w1121w1=0

masukkan deskripsi gambar di sini

η=12w1w1:=w1ηdL2(w)dw=w112w1

masukkan deskripsi gambar di sini

η

Kent Munthe Caspersen
sumber
3
η=0.5
wfirst step=0.10.5(+1)=>w=0.4
wsecondstep=0.40.5(1)=0.1.
5
@AlexYashin yang benar - jika kita hanya memperbarui bobot berdasarkan regularisasi L1, kita mungkin berakhir memiliki bobot yang berosilasi di dekat 0. Tapi kita tidak pernah menggunakan regularisasi sendirian untuk menyesuaikan bobot. Kami menggunakan regularisasi dalam kombinasi dengan mengoptimalkan fungsi kerugian. Dengan cara itu, regularisasi mendorong bobot ke nol sementara kami pada saat yang sama mencoba mendorong bobot ke nilai yang mengoptimalkan prediksi. Aspek kedua adalah tingkat pembelajaran. Dengan tingkat belajar yang lebih kecil, kita bisa mendekati nilai yang mungkin membuat regularisasi terombang-ambing sehingga kita bisa mengabaikannya
Kent Munthe Caspersen
1
Mengapa dL2(w)/dw'modul' dan bukan hanya linier?
mrgloom
1
@ mrgloom dL2(w)/dwdapat dibaca sebagai perubahan L2(w)per perubahan berat. Karena L2-regularisasi mengkuadratkan bobot, L2(w)akan berubah lebih banyak untuk perubahan bobot yang sama ketika kita memiliki bobot yang lebih tinggi. Inilah sebabnya mengapa fungsinya cembung saat Anda memplotnya. Namun untuk L1, perubahan L1(w)per perubahan bobot adalah sama terlepas dari apa bobot Anda - ini mengarah ke fungsi linier.
Kent Munthe Caspersen
1
@KentMuntheCaspersen Penjelasan luar biasa! Terima kasih atas grafik dan upaya yang Anda investasikan untuk menjadikan ini intuitif!
layser
15

Gambar 3.11 dari Elemen Pembelajaran Statistik oleh Hastie, Tibshirani, dan Friedman sangat ilustratif:masukkan deskripsi gambar di sini

β^β1β2β^L1L2) regresi masing-masing. Secara heuristik, untuk setiap metode, kami mencari persimpangan elips merah dan wilayah biru karena tujuannya adalah untuk meminimalkan fungsi kesalahan sambil mempertahankan kelayakan.

L1

Zhanxiong
sumber
16
Ilustrasi ini tidak terlalu meyakinkan tanpa informasi tambahan. Misalnya mengapa kontur kesalahan harus ditempatkan di tempat mereka pada gambar?
wabbit
@HrishikeshGanu Akhirnya punya waktu untuk mengedit posting.
Zhanxiong
Semua kontur akan memiliki bentuk yang sama ...
kjetil b halvorsen
1
β^β1β2β1=β2
13

β^β^1(β^)<t2(β^)<t

11{x:1(x)1}

Secara lebih umum, buku ini adalah referensi yang bagus untuk subjek ini: penjelasan yang bagus dan ilustrasi yang bagus.

Elvis
sumber
3
Saya pikir paragraf kedua Anda adalah kunci ... setidaknya untuk intuisi saya: "bola" l1 lebih seperti berlian yang spikey di sepanjang sumbu, yang berarti bahwa sebuah hyperplane yang tertabrak untuk memukulnya cenderung memiliki angka nol pada kapak.
Wayne
2
β^1212β^
3
Buku itu bagus, tetapi tidak pernah menjelaskan dari mana asalnya dan matematika di baliknya.
user13985
2

Jawaban non matematis sederhana adalah:

Untuk L2: Istilah penalti dikuadratkan , jadi mengkuadratkan nilai yang kecil akan membuatnya lebih kecil. Kami tidak harus membuatnya nol untuk mencapai tujuan kami untuk mendapatkan kesalahan kuadrat minimum, kami akan mendapatkannya sebelum itu.

Untuk L1: Istilah hukuman adalah absolut , kita mungkin perlu pergi ke nol karena tidak ada katalis untuk membuat lebih kecil .

Ini sudut pandang saya.

Arnab Mukherjee
sumber
Tidak terlalu meyakinkan bagi saya.
Tyler 十三 将士 归 玉门
2

L1 Norm vs L2 Norm

Gambar menunjukkan bentuk area yang ditempati oleh L1 dan L2 Norm. Gambar kedua terdiri dari berbagai kontur Gradient Descent untuk berbagai masalah regresi. Di semua plot kontur, amati lingkaran merah yang memotong Ridge atau L2 Norm. persimpangan tidak pada sumbu. Lingkaran hitam di semua kontur mewakili lingkaran yang memotong Norma L1 atau Lasso. Itu berpotongan relatif dekat dengan sumbu. Ini menghasilkan koefisien untuk 0 dan karenanya pemilihan fitur. Oleh karena itu norma L1 membuat model jarang.

Penjelasan lebih rinci di tautan berikut: Klik Posting di Menuju Ilmu Data

solver149
sumber
2β1=1β1=0L1