Hidden Markov Model

Model generatif klasik untuk pelabelan barisan pada tingkat pengenalan.

Daftar isi

Topik ini membahas Hidden Markov Model, disingkat HMM, yaitu model generatif klasik untuk pelabelan barisan. Pembahasannya dibatasi pada tingkat pengenalan, yaitu intuisi dan struktur tanpa derivasi matematis. Setelah membacanya, tiga kelompok probabilitas HMM dapat dijelaskan, model kecil dapat dilatih dengan NLTK menggunakan pelatihan terbimbing, dan batasan yang kemudian memunculkan conditional random field dapat disebutkan.

Keadaan tersembunyi dan pengamatan#

HMM memandang kalimat berlabel sebagai hasil dua lapis kejadian. Lapis pertama adalah barisan keadaan tersembunyi (hidden state) yang tidak terlihat, yaitu label pada setiap token. Lapis kedua adalah barisan pengamatan (observation) yang terlihat, yaitu kata pada setiap token. Tugas pelabelan adalah menemukan barisan keadaan yang paling mungkin untuk barisan pengamatan yang diberikan.

Tiga kelompok probabilitas merangkai seluruh model, yaitu sebagai berikut.

Probabilitas awal (initial probability), yaitu peluang setiap label mengawali barisan.
Probabilitas transisi (transition probability), yaitu peluang label berikutnya diberikan label sekarang.
Probabilitas emisi (emission probability), yaitu peluang sebuah kata dipancarkan oleh sebuah label.

Diagram berikut memperlihatkan ketiga komponen itu pada model kecil dengan tiga label, yaitu PER untuk nama orang, O untuk token di luar entitas, dan LOC untuk nama tempat.

Tiga komponen HMM: probabilitas awal, transisi antarlabel, dan emisi kata

Angka pada diagram berasal dari sepuluh kalimat latihan yang digunakan pada demo di bagian berikut. Probabilitas awal hampir seluruhnya jatuh ke PER karena setiap kalimat diawali nama orang, dan transisi PER menuju O juga hampir pasti. Keadaan O membagi peluang lanjutannya sama besar antara tetap di O dan berpindah ke LOC, karena setiap kalimat memuat dua token O yang saling menyambung lalu diakhiri nama tempat. Kotak di bawah setiap keadaan memuat contoh kata yang dipancarkan, yaitu nama orang untuk PER, kata penghubung untuk O, dan nama tempat untuk LOC.

Pelatihan terbimbing dengan NLTK#

Pada pelatihan terbimbing (supervised training), ketiga tabel probabilitas cukup dihitung dari frekuensi, yaitu dengan menghitung berapa kali setiap transisi dan emisi muncul di data latih. Hasil penghitungan tersebut bersifat deterministik karena tidak ada langkah acak di dalamnya. NLTK menyediakan jalur ini melalui metode HiddenMarkovModelTrainer.train_supervised dengan masukan berupa kalimat berlabel dalam format [(kata, label), ...].

Hitungan frekuensi murni memberi probabilitas nol pada kejadian yang belum pernah terlihat, dan nilai nol tersebut memutus perhitungan pelabelan barisan. Karena itu, demo di bawah memakai penghalusan Lidstone (Lidstone smoothing), yaitu menambahkan hitungan kecil pada setiap kejadian agar kejadian yang jarang dan yang belum terlihat memperoleh probabilitas kecil, bukan nol. Berkas berikut melatih model pada sepuluh kalimat sintetis, kemudian melabeli dua kalimat uji yang sebagian katanya belum pernah dilihat.

python latih_hmm.py

import warnings

warnings.filterwarnings("ignore")

from nltk.probability import LidstoneProbDist
from nltk.tag.hmm import HiddenMarkovModelTrainer

# sepuluh kalimat sintetis berlabel, format [(kata, label), ...] per kalimat
data_latih = [
    [("Ali", "PER"), ("pergi", "O"), ("ke", "O"), ("Bandung", "LOC")],
    [("Budi", "PER"), ("pergi", "O"), ("ke", "O"), ("Bogor", "LOC")],
    [("Citra", "PER"), ("pergi", "O"), ("ke", "O"), ("Sukabumi", "LOC")],
    [("Dewi", "PER"), ("pergi", "O"), ("ke", "O"), ("Malang", "LOC")],
    [("Ali", "PER"), ("singgah", "O"), ("di", "O"), ("Bandung", "LOC")],
    [("Budi", "PER"), ("singgah", "O"), ("di", "O"), ("Malang", "LOC")],
    [("Citra", "PER"), ("singgah", "O"), ("di", "O"), ("Bogor", "LOC")],
    [("Dewi", "PER"), ("singgah", "O"), ("di", "O"), ("Sukabumi", "LOC")],
    [("Eka", "PER"), ("pergi", "O"), ("ke", "O"), ("Bandung", "LOC")],
    [("Eka", "PER"), ("singgah", "O"), ("di", "O"), ("Malang", "LOC")],
]


def estimator(fd, bins):
    """Penghalusan Lidstone agar kata baru tidak beremisi nol."""
    return LidstoneProbDist(fd, 0.1, bins)


trainer = HiddenMarkovModelTrainer()
model = trainer.train_supervised(data_latih, estimator=estimator)

# kalimat uji pertama: tiga kata dikenal, satu kata baru
for kata, label in model.tag(["Eka", "pergi", "ke", "Purwokerto"]):
    print(f"{kata:<12}{label}")

print()

# kalimat uji kedua: dua kata baru
for kata, label in model.tag(["Rina", "singgah", "di", "Balikpapan"]):
    print(f"{kata:<12}{label}")

text Keluaran

Eka         PER
pergi       O
ke          O
Purwokerto  LOC

Rina        PER
singgah     O
di          O
Balikpapan  LOC

Keluaran tersebut sesuai harapan untuk tugas yang sangat kecil ini. Kata Eka dikenal sebagai emisi PER, kata pergi dan ke dikenal sebagai emisi O, dan transisi antarlabelnya mengikuti pola data latih. Purwokerto dan Balikpapan belum pernah muncul di data latih, tetapi tetap diberi label yang wajar. Kata baru memperoleh probabilitas emisi kecil dari setiap label, dan emisi keadaan O terbagi ke lebih banyak kata daripada emisi PER atau LOC, sehingga kata baru terlihat lebih cocok dengan PER dan LOC. Untuk Purwokerto, transisi O menuju LOC yang sama besarnya dengan O menuju O menentukan pilihannya, sedangkan Rina berada pada posisi awal yang sudah menunjuk PER.

Algoritma Viterbi secara sekilas#

Pelabelan barisan memerlukan pemilihan satu barisan label utuh, dan jumlah kandidatnya tumbuh cepat. Untuk $k$ jenis label dan $n$ token, jumlah barisan kandidat adalah $k^n$ , sehingga pencarian langsung tidak mungkin. HMM memberi skor pada setiap kandidat melalui kelipatan probabilitasnya sepanjang barisan, yaitu sebagai berikut.

P(y_1, \ldots, y_n, w_1, \ldots, w_n) = P(y_1)\, P(w_1 \mid y_1) \, \prod_{i=2}^{n} P(y_i \mid y_{i-1})\, P(w_i \mid y_i)

Algoritma Viterbi mencari kandidat dengan skor terbesar tanpa menghitung semuanya. Cara kerjanya adalah pemrograman dinamis, yaitu menyimpan skor terbaik untuk setiap keadaan pada setiap posisi, karena kelanjutan terbaik dari keadaan yang sama dapat dihitung sekali dan digunakan ulang. Kompleksitasnya $O(n\,k^2)$ , yaitu masih tergolong cepat untuk jumlah label yang realistis. Yang terpenting, Viterbi memilih barisan terbaik dan bukan label terbaik per token, sehingga konsistensi barisan yang dituntut skema BIO tetap terjaga. Keluaran model.tag pada demo sebelumnya adalah hasil pencarian ini, yaitu barisan PER, O, O, LOC yang menang karena skor gabungannya terbesar di antara semua kandidat.

Kesalahan umum#

Kesalahan berikut lazim terjadi ketika HMM digunakan untuk pertama kali. Masing-masing disertai penyebab dan perbaikannya.

Melabeli kata baru tanpa penghalusan. Estimator bawaan train_supervised adalah distribusi frekuensi maksimum tanpa penghalusan, sehingga setiap kata di luar kosakata latihan memperoleh emisi nol. Pada data latih demo ini, kalimat uji berisi empat token yang seluruhnya baru, dan modelnya melabel keempat token itu PER karena seluruh skor Viterbi bernilai nol dan pilihan jatuh pada keadaan pertama. Sediakan estimator penghalusan seperti pada demo.
Menganggap HMM mampu menggunakan fitur bebas. Emisi HMM hanya menghubungkan kata dengan label saat itu, sedangkan transisi hanya menghubungkan label dengan label sebelumnya, sehingga sinyal seperti kapitalisasi awal, akhiran, atau kata tetangga tidak dapat masuk ke model. Keterbatasan inilah yang kemudian memunculkan conditional random field.
Menyamakan pelatihan terbimbing dengan pelatihan tanpa supervisi. Hasil Baum-Welch bergantung pada keadaan awal acak, sehingga dua eksekusi pada data yang sama dapat menghasilkan model yang berbeda. Gunakan jalur terbimbing bila data sudah berlabel dan keluarannya harus dapat direproduksi.

Ringkasan#

HMM memandang label sebagai keadaan tersembunyi dan kata sebagai pengamatannya, dengan tiga kelompok probabilitas, yaitu awal, transisi, dan emisi.
Pelatihan terbimbing cukup menghitung frekuensi transisi dan emisi, dan penghalusan diperlukan agar kata baru tidak beremisi nol.
Algoritma Viterbi mencari barisan label dengan skor gabungan terbesar secara efisien melalui pemrograman dinamis.
Emisi dan transisi yang sempit membuat HMM tidak dapat menggunakan fitur bebas, dan kata di luar kosakata menjadi titik lemah utamanya.

Referensi#

Speech and Language Processing, draf edisi ke-3 — Jurafsky & Martin, Stanford — Bab sequence labeling menguraikan komponen HMM dan algoritma Viterbi untuk decoding secara bertahap.