Gibt es Verteilungseigenschaften, die „maximal“ schwer zu testen sind?

13

Ein Verteilungstestalgorithmus für eine Verteilungseigenschaft P (die nur eine Teilmenge aller Verteilungen über [n] ist) erlaubt den Zugriff auf Stichproben gemäß einer Verteilung D und muss entscheiden (whp), ob DP oder d(D,P)>ϵ ( d hier normalerweise der Abstand 1 ). Das häufigste Maß für die Komplexität ist die Anzahl der vom Algorithmus verwendeten Stichproben.

Beim Testen von Standardeigenschaften mit Abfragezugriff auf ein Objekt ist eine lineare Untergrenze für die Abfragekomplexität offensichtlich die stärkste Untergrenze, die möglich ist, da n Abfragen das gesamte Objekt offenbaren würden. Gilt das auch für Distributionstests?

Soweit ich weiß, ist die "triviale" Obergrenze zum Testen der Eigenschaften von Verteilungen O(n2logn) - durch Chernoff-Grenzen ist dies ausreichend, um eine Verteilung D ', die nahe bei D in liegt, "aufzuschreiben" 1 distance, und dann können wir nur überprüfen, ob es Verteilungen in der Nähe von D 'gibt, die in P liegen (dies kann unendlich viel Zeit in Anspruch nehmen, ist jedoch für die Komplexität der Stichprobe irrelevant).

  • Gibt es einen besseren "trivialen" Test für alle Verteilungseigenschaften?
  • Gibt es Verteilungseigenschaften, für die wir wissen, dass die unteren Grenzen der Stichproben stärker als linear sind?
Yonatan
quelle
scheint ähnlich zu sein, um die Trennung von Komplexitätsklassen zu beweisen & als könnte es sich um ein bekanntes offenes Problem handeln ...?
VZN 06.10.12
Gerade gesehen , diese ... Ich bin nicht ganz sicher , wie man das gebundene abgeleitet , aber beachten Sie, dass tatsächlich Distributionen Lernen (über Domäne der Größe n ) zu TV / 1 Abstand ε mit einer Wahrscheinlichkeit von 2 / 3 tatsächlich kann mit O ( n / ε 2 ) Proben durchgeführt werden (und dies ist eng). Wenn Sie also nicht konstante Werte des Proximity-Parameters ε betrachten , besteht keine Hoffnung, ω ( n ) -Untergrenzen zu erhalten ...O(n2logn)n1ε2/3O(n/ε2)εω(n)
Clement C.

Antworten:

5

Entschuldigen Sie, dass Sie diesen Beitrag gefunden haben - er ist ziemlich alt, aber ich dachte, es wäre keine so schlechte Idee, ihn beantwortet zu haben.

Zunächst sieht es so aus, als hätten Sie Ihren Chernoff-Test mit einer etwas merkwürdigen Parametereinstellung durchgeführt. Beachten Sie, dass es zur Durchführung des vorgeschlagenen Ansatzes "Testen durch Lernen" ausreicht, die Verteilung der Gesamtabweichung (oder - falls - you 1 , die bis zu einem Faktor 2 gleich ist) zur Entfernung ε zu lernen1 . (bevor "offline" geprüft wird, ob es eine Verteilungp'mit der EigenschaftPn gibt,die selbst höchstensε entfernt istε2pPn von Ihrer gelernten Hypothese p ). Dies würde naiv zu einemO(nlogn führenε2p^obere Grenze der Probenkomplexität für diesen Ansatz; Allerdings ist es bekannt (und „Heimat“)die eine willkürliche Verteilung über eine Domäne der Größe Lernnbis Abstandε(in Gesamtvariation Abstand) mit nur erfolgenO(nO(nlognε2)nεProben (und das ist dicht).O(nε2)

Die Grundlinie sollte also tatsächlich , der innbereits linear ist. Nun kann man die nächste Frage stellen:Gibt es "natürliche" Eigenschaften, für die das Testen (zum Beispiel für die Konstanteε) eine lineare Abhängigkeit von der Domänengrößenerfordert?O(nε2)nεn

1/10Θε(nlogn)

(Beachten Sie, dass es ein bisschen "Schummeln" ist, in dem Sinne, dass die Eigenschaft lediglich eine Möglichkeit darstellt, eine tolerante Testfrage zu beantworten und sie als Test einer Ad-hoc- Eigenschaft neu zu kennzeichnen .)

kkk=n/10Ω(nlogn)n100

Clement C.
quelle