Ist es möglich, dass ein Computer einen regulären Ausdruck durch vom Benutzer bereitgestellte Beispiele “lernt”?

Ist es möglich, dass ein Computer einen regulären Ausdruck durch vom Benutzer bereitgestellte Beispiele “lernt”?

Um klarzustellen:

  • Ich möchte keine regulären Ausdrücke lernen.
  • Ich möchte ein Programm erstellen, das aus Beispielen, die von einem Benutzer interaktiv zur Verfügung gestellt werden, einen regulären Ausdruck “lernt”, vielleicht indem er Teile aus einem Text auswählt oder Anfangs- oder Endmarkierungen auswählt.

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

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

Das Buch Eine Einführung in die Computational Learning Theory 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 durch ein 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 von versteckten Markov-Modellen , bei denen es sich um probalistische 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 sind als normale Sprachen und daher manchmal schwieriger zu lernen sind.

Kein Computerprogramm wird jemals in der Lage sein, einen aussagekräftigen regulären Ausdruck zu erzeugen, der nur auf einer Liste gültiger Übereinstimmungen basiert. 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. Eine Regex, die 6 Einsen und Neun entspricht [19]{6}
  4. Eine Regex, die 6 Ziffern entspricht \d{6}
  5. Beliebige der obigen drei, mit Wortgrenzen, zB \b\d{6}\b
  6. Irgendeine der ersten drei, nicht vorangestellt oder gefolgt von einer Ziffer, zB (?< !\d)\d{6}(?!\d)

Wie Sie sehen, gibt es viele Möglichkeiten, wie Beispiele zu einem regulären Ausdruck verallgemeinert werden können. Die einzige Möglichkeit für den Computer, einen vorhersagbaren 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 Beschreibung auf höherer Ebene. Das ist genau das, was reguläre Ausdrücke bieten sollen. Anstatt eine lange Liste mit 6-stelligen Nummern zu erstellen, geben Sie dem Programm einfach "alle sechs Ziffern" an. In der regulären Ausdruckssyntax wird dies \ d {6}.

Jede Methode zur Bereitstellung einer höheren Beschreibung, die so flexibel ist wie reguläre Ausdrücke, ist ebenso komplex wie reguläre Ausdrücke. Alle Tools wie RegexBuddy können es einfacher machen, die High-Level-Beschreibung zu erstellen und zu testen. Anstatt die Syntax der kurzen regulären Ausdrücke direkt zu verwenden, können Sie mit RegexBuddy einfache englische Bausteine ​​verwenden. Aber es kann keine High-Level-Beschreibung für Sie erstellen, da es magisch nicht wissen kann, wann es Ihre Beispiele verallgemeinern sollte und wann nicht.

Es ist sicherlich möglich, ein Tool zu erstellen, das Beispieltext zusammen mit Richtlinien verwendet, die vom Benutzer zur Verfügung gestellt werden, um einen regulären Ausdruck zu generieren. Der schwierige Teil beim Entcasting eines solchen Werkzeugs ist, wie es den Benutzer nach den Führungsinformationen fragt, die es benötigt, ohne das Werkzeug schwieriger zu lernen als reguläre Ausdrücke selbst und ohne das Werkzeug auf gewöhnliche Regex-Jobs oder einfache reguläre Ausdrücke zu beschränken.

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

Regex Generator ++ Online-Tool generiert einen Regex von bereitgestellten Beispielen mit einem GP-Suchalgorithmus. Der GP-Algorithmus wird von einer multi-objektiven Fitness gesteuert, die zu höherer performance und einfacherer Lösungsstruktur führt (Ockhams Razor). Dieses Tool ist eine Demonstrationsanwendung des Machine Lern ​​Lab, Universität Triest (Università degli Studi di Trieste). Sehen Sie sich das Video-Tutorial hier an .

Dies ist ein Forschungsprojekt, so dass Sie hier über verwendete Algorithmen nachlesen können.

Erblicken! 🙂

Eine sinnvolle Regex / Lösung aus Beispielen zu finden, ist nur dann möglich, wenn die mitgelieferten Beispiele das Problem gut beschreiben. Betrachten Sie diese Beispiele, die eine Extraktionsaufgabe beschreiben, suchen wir nach bestimmten Artikelcodes; Die Beispiele sind Text / Extraktions-Paare:

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

Ein (menschlicher) Typ, der sich die Beispiele ansieht, mag sagen: “Die Artikelcodes sind Dinge wie \ d ++ – 345 [AB]”

Wenn der Artikelcode freizügiger ist, wir aber keine anderen Beispiele angegeben haben, haben wir keine Beweise, um das Problem gut zu verstehen. Bei der Anwendung der menschlich generierten Lösung \ d ++ – 345 [AB] auf den folgenden Text schlägt es fehl:

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

Sie müssen andere Beispiele angeben, um besser zu beschreiben, was eine Übereinstimmung ist und was nicht die 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.

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

 string MakeRegexFromExamples(, ) { if HasIntersection(, ) return  string regex = ""; foreach(string example in ) { if(regex != "") { regex += "|"; } regex += DoRegexEscaping(example); } regex = "^(" + regex + ")$"; // Ignore ; they're excluded by definition return regex; } 

Das Problem ist, dass es eine unendliche Anzahl von Regexs gibt, die mit einer Liste von Beispielen übereinstimmen. Dieser Code stellt die einfachste / dümmste Regex in der Menge zur Verfügung und stimmt grundsätzlich mit allem in der Liste der positiven Beispiele überein (und nichts anderes, einschließlich der negativen Beispiele).

Ich nehme an, die wirkliche Herausforderung wäre, die kürzeste Regex zu finden, die allen Beispielen entspricht, aber selbst dann müsste der Benutzer sehr gute Eingaben liefern, um sicherzustellen, dass der resultierende Ausdruck “der richtige” ist.

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. (Im Grunde müsste man das Programm fragen, ob der Nutzer ja / nein war, bis er zufrieden war.)

Vielleicht möchten Sie mit dieser Seite ein wenig spielen, es ist ziemlich cool und hört sich an, als würde es etwas ähnliches tun, worüber Sie sprechen: http://txt2re.com

Es gibt eine Sprache, die sich solchen Problemen auf der Basis von Prolog widmet. Es heißt Progol .

Wie andere bereits erwähnt haben, ist die Grundidee das induktive Lernen, das in KI-Kreisen oft als ILP ( induktive Logikprogrammierung ) bezeichnet wird.

Zweiter Link ist der Wiki-Artikel zu ILP, der eine Menge nützliches Quellenmaterial enthält, wenn Sie mehr über das Thema erfahren möchten.

@Yuval ist korrekt. Sie betrachten Computational Learning Theorie oder “induktive Inferenz”.

Die Frage ist komplizierter als Sie denken, da die Definition von “lernen” nicht trivial ist. Eine übliche Definition ist, dass der Lerner Antworten ausspucken kann, wann immer er will, aber schließlich muss er entweder aufhören, Antworten auszuspucken, oder immer die gleiche Antwort ausspucken. Dies setzt eine unendliche Anzahl von Eingaben voraus und gibt absolut keine Sicherheit darüber, wann das Programm seine Entscheidung treffen wird. Außerdem können Sie nicht sagen, wann es seine Entscheidung getroffen hat, weil es später möglicherweise noch etwas anderes ausgeben könnte.

Durch diese Definition bin ich mir ziemlich sicher, dass reguläre Sprachen erlernbar sind. Mit anderen Definitionen, nicht so sehr …

Ich habe etwas über Google und CiteSeer recherchiert und folgende Techniken / Dokumente gefunden:

  • Spracherkennung im Limit
  • Wahrscheinlich ungefähr richtiges Lernen

Auch Dana Angluins “Regelmäßiges Lernen von Fragen und Gegenbeispielen” erscheint vielversprechend, aber ich konnte keine PS- oder PDF-Version finden, sondern nur Zitieren und Seminararbeiten.

Es scheint, dass dies selbst auf der theoretischen Ebene ein schwieriges Problem ist.

Wenn es für eine Person möglich ist, einen regulären Ausdruck zu lernen, dann ist es grundsätzlich für ein Programm möglich. Dieses Programm muss jedoch richtig programmiert sein, um lernen zu können. Zum Glück ist das ein ziemlich begrenzter Raum der Logik, also wäre es nicht so komplex wie ein Programm zu lehren, Objekte oder etwas in der Art zu sehen.