UAS Pengolahan Bahasa Alami 2025 (B)

UAS Pengolahan Bahasa Alami 2024/2025 — Soal B

Selasa, 10 Juni 2025 · 10.00–11.30 WIB (90 menit) · Buku tertutup. Tuliskan NIM,nama,kode soal; sertakan asumsi/gambar bila perlu. Dilarang bekerja sama, menyontek, meminjam alat tulis/penghapus; pelanggaran bernilai 0.

1. Hierarchical clustering (35%)

Matriks similarity (jarak) antardokumen:

	D1	D2	D3	D4	D5	D6
D1	0	2	6	4	7	5
D2	2	0	5	3	6	4
D3	6	5	0	2	3	1
D4	4	3	2	0	2	3
D5	7	6	3	2	0	2
D6	5	4	1	3	2	0

a. Lakukan hierarchical clustering single link dan complete link. b. Gambarkan dendrogram kedua metode.

2. CFG (35%)

S   → NP VP
VP  → V NP | VP PP
NP  → Det N | NP PP
PP  → P NP
Det → the | a
N   → man | park | dog | binoculars
V   → saw | walked
P   → in | with

Kalimat: “the man saw the dog in the park with binoculars”. a. Buat tabel parsing algoritma CYK berdasarkan CFG. b. Tentukan validitas kalimat dari tabel parsing.

3. Summarization (30%)

ID	Kalimat ringkasan
M	cloud computing menyediakan layanan komputasi berbasis internet
R1	komputasi awan menawarkan layanan komputasi melalui internet
R2	layanan cloud computing memungkinkan akses data secara online
R3	teknologi cloud menyediakan layanan komputasi via jaringan internet

a. Identifikasi token unigram dan bigram tiap kalimat. b. Hitung ROUGE-L tiap referensi dibanding ringkasan model. c. Hitung Average ROUGE-L model berdasarkan tiga referensi.

1. Hierarchical clustering

Walaupun soal menyebut similarity, diagonal nol dan sebutan jarak menunjukkan interpretasi dissimilarity, sehingga jarak kecil digabung dulu. Dengan urutan tie leksikografis:

Tahap	Single link	tinggi	Complete link	tinggi
1	D3 + D6	1	D3 + D6	1
2	D1 + D2	2	D1 + D2	2
3	{D3,D6} + D4	2	D4 + D5	2
4	{D3,D4,D6} + D5	2	{D3,D6} + {D4,D5}	3
5	{D1,D2} + {D3,D4,D5,D6}	3	{D1,D2} + {D3,D4,D5,D6}	7

Tabel adalah dendrogram dalam format merge-height; tie pada tinggi 2 boleh ditukar tanpa mengubah jarak yang sesuai. Single memakai minimum jarak lintas cluster, complete maksimum.

2. CYK

Token bernomor: 1 the, 2 man, 3 saw, 4 the, 5 dog, 6 in, 7 the, 8 park, 9 with, 10 binoculars. Grammar cetak memakai S→NP VP, VP→V NP | VP PP, NP→Det N | NP PP, PP→P NP. Untuk CYK, isi diagonal dengan kategori leksikal: Det,N,V,Det,N,P,Det,N,P,N. Sel non-diagonal yang tidak kosong:

Span inklusif	Kategori
1–2	NP
4–5	NP
7–8	NP
3–5	VP
6–8	PP
1–5	S
4–8	NP
3–8	VP
1–8	S

Sel lainnya kosong, termasuk 1–10. Kata binoculars hanya N dan grammar tidak memiliki NP→N atau determiner sebelum kata itu, sehingga with binoculars tidak dapat dibentuk menjadi PP. Kalimat tidak valid menurut grammar yang tercetak, meskipun wajar dalam bahasa Inggris. Penambahan NP→N akan mengubah grammar dan memungkinkan analisis tambahan.

3. ROUGE-L

Bigram dibentuk dari setiap pasangan berurutan dalam daftar masing-masing; contohnya M memiliki cloud computing, computing menyediakan, menyediakan layanan, layanan komputasi, komputasi berbasis, berbasis internet. R1: komputasi awan, awan menawarkan, menawarkan layanan, layanan komputasi, komputasi melalui, melalui internet. R2: layanan cloud, cloud computing, computing memungkinkan, memungkinkan akses, akses data, data secara, secara online. R3: teknologi cloud, cloud menyediakan, menyediakan layanan, layanan komputasi, komputasi via, via jaringan, jaringan internet.

Referensi	Panjang LCS	Precision LCS/7	Recall LCS/panjang referensi	F1
R1	3	0,4286	0,4286	0,4286
R2	2	0,2857	0,2500	0,2667
R3	5	0,7143	0,6250	0,6667

Dengan definisi ROUGE-L sebagai F1 LCS, rata-rata makro = $(0,4286+0,2667+0,6667)/3≈0,4540$ . Jika yang dimaksud recall saja, rata-ratanya ≈0,4345; definisi harus dinyatakan.

Pembahasan ditulis independen oleh belajar.myudak, bukan kunci jawaban resmi. Soal asli tetap milik pengampu mata kuliah dan ditampilkan langsung dari arsip Google Drive.