Pembelajaran PAC yang tepat untuk 2-DNF dengan distribusi seragam

Apa hasil canggih tentang kompleksitas kueri dari rumus 2-DNF pembelajaran PAC yang tepat dengan kueri sampel dan di bawah distribusi yang seragam ? Atau ada yang tidak sepele yang terikat padanya?

Karena saya sama sekali tidak terbiasa dengan teori belajar dan pertanyaan ini dimotivasi oleh bidang yang berbeda, jawabannya mungkin jelas. Saya memeriksa buku oleh Kearns dan Vazirani, tetapi mereka tampaknya tidak mempertimbangkan pengaturan ini secara eksplisit.

upd. Meskipun parameter utama yang diminati adalah kompleksitas kueri, waktu berjalan juga penting. Jika memungkinkan, waktu yang berjalan sebaiknya kira-kira sama dengan kompleksitas kueri atau paling banyak polinomial.

upd. Lampiran B (atas halaman 18) dari makalah "Belajar Fungsi Submodular" oleh Balcan dan Harvey menyebutkan bahwa "Sudah diketahui bahwa 2-DNF efisien PAC yang bisa dipelajari." Namun, mereka tidak menyebutkan, apakah hasil ini untuk pembelajaran yang tepat atau memberikan referensi.

Saya tidak tahu apakah Anda akan mempertimbangkan hal-hal berikut yang tidak sepele, tetapi ini dia.

Pertama, agar jelas agar kita tidak membingungkan -DNF dengan k -term DNF (yang sering saya lakukan), rumus c -DNF atas variabel x 1 , … , x n adalah dalam bentuk ∨ k i = 1 ( ℓ i , 1 ∧ ℓ i , 2 . . . ℓ i , c ) di mana ∀ 1 ≤ i ≤ k dan 1 ≤ j ≤ $c$$k$$c$$x_1, \ldots, x_n$$\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$$\forall 1 \le i \le k$$1 \le j \le c$, .$\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$

Pertama-tama kita dapat bertanya berapa banyak istilah berbeda yang bisa ada dalam -DNF. Setiap istilah akan memiliki c dari n variabel, masing-masing baik dinegasikan atau tidak - untuk 2 c ($c$$c$$n$ istilah yang mungkin berbeda. Dalam contoh 2-DNF, setiap istilah akan muncul atau tidak, membuat untuk| H| =22c ($2^c\binom{n}{c}$ kemungkinan "target", di manaHadalah ruang hipotesis.$|\mathcal{H}| = 2^{2^c\binom{n}{c}}$$\mathcal{H}$

Bayangkan sebuah algoritma yang mengambil sampel dan kemudian mencoba semua | H | hipotesis sampai menemukan satu yang memprediksi dengan sempurna pada sampel. Teorema Razor Occam mengatakan bahwa Anda hanya perlu mengambil sekitar m = O ( $m$$|\mathcal{H}|$sampel untuk algoritma ini untuk menemukan target dengan kesalahan≤ϵdengan probabilitas≥1-δ.$m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$$\le \epsilon$$\ge 1-\delta$

Dalam kasus kami, untuk , lg | H | = O ( n 2 ) , yang berarti Anda akan membutuhkan sekitar n 2 sampel untuk melakukan pembelajaran (yang tepat).$c=2$$\lg|\mathcal{H}| = O(n^2)$$n^2$

Tetapi keseluruhan permainan dalam pembelajaran tidak benar-benar kompleksitas sampel (meskipun itu bagian dari permainan, terutama dalam pembelajaran atribut-efisien), tetapi dalam mencoba merancang algoritma polinomial-waktu. Jika Anda tidak peduli dengan efisiensi, maka adalah jawaban paling sederhana untuk kompleksitas sampel PAC.$n^2$

UPDATE (diberi pertanyaan yang diubah) :

Karena Anda secara eksplisit menyatakan bahwa Anda hanya peduli pada kompleksitas sampel, saya mempresentasikan Algoritma Occam, yang mungkin merupakan argumen paling sederhana. Namun, jawaban saya agak malu-malu. -DNF sebenarnya bisa dipelajari dalam waktu polinomial! Ini adalah hasil dari makalah asli Valiant, " A Theory of the Learnable ." Sebenarnya c -DNF dapat dipelajari untuk c = O ( 1 ) .$2$$c$$c = O(1)$

Argumennya sebagai berikut. Anda dapat melihat -DNF sebagai disjungsi dari ≈ n c "meta-variabel" dan mencoba mempelajari disjungsi dengan menghilangkan meta-variabel yang tidak konsisten dengan contoh-contoh. Solusi semacam itu dapat dengan mudah diterjemahkan kembali ke solusi "tepat", dan membutuhkan waktu O ( n c ) . Sebagai catatan tambahan, masih terbuka apakah ada algoritma waktu polinomial untuk c = ω ( 1 ) .$c$$\approx n^c$$O(n^c)$$c = \omega(1)$

Seperti apakah kompleksitas sampel juga merupakan batas bawah, jawabannya cukup banyak ya. Makalah ini oleh Ehrenfeucht et al. menunjukkan bahwa Occam terikat hampir ketat.$n^2$