Mari kita mendefinisikan kelas fungsi lebih dari satu set bit. Perbaiki dua distribusi yang "cukup" berbeda satu sama lain (jika Anda suka, jarak variasional mereka setidaknya , atau yang serupa).p , q ϵ
Sekarang setiap fungsi dalam kelas ini didefinisikan oleh kumpulan indeks , dan dievaluasi sebagai berikut: Jika paritas bit yang dipilih adalah 0, kembalikan sampel acak dari , jika tidak kembalikan sampel acak dari .k S p q
Masalah : Misalkan saya diberi akses oracle ke beberapa dari kelas ini, dan sementara saya tahu (atau ukuran jarak lain), saya tidak tahu dan .ϵ p q
Apakah ada batasan jumlah panggilan yang harus saya lakukan untuk PAC-pelajari ? Agaknya jawaban saya adalah dan .n , k ϵ
Catatan : Saya tidak menentukan domain output. Sekali lagi, saya fleksibel, tetapi untuk sekarang katakanlah dan didefinisikan di atas domain terbatas . Secara umum, saya juga akan tertarik pada kasus ketika mereka didefinisikan lebih dari (misalnya, jika mereka Gaussians)q [ 1 .. M ] R
sumber
Jawaban:
Diskusi dalam komentar di bawah ini menunjukkan bahwa saya telah salah memahami pertanyaan. Jawaban saya adalah didasarkan pada Oracle tidak mengambil input dan kembali di mana x ~ p atau x ~ q , tergantung pada f ∈ F . Ini rupanya bukan yang diminta.( x , f( x ) ) x ∼ hlm x ∼ q f∈ F
Karena distribusi target ditetapkan untuk setiap target , batas atas sampel PAC berlaku (ini mengikuti fakta bahwa distribusi target untuk batas ini bahkan dapat sepenuhnya bergantung pada f ∗ ). Karenanya, m ≤ ˜ O ( 1f∗∈ F f∗
contoh harus cukup untuk menemukan hipotesis kesalahan≤ϵwp≥1-δ. Catatan - setelah melihat contoh-contoh ini, seseorang perlu menemukan hipotesis yang konsisten dariF, dan ini mungkin tidak dapat ditelusuri.
Di sisi lain, seseorang dapat memperoleh batas bawah yang hampir cocok bahkan untuk kasus , distribusi seragam, di mana m ≥ Ω ( V C ( F ) ) masih diperlukan contoh (ini dapat ditingkatkan sedikit) .p = q= U m ≥ Ω ( V C ( F) )
Jarak variasional antara dan q , serta k dapat memainkan peran dalam celah kecil antara batas-batas ini, tapi saya ragu.hal q k
sumber
def fitness() ...
random_number_generator.set_seed(x)