Wie intrinsisch ist der Term

8

Ein -net für einen Bereichsraum ist eine Teilmenge N von X, so dass N \ cap R für alle R \ in \ mathcal {R} nicht leer ist, so dass | X \ cap R | \ ge \ varepsilon | X | .ε(X.,R.)N.X.N.R.R.R.|X.R.|ε|X.|

Bei einem Bereichsraum (X.,R.) der VC-Dimension d ist ein ε Netz der Größe O(dεlog(dε)) kann in der Zeit O (d) ^ {3d} \ left (\ frac {1} {\ varepsilon ^ 2} \ log \ left (\ frac {d} {\ varepsilon} \ right) \ berechnet werden rechts) ^ d | X | O(d)3d(1ε2log(dε))d|X|(siehe [1], Thm 4.6).

Inwieweit ist der Begriff O(d)3d diesem Problem eigen? Kann es speziell auf 2 ^ {O (d)} verbessert werden 2O(d)? Sind Untergrenzen bekannt?

Eine verwandte Frage: Gibt es allgemeine Bedingungen für (X,R) für die eine solche Verbesserung bekannt ist?

[1] Bernard Chazelle. Die Diskrepanzmethode. 2000.

Don Sheehy
quelle
2
Gute Frage ! und willkommen Don!
Suresh Venkat

Antworten:

10

Wenn Sie mit einem randomisierten Algorithmus einverstanden sind, können Sie einfach zufällig Punkteabtasten, und dies ist ein ϵ- Netz mit einer Wahrscheinlichkeit von mindestens 1 - δ . O((d/ϵ)log(d/ϵδ))ϵ1δ

Für den deterministischen Algorithmus glaube ich, dass der -Term aus folgendem Grund stammt. Sie partitionieren zuerst Ihren vollständigen Satz in Teilmengen mit einer Größe von etwa s = O ( ( d / ϵ ) log ( d / ϵ ) ), wobei s die Größe des ϵ- Netzes ist, das Sie am Ende erhalten möchten. Dann führen Sie zwei solcher Teilmengen zusammen und reduzieren sie auf die Hälfte dieser Größe. (Grundsätzlich wird dies wiederholt, bis ein Satz übrig ist.) Der Reduktionsschritt berücksichtigt im Wesentlichen alle interessanten Bereiche des zusammengeführten Satzes der Größe 2 sdO(d)s=O((d/ϵ)log(d/ϵ))sϵ2s. Durch VC-Grenzen gibt es ungefähr Bereiche, und Sie müssen jeden dieser Bereiche "überprüfen", um festzustellen, ob er getroffen wurde. Das s d hat ein d O ( d ) . Das d im s- Term wird benötigt. Um diese Grenze unter Verwendung dieses deterministischen Rahmens zu verringern, müssten Sie irgendwie alle Bereiche implizit "überprüfen", ohne sie explizit aufzuzählen. Dies scheint deterministisch schwierig zu sein, aber ich bin nicht sicher, ob ich eine explizite Untergrenze kenne - die meisten Arbeiten in diesem Bereich gehen davon aus, dass d konstant ist, und missbrauchen dies stark. O((2s)d)sddO(d)dsd

Jeff Phillips
quelle