Richtiges PAC-Lernen von 2-DNF unter gleichmäßiger Verteilung

Was ist das Stand der Technik über die Abfragekomplexität von richtigen PAC-Lern-2-DNF-Formeln mit Beispielabfragen und unter gleichmäßiger Verteilung ? Oder eine nicht triviale Bindung daran?

Da ich mit Lerntheorie überhaupt nicht vertraut bin und diese Frage von einem anderen Bereich motiviert ist, könnte die Antwort offensichtlich sein. Ich habe das Buch von Kearns und Vazirani überprüft, aber sie scheinen diese Einstellung nicht explizit zu berücksichtigen.

upd. Obwohl der Hauptparameter von Interesse die Komplexität der Abfrage ist, ist auch die Laufzeit wichtig. Wenn möglich, sollte die Laufzeit vorzugsweise in etwa der Komplexität der Abfrage oder höchstens dem Polynom entsprechen.

upd. Anhang B (oben auf Seite 18) des Papiers "Learning Submodular Functions" von Balcan und Harvey erwähnt: "Es ist bekannt, dass 2-DNFs effizient PAC-lernbar sind." Sie erwähnen jedoch nicht, ob dieses Ergebnis für das richtige Lernen ist oder geben einen Hinweis.

Ich weiß nicht, ob Sie das Folgende als nicht trivial betrachten werden, aber hier bin ich.

Um klar zu sein, damit wir DNF nicht mit k- Term DNF verwechseln (was ich oft mache), hat eine c- DNF-Formel über Variablen x 1 , … , x n die Form ∨ k i = 1 ( l i , 1 ∧ l i , 2 . . . l i , c ) , wo ∀ 1 ≤ i ≤ k und 1 ≤ j ≤ $c$$k$$c$$x_1, \ldots, x_n$$\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$$\forall 1 \le i \le k$$1 \le j \le c$, .$\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$

Wir können zunächst fragen, wie viele verschiedene Begriffe in einem DNF existieren können. Jeder Begriff hat c der$c$$c$ Variablen, jede entweder negiert oder nicht - was 2 c ($n$ verschiedene mögliche Begriffe. In einer 2-DNF-Instanz wird jeder Begriff entweder angezeigt oder nicht, was zu| führt $2^c\binom{n}{c}$ mögliche "Ziele", wobeiHder Hypothesenraum ist.$|\mathcal{H}| = 2^{2^c\binom{n}{c}}$$\mathcal{H}$

Stellen Sie sich einen Algorithmus vor, der Samples nimmt und dann alle | ausprobiert H | Hypothesen, bis eine gefunden wird, die die Stichproben perfekt vorhersagt. Occams Rasiermessersatz besagt, dass Sie nur etwa m = O ( $m$$|\mathcal{H}|$Abtastwerte für diesen Algorithmus, um ein Ziel mit einem Fehler≤ϵmit einer Wahrscheinlichkeit von≥1-δ zu finden.$m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$$\le \epsilon$$\ge 1-\delta$

In unserem Fall für , lg | H $c=2$ , was bedeutet, dass Sie ungefähr n 2 Proben benötigen, um das (richtige) Lernen durchzuführen.$\lg|\mathcal{H}| = O(n^2)$$n^2$

Das ganze Lernspiel besteht jedoch nicht wirklich aus Beispielkomplexität (obwohl dies Teil des Spiels ist, insbesondere beim Attribut-effizienten Lernen), sondern darin, Polynom-Zeit-Algorithmen zu entwerfen. Wenn Sie sich nicht für Effizienz interessieren, ist die einfachste Antwort für die Komplexität von PAC-Stichproben.$n^2$

UPDATE (angesichts der geänderten Frage) :

Da Sie ausdrücklich angegeben haben, dass Sie sich nur um die Komplexität der Stichproben kümmern, habe ich den Brute-Force-Occam-Algorithmus vorgestellt, der wahrscheinlich das einfachste Argument ist. Meine Antwort war jedoch etwas schüchtern. -DNF sind tatsächlich in Polynomzeit lernbar! Dies ist ein Ergebnis von Valiants Originalarbeit " A Theory of the Learnable ". Tatsächlich sind c- DNF für jedes c = O ( 1 ) lernbar .$2$$c$$c = O(1)$

Das Argument lautet wie folgt. Sie können eine DNF als Disjunktion von ≈ n c " Metavariablen " anzeigen und versuchen, die Disjunktion zu lernen, indem Sie die Metavariablen entfernen , die nicht mit den Beispielen übereinstimmen. Eine solche Lösung kann leicht in eine "richtige" Lösung zurückübersetzt werden und benötigt O ( n c ) Zeit. Als Randnotiz ist noch offen, ob es einen Polynomzeitalgorithmus für c = ω ( 1 ) gibt .$c$$\approx n^c$$O(n^c)$$c = \omega(1)$

Die Frage, ob die Komplexität der -Stichproben auch eine Untergrenze ist, lautet so ziemlich Ja. Dieses Papier von Ehrenfeucht et al. zeigt, dass die Occam-Grenze fast eng ist.$n^2$