Karakterisasi kombinatorial dari pembelajaran eksak dengan pertanyaan keanggotaan

Sunting: Karena saya belum menerima tanggapan / komentar dalam seminggu, saya ingin menambahkan bahwa saya senang mendengar apa pun tentang masalah tersebut. Saya tidak bekerja di daerah itu, jadi meskipun itu pengamatan sederhana, saya mungkin tidak mengetahuinya. Bahkan komentar seperti "Saya bekerja di area ini, tetapi saya belum melihat karakterisasi seperti ini" akan sangat membantu!

Latar Belakang:

Ada beberapa model pembelajaran yang dipelajari dengan baik dalam teori belajar (misalnya, pembelajaran PAC, pembelajaran online, pembelajaran eksak dengan pertanyaan keanggotaan / kesetaraan).

Misalnya, dalam pembelajaran PAC, kompleksitas sampel dari kelas konsep memiliki karakterisasi kombinatorial yang baik dalam hal dimensi VC kelas. Jadi jika kita ingin belajar kelas dengan akurasi dan kepercayaan diri yang konstan, ini dapat dilakukan dengan sampel, di mana adalah dimensi VC. (Perhatikan bahwa kita berbicara tentang kompleksitas sampel, bukan kompleksitas waktu.) Ada juga karakterisasi yang lebih halus dalam hal akurasi dan kepercayaan diri. Demikian pula, model terikat pembelajaran online memiliki karakterisasi kombinatorial yang bagus.$\Theta(d)$$d$

Pertanyaan:

Saya ingin tahu apakah hasil yang serupa diketahui untuk model pembelajaran pasti dengan pertanyaan keanggotaan. Model didefinisikan sebagai berikut: Kami memiliki akses ke kotak hitam yang pada input memberi Anda . Kita tahu berasal dari beberapa kelas konsep . Kami ingin menentukan dengan pertanyaan sesedikit mungkin.$x$$f(x)$$f$$C$$f$

Apakah ada parameter kombinatorial dari konsep kelas yang mencirikan jumlah kueri yang diperlukan untuk mempelajari konsep dalam model pembelajaran eksak dengan kueri keanggotaan?$C$

Apa yang saya tahu:

Karakterisasi terbaik yang saya temukan dalam tulisan ini oleh Servedio dan Gortler , menggunakan parameter yang mereka kaitkan dengan Bshouty, Cleve, Gavaldà, Kannan dan Tamon . Mereka mendefinisikan parameter kombinatorial yang disebut , di mana adalah kelas konsep, yang memiliki properti berikut. (Biarkan menjadi jumlah kueri optimal yang diperlukan untuk mempelajari dalam model ini.)$\gamma^C$$C$$Q_C$$C$

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

Karakterisasi ini hampir ketat. Namun, mungkin ada kesenjangan kuadrat antara batas atas dan bawah. Misalnya jika , maka batas bawah adalah , tetapi batas atas adalah . (Saya juga berpikir kesenjangan ini dapat dicapai, yaitu, ada kelas konsep yang batas bawah keduanya , tetapi batas atas adalah .)Ω ( k ) O ( k 2 ) Ω ( k $1/\gamma^C = \log |C| = k$$\Omega(k)$$O(k^2)$$\Omega(k)$$O(k^2)$

Untuk mengarahkan pulang titik dari contoh moose anonim, pertimbangkan kelas konsep yang terdiri dari fungsi yang menghasilkan 1 hanya pada satu titik di {0,1} ^ n. Kelas berukuran 2 ^ n, dan 2 ^ n pertanyaan diperlukan dalam kasus terburuk. Lihatlah Dimensi Pengajaran kasus terburuk (Goldman & Schapire) yang menyediakan sesuatu yang mirip dengan apa yang Anda cari.

Saya tidak tahu karakterisasi seperti itu. Namun, perlu dicatat bahwa untuk hampir semua kelas konsep, kita perlu menanyakan semua poin. Untuk melihatnya, pertimbangkan kelas konsep yang terdiri dari semua vektor boolean n-dimensi dengan bobot Hamming 1. Kelas konsep ini jelas membutuhkan n kueri untuk dipelajari, yang setara dengan kardinalitasnya. Anda mungkin dapat menggeneralisasi pengamatan ini untuk mendapatkan bahwa hampir semua kelas konsep juga mengharuskan melakukan semua pertanyaan.

Saya akan curiga bahwa dengan memberikan kelas konsep C sebagai input, sulit untuk menentukan kompleksitas tepatnya mempelajari kelas konsep dengan pertanyaan keanggotaan, atau bahkan memperkirakannya hingga mengatakan konstanta. Ini akan memberikan beberapa indikasi bahwa karakterisasi kombinatorial "baik" tidak ada. Jika Anda ingin membuktikan hasil kekerasan-NP tetapi cobalah dan gagal, jangan ragu untuk memposting di sini dan saya akan melihat apakah saya bisa mengetahuinya (saya punya beberapa ide).

Meskipun yang lain sudah menunjukkan jawabannya. Saya pikir saya dapat membuatnya mandiri dan menunjukkan mengapa dimensi pengajaran adalah jawabannya.

$C$$X$$S\subseteq X$$f$$f$$C$$S$

$\mathcal{T}(f)$$f$$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$$f$$_{min}(f)$$\mathcal{T}(f)$$(C)=$$_{f\in C}$$(f,C)$$C$

$f$$(f,C)$$_{min}(f)$$(C)$$f$