Indukcja języków regularnych

W teorii obliczeniowego uczenia się indukcja języków regularnych odnosi się do zadania nauczenia się formalnego opisu ( np. gramatyki) języka regularnego z danego zestawu przykładowych ciągów znaków. Chociaż E. Mark Gold wykazał, że nie każdego zwykłego języka można się nauczyć w ten sposób (patrz identyfikacja języka w limicie ), zbadano podejścia dla różnych podklas. Zostały one naszkicowane w tym artykule. Aby zapoznać się z bardziej ogólną gramatyką, zobacz Indukcja gramatyki .

Przykład

Język regularny definiuje się jako (skończony lub nieskończony) zestaw ciągów znaków , który można opisać za pomocą jednego z formalizmów matematycznych zwanych „ automatem skończonym ”, „ gramatyką regularną ” lub „ wyrażeniem regularnym ”, z których wszystkie mają taką samą moc wyrażania . Ponieważ ten ostatni formalizm prowadzi do najkrótszych zapisów, zostanie on tutaj wprowadzony i wykorzystany. Biorąc pod uwagę zbiór Σ symboli (inaczej alfabet), wyrażenie regularne może być dowolnym z

  • ∅ (oznaczający pusty zestaw ciągów),
  • ε (oznaczający zestaw singleton zawierający tylko pusty ciąg),
  • a (gdzie a jest dowolnym znakiem w Σ; oznacza zbiór singleton zawierający tylko ciąg jednoznakowy a ),
  • r + s (gdzie r i s to z kolei prostsze wyrażenia regularne; oznaczające sumę ich zbioru)
  • r ⋅ s (oznaczający zbiór wszystkich możliwych konkatenacji napisów ze zbioru r 's i s '),
  • r + (oznaczający zbiór n -krotnych powtórzeń ciągów ze zbioru r dla dowolnego n ≥1), lub
  • r * (podobnie oznacza zbiór n -krotnych powtórzeń, ale zawiera również pusty ciąg, postrzegany jako 0-krotne powtórzenie).

Na przykład, używając Σ = { 0,1 }, wyrażenie regularne (0+1+ε)⋅(0+1) oznacza zbiór wszystkich liczb binarnych z jedną lub dwiema cyframi (dozwolone zero wiodące), podczas gdy 1⋅( 0+1) * ⋅0 oznacza (nieskończony) zbiór wszystkich parzystych liczb binarnych (bez wiodących zer).

Biorąc pod uwagę zestaw ciągów (zwanych także „przykładami pozytywnymi”), zadaniem indukcji języka regularnego jest wymyślenie wyrażenia regularnego, które oznacza zbiór zawierający je wszystkie. Jako przykład, biorąc pod uwagę { 1, 10, 100 }, „naturalnym” opisem może być wyrażenie regularne 1⋅0 * , odpowiadające nieformalnej charakterystyce „ a 1, po której następuje dowolnie wiele (może nawet brak) 0es ”. Jednak (0+1) * a 1+(1⋅0)+(1⋅0⋅0) jest kolejnym wyrażeniem regularnym, oznaczającym największy (zakładając Σ={0,1}) i najmniejszy zbiór zawierający podane ciągi, nazywany trywialną nadgeneralizacją i niedouogólnieniem odpowiednio. Niektóre podejścia działają w rozszerzonym ustawieniu, w którym podany jest również zestaw ciągów „przykładów negatywnych”; następnie należy znaleźć wyrażenie regularne, które generuje wszystkie przykłady pozytywne, ale żadnego negatywnego.

Krata automatów

Częściowa kolejność automatów generujących ciągi 1, 10 i 100 (przykłady pozytywne). Dla każdego z negatywnych ciągów przykładowych 11, 1001, 101 i 0 górny zestaw generujących go automatów. Jedynymi automatami, które generują wszystkie { 1, 10, 100 }, ale żaden z { 11, 1001, 101, 0 }, są trywialne automaty dolne i odpowiadające wyrażeniu regularnemu 1⋅0 * .

Dupont i in. wykazali, że zbiór wszystkich strukturalnie kompletnych automatów skończonych generujących dany wejściowy zestaw przykładowych łańcuchów tworzy kratę , z trywialnym automatem niedogenerowanym i trywialnym automatem nadmiernie uogólnionym jako odpowiednio dolnym i górnym elementem. Każdy element tej sieci można otrzymać, rozkładając na czynniki automat niedouogólniony za pomocą odpowiedniej relacji równoważności .

Dla powyższego przykładowego zestawu łańcuchów { 1, 10, 100 }, rysunek pokazuje na dole niedorozwinięty automat A a,b,c,d w kolorze szarym , składający się ze stanów a , b , c i d . Na zbiorze stanów { a,b,c,d } istnieje w sumie 15 relacji równoważności, tworzących siatkę. Odwzorowanie każdej równoważności E na odpowiedni język automatu ilorazowego L ( A a, b, c, d / E ) uzyskuje pokazany na rysunku częściowo uporządkowany zestaw. Język każdego węzła jest oznaczony wyrażeniem regularnym. Język można rozpoznać za pomocą automatów ilorazowych z różnymi relacjami równoważności, z których wszystkie są pokazane poniżej węzła. Strzałka między dwoma węzłami wskazuje, że język niższego węzła jest właściwym podzbiorem języka wyższego węzła.

Jeśli podano zarówno dodatnie, jak i ujemne ciągi przykładowe, Dupont i in. zbuduj siatkę z pozytywnych przykładów, a następnie zbadaj granicę separacji między automatami, które generują jakiś negatywny przykład, a takimi, które tego nie robią. Najciekawsze są te automaty bezpośrednio pod granicą. Na rysunku pokazano granice separacji dla przykładowych łańcuchów ujemnych 11 ( zielony ), 1001 ( niebieski) , 101 ( cyjan ) i 0 ( czerwony ).

Coste i Nicolas przedstawiają własną metodę przeszukiwania sieci, którą odnoszą do paradygmatu przestrzeni wersji Mitchella . Aby znaleźć granicę separacji, używają algorytmu kolorowania wykresów na relacji nierówności stanu wywołanej negatywnymi przykładami. Później badają kilka relacji porządkujących na zbiorze wszystkich możliwych fuzji stanów.

Kudo i Shimbo wykorzystują reprezentację przez rozkłady na czynniki automatów, aby stworzyć unikalne ramy dla następujących podejść (naszkicowanych poniżej ):

Pokazano, że każde z tych podejść odpowiada określonemu rodzajowi relacji równoważności używanych do faktoryzacji.

Podchodzi do

k -języki odwracalne

Angluin rozważa tak zwane „ k -odwracalne” automaty regularne, to znaczy automaty deterministyczne, w których każdy stan można osiągnąć co najwyżej z jednego stanu, podążając łańcuchem przejściowym o długości k . Formalnie, jeśli Σ, Q i δ oznaczają odpowiednio alfabet wejściowy, zbiór stanów i funkcję przejścia automatu A , to A nazywa się k -odwracalnym, jeśli : 0 ∀ a ,..., a k ∈ Σ ∀ s 1 , s 00 2 ∈ Q : δ * ( s 1 , a ... a k ) = δ * ( s 2 , a ... a k ) ⇒ s 1 = s 2 , gdzie δ * oznacza homomorficzne rozszerzenie δ na dowolne słowa . Angluin podaje sześcienny algorytm do uczenia się najmniejszego k -język odwracalny z zadanego zestawu słów wejściowych; dla k = 0 algorytm ma nawet prawie liniową złożoność. Wymagana jednoznaczność stanu po k +1 danych symboli wymusza ujednolicenie stanów automatu, prowadząc tym samym do właściwego uogólnienia odmiennego od trywialnego automatu niedogeneralizowanego. Algorytm ten został wykorzystany do nauki prostych części składni języka angielskiego; później udostępniono wersję przyrostową. Innym podejściem opartym na k -odwracalnych automatach jest metoda grupowania ogonów .

Automaty następcze

Z danego zestawu ciągów wejściowych Vernadat i Richetin budują tak zwany automat następczy , składający się z jednego stanu dla każdego odrębnego znaku i przejścia między dwoma sąsiednimi stanami znaków. Na przykład pojedynczy zbiór danych wejściowych { aabbaabb } prowadzi do automatu odpowiadającego wyrażeniu regularnemu ( a + ⋅ b + ) * .

Rozszerzeniem tego podejścia jest metoda poprzednik-następnik , która uogólnia każde powtórzenie znaku bezpośrednio do Kleene + , a następnie zawiera dla każdego znaku zestaw możliwych poprzedników w jego stanie. Automaty następcze mogą dokładnie poznać klasę języków lokalnych . Ponieważ każdy język regularny jest homomorficznym obrazem języka lokalnego, gramatyk z poprzedniej klasy można się nauczyć podnosząc , jeśli odpowiedni (w zależności od zamierzonego zastosowania) homomorfizm jest zapewniony. W szczególności taki homomorfizm występuje dla klasy języków, których można się nauczyć metodą poprzednik-następnik. Możliwości uczenia się języków lokalnych można zredukować do poziomu k- języków odwracalnych.

Wczesne podejścia

Ilustracja lematu o pompowaniu dla automatów regularnych

Chomsky i Miller (1957) wykorzystali lemat o pompowaniu : odgadują część v ciągu wejściowego uvw i próbują zbudować odpowiedni cykl w automacie, który ma być nauczony; za pomocą zapytań o członkostwo pytają o odpowiednie k , który z łańcuchów uw , uvvw , uvvvw , ..., uv k w również należy do języka, którego mają się nauczyć, udoskonalając w ten sposób strukturę swojego automatu. W 1959 Solomonoff uogólnił to podejście do języków bezkontekstowych , które również są zgodne z lematem o pompowaniu .

Automaty okładkowe

Câmpeanu i in. naucz się automatu skończonego jako zwartej reprezentacji dużego skończonego języka. Mając taki język F , przeszukują tzw. automat okładkowy A taki, aby jego język L ( A ) obejmował F w następującym sensie: L ( A ) ∩ Σ ≤ l = F , gdzie l jest długością najdłuższego łańcucha w F , a Σ ≤ l oznacza zbiór wszystkich ciągów nie dłuższych niż ja . Jeśli taki automat okładki istnieje, F jest jednoznacznie określony przez A i l . Na przykład F = { ad , read , reread } ma l = 6 i automat okładki odpowiadający wyrażeniu regularnemu ( r ⋅ e ) * ⋅ a ⋅ d .

Dla dwóch ciągów x i y Câmpeanu i in. zdefiniuj x ~ y , jeśli xz ∈ F ⇔ yz ∈ F dla wszystkich ciągów z o długości takiej, że zarówno xz , jak i yz nie są dłuższe niż l . Na podstawie tej relacji, której brak przechodniości powoduje spore problemy techniczne, dają algorytm O ( n 4 ) do skonstruowania z F automat okładkowy A o minimalnej liczbie stanów. Co więcej, dla sumy, przecięcia i różnicy dwóch skończonych języków zapewniają one odpowiednie operacje na swoich automatach okładkowych. Păun i in. poprawić złożoność czasową do O ( n 2 ).

Resztkowe automaty

Pochodna Brzozowskiego (na czerwonym tle) ciągu słownikowego ustawionego względem „ con ”

Dla zbioru S strun i struny u , pochodna Brzozowskiego u −1 S jest zdefiniowana jako zbiór wszystkich pozostałych strun możliwych do uzyskania ze struny w S przez odcięcie jej przedrostka u (jeśli to możliwe), formalnie: u −1 S = { v ∈ Σ * : uv ∈ S } , por. zdjęcie. Denis i in. zdefiniuj automat resztkowy jako niedeterministyczny automat skończony A gdzie każdy stan q odpowiada pochodnej Brzozowskiego przyjętego języka L ( A ), formalnie: ∀ q ∈ Q ∃ u ∈Σ * : L ( A , q ) = u −1 L ( A ) , gdzie L ( A , q ) oznacza język przyjęty z q jako stan początkowy.

Pokazują one, że każdy język regularny jest generowany przez jednoznacznie określony minimalny automat resztkowy. Jego stany są ∪ -nierozkładalnymi pochodnymi Brzozowskiego i mogą być wykładniczo mniejsze niż minimalny automat deterministyczny. Co więcej, pokazują, że automatów resztkowych dla języków regularnych nie można nauczyć się w czasie wielomianowym, nawet przy założeniu optymalnych przykładowych danych wejściowych. Podają algorytm uczenia się dla automatów resztkowych i dowodzą, że uczy się on automatu z charakterystycznej próbki dodatnich i ujemnych ciągów wejściowych.

Nauka zapytań

Języków regularnych nie można nauczyć się w czasie wielomianowym, używając tylko zapytań o członkostwo lub używając tylko zapytań o równoważność. Jednak Angluin wykazał, że języków regularnych można się nauczyć w czasie wielomianowym za pomocą zapytań o członkostwo i zapytania o równoważność, i dostarczył algorytm uczenia się nazwany L*, który dokładnie to robi. Algorytm L* został później uogólniony, aby generować NFA ( niedeterministyczne automaty skończone ), a nie DFA ( deterministyczne automaty skończone ), za pośrednictwem algorytmu określanego jako NL*. Wynik ten został dalej uogólniony, a algorytm, który generuje AFA ( przemienne automaty skończone ) nazwany AL* został wymyślony. Należy zauważyć, że NFA może być wykładniczo bardziej zwięzły niż DFA, a AFA może być wykładniczo bardziej zwięzły niż NFA i podwójnie wykładniczo bardziej zwięzły niż DFA.

Zredukowane wyrażenia regularne

Brill definiuje zredukowane wyrażenie regularne jako dowolne z

  • a (gdzie a jest dowolnym znakiem w Σ; oznacza zbiór singleton zawierający tylko jednoznakowy ciąg a),
  • ¬ a (oznaczający dowolny inny pojedynczy znak w Σ z wyjątkiem a ),
  • • (oznaczający dowolny pojedynczy znak w Σ)
  • lub _ _ _ _ _ _ _ _ _ _ _ _
  • r ⋅ s (gdzie r i s to z kolei prostsze zredukowane wyrażenia regularne; oznaczające zbiór wszystkich możliwych konkatenacji napisów ze zbioru r i s ).

Mając wejściowy zestaw łańcuchów, buduje krok po kroku drzewo, w którym każda gałąź jest oznaczona zredukowanym wyrażeniem regularnym akceptującym przedrostek niektórych ciągów wejściowych, a każdy węzeł jest oznaczony zestawem długości akceptowanych przedrostków. Jego celem jest poznanie zasad poprawiania błędów ortograficznych w języku angielskim, a nie teoretyczne rozważania na temat przyswajalności zajęć językowych. W związku z tym używa heurystyki do przycinania nagromadzenia drzew, co prowadzi do znacznej poprawy czasu działania.

Aplikacje

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Induction_of_regular_languages&oldid=1141026903 ”