Ist es einem Computer möglich, einen regulären Ausdruck anhand von vom Benutzer bereitgestellten Beispielen zu „lernen“?

94

Ist es einem Computer möglich, einen regulären Ausdruck anhand von vom Benutzer bereitgestellten Beispielen zu "lernen"?

Zu klären:

  • Ich möchte keine regulären Ausdrücke lernen.
  • Ich möchte ein Programm erstellen, das einen regulären Ausdruck aus Beispielen "lernt", die von einem Benutzer interaktiv bereitgestellt werden, möglicherweise durch Auswahl von Teilen aus einem Text oder Auswahl von Anfangs- oder Endmarkierungen.

Ist es möglich? Gibt es Algorithmen, Schlüsselwörter usw., für die ich Google verwenden kann?

EDIT : Vielen Dank für die Antworten, aber ich bin nicht an Tools interessiert, die diese Funktion bieten . Ich suche nach theoretischen Informationen wie Artikeln, Tutorials, Quellcode und Namen von Algorithmen, damit ich etwas für mich selbst erstellen kann.

Daniel Rikowski
quelle
4
Ich bin überrascht, dass niemand Regex :: PreSuf
Tripleee

Antworten:

43

Das Buch Eine Einführung in die rechnergestützte Lerntheorie enthält einen Algorithmus zum Lernen eines endlichen Automaten. Da jede reguläre Sprache einem endlichen Automaten entspricht, ist es möglich, einige reguläre Ausdrücke von einem Programm zu lernen. Kearns und Valiant zeigen einige Fälle, in denen es nicht möglich ist, einen endlichen Automaten zu lernen. Ein verwandtes Problem ist das Lernen versteckter Markov-Modelle , bei denen es sich um probabilistische Automaten handelt, die eine Zeichenfolge beschreiben können. Beachten Sie, dass die meisten modernen "regulären Ausdrücke", die in Programmiersprachen verwendet werden, tatsächlich stärker als reguläre Sprachen sind und daher manchmal schwerer zu lernen sind.

Yuval F.
quelle
42

Ja, es ist möglich, wir können reguläre Ausdrücke aus Beispielen generieren (Text -> gewünschte Extraktionen). Dies ist ein funktionierendes Online-Tool, das die Aufgabe erfüllt: http://regex.inginf.units.it/

Das Online-Tool Regex Generator ++ generiert einen Regex aus den bereitgestellten Beispielen mithilfe eines GP-Suchalgorithmus. Der GP-Algorithmus basiert auf einer multiobjektiven Fitness, die zu einer höheren Leistung und einer einfacheren Lösungsstruktur führt (Occam's Razor). Dieses Tool ist eine demostrative Anwendung des Machine Lerning Lab der Universität Triest (Università degli studi di Trieste). Bitte schauen Sie sich das Video-Tutorial hier an .

Dies ist ein Forschungsprojekt , so dass Sie über Algorithmen lesen hier .

Erblicken! :-)

Das Finden einer aussagekräftigen Regex / Lösung aus Beispielen ist nur dann möglich, wenn die bereitgestellten Beispiele das Problem gut beschreiben. Betrachten Sie diese Beispiele, die eine Extraktionsaufgabe beschreiben. Wir suchen nach bestimmten Artikelcodes. Die Beispiele sind Text / Extraktions-Paare:

"The product code is 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Ein (menschlicher) Typ, der sich die Beispiele ansieht, kann sagen: "Die Artikelcodes sind Dinge wie \ d ++ - 345 [AB]."

Wenn der Artikelcode freizügiger ist, wir jedoch keine anderen Beispiele angegeben haben, haben wir keine Beweise, um das Problem gut zu verstehen. Wenn die vom Menschen generierte Lösung \ d ++ - 345 [AB] auf den folgenden Text angewendet wird, schlägt dies fehl:

"On the back of the item there is a code: 966-347Z"

Sie müssen andere Beispiele angeben, um besser beschreiben zu können, was eine Übereinstimmung ist und was keine gewünschte Übereinstimmung ist: --ie:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Die Telefonnummer ist keine Produkt-ID, dies kann ein wichtiger Beweis sein.

Fabiano Tarlao
quelle
4
Dies sollte die beste Antwort sein. Es ist möglich, und das zeigt es. Die Quelle ist hier verfügbar: github.com/MaLeLabTs/RegexGenerator
rjurney
Ihr Beispiel für die Produktcodes zeigt, warum der Mensch die Spezifikation für Produktcodes nachschlagen und den regulären Ausdruck basierend auf der Spezifikation schreiben sollte, anstatt zu versuchen, den regulären Ausdruck aus einem begrenzten Satz von Beispielproduktcodes abzuleiten (unabhängig davon, ob eine Person oder Ein Programm versucht, auf den regulären Ausdruck zu schließen.
Jan Goyvaerts
2
Dies ist der richtige Weg, um Dinge zu tun. Mein Beispiel ist nur eine Möglichkeit, das Problem konzeptionell zu erklären. Manchmal gibt es keine Spezifikation, oder der Typ ist einfach nicht in der Lage, den regulären Ausdruck (mangelndes Wissen) selbst zu schreiben.
Fabiano Tarlao
2
Der Artikel "Inferenz regulärer Ausdrücke für die Textextraktion
mimmuz
3
Dies ist ein ausgezeichnetes Projekt und eine fantastische Demonstration der Kraft der genetischen Programmierung, gut gemacht!
rcgeorge23
36

Kein Computerprogramm wird jemals in der Lage sein, einen aussagekräftigen regulären Ausdruck zu generieren, der ausschließlich darauf basiert auf einer Liste gültiger Übereinstimmungen . Lass mich dir zeigen warum.

Angenommen, Sie geben die Beispiele 111111 und 999999 an, falls der Computer Folgendes generiert:

  1. Eine Regex, die genau diesen beiden Beispielen entspricht: (111111|999999)
  2. Ein Regex mit 6 identischen Ziffern (\d)\1{5}
  3. Ein Regex mit 6 Einsen und Neunen [19]{6}
  4. Ein Regex, der mit 6 Ziffern übereinstimmt \d{6}
  5. Eine der oben genannten drei mit Wortgrenzen, z \b\d{6}\b
  6. Eine der ersten drei, denen keine Ziffer vorangestellt oder gefolgt ist, z (?<!\d)\d{6}(?!\d)

Wie Sie sehen, gibt es viele Möglichkeiten, Beispiele in einen regulären Ausdruck zu verallgemeinern. Die einzige Möglichkeit für den Computer, einen vorhersehbaren regulären Ausdruck zu erstellen, besteht darin, dass Sie alle möglichen Übereinstimmungen auflisten müssen. Dann könnte es ein Suchmuster erzeugen, das genau diesen Übereinstimmungen entspricht.

Wenn Sie nicht alle möglichen Übereinstimmungen auflisten möchten, benötigen Sie eine übergeordnete Beschreibung. Genau dafür sollen reguläre Ausdrücke sorgen. Anstatt eine lange Liste mit 6-stelligen Zahlen anzugeben, weisen Sie das Programm einfach an, mit "sechs Ziffern" übereinzustimmen. In der Syntax regulärer Ausdrücke wird dies zu \ d {6}.

Jede Methode zur Bereitstellung einer übergeordneten Beschreibung, die so flexibel ist wie reguläre Ausdrücke, ist auch so komplex wie reguläre Ausdrücke. Alle Tools wie RegexBuddy können das Erstellen und Testen der allgemeinen Beschreibung vereinfachen. Anstatt die knappe Syntax für reguläre Ausdrücke direkt zu verwenden, können Sie mit RegexBuddy einfache englische Bausteine ​​verwenden. Es kann jedoch keine allgemeine Beschreibung für Sie erstellen, da es nicht auf magische Weise wissen kann, wann es Ihre Beispiele verallgemeinern sollte und wann nicht.

Es ist sicherlich möglich, ein Tool zu erstellen, das Beispieltext zusammen mit den vom Benutzer bereitgestellten Richtlinien verwendet, um einen regulären Ausdruck zu generieren. Der schwierige Teil beim Entwerfen eines solchen Tools besteht darin, wie der Benutzer nach den benötigten Leitinformationen gefragt wird, ohne dass das Tool schwieriger zu erlernen ist als reguläre Ausdrücke selbst und ohne das Tool auf allgemeine Regex-Jobs oder einfache reguläre Ausdrücke zu beschränken.

Jan Goyvaerts
quelle
Sie haben Recht, viele Lernalgorithmen, die ich nach dem Posten meiner Frage gefunden habe, erfordern positive und negative Informationen. Soweit ich weiß, ist eine explizite "Beschreibung auf höherer Ebene" nicht erforderlich, da der Benutzer diese durch Beantwortung von Fragen bereitstellt.
Daniel Rikowski
Wenn ein Tool Fragen stellt, bildet die Kombination der Fragen und der gegebenen Antworten die übergeordnete Beschreibung. Die Qualität solcher Tools hängt weitgehend von den gestellten Fragen ab.
Jan Goyvaerts
Das ist dumm, denn wenn Sie ein anderes Beispiel angegeben haben, können Sie einige dieser Möglichkeiten ausschließen. Ein weiteres Beispiel beseitigt mehr.
Cris
2
@Cris: Das Prinzip bleibt bestehen, unabhängig davon, wie viele Proben Sie bereitstellen. Es ändert einfach die Möglichkeiten. Durch Hinzufügen von 123456 werden beispielsweise # 2 zu (\ d) \ 1 {5} | 123456 und # 3 zu [19] {6} | 123456 geändert. Oder es könnte # 3 in [1-69] {6} ändern. Es könnte sogar sein, dass das gewünschte Muster mit 6 identischen Ziffern oder 6 Ziffern übereinstimmt, wobei jede Ziffer eine Nummer größer als die vorhergehende Ziffer ist. Selbst wenn Sie 10.000 Beispiele mit 6-stelligen Zahlen bereitstellen, kann das Programm ohne zusätzliche Anweisungen des Benutzers nicht zwischen Nr. 1, Nr. 4, Nr. 5 oder Nr. 6 unterscheiden.
Jan Goyvaerts
Ich bin der Meinung, dass dieses Problem leicht wie folgt gelöst werden kann: Das Programm versucht, so allgemein wie möglich zu sein (im Rahmen der Vernunft) und gibt Ihnen dann Beispiele für andere Dinge, von denen es glaubt, dass sie übereinstimmen würden. Indem Sie den vorgeschlagenen Übereinstimmungen einfach "Ja" und "Nein" sagen, können Sie ihm helfen, die Grenzen dessen zu verstehen, was Sie tatsächlich erfassen möchten. Ich würde gerne ein Tool in einem Texteditor sehen, das dieses Konzept verwendet und Übereinstimmungen aus der aktuell geöffneten Datei vorschlägt.
Jon McClung
9

Ja, es ist sicherlich "möglich"; Hier ist der Pseudocode:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

Das Problem ist, dass es unendlich viele Regexs gibt, die einer Liste von Beispielen entsprechen. Dieser Code bietet den einfachsten / dümmsten regulären Ausdruck in der Menge und stimmt im Grunde mit allem in der Liste der positiven Beispiele überein (und nichts anderes, einschließlich eines der negativen Beispiele).

Ich nehme an, die eigentliche Herausforderung wäre es, den kürzesten regulären Ausdruck zu finden, der allen Beispielen entspricht, aber selbst dann müsste der Benutzer sehr gute Eingaben machen, um sicherzustellen, dass der resultierende Ausdruck "der richtige" ist.

Daniel LeCheminant
quelle
3
Es wird interessant, wenn der Benutzer positive und negative Proben eingibt . Der Regex müsste mit den positiven Stichproben übereinstimmen und nicht mit den negativen.
user55400
1
@ Thomas: Meins passt zu allen Beispielen und sonst nichts!
Daniel LeCheminant
@blixtor - Eigentlich ist es ganz einfach. Fügen Sie einfach kein negatives Beispiel in die konstruierte Regex ein, und sie werden abgelehnt. Denken Sie daran, dass der Code, den der Code erstellt, nur einem positiven Beispiel entspricht. negative Beispiele (und alles andere) sind per Definition ausgeschlossen!
Daniel LeCheminant
Daniel hat recht. Ohne eine übergeordnete Beschreibung ist eine Liste von Alternativen alles, was aus einer Liste von Beispielen konsistent und genau abgeleitet werden kann.
Jan Goyvaerts
6

Ich glaube, der Begriff ist "Induktion". Sie möchten eine reguläre Grammatik einführen.

Ich denke nicht, dass es mit einer endlichen Reihe von Beispielen (positiv oder negativ) möglich ist. Aber wenn ich mich richtig erinnere, kann es gemacht werden, wenn es ein Oracle gibt, das konsultiert werden kann. (Grundsätzlich müsste das Programm dem Benutzer Ja / Nein-Fragen stellen lassen, bis es zufrieden ist.)

Jay Kominek
quelle
Ja, das möchte ich tun, frage den Benutzer interaktiv.
Daniel Rikowski
Die Referenzen von Yuval F scheinen das zu sein, was ich mir vorgestellt habe. Ich würde vorschlagen, sie sich anzusehen.
Jay Kominek
5

Vielleicht möchten Sie ein bisschen mit dieser Seite spielen, sie ist ziemlich cool und klingt so, als würde sie etwas Ähnliches tun wie das, worüber Sie sprechen: http://txt2re.com

Chad Birch
quelle
4

Es gibt eine Sprache für solche Probleme, die auf Prolog basiert. Es heißt Progol .

Wie andere bereits erwähnt haben, ist die Grundidee das induktive Lernen, das in KI-Kreisen häufig als ILP ( Inductive Logic Programming ) bezeichnet wird.

Der zweite Link ist der Wiki-Artikel zu ILP, der viele nützliche Quellen enthält, wenn Sie mehr über das Thema erfahren möchten.

Patros
quelle
2

@ Yuval ist richtig. Sie betrachten die Theorie des rechnergestützten Lernens oder "induktive Inferenz".

Die Frage ist komplizierter als Sie denken, da die Definition von "lernen" nicht trivial ist. Eine gebräuchliche Definition ist, dass der Lernende Antworten ausspucken kann, wann immer er will, aber schließlich muss er entweder aufhören, Antworten auszuspucken, oder immer dieselbe Antwort ausspucken. Dies setzt eine unendliche Anzahl von Eingaben voraus und gibt absolut keinen Hinweis darauf, wann das Programm seine Entscheidung treffen wird. Außerdem können Sie nicht sagen, wann es seine Entscheidung getroffen hat, da es später möglicherweise noch etwas anderes ausgibt.

Nach dieser Definition bin ich mir ziemlich sicher, dass reguläre Sprachen lernbar sind. Nach anderen Definitionen nicht so sehr ...

Brian Postow
quelle
2

Ich habe einige Nachforschungen über Google und CiteSeer angestellt und folgende Techniken / Artikel gefunden:

Auch Dana Angluins "Lernen regelmäßiger Sets aus Abfragen und Gegenbeispielen" scheint vielversprechend, aber ich konnte keine PS- oder PDF-Version finden, sondern nur Zitate und Seminararbeiten.

Es scheint, dass dies selbst auf theoretischer Ebene ein heikles Problem ist.

Daniel Rikowski
quelle
0

Wenn es einer Person möglich ist, einen regulären Ausdruck zu lernen, ist es für ein Programm grundsätzlich möglich. Dieses Programm muss jedoch korrekt programmiert sein, um lernen zu können. Glücklicherweise ist dies ein ziemlich begrenzter Raum der Logik, daher wäre es nicht so komplex wie das Unterrichten eines Programms, um Objekte oder ähnliches sehen zu können.

cjk
quelle
1
Nicht wahr, Sie sollten nach Problemen suchen, die auf Turing-Maschinen nicht entschieden werden können.
Stephen Curial
Um fair zu sein, sagte ich, wenn eine Person einen REGEX lernen kann, dann kann eine Maschine. Ich habe es nicht allgemein gemeint.
cjk
@scurial Ich glaube nicht, dass es Probleme gibt, die sich als lösbar für Menschen erwiesen haben, aber auf Turingmaschinen unentscheidbar sind, oder?
Sunny88