Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Chương 4: Phân tích cú pháp xác suất - Lê Thanh Hương

Phân tích cú pháp xác 
suất
Lê Thanh Hương
1
Bộ môn Hệ thống Thông tin
Viện CNTT &TT – Trường ĐHBKHN
Email: huonglt-fit@mail.hut.edu.vn
Làm cách nào chọn cây đúng?
z Ví dụ: 
I saw a man with a telescope.
z Khi số luật tăng, khả năng nhập nhằng tăng
z Tập luật NYU: bộ PTCP Apple pie : 20,000-30,000 
2
luật cho tiếng Anh
z Lựa chọn luật AD: V DT NN PP
(1) VP → V NP PP
NP → DT NN
(2) VP → V NP
NP → DT NN PP
Kết hợp từ (bigrams pr)
Ví dụ:
Eat ice-cream (high freq)
Eat John (low, except on Survivor)
Nhược điểm:
z P(John decided to bake a) có xác suất cao
z Xét:
P(w3) = P(w3|w2w1)=P(w3|w2)P(w2|w1)P(w1)
3
Giả thiết này quá mạnh: chủ ngữ có thể quyết định bổ ngữ trong 
câu
Clinton admires honesty
¾ sử dụng cấu trúc ngữ pháp để dừng việc lan truyền
z Xét Fred watered his mother’s small garden. Từ garden có 
ảnh hưởng như thế nào?
z Pr(garden|mother’s small) thấp ⇒ mô hình trigram không tốt
z Pr(garden | X là thành phần chính của bổ ngữ cho động từ to 
water) cao hơn
¾ sử dụng bigram + quan hệ ngữ pháp
Kết hợp từ (bigrams pr)
z V có một số loại bổ ngữ nhất định
⇒ Verb-with-obj, verb-without-obj
z Sự tương thích giữa chủ ngữ và bổ ngữ:
John admires honesty 
Honesty admires John ???
4
Nhược điểm:
• Kích thước tập ngữ pháp tăng
z Các bài báo của tạp chí Wall Street Journal trong 1 năm: 
47,219 câu, độ dài trung bình 23 từ, gán nhãn bằng tay: chỉ 
có 4.7% hay 2,232 câu có cùng cấu trúc ngữ pháp
¾ Không thể dựa trên việc tìm các cấu trúc cú pháp đúng cho 
cả câu. Phải xây dựng tập các mẫu ngữ pháp nhỏ
Ví dụ
S
VP VP
VP
Luật 3
5
This apple pie looks good and is a real treat
DT NN NN VBX JJ CC VBX DT JJ NN
NP NP
VP ADJLuật 1 
Luật 2 
Luật 
1. NP→DT NN NN
2. NP→DT JJ NN
3. S→NP VBX JJ CC VBX NP
z Nhóm (NNS, NN) thành NX; (NNP, NNPs)=NPX; 
(VBP, VBZ, VBD)=VBX;
6
z Chọn các luật theo tần suất của nó
Tính xác suất
X NP
1470
Pr(X →Y)
7
Y DT JJ NN
9711
NP
= = 0.1532
Tính Pr
S
NP VP
DT JJ NN VBX NP
DT JJ NNThe big guy
ate
1
4
3
S → NP VP; 0.35
NP → DT JJ NN; 0.1532
VP → VBX NP; 0.302
2
8
Luật áp dụng Chuỗi Pr
1 S →NP VP 0.35
2 NP → DT JJ NN 0.1532 x 0.35 = 0.0536
3 VP → VBX NP 0.302 x 0.0536= 0.0162
4 NP → DT JJ NN 0.1532 x 0.0162=0.0025
Pr = 0.0025
the apple pie
Văn phạm phi ngữ cảnh xác suất
z 1 văn phạm phi ngữ cảnh xác suất (Probabilistic Context 
Free Grammar) gồm các phần thông thường của CFG
z Tập ký hiệu kết thúc {wk}, k = 1, . . . ,V
z Tập ký hiệu không kết thúc {Ni}, i = 1, . . . ,n
z Ký hiệu khởi đầu N1
9
z Tập luật {Ni → ζj}, ζj là chuỗi các ký hiệu kết thúc và không 
kết thúc
z Tập các xác suất của 1 luật là:
∀i ∑j P(Ni → ζj) = 1
z Xác suất của 1 cây cú pháp:
P(T) = Πi=1..n p(r(i))
Các giả thiết
z Độc lập vị trí: Xác suất 1 cây con không phụ thuộc vào vị trí 
của các từ của cây con đó ở trong câu
∀k, P(Njk(k+c) →ζ) là giống nhau
z Độc lập ngữ cảnh: Xác suất 1 cây con không phụ thuộc vào 
10
các từ ngoài cây con đó
P(Njkl→ζ| các từ ngoài khoảng k đến l) = P(Njkl→ζ)
z Độc lập tổ tiên: Xác suất 1 cây con không phụ thuộc vào 
các nút ngoài cay con đó
P(Njkl→ζ| các nút ngoài cây con Njkl ) = P(Njkl→ζ)
Các thuật toán
z CKY
z Beam search
z Agenda/chart based search
11
- 
z 
CKY kết hợp xác suất
z Cấu trúc dữ liệu:
z Mảng lập trình động π[i,j,a] lưu xác suất lớn nhất 
của ký hiệu không kết thúc a triển khai thành chuỗi 
ij. 
ế ế ầ
12
z Backptrs lưu liên k t đ n các thành ph n trên cây
z Ra: Xác suất lớn nhất của cây
Tính Pr dựa trên suy diễn
z Trường hợp cơ bản: chỉ có 1 từ đầu vào
Pr(tree) = pr(A→ wi)
z Trường hợp đệ qui: Đầu vào là xâu các từ
A⇒wij if ∃k: A→ ΒC, B ⇒wik ,C ⇒wkj ,i≤k ≤j. * **
13
p[i,j] = max(p(A→ ΒC) x p[i,k] x p[k,j]). 
i k j
A
B C
wij
14
TÍnh xác suất Viterbi (thuật toán 
CKY)
15
0.0504
Ví dụ
z S Æ NP VP 0.80
z NP Æ Det N 0.30
z VP Æ V NP 0.20
z VÆ includes 0 05
z Det Æ the 0.50
z Det Æ a 0.40
z N Æ meal 0.01
z NÆ flight 0 02 . .
Dùng thuật toán CYK phân tích câu vào:
“The flight includes a meal”
Tính Pr
1. S → NP VP 1.0
2. VP → V NP PP 0.4
3. VP → V NP 0.6
4. NP → N 0.7
5. NP → N PP 0.3
6. PP → PREP N 1.0 NP NP PP
VP
S VP
NP
PP
V N
1.0
0.4
0 7 0 7
0.6
0.3
17
7. N → a_dog 0.3
8. N → a_cat 0.5
9. N → a_telescop 0.2
10. V → saw 1.0
11. PREP → with 1.0
N V N PREP N 
PREP N 
.
0.3 1.0 0.5 1.0 0.2
.
1.0
1.0
Pl = 1×.7×.4×.3×.7×1×.5×1×1×.2 = .00588 
Pr = 1×.7×.6×.3×.3×1×.5×1×1×.2 = .00378
¾ Pl is chosen
a_dog saw a_cat with a_telescope
Xác suất Forward và Backward
The big brown fox
NP
N’
N’’
The
big
t 
Xt
1 t-1 T
• Forward= xác suất các phần 
tử trên và bao gồm 1 nút cụ 
thể nào đó
18
Nbrown
fox
Forward
Probability =
ai(t)=P(w1(t-1), Xt=i)
i
Backward 
Probability =
bi(t)=P(wtT |Xt=i)
bi(t)
ai(t)
• Backward= xác suất các 
phần tử dưới 1 nút cụ thể 
nào đó
Xác suất trong và ngoài
N1= Start
Nj
β
α
Outside αj(p,q)
Inside βj(p,q)
19
z Npq = ký hiệu không kết thúc Nj trải từ vị trí p đến q trong 
xâu
z αj = xác suất ngoài (outside)
z βj = xác suất trong (inside)
z Nj phủ các từ wp  wq, nếu Nj ⇒∗ wp  wq
w1 wmwp wq wq+1wp-1
N1= Start
Nj
α
Outside αj(p,q)
Inside βj(p,q)
Xác suất trong và ngoài
20
w1 wm
β
wp wq wq+1wp-1
αj(p,q) βj(p,q) = P(N1⇒∗ w1m , Nj ⇒∗ wpq | G)
= P(N1⇒∗ w1m |G)• P(Nj ⇒∗ wpq | N1⇒∗ w1m, G)
αj(p,q)=P(w1(p-1) , Npqj,w(q+1)m|G)
βj(p,q)=P(wpq|Npqj, G)
Tính xác suất của xâu
z Sử dụng thuật toán Inside, 1 thuật toán lập trình động dựa 
trên xác suất inside
P(w1m|G) = P(N1 ⇒* w1m|G) = P(w1m|N1m1, G) = β1(1,m)
21
z Trường hợp cơ bản:
βj(k,k) = P(wk|Nkkj, G)=P(Nj → wk|G)
z Suy diễn:
βj(p,q) = Σr,sΣd∈(p,q-1) P(Nj → NrNs) βr(p,d) βs(d+1,q)
Suy diễn
Nj
P(Nj → NrNs)
Tính βj(p,q) với p < q – tính trên tất cả các điểm j –
thực hiện từ dưới lên
22
Nr Ns
wp wdwd+1 wq
βr(p,d) βs(d+1,q)x
-nhân 3 thành phần, tính 
tổng theo j, r,s.
Ví dụ
1. S → NP VP 1.0
2. VP → V NP PP 0.4
3. VP → V NP 0.6
4. NP → N 0.7
5. NP → N PP 0.3 NP NP PP
VP
S VP
NP
PP
V N
1.0
0.4
0.6
0.3
23
6. PP → PREP N 1.0
7. N → a_dog 0.3
8. N → a_cat 0.5
9. N → a_telescope 0.2
10. V → saw 1.0
11. PREP → with 1.0 P(a_dog saw a_cat with a_telescope) =
N V N PREP N 
PREP N 
0.7
0.3 1.0 0.5 1.0 0.2
0.7
1.0
1.0
1×.7×.4×.3×.7×1×.5×1×1×.2 + ... ×.6... ×.3... = .00588 + .00378 = .00966
Tìm kiếm kiểu chùm
z Tìm kiếm trong không gian trạng thái
z Mỗi trạng thái là một cây cú pháp con với 1 xác suất 
nhất định
z Tại mỗi thời điểm, chỉ giữ các thành phần có điểm cao nhất
24
Làm giàu PCFG
z PCFG đơn giản hoạt động không tốt do các 
giả thiết độc lập
z Giải quyết: Đưa thêm thông tin
Ph th ộ ấ t ú
25
z ụ u c c u r c
z Việc triển khai 1 nút phụ thuộc vào vị trí của nó 
trên cây ( độc lập với nội dung về từ vựng của nó)
z Ví dụ: bổ sung thông tin cho 1 nút bằng cách lưu 
giữ thông tin về cha của nó: SNP khác với VPNP
Làm giàu PCFG
z PCFG từ vựng hóa : PLCFG (Probabilistic 
Lexicalized CFG, Collins 1997; Charniak 
1997)
z Gán từ vựng với các nút của luật
z Cấu trúc Head
26
z Mỗi phần tử của parsed tree được gắn liền với 
một lexical head 
z Để xác định head của một nút trong ta phải xác 
định trong các nút con, nút nào là head (xác định 
head trong vế phải của một luật).
Làm giàu PLCFG
VP(dumped) → VBD(dumped) NP(sacks) PP(into) 3*10-10
VP(dumped) → VBD(dumped) NP(cats) PP(into) 8*10-11
27
Tại sao dùng PLCFG
z Tính ngoại lệ (exception) của ngôn ngữ
z Sự phân loại theo cú pháp hiện tại chưa thể 
hiện hết đặc tính hoạt động của từng từ 
vựng.
z Từ vựng hóa luật CFG giúp bộ phân tích cú 
pháp thực hiện chính xác hơn
Hạn chế của PLCFG
VP -> VBD NP PP
VP(dumped) -> VBD(dumped) NP(sacks) 
PP(into)
z Không có một corpus đủ lớn!
z Thể hiện hết các trường hợp cú pháp, hết các 
trường hợp đối với từng từ.
Penn Treebank
z Penn Treebank: tập ngữ liệu có chú giải ngữ 
pháp, có 1 triệu từ, là nguồn ngữ liệu quan 
trọng
z Tính thưa:
30
z có 965,000 mẫu, nhưng chỉ có 66 mẫu WHADJP, 
trong đó chỉ có 6 mẫu không là how much hoặc 
how many
z Phần lớn các phép xử lý thông minh phụ thuộc 
vào các thống kê mối quan hệ từ vựng giữa 2 
từ liền nhau:
A Penn Treebank tree
31
Đánh giá độ chính xác của PTCP
z Độ chính xác của parser được đo qua việc tính xem có bao 
nhiêu thành phần ngữ pháp trong cây giống với cây chuẩn, gọi là 
gold-standard reference parses.
z Độ chính xác (Precision) =
% trường hợp hệ gán đúng
32
tổng số trường hợp hệ gán 
(%THợp hệ tính đúng). 
z Độ phủ (Recall) =
% số trường hợp hệ gán đúng
tổng số trường hợp đúng 
(%THợp hệ tính đúng so với con người). 
Biểu diễn cây theo các thành phần 
ngữ pháp
Đánh giá
Ví dụ 2
35
Độ chính xác của các hệ thống 
PTCP
36