Pertanyaan pembelajaran paritas

10

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 ϵnp,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 qfkSpq

Masalah : Misalkan saya diberi akses oracle ke beberapa dari kelas ini, dan sementara saya tahu (atau ukuran jarak lain), saya tidak tahu dan .ϵ p qfϵpq

Apakah ada batasan jumlah panggilan yang harus saya lakukan untuk PAC-pelajari ? Agaknya jawaban saya adalah dan .n , k ϵfn,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 ] Rpq[1..M]R

Suresh Venkat
sumber
Saya tidak yakin saya mengerti modelnya. Apa yang Anda tentukan dalam panggilan oracle? Apakah contoh selalu diambil dari distribusi yang ditentukan oleh target?
Lev Reyzin
1
Dalam panggilan oracle, Anda memanggil f () dan mengembalikan nilai.
Suresh Venkat
Jadi tergantung pada fungsi target , apakah p atau q selalu digunakan untuk menghasilkan contoh? (Saya berasumsi Anda sedang belajar beberapa kelas F. )fFpqF
Lev Reyzin
Ya itu benar. masalahnya adalah mempelajari yang mana (atau mempelajari bit paritas yang digunakan)
Suresh Venkat
2
Saya tidak yakin bagaimana Anda mengadaptasi model PAC ke model ini. Tetapi tampaknya itu cukup untuk dapat membedakan dari q dengan probabilitas 1 - 1 / ( 2 k ) dan kemudian Anda bisa mendapatkan nilai f ( x ) untuk k bebas linear x dan menggunakan eliminasi gaussian untuk menemukan f (karena f linear). membedakan dua gaussi yang terpisah akan mudah misalnya. pq11/(2k)f(x)kxff
Sasho Nikolov

Jawaban:

6

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))xpxqfF


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 ( 1fFf contoh harus cukup untuk menemukan hipotesis kesalahanϵwp1-δ. Catatan - setelah melihat contoh-contoh ini, seseorang perlu menemukan hipotesis yang konsisten dariF, dan ini mungkin tidak dapat ditelusuri.

mO~(1ϵ(VC(F)+log(1/δ)))
ϵ1δF

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=UmΩ(VC(F))

Jarak variasional antara dan q , serta k dapat memainkan peran dalam celah kecil antara batas-batas ini, tapi saya ragu.pqk

Lev Reyzin
sumber
Pengaturan khas pembelajaran PAC memiliki oracle yang mengambil sampel x dari distribusi D , dan mengembalikan ( x , f ( x ) ) . Ini bukan pengaturan yang dijelaskan dalam pertanyaan Suresh atau posting blog yang menginspirasinya: bit.ly/YtwdST . Dalam kedua hal ini, oracle adalah fungsi f , dan pelajar bebas untuk menyerahkan elemen apa pun dari set instance (bitstrings of length n(f,D)xD(x,f(x))fn). Im, apakah jawaban Anda menganggap oracle dari tipe pertama, atau tipe kedua? Jika tipe kedua, apakah kita masih berbicara tentang pembelajaran PAC?
Keki Burjorjee
1
Saya melihat. Dalam PAC, yang "oracle" biasanya dianggap sebagai sebuah tombol yang kembali di mana x ~ D . Oracle yang Anda jelaskan disebut "kueri keanggotaan" untuk f . Jawaban saya hanya berlaku untuk yang pertama. Jika Anda hanya bertanya tentang keanggotaan, bagaimana Anda mengetahui informasi tentang p atau q menggunakan kerangka kerja Suresh? Katakanlah p = q untuk kesederhanaan. (x,f(x))xDfhalqhal=q
Lev Reyzin
Terima kasih atas klarifikasi itu. Jadi, dalam kasus yang dijelaskan Suresh, oracle "permintaan keanggotaan" berfungsi sebagai berikut (saya kira Anda telah menempatkan entitas ini dalam tanda kutip karena oracle dapat mengembalikan nilai nyata, bukan hanya boolean yang menjadi-anggota / tidak-a- jawaban anggota): jika paritas atribut efektif adalah 1, maka hasil yang dikembalikan diambil dari distribusi . Kalau tidak, hasilnya diambil dari distribusi q . Ada kerutan tambahan. Sang oracle mengingat semua jawaban sebelumnya, dan mengembalikannya jika ditanya dengan input yang sama. Dengan kata lain, itu deterministik. pq
Keki Burjorjee
1
Saya tidak mengerti. Jika oracle hanyalah sebuah fungsi dan Anda menanyakannya dengan memberinya x , bukankah hanya mengembalikan f ( x ) ? Bagaimana p atau q masuk untuk bermain jika pelajar menghasilkan x sendiri? Saya pikir saya telah gagal memahami poin dasar ini selama ini ...fxf(x)pqx
Lev Reyzin
Untuk dan q = N ( - 0,25 , 1 ) , pseudocode oracle untuk masalah dengan "kerutan" diberikan di bagian bawah komentar reddit ini: bit.ly/XvVMC4 ( ). Saya tidak dapat memasukkan kode karena SE tidak mengizinkan baris baru dalam komentar. Untuk mendapatkan versi "non-wrinkly" dari masalah, cukup hapus barisnya . hal=N(+0,25,1)q=N(-0,25,1)def fitness() ...random_number_generator.set_seed(x)
Keki Burjorjee