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