Ist es möglich, dass ein computer "lernen" einem regulären Ausdruck durch Benutzer-Beispiele?

Question

Ist es möglich, dass ein computer "lernen" einem regulären Ausdruck durch Benutzer-Beispiele?

Zu klären:

• Ich tun nicht wollen lernen, reguläre Ausdrücke.
• Ich möchte ein Programm erstellen, die "lernt" einen regulären Ausdruck aus Beispiele, die interaktiv durch einen Anwender, vielleicht indem Sie Teile aus einem text oder Auswahl begin oder end-Marker.

Ist es möglich?Gibt es algorithmen, keywords, etc.kann ich Google?

BEARBEITEN:Danke für die Antworten, aber ich bin nicht daran interessiert, Werkzeuge, die bieten diese Funktion.Ich bin auf der Suche nach theoretischen Informationen, wie papers, tutorials, Quelle code, Namen von algorithmen, also kann ich auch etwas für mich.

Answer 1

Das Buch Eine Einführung in Computational Learning Theory einen Algorithmus enthält ein für das Lernen endliche Automaten. Da jede reguläre Sprache zu einem endlichen Automaten äquivalent ist, ist es möglich, einige regulären Ausdrücke durch ein Programm zu lernen. Kearns und Valiant einige Fälle zeigen, in denen es ist nicht möglich, einen endlichen Automaten zu lernen. Ein verwandtes Problem ist Hidden-Markov-Modelle lernen , die probabilistischen Automaten sind, die eine beschreiben Zeichensequenz. Beachten Sie, dass die meisten modernen „reguläre Ausdrücke“ verwendet in Programmiersprachen sind tatsächlich stärker als reguläre Sprachen, und deshalb manchmal schwieriger zu erlernen.

Answer 2

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

Regex Generator ++ Online-Tool erzeugt einen regulären Ausdruck aus bereitgestellten Beispiele einen GP-Suchalgorithmus verwendet wird. Der GP-Algorithmus wird von einem Mehrziel Fitness angetrieben, die zu einer höheren Leistung führt und einfachere Lösung Struktur (Ockhams Rasiermesser). Dieses Tool ist eine demostrative Anwendung, die von der Maschine Lerning Lab, Triest Univeristy (Università degli studi di Trieste). Bitte schauen Sie sich das Video Tutorial hier .

Dies ist ein Forschungsprojekt, so können Sie über Algorithmen lesen hier .

Siehe : -)

Die Suche nach einer sinnvollen regex / Lösung von Beispielen ist möglich , wenn und nur wenn die bereitgestellten Beispiele das Problem gut beschreiben. Betrachten Sie diese Beispiele, die eine Extraktion Aufgabe beschreiben, wir sind für bestimmten Itemcodes suchen; Die Beispiele sind text / Extraktionspaare:

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

Ein (Mensch) Mann, an den Beispielen suchen, sagen kann: "die Artikelcodes sind Dinge wie \ d ++ - 345 [AB]"

Wenn der Artikelcode zügiger ist, aber wir haben nicht andere Beispiele zur Verfügung gestellt, wir haben nicht Beweise das Problem gut zu verstehen. Wenn die menschliche erzeugte Lösung Anwendung \ d ++ - 345 [AB], um den folgenden Text ein, es fehlschlägt:

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

Sie haben andere Beispiele zu liefern, um besser zu beschreiben, was ein Spiel ist und was nicht ein gewünschtes Spiel: --i.e:

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

Die Telefonnummer ist kein Produkt-ID, kann dies ein wichtiger sicher sein.

Answer 3

Keine computer-Programm wird jemals in der Lage sein zum generieren einer sinnvollen regular expression based allein für eine Liste der gültigen Spiele.Lassen Sie mich Ihnen zeigen, warum.

Angenommen, Sie stellen die Beispiele 111111 und 999999, sollte der computer generieren:

1. Ein regex-matching genau diese beiden Beispiele: (111111|999999)
2. Ein regex-matching-6 identischen Ziffern (\d)\1{5}
3. Ein regex-matching-6 Einsen und Neunen [19]{6}
4. Eine regex passt zu jedem 6-stellig \d{6}
5. Jede der drei genannten, mit word-Grenzen, z.B. \b\d{6}\b
6. Die ersten drei, nicht vorangestellt oder gefolgt von einer Ziffer, z.B.(?<!\d)\d{6}(?!\d)

Wie Sie sehen können, gibt es viele Möglichkeiten, in denen Beispiele verallgemeinert werden können in einen regulären Ausdruck.Die einzige Möglichkeit, den computer zu bauen, die eine vorhersehbare regulärer Ausdruck ist, müssen Sie die Liste alle mögliche übereinstimmungen.Dann könnte es erzeugen ein Suchmuster, das entspricht genau die Spiele.

Wenn Sie nicht wollen, um eine Liste aller möglichen übereinstimmungen, Sie brauchen eine höhere-Ebene-Beschreibung.Das ist genau das, was reguläre Ausdrücke sind so konzipiert, bieten.Statt eine lange Liste mit 6-stelligen zahlen, Sie geben einfach das Programm zu Spiel "alle sechs Ziffern".In der syntax für reguläre Ausdrücke, das wird \d{6}.

Jede Methode bietet eine höhere Ebene der Beschreibung, die ist so flexibel, wie reguläre Ausdrücke werden auch als komplexe als reguläre Ausdrücke.Alle Extras wie RegexBuddy tun können, ist zu machen es einfacher zu erstellen und zu testen, die high-level-Beschreibung.Anstatt die knappe syntax für reguläre Ausdrücke direkt, RegexBuddy ermöglicht die Verwendung von Klartext-Blöcke.Aber es kann nicht erstellen Sie die high-level-Beschreibung, da es nicht auf Magische Weise wissen, Wann es sollten verallgemeinern Ihrem Beispiele, und wenn es nicht sollte.

Es ist durchaus möglich, ein Werkzeug zu schaffen, die verwendet Beispieltext zusammen mit den Vorgaben der Benutzer generieren einer reguläre Ausdrücke.Der schwierige Teil bei der Gestaltung solch ein Werkzeug ist, wie es der Benutzer aufgefordert, für die anleitende Informationen, die es benötigt, ohne dass das Werkzeug schwerer zu lernen als die regulären Ausdrücke selbst, und ohne Einschränkung der Werkzeug common regex jobs oder einfache reguläre Ausdrücke.

Answer 4

Ja, es ist sicherlich „möglich“; Hier ist der Pseudo-Code:

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 eine unendliche Anzahl von regexs ist, die eine Liste von Beispielen übereinstimmen. Dieser Code stellt die einfachste / dümmste regex in der Menge, im Grunde in der Liste der positiven Beispiele (und nichts anderes, einschließlich einer der negativen Beispiele) passend zu nichts.

Ich nehme an die eigentliche Herausforderung die kürzeste regex zu finden wäre, dass alle Beispiele passt, aber auch dann würde der Benutzer sehr gute Beiträge liefern müssen, um die sich ergebende Ausdruck sicherzustellen, dass „die richtige“ war.

Answer 5

Ich glaube, der Begriff ist „Induktion“. Sie wollen eine regelmäßige Grammatik induzieren.

Ich glaube nicht, es ist möglich, mit einer endlichen Menge von Beispielen (positiv oder negativ). Aber, wenn ich mich richtig erinnere, es kann getan werden, wenn eine Oracle ist die Rate gezogen werden kann. (Im Grunde würden Sie das Programm fragen lassen müssen, um den Benutzer Ja / Nein-Fragen, bis er Inhalt war.)

Answer 6

Sie möchten mit dieser Seite ein wenig spielen, ist es ziemlich cool ist, und es klingt wie macht es etwas Ähnliches, was du redest: http://txt2re.com

Answer 7

Es gibt eine Sprache, um Probleme wie diese auf Grundlage des Prologs. Es heißt PROGOL .

Wie andere erwähnt haben, ist die Grundidee induktive Lernen, oft ILP ( induktive logische Programmierung ) in AI Kreisen.

Zweiter Link ist der Wiki-Artikel über ILP, die viele nützliche Quellenmaterial enthält, wenn Sie in das Lernen mehr über das Thema interessiert sind.

Answer 8

@Yuval ist richtig. Sie befinden sich in Computational Lerntheorie suchen, oder „induktive Inferenz.“

Die Frage ist komplizierter, als man denkt, wie die Definition von „lernen“, ist nicht trivial. Eine gängige Definition ist, dass der Lernende Antworten ausspucken kann, wann immer er will, aber irgendwann muss es entweder aufhören Antworten spuckt, oder immer die gleiche Antwort ausspucken. Dies setzt eine unendliche Anzahl von Eingängen und gibt absolut keine garauntee auf, wenn das Programm seine Entscheidung treffen. Sie können aber auch nicht sagen, wann es seine Entscheidung getroffen hat, weil es vielleicht noch etwas anderes ausgegeben später.

Durch diese Definition Ich bin mir ziemlich sicher, dass reguläre Sprachen erlernbar sind. Durch andere Definitionen, nicht so sehr ...

Answer 9

Ich habe einige der Forschung auf Google getan und CiteSeer und fand diese Techniken / papers:

• Spracherkennung im Limit
• Wahrscheinlich annähernd richtiges Lernen

Auch Dana Angluin der scheint „regular Sätze von Abfragen und Gegenbeispielen lernen“ vielversprechend aus, aber ich war nicht in der Lage eine PostScript- oder PDF-Version zu finden, die nur zitiert und Seminararbeiten.

Es scheint, dass dies ein heikles Problem ist auch auf der theoretischen Ebene.

Answer 10

Wenn sein möglich, dass eine Person einen regulären Ausdruck zu lernen, dann ist es grundsätzlich möglich, für ein Programm. Allerdings muß das Programm richtig in der Lage sein zu lernen, programmiert werden. Zum Glück ist dies ein ziemlich endlicher Raum der Logik, so wäre es nicht so komplex wie ein Programm lehren können Objekte oder so etwas sehen.