Mengapa fungsi kerugian 0-1 sulit diterapkan?

12

Dalam buku Deep Learning Ian Goodfellow , tertulis itu

Terkadang, fungsi kerugian yang benar-benar kita pedulikan (katakanlah, kesalahan klasifikasi) bukan salah satu yang dapat dioptimalkan secara efisien. Misalnya, meminimalkan kerugian yang diharapkan 0-1 yang diharapkan biasanya tidak dapat dilakukan (eksponensial dalam dimensi input), bahkan untuk pengklasifikasi linier. Dalam situasi seperti itu, orang biasanya mengoptimalkan fungsi pengganti pengganti, yang bertindak sebagai proksi tetapi memiliki kelebihan.

Mengapa kehilangan 0-1 tidak bisa dilakukan, atau bagaimana hal itu eksponensial dalam dimensi input?

samra irshad
sumber

Jawaban:

18

Fungsi kerugian 0-1 adalah non-cembung dan terputus-putus, sehingga metode (sub) gradien tidak dapat diterapkan. Untuk klasifikasi biner dengan pemisah linier, fungsi kerugian ini dapat dirumuskan sebagai mencari yang meminimalkan nilai rata-rata fungsi indikator atas semua sampel . Ini adalah eksponensial dalam input, karena karena ada dua nilai yang mungkin untuk setiap pasangan, ada konfigurasi yang mungkin untuk memeriksaβ1(yiβxi0)i2nntotal titik sampel. Ini dikenal sebagai NP-hard. Mengetahui nilai saat ini dari fungsi kerugian Anda tidak memberikan petunjuk apa pun tentang bagaimana Anda harus memodifikasi solusi Anda saat ini untuk meningkat, karena Anda dapat menurunkan jika metode gradien untuk fungsi cembung atau kontinu tersedia.

Don Walpola
sumber
1
Poin yang sangat bagus - dalam praktik pencarian acak atau pencarian lengkap adalah satu-satunya metode yang dapat digunakan untuk menemukan minimum fungsi kerugian seperti itu, bukan?
DeltaIV
2
^^ atau metode kecerdasan evolusioner / berbasis segerombolan mungkin?
samra irshad
@samrairshad Ya, sebenarnya 0-1 kerugian tidak jarang terlihat dalam metode evolusi.
John Doucette
Sebelum melompat dari pencarian acak ke algoritma evolusioner / kerumunan yang kompleks, saya akan memeriksa metode cross-entropy (CEM).
maksimal
1

Kesalahan klasifikasi kadang-kadang bisa dilakukan. Ini dapat dioptimalkan secara efisien - meskipun tidak sepenuhnya - menggunakan metode Nelder-Mead, seperti yang ditunjukkan dalam artikel ini:

https://www.computer.org/csdl/trans/tp/1994/04/i0420-abs.html

"Pengurangan dimensi adalah proses mengubah vektor multidimensi menjadi ruang dimensi rendah. Dalam pengenalan pola, sering diinginkan bahwa tugas ini dilakukan tanpa kehilangan informasi klasifikasi yang signifikan. Kesalahan Bayes adalah kriteria ideal untuk tujuan ini; namun, itu dikenal sangat sulit untuk perawatan matematika.Oleh karena itu, kriteria suboptimal telah digunakan dalam praktek.Kami mengusulkan kriteria alternatif, berdasarkan estimasi kesalahan Bayes, yang diharapkan lebih dekat dengan kriteria optimal daripada kriteria yang saat ini digunakan Algoritma untuk pengurangan dimensi linier, berdasarkan kriteria ini, disusun dan diimplementasikan. Eksperimen menunjukkan kinerja superiornya dibandingkan dengan algoritma konvensional. "

Kesalahan Bayes yang disebutkan di sini pada dasarnya adalah kerugian 0-1.

Pekerjaan ini dilakukan dalam konteks pengurangan dimensi linier. Saya tidak tahu seberapa efektif itu untuk melatih jaringan pembelajaran yang mendalam. Tetapi intinya adalah, dan jawaban atas pertanyaan: kerugian 0-1 tidak bisa dipecahkan secara universal. Ini dapat dioptimalkan dengan relatif baik untuk setidaknya beberapa jenis model.

ljubomir
sumber