Memperkirakan Dimensi VC

Apa yang diketahui tentang masalah berikut?

Diberikan kumpulan fungsi , temukan subkoleksi terbesar tunduk pada kendala bahwa VC-Dimensi untuk beberapa bilangan bulat . $C$ $f:\{0,1\}^n\rightarrow\{0,1\}$ $S \subseteq C$ $(S) \leq k$ $k$

Apakah ada algoritma perkiraan atau hasil kekerasan untuk masalah ini?

reference-request approximation-algorithms cg.comp-geom lg.learning vc-dimension Aaron Roth
sumber

Fungsi-fungsi tampaknya tidak berperan dalam memaksimalkan | S |

Suresh Venkat

Pilihan fungsi menentukan Dimensi-VC dari S. Masalahnya adalah menemukan kelas fungsi sebesar mungkin, dengan tunduk pada batasan dimensi-VC.

Aaron Roth

Saya melihat. Jadi diterjemahkan menjadi "tanah geometri", Anda diberikan koleksi rentang (f bertindak sebagai fungsi karakteristik) dan Anda menginginkan subkoleksi terbesar dari dimensi VC yang dibatasi.

Suresh Venkat

Masalah lain dalam menjawab pertanyaan: bagaimana C disajikan? Kita tahu bahwa ukuran maksimum yang mungkin dari

adalah

oleh Sauer's Lemma, dan menuliskan bahkan satu fungsi dalam

membutuhkan

bit.

S

$S$

O (2^{n k})

$O(2^{nk})$

C

$C$

n

$n$

Suresh Venkat

Baik. Saya tertarik pada hasil dalam rezim representasi apa pun. Anda dapat membayangkan bahwa

disajikan sebagai

matriks, dalam hal ini waktu berjalan

akan menjadi `` efisien '' (walaupun bukan waktu

, yang diperlukan untuk memeriksa secara menyeluruh apakah semua koleksi titik

dihancurkan). Jika ada hasil algoritmik yang mungkin dengan hanya akses kotak hitam ke fungsi di

, itu akan lebih baik.

C

$C$

2^{n} \times | C |

$2^n\times |C|$

2^{n} \times | C |

$2^n\times |C|$

2^{n \times k}

$2^{n\times k}$

k

$k$

C

$C$

Aaron Roth

Jawaban:

Sunting : masalah aslinya adalah -sekarang untuk mendekati saat mana menunjukkan jumlah set. $n^{1-\epsilon}$ $k=1$ $n$

The ganda dari hipergraf sebuah diperoleh dengan bertukar simpul dengan tepi, dan melestarikan insiden. Lebih mudah untuk memahami masalah ketika kita mencatat bahwa sebuah hypergraph memiliki VC-dimensi 1 jika dual-nya bebas silang (untuk semua dalam , setidaknya satu dari kosong). $P, Q$ $A$ $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$

Secara dualitas masalah asli (untuk ) adalah setara dengan, diberikan hypergraph , cari ukuran-maksimum dengan bebas silang. $k=1$ $(V, \mathcal{S})$ $U \subseteq V$ $(U, \{S \cap U \mid S \in \mathcal{S}\})$

Sebenarnya, masalah (ganda) ini sangat sulit bahkan ketika semua set dalam memiliki ukuran 2: maka itu adalah grafik dan kami sedang mencari ukuran vertex ukuran-besar yang subgraf yang diinduksikannya yang tidak mengandung jalur dua sisi ( tidak sulit untuk melihat ini adalah satu-satunya cara pasangan penyilang dapat muncul, dengan asumsi grafik memiliki setidaknya 4 simpul). Tetapi properti ini adalah turun temurun dan tidak trivial dan dengan demikian kita dapat menggunakan hasil dari Feige dan Kogan untuk menunjukkan kekerasan. $\mathcal{S}$

Balasan asli

$k=1$ $S$ $S$ $n^{1-\epsilon}$ $\Theta(n)$

$A$ $P, Q$ $A$ $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$

$G=(V, E)$ $H=(X, S)$ $X = V \uplus E \uplus \{0\}$ $0$ $v$ $G$ $T_v$ $S$

{v} \cup {e ∣ e is an edge incident to v} .

$\{v\} \cup \{e \mid e \textrm{ is an edge incident to }v\}.$

$\{T_v\}_{v \in U}$ $U$ $G$

Tetapi untuk masalah (primal) asli, tampaknya beberapa pemikiran diperlukan ... terlihat menarik!

daveagp
sumber

Beberapa pekerjaan terkait yang relevan: Memperkirakan dimensi VC itu sendiri (apalagi menemukan subkoleksi besar dengan dimensi VC terbatas) dalam representasi Anda adalah lengkap- LOGNP (LOGNP adalah NP terbatas untuk log n bit nondeterminisme). Ada juga sedikit pekerjaan terkait dalam memperkirakan dan mendekati dimensi VC ketika presentasi ruang jangkauan lebih kompak (lihat referensi di dalamnya juga)

Suresh Venkat
sumber