Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing): Bài 4(tt) - Lê Thanh Hương

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