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

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 $D\in P$ oder $d(D,P)>\epsilon$ ( $d$ hier normalerweise der Abstand $\ell_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(n^2\log n)$ - durch Chernoff-Grenzen ist dies ausreichend, um eine Verteilung D ', die nahe bei D in liegt, "aufzuschreiben" $\ell_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?

cc.complexity-theory machine-learning query-complexity property-testing 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

) zu TV /

Abstand

mit einer Wahrscheinlichkeit von

tatsächlich kann mit

Proben durchgeführt werden (und dies ist eng). Wenn Sie also nicht konstante Werte des Proximity-Parameters

, besteht keine Hoffnung,

-Untergrenzen zu erhalten ...

O (n^{2} \log n)

$O(n^2\log n)$

n

$n$

ℓ_{1}

$\ell_1$

ε

$\varepsilon$

2 / 3

$2/3$

O (n / ε^{2})

$O(n/\varepsilon^2)$

ε

$\varepsilon$

ω (n)

$\omega(n)$

Clement C.

Antworten:

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 , die bis zu einem Faktor 2 gleich ist) zur Entfernung zu lernen $\ell_1$ . (bevor "offline" geprüft wird, ob es eine Verteilungmit der Eigenschaftdie selbst höchstens $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ von Ihrer gelernten Hypothese ). Dies würde naiv zu einem $\frac{\varepsilon}{2}$ $\hat{p}$ 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 Lernbis Abstand(in Gesamtvariation Abstand) mit nur erfolgen $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ Proben (und das ist dicht). $O(\frac{n}{\varepsilon^2})$

Die Grundlinie sollte also tatsächlich , der inbereits 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ößeerfordert? $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ $n$

$1/10$ $\Theta_\varepsilon(\frac{n}{\log n})$

(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 .)

$k$ $k$ $k=n/10$ $\Omega(\frac{n}{\log n})$ $\frac{n}{100}$

Clement C.
quelle