Rozpoznawanie gramatyki w sekwencji rozmytych tokenów

Mam dokumenty tekstowe, które zawierają głównie listy pozycji.

Każdy element jest grupą kilku tokenów z różnych typów: Imię, Nazwisko, Data urodzenia, Numer telefonu, Miasto, Zawód itp. Token to grupa słów.

Przedmioty mogą leżeć w kilku liniach.

Elementy z dokumentu mają mniej więcej tę samą składnię tokenów, ale niekoniecznie muszą być dokładnie takie same.

Mogą to być jakieś więcej / mniej żetonów między Przedmiotami, a także wewnątrz Przedmiotów.

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

Celem jest identyfikacja użytej gramatyki, np

Occupation City

a na końcu zidentyfikuj wszystkie przedmioty, nawet jeśli nie pasują do siebie.

Aby pozostać krótkie i czytelne, użyjmy zamiast tego kilku aliasów A, B, C, D, ... do oznaczenia tych typów tokenów.

na przykład

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

Tutaj widzimy, że składnia elementu jest

A B C
D E F

ponieważ jest to ta, która najlepiej pasuje do sekwencji.

Składnia (typy tokenów i zamówienia) może się bardzo różnić w zależności od dokumentu. np. inny dokument może mieć tę listę

D A
D A
D
D A
B
D A

Celem jest ustalenie tej składni bez wcześniejszej wiedzy .

Od tej pory nowa linia jest również uważana za token. Dokument może być następnie reprezentowany jako jednowymiarowa sekwencja tokenów:

Tutaj powtarzająca się sekwencja byłaby, A B C Bponieważ to token powoduje najmniej konfliktów.

Skomplikujmy to trochę. Odtąd każdy token nie ma określonego typu. W prawdziwym świecie nie zawsze jesteśmy w 100% pewni co do typu tokena. Zamiast tego dajemy mu prawdopodobieństwo posiadania określonego typu.

  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

Oto abstrakcyjna grafika tego, co chcę osiągnąć:

Rozwiązanie rozważane A: Zwojenie łaty żetonów

To rozwiązanie polega na zastosowaniu splotu z kilkoma łatami tokenów i wybranie tego, który powoduje najmniej konfliktów.

Trudność polega tutaj na znalezieniu potencjalnych łatek, które można przetoczyć wzdłuż sekwencji obserwacji. Kilka pomysłów na ten, ale nic bardzo satysfakcjonującego:

Wada: ponieważ model Markowa nie ma pamięci, stracimy porządki przejścia. np. jeśli powtarzana jest sekwencja A B C B D, tracimy fakt, że A-> B występuje przed C-> B.

Wydaje się, że jest to szeroko stosowane w biologii w celu analizy zasad nukleinowych (GTAC) w DNA / RNA. Wada: drzewa sufiksów są odpowiednie do dokładnego dopasowania dokładnych żetonów (np. Postaci). Nie mamy ani dokładnych sekwencji, ani dokładnych tokenów.

Wypróbuj każdą kombinację każdego rozmiaru. Może faktycznie działać, ale zajmie to trochę czasu (długo).

Rozważane rozwiązanie B: Zbuduj tabelę odległości Levenshteina dla sufiksów

Intuicja jest taka, że ​​mogą istnieć lokalne minimalne odległości przy obliczaniu odległości od każdego sufiksu do każdego sufiksu.

Funkcja odległości jest odległością Levenshteina, ale będziemy mogli ją dostosować w przyszłości, aby uwzględnić prawdopodobieństwo istnienia określonych typów, zamiast mieć stały typ dla każdego tokena.

Aby zachować prostotę w tej demonstracji, użyjemy tokenów stałego typu i użyjemy klasycznego Levenshtein do obliczenia odległości między tokenami.

np. Miejmy sekwencję wejściową ABCGDEFGH ABCDEFGH ABCDNEFGH.

Odległość każdego przyrostka obliczamy dla każdego przyrostka (przyciętego, aby był równej wielkości):

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)

Otrzymujemy np. Następujący wynik (biały jest niewielki, czarny jest duży):

Teraz jest oczywiste, że każdy przyrostek w porównaniu do siebie będzie miał zerową odległość. Ale nie interesuje nas dopasowanie (dokładnie lub częściowo) samego siebie, więc przycinamy tę część.

Ponieważ sufiksy są przycinane do tego samego rozmiaru, porównanie długiego łańcucha zawsze da większą odległość niż porównanie mniejszych łańcuchów.

Musimy to zrekompensować płynną karą, zaczynając od prawej (+ P), stopniowo zanikając w lewo.

Nie jestem jeszcze pewien, jak wybrać dobrą funkcję karną, która pasuje do wszystkich przypadków.

Tutaj nakładamy karę (+ P = 6) na skrajnie prawą stronę, zmniejszając do 0 na lewo.

Teraz możemy wyraźnie zobaczyć 2 wyraźne ukośne linie. W tej sekwencji znajdują się 3 przedmioty (pozycja 1, pozycja 2, pozycja 3). Najdłuższa linia reprezentuje dopasowanie między pozycją 1 a pozycją 2 i pozycją 2 względem pozycji 3. Drugi najdłuższy reprezentuje dopasowanie między Przedmiotem 1 a Przedmiotem 3.

Teraz nie jestem pewien, jak najlepiej wykorzystać te dane. Czy to tak proste, jak przyjmowanie najwyższych linii ukośnych?

Załóżmy, że tak.

Obliczmy średnią wartość ukośnej linii, która zaczyna się od każdego tokena. Możemy zobaczyć wynik na poniższym obrazku (wektor poniżej macierzy):

Istnieją wyraźnie 3 lokalne minima, które pasują do początku każdego przedmiotu. Wygląda fantastycznie!

Dodajmy jeszcze kilka niedoskonałości w sekwencji: ABCGDEFGH ABCDEFGH TROLL ABCDEFGH

Najwyraźniej nasz wektor średnich diagonalnych jest zawalony i nie możemy go więcej wykorzystywać ...

Zakładam, że można to rozwiązać za pomocą niestandardowej funkcji odległości (zamiast Levenshteina), w której wstawienie całego bloku może nie być tak bardzo karane. Nie jestem tego pewien.

Wniosek

Żadne z zbadanych rozwiązań opartych na konwolucji nie wydaje się pasować do naszego problemu.

Rozwiązanie oparte na odległości Levenshteina wydaje się obiecujące, szczególnie dlatego, że jest kompatybilne z tokenami opartymi na prawdopodobieństwie. Ale nie jestem jeszcze pewien, jak wykorzystać jego wyniki.

Byłbym bardzo wdzięczny, jeśli masz doświadczenie w pokrewnej dziedzinie i kilka dobrych wskazówek, które możesz nam przekazać, lub innych technik do zbadania. Z góry bardzo dziękuję.

Możesz rzucić okiem na Ukryte Modele Markowa lub Stochastyczne Gramatyki Bez Kontekstu . Oba mogą być użyte do modelowania gramatyki i wnioskowania na podstawie danych.

Na przykład, obie były używane w przeszłości do modelowania sekwencji genetycznych, np. To i to .