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

9

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.

Grigory Yaroslavtsev
quelle
Welche Art von Fragen?
Timothy Sun
Nur Proben. Außerdem sollte ich ausdrücklich darauf hinweisen, dass es bei der Frage um die Komplexität der Abfrage geht, nicht um die Laufzeit (bearbeitet).
Grigory Yaroslavtsev
Ich habe Ihre Frage beantwortet, vorausgesetzt, Beispielabfragen sind nur zufällige Beispiele (und keine Mitgliedschaftsabfragen).
Lev Reyzin
1
Ja, Abfragen sind nur zufällige Beispiele aus der gleichmäßigen Verteilung.
Grigory Yaroslavtsev

Antworten:

14

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 , 1l i , 2 . . . l i , c ) , wo 1 i k und 1 j cckcx1,,xnich=1k(ich,1ich,2...ich,c)1ichk1jc, .ich,j{x1,,xn,x¯1,,x¯n}}

Wir können zunächst fragen, wie viele verschiedene Begriffe in einem DNF existieren können. Jeder Begriff hat c dercc Variablen, jede entweder negiert oder nicht - was 2 c ( n ergibtn verschiedene mögliche Begriffe. In einer 2-DNF-Instanz wird jeder Begriff entweder angezeigt oder nicht, was zu| führt H.2c(nc) mögliche "Ziele", wobeiHder Hypothesenraum ist.|H.|=22c(nc)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 ( 1) nehmen müssenm|H.|Abtastwerte für diesen Algorithmus, um ein Ziel mit einem Fehlerϵmit einer Wahrscheinlichkeit von1-δ zu finden.m=Ö(1ϵ|(H.|+1δ)ϵ1- -δ

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|H.|=Ö(n2)n2

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.n2

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 .2cc=Ö(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 .cncÖ(nc)c=ω(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.n2

Lev Reyzin
quelle
1
Vielen Dank! Dies ist ein nicht triviales Ergebnis - ich wusste nicht, dass eine exponentielle Laufzeit hilfreich sein wird. Für die Anwendung, an die ich denke, ist die Polynomzeit jedoch viel wünschenswerter (die Frage wurde aktualisiert). Ist der von Ihnen beschriebene Ansatz der bekannteste für dieses Problem? Gibt es Untergrenzen für die Komplexität von Abfragen (auch für unbegrenzte Laufzeit)?
Grigory Yaroslavtsev
Die Frage wurde mit einer Referenz aktualisiert, die die Frage motivierte.
Grigory Yaroslavtsev
1
hat die Antwort auf Ihre aktualisierte Frage aktualisiert
Lev Reyzin
Auch - in diesem Fall halte ich eine exponentielle Laufzeit nicht für hilfreich. Aber im Allgemeinen scheint es so zu sein. Das Lernen (mit optimaler Stichprobenkomplexität) ist normalerweise einfach, wenn Sie exponentielle Zeit haben.
Lev Reyzin
2
Vielen Dank! Ich werde einige Zeit brauchen, um die Referenzen zu überprüfen, aber bisher scheint es eine vollständige Antwort zu sein.
Grigory Yaroslavtsev