Czy znalezienie minimalnego wyrażenia regularnego jest problemem NP-zupełnym?

43

Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail).

Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam dokładnej terminologii, ale uzgodnijmy pewną klasę dozwolonych wyrażeń.

Zamiast ręcznie tworzyć wyrażenie, chcę dać mu zestaw pozytywnych i negatywnych przykładów.

Powinien wtedy znaleźć wyrażenie, które pasuje do +, odrzuca - i jest minimalne w ściśle określonym znaczeniu (liczba stanów w automatach?).

Moje pytania to:

  • Czy rozważono ten problem, jak można go zdefiniować w bardziej konkretny sposób i czy można go skutecznie rozwiązać? Czy możemy to rozwiązać w czasie wielomianowym? Czy NP jest kompletny, czy możemy jakoś go przybliżyć? Dla jakich klas wyrażeń to by działało? Byłbym wdzięczny za każdy wskaźnik do podręczników, artykułów lub takich, które omawiają ten temat.
  • Czy ma to jakiś związek ze złożonością Kołmogorowa?
  • Czy ma to jakiś związek z nauką? Jeśli wyrażenie regularne jest zgodne z moimi przykładami, ponieważ jest ono minimalne, czy możemy powiedzieć coś o jego mocy uogólniającej na jeszcze niewidzianych przykładach? Jakie kryterium minimalności byłoby do tego bardziej odpowiednie? Który byłby bardziej wydajny? Czy ma to jakiś związek z uczeniem maszynowym? Ponownie wszelkie wskazówki byłyby pomocne ...

Przepraszam za niechlujne pytanie ... Wskaż mi właściwy kierunek, aby to rozgryźć. Dzięki !

László Kozma
źródło
2
Następująca strona wydaje się być bardzo istotna w aspekcie uczenia się pytania: people.dsv.su.se/~henke/ML/MERLIN.html
Tsuyoshi Ito
1
… albo może nie. Zresztą wydaje się, że jest wiele prac dotyczących nauki DFA.
Tsuyoshi Ito
2
To pytanie zostało ostatnio omówione na blogu społeczności .
Aaron Sterling

Odpowiedzi:

39

OPTkkP=NP

Jeśli chodzi o pytanie edukacyjne: Kearns i Valiant udowodnili , że można zakodować RSA w DFA. Tak więc, nawet jeśli oznaczone przykłady pochodzą z rozkładu jednolitego, możliwość uogólnienia na przyszłe przykłady (również pochodzące z rozkładu jednolitego) złamałaby RSA. Dlatego uważamy, że w najgorszym przypadku oznakowanie przykładów nie pomaga w nauce DFA (w modelu PAC). Jest to jeden z klasycznych wyników twardości kryptograficznej do nauki.

Oba te problemy są ze sobą powiązane ze względu na to, co nazywamy twierdzeniem Razora . Zasadniczo stwierdza, że ​​jeśli mamy procedurę znajdowania najmniejszej hipotezy z danej klasy, która jest spójna z próbką oznaczoną hipotezą z tej samej klasy, możemy PAC nauczyć się tej klasy. Biorąc pod uwagę wynik twardości RSA, spodziewalibyśmy się, że znalezienie najmniejszego spójnego DFA byłoby ogólnie trudne!

Aby dodać pozytywny wynik uczenia się, Angluin pokazał , że możesz nauczyć się DFA, jeśli możesz wymyślić własne przykłady, ale wymaga to dodatkowej mocy, by móc zapytać „czy moja obecna hipoteza jest poprawna?” Był to także kluczowy artykuł w nauce.

Aby odpowiedzieć na inne pytanie, wszystko to jest rzeczywiście związane ze złożonością Kołmogorowa, ponieważ problem uczenia się staje się łatwiejszy, gdy kanoniczna reprezentacja docelowego DFA ma niską złożoność.

Lew Reyzin
źródło
3
Pokonałeś mnie nowszym, silniejszym rezultatem! Lepiej odpowiedz później !! 1 !!
Tsuyoshi Ito
UPS przepraszam! Spędziłem wystarczająco dużo czasu na nauce DFA, że musiałem na to wskoczyć :)
Lev Reyzin
1
Na wszelki wypadek żartowałem w poprzednim komentarzu. Oczywiście cieszę się, że widzę lepszą odpowiedź!
Tsuyoshi Ito
1
innymi słowy, kluczową różnicą między tym problemem a regularną minimalizacją DFA jest obecność negatywnych przykładów, tak?
Suresh Venkat
1
Nie rozumiem. bez negatywnych przykładów najmniejsza spójna dfa ma tylko 1 stan - stan akceptacji, który wskazuje na siebie ...
Lev Reyzin
13

Odpowiadam na pytania związane z uczeniem się.

Ten problem wydaje się w literaturze nazywany „uczeniem się DFA”.

Złoto [Gol78] pokazało, że NP jest kompletne, aby zadecydować, biorąc pod uwagę k ∈ℕ oraz dwa zbiory skończone P i N ciągów, czy istnieje deterministyczny automat skończony (DFA) z co najwyżej k stanami, które przyjmują każdy ciąg w P i żaden z ciągów w N . Artykuł [PH01] wydaje się omawiać problemy związane z tą motywacją (może być ich znacznie więcej; pojawiło się to, gdy próbowałem znaleźć odpowiednie artykuły w Google).

Referencje

[Gol78] E Mark Gold. Złożoność automatycznej identyfikacji na podstawie danych. Informacje i Kontroli , 37 (3): 302-320, June 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh i Vasant Honavar. Uczenie się DFA na prostych przykładach. Machine Learning , 44 (1–2): 9–35, lipiec 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

Tsuyoshi Ito
źródło
1
Dzięki za odpowiedź, patrzę na referencje. Czy mogę głosować na więcej niż jedną najlepszą odpowiedź na tej stronie? :) Ponownie jestem zawstydzony, że przegapiłem całe subpole „DFA learning”, mimo że przez lata studiowałem uczenie maszynowe.
László Kozma
@steve: Możesz zaakceptować tylko jedną odpowiedź, ale możesz głosować na tyle odpowiedzi, ile chcesz.
Jukka Suomela
2
Zauważ, że [Gold78] stwierdza również, że DFA można się nauczyć w czasie wielomianowym (w ramach uczenia się w ramach identyfikacji w limicie). Zobacz także ostatnią książkę na temat wnioskowania gramatycznego ( pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html ).
mgalle
@mgalle: Dziękujemy za dodatkowe informacje.
Tsuyoshi Ito,
8

W trakcie tej dyskusji zakładano, że znalezienie minimalnego wyrażenia regularnego sprowadza się do znalezienia minimalnego FSM rozpoznającego język, ale są to dwie różne rzeczy. Jeśli dobrze pamiętam, DFA można zminimalizować w czasie wielomianowym, podczas gdy znalezienie minimalnego wyrażenia regularnego reprezentującego dany język regularny jest trudne dla PSPACE. Ta ostatnia jest jednym z tych wyników, które należą do folkloru teorii automatów, ale których dowodów nigdzie nie można znaleźć. Myślę, że jest to określone w książce Papadimitrou jako ćwiczenie.


źródło
1
Prawdą jest, że długość wyrażenia regularnego i liczba stanów w DFA to różne funkcje celu. Odpowiedziałem na temat minimalizacji DFA, ponieważ ma ona ładniejszą właściwość (na przykład, istnieje unikalny DFA z minimalną liczbą stanów) i po sposobie, w jaki pytanie zostało zadane, odniosłem wrażenie, że dokładna funkcja celu była elastyczna.
Tsuyoshi Ito,
Komentarz losowy: biorąc pod uwagę fakt, że wyrażenie regularne o wielkości f (n) może być symulowane przez NFA o rozmiarze O (f (n)), minimalizacja wyrażeń regularnych jest bardziej jak minimalizowanie NFA, co jest oczywiście trudniejsze.
Hsien-Chih Chang 張顯 之
niektóre z nich zostały omówione w komentarzach do odpowiedzi @
keitha
2

Zobacz także ten post przepełnienia stosu. Książka, której szukasz, wydaje się być Wstępem do teorii obliczeń Michaela Sipsera.

Zadajesz kilka różnych pytań, więc zadawaj je pojedynczo:

Is finding a minimal Finite State Machine for a language L NP-complete?

Nie, nie jest. Wpis Przepełnienie stosu omawia naiwny algorytm redukcji ^ ^ do minimalnego rozmiaru FSM. (Pracując wstecz od stanów stop, łącz stany, które są „identyczne” w konkretnym sensie.)

Najwyraźniej (nie podążyłem za linkiem) istnieje algorytm, aby to zrobić.

I have a training set of strings, how do I find the minimal FSM 
that separates the good examples from the bad?

Jak to określiłeś, twój zestaw treningowy opisuje skończony język. Języki skończone odwzorowują w trywialny sposób na FSM - utwórz liniowy zestaw stanów kończących się stanem zatrzymania dla każdego łańcucha w twoim języku, bez potrzeby zapętlania. Następnie uruchom algorytm minimalizacji FSM na powstałej maszynie.

Is this a good way to build a classifier?

Nie powiedziałbym tak. Minimalizacja FSM nie zmienia jego mocy dyskryminacyjnej - o to właśnie chodzi. Minimalny FSM akceptuje dokładnie zestaw ciągów znaków jako każdy równoważny nie-minimalny FSM.

Zasadniczo wyrażenia regularne nie są odpowiednie do klasyfikowania nowych danych. Dla każdego skończonego zestawu treningowego otrzymasz RE / FSM, który pasuje tylko do pozytywnych przykładów w tym zestawie, bez możliwości uogólnienia na nowe dane. Nigdy nie widziałem podejścia, które próbuje znaleźć nieskończony, regularny język pasujący do korpusu szkoleniowego.

Do uczenia maszynowego szukasz czegoś naiwnego klasyfikatora Bayesa, drzewa decyzyjnego, sieci neuronowej lub czegoś bardziej egzotycznego. Sztuczna inteligencja Russella i Norviga : nowoczesne podejście jest tak samo dobrym miejscem, jak każdy, aby znaleźć przegląd technik uczenia maszynowego (i wiele, wiele innych).

Społeczność
źródło
2
Nie zgadzam się z tą odpowiedzią. Jeśli po prostu weźmiesz wszystkie pozytywne przykłady i skonstruujesz FSM, który akceptuje tylko te przykłady i nic więcej, twój FSM może być ogromny. Z drugiej strony najmniejszy FSM, który akceptuje wszystkie pozytywne przykłady i nie ma negatywnych przykładów, może być znacznie mniejszy.
Jukka Suomela
3
Myślę, że pierwotne pytanie było dość jasne: „wyrażenie, które pasuje do tych +, odrzuca je i jest minimalne w ściśle określonym znaczeniu”.
Jukka Suomela
5
@ z rozróżnieniem między twoją odpowiedzią a moją jest dość subtelna. Kiedy budujesz swoją DFA, tworząc nowe stany dla każdego ciągu w próbce, zobowiązujesz się do użycia innego języka niż ten reprezentowany przez minimalną DFA oddzielającą przykłady pozytywne i negatywne. więc algorytm generowania dfa, a następnie minimalizowania go niestety nie robi tego!
Lew Reyzin
1
Nie jestem pewien, czy rozumiem to rozróżnienie. Jeśli mamy zbiór pozytywnych i negatywnych przykładów, mamy rodzinę języków, które spełniają te ograniczenia. dla każdego istnieje (zestaw) minimalnych plików dfas. Tak długo, jak zwracam DFA o minimalnym rozmiarze, jak ważne jest, który język wybrać.
Suresh Venkat
1
Do nauki chcesz wybrać najmniejszy DFA, ponieważ ma on najlepszą zdolność do generalizacji. Procedura @ kietha nie wybierze minimalium DFA dla wszystkich tych języków, tylko najmniejszego dla języka, który zobowiązuje się do korzystania z jego procedury.
Lew Reyzin