Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
IKI 40931: Topik Khusus: NLP Kuliah 5: POS Tagging (Lanjutan) (Bab 8.5-8.8 Jurafsky & Martin)
Ruli Manurung Fakultas Ilmu Komputer Universitas Indonesia
25 Februari 2008
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Outline
1
Stochastic POS Tagging
2
TBL POS Tagging
3
Evaluasi
4
Isu-isu lain
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
POS ditentukan oleh konteks Ide dasar POS tagging POS tag sebuah kata dapat ditentukan oleh konteks di mana ia muncul. Bisa dalam corpus 1
Gue bisa menyelesaikan persoalan itu kok.
2
Penjinak ular menguras bisa hanya dengan cangkir plastik.
3
Masyarakat dan aparat bisa membersihkan sampah dengan baik.
4
Beliau menyatakan bisa menurunkan harga kedelai tahun ini.
Aturan apa yang dapat disimpulkan mengenai bisa? Dalam rule-based tagger, ide ini dinyatakan dalam rule yang dibuat secara manual (mis: “jika kata sesudahnya . . ., maka . . .”) Pada stochastic POS, konteks (corpus) diamati dan dipelajari secara otomatis. Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Pemodelan statistik Pada intinya, pilih tag yang memaksimalkan rumus berikut: P(kata|tag) × P(tag|n tag sebelumnya) Sebagai aproksimasi, sebuah bigram tagger memilih tag untuk kata ke-i (ti ) berdasarkan tag sebelumnya (ti−1 ) dan kata ke-i tersebut (wi ) ti = argmaxj P(tj |ti − 1, wi ) Melalui beberapa asumsi Markovian, diperoleh: ti = argmaxj P(tj |ti − 1) × P(wi |tj ) Perumusan statistik: “Berapa kemungkinan tag VB (atau NN) jika tag sebelumnya TO?” (tag sequence probability) dikalikan dengan “Jika diketahui sebuah kata adalah VB (atau NN), berapa kemungkinan ia adalah race?” (lexical likelihood) Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Sebuah contoh Amati race pada dua kalimat berikut: 1
Secretariat/NNP is/VBZ expected/VBN to/TO race/VB tomorrow/NN
2
People/NNS continue/VBP to/TO inquire/VB the/DT reason/NN for/IN the/DT race/NN for/IN outer/JJ space/NN
Bayangkan sudah diketahui POS tag yg benar kecuali untuk race. Konteks yang perlu diamati (secara bigram): 1
to/TO race/???
2
the/DT race/???
Untuk kasus pertama: 1
P(VB|TO) × P(race|VB) = 0.34 × 0.00003 = 0.00001
2
P(NN|TO) × P(race|NN) = 0.021 × 0.00041 = 0.000007
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Menggunakan statistik Definisi Hidden Markov Model (HMM) adalah pemodelan statistik di mana sebuah sistem “menghasilkan” (emit) urutan simbol yang dapat diamati (observation symbols) berdasarkan sebuah proses probabilistik yang parameternya tidak diketahui (hidden parameters). Proses probabilistik dinyatakan sebuah FSA: x1 , x2 , . . . adalah state yang menyatakan proses. aij adalah state transition probabilities: berapa kemungkinan proses berpindah dari state i ke j? y1 , y2 , . . . adalah observation symbols. bij adalah output/emission probability: berapa kemungkinan proses di state i menghasilkan symbol j?
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Contoh gambar HMM
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Menggunakan statistik HMM sering digunakan untuk memodelkan data sequential/temporal, di mana proses berjalan seiring waktu t, dengan asumsi berikut: Nilai hidden state x(t) sepenuhnya ditentukan oleh hidden state sebelumnya, x(t − 1). Nilai observed symbol y (t) sepenuhnya ditentukan oleh hidden state pada saat itu, x(t).
Menghitung probabilitas sebuah observation sequence Probabilitas P Y = y0 , y1 , y2 , . . . , yL−1 dengan panjang L adalah P(Y ) = X P(Y |X )P(X ). Jadi, kita menjumlahkan semua kemungkinan X = x0 , x1 , x2 , . . . , xL−1 . Penghitungan brute-force dalam prakteknya bersifat intractable. Namun, ada algoritma forward dan Viterbi . . . Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
HMM Tagger
Contoh race: memilih tag terbaik untuk kata yang diamati. Sebuah HMM tagger memilih tag sequence terbaik untuk word sequence yang diamati.
Word sequence yang diamati: W = w1 , w2 , . . . , wn Tag sequence yang terbaik/“benar”: T = t1 , t2 , . . . , tn Tˆ = argmaxT ∈τ P(T |W ) Dengan Bayes Law: Tˆ = argmaxT ∈τ P(T )P(W |T ) Dengan chain rule: Q Tˆ = argmaxT ∈τ ni=1 P(wi |w1 t1 . . . wi−1 ti−1 ti )P(ti |t1 , . . . ti−1 )
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Transformation-Based Tagging
Eric Brill merumuskan teori transformation-based learning. Ide dasar: tangani dulu secara “bodoh”, perbaiki masalah yang timbul. Ulangi sampai beres. Contoh:
P(NN|race) = 0.98 P(VB|race) = 0.02 Kesimpulan: tag semua race sebagai NN! Berdasarkan training data, pelajari rule, mis: Change NN to VB when the previous tag is TO.
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Cara kerja TBL Tagger
Cara kerja: 1 2
3
Lakukan proses tagging berdasarkan kamus Cobalah semua kemungkinan transformasi (rule). Pilih yang paling banyak mengurangi error . Aplikasikanlah. Ulangi langkah di atas sampai “cukup”.
Tentunya ada banyak sekali kemungkinan transformasi, jadi dibatasi dengan template: Kata sebelum/sesudah adalah Z . Kata kedua sebelum/sesudah adalah Z . Salah satu dari kedua kata sebelum/sesudah adalah Z . dst.
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Mengevaluasi hasil POS Tagger Biasanya dibandingkan dengan gold standard: data yang sudah di-tag secara manual oleh manusia. Yang dihitung adalah persentase tag yang dihasilkan benar sesuai dengan gold standard. Rata-rata POS tagger sekarang memiliki akurasi 96-97% (untuk tagset Penn Treebank → “sederhana”) Ini bagus atau jelek?
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Mengevaluasi hasil POS Tagger Biasanya dibandingkan dengan gold standard: data yang sudah di-tag secara manual oleh manusia. Yang dihitung adalah persentase tag yang dihasilkan benar sesuai dengan gold standard. Rata-rata POS tagger sekarang memiliki akurasi 96-97% (untuk tagset Penn Treebank → “sederhana”) Ini bagus atau jelek? Human ceiling (upper-bound) Marcus et al. (1993) menemukan bahwa manusia memiliki kesepakatan 96-97% ketika Brown Corpus di-tag dengan tagset Penn Treebank. Artinya, sebuah gold standard dapat memiliki error 3-4%.
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Mengevaluasi hasil POS Tagger Biasanya dibandingkan dengan gold standard: data yang sudah di-tag secara manual oleh manusia. Yang dihitung adalah persentase tag yang dihasilkan benar sesuai dengan gold standard. Rata-rata POS tagger sekarang memiliki akurasi 96-97% (untuk tagset Penn Treebank → “sederhana”) Ini bagus atau jelek? Human ceiling (upper-bound) Marcus et al. (1993) menemukan bahwa manusia memiliki kesepakatan 96-97% ketika Brown Corpus di-tag dengan tagset Penn Treebank. Artinya, sebuah gold standard dapat memiliki error 3-4%. Unigram baseline (lower-bound) Charniak et al. (1993) menunjukkan bahwa sebuah baseline algorithm, yang hanya menggunakan frekuensi unigram, mencapai akurasi 90-91%! Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Multiple tags, Multiple words Multiple tags Kadang-kadang, sebuah POS tagger benar-benar kesulitan menentukan tag sebuah kata. Daripada memaksa untuk memilih, ia akan memberikan alternatif, mis: (JJ/VBD/VBN), (JJ/NN), dst. Multiple words Beberapa tagset, mis. C5 dan C7, menganggap frasa sebagai sebuah “kata”, mis: “in terms of” dianggap sebagai sebuah preposition (II3) dan diberi label in/II31 terms/II32 of/II33 Beberapa corpus memecah stem + morfem-nya, mis: would/MD n’t/RB dan children/NNS ’s/POS
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
Stochastic POS Tagging TBL POS Tagging Evaluasi Isu-isu lain
Ringkasan
POS tag (yang ambigu) bisa ditentukan dengan bantuan konteks. Stochastic POS tagger memaksimalkan probabilitas P(kata|tag) × P(tag|n tag sebelumnya) (nilai dihitung dari corpus). Hidden Markov Model adalah model statistik yang bisa mengestimasi hidden parameter dari pengamatan observable sequence yang dihasilkan. Tagger berdasarkan transformation based learning menggabungkan pendekatan rule-based dan stochastic. Evaluasi tagger dilakukan terhadap gold standard dan unigram baseline.
Ruli Manurung
IKI40931 • Kuliah 5 • 25 Februari 2008
