Szacowanie wymiaru VC

Co wiadomo na temat następującego problemu?

Biorąc pod uwagę zbiór funkcji , znajdź największą podkolekcję zastrzeżeniem ograniczenia, że VC-Wymiar dla jakiejś liczby całkowitej . $C$ $f:\{0,1\}^n\rightarrow\{0,1\}$ $S \subseteq C$ $(S) \leq k$ $k$

Czy istnieją algorytmy aproksymacyjne lub wyniki twardości dla tego problemu?

— Aaron Roth
źródło

Funkcje wydają się nie odgrywać żadnej roli w maksymalizacji | S |

— Suresh Venkat

Wybór funkcji determinuje wymiar VC S. Problem polega na znalezieniu jak największej klasy funkcji, z zastrzeżeniem ograniczenia wymiaru VC.

— Aaron Roth,

Widzę. Przetłumaczone na „obszar geometrii”, otrzymujesz zbiór zakresów (f działa jako funkcja charakterystyczna) i chcesz mieć największą podgrupę ograniczonego wymiaru VC.

— Suresh Venkat

Drugi problem w odpowiedzi na pytanie: jak przedstawia się C? Wiemy, że maksymalny możliwy rozmiar

wynosi

według Lemera Sauera, a zapisanie nawet jednej funkcji w

wymaga

bitów.

S

$S$

O (2^{n k})

$O(2^{nk})$

C

$C$

n

$n$

— Suresh Venkat

Dobrze. Interesują mnie wyniki w dowolnym systemie reprezentacyjnym. Można sobie wyobrazić, że

jest przedstawione jako

macierz, w którym to przypadku czas działania

byłby `` efektywny '' (choć nie czas

, co wystarczyłoby, aby wyczerpująco sprawdzić, czy wszystkie zbiory

punktów zostały rozbite). Jeśli jakiekolwiek wyniki algorytmu są możliwe przy jedynie dostępnym zapytaniu do czarnej skrzynki do funkcji w

, byłoby to jeszcze lepsze.

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

Odpowiedzi:

Edycja : pierwotny problem to twardy do przybliżenia, gdy gdzie oznacza liczbę zbiorów. $n^{1-\epsilon}$ $k=1$ $n$

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

W dualności pierwotny problem (dla ) jest równoważny, biorąc pod uwagę hypergraph , znajdź maksymalny rozmiar przy bezkrzyżowym. $k=1$ $(V, \mathcal{S})$ $U \subseteq V$ $(U, \{S \cap U \mid S \in \mathcal{S}\})$

W rzeczywistości ten (podwójny) problem jest bardzo trudny, nawet jeśli wszystkie zestawy w mają rozmiar 2: wtedy jest to wykres i szukamy maksymalnego rozmiaru wierzchołka, którego indukowany podgraf, który nie zawiera ścieżki o dwóch krawędziach ( nietrudno zauważyć, że jest to jedyny sposób na powstanie krzyżującej się pary, zakładając, że wykres ma co najmniej 4 wierzchołki). Ale ta właściwość jest dziedziczna i nietrywialna, dlatego możemy użyć wyniku Feige i Kogana do wykazania twardości. $\mathcal{S}$

Oryginalna odpowiedź

$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$

Ale w przypadku pierwotnego (pierwotnego) problemu wydaje się, że potrzeba więcej przemyśleń ... wygląda interesująco!

— daveagp
źródło

Niektóre istotne powiązane prace: Szacowanie samego wymiaru VC (nie mówiąc już o znalezieniu dużego podkolekcji z ograniczonym wymiarem VC) w twojej reprezentacji jest uzupełnieniem LOGNP (LOGNP jest NP ograniczony do log n bitów niedeterminizmu). Jest również trochę powiązanych prac dotyczących szacowania i aproksymacji wymiaru VC, gdy prezentacja przestrzeni zasięgu jest bardziej zwarta (patrz również odnośniki w środku)

— Suresh Venkat
źródło