Diberikan

Inilah masalah dengan cita rasa yang mirip dengan belajar junta:

Input: Fungsi $f: \{0,1\}^n \rightarrow \{-1,1\}$ , diwakili oleh oracle keanggotaan, yaitu oracle yang diberikan $x$ , mengembalikan $f(x)$ .

Sasaran: Temukan subkelompok $S$ dari $\{0,1\}^n$ dengan volume $|S|=2^{n-k}$ sedemikian rupa sehingga $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$ . Kami berasumsi subkubus semacam itu ada.

Sangat mudah untuk mendapatkan algoritma yang berjalan dalam waktu $n^{O(k)}$ dan mengembalikan jawaban yang benar dengan probabilitas $\ge 0.99$ dengan mencoba semua $(2n)^k$ cara untuk memilih subkumpulan dan pengambilan sampel rata-rata di masing-masing.

Saya menarik dalam menemukan algoritma yang berjalan dalam waktu $poly(n,2^k)$ . Atau, batas bawah akan bagus. Masalahnya memiliki rasa yang mirip dengan belajar junta, tetapi saya tidak melihat hubungan yang sebenarnya antara kesulitan komputasi mereka.

Pembaruan: @ Thomas di bawah ini membuktikan bahwa kompleksitas sampel masalah ini adalah . Masalah yang menarik adalah, masih, kompleksitas komputasi dari masalah tersebut. $poly(2^k,\log n)$

Sunting: Anda dapat mengasumsikan untuk kesederhanaan bahwa ada subkotak dengan (perhatikan celahnya: kami sedang mencari subkube dengan rata-rata .) Saya cukup yakin setiap solusi untuk masalah dengan celah tersebut juga akan menyelesaikan masalah tanpa celah tersebut. $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ $\ge 0.1$

machine-learning lg.learning boolean-functions sample-complexity pangsit mobius
sumber

Jawaban:

Ini adalah batasan yang lebih baik pada kompleksitas sampel. (Meskipun kompleksitas komputasi masih .) $n^k$

Dalil. Asumsikan ada subkelompok ukuran sehingga . Dengan sampel kita dapat, dengan probabilitas tinggi, mengidentifikasi sebuah subkelompok dari ukuran sedemikian rupa sehingga $S$ $2^{n-k}$ $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$ $O(2^k \cdot k \cdot \log n)$ $S'$ $2^{n-k}$ . $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$

Perhatikan kerugian kecil dalam parameter ( optimal versus jaminan ). $0.12$ $0.1$

Bukti. Memilih poin seragam secara acak dan permintaan pada setiap . $m$ $P \subset \{0,1\}^n$ $f$ $x \in P$

Memperbaiki subkotak ukuran . Kami memiliki . Dengan ikatan Chernoff, Juga $S$ $2^{n-k}$ $\mathbb{E}[|S \cap P|]=m 2^{-k}$

P [| S \cap P | < m 2^{- k - 1}] \leq 2^{- Ω (m 2^{- k})} .

$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$

P [| E_{x \in S \cap P} [f (x)] - E_{x \in S} [f (x)] | > ε] \leq 2^{- Ω (| S \cap P | ε^{2})} .

$\mathbb{P}[| \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | > \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$

Oleh serikat terikat semua pilihan, kita punya ${n \choose k}2^k$ $S$ Jadi dengan memilih, kita dapat memastikan bahwa, dengan probabilitas setidaknya, kita dapat memperkirakanke dalamuntuk semua subkubudari ukuran

P [\forall S | E_{x \in S \cap P} [f (x)] - E_{x \in S} [f (x)] | \leq ε] \geq 1 - (\binom{n}{k}) 2^{k} 2^{- Ω (m 2^{- k} ε^{2})} .

$\mathbb{P}[\forall S ~~ | \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | \leq \varepsilon] \geq 1 - {n \choose k} 2^k 2^{-\Omega(m 2^{-k} \varepsilon^2)}.$

m = O (2^{k} / ε^{2} \cdot k \log n)

$m = O(2^k/\varepsilon^2 \cdot k \log n)$

0.99

$0.99$

E_{x \in S} [f (x)]

$\mathbb{E}_{x \in S}[f(x)]$

ε

$\varepsilon$

S

$S$

2^{n - k}

$2^{n-k}$ .

Pengaturan , kami membuktikan teorema: memilih subkumpulan dengan yang terbesar akan, dengan probabilitas tinggi, memenuhi persyaratan. QED $\varepsilon=0.01$ $| \mathbb{E}_{x \in S \cap P}[f(x)]|$

Thomas
sumber

C \cdot 2^{k}

$C \cdot 2^k$

C

$C$

C

$C$

n^{k}

$n^k$

Cara lain untuk melihat ini adalah bahwa ruang rentang yang Anda gambarkan telah membatasi dimensi hancuran dan oleh karena itu dimensi VC terikat, dan kemudian Anda melemparkan teorema aproksimasi padanya.

Suresh Venkat