Ist das Finden des regulären Mindestausdrucks ein NP-vollständiges Problem?

42

Ich denke an das folgende Problem: Ich möchte einen regulären Ausdruck finden, der einem bestimmten Satz von Zeichenfolgen entspricht (z. B. gültige E-Mail-Adressen) und nicht mit anderen übereinstimmt (ungültige E-Mail-Adressen).

Nehmen wir an, wir meinen mit regulären Ausdrücken eine wohldefinierte endliche Zustandsmaschine, ich kenne die genaue Terminologie nicht, aber wir stimmen einer Klasse erlaubter Ausdrücke zu.

Anstatt den Ausdruck manuell zu erstellen, möchte ich ihm eine Reihe positiver und eine Reihe negativer Beispiele geben.

Es sollte dann ein Ausdruck erstellt werden, der mit den + übereinstimmt, die - ablehnt und in einem bestimmten Sinne minimal ist (Anzahl der Zustände in den Automaten?).

Meine Fragen sind:

  • Wurde dieses Problem berücksichtigt, wie kann es konkreter definiert und effizient gelöst werden? Können wir es in polynomialer Zeit lösen? Ist es NP vollständig, können wir es irgendwie approximieren? Für welche Ausdrucksklassen würde es funktionieren? Ich würde mich über jeden Hinweis auf Lehrbücher, Artikel oder ähnliches freuen, die dieses Thema behandeln.
  • Hängt dies in irgendeiner Weise mit der Komplexität von Kolmogorov zusammen?
  • Hat dies etwas mit Lernen zu tun? Wenn der reguläre Ausdruck mit meinen Beispielen übereinstimmt, können wir aufgrund seiner Minimalität etwas über seine Verallgemeinerungskraft für noch nicht gesehene Beispiele sagen? Welches Minimalitätskriterium wäre dafür besser geeignet? Welches wäre effizienter? Hat dies irgendeinen Zusammenhang mit maschinellem Lernen? Auch hier wären alle Hinweise hilfreich ...

Entschuldigen Sie die unordentliche Frage ... Zeigen Sie mir in die richtige Richtung, um das herauszufinden. Vielen Dank !

László Kozma
quelle
2
Die folgende Seite scheint für den Lernaspekt
Tsuyoshi Ito
1
… oder vielleicht nicht. Es scheint sowieso viele Arbeiten zum DFA-Lernen zu geben.
Tsuyoshi Ito
2
Diese Frage wurde kürzlich im Community-Blog diskutiert .
Aaron Sterling

Antworten:

38

OPTkkP=NP

Zur Lernfrage: Kearns und Valiant haben bewiesen, dass Sie RSA in einen DFA codieren können. Selbst wenn die gekennzeichneten Beispiele aus der gleichmäßigen Verteilung stammen, würde die Verallgemeinerung auf zukünftige Beispiele (auch aus der gleichmäßigen Verteilung) die RSA brechen. Wir sind daher der Meinung, dass es im schlimmsten Fall nicht hilfreich ist, ein DFA (im PAC-Modell) zu erlernen, wenn Beispiele gekennzeichnet sind. Dies ist eines der klassischen kryptografischen Härteergebnisse für das Lernen.

Beide Probleme sind durch das, was wir als Occam's Razor Theorem bezeichnen, miteinander verflochten . Grundsätzlich heißt es, wenn wir eine Prozedur zum Finden der kleinsten Hypothese aus einer bestimmten Klasse haben, die mit einer Stichprobe übereinstimmt, die durch eine Hypothese aus derselben Klasse gekennzeichnet ist, können wir diese Klasse PAC lernen. Angesichts des RSA-Härteergebnisses würden wir erwarten, dass es im Allgemeinen schwierig sein würde, den kleinsten konsistenten DFA zu finden!

Um ein positives Lernergebnis zu erzielen, hat Angluin gezeigt, dass Sie einen DFA lernen können, wenn Sie Ihre eigenen Beispiele erstellen können, aber es erfordert die zusätzliche Kraft, fragen zu können: "Ist meine aktuelle Hypothese korrekt?" Dies war auch eine wegweisende Abhandlung zum Thema Lernen.

Die Beantwortung Ihrer anderen Frage hängt in der Tat mit der Komplexität von Kolmogorov zusammen, da das Lernproblem einfacher wird, wenn die kanonische Darstellung des Ziel-DFA eine geringe Komplexität aufweist.

Lev Reyzin
quelle
3
Du hast mich mit einem neueren, stärkeren Ergebnis geschlagen! Du solltest später eine bessere Antwort schreiben !! 1 !!
Tsuyoshi Ito
ups, tut mir Leid! Ich habe genug Zeit damit verbracht, DFA zu lernen, dass ich darauf springen musste :)
Lev Reyzin
1
Nur für den Fall, ich habe in meinem vorherigen Kommentar einen Scherz gemacht. Natürlich freue ich mich über eine bessere Antwort!
Tsuyoshi Ito
1
Mit anderen Worten, der Hauptunterschied zwischen diesem Problem und der regelmäßigen Minimierung von DFAs ist das Vorhandensein von negativen Beispielen, ja?
Suresh Venkat
1
ich verstehe nicht ohne negative beispiele hat die kleinste konsistente dfa nur 1
zustand
13

Ich beantworte die lernbezogenen Aspekte der Frage.

Dieses Problem scheint in der Literatur als "DFA-Lernen" bezeichnet zu werden.

Gold [Gol78] zeigte, dass es NP-vollständig ist, bei k ∈ℕ und zwei endlichen Mengen P und N von Zeichenketten zu entscheiden, ob es einen deterministischen endlichen Automaten (DFA) mit höchstens k Zuständen gibt, der jede Zeichenkette akzeptiert P und keine der Saiten in N . Der Artikel [PH01] scheint Probleme zu behandeln, die mit dieser Motivation zusammenhängen (möglicherweise gibt es noch viel mehr; dies ist gerade aufgetaucht, als ich versucht habe, relevante Artikel bei Google zu finden).

Verweise

[Gol78] E Mark Gold. Komplexität der Automatenidentifikation aus gegebenen Daten. Information and Control , 37 (3): 302–320, Juni 1978. http://dx.doi.org/10.1016/S0019-9958(78)90562-4

[PH01] Rajesh Parekh und Vasant Honavar. Lernen Sie DFA anhand einfacher Beispiele. Machine Learning , 44 (1–2): 9. – 35. Juli 2001. http://www.springerlink.com/content/kr2501h2442l8mk1/ http://www.cs.iastate.edu/~honavar/Papers/parekh- dfa.pdf

Tsuyoshi Ito
quelle
1
Danke für die Antwort, ich schaue mir die Referenzen an. Kann ich mehr als eine der besten Antworten auf dieser Site bewerten? :) Auch hier ist es mir peinlich, dass ich das gesamte Unterfeld "DFA-Lernen" verpasst habe, obwohl ich jahrelang maschinelles Lernen studiert habe.
László Kozma
@steve: Sie können nur eine Antwort akzeptieren , aber Sie können so viele Antworten abstimmen, wie Sie möchten.
Jukka Suomela
2
Beachten Sie, dass [Gold78] auch angibt, dass DFA in Polynomzeit gelernt werden kann (innerhalb des Lernrahmens der Identifikation im Grenzbereich). Siehe auch das kürzlich erschienene Buch über grammatikalische Inferenz ( pagesperso.lina.univ-nantes.fr/~cdlh/book_webpage.html ) für eine Übersicht.
mgalle
@mgalle: Danke für die zusätzlichen Informationen.
Tsuyoshi Ito
8

Während dieser Diskussion wurde angenommen, dass das Finden eines minimalen regulären Ausdrucks das Finden eines minimalen FSM darstellt, der die Sprache erkennt, aber dies sind zwei verschiedene Dinge. Wenn ich mich richtig erinnere, kann ein DFA in der Polynomzeit minimiert werden, während das Finden eines minimalen regulären Ausdrucks, der eine bestimmte reguläre Sprache darstellt, PSPACE-schwierig ist. Letzteres ist eines jener Ergebnisse, die zur Folklore der Automatentheorie gehören, deren Beweis jedoch nirgendwo zu finden ist. Ich denke, es ist eine Übung in Papadimitrous Buch.


quelle
1
Es ist richtig, dass die Länge des regulären Ausdrucks und die Anzahl der Zustände in DFA unterschiedliche Zielfunktionen sind. Ich habe auf die DFA-Minimierung geantwortet, weil sie eine schönere Eigenschaft hat (zum Beispiel gibt es eine eindeutige DFA mit der Mindestanzahl von Zuständen), und aufgrund der Art und Weise, in der die Frage gestellt wurde, hatte ich den Eindruck, dass die genaue Zielfunktion flexibel war.
Tsuyoshi Ito
Zufälliger Kommentar: Angesichts der Tatsache, dass ein regulärer Ausdruck der Größe f (n) durch einen NFA der Größe O (f (n)) simuliert werden kann, ähnelt das Minimieren regulärer Ausdrücke eher dem Minimieren von NFAs, was offensichtlich schwieriger ist.
Hsien-Chih Chang 張顯 張顯
Einiges davon wird in den Kommentaren zu @ keith's Antwort angesprochen
Lev Reyzin
2

Siehe auch diesen Stapelüberlaufpfosten. Das Buch, nach dem Sie suchen, scheint eine Einführung in die Computertheorie von Michael Sipser zu sein.

Du stellst ein paar verschiedene Fragen, also nimm sie nacheinander:

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

Nein, ist es nicht. Der Beitrag zum Stapelüberlauf beschreibt einen naiven n ^ 2-Algorithmus zum Reduzieren eines FSM auf seine minimale Größe. (Ausgehend von Stoppzuständen rückwärts arbeiten und Zustände kombinieren, die in einem genauen Sinne "identisch" sind.)

Anscheinend (ich bin dem Link nicht gefolgt) gibt es einen n log n-Algorithmus, um dies zu tun.

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

Wie Sie es formuliert haben, beschreibt Ihr Trainingssatz eine endliche Sprache. Trivialerweise werden endliche Sprachen einem FSM zugeordnet. Erstellen Sie für jede Zeichenfolge in Ihrer Sprache einen linearen Satz von Status, der mit einem Stoppstatus endet, ohne dass eine Schleife erforderlich ist. Führen Sie dann den FSM-Minimierungsalgorithmus auf dem resultierenden Computer aus.

Is this a good way to build a classifier?

Das würde ich nicht sagen. Die Minimierung des FSM ändert nichts an seiner Unterscheidungskraft - das ist der springende Punkt. Die minimale FSM akzeptiert genau den Satz von Zeichenfolgen wie jede äquivalente nicht minimale FSM.

Im Allgemeinen eignen sich reguläre Ausdrücke nicht zur Klassifizierung neuartiger Daten. Für jede endliche Trainingsmenge erhalten Sie eine RE / FSM, die nur mit den positiven Beispielen in dieser Menge übereinstimmt, ohne die Möglichkeit, auf neue Daten zu verallgemeinern. Ich habe noch nie einen Ansatz gesehen, der versucht, eine unendliche reguläre Sprache zu finden, die zu einem Trainingskorpus passt.

Für maschinelles Lernen würden Sie nach einem naiven Bayes-Klassifikator, einem Entscheidungsbaum, einem neuronalen Netzwerk oder etwas Exotischerem suchen. Russell und Norvigs künstliche Intelligenz: Ein moderner Ansatz ist so gut wie jeder andere Ort, um einen Überblick über Techniken des maschinellen Lernens (und vieles mehr) zu erhalten.

Gemeinschaft
quelle
2
Ich stimme dieser Antwort nicht zu. Wenn Sie einfach alle positiven Beispiele nehmen und eine FSM erstellen, die nur diese Beispiele und nichts anderes akzeptiert, ist Ihre FSM möglicherweise riesig. Andererseits ist der kleinste FSM, der alle positiven und keine negativen Beispiele akzeptiert, möglicherweise viel kleiner.
Jukka Suomela
3
Ich denke, die ursprüngliche Frage hat es ziemlich deutlich gemacht: "Ein Ausdruck, der mit den + übereinstimmt, die - ablehnt und in gewissem Sinne minimal ist".
Jukka Suomela
5
@keith die Unterscheidung zwischen deiner und meiner Antwort ist ziemlich subtil. Wenn Sie Ihre DFA erstellen, indem Sie neue Status für jede Zeichenfolge im Beispiel erstellen, verpflichten Sie sich zu einer möglicherweise anderen Sprache als der durch die minimale DFA dargestellten, die die positiven und negativen Beispiele trennt. Der Algorithmus zum Generieren einer DFA und zum anschließenden Minimieren macht das leider nicht!
Lev Reyzin
1
Ich bin mir nicht sicher, ob ich diesen Unterschied verstehe. Wenn wir eine Reihe positiver und negativer Beispiele haben, haben wir eine Familie von Sprachen, die alle diese Einschränkungen erfüllen. Für jede gibt es eine (Menge von) minimalen Dfas. Solange ich einen DFA mit minimaler Größe zurückgebe, spielt es keine Rolle, welche dieser Sprachen ich auswähle.
Suresh Venkat
1
Zum Lernen möchten Sie den kleinsten DFA auswählen, da dieser die beste Verallgemeinerungsfähigkeit aufweist. Die Prozedur von @ kieth wählt nicht den minimalen DFA für alle diese Sprachen aus, sondern nur den kleinsten für die Sprache, die sich für die Verwendung seiner Prozedur einsetzt.
Lev Reyzin