Erkennen Sie eine Grammatik in einer Folge von unscharfen Token

Ich habe Textdokumente, die hauptsächlich Listen von Gegenständen enthalten.

Jedes Objekt ist eine Gruppe von mehreren Token verschiedener Typen: Vorname, Nachname, Geburtsdatum, Telefonnummer, Stadt, Beruf usw. Ein Token ist eine Gruppe von Wörtern.

Artikel können in mehreren Zeilen liegen.

Elemente aus einem Dokument haben ungefähr dieselbe Tokensyntax, müssen jedoch nicht unbedingt exakt gleich sein.

Dies können mehr oder weniger Token sein, sowohl zwischen Gegenständen als auch innerhalb von Gegenständen.

FirstName LastName BirthDate PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
Occupation UnrecognizedToken
FirstName LastName PhoneNumber
Occupation City
FirstName LastName BirthDate PhoneNumber
City Occupation

Ziel ist es, die verwendete Grammatik zu identifizieren, z

Occupation City

und am Ende identifizieren Sie alle Elemente, auch wenn sie nicht genau übereinstimmen.

Um kurz und lesbar zu bleiben, verwenden wir stattdessen einige Aliase A, B, C, D, ..., um diese Tokentypen zu kennzeichnen.

z.B

A B C
D F
A B C
D E F
F
A B C
D E E F
A C B
D E F
A B D C
D E F
A B C
D E F G

Hier können wir sehen, dass die Item-Syntax ist

A B C
D E F

weil es das ist, das am besten zu der Sequenz passt.

Die Syntax (Tokentypen und -reihenfolgen) kann von Dokument zu Dokument sehr unterschiedlich sein. zB kann ein anderes Dokument diese Liste haben

D A
D A
D
D A
B
D A

Ziel ist es, diese Syntax ohne Vorkenntnisse herauszufinden .

Ab sofort gilt eine neue Zeile auch als Token. Ein Dokument kann dann als eindimensionale Folge von Token dargestellt werden:

Hier wäre die wiederholte Sequenz, A B C Bweil es das Token ist, das die geringsten Konflikte erzeugt.

Lassen Sie es uns etwas komplexer machen. Ab jetzt hat jeder Token keinen festgelegten Typ. In der realen Welt sind wir uns des Typs eines Tokens nicht immer zu 100% sicher. Stattdessen geben wir eine Wahrscheinlichkeit für einen bestimmten Typ an.

  A 0.2    A 0.0    A 0.1
  B 0.5    B 0.5    B 0.9     etc.
  C 0.0    C 0.0    C 0.0
  D 0.3    D 0.5    D 0.0

Hier ist eine abstrakte Grafik von dem, was ich erreichen möchte:

Lösung als A: Faltung eines Patches von Token

Diese Lösung besteht darin, eine Faltung mit mehreren Token-Patches anzuwenden und diejenige zu nehmen, die die geringsten Konflikte verursacht.

Das Schwierige dabei ist, potenzielle Flecken zu finden, die sich entlang der Beobachtungssequenz bewegen. Einige Ideen für dieses, aber nichts sehr Befriedigendes:

Nachteil: Da ein Markov-Modell kein Gedächtnis hat, verlieren wir die Ordnungen des Übergangs. ZB wenn die wiederholte Sequenz ist A B C B D, verlieren wir die Tatsache, dass A-> B vor C-> B auftritt.

Dies scheint in der Biologie weit verbreitet zu sein, um Nukleobasen (GTAC) in DNA / RNA zu analysieren. Nachteil: Suffixbäume eignen sich für die exakte Zuordnung von exakten Token (z. B. Zeichen). Wir haben weder exakte Sequenzen noch exakte Token.

Probieren Sie jede Kombination in jeder Größe. Könnte eigentlich funktionieren, würde aber einige (lange (lange)) Zeit in Anspruch nehmen.

Betrachtete Lösung B: Erstellen Sie eine Tabelle mit Levenshtein-Abständen von Suffixen

Die Intuition ist, dass beim Berechnen des Abstands von jedem Suffix zu jedem Suffix einige lokale Abstandsminima existieren können.

Die Distanzfunktion ist die Levenshtein-Distanz, aber wir werden sie in Zukunft anpassen können, um die Wahrscheinlichkeit eines bestimmten Typs zu berücksichtigen, anstatt für jeden Token einen festen Typ zu haben.

Um in dieser Demonstration einfach zu bleiben, verwenden wir Token vom festen Typ und verwenden das klassische Levenshtein, um den Abstand zwischen Token zu berechnen.

Beispiel: Geben Sie die Eingabesequenz ein ABCGDEFGH ABCDEFGH ABCDNEFGH.

Wir berechnen die Entfernung jedes Suffixes mit jedem Suffix (auf gleiche Größe zugeschnitten):

for i = 0 to sequence.lengh
  for j = i to sequence.lengh
    # Create the suffixes
    suffixA = sequence.substr(i)
    suffixB = sequence.substr(j)
    # Make the suffixes the same size
    chunkLen = Math.min(suffixA.length, suffixB.length)
    suffixA = suffixA.substr(0, chunkLen)
    suffixB = suffixB.substr(0, chunkLen)
    # Compute the distance
    distance[i][j] = LevenshteinDistance(suffixA, suffixB)

Wir erhalten zB folgendes Ergebnis (Weiß ist kleiner Abstand, Schwarz ist groß):

Nun ist es offensichtlich, dass jedes Suffix im Vergleich zu sich selbst einen Nullabstand hat. Wir sind jedoch nicht daran interessiert, dass das Suffix (genau oder teilweise) mit sich selbst übereinstimmt, daher beschneiden wir diesen Teil.

Da die Suffixe auf dieselbe Größe zugeschnitten sind, ergibt der Vergleich langer Zeichenfolgen immer einen größeren Abstand als der Vergleich kleinerer Zeichenfolgen.

Wir müssen das durch einen gleichmäßigen Abzug von rechts (+ P) ausgleichen, der linear nach links ausgeblendet wird.

Ich bin mir noch nicht sicher, wie ich eine gute Straffunktion wählen soll, die in alle Fälle passt.

Hier wenden wir eine (+ P = 6) Strafe ganz rechts an und blenden nach links auf 0 aus.

Jetzt sehen wir deutlich 2 klare diagonale Linien. In dieser Reihenfolge befinden sich 3 Elemente (Element1, Element2, Element3). Die längste Zeile steht für die Übereinstimmung zwischen Item1 und Item2 und Item2 und Item3. Die zweitlängste entspricht der Übereinstimmung zwischen Item1 und Item3.

Jetzt bin ich mir nicht sicher, wie ich diese Daten am besten nutzen kann. Ist es so einfach wie die höchsten diagonalen Linien zu nehmen?

Nehmen wir an, es ist.

Berechnen wir den Durchschnittswert der diagonalen Linie, die von jedem Token ausgeht. Wir können das Ergebnis auf dem folgenden Bild sehen (der Vektor unter der Matrix):

Es gibt eindeutig 3 lokale Minima, die dem Anfang jedes Gegenstands entsprechen. Sieht super aus!

Fügen wir nun einige weitere Unvollkommenheiten in die Sequenz ein: ABCGDEFGH ABCDEFGH TROLL ABCDEFGH

Offensichtlich ist unser Vektor der diagonalen Durchschnitte durcheinander und wir können ihn nicht mehr ausnutzen ...

Ich gehe davon aus, dass dies durch eine benutzerdefinierte Distanzfunktion (anstelle von Levenshtein) gelöst werden könnte, bei der das Einfügen eines ganzen Blocks möglicherweise nicht so stark beeinträchtigt wird. Da bin ich mir nicht sicher.

Fazit

Keine der untersuchten faltungsbasierten Lösungen scheint zu unserem Problem zu passen.

Die auf Levenshtein-Entfernungen basierende Lösung erscheint vielversprechend, insbesondere weil sie mit wahrscheinlichkeitsbasierten Tokens kompatibel ist. Ich bin mir aber noch nicht sicher, wie ich die Ergebnisse nutzen soll.

Ich wäre Ihnen sehr dankbar, wenn Sie Erfahrung auf einem verwandten Gebiet haben und uns ein paar gute Tipps oder andere zu erforschende Techniken geben könnten. Vielen Dank im Voraus.

Vielleicht möchten Sie sich versteckte Markov-Modelle oder stochastische kontextfreie Grammatiken ansehen . Mit beiden können Grammatiken modelliert und aus Daten abgeleitet werden.

Zum Beispiel haben beide in der Vergangenheit verwendet wurden Gensequenzen zu modellieren, zB diese und diese .