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

Bài giảng về "Phân tích ngữ nghĩa" thảo luận một số nội dung chủ yếu sau: Tại sao cần phân tích ngữ nghĩa? Thế nào được coi là hiểu? Một số khái niệm cơ bản về logic, logic: thuật ngữ Lambda, cách biểu diễn vị từ, sử dụng lượng từ, các thuộc tính về sự kiện,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing): Bài 4(tt) - Lê Thanh HươngLàm cách nào chọn cây đúng?Phân tích cú pháp xácsuấtzVí dụ:zKhi số luật tăng, khả năng nhập nhằng tăngTậpp luật NYU: bộ PTCP Applepp ppie : 20,000-30,000luật cho tiếng AnhLựa chọn luật AD: V DT NN PP(1) VP → V NP PPNP → DT NN(2) VP → V NPNP → DT NN PPI saw a man with a telescope.Lê Thanh HươnggBộ môn Hệ thống Thông tinViện CNTT &TT – Trường ĐHBKHNEmail: huonglt-fit@mail.hut.edu.vnzz1Kết hợp từ (bigrams pr)2Kết hợp từ (bigrams pr)Ví dụ:Eat ice-cream (high freq)Eat John (low, except on Survivor)z⇒ Verb-with-obj, verb-without-objzNhược điểm:P(John decided to bake a) có xác suất caoz Xét:P(w3) = P(w3|w2w1))=P(wP(w3|w2)P(w2|w1)P(w1)Giả thiết này quá mạnh: chủ ngữ có thể quyết định bổ ngữ trongcâuClinton admires honesty¾ sử dụng cấu trúc ngữ pháp để dừng việc lan truyềnz Xét Fred watered his mother’s small garden. Từ garden cóảnh hưởng như thế nào?zzzPr(garden|mother’s small) thấp ⇒ mô hình trigram không tốtPr(garden | X là thành phần chính của bổ ngữ cho động từ towater) cao hơn¾ sử dụng bigram + quan hệ ngữ phápVí dụNhược điểm:• Kích thước tập ngữ pháp tăngz 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 chocả câu. Phải xây dựng tập các mẫu ngữ pháp nhỏ4LuậtLuật 31.VP2.3.VPVP ADJNPDT NNSự tương thích giữa chủ ngữ và bổ ngữ:John admires honestyHonesty admires John ???3SLuật 1V có một số loại bổ ngữ nhất địnhzVPLuật 2zNP→DT NN NNNP→DT JJ NNS→NP VBX JJ CC VBX NPNhóm (NNS, NN) thành NX; (NNP, NNPs)=NPX;(VBP, VBZ, VBD)VBD)=VBX;VBX;Chọn các luật theo tần suất của nóNPNN VBX JJ CC VBX DT JJ NNThis apple pie looks good and isa real treat56Tính PrTính xác suấtPr(X →Y)X1 S2 NP VP 3NPDT JJ NN VBX NP 4The big guy ateDT JJ NNthe apple pie1470YDT JJ NNNP=S → NP VP; 0.35NP → DT JJ NN; 0.1532VP → VBX NP; 0.302= 0.1532Luật áp dụng97111 S →NP VP2 NP → DT JJ NN3 VP → VBX NP4 NP → DT JJ NNPr = 0.0025Chuỗi Pr0.350.1532 x 0.35 = 0.05360.302 x 0.0536= 0.01620.1532 x 0.0162=0.002578Các giả thiếtVăn phạm phi ngữ cảnh xác suấtzzzzzzz1 văn phạm phi ngữ cảnh xác suất (Probabilistic ContextFree Grammar) gồm các phần thông thường của CFGTập ký hiệu kết thúc {wk}, k = 1, . . . ,VTập ký hiệu không kết thúc {Ni}, i = 1, . . . ,nKý hiệu khởi đầu N1Tập luật {Ni → ζj}, ζj là chuỗi các ký hiệu kết thúc và khôngkết thúcTập các xác suất của 1 luật là:∀i ∑j P(Ni → ζj) = 1Xác suất của 1 cây cú pháp:P(T) = Πi=1..n p(r(i))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 nhauzĐộcộ lậpập ngữg cảnh: Xác suất 1 câyy con khônggpphụụ thuộcộ vàocá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àocác nút ngoài cay con đóP(Njkl→ζ| các nút ngoài cây con Njkl ) =910CKY kết hợp xác suấtCác thuật toánzzzzzP(Njkl→ζ)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ấtcủa ký hiệu không kết thúc a triển khai thành chuỗii…j.z Backptrs lưu liên kếtế đếnế các thành phầnầ trên câyCKYBeam searchAgenda/chart based searchAgenda/chart-based…z11Ra: Xác suất lớn nhất của cây12Tính Pr dựa trên suy diễnzTrường hợp cơ bản: chỉ có 1 từ đầu vàozTrường hợp đệ qui: Đầu vào là xâu các từ* ij if ∃k: A→ ΒC, B ⇒w* ik ,C ⇒w* kj ,i≤k ≤j.A⇒wp[i,j] = max(p(A→ ΒC) x p[i,k] x p[k,j]).Pr(tree) = pr(A→ wi)ABiCkwijj13TÍnh xác suất Viterbi (thuật toánCKY)14Ví dụzzzzS Æ NP VPNP Æ Det NVP Æ V NPV Æ includes0.800.300.200 050.05zzzzDet Æ theDet Æ aN Æ mealN Æ flight0.500.400.010 020.02Dùng thuật toán CYK phân tích câu vào:“The flight includes a meal”0.050415Xác suất Forward và BackwardTính Pr1.2.3.4.5.6.7.8.9.10.11.S → NP VPVP → V NP PPVP → V NPNP → NNP → N PPPP → PREP NN → a_dogN → a_catN → a_telescopV → sawPREP → with1.00.40.60.70.31.00.30.50.21.01.0VP0.6NPS1.0NP070.7VP0.4NP070.70.3PPVN1.0N V N PREP N0.3 1.0 0.5 1.0 0.21 t-1… t …TThe big brown foxNPPP1.0PREP NbigForwardProbability =ai(t)=P(w1(t-1), Xt=i)N’’Nbrownibi(t)• Forward= xác suất các phầntử trên và bao gồm 1 nút cụthể nào đóNfox• Backward= xác suất cácphần tử dưới 1 nút cụ thểnào đóBackwardProbability =bi(t)=P(wtT |Xt=i)a_dog saw a_cat with a_telescopePl = 1×.7×.4×.3×.7×1×.5×1×1×.2 = .00588Pr = 1×.7×.6×.3×.3×1×.5×1×1×.2 = .00378¾ Pl is chosenai(t)XtN’The1718Xác suất trong và ngoàiXác suất trong và ngoàiN1= StartαNjw1wp-1N1= StartOutside αj(p,q)Inside βj(p,q)βwp wq wq+1Outside αj(p,q)αNjwmw1wp-1Inside βj(p,q)βwp wq wq+1Npq = ký hiệu không kết thúc Nj trải từ vị trí p đến q trongxâuαj(p,q)=P(w1(p-1) , Npqj,w(q+1)m|G)zαj = xác suất ngoài (outside)βj(p,q)=P(wpq|Npqj, G)zβj = xác suất trong (inside)zNj phủ các từ wp … wq, nếu Nj ⇒∗ wp … wqz19αj(p,q) βj(p,q) = P(N1⇒∗ w1m , Nj ⇒∗ wpq | G)= P(N1⇒∗ w1m |G)• P(Nj ⇒∗ wpq | N1⇒∗ w1m, G)Tính xác suất của xâuSử dụng thuật toán Inside, 1 thuật toán lập trình động dựatrên xác suất insideP(w1m|G) = P(N1 ⇒* w1m|G) = P(w1m|N1m1, G) = β1(1,m)zTí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ênNjTrường hợp cơ bản:βj(k,k) = P(wk|Nkkj, G)=P(Nj → wk|G)Suy diễn:βj(p,q) = Σr,sΣd∈(p,q-1) P(Nj → NrNs) βr(p,d) βs(d+1,q)P(Nj → NrNs)NsNrwpwdwd+1βr(p,d) xwqβs(d+1,q)-nhân 3 thành phần, tínhtổng theo j, r,s.21S → NP VPVP → V NP PPVP → V NPNP → NNP → N PP ...