Dimensi VC digeneralisasi ke domain diskrit, non-biner, tidak berurutan?

8

Dimensi VC adalah ukuran kompleksitas kelas fungsi yang terkait erat dengan kompleksitas sampel. Dimensi penghancuran lemak adalah generalisasi yang cocok untuk domain yang lebih kaya: yaitu . Apakah ada generalisasi standar dimensi-VC yang cocok untuk fungsi dengan domain diskrit dan tidak berurutan? yaitu mana adalah himpunan terbatas tanpa urutan di atasnya.f:X{0,1}f:XRf:XKK

Aaron Roth
sumber

Jawaban:

10

Ya - Saya pikir Anda sedang mencari "dimensi multiclass VC," dan ada beberapa generalisasi yang berbeda dari dimensi VC ke klasifikasi multiclass. Makalah yang bagus tentang ini adalah oleh Ben-David et al. ('95). Selain membuktikan hasil yang dapat dipelajari, mereka memberikan sejarah yang bagus dan referensi untuk ekstensi dimensi VC sebelumnya ke casing multiclass. Lain mungkin relevan kerja oleh Haussler dan Long ('95) generalisasi lemma Sauer untuk versi yang lebih umum dari dimensi VC.

Lev Reyzin
sumber