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


33

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.m O ( m n 2 ) n - 1nmO(mn2)n1

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


Referencje i powiązane pytania


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

2
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:


15

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(n2+nlogm)


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 1 , s 2S s 1s 2 r o w ( s 1 ) r o w ( s 2 ) | S | n(S,E,T)(S,E,T)s1,s2Ss1s2row(s1)row(s2)|S|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 S e E e ( S , E , T ) S ezzSeEe(S,E,T)Se

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

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 .q 0 δ e s s aoq0δessa

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,z r i z = p i r i 0 | p i | = i < | z | s i p i log m k o ( δ ( q 0 , s k r k ) ) o ( δ ( q 0 , s k + 1 r k + 1 ) r kezriz=piri0|pi|=i<|z|sipilogmko(δ(q0,skrk))o(δ(q0,sk+1rk+1) eE.rk+1rozróż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 .mimi


5

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


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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.