Conditional random field

Topik ini membahas conditional random field, disingkat CRF, yaitu model diskriminatif untuk pelabelan barisan yang memodelkan probabilitas label diberikan kata. Pembahasannya tetap pada tingkat pengenalan, sebagaimana HMM pada topik sebelumnya dalam modul ini. Setelah membacanya, perbedaan model generatif dan diskriminatif dapat dijelaskan, fitur per token dapat disusun, dan model CRF kecil dapat dilatih serta dibaca bobot transisinya.

Dari generatif ke diskriminatif#

HMM memodelkan kejadian bersama antara label dan kata, sedangkan CRF memodelkan langsung probabilitas bersyarat $P(y \mid w)$, yaitu peluang barisan label $y$ diberikan barisan kata $w$. Perbedaan arah ini terlihat kecil, tetapi konsekuensinya besar. Model generatif harus menjelaskan bagaimana kata diciptakan, sehingga pengamatannya dipaksa saling bebas dan hanya terhubung ke label saat itu. Model diskriminatif tidak menanggung beban itu, sehingga setiap sinyal yang berkaitan dengan label boleh masuk sebagai fitur, termasuk fitur yang saling bertumpuk seperti kapitalisasi dan jenis kata.

CRF linear-chain, varian yang paling umum untuk pelabelan barisan, menetapkan skor untuk setiap pasangan barisan kata dan barisan label. Skornya berupa jumlah hasil kali bobot dan fitur, yaitu sebagai berikut.

Setiap $f_j$ adalah satu fitur yang dibaca dari kata dan tetangganya, sedangkan bobot $\lambda_j$ dipelajari dari data berlabel. Probabilitas barisan label diperoleh dengan mengubah skor menjadi distribusi pada seluruh kandidat barisan, dan dekodernya memilih barisan dengan skor terbesar. Struktur dekoder ini sama dengan Viterbi pada HMM, sehingga konsistensi barisan yang dituntut skema BIO tetap terjaga.

Fitur per token dan tetangga#

Fitur adalah pengukuran kecil atas token dan posisinya yang diduga berkaitan dengan label. Untuk NER, fitur yang paling sederhana mencakup bentuk kata, apakah huruf awalnya kapital, dan posisi token di dalam kalimat. Potongan berikut menampilkan fitur semacam itu untuk satu kalimat.

def fitur(token, posisi, panjang):
    """Fitur sederhana untuk satu token: kata, kapitalisasi, dan posisi."""
    return {
        "kata": token,
        "kapital_awal": token[0].isupper(),
        "posisi_awal": posisi == 0,
        "posisi_akhir": posisi == panjang - 1,
    }


contoh = ["Gita", "pergi", "ke", "Pantai", "Carita"]
for token, f in zip(contoh, [fitur(k, i, len(contoh)) for i, k in enumerate(contoh)]):
    print(f"{token:<8}{f}")

Gita    {'kata': 'Gita', 'kapital_awal': True, 'posisi_awal': True, 'posisi_akhir': False}
pergi   {'kata': 'pergi', 'kapital_awal': False, 'posisi_awal': False, 'posisi_akhir': False}
ke      {'kata': 'ke', 'kapital_awal': False, 'posisi_awal': False, 'posisi_akhir': False}
Pantai  {'kata': 'Pantai', 'kapital_awal': True, 'posisi_awal': False, 'posisi_akhir': False}
Carita  {'kata': 'Carita', 'kapital_awal': True, 'posisi_awal': False, 'posisi_akhir': True}

Fitur pada keluaran tersebut memberi tiga jenis bukti. Fitur kata mengenali kata yang sudah dikenal, misalnya ke yang hampir selalu di luar entitas. Fitur kapital_awal menandai kandidat nama diri tanpa bergantung pada kosakata, sehingga kata baru yang kapital tetap membawa sinyal. Fitur posisi_awal dan posisi_akhir menangkap struktur kalimat, misalnya kecenderungan nama orang mengawali kalimat.

Pada sistem nyata, fitur ditambah jauh lebih banyak, misalnya akhiran, jenis kata dari tagger, kata sebelum dan sesudah token, serta tanda kehadiran angka. Semua fitur ditulis dalam bentuk kamus Python, dan nilai fitur yang belum pernah terlihat pada data latih tidak berkontribusi apa pun pada skor. Fitur yang saling bertumpuk tidak menjadi masalah karena model diskriminatif menimbang semuanya sekaligus saat belajar.

Melatih CRF dengan sklearn-crfsuite#

Library sklearn-crfsuite membungkus implementasi CRF dengan antarmuka fit dan predict sebagaimana scikit-learn. Berkas berikut melatih model pada dua belas kalimat sintetis berlabel BIO menggunakan fitur di atas, kemudian melabeli kalimat uji yang seluruh tokennya belum pernah dilihat, dan menampilkan bobot transisi antarlabel yang dipelajari. Data latihnya sengaja dibuat sangat kecil agar pelatihan dapat direproduksi dalam hitungan detik pada lingkungan mana pun.

import sklearn_crfsuite

# dua belas kalimat sintetis berlabel BIO
data_latih = [
    [("Ali", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Danau", "B-LOC"), ("Toba", "I-LOC")],
    [("Budi", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Danau", "B-LOC"), ("Poso", "I-LOC")],
    [("Citra", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Sungai", "B-LOC"), ("Kapuas", "I-LOC")],
    [("Dewi", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Gunung", "B-LOC"), ("Semeru", "I-LOC")],
    [("Ali", "B-PER"), ("singgah", "O"), ("di", "O"), ("Danau", "B-LOC"), ("Poso", "I-LOC")],
    [("Budi", "B-PER"), ("singgah", "O"), ("di", "O"), ("Gunung", "B-LOC"), ("Semeru", "I-LOC")],
    [("Citra", "B-PER"), ("singgah", "O"), ("di", "O"), ("Danau", "B-LOC"), ("Toba", "I-LOC")],
    [("Dewi", "B-PER"), ("singgah", "O"), ("di", "O"), ("Sungai", "B-LOC"), ("Kapuas", "I-LOC")],
    [("Eka", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Danau", "B-LOC"), ("Sentani", "I-LOC")],
    [("Fajar", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Gunung", "B-LOC"), ("Bromo", "I-LOC")],
    [("Gita", "B-PER"), ("singgah", "O"), ("di", "O"), ("Bukit", "B-LOC"), ("Barisan", "I-LOC")],
    [("Hana", "B-PER"), ("pergi", "O"), ("ke", "O"), ("Pantai", "B-LOC"), ("Carita", "I-LOC")],
]


def fitur(token, posisi, panjang):
    """Fitur sederhana untuk satu token: kata, kapitalisasi, dan posisi."""
    return {
        "kata": token,
        "kapital_awal": token[0].isupper(),
        "posisi_awal": posisi == 0,
        "posisi_akhir": posisi == panjang - 1,
    }


def fitur_barisan(token):
    """Menyusun daftar fitur untuk seluruh barisan token."""
    return [fitur(k, i, len(token)) for i, k in enumerate(token)]


X_latih = [fitur_barisan([k for k, _ in kal]) for kal in data_latih]
y_latih = [[l for _, l in kal] for kal in data_latih]

crf = sklearn_crfsuite.CRF(
    algorithm="lbfgs",
    c1=0.1,
    c2=0.1,
    max_iterations=100,
    all_possible_transitions=True,
)
crf.fit(X_latih, y_latih)

# prediksi kalimat baru yang belum pernah dilihat
uji = ["Rina", "singgah", "di", "Danau", "Ranau"]
for kata, label in zip(uji, crf.predict([fitur_barisan(uji)])[0]):
    print(f"{kata:<12}{label}")
print()

# bobot transisi antarlabel yang dipelajari model
for (dari, ke), berat in sorted(crf.transition_features_.items(), key=lambda item: -item[1]):
    if berat > 0:
        print(f"{dari:<8}-> {ke:<8}{berat:+.3f}")

Rina        B-PER
singgah     O
di          O
Danau       B-LOC
Ranau       I-LOC

O       -> O       +2.331
B-LOC   -> I-LOC   +2.265
B-PER   -> O       +2.050
O       -> B-LOC   +1.733

Prediksi pada kalimat uji tepat meskipun hampir seluruh katanya belum pernah dilihat, dan hanya singgah serta di yang sudah dikenal model. Kata Rina diberi B-PER karena fitur kapital pada posisi awal, dan pola yang sama dipelajari dari semua nama orang di data latih. Kata Danau dikenali melalui fitur kata yang sudah tercatat sebagai B-LOC, dan Ranau yang baru diberi I-LOC karena transisi B-LOC menuju I-LOC berbobot besar. Tabel transisi di bagian akhir keluaran memperlihatkan bobot itu secara langsung, yaitu empat pasangan label yang sering muncul berurutan memperoleh bobot positif, sedangkan pasangan yang tidak masuk akal seperti B-PER menuju B-PER diberi bobot negatif.

Parameter pelatihan pada berkas tersebut memerlukan penjelasan singkat. Algoritma lbfgs adalah metode optimisasi gradien yang deterministik, dan max_iterations=100 menetapkan jumlah langkahnya, sehingga pelatihan tidak bergantung pada keacakan. Nilai c1 dan c2 mengatur kekuatan regularisasi yang menjaga bobot tetap kecil, dan all_possible_transitions=True menyediakan bobot awal nol untuk semua pasangan label, termasuk pasangan yang tidak pernah muncul berurutan di data latih.

HMM atau CRF#

Perbedaan arah pemodelan menentukan perbedaan kerja sehari-hari. Pada HMM, seluruh pengetahuan tentang kata tersimpan di tabel emisi yang hanya menghubungkan satu kata dengan satu label, sedangkan pada CRF, pengetahuan itu tersebar di bobot fitur yang menangkap bentuk kata, posisi, dan tetangganya sekaligus. Kedua model memecahkan tugas yang sama dan keduanya menggunakan dekoder bergaya Viterbi. Perbandingan berikut merangkum perbedaannya pada tingkat pengenalan.

CRF menggantikan HMM dalam praktik karena fiturnya bebas, tetapi fiturnya tetap disusun secara manual. HMM tetap berguna sebagai pembanding yang cepat dibangun, karena pelatihannya hanya penghitungan frekuensi dan keluarannya berupa tabel probabilitas yang mudah diperiksa. CRF menuntut data berlabel dan penyusunan fitur, tetapi imbalannya adalah akurasi yang lebih tinggi pada tugas yang sama karena setiap sinyal yang relevan dapat ditampung sebagai fitur. Penyusunan fitur yang baik menuntut pengetahuan tentang tugas dan bahasanya, dan itulah pekerjaan yang kemudian dialihkan ke model neural.

Ringkasan#

• CRF adalah model diskriminatif yang memodelkan $P(y \mid w)$ secara langsung, sedangkan HMM memodelkan kejadian bersama $P(y, w)$.
• Fitur per token bebas dan boleh saling bertumpuk, mulai dari bentuk kata, kapitalisasi, sampai posisi dalam kalimat.
• Bobot transisi antarlabel yang dipelajari menunjukkan pasangan label yang sah, dan dekoder menimbang seluruh barisan sebagaimana Viterbi.
• CRF menang di atas HMM karena fiturnya bebas, tetapi keduanya tetap bergantung pada data berlabel dan fitur yang disusun manual.

Referensi#

• An Introduction to Conditional Random Fields — Sutton & McCallum, arXiv — Tinjauan lengkap CRF linear-chain, termasuk perbandingannya dengan HMM dan pemilihan fitur.
• Speech and Language Processing, draf edisi ke-3 — Jurafsky & Martin, Stanford — Bab sequence labeling membandingkan CRF dengan HMM untuk tugas yang sama.