Untergrenzen für das Lernen in der Mitgliedschaftsabfrage und im Gegenbeispielmodell

Dana Angluin ( 1987 ; pdf ) definiert ein Lernmodell mit Mitgliedschaftsabfragen und theoretischen Abfragen (Gegenbeispiele zu einer vorgeschlagenen Funktion). Sie zeigt, dass eine reguläre Sprache, die durch einen minimalen DFA von Zuständen dargestellt wird, in Polynomzeit (wobei die vorgeschlagenen Funktionen DFAs sind) mit O ( m n 2 ) Zugehörigkeitsabfragen und höchstens n - 1 theoretischen Abfragen ( m ) lernbar ist ist die Größe des größten vom Tutor bereitgestellten Gegenbeispiels). Leider diskutiert sie keine Untergrenzen.$n$$O(mn^2)$$n−1$$m$

Wir können das Modell leicht verallgemeinern, indem wir einen magischen Tutor annehmen, der die Gleichheit zwischen beliebigen Funktionen überprüfen und Gegenbeispiele liefern kann, wenn diese unterschiedlich sind. Dann können wir fragen, wie schwierig es ist, Klassen zu lernen, die größer sind als normale Sprachen. Ich interessiere mich für diese Verallgemeinerung und die ursprüngliche Beschränkung auf reguläre Sprachen.

Gibt es bekannte Untergrenzen für die Anzahl der Abfragen im Mitgliedschafts- und Gegenbeispielmodell?

Ich interessiere mich für Untergrenzen für die Anzahl der Mitgliedschaftsabfragen, theoretischen Abfragen oder Kompromisse zwischen den beiden. Ich interessiere mich für Untergrenzen für jede Klasse von Funktionen, auch für kompliziertere Klassen als normale Sprachen.

Wenn es keine Untergrenzen gibt : Gibt es bekannte Hindernisse für den Nachweis von Abfrageuntergrenzen in diesem Modell?

Verwandte Fragen

Gibt es Verbesserungen am Algorithmus von Dana Angluin zum Lernen regulärer Mengen?

$NP \neq coNP$

$O(n)$$O(n^2+ n \log m)$

Ein einfacher Weg, um Untergrenzen zu erreichen, ist die Informationstheorie. Sie können herausfinden, wie viele unterschiedliche Ziele es gibt und wie viele Bits eine Abfrage Ihnen gibt usw. Diese oberen Grenzen kommen nahe, sind aber nicht vorhanden. Es gibt auch Probleme, über die man nachdenken muss, wie die "Gegenbeispiele" beim Lernenden ankommen. Ein gut ausgewähltes Gegenbeispiel kann eine Menge Informationen preisgeben.

Aktualisierung der obigen Diskussion : Angluin und Dohrn behandeln das Fragenlernen mit zufälligen Gegenbeispielen in einem kürzlich erschienenen Artikel .