Penyesalan Internal dalam Optimasi Cembung Online

19

"Optimasi cembung online" Zinkevich ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) menggeneralisasi "penyesalan minimalisasi" algoritma pembelajaran dari pengaturan linier ke pengaturan cembung dan memberikan "penyesalan eksternal" yang bagus. . Apakah ada generalisasi serupa untuk penyesalan internal? (Aku tidak sepenuhnya yakin apa artinya itu.)

lg.learning online-learning Noam
sumber
Apakah mungkin menambahkan deskripsi singkat penyesalan internal pada pertanyaan?
Moritz
Dalam "para ahli" yang biasa menetapkan penyesalan internal berarti bahwa jika dipikir-pikir Anda tidak akan ingin beralih satu tindakan dengan yang lain, secara konsisten sepanjang sejarah. Makalah Blum-Mansour mungkin adalah referensi terbaik untuk penyesalan internal vs eksternal: jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf
Noam

Jawaban:

9

Coba "Belajar tanpa penyesalan dalam game cembung" oleh Gordon, Greenwald, dan Marks http://portal.acm.org/citation.cfm?id=1390202 . Abstraknya sepertinya menjawab pertanyaan Anda, atau setidaknya siapa pun yang menjawab pertanyaan itu akan mengutip atau dikutip oleh makalah itu.

Warren Schudy
sumber
0

Makalah Avrim Blum ini menunjukkan hubungan antara penyesalan eksternal dan internal. Menurut abstraknya, penyesalan eksternal adalah ukuran seberapa buruk suatu algoritma dibandingkan dengan tindakan tetap terbaik, sedangkan penyesalan internal membandingkan dengan variasi terbaik dari metode tersebut (permutasi output tetap terbaik, seperti pelaporan kelas A setiap kali algoritma asli melaporkan kelas B).

Alexandre Passos
sumber
1
Makalah Blum-Mansour tidak dalam pengaturan "optimasi cembung online", melainkan dalam pengaturan "pakar" linier. Pertanyaan saya adalah apakah sesuatu yang serupa, atau algoritma penyesalan internal langsung lainnya dapat diterapkan dalam pengaturan cembung.
Noam