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

Nội dung chính trong bài này tập trung các kiến thức về phân tích cú pháp trong xử lý ngôn ngữ tự nhiên như: Bài toán phân tích cú pháp, khái niệm về văn phạm, dạng chuẩn Chomsky, cấu trúc ngữ pháp, các ứng dụng của phân tích cú pháp,... 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 - Lê Thanh Hương Bài toán PTCP cây PTCP mẫu Phân tích cú pháp P Lê Thanh Hương Bộ môn Hệ thống Thông tin Viện CNTT &TT – Trường ĐHBKHN Email: huonglt-fit@mail.hut.edu.vn T tính C điể điểm câu P cây cú pháp Văn phạm độ chính xác Các bộ PTCP hiện nay có độ chính xác cao (Eisner, Collins, Charniak, etc.) 1 Khái niệm về văn phạm z z z Văn phạm Phân tích câu “Bò vàng gặm cỏ non” Cây cú pháp: Tập luật z z z z z 2 z z z C Æ CN VN CN Æ DN VN Æ ĐgN ĐgN Æ ĐgT DN DN Æ DT TT z z z z z Một văn phạm sản sinh là một hệ thống G = ( T, N, S, R ), trong đó T (terminal) – tập ký hiệu kết thúc N (non terminal) – tập ký hiệu không kết thúc S (start) – ký hiệu khởi đầu R (rule) – tập luật R = { α Æ β | α, β ∈ (T∪N) } α Æ β gọi là luật sản xuất 3 Nhắc lại về văn phạm Dạng chuẩn Chomsky z z Mọi NNPNC không chứa ε đều có thể sinh từ một văn phạm tnđó mọi sản xuất đều có dạng A Æ BC hoặc A Æ a, với A,B,C∈N và a ∈T Ví dụ: Tìm dạng chuẩn Chomsky cho văn phạm G với T = {a,b}, N ={S,A,B}, R như sau: z z z 4 S Æ bA|aB A ÆbAA|aS|a B Æ aBB|bS|b z z z z Văn phạm: 1 tập luật viết lại Ký hiệu kết thúc: các ký hiệu không thể phân rã được nữa. Ký hiệu không kết thúc: các ký hiệu có thể phân rã được. Xét văn ă phạm h G: G S → NP VP NP → John, garbage VP → laughed, walks G có thể sinh ra các câu sau: John laughed. John walks. Garbage laughed. Garbage walks. 5 6 Cấu trúc ngữ pháp Các ứng dụng của PTCP Cây cú pháp biểu diễn cấu trúc ngữ pháp của một câu. Bò vàng gặm cỏ non. ƒ Dịch máy (Alshawi 1996, Wu 1997, ...) C DT Bò CN VN DN ĐgN ĐgT gặm TT vàng tiếng Anh DN ƒ DT cỏ các thao tác với cây tiếng Việt Nhận dạng tiếng nói sử dụng PTCP (Chelba et al 1998) Put the file in the folder. Put the file and the folder. TT non 7 Văn phạm phi ngữ cảnh (Context-Free Grammar) Các ứng dụng của PTCP ƒ Kiểm tra ngữ pháp ƒ Trích rút thông tin (Hobbs 1996) … còn gọi là văn phạm cấu trúc đoạn z G = z T – tập các ký hiệu kết thúc (terminals) z N - tập các ký hiệu không kết thúc (non-terminals) z P – ký hiệu tiền kết thúc (preterminals), khi viết lại trở thành ký hiệu kết thúc, thúc P⊂ Nphạm cảm ngữ cảnh So với văn z S – ký hiệu bắt đầu R: αAγ ⇒ αβγ z R: X → γ , X là ký hiệu không kết thúc; γ là chuỗi các ký hiệu kết thúc và không kết thúc (có thể rỗng) z Văn phạm G sinh ra ngôn ngữ L z Bộ nhận dạng: trả về yes hoặc no z Bộ PTCP: trả về tập các cây cú pháp (Microsoft) CSDL Kho văn bản NY Times 8 câu truy vấn 9 z Văn phạm ngữ cấu: z z z z r = α→β, với α ∈ V+ , β ∈ V* , ⏐α⏐≤⏐β⏐ và α1Aα2→α1β’α2 với β’≠ε Văn phạm phi ngữ cảnh: z z z Văn phạm phi ngữ cảnh α→β, với α ∈ V+ , β ∈ V* Văn phạm cảm ngữ cảnh: z 10 A → θ, A ∈ N, với ới θ ∈ V*= V* ( T ∪ N )* Văn phạm chính qui: A → aB, A → Ba, z A → a, với A, B ∈ N, a ∈ T. z z VPCQ VPPNC VPCNC VPNC 11 12 Cấu trúc đoạn đệ qui Áp dụng tập luật ngữ pháp z S → NP VP → DT NNS VBD → The children slept p z S → NP VP → DT NNS VBD NP → DT NNS VBD DT NN → The children ate the cake 13 Văn phạm cho ngôn ngữ tự nhiên có nhập nhằng S PTCP kiểu trên xuống John saw snow on the campus S NP 0 John 14 z Nhập nhằng - PP có thể gắn tại 2 điểm (với VP hoặc với NP) z z VP ……. z z PP 3 on NP z VP Hướng đích Khởi đầu với 1 danh sách các ký hiệu cần triển khai (S, NP,VP,…) Viết lại các đích trong tập đích bằng cách: z 1 saw NP 2 snow NP tìm luật có vế trái trùng với đích cần triển khai triểu khai nó với vế phải luật, tìm cách khớp với câu đầu vào Nếu 1 đích có nhiều cách viết lại Æ chọn 1 luật để áp dụng (bài toán tìm kiếm) Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc tìm kiếm sâu (depth-first search) 4 the 5 campus 6 15 Khó khăn với PTCP trên xuống z Các luật đệ qui trái z PTCP trên xuống rất bất lợi khi có nhiều luật có cùng vế trái 16 PTCP dưới lên z S→NP X2 …… S→NP X600 VP ……. z S→NP X1 S NP z S→VP Y1 z z Nhiều thao tác thừa: triển khai tất cả các nút có thể phân tích trên xuống z z PTCP trên xuống sẽ làm việc tốt khi có chiến lược điều khiển ngữ pháp phù hợp z z PTCP trên xuống không thể triển khai các ký hiệu tiền kết thúc thành các ký hiệu kết thúc. Trên thực tế, người ta thường sử dụng phương pháp dưới lên để làm việc này. z Lặp lại công việc: bất cứ chỗ nào có cấu trúc giống nhau 17 Hướng dữ liệu Khởi tạo với xâu cần phân tích Nếu chuỗi trong tập đích phù hợp với vế phải của 1 luật → thay nó bằng vế trái của luật luật. Kết thúc khi tập đích = {S}. Nếu vế phải của các luật khớp với nhiều luật trong tập đích, cần lựa chọn luật áp dụng (bài toán tìm kiếm) Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc tìm kiếm sâu (depth-first search) 18 Thuật toán CKY (bộ nhận dạng) Khó khăn với PTCP dưới lên z z z Không hiệu quả khi có nhiều nhập nhằng mức từ vựng Lặp lại công việc: bất cứ khi nào có cấu trúc con chung Cả PTCP TD (LL) và BU (LR) đều có độ phức tạp là hàm mũ của độ dài câu. ƒ ƒ ƒ Vào: xâu n từ Ra: yes/no Cấu trúc ngữ g pháp: p p bảng g n x n ((chart table)) ƒ ƒ ƒ hàng đánh số 0 đến n-1 cột đánh số 1 đến n cell [i,j] liệt kê tất cả các nhãn cú pháp giữa i và j 19 Thuật toán CKY (bottom-up) ƒ ƒ 20 Ví dụ for i := 1 to n ƒ Thêm tất cả từ loại của từ thứ i vào ô [i-1,i] for width := 2 to n ƒ for start := 0 to n-width ƒ end := start + width ƒ for mid := start+1 to end-1 ƒ for mọi nhãn cú pháp X trong [start,mid] ƒ for mọi nhãn cú pháp Y trong [mid,end] ƒ for mọi cách kết hợp X và Y (nếu có) ƒ Thêm nhãn kết quả vào [start,end] nếu chưa Bò vàng gặm 2 3 1 0 DT 3. 4. 5. 6. 7. 8. 5 C TT 2 VN ĐgN ĐgT 3 DT DN 4 TT Văn phạm phi ngữ cảnh Start→ S S → NP VP NP → Det Noun NP → Name NP → Name PP PP → Prep NP VP → V NP VP → V NP PP 4 CN DN 21 2. non 1 có nhãn này 1. cỏ 9. 10. 11. 12. 13. 14. 15. 22 Luật kết hợp V → ate Name → John Name → ice-cream, snow Noun → ice-cream, pizza Noun → table, guy, campus Det → the Prep → on Ô Cell[i,j] chứa nhãn X ...