Pemodelan bahasa

Part of speech tagging

Parsing

Tutorial: Pengenalan terhadap POS tagging dan

Probabilistic Parsing

Ruli Manurung

Fakultas Ilmu Komputer

Universitas Indonesia
maruli@[Link]

Workshop Nasional INACL

Kamis, 7 Januari 2016

1/53
 Pemodelan bahasa
Part of speech tagging
Parsing

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

2/53
 Pemodelan bahasa
Part of speech tagging
Parsing

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

3/53
 Pemodelan bahasa
Part of speech tagging
Parsing

Apa itu model bahasa?

Model bahasa dapat memprediksi perilaku sebuah bahasa,
mis. aturan tata bahasa, distribusi probabilitas.
Dibutuhkan pada hampir setiap aplikasi NLP.
Dengan bantuan model bahasa, kita dapat memahami dan
memprediksi sifat, fungsi, dan makna sebuah teks.
Pendekatan Linguist (“top-down”)
Implementasikan algoritma dan struktur data berdasarkan teori dan
model linguistik.

Pendekatan Empiricist (“bottom-up”)

Gunakan model “black-box” berdasarkan statistik atau machine
learning.

4/53
 Pemodelan bahasa
Part of speech tagging
Parsing

Contoh sederhana
Bagaimana caranya menginterpretasikan sebuah sinyal lisan:
1 “I scream is delicious”.
2 “Ice cream is delicious”.
Model linguistik
Kalimat (1) tidak valid, sedangkan kalimat (2) adalah valid.

Model empiris
“Ice cream is” lebih sering dijumpai daripada “I scream is”.

Cara kita memodelkan bahasa pun beragam, mis. n-gram, bag of

words, POS sequence, parse tree, dst.

5/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

6/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

7/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

POS

Kelas kata
Part-of-speech, POS, word class, morphological class, lexical tag: sebuah
atribut dari kata. Secara umum, menentukan “tipe” dari kata tersebut.

Apa yang bisa diprediksi oleh POS?

Sifat morphological: imbuhan apa saja yang bisa ditambahkan?
Sifat syntactic: apa saja kata-kata yang bisa muncul di dekatnya?
Sifat semantic: secara umum, apa “maksud” dari kata tersebut?
Apa gunanya?
Speech recognition: “I scream is delicious”
Information retrieval: stemming (tahu imbuhan yang mungkin)
Masih banyak lagi... shallow parsing

8/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Open vs closed class types

Open class words adalah kelas kata yang keanggotaannya

biasanya besar dan senantiasa bertambah (serapan bahasa
lain, teknologi baru, etc.). Kata-kata ini, pada umumnya,
menyatakan “isi dunia”: obyek, kejadian, atribut.
Closed class words adalah kelas kata yang keanggotaannya
biasanya kecil dan stabil. Kata-kata ini, pada umumnya,
digunakan untuk menyatakan hubungan antar open class
words.

9/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Open class words

Nomina
Kata-kata yang menyatakan orang, benda, tempat. Tunggal vs. jamak.
Konkrit vs. abstrak. Proper vs. common noun.

Verbs
Kata-kata yang menyatakan tindakan, proses, kejadian. English verbs bisa
berbeda bentuk (eat, eats, eating, eaten).

Adjectives
Kata-kata yang menyatakan sifat/atribut. Hampir semua bahasa memiliki
adjective yang menyatakan warna (hitam, putih), usia (tua, muda), dst.

Adverbs
Merupakan modifier/keterangan terhadap verb. Seringkali menjadi category
“dan lain-lain”. Contoh: “Unfortunately , John walked home extremely slowly
yesterday”
10/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Closed class words

Closed class words sebuah bahasa jumlahnya biasanya terbatas.
Penutur bahasa harusnya tahu (hampir) semua closed class words.
Disebut juga function words – memainkan peran grammatical.

Contoh:
prepositions: on, under, over, near, . . .
determiners: a, an, the
pronouns: she, who, I others
conjunctions: and, but, or, as, if, when
auxiliary verbs: can, may, should, are
particles: up, down, on, off, in, out, at, by
numerals: one, two, three, first, second, third

Bandingkan dengan open class words. Kira-kira apa ciri-ciri pembedanya?

11/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Open vs. closed

Kata-kata ini open atau closed?
Bakso
pedoman
menyakitkan
tentang
menyanyi
melakukan
melalui
bawah

Analogi CS?
Anggap closed class word seperti reserved keyword dalam bahasa
pemrograman: for, if, while, etc. Open class ≈ variable(?)

12/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Tagset

Contoh tagset bahasa Inggris

Brown corpus tagset: 87 tag (Francis and Kučera, 1982)
Penn Treebank tagset: 45 tag (Marcus et al., 1993)
C5 CLAWS BNC tagset: 61 tag (Garside et al., 1997)
C7 tagset: 146 tag (Leech et al., 1994)

Perbedaannya?
Penn Treebank menggabungkan beberapa tag menjadi satu, karena ada
informasi parse tree.
Tergantung kebutuhan!

13/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Penn Treebank Tagset

Cuplikan Penn Treebank Tagset

Tag Description Example
DT Determiner a, the
IN Preposition on, in, by
JJ Adjective big
JJR Adjective, comparative bigger
NN Noun, sing. or mass dog, snow, llama
NNS Noun, plural dogs, llamas
NNP Proper noun, singular IBM
VB Verb, base form eat
VBD Verb, past tense ate
VBG Verb, gerund eating

Contoh kalimat yang di-tag: The/DT grand/JJ jury/NN commented/VBD

on/IN a/DT number/NN of/IN other/JJ topics/NNS ./.

14/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

15/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Part-of-speech tagging

Tagging adalah proses menentukan kelas kata / part-of-speech tag untuk

setiap kata dalam sebuah teks.
Input: rangkaian kata + tagset. Output: tag yang paling tepat untuk
setiap kata.
≈ tokenization untuk bahasa pemrograman (di mana bedanya?) → POS
tagging bisa ambiguous!
Contoh:
Book that flight .
Vb Dt Nn .
Book bisa juga Nn (malahan lebih sering?).

16/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Mengamati masalah POS tagging

Sebetulnya, seberapa sulitkah POS tagging ini?
DeRose(1988): Hanya 11.5% kata Inggris unik (type) dari Brown corpus
adalah rancu.
Unambiguous (1 tag) 35340
Ambiguous (2-7 tags) 4100
2 tags 3760
3 tags 264
4 tags 61
5 tags 12
6 tags 2
7 tags 1 (“still”)
Namun demikian, 40% dari (token) di Brown corpus rancu!
Type vs. token = class vs. instance.
“the boy saw the man”:

17/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Mengamati masalah POS tagging

Sebetulnya, seberapa sulitkah POS tagging ini?
DeRose(1988): Hanya 11.5% kata Inggris unik (type) dari Brown corpus
adalah rancu.
Unambiguous (1 tag) 35340
Ambiguous (2-7 tags) 4100
2 tags 3760
3 tags 264
4 tags 61
5 tags 12
6 tags 2
7 tags 1 (“still”)
Namun demikian, 40% dari (token) di Brown corpus rancu!
Type vs. token = class vs. instance.
“the boy saw the man”: 5 token, 4 type
“pria itu berdiri di tengah pria-pria lainnya”:

17/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Mengamati masalah POS tagging

Sebetulnya, seberapa sulitkah POS tagging ini?
DeRose(1988): Hanya 11.5% kata Inggris unik (type) dari Brown corpus
adalah rancu.
Unambiguous (1 tag) 35340
Ambiguous (2-7 tags) 4100
2 tags 3760
3 tags 264
4 tags 61
5 tags 12
6 tags 2
7 tags 1 (“still”)
Namun demikian, 40% dari (token) di Brown corpus rancu!
Type vs. token = class vs. instance.
“the boy saw the man”: 5 token, 4 type
“pria itu berdiri di tengah pria-pria lainnya”: 7 token, 7 type
(Perhatikan ini adalah beda tag, bukan makna/sense.)

17/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Metode POS tagging

Secara umum, ada 3 cara:

Rule-based tagging. Cara top-down – konsultasi ahli
linguistik; definisikan aturan-aturan yang biasa digunakan
manusia.
Stochastic tagger. Cara bottom-up – gunakan corpus
sebagai training data untuk menentukan secara probabilistik
tag yang terbaik untuk sebuah kata (dalam sebuah konteks).
Transformation-based tagger. Semacam gabungan teknik
di atas. Tetap belajar dari corpus, tapi knowledge yang
dipelajari dinyatakan sebagai rule.

18/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

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.

19/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Sebuah contoh kasus

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 yang benar kecuali untuk race. Konteks
yang perlu diamati (secara bigram):
1 to/TO race/???
2 the/DT race/???

Perumusan statistik (untuk kasus pertama):

“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)

20/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Pemodelan statistik

Pada intinya, kita ingin memilih 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 )
(Pada kenyataannya, kita ingin melakukan tagging pada seluruh kalimat
sekaligus, bukan hanya satu kata!)

21/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Probabilitas mengamati sekuens kata & tag

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

22/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

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?

23/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Contoh gambar HMM

24/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

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.

25/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

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:
T̂ = argmaxT ∈τ ni=1 P(wi |w1 t1 . . . wi−1 ti−1 ti )P(ti |t1 , . . . ti−1 )
Q

Algoritma Viterbi dapat melakukan pencarian tag sequence terbaik ini

secara cepat (dynamic programming ).

26/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

27/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Persiapan data

Data: [Link]
Tool: [Link]
Siapkan dokumen training:
Dokumen training berisi kalimat yang sudah diberi tagging secara manual
dengan format:

Jokowi/NNP merayakan/VB tahun/NN baru/JJ di/IN Papua/NNP

Contoh file dokumen training dapat dilihat pada file:

postag training [Link]

28/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Pembuatan model

Buat file properties (contoh: postag [Link])

untuk menentukan setting untuk melakukan training model
POS Tagger.
Dua properti utama adalah: model: nama file model yang
akan dihasilkan trainFile: dokumen training yang akan
digunakan
Jalankan perintah untuk melakukan training:
java -classpath [Link]
[Link] -prop
postag [Link]
Akan dihasilkan sebuah model: [Link]

29/53
 Pemodelan bahasa Kelas kata
Part of speech tagging Tagging
Parsing Hands-on

Penggunaan model

Berikan parameter path/nama file tagger model (Pada contoh

ini file model disimpan dalam folder model)
Jalankan perintah: java -classpath
[Link]
[Link]
-model model/[Link]

30/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

31/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

32/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Apa itu grammar?

Grammar : aturan-aturan yang menjelaskan struktur suatu

fenomena.
Dalam bahasa, grammar ≈ tata bahasa: aturan yang
menjelaskan bagaimana merangkai kata-kata menjadi kalimat.
Istilah lain: syntax. Secara umum, berarti “hal-hal yang
berkaitan dengan tata-bahasa”.
Dengan grammar, kita bisa memahami struktur kalimat →
model lebih kaya dan ekspresif.
Kita akan melihat sebuah grammar formalism, yakni
Context-Free Grammar.

33/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Definisi formal CFG

Ingat, sebuah CFG adalah 4-tuple:

1 himpunan simbol non-terminal N
2 himpunan simbol terminal Σ (di mana N ∩ Σ = ∅)
3 himpunan production rule P, masing-masing berbentuk A → α di mana
A ∈ N, dan
α ∈ (Σ ∪ N)∗ (dkl. α adalah string simbol terminal/nonterminal)
4 sebuah start symbol S ∈ N

Bahasa formal yang dinyatakan oleh sebuah CFG adalah himpunan string yang
bisa di-derive dari symbol khusus: start symbol (S). Dalam NLP, S sering
diartikan sebagai “sentence”.

34/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Context-Free Grammar
Context-Free Grammar (CFG/Phrase-Structure Grammar/Backus-Naur
Form) adalah suatu notasi matematis yang menyatakan aturan sebuah
bahasa berdasarkan constituency.
CFG terdiri dari dua bagian:
1 sehimpunan (rewrite) rule atau production, yang menyatakan

bagaimana symbol dalam bahasa dikelompokkan

2 lexicon: daftar symbol/kata

Symbol-symbol dalam CFG terbagi 2 kelas:

1 Terminal symbols: symbol yang merepresentasikan kata dalam
bahasa (muncul dama string/kalimat).
2 Non-terminal symbols: symbol yang merepresentasikan
kelompok/aggregate/generalisasi terminal.
Lexicon adalah daftar terminal symbol.
Non-terminal yang diasosiasikan dengan terminal kadang disebut
preterminal symbol. Pada NLP, preterminal = part of speech!

35/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal
NP → ProperNoun

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal
NP → ProperNoun
Nominal → Noun | Noun Nominal

Contoh lexicon:
Lexicon bisa saja dinyatakan sebagai aturan context-free sebagai berikut:

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal
NP → ProperNoun
Nominal → Noun | Noun Nominal

Contoh lexicon:
Lexicon bisa saja dinyatakan sebagai aturan context-free sebagai berikut:
Det → a

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal
NP → ProperNoun
Nominal → Noun | Noun Nominal

Contoh lexicon:
Lexicon bisa saja dinyatakan sebagai aturan context-free sebagai berikut:
Det → a
Det → the

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh CFG

Contoh rule:
Dalam bhs. Inggris, sebuah NP bisa terdiri dari ProperNoun atau Determiner
diikuti Nominal. Sebuah Nominal bisa terdiri dari satu atau lebih Noun.
NP → Det Nominal
NP → ProperNoun
Nominal → Noun | Noun Nominal

Contoh lexicon:
Lexicon bisa saja dinyatakan sebagai aturan context-free sebagai berikut:
Det → a
Det → the
Noun → flight
(dalam kenyataannya, kurang efisien)

36/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

CFG sebagai parser

Sebagai parser:
CFG sebagai mesin yang menghasilkan struktur untuk sebuah kalimat input.

Sebagai parser, bacalah tanda “→” sebagai: “if you see the symbols on the
right, rewrite with the symbol on the left”.
S

Masalah bahasa manusia: satu

NP VP kalimat, banyak struktur
Anto
(=ambiguity/kerancuan)
Tujuan akhir parsing : agar
V NP PP
program dapat “memahami”
memakan bakso Prep NP semantics/makna dari
dengan sendok kalimat.
Notasi alternatif, bracketed notation:
[S [NP Anto ] [VP [V memakan ] [NP bakso ] [PP [Prep dengan ] [NP sendok ] ] ] ]

37/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Grammar singkat untuk bahasa Inggris (ATIS)

Lexicon untuk L0
Noun → flights — breeze — trip — morning — . . .
Verb → is — prefer — like — need — . . .
Adjective → cheapest — first — other — direct — . . .
Pronoun → me — I — you — it — . . .
ProperNoun → Alaska — Baltimore — Chicago — Garuda — . . .
Determiner → the — a — an — this — . . .
Preposition → from — to — on — near — . . .

Grammar untuk L0
S → NP VP I + prefer a morning flight
NP → Pronoun I
— ProperNoun Los Angeles
— Det Nominal a + flight
Nominal → Noun Nominal morning + flight
— Noun flights
VP → Verb do
— Verb NP prefer a morning flight
— Verb NP PP leave Boston in the morning
— Verb PP leave in the morning
PP → Prep NP from Los Angeles

38/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Grammaticality
Kalimat-kalimat yang bisa di-derive dari S dikatakan grammatical.
Kalimat-kalimat yang TIDAK bisa di-derive dari S dikatakan
ungrammatical.
Perbedaan yang sangat “tajam” untuk bahasa formal seperti ini
terkadang kurang cocok untuk bahasa natural/manusia . . .
Dalam bidang linguistics, pemodelan ini disebut generative grammar
(Chomsky), akhir ’60-an.

Apakah kalimat-kalimat berikut grammatical (menurut L0 )?

You need a trip to Baltimore.
I prefer a morning trip.
I prefer a trip morning.
I do to you.

39/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Grammaticality
Kalimat-kalimat yang bisa di-derive dari S dikatakan grammatical.
Kalimat-kalimat yang TIDAK bisa di-derive dari S dikatakan
ungrammatical.
Perbedaan yang sangat “tajam” untuk bahasa formal seperti ini
terkadang kurang cocok untuk bahasa natural/manusia . . .
Dalam bidang linguistics, pemodelan ini disebut generative grammar
(Chomsky), akhir ’60-an.

Apakah kalimat-kalimat berikut grammatical (menurut L0 )?

You need a trip to Baltimore.
I prefer a morning trip.
I prefer a trip morning.
I do to you.

Pesan kepada sang linguist: Perhatikan masalah overgeneration!

39/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

40/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Dunia tidak hitam dan putih

CFG mempartisi string NLP menjadi 2: sah (di-accept) dan

tidak (di-reject).
Namun, bahasa tidak sediskrit ini. Ada kalimat yang “lebih
sah” dari yang lain.
Pendekatan formal tidak menangani disambiguation.
Pokoknya, kembalikan semua kemungkinan!
Language modelling: sebuah model yang lebih akurat.
Aplikasi: psycholinguistics, NLU, NLG, speech recognition

41/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Menambahkan probabilitas
Rule sebuah CFG secara non-deterministik menjabarkan semua kemungkinan
rewrite sebuah non-terminal:
Contoh kemungkinan expansion VP:
VP → Verb
VP → Verb NP
VP → Verb NP NP

42/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Menambahkan probabilitas
Rule sebuah CFG secara non-deterministik menjabarkan semua kemungkinan
rewrite sebuah non-terminal:
Contoh kemungkinan expansion VP:
VP → Verb
VP → Verb NP
VP → Verb NP NP

Dengan PCFG, kita nyatakan probabilitas setiap kemungkinan expansion

terjadi.

42/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Menambahkan probabilitas
Rule sebuah CFG secara non-deterministik menjabarkan semua kemungkinan
rewrite sebuah non-terminal:
Contoh kemungkinan expansion VP:
VP → Verb [0.55]
VP → Verb NP [0.40]
VP → Verb NP NP [0.05]

Dengan PCFG, kita nyatakan probabilitas setiap kemungkinan expansion

terjadi.
Notasi: A → β[p], di mana p = P(A → β|A)
Jumlah probabilitas semua kemungkinan rule yang meng-expand A harus
1.

42/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Definisi formal CFG

Sebuah CFG adalah 4-tuple G = (N, Σ, P, S ):

1 himpunan simbol non-terminal N
2 himpunan simbol terminal Σ (di mana N ∩ Σ = ∅)
3 himpunan production rule P, masing-masing berbentuk A → α di mana
A ∈ N, dan
α ∈ (Σ ∪ N)∗ (dkl. α adalah string simbol terminal/nonterminal)
4 sebuah start symbol S ∈ N

43/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Definisi formal PCFG

Sebuah PCFG adalah 5-tuple G = (N, Σ, P, S, D):

1 himpunan simbol non-terminal N
2 himpunan simbol terminal Σ (di mana N ∩ Σ = ∅)
3 himpunan production rule P, masing-masing berbentuk A → α di mana
A ∈ N, dan
α ∈ (Σ ∪ N)∗ (dkl. α adalah string simbol terminal/nonterminal)
4 sebuah start symbol S ∈ N
5 sebuah fungsi D yang menyatakan nilai probabilitas [0,1] untuk setiap
rule A → α ∈ P

43/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh PCFG

44/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

45/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Disambiguation dengan PCFG

Menghitung probabilitas sebuah parse tree T
Probabilitas T untuk sebuah kalimat S adalah hasil perkalian
probabilitas semua rule Q
r yang digunakan untuk meng-expand setiap
node n ∈ T : P(T , S) = n∈T p(r (n))
P(T , S) = P(T ). Mengapa? P(T , S) = P(T ) × P(S|T ). Namun
P(S|T ) pasti 1, karena parse tree secara deterministik menentukan
kalimat (postorder leaf traversal?)

Disambiguation dengan PCFG:

Definisi: τ (S) = himpunan semua kemungkinan parse tree untuk S.
Parse tree yang “tepat” untuk sebuah kalimat S adalah parse tree dengan
probabilitas tertinggi:
P(T ,S)
T̂ (S) = argmaxT ∈τ (S) P(T |S) = argmaxT ∈τ (S) P(S)
T̂ (S) = argmaxT ∈τ (S) P(T , S) = argmaxT ∈τ (S) P(T )

46/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Contoh disambiguation dengan PCFG

Ta ≈ “bisakah anda
memesan penerbangan
untuk TWA”?
Tb ≈ “bisakah anda
memesan penerbangan
maskapai TWA”?
P(Ta ) = .15 × .40 × .05 ×
.05 × .35 × .75 × .40 × .40 ×
.40 × .30 × .40 × .50 =
1.5 × 10−6
P(Tb ) = .15 × .40 × .40 ×
.05 × .05 × .75 × .40 × .40 ×
.40 × .30 × .40 × .50 =
1.7 × 10−6

47/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Language modelling

PCFG juga menyatakan probabilitas sebuah kalimat S.

Hal ini berguna untuk berbagai aplikasi, mis. speech recognition:
I like ice cream
I like I scream.
Untuk kalimat yang unambiguous, P(S) = P(T , S) = P(T ).
Probabilitas sebuah kalimat S yang ambiguous adalah jumlah probabilitas
semua parse tree T ∈ τ (S):
P P
P(S) = T ∈τ (S) P(T , S) = T ∈τ (S) P(T )
Penjabaran semua parse tree tidak efisien → dynamic programming.
Inside algorithm pada PCFG ≈ Forward algorithm pada HMM.
Menjumlahkan probabilitas semua {parse tree / state sequence} untuk
sebuah {input string / observation sequence}.

48/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Menghitung probabilitas dari treebank

Dari mana asalnya nilai probabilitas PCFG?

Dari sebuah corpus yang telah di-parse secara manual, atau treebank.
Contohnya: Penn Treebank (Marcus et al. 1993)
Probabilitas sebuah expansion rule α → β bisa dihitung: berapa kali
α → β terjadi, dibagi dengan kemunculan α:
Count(α → β) Count(α → β)
P(α → β|α) = P =
γ Count(α → γ) Count(α)
Treebank harus dihasilkan secara manual, ongkosnya mahal.

49/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Outline

1 Pemodelan bahasa
2 Part of speech tagging
Kelas kata
Tagging
Hands-on
3 Parsing
Grammar
Probabilistic parsing
Menggunakan PCFG
Hands-on

50/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Persiapan data
Data: [Link]
Tool: [Link]
Siapkan dokumen training:
Dokumen training berisi kalimat yang sudah diberi bracketing secara
manual dengan format:

(ROOT (S (NP-SBJ (NNP (Gates)) (CC (dan)) (NNP (Buffett))) (VP

(VB (mengatakan)) (SBAR (SC (0)) (S (NP-SBJ (PRP (mereka))) (VP
(VP (VB (berada)) (PP (IN (di)) (NP (NNP (Cina))))) (SBAR (SC
(untuk)) (S (NP-SBJ (*)) (VP (VB (mempelajari)) (NP (NP (NN
(kegiatan)) (NN (amal))) (PP (IN (di)) (NP (NN (negara)) (PR
(itu)))))))))))) (Z (.))))

Contoh file dokumen training dapat dilihat pada file:

parser [Link]

51/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Pembuatan model

Jalankan perintah untuk melakukan training:

java
edu/stanford/nlp/parser/shiftreduce/ShiftReduceParser
-trainTreebank parser [Link]
-devTreebank parser [Link]
-serializedPath Indonesian [Link]
Akan dihasilkan sebuah model: Indonesian [Link]
Jalankan perintah:
java ParserShiftReduce "Jokowi merayakan tahun
baru di Papua"

52/53
 Grammar
Pemodelan bahasa
Probabilistic parsing
Part of speech tagging
Menggunakan PCFG
Parsing
Hands-on

Ringkasan

Model bahasa sangat berguna dalam berbagai aplikasi NLP

POS tagging: memprediksi sekuens POS tag sebuah teks. Model linear.
Parsing: memprediksi struktur konstituensi sebuah teks. Model hirarkis.
Distribusi probabilitas dihitung dari tagged corpus / treebank, dimodelkan
dengan HMM/PCFG.
Lebih banyak training data, lebih baik :-)

53/53