Kenali tata bahasa dalam urutan token fuzzy

Saya memiliki dokumen teks yang sebagian besar berisi daftar Item.

Setiap Item adalah sekelompok token dari berbagai jenis: FirstName, LastName, BirthDate, PhoneNumber, City, Occupation, dll. Token adalah sekelompok kata.

Barang bisa terletak pada beberapa baris.

Item dari dokumen memiliki sintaks token yang sama, tetapi tidak harus sama persis.

Mereka mungkin lebih / kurang token antara Item, serta dalam Item.

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

Tujuannya adalah untuk mengidentifikasi tata bahasa yang digunakan, misalnya

Occupation City

dan pada akhirnya mengidentifikasi semua Item, bahkan berpikir mereka tidak persis cocok.

Agar tetap pendek dan mudah dibaca, mari kita gunakan beberapa alias A, B, C, D, ... untuk menunjuk tipe-tipe token tersebut.

misalnya

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

Di sini kita dapat melihat bahwa sintaks Item adalah

A B C
D E F

karena itu adalah yang paling cocok dengan urutan.

Sintaks (jenis dan pesanan token) dapat sangat bervariasi dari satu dokumen ke dokumen lainnya. misalnya dokumen lain mungkin memiliki daftar itu

D A
D A
D
D A
B
D A

Tujuannya adalah untuk mengetahui sintaksis itu tanpa sepengetahuan sebelumnya .

Mulai sekarang, baris baru dianggap sebagai token juga. Sebuah dokumen kemudian dapat direpresentasikan sebagai urutan token 1 dimensi:

Di sini urutan yang berulang adalah A B C Bkarena token yang menciptakan konflik paling sedikit.

Mari kita sedikit rumit. Mulai sekarang setiap token tidak memiliki tipe yang ditentukan. Di dunia nyata, kita tidak selalu 100% yakin dengan tipe token tertentu. Sebagai gantinya, kami memberikannya kemungkinan memiliki jenis tertentu.

  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

Berikut ini adalah grafik abstrak dari apa yang ingin saya capai:

Solusi dianggap A: Konvolusi tambalan token

Solusi ini terdiri dalam menerapkan konvolusi dengan beberapa tambalan token, dan mengambil salah satu yang menciptakan konflik paling sedikit.

Bagian yang sulit di sini adalah menemukan tambalan potensial untuk bergulir di sepanjang urutan pengamatan. Beberapa ide untuk yang satu ini, tetapi tidak ada yang sangat memuaskan:

Kelemahan: karena model Markov tidak memiliki memori, kami akan kehilangan urutan transisi. mis. Jika urutan berulang adalah A B C B D, kita kehilangan fakta bahwa A-> B terjadi sebelum C-> B.

Ini tampaknya digunakan secara luas dalam biologi untuk menganalisis nucleobases (GTAC) dalam DNA / RNA. Kekurangan: Pohon sufiks baik untuk pencocokan tepat token yang tepat (misalnya karakter). Kami tidak memiliki urutan yang tepat, atau token yang tepat.

Coba setiap kombinasi dari setiap ukuran. Sebenarnya bisa bekerja, tetapi akan memakan waktu (lama (lama)).

Solusi yang dipertimbangkan B: Buat tabel jarak sufiks Levenshtein

Intuisi adalah bahwa mungkin ada beberapa jarak minimum lokal ketika menghitung jarak dari setiap sufiks ke setiap sufiks.

Fungsi jarak adalah jarak Levenshtein, tetapi kami akan dapat menyesuaikannya di masa mendatang untuk memperhitungkan kemungkinan jenis tertentu, alih-alih memiliki jenis tetap untuk setiap token.

Agar tetap sederhana dalam demonstrasi itu, kami akan menggunakan token tipe tetap, dan menggunakan Levenshtein klasik untuk menghitung jarak antara token.

mis. Mari kita memiliki urutan input ABCGDEFGH ABCDEFGH ABCDNEFGH.

Kami menghitung jarak setiap akhiran dengan setiap akhiran (dipotong dengan ukuran yang sama):

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)

Kami mendapatkan misalnya hasil berikut (putih jarak kecil, hitam besar):

Sekarang, sudah jelas bahwa sufiks apa pun dibandingkan dengan dirinya sendiri akan memiliki jarak nol. Tapi kami tidak tertarik dengan sufiks (persis atau sebagian) yang cocok dengan dirinya sendiri, jadi kami memotong bagian itu.

Karena sufiks dipangkas dengan ukuran yang sama, membandingkan string panjang akan selalu menghasilkan jarak yang lebih besar daripada membandingkan string yang lebih kecil.

Kita perlu mengkompensasinya dengan penalti yang mulus mulai dari kanan (+ P), memudar secara linear ke kiri.

Saya belum yakin bagaimana memilih fungsi penalti yang baik yang cocok untuk semua kasus.

Di sini kita menerapkan penalti (+ P = 6) di paling kanan, memudar ke 0 ke kiri.

Sekarang kita dapat dengan jelas melihat 2 garis diagonal yang jelas muncul. Ada 3 Item (Item1, Item2, Item3) dalam urutan itu. Baris terpanjang mewakili kecocokan antara Item1 vs Item2 dan Item2 vs Item3. Yang terpanjang kedua mewakili kecocokan antara Item1 vs Item3.

Sekarang saya tidak yakin tentang cara terbaik untuk mengeksploitasi data itu. Apakah sesederhana mengambil garis diagonal tertinggi?

Mari kita asumsikan demikian.

Mari kita hitung nilai rata-rata garis diagonal yang dimulai dari setiap token. Kita dapat melihat hasilnya pada gambar berikut (vektor di bawah matriks):

Jelas ada 3 minimum lokal, yang cocok dengan awal setiap Item. Terlihat fantastis!

Sekarang mari kita tambahkan beberapa ketidaksempurnaan dalam urutan: ABCGDEFGH ABCDEFGH TROLL ABCDEFGH

Jelas sekarang, vektor rata-rata diagonal kami berantakan, dan kami tidak dapat mengeksploitasinya lagi ...

Asumsi saya adalah bahwa ini dapat diselesaikan dengan fungsi jarak yang disesuaikan (bukan Levenshtein), di mana penyisipan seluruh blok mungkin tidak begitu banyak dihukum. Itu yang saya tidak yakin.

Kesimpulan

Tidak ada solusi berbasis konvolusi yang dieksplorasi yang cocok dengan masalah kita.

Solusi berbasis jarak Levenshtein tampaknya menjanjikan, terutama karena itu kompatibel dengan token tipe berbasis probabilitas. Tapi saya belum yakin bagaimana cara memanfaatkan hasilnya.

Saya akan sangat berterima kasih jika Anda memiliki pengalaman dalam bidang terkait, dan beberapa petunjuk bagus untuk diberikan kepada kami, atau teknik lain untuk dijelajahi. Terima kasih banyak sebelumnya.

Anda mungkin ingin melihat Hidden Markov Models atau Grammar Konteks Bebas Stochastic . Keduanya dapat digunakan untuk memodelkan tata bahasa dan menyimpulkannya dari data.

Misalnya, keduanya telah digunakan di masa lalu untuk memodelkan urutan genetik, misalnya ini dan ini .