Gibt es Verbesserungen Dana Angluin-Algorithmus für das lernen regelmäßigen sets

Question

In Ihrem 1987 wegweisenden Dana Angluin präsentiert eine Polynom-Zeit-Algorithmus für das lernen eines DFA-Mitgliedschaft Abfragen und Theorie Abfragen (Gegenbeispiele zu einer vorgeschlagenen DFA).

Sie zeigt, dass, wenn Sie versuchen zu lernen, ein minimaler DFA mit $n$ Mitgliedstaaten, und Ihre größte countexample ist der Länge $m$, dann brauchen Sie, um $O(mn^2)$ Mitgliedschaft-Abfragen und höchstens $n - 1$ - Theorie-Abfragen.

Es wurden deutliche Verbesserungen bei der Anzahl der Anfragen erforderlich zu lernen, einen normalen Satz?

---

Referenzen und Verwandte Fragen

• Dana Angluin (1987) "Lernen Regelmäßigen Sets von Abfragen und Gegenbeispiele", Informationen und Berechnungen 75:87-106

• Untere Grenzen für das lernen in der Mitgliedschaft Abfrage und Gegenbeispiel Modell

Answer 1

In seine Antwort auf cstheory.SE Lev Reyzin verwies mich an Robert Schapire ' s thesis das verbessert die gebunden an $O(n^2 + n\log m)$ Mitgliedschaft-Abfragen im Abschnitt 5.4.5.Die Anzahl der Gegenbeispiel-Abfragen unverändert bleibt.Der Algorithmus Schapire verwendet, unterscheidet sich in dem, was es tut, nach einem Gegenbeispiel Abfrage.

---

Skizze der Verbesserung

Auf der höchsten Ebene, Schapire-Streitkräfte $(S,E,T)$ von Angluin ' s Algorithmus, um die zusätzlichen Bedingung, dass für ein geschlossenes $(S,E,T)$ und jedes $s_1, s_2 \in S$, wenn $s_1 eq s_2$, dann $row(s_1) eq Zeile(s_2)$.Dies garantiert, dass $|S| \leq n$ und macht auch die Konsistenz Eigentum von Angluin-Algorithmus trivial zu befriedigen.Um dies zu gewährleisten, hat er Griff die Ergebnisse ein Gegenbeispiel anders.

Gegeben ein Gegenbeispiel $z$, Angluin einfach Hinzugefügt, $z$ und alle seine Präfixe zu $S$.Schapire, tut etwas subtiler, indem Sie stattdessen das hinzufügen einer einzigen element $e$ auf $E$.Diese neue $e$ wird $(S,E,T)$ nicht geschlossen in Angluin den Sinn und das update auf die Schließung mit der Einführung mindestens eine neue Zeichenfolge $S$, während alle Zeilen deutlich.Die Bedingung auf $e$ ist:

$$\existiert s, s' \in S, a \in \Sigma \quad ext{s.t} \quad Zeile(N) = row(s ' a) \; ext{und} \;o(\delta(q_0,se)) eq o(\delta(q_0,s'ae))$$

Wobei $a$ ist die Ausgang-Funktion, $q_0$ ist der erste Staat, und $\delta$ der Regel aktualisieren des wahren "unbekannten" DFA.In otherwords, $e$ muß als Zeuge dienen zu unterscheiden, die Zukunft von $s$ von $s ' a$.

Um herauszufinden, diese $e$ von $z$, wir tun eine binäre Suche, um herauszufinden, ein substring $r_i$, so dass $z = p_ir_i$ und $0 \leq |p_i| = i < |z|$, so dass das Verhalten unserer vermutete-Maschine unterscheidet sich basierend auf einer eingegebenen Zeichen.Im detail lassen wir $s_i$ die Zeichenkette entsprechend dem Stand erreichte Sie in unserer vermutete, der Maschine, indem Sie die folgenden $p_i$.Wir verwenden binäre Suche (dies ist, wo die $\log m$ kommt) zu finden, ein $k$, so dass $o(\delta(q_0,s_kr_k)) eq o(\delta(q_0,s_{k+1}r_{k+1})$.In anderen Worten, $r_{k+1}$ unterscheidet zwei Zustände, die unser vermutete Maschinen findet äquivalent und damit erfüllt Sie die Bedingung auf $e$, also fügen wir es auf $E$.

Answer 2

Ich weiß nicht, ob meine Antwort noch relevant ist. Kürzlich wurde die Umsetzung eines neuen Algorithmus bezeichnet, der als Beobachtungspaket oder unter bestimmten Umständen durch Falk Howar Diskriminierungsbaum bezeichnet wird. Dieser Algorithmus ist wie L*, aber verwenden Sie Rivest-Form oder eine andere Methode (siehe Steffen und Isberner) für die Zersetzung des Griffs für das Griff. und es verwendet eine Datenstruktur, einen Diskriminierungsbaum (ein binärer Baum), um effizient zu einem "sieben" zu machen, nämlich die Einführung einer A-Übersetzung (wobei a jedes Symbol des Alphabets ist) eines neuen Zustand . Dieser Algorithmus existiert in zwei Versionen: einglobal und onelokal, je nachdem, ob das in der Zersetzung gegründete Suffix zu jeder Komponente hinzuge Im Ziel des zu diesem Zeitpunkts gefundenen Suffixe. Später mit einem neuen Gegenbeispiel wird ein neues Suffix festgestellt, dass mindestens 2 Präfixe derselben Komponente unterscheidet. Dies verursacht eine Spaltung dieser Komponente in zwei Komponenten). Mit onelozentral gibt es weitaus weniger Mitgliederabfrage, aber die Anzahl der Äquivalenzabfragen kann mit dem großen Ziel -DFA drastisch zunehmen. Vielmehr hat einglobal eine Reihe von Mitgliedsabfragen, die immer niedriger als L* (aber größer als onelokal) und eine ähnliche Anzahl von Äquivalenzen -Abfragen als L*

Ich weiß, dass dies auch ein weiterer Algorithmus existiert: TTT -Algorithmus, der besser als das Beobachtungspaket ist, aber ich habe keine gute Kenntnis darüber. TTT -Algorithmus sollte der Stand der Technik sein