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

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 !

$OPT^k$$k$$P = 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ść.

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

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.

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).