Bài giảng Xử lý ngôn ngữ tự nhiên - 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