Gibt es Verbesserungen an Dana Angluins Algorithmus zum Erlernen regulärer Mengen?

33

In ihrer wegweisenden Arbeit von 1987 präsentiert Dana Angluin einen polynomialen Zeitalgorithmus zum Lernen eines DFA aus Mitgliedschaftsabfragen und theoretischen Abfragen (Gegenbeispiele zu einem vorgeschlagenen DFA).

Sie zeigt, dass, wenn Sie versuchen, einen minimalen DFA mit Zuständen zu lernen , und Ihr größtes Beispiel die Länge m hat , Sie O ( m n 2 ) Mitgliedschaftsabfragen und höchstens n - 1 Theorieabfragen durchführen müssen.nmO(mn2)n1

Hat sich die Anzahl der Abfragen, die zum Erlernen eines regulären Satzes erforderlich sind, erheblich verbessert?


Referenzen und verwandte Fragen

Artem Kaznatcheev
quelle
Hoffentlich kommt @DominikFreydenberger irgendwann in der Zukunft vorbei. Er wird es wissen.
Raphael
2
Ich vermute, @LevReyzin würde auch die Antwort wissen ... und aus diesem Grund habe ich ursprünglich darüber nachgedacht, nach Cstheory zu fragen, aber ich denke, ich sollte helfen, diese neue Site zu erweitern.
Artem Kaznatcheev
Keine Antwort auf die Frage, aber dennoch hilfreich: [ citeulike.org/user/erelsegal-halevi/article/9275508 Ein universeller Kern für das Erlernen regulärer Sprachen]
Erel Segal-Halevi
Vielen Dank für den Link @Erel, aber ich verstehe nicht, wie es zusammenhängt. Kontorovichs Universalkern ist nicht effizient berechenbar, und das Lernmodell enthält keine Gegenbeispiele.
Artem Kaznatcheev

Antworten:

15

In seiner Antwort zu cstheory.SE verwies Lev Reyzin mich auf die These von Robert Schapire , die die in Abschnitt 5.4.5 an gebundenen Zugehörigkeitsabfragen verbessert. Die Anzahl der Gegenbeispielabfragen bleibt unverändert. Der von Schapire verwendete Algorithmus unterscheidet sich darin, was er nach einer Gegenbeispielabfrage tut.O(n2+nlogm)


Skizze der Verbesserung

Auf der höchsten Ebene zwingt Schapire aus Angluins Algorithmus, die zusätzliche Bedingung zu haben, dass für ein geschlossenes ( S , E , T ) und jedes s 1 , s 2S, wenn s 1s 2 ist, dann r o w ( s 1 ) r o w ( s 2 ) . Dies garantiert, dass | S |(S,E,T)(S,E,T)s1,s2Ss1s2row(s1)row(s2) und macht es auchtrivial,dieKonsistenz-Eigenschaft von Angluins Algorithmus zu erfüllen. Um dies zu gewährleisten, muss er die Ergebnisse eines Gegenbeispiels unterschiedlich behandeln.|S|n

Bei einem Gegenbeispiel fügte Angluin einfach z und alle seine Präfixe zu S hinzu . Schapire tut etwas Feineres, indem es stattdessen ein einzelnes Element e zu E hinzufügt . Dieses neue e bewirkt, dass ( S , E , T ) nicht im Sinne von Angluin geschlossen wird, und das Update, um den Abschluss zu erhalten, indem mindestens eine neue Zeichenfolge in S eingefügt wird, während alle Zeilen getrennt bleiben . Die Bedingung für e ist:zzSeEe(S,E,T)Se

s,sS,aΣs.trow(s)=row(sa)ando(δ(q0,se))o(δ(q0,sae))

oq0δessa

ezriz=piri0|pi|=i<|z|sipilogmko(δ(q0,skrk))o(δ(q0,sk+1rk+1)rk+1eE

Artem Kaznatcheev
quelle
5

Ich weiß nicht, ob meine Antwort noch relevant ist. Kürzlich wurde die Implementierung eines neuen Algorithmus namens Observation Pack oder unter bestimmten Umständen Discrimination Tree von Falk Howar beschrieben. Dieser Algorithmus ist wie L *, verwendet jedoch Rivest-Shapire oder eine andere Methode (siehe Steffen und Isberner), um die Zerlegung eines Gegenbeispiels zu handhaben. und es verwendet eine Datenstruktur, einen Unterscheidungsbaum (einen Binärbaum), um effizient ein "Sieben" zu machen, nämlich das Einfügen eines A-Übergangs (wobei A jedes Symbol des Alphabets ist) eines neuen Zustands, der gefunden wird, bis es keine Geschlossenheit gibt . Dieser Algorithmus existiert in zwei Versionen: OneGlobally und OneLocally, je nachdem, ob das in der Zerlegung festgelegte Suffix zu jeder Komponente hinzugefügt wird oder nicht (das Verhältnis hinter dem Algorithmus besteht darin, dass alle Präfixe in einer Komponente einem kurzen Präfix entsprechen und den gleichen Status im Ziel gemäß den gefundenen Suffixen darstellen zu diesem Zeitpunkt. Später wird mit einem neuen Gegenbeispiel ein neues Suffix gefunden, das mindestens zwei Präfixe derselben Komponente unterscheidet. Dies führt zu einer Aufteilung dieser Komponente in zwei Komponenten. Mit OneLocally gibt es viel weniger Mitgliedschaftsabfragen, aber die Anzahl der Äquivalenzabfragen kann bei großen Ziel-DFAs drastisch ansteigen. Vielmehr hat OneGlobally eine Anzahl von Mitgliedschaftsabfragen, die immer kleiner als L * (aber größer als OneLocally) ist, und eine ähnliche Anzahl von Äquivalenzabfragen wie L *. Später wird mit einem neuen Gegenbeispiel ein neues Suffix gefunden, das mindestens 2 Präfixe derselben Komponente unterscheidet. Dies führt zu einer Aufteilung dieser Komponente in zwei Komponenten. Mit OneLocally gibt es viel weniger Mitgliedschaftsabfragen, aber die Anzahl der Äquivalenzabfragen kann bei großen Ziel-DFAs drastisch ansteigen. Vielmehr hat OneGlobally eine Anzahl von Mitgliedschaftsabfragen, die immer kleiner als L * (aber größer als OneLocally) ist, und eine ähnliche Anzahl von Äquivalenzabfragen wie L *. Später wird mit einem neuen Gegenbeispiel ein neues Suffix gefunden, das mindestens 2 Präfixe derselben Komponente unterscheidet. Dies führt zu einer Aufteilung dieser Komponente in zwei Komponenten. Mit OneLocally gibt es viel weniger Mitgliedschaftsabfragen, aber die Anzahl der Äquivalenzabfragen kann bei großen Ziel-DFAs drastisch ansteigen. Vielmehr hat OneGlobally eine Anzahl von Mitgliedschaftsabfragen, die immer kleiner als L * (aber größer als OneLocally) ist, und eine ähnliche Anzahl von Äquivalenzabfragen wie L *.

Ich weiß, dass es auch einen anderen Algorithmus gibt: TTT-Algorithmus, der besser als das Observation Pack ist, aber ich weiß es nicht genau. Der TTT-Algorithmus sollte auf dem neuesten Stand sein

Umbert
quelle
Danke für diese Antwort! Haben Sie eine Papierreferenz für den Howar-Algorithmus und für TTT?
Artem Kaznatcheev
Dieses für Observation Pack Link Howar und dieses für TTT Algorithmus Link TTT Die Implementierung finden Sie in LearLib (Observation Pack heißt dort Discrimination Tree)
Umbert