Czy istnieją ulepszenia w algorytmie Dany Angluin do uczenia się regularnych zestawów

W swojej zasadniczej pracy z 1987 roku Dana Angluin przedstawia algorytm wielomianowy do nauki DFA na podstawie zapytań członkowskich i teorii (kontrprzykłady do proponowanego DFA).

Pokazuje, że jeśli próbujesz nauczyć się minimalnego DFA ze stanami , a twój największy przykład ma długość , to musisz wykonać kwerendy członkostwa i co najwyżej kwerendy teoretyczne. $n$ $m$ $O(mn^2)$ $n - 1$

Czy nastąpiła znacząca poprawa liczby zapytań potrzebnych do nauki regularnego zestawu?

Referencje i powiązane pytania

Dana Angluin (1987) „Uczenie się regularnych zbiorów na podstawie zapytań i kontrprzykładów”, Infortmation and Computation 75: 87-106
Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym

algorithms learning-theory machine-learning

— Artem Kaznatcheev
źródło

Mamy nadzieję, że @DominikFreydenberger wpadnie w przyszłości. On będzie wiedział.

— Raphael

Podejrzewam, że @LevReyzin też zna odpowiedź ... i dlatego pierwotnie zastanawiałem się nad pytaniem o cstheory, ale myślę, że powinienem pomóc rozwinąć tę nową stronę.

— Artem Kaznatcheev

Nie jest to odpowiedź na pytanie, ale może być pomocna: [ citeulike.org/user/erelsegal-halevi/article/9275508 Uniwersalne jądro do nauki regularnych języków]

— Erel Segal-Halevi

dzięki za link @Erel, ale nie rozumiem, jak to się odnosi. Uniwersalne jądro Kontorowicza nie jest wydajnie obliczalne, a model uczenia się nie zawiera kontrprzykładów.

— Artem Kaznatcheev

Odpowiedzi:

W swojej odpowiedzi na cstheory.SE Lev Reyzin skierował mnie do tezy Roberta Schapire'a, która poprawia powiązanie z zapytaniami o członkostwo w rozdziale 5.4.5. Liczba zapytań kontrprzykładowych pozostaje niezmieniona. Algorytm wykorzystywany przez Schapire różni się tym, co robi po zapytaniu kontrprzykładowym. $O(n^2 + n\log m)$

Szkic ulepszenia

Na najwyższym poziomie, Schapire zmusza z algorytmu Angluina do spełnienia dodatkowego warunku, że dla zamkniętego i każdego jeśli to . To gwarantuje, że , a także sprawia, że konsystencja własność algorytmu Angluin za trywialne do spełnienia. Aby to zapewnić, musi inaczej traktować wyniki kontrprzykładu. $(S,E,T)$ $(S,E,T)$ $s_1, s_2 \in S$ $s_1 \neq s_2$ $row(s_1) \neq row(s_2)$ $|S| \leq n$

Biorąc kontrprzykład , Angluin prostu dodaje i wszystkie jej prefiksy do . Schapire robi coś bardziej subtelnego zamiast przez dodanie jednego elementu na . To nowe sprawi, że nie będą zamknięte w sensie Angluina, a aktualizacja umożliwiająca zamknięcie z wprowadzeniem co najmniej jednego nowego ciągu do przy jednoczesnym zachowaniu odrębności wszystkich wierszy. Warunkiem na jest: $z$ $z$ $S$ $e$ $E$ $e$ $(S,E,T)$ $S$ $e$

\exists s, s^{'} \in S, a \in Σ s.t r o w (s) = r o w (s^{'} a) and o (δ (q_{0}, s e)) \neq o (δ (q_{0}, s^{'} a e))

$\exists s, s' \in S, a \in \Sigma \quad \text{s.t} \quad row(s) = row(s'a) \; \text{and} \; o(\delta(q_0,se)) \neq o(\delta(q_0,s'ae))$

Gdzie jest funkcją wyjściową, jest stanem początkowym, a regułą aktualizacji prawdziwego „nieznanego” DFA. W otherwords, musi służyć jako świadka do odróżnienia przyszłość od . $o$ $q_0$ $\delta$ $e$ $s$ $s'a$

Aby to z , wykonujemy wyszukiwanie binarne, aby znaleźć podłańcuch taki, że itak, że zachowanie naszej domyślnej maszyny różni się w zależności od jednego znaku wejściowego. Bardziej szczegółowo, pozwalamy być ciągiem odpowiadającym stanowi osiągniętemu w naszej domniemanej maszynie, wykonując . Używamy wyszukiwania binarnego ( stąd pochodzi ), aby znaleźć taki, że . Innymi słowy, $e$ $z$ $r_i$ $z = p_ir_i$ $0 \leq |p_i| = i < |z|$ $s_i$ $p_i$ $\log m$ $k$ $o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$ $r_{k+1}$ rozróżnia dwa stany przypuszczał, że nasze maszyny znajdzie równoważne i tym samym spełnia warunek na , więc możemy go dodać do . $e$ $E$

— Artem Kaznatcheev
źródło

Nie wiem, czy moja odpowiedź jest nadal aktualna. Niedawno została opisana implementacja nowego algorytmu o nazwie Observation Pack lub w niektórych okolicznościach Drzewo Dyskryminacji autorstwa Falk Howar. Algorytm ten jest podobny do L *, ale używa Rivest-Shapire lub innej metody (patrz Steffen i Isberner) do obsługi przeciwnego przykładu rozkładu; i wykorzystuje strukturę danych, drzewo rozróżniania (drzewo binarne), aby skutecznie „przesiać”, a mianowicie wstawienie przejścia A (gdzie A jest każdym symbolem alfabetu) nowego stanu, dopóki nie zostanie zamknięta . Ten algorytm występuje w dwóch wersjach: OneGlobally i OneLocally w zależności od tego, czy przyrostek oparty na rozkładzie jest dodawany do każdego składnika, czy nie (stosunek za algorytmem polega na tym, że wszystkie przedrostki w składniku są równoważne krótkiemu przedrostkowi i reprezentują ten sam stan w celu zgodnie z znalezionymi przyrostkami w tej chwili. Później z nowym kontrprzykładem znaleziono nowy sufiks, który rozróżnia co najmniej 2 prefiksy tego samego komponentu. Powoduje to podział tego komponentu na dwa komponenty. W OneLocally jest znacznie mniej zapytań członkowskich, ale liczba równoważnych zapytań może drastycznie wzrosnąć przy dużym docelowym DFA. Zamiast tego OneGlobally ma liczbę zapytań członkowskich zawsze niższych niż L * (ale większych niż OneLocally) i podobną liczbę zapytań równoważności niż L * Później z nowym kontrprzykładem znaleziono nowy sufiks, który rozróżnia co najmniej 2 prefiksy tego samego komponentu. To powoduje podział tego komponentu na dwa komponenty). W OneLocally jest znacznie mniej zapytań członkowskich, ale liczba równoważnych zapytań może drastycznie wzrosnąć przy dużym docelowym DFA. Zamiast tego OneGlobally ma liczbę zapytań członkowskich zawsze niższych niż L * (ale większych niż OneLocally) i podobną liczbę zapytań równoważności niż L * Później z nowym kontrprzykładem znaleziono nowy sufiks, który rozróżnia co najmniej 2 prefiksy tego samego komponentu. To powoduje podział tego komponentu na dwa komponenty). W OneLocally jest znacznie mniej zapytań członkowskich, ale liczba równoważnych zapytań może drastycznie wzrosnąć przy dużym docelowym DFA. Zamiast tego OneGlobally ma liczbę zapytań członkowskich zawsze niższych niż L * (ale większych niż OneLocally) i podobną liczbę zapytań równoważności niż L *

Wiem, że istnieje również inny algorytm: algorytm TTT, który jest również lepszy niż pakiet obserwacyjny, ale nie znam go dobrze. Algorytm TTT powinien być najnowocześniejszy

— Umbert
źródło

Dziękuję za tę odpowiedź! Czy masz dokumentację dotyczącą algorytmu Howar i TTT?

— Artem Kaznatcheev

To do linku do pakietu obserwacyjnego Howar i to do linku do algorytmu TTT TTT Implementację można znaleźć w LearLib (pakiet obserwacyjny nazywa się tam Drzewo dyskryminacji)

— Umbert