Outline. IKI 40931: Topik Khusus: NLP Kuliah 7: Parsing CFG. Parsing. Contoh parsing. Ruli Manurung. 10 Maret (Bab Jurafsky & Martin)

Parsing sebagai search: top-down, bottom-up Top-down + bottom-up: v1 Tiga masalah dengan algo v1 Chart parsing


Outline IKI 40931: Topik Khusus: NLP Kuliah 7: Parsing CFG

1

Parsing sebagai search: top-down, bottom-up

2

Top-down + bottom-up: v1

3

Tiga masalah dengan algo v1

4

Chart parsing

(Bab 10.1 - 10.4 Jurafsky & Martin)

Ruli Manurung Fakultas Ilmu Komputer Universitas Indonesia

10 Maret 2008

Ruli Manurung

IKI40931 • Kuliah 5 • 10 Maret 2008


Ruli Manurung



Parsing

Contoh parsing Contoh grammar G:

CFG mengandung declarative knowledge: susunan kata apa saja yang membuat kalimat sah. Knowledge ini dapat digunakan untuk generation maupun understanding. Tahap awal understanding adalah untuk mengetahui struktur sebuah kalimat berdasarkan sebuah grammar. Definisi proses parsing (penguraian) Jika diberikan sebuah kalimat K dan sebuah CFG g, tentukan urutan aplikasi rule dalam g yang menghasilkan K (dkl., gambarkan parse tree K ) Bagaimana algoritma/prosesnya?

Ruli Manurung


Contoh kalimat:

S → NP VP S → Aux NP VP S → VP NP → Det Nominal Nominal → Noun Nominal → Noun Nominal NP → ProperNoun VP → Verb VP → Verb NP Det → that | this | a Noun → book | flight | meal | money Verb → book | include | prefer Aux → does Prep → from | to | on ProperNoun → Houston | TWA Nominal → Nominal PP

Ruli Manurung

Parse-lah kalimat “Book that flight” dengan grammar G.




Parsing sebagai search

Top-down parsing

Search: strategi pemecahan masalah. Nyatakan sebagai state space, di mana state = abstraksi masalah. Terdapat goal state yang dicapai melalui serangkaian action.

1

State space pada parsing = himpunan semua kemungkinan parse tree → didefinisikan oleh grammar .

4

Action yang bisa diambil untuk pindah dari state X ke X 0 adalah rewrite rule dari CFG.

2 3

Bangun parse tree mulai dari root S. Aplikasikan semua rule yang LHS-nya S. Aplikasikan semua rule yang LHS-nya hasil expansion dari S. . . . ulangi seterusnya sampai sukses . . .

Contoh proses top-down parsing

Tujuan search adalah mencari goal state yang menyatakan parse tree untuk K . Goal ini memiliki dua constraint: dari grammar: parse tree di goal state harus memiliki root S. dari data: parse tree dan semua leaf -nya adalah kata-kata k ∈ K . Sebuah pertanyaan: Dari mana kita memulai (initial state)? ke arah mana kita melangkah? Secara teoritis, bisa saja murni random: generate-and-test Ruli Manurung



1

3 4



Bottom-up parsing 2

Ruli Manurung

Bottom-up parsing (lanjutan)

Bangun parse tree mulai dari leaf berupa kata k ∈ K . Aplikasikan semua rule yang RHS-nya k . Aplikasikan semua rule yang RHS-nya hasil rewrite dari k . . . . ulangi seterusnya sampai sukses . . .

Lanjutan contoh proses bottom-up parsing

Contoh proses bottom-up parsing

Ruli Manurung


Ruli Manurung




Menggabungkan top-down & bottom-up: v1

Top-down vs. Bottom-up Top-down parsing +: -:

hanya mengunjungi state yang menyatakan parse tree dengan root node S. mengunjungi state yang tidak mungkin mencapai parse tree yang memiliki leaf yang tepat berisi k ∈ K .

-:

Bagaimana cara menggabungkan teknik top-down & bottom-up? Sebuah usulan: Gunakan sebuah teknik sebagai strategi utama, gunakan constraint dari teknik yang satu lagi sebagai filter untuk parse yang tidak cocok.

Bottom-up parsing +:

Jika kita bisa memanfaatkan constraint dari sisi data DAN sisi grammar , proses search bisa dipercepat!

hanya mengunjungi state yang menyatakan parse tree dengan leaf yang tepat berisi k ∈ K . mengunjungi state yang tidak mungkin mencapai parse tree dengan root node S.

Kita akan melihat contoh top-down strategy with bottom-up filtering. Bisa saja dirancang algoritma bottom-up strategy with top-down filtering. Mulai dengan implementasi top-down strategy.

Keduanya fokus pada salah satu constraint saja, dan mengabaikan yang satu lagi . . . Ruli Manurung



Ruli Manurung



Implementasi top-down parser

Contoh proses depth-first top-down parse

Pada pembahasan strategi top-down, diasumsikan mencoba semua kemungkinan expansion secara paralel → breadth first search. Memory requirement BFS tidak feasible: exponential complexity! Solusi: gunakan strategi depth-first search. Ketika meng-expand sebuah node, tambahkan semua kemungkinan ke agenda (fringe), pilih yang paling jauh dari root. Agenda = struktur data LIFO (Last In, First Out) → implementasi sebagai stack . Dua isu lagi: Leaf mana yang mau di-expand? (Bedakan antara search tree dan parse tree!) Biasanya, pilih leaf pojok kiri bawah. Rule mana yang mau diaplikasikan? Biasanya, pilih rule pertama yang cocok. Ruli Manurung


Ruli Manurung




Algoritma Depth-First Top Down Parser

Ruli Manurung



Ruli Manurung



Contoh: “Does this flight include a meal?”

Ruli Manurung




Ruli Manurung





Sebuah pengamatan: konsep left-corner Algoritma depth-first menggunakan current input untuk menentukan kapan harus backtrack. Current input harus bisa menjadi kata pertama dari derivasi/frase yang sedang di-expand. Kita sebut kata pertama dari derivasi ini sebagai left corner.

Left corner secara formal ∗

B adalah left-corner untuk A jika A ⇒ Bα Ruli Manurung



Ruli Manurung



Bottom-up filtering

Masalah 1: Left-recursion Left-recursion: grammar tertentu bisa menyebabkan infinite loop.

Informasi current input bisa digunakan untuk (sedikit) mempercepat search! Contoh: ketika memulai parsing kalimat “Does this flight include a meal?”, ada 3 rule S: S → NP VP S → Aux NP VP ←− hanya ini yang perlu dilihat! S → VP Dengan algo di atas, left-corner baru membantu ketika sudah sampai POS. Padahal, left-corner untuk semua category bisa dihitung untuk sembarang grammar (coba lihat grammar di papan!). Category Left corner S Det, ProperNoun, Aux, Verb NP Det, ProperNoun Nominal Noun VP Verb

Ruli Manurung


Left-recursive rule Rule yang berbentuk A → Aβ, mis.: NP → NP PP (“bakso dengan bihun”) VP → VP PP (“memakan bakso dengan Anto”) S → S Conj S (“Anto makan bakso dan Budi makan dodol”)

Ruli Manurung




Masalah 1: Left-recursion

Structural ambiguity

Left-recursive grammar ∗

∗

Grammar yang mengandung non-terminal A di mana A ⇒ αAβ dan α ⇒ . Contoh, aturan untuk possessive NP, mis. “Atlanta’s airport”, sbb. NP → Det Nominal

Bahasa memiliki banyak kerancuan. Selain POS ambiguity (satu kata, banyak POS), mis. “book” sebagai verb atau noun, ada juga structural ambiguity: Attachment ambiguity Coordination ambiguity Noun-phrase bracketing ambiguity.

Det → NP 0 s Dua solusi “hack” Rancang ulang grammar: ada prosedur otomatis yang membuat weakly-equivalent grammar (accept/reject bahasa yang sama, struktur berbeda).

Groucho Marx, Animal Crackers, 1930: One morning, I shot an elephant in my pajamas. How he got into my pajamas I don’t know.

Batasi kedalaman rekursi (depth-limited search).

Ruli Manurung



Ruli Manurung



Structural ambiguity

Repeated parsing of subtrees Wasting time: Ketika mencoba mem-parse sebuah kalimat, top-down parser seringkali membangun parse tree untuk sebagian input, lalu backtrack, lalu membangun ulang, dst.

Secara teoritis, jumlah parse untuk natural language bisa exponential. Dalam kenyataan, manusia (biasanya) tidak kesulitan memilih parse tree yang benar. Disambiguation secara otomatis memerlukan informasi statistik dan/atau semantik. Tugas parser : laporkan semua kemungkinan parse! Ruli Manurung


Ruli Manurung




Repeated parsing of subtrees

Earley Algorithm Ketiga masalah di atas bisa diatasi dengan Earley Algorithm, yang dikenal juga sebagai chart parsing. Menggunakan teknik dynamic programming: mencatat hasil sementara. Sebuah struktur data chart menyimpan semua partial parse yang memenuhi constraint top dan bottom. Chart berisi state-state yang menyatakan partial parse. Pada akhir proses, chart berisi goal state. Notasi dotted rule Sebuah state direpresentasikan dengan notasi dotted rule, yang berisi 3 hal:

Ruli Manurung

1

Sebuah subtree yang menyatakan sebuah grammar rule

2

“Status”/”progress” dalam mem-parse subtree tsb.

3

Posisi subtree tersebut terhadap kalimat input


Ruli Manurung




Dotted rules

Tiga operator penting

Contoh: Rule S → • VP

Posisi [0,0]

NP → Det • Nominal

[1,2]

VP → V NP •

[0,3]

Baca “Saya prediksi bahwa mulai posisi 0 akan ada VP yang membentuk S” “Saya prediksi bahwa mulai posisi 1 akan ada Det Nominal yang membentuk NP. Nah, sampai dengan posisi 2 saya sudah melihat Det” “Saya sudah menemukan sebuah VP, yang terdiri dari V NP, dan merentang dari posisi 0 sampai 3”

Ada tiga operator penting dalam algoritma Earley: 1

Operator P REDICTOR

2

Operator S CANNER

3

Operator C OMPLETER

Ketiga operator ini mengambil input sebuah generating state dan menghasilkan state(-state) baru, yang lalu ditambahkan ke chart.

Ruli Manurung


Ruli Manurung




P REDICTOR

S CANNER

Fungsi operator P REDICTOR adalah untuk menambahkan top-down prediction selama proses parsing berjalan.

Fungsi operator S CANNER bottom-up: ia mengamati kata-kata yang muncul pada kalimat input dan meng-update status/progress state yang menantikannya.

Definisi

Definisi

Jika sebuah state memiliki non-terminal di sebelah kanan dot yang bukan part-of-speech category, P REDICTOR menambahkan 1 state untuk setiap kemungkinan expansion rule untuk non-terminal tersebut. State dimulai dan berakhir pada posisi di mana generating state berakhir.

Jika sebuah state memiliki part-of-speech category di sebelah kanan dot, S CANNER memeriksa kata input pada posisi state tersebut dan, jika cocok, menambahkan 1 state di mana dot-nya dimajukan sesudah POS category tsb.

Contoh

Contoh

Input/generating state: S → • VP, [0,0] Output/added state: VP → • Verb, [0,0] VP → • Verb NP, [0,0]

Input/generating state: VP → • Verb NP, [0,0] Condition: Ada kata book muncul antara posisi 0 dan 1, dan book bisa jadi Verb. Output/added state: VP → Verb • NP, [0,1] Ruli Manurung



Ruli Manurung



C OMPLETER

Earley Algorithm

Fungsi operator C OMPLETER adalah untuk mengamati category (selain POS) yang ditemukan selama parsing dan meng-update status/progress semua state lain yang menantikannya. Definisi Jika sebuah state menyatakan ditemukannya sebuah category (dot sudah di akhir sebuah rule), C OMPLETER menambahkan 1 state baru untuk setiap state yang menantikan category di posisi tersebut, di mana dot-nya dimajukan sesudah category tsb. Contoh Input/generating state: NP → Det Nominal •, [1,3] Condition: Ada state VP → Verb • NP, [0,1] Output/added state: VP → Verb NP • , [0,3] (inipun jadi input C OMPLETER nanti!) Ruli Manurung


Ruli Manurung




Earley Algorithm

Contoh proses chart parsing . . .

Marilah kita menggunakan chart parsing untuk mem-parse kalimat: “Book that flight”.

Ruli Manurung



Ringkasan

Parsing bisa dianggap sebagai suatu search problem, di mana state = (partial) parse tree, dan action = CFG rewrite rule. Bisa secara top-down maupun bottom-up, bisa digabungkan dengan left-corner filtering. Masih ada masalah: left-recursion, ambiguity, recomputation. Earley algorithm, atau chart parsing, menggunakan teknik dynamic programming untuk mengatasi ketiga masalah ini!

Ruli Manurung


Ruli Manurung


Outline. IKI 40931: Topik Khusus: NLP Kuliah 7: Parsing CFG. Parsing. Contoh parsing. Ruli Manurung. 10 Maret (Bab Jurafsky & Martin)

Recommend Documents