Jumlah pertanyaan terburuk yang diperlukan untuk mempelajari predikat monoton atas suatu poset

15

Pertimbangkan poset terbatas di atas item, dan predikat monoton yang tidak diketahui atas (yaitu, untuk , , jika dan maka ) . Saya dapat mengevaluasi dengan memberikan satu simpul dan mencari tahu apakah tahan atau tidak. Tujuan saya adalah untuk menentukan set node sedemikian rupa sehingga digunakan, menggunakan beberapa evaluasi(X,)nPXxyXP(x)xyP(y)PxXP(x)xXP(x)Pmungkin. (Saya dapat memilih pertanyaan saya tergantung pada jawaban semua pertanyaan sebelumnya, saya tidak diharuskan untuk merencanakan semua pertanyaan sebelumnya.)

Strategi over adalah fungsi yang memberi tahu saya, sebagai fungsi dari kueri yang saya jalankan sejauh ini dan jawaban mereka, simpul ke kueri, dan yang memastikan bahwa pada setiap predikat , dengan mengikuti strategi , Saya akan mencapai kondisi di mana saya tahu nilai pada semua node. Waktu berjalan dari pada predikat adalah jumlah pertanyaan yang diperlukan untuk mengetahui nilai pada semua node. Waktu berjalan terburuk dari adalah . Strategi optimal S ' sedemikian rupa sehingga wr (S') = \ min_S wr (S) .S(X,)PPr(S,P)SPPSwr(S)=maxPr(S,P)Swr(S)=minSwr(S)

Pertanyaan saya adalah sebagai berikut: diberikan sebagai masukan poset (X,) , bagaimana saya bisa menentukan waktu berjalan terburuk dari strategi optimal?

[Jelaslah bahwa untuk poset kosong n query akan diperlukan (kita perlu bertanya tentang setiap node tunggal), dan bahwa untuk total order sekitar log2n query akan diperlukan (melakukan pencarian biner untuk menemukan perbatasan). Hasil yang lebih umum adalah informasi berikut-teoretis batas bawah: jumlah pilihan yang mungkin untuk predikat P adalah jumlah NX dari antichains (X,) (karena ada pemetaan satu-ke-satu antara predikat monotonik dan antikristus diartikan sebagai elemen maksimal P ), jadi, karena setiap kueri memberi kita sedikit informasi, kita akan memerlukan setidaknya log2NXpertanyaan, merangkum dua kasus sebelumnya. Apakah ini terikat erat, atau apakah mereka beberapa poset yang strukturnya sedemikian rupa sehingga pembelajaran dapat membutuhkan lebih banyak permintaan secara asimptotik daripada jumlah antikristus?]

a3nm
sumber
2
Apa bedanya dengan pertanyaan Anda sebelumnya tentang topik ini? cstheory.stackexchange.com/questions/14772/…
Suresh Venkat
1
Setuju, ini mirip, tapi saya tertarik tentang poset umum di sini, termasuk poset dengan lebar kecil yang tidak terlihat sama sekali seperti kisi lengkap. Selain itu, saya tidak peduli lagi tentang kompleksitas tambahan atau hal semacam itu, hanya pada jumlah pertanyaan yang diperlukan sebagai fungsi dari pilihan poset. Dalam pengaturan ini, interpretasi fungsi boolean tidak dapat diterapkan dan sepertinya jawabannya tergantung pada "struktur" poset (mungkin jumlah antikristus, seperti yang saya sarankan). Mudah-mudahan ini waran pertanyaan terpisah, tolong tutup jika saya salah.
a3nm
1
FYI, dalam literatur kompleksitas, strategi seperti yang Anda definisikan biasanya disebut "pohon keputusan," dan mereka memiliki gagasan standar tinggi (ukuran yang Anda minati) dan ukuran.
Joshua Grochow
Terima kasih, Joshua! Saya kurang lebih sadar akan hal ini, saya hanya berpikir lebih mudah menggunakan kosakata dari teori permainan, tapi ya, saya sadar bahwa strateginya dapat dilihat sebagai pohon.
a3nm
1
(Ngomong-ngomong. Ngomong-ngomong, saya tidak hanya menunjukkan bahwa itu bisa dilihat sebagai pohon. Cara Anda menggambarkannya memang sangat mudah dan jelas, tetapi saya memberi Anda kata kunci / istilah seni yang mungkin Anda miliki dapat mencari, selain istilah yang mungkin langsung akrab bagi banyak orang yang sering mengunjungi situs ini. Cheers!)
Joshua Grochow

Jawaban:

7

Ini bukan jawaban yang lengkap, tetapi terlalu panjang untuk menjadi komentar.

Saya pikir saya menemukan contoh yang terikat tidak ketat.log2NX

Pertimbangkan hal berikut ini. Set ground adalah , dan lebih kecil dari untuk semua . Pasangan lainnya tidak ada bandingannya. (Diagram Hasse adalah siklus).a i b j i , j { 1 , 2 } 4X={a1,a2,b1,b2}aibji,j{1,2}4

Biarkan saya mengidentifikasi properti monoton dengan gangguan poset. Poset ini memiliki tujuh gangguan: , , , , , , , dan poset ini memiliki tujuh antichains karena antichains bersesuaian satu dengan yang lain dengan gangguan. Jadi, untuk poset ini.{ b 1 } { b 2 } { b 1 , b 2 } { a 1 , b 1 , b 2 } { a 2 , b 1 , b 2 } { a 1 , a 2 , b 1 , b 2 } log 2 N X= log 2 7 {b1}{b2}{b1,b2}{a1,b1,b2}{a2,b1,b2}{a1,a2,b1,b2}log2NX=log27=3

Sekarang, dengan argumen musuh, saya akan menunjukkan bahwa strategi apa pun membutuhkan setidaknya empat permintaan (jadi perlu menanyakan semua elemen). Mari kita perbaiki strategi yang sewenang-wenang.

Jika strategi pertama kali menanyakan , maka musuh menjawab " tidak berlaku." Lalu, kita dibiarkan dengan lima kemungkinan: , , , , . Jadi, untuk menentukan kasusnya, kita memerlukan setidaknya pertanyaan lagi. Secara total, kami membutuhkan empat pertanyaan. Argumen yang sama berlaku jika kueri pertama adalah . P ( a 1 ) { b 1 } { b 2 } { b 1 , b 2 } { a 2 , b 1 , b 2 } log 2 5 = 3 a 2a1P(a1){b1}{b2}{b1,b2}{a2,b1,b2}log25=3a2

Jika strategi pertama kali menanyakan , maka musuh menjawab " berlaku." Lalu, kita dibiarkan dengan lima kemungkinan: , , , , . Oleh karena itu, kita memerlukan setidaknya tiga pertanyaan lagi seperti sebelumnya. Secara total, kami membutuhkan empat pertanyaan. Argumen yang sama berlaku ketika kueri pertama adalah . P ( b 1 ) { b 1 } { b 1 , b 2 } { a 1 , b 1 , b 2 } { a 2 , b 1 , b 2 } { a 1 , a 2 , b 1 , b 2 } b 2b1P(b1){b1}{b1,b2}{a1,b1,b2}{a2,b1,b2}{a1,a2,b1,b2}b2

Jika kita mengambil salinan paralel dari poset ini, maka ia memiliki antichains, dan dengan demikian diusulkan terikat adalah . Tetapi, karena masing-masing salinan membutuhkan empat kueri, kita memerlukan setidaknya kueri.7 klog 2 7 k= 3 k 4 kk7klog27k=3k4k

Mungkin, ada poset yang lebih besar dengan celah yang lebih besar. Tetapi argumen ini hanya dapat meningkatkan koefisien.

Di sini, masalahnya adalah situasi di mana tidak ada kueri yang mem-partisi ruang pencarian secara merata. Dalam kasus seperti itu, musuh dapat memaksa bagian yang lebih besar tetap ada.

Yoshio Okamoto
sumber
1
Ah, menarik. Generalisasi contoh Anda ke , jelas bahwa jika jawabannya adalah dan maka kita tidak akan tahu pasti sampai semua node dipertanyakan. Namun, ada antiklin ( himpunan bagian kosong dari , idem untuk , dan himpunan kosong), sehingga tidak ketat oleh faktor. 2. Terima kasih atas contoh ini. Namun, saya tidak benar-benar melihat bagaimana / jika kesenjangan bisa lebih dari faktor multiplikasi, atau jika batas atas non-sepele dapat ditemukan, apalagi algoritma untuk jawaban yang tepat. X={a1,...,an,b1,...,bn}i,¬P(ai)i,P(bi)2n2n+112n1aibi
a3nm
7

Dalam makalah mereka Setiap Poset Memiliki Elemen Pusat , Linial dan Saks menunjukkan (Teorema 1) bahwa jumlah pertanyaan yang diperlukan untuk menyelesaikan masalah identifikasi ideal dalam poset paling banyak adalah , di mana dan adalah jumlah cita-cita . Apa yang mereka sebut "ideal" sebenarnya adalah himpunan yang lebih rendah dan ada korespondensi yang jelas antara predikat monotonik dan himpunan lebih rendah dari poin-poin yang tidak mereka pegang, selain itu "masalah identifikasi" mereka adalah mengidentifikasi dengan menanyakan node seperti dalam pengaturan saya, jadi saya pikir mereka berurusan dengan masalah yang saya tertarik dan bahwaXK0log2i(X)K0=1/(2log2(1+log25))i(X)Xi(X)=NX.

Jadi, menurut hasil mereka, informasi-teori batas bawah ketat hingga konstanta multiplikasi yang relatif kecil. Jadi ini pada dasarnya menyelesaikan pertanyaan dari jumlah pertanyaan yang diperlukan, sebagai fungsi dan hingga konstanta multiplikatif: antara dan .NXlog2NXK0log2NX

Linial dan Saks mengutip komunikasi pribadi oleh Shearer untuk mengatakan bahwa ada pesanan yang diketahui yang dapat kita buktikan dengan batas bawah untuk beberapa yang hanya sedikit kurang dari (ini adalah semangat jawaban Yoshio Okamoto yang mencoba pendekatan ini untuk nilai yang lebih kecil dari ).K1log2NXK1K0K1

Ini tidak sepenuhnya menjawab pertanyaan saya tentang menghitung jumlah pertanyaan yang diperlukan dari , namun, karena menghitung dari adalah # P-complete , saya merasa ada sedikit harapan. (Komentar tentang hal ini disambut baik.) Namun, hasil ini oleh Linial dan Saks mencerahkan.XNXX

a3nm
sumber
5

Untuk Boolean n-cube (atau, yang setara, untuk poset ( 2 S , ) dari semua himpunan bagian dari himpunan elemen-n), jawabannya diberikan oleh teorema Korobkov dan Hansel (masing-masing dari tahun 1963 dan 1966). Teorema Hansel [1] menyatakan bahwa fungsi Boolean monoton yang tidak diketahui (yaitu, predikat monoton yang tidak diketahui pada poset ini) dapat dipelajari dengan membuat algoritma deterministik paling banyak ϕ ( n ) = ( n({0,1}n,)(2S,) query (yaitu, memintaφ(n)pertanyaan dalam kasus terburuk). Algoritma ini cocok dengan batas bawah teorema Korobkov [2], yang mengatakan bahwaϕ(n)-1kueri tidak cukup. (Jadi algoritma Hansel optimal dalam pengaturan kasus terburuk.) Suatu algoritma dalam kedua pernyataan dipahami sebagai pohon keputusan deterministik.ϕ(n)=(nn/2)+(nn/2+1)ϕ(n)ϕ(n)1

Logaritma jumlah antichains di secara asimptotik sama dengan ( n({0,1}n,) , jadi ada kesenjangan faktor-konstan antaralogNXdan kinerja algoritma optimalϕ(n)2 ( n(nn/2)2n/πn/2logNX untuk poset ini.ϕ(n)2(nn/2)

Sayangnya, saya belum dapat menemukan perawatan yang baik dari algoritma Hansel dalam bahasa Inggris yang tersedia di web. Ini didasarkan pada lemma yang mempartisi n-kubus menjadi rantai dengan sifat khusus. Beberapa deskripsi dapat ditemukan di [3]. Untuk batas bawah, saya tidak tahu referensi ke deskripsi dalam bahasa Inggris.ϕ(n)

Karena saya terbiasa dengan hasil ini, saya dapat memposting deskripsi di arXiv, jika perawatan di kertas Kovalerchuk tidak cukup.

Jika am tidak banyak keliru, telah ada upaya untuk menggeneralisasi pendekatan Hansel, setidaknya untuk poset , di mana ( E k , ) adalah sebuah rantai 0 < 1 < ... < k - 1 , meskipun saya tidak dapat langsung memberikan referensi. Untuk kasus Boolean, orang juga telah menyelidiki gagasan kompleksitas selain dari kasus terburuk untuk masalah ini.(Ekn,)(Ek,)0<1<<k1

[1] G. Hansel, Sur le nombre des fonctions booléennes monotones de n variabel. CR Acad. Sci. Paris, 262 (20), 1088-1090 (1966)

[2] VK Korobkov. Perkiraan jumlah fungsi monoton aljabar logika dan kompleksitas algoritma untuk menemukan set resolven untuk fungsi monoton aljabar logika arbitrer. Matematika Soviet. Doklady 4, 753-756 (1963) (terjemahan dari bahasa Rusia)

[3] B. Kovalerchuk, E. Triantaphyllou, AS Deshpande, E. Vityaev. Pembelajaran interaktif fungsi monoton Boolean. Ilmu Informasi 94 (1), 87-118 (1996) ( tautan )

dd1
sumber
Terima kasih banyak atas jawaban terperinci ini! Untuk Boolean -cube, cf < cstheory.stackexchange.com/q/14772 >. Saya dapat membaca bahasa Prancis tetapi tidak dapat menemukan kertas Hansel (seharusnya tersedia di Gallica tetapi masalah ini tampaknya hilang), saya menemukan info yang relevan di Sokolov, NA (1982), "Tentang Evaluasi Optimal Fungsi Boolean Monoton", USSR Comput Math Math Phys, Vol 22, No 2, 207-220 (Terjemahan bahasa Inggris ada). Saya tertarik tentang generalisasi ke DAG lain jika Anda dapat menemukan referensi. Jangan ragu untuk membalas melalui email (a3nm AT a3nm DOT net) jika batas panjang adalah masalah. Terima kasih lagi! n
a3nm
Sama sama! Sayangnya, saya tidak tahu bagaimana cara mengikat algoritma waktu berjalan dalam hal ukuran output. Bukti Korobkov tentang batas bawah, misalnya, tidak memberikan jawaban untuk pertanyaan itu. Namun, saya merasa mungkin ada referensi yang sedikit relevan. Saya akan mencoba mencari waktu selama akhir pekan dan mencari generalisasi juga. Pada saat yang sama, saya tidak yakin apakah deskripsi bahasa Inggris yang tertutup dari kasus Boolean (dua teorema ini) layak untuk ditulis ...
dd1
@ A3nm mungkin kasus DAG belum dipertimbangkan dalam literatur? mungkinkah ini lebih sulit daripada boolean n-cube yang dipesan dengan dimasukkan?
vzn
@ vz Saya kira setidaknya beberapa pertanyaan di sini pasti terbuka. Bahkan untuk sebuah rantai, tidak segera jelas bagaimana cara menggeneralisasi algoritma Hansel.
dd1
@ a3nm semuanya tampaknya mirip dengan menemukan batas bawah / sirkuit monoton minimal (ukuran) tetapi belum melihatnya terhubung dengan jelas sejauh ini ...
vzn
0

[ CATATAN: Argumen berikut sepertinya tidak berfungsi, tapi saya meninggalkannya di sini sehingga orang lain tidak membuat kesalahan yang sama / kalau-kalau ada yang bisa memperbaikinya. Masalahnya adalah bahwa batas bawah eksponensial pada belajar / mengidentifikasi fungsi monoton, seperti di bawah ini, tidak selalu bertentangan dengan algoritma polinomial tambahan untuk masalah tersebut. Dan yang terakhir yang setara dengan memeriksa dualitas timbal balik dari dua fungsi monoton dalam waktu poli.]

Saya percaya dugaan Anda pada adalah palsu pada umumnya. Jika memang kasus yang log N X query yang dibutuhkan, yang menyiratkan cukup kuat batas bawah pada pembelajaran fungsi monoton menggunakan query keanggotaan . Secara khusus, biarkan poset X menjadi kubus Boolean dengan pemesanan biasa (jika Anda suka, X adalah Powerset dari { 1 , . . . , N } dengan sebagai urutan parsial). Jumlah M dari antichains maksimal dalam X memenuhi log M =logNXlogNXXX{1,...,n}MX [1]. Jika ide Anda padalogNXbenar, maka ada beberapa predikat monoton padaXyang membutuhkan dasarnya ( n-1logM=(1+o(1))(n1n/2)logNXXpermintaan. Secara khusus, ini menyiratkan batas bawah pada dasarnya2nuntuk kompleksitas algoritma yang memecahkan masalah ini.(n1n/2)2n2n

Namun, jika saya mengerti dengan benar [ yang sekarang saya tahu saya belum ], masalah Anda setara dengan memeriksa dualitas timbal balik dari dua fungsi monoton, yang dapat dilakukan dalam waktu kuasi-polinomial (lihat intro dari makalah ini dengan Biok dan Ibaraki , yang mengutip Fredman dan Khachiyan), bertentangan dengan apa pun yang mendekati batas bawah .2n

[1] Liviu Ilinca dan Jeff Kahn. Menghitung antichains maksimal dan set independen . arXiv: 1202.4427

Joshua Grochow
sumber
Josh, saya tidak melihat masalah dengan argumen Pemahaman saya adalah bahwa terbuka apakah fungsi monoton dapat dipelajari dalam polinomial waktu dalam n dan jumlah elemen minimal. makalah Bioch-Ibaraki adalah tentang algoritma polinomial tambahanlogNXn
Sasho Nikolov
Ah, baiklah. Saya tidak menyadarinya. (Seperti yang saya katakan, saya bukan ahli dalam bidang ini - jawaban saya hanya didasarkan pada mencari beberapa hal dan menyatukannya.) Saya akan meninggalkannya di sini sehingga orang lain dapat melihatnya dan setidaknya tidak membuat kesalahan yang sama / paling baik mengubahnya menjadi sesuatu yang bermanfaat.
Joshua Grochow