Regulasi dan proyeksi ke

8

Saya mencoba memahami bagaimana regularisasi bekerja dalam hal proyeksi ke a l bola, dan proyeksi Euclidean ke simpleks.

Saya tidak yakin saya mengerti apa yang kami maksud ketika kami memproyeksikan vektor bobot ke l1 atau l2 bola.

Saya bisa mengerti konsep l1program regularisasi, seperti dalam, kita pergi melalui setiap elemen dalam vektor bobot, dan menerapkan di signum(w) * max(0.0, abs(w) - shrinkageValue)mana shrinkageValue = regularizationParameter * eta, dengan demikian mengarahkan bobot kecil ke 0.

Saya kira saya kehilangan beberapa matematika di sini, jadi pertanyaan saya adalah bagaimana kita menerjemahkan proyeksi vektor ke dalam program yang baru saja saya jelaskan? Bagaimana proyeksi regularisasi dan vektor terhubung?

Sunting: Saya sedang mencoba melalui makalah ini Proyeksi Efisien kel1 -Ball untuk Belajar dalam Dimensi Tinggi

Batang
sumber

Jawaban:

11

Proyeksi regularisasi dan vektor terhubung melalui ide optimasi terbatas dan kondisi Karush-Kuhn (tidak ada hubungan) .

Bagaimana kondisi KKT?

Secara singkat, ini menyatakan bahwa, jika x adalah solusi untuk masalah "kecilkan f(x) tunduk pada g(x)0", kemudian x juga merupakan solusi untuk masalah tersebut f(x)=λg(x) untuk beberapa skalar λ. Tapi ini sama dengan mengatakanf(x)λg(x)=0, yang artinya xmeminimalkan masalah optimisasi yang tidak dibatasi "minimalf(x)λg(x)".

Intuisinya adalah:

  • g(x)<0. Pada kasus ini,x adalah "solusi interior" sehingga gradien fharus nol pada saat itu. (Jika bukan nol, kita bisa bergerak sedikit ke arah itu darix, sambil mempertahankan g(x)<0, dan memiliki nilai lebih tinggi untuk f(x). Lalu kita aturλ=0 dan kita sudah selesai.

  • Atau, g(x)=0. Pada kasus ini,xada di tepi ruang solusi yang memungkinkan. Secara lokal, tepi ini terlihat seperti hyperplane orthogonal ke gradieng(x), karena cara Anda mempertahankan g(x)=0kendala adalah untuk tidak bergerak ke atas atau ke bawah gradien sama sekali. Tetapi itu berarti bahwa satu-satunya arah gradienf mungkin bisa menunjuk adalah arah yang sama persis seperti g--Jika memiliki komponen yang ortogonal g, kita bisa bergerak x sedikit ke arah itu, tetap di hyperplane ortogonal g(x)=0, dan meningkat f(x).

Bagaimana kondisi KKT menjelaskan hubungan antara minimisasi terbatas dan regularisasi

Jika g(x)=|x|c untuk beberapa norma dan beberapa konstan c, lalu kendala g(x)0 maksudnya x terletak di bidang jari-jari cdi bawah norma itu. Dan dalam formulasi yang tidak dibatasi, kurangiλg(x) dari fungsi yang ingin Anda maksimalkan inilah yang akhirnya menerapkan hukuman regularisasi: Anda benar-benar mengurangi λ|x|+λc (dan konstanta λc tidak masalah untuk optimasi).

Orang sering mengambil keuntungan dari "dualitas" ini antara optimasi yang tidak dibatasi dan dibatasi. Untuk contoh yang bisa saya temukan dengan cepat dengan Googling lihat On the LASSO dan dualnya .

Mengapa proyeksi penting di sini?

OK, jadi mengapa seseorang menulis makalah tentang proyeksi cepat?

Pada dasarnya, satu cara Anda dapat melakukan optimasi terbatas - "maksimalkan f(x) tunduk pada xX"- adalah untuk melakukan hal berikut:

  • Ambil algoritma iteratif apa pun untuk maksimisasi tanpa batasanf(x)
  • Mulailah dengan menebak x0
  • Ambil satu langkah dari algoritma: x0step(x0)
  • Kemudian proyeksikan kembali ke set X: x1PX(x0).
  • Dan ulangi sampai konvergensi.

Sebagai contoh, ini adalah bagaimana proyeksi gradient descent diturunkan dari gradient descent biasa. Tentu saja, mengoptimalkan fungsi proyeksi AndaPX sangat penting di sini.

Menyatukan semuanya

Jadi, anggaplah Anda ingin menyelesaikan LASSO:

argminβ(yβX)2+λ||β||1

Itu versi yang tidak dibatasi. Dengan kondisi KKT, menambahkan istilah regularisasi setara dengan membatasi solusi untuk berbohong||β||1c untuk beberapa konstan c. Tapi itu baru saja1-Bola dengan jari-jari c!

Jadi Anda dapat membayangkan menyelesaikan ini dengan proyeksi (sub) gradient descent. * Jika Anda melakukannya, Anda PX Fungsi akan menjadi proyeksi ke bola unit, dan Anda ingin membuatnya cepat.

* Saya tidak berpikir orang benar-benar melakukan ini, karena ada cara yang lebih efisien. Tetapi mereka mungkin menggunakan proyeksi juga. EDIT: seperti yang ditunjukkan @Dougal, varian yang lebih canggih dari keturunan yang diproyeksikan cukup bagus untuk menulis makalah tentang tahun 2008.

Ben Kuhn
sumber
1
Algoritma ISTA / FISTA pada dasarnya (dipercepat) memproyeksikan penurunan subgradien, yang mungkin bukan algoritma LASSO yang paling disukai, tetapi itu cukup bagus (dan saya pikir sangat canggih sekitar 2008 ketika makalah itu diterbitkan).
Dougal
@Dougal: terima kasih untuk referensi! Saya sudah mengeditnya.
Ben Kuhn