Komplexität von Computerabfragen beim SQ-Lernen

Es ist bekannt, dass es für das PAC-Lernen natürliche Konzeptklassen gibt (z. B. Untergruppen von Entscheidungslisten), für die es polynomielle Lücken zwischen der Komplexität der Stichprobe, die für das informationstheoretische Lernen durch einen rechnerisch unbegrenzten Lernenden benötigt wird, und der Komplexität der Stichprobe, die von einem Polynom benötigt wird. Zeitlerner. (siehe z. B. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE oder http://portal.acm.org/citation.cfm?id=301437 )

Diese Ergebnisse scheinen jedoch von der Kodierung eines Geheimnisses in bestimmten Beispielen abzuhängen und lassen sich daher nicht auf das SQ-Modell des Lernens übertragen, bei dem der Lernende lediglich statistische Eigenschaften der Verteilung abfragt.

Ist bekannt, ob es Konzeptklassen gibt, für die informationstheoretisches Lernen im SQ-Modell mit O (f (n)) Abfragen möglich ist, rechnerisch effizientes Lernen jedoch nur mit Omega (g (n)) Abfragen für g (n) ) >> f (n)?

Ich habe (mich) diese Frage vor einiger Zeit gestellt. Zumindest für das Lernen in Bezug auf eine bestimmte Verteilung gibt es ein ziemlich einfaches Beispiel für eine Konzeptklasse, die informationstheoretisch SQ-lernbar, aber NP-schwer zu SQ-lernen ist. Es sei \ phi eine binäre Codierung einer SAT-Instanz und y ihre lexikografisch erste erfüllende Zuweisung (oder 0 ^ n ist die Instanz ist nicht erfüllbar). Nun sei f (\) eine Funktion, bei der über eine Hälfte der Domäne die MAJ (\) und über die zweite Hälfte der Domäne die PAR (y) ist. Hier ist MAJ die Mehrheitsfunktion über Variablen, die in der Zeichenfolge \ phi auf 1 gesetzt sind, und PAR (y) ist die Paritätsfunktion über Variablen, die in der Zeichenfolge y auf 1 gesetzt sind. Sei F die auf diese Weise erhaltene Klasse von Funktionen. Um F über die Gleichverteilung U zu lernen, muss man nur Mehrheiten lernen (was einfach ist), um \ phi und dann y zu finden. Andererseits ist es ziemlich einfach, das SAT-zu-SQ-Lernen von F (mit einer Genauigkeit, die merklich größer als 3/4 ist) über die gleichmäßige Verteilung zu reduzieren. Der Grund dafür ist natürlich, dass Paritäten für SQs im Wesentlichen "unsichtbar" sind und daher SAT gelöst werden muss, um F zu lernen.

Das ist eine schöne Frage. Die Stärke des statistischen Abfragemodells ist genau die Fähigkeit, unbedingte Untergrenzen für das Lernen mit SQ zu beweisen - zum Beispiel ist Parität bei statistischen Abfragen mit Polynomzahlen nicht lernbar.

Ich kenne die Ergebnisse des von Ihnen angeforderten Formulars nicht, aber vielleicht fehlt uns etwas Offensichtliches ...