CHƯƠNG 1 TỔNG QUAN VỀ CÁC MÔ HÌNH VĂN PHẠM CHO NGÔN NGỮ TỰ NHIÊN Theo Jurafsky [70], quan hệ văn phạm là cách hình thức hóa những tư tưởng của văn phạm truyền thống như chủ ngữ hay bổ ngữ và những mối quan hệ khác. Nhiều mô hình văn phạm đã được đưa ra theo các hướng tiếp cận: cấu trúc (constituency), quan hệ văn phạm (grammar relation), phân loại con (subcategorization) hay phụ thuộc (dependency). Hai hướng tiếp cận phổ biến nhất hiện nay là cấu trúc và phụ thuộc. Chương này sẽ giới thiệu các mô hình văn phạm phổ biến và vị trí của văn phạm liên kết trong hệ thống các mô hình văn phạm đó.
Cách tiếp cận cấu trúc và văn phạm phi ngữ cảnh Vấn đề đầu tiên đặt ra khi mô tả các quy tắc cú pháp là biểu diễn được các quy luật để nhóm các từ lại thành câu. Nếu ngữ pháp tiếng Việt [28] quy định câu phải chứa một nòng cốt (đơn hoặc ghép), nòng cốt đơn phải chứa chủ ngữ, vị ngữ với chủ ngữ luôn đi trước vị ngữ, thì vấn đề mô tả quy tắc cú pháp sẽ chuyển thành vấn đề tạo lập các cấu trúc (constituent) và đưa ra các quy tắc về vị trí của các cấu trúc. Mô hình cho phép nghiên cứu việc tạo lập các cấu trúc một cách đệ quy chính là mô hình văn phạm phi ngữ cảnh. Mô hình hình thức này tương đương với dạng chuẩn BNF (Backus Naur Form) của ngôn ngữ lập trình.
Văn phạm phi ngữ cảnh biểu diễn ngôn ngữ tự nhiên Văn phạm phi ngữ cảnh bao gồm một tập các luật hay sản xuất, mỗi luật biểu diễn cách thức mà các ký hiệu của ngôn ngữ được nhóm lại rồi sắp theo thứ tự và một tập từ vựng bao gồm các từ và ký hiệu. Ví dụ: Một tập sản xuất của văn phạm phi ngữ cảnh tiếng Việt với ý nghĩa của các ký hiệu không kết thúc: S - câu, NP - danh ngữ, VP - động ngữ, N - danh từ, V - động từ, P - đại từ. S → NP VP NP → P NP → N P VP → V NP 20 Tập sản xuất này có thể mô tả cấu trúc cú pháp của câu “Tôi yêu mẹ tôi” với đại từ “tôi”, danh từ “mẹ” và động từ “yêu”. Một cách hình thức, có thể mô tả văn phạm phi ngữ cảnh như sau: Định nghĩa 1.
Σ: tập ký hiệu kết thúc (không giao với N). R: tập luật, hay tập sản xuất dạng A → β, A là ký hiệu không kết thúc, β là xâu gồm hữu hạn ký hiệu trên tập vô hạn (Σ ∪ N)* (tập tất cả các xâu trên bảng chữ Σ ∪ N). Trong mô hình văn phạm phi ngữ cảnh, bài toán phân tích cú pháp là bài toán tìm ra cây ngữ cấu cho câu đưa vào. Mỗi nút của cây ngữ cấu có nhãn là một ký hiệu không kết thúc biểu diễn một cấu trúc.
Theo [56], cây ngữ cấu thể hiện những thông tin sau về cú pháp: • Thứ tự tuyến tính của các từ trong câu. • Tên các phạm trù cú pháp của các từ và nhóm từ. • Cấu trúc phân cấp của các phạm trù cú pháp. Các bộ phân tích cú pháp theo mô hình văn phạm phi ngữ cảnh cổ điển chủ yếu theo hai phương pháp CYK (Cocke – Younger - Kasami) và Earley.
Đã có những bộ phân tích cú pháp tiếng Việt được xây dựng theo phương pháp CYK [12], Earley [5], [27] với những cải tiến thích hợp.1 là cây ngữ cấu cho câu “Tôi thích chân gà”. Cây ngữ cấu này nếu không tính nhãn của các nút lá, thì giống hệt cây ngữ cấu của câu “Tôi thích áo lụa”, tuy nhiên, nếu đem dịch sang tiếng Anh, hai câu này phải dịch khác hẳn nhau. Quan hệ giữa danh từ chỉ bộ phận cơ thể động vật và danh từ chỉ động vật là quan hệ sở hữu, do vậy “chân gà” phải hiểu là “chân của gà”, trong khi quan hệ giữa “áo” và “lụa” lại là quan hệ về mặt chất liệu “áo bằng lụa”. Mô hình phi ngữ cảnh chưa thể hiện được mối liên hệ này.
Cây ngữ cấu của câu “Tôi thích chân gà”. 21 Vấn đề nhập nhằng là một trong những vấn đề phức tạp nhất mà các bộ phân tích cú pháp phải giải quyết. Giả thiết ta chỉ xét câu đơn, tức là câu chỉ có một nòng cốt và bỏ qua vấn đề nhập nhằng từ loại. Vấn đề nhập nhằng cấu trúc xảy ra khi một câu có nhiều hơn một cây phân tích.2 là hai cây ngữ cấu khác nhau cho câu “Họ sẽ không chuyển hàng xuống thuyền vào ngày mai” (câu ví dụ trong [20]) với văn phạm phi ngữ cảnh S → NP VP NP → P VP → R VP | R R V N PP PP PP-TMP | VP PP | V NP PP PP → E NP PP-TMP →E NP Ý nghĩa của các ký hiệu: S - câu, NP - danh ngữ, VP- động ngữ, PP - giới ngữ, N - danh từ, V - động từ, P - đại từ, R - phụ từ, E - giới từ, PP-TMP - giới ngữ chỉ thời gian.
Hai cây ngữ cấu của câu “Họ sẽ không chuyển hàng xuống thuyền vào ngày mai”. 22 Một trong những cách tiếp cận đầu tiên để giải quyết vấn đề nhập nhằng khi phân tích cú pháp trên mô hình văn phạm phi ngữ cảnh là mô hình văn phạm phi ngữ cảnh xác suất (Probabilistic Context Free Grammar). Văn phạm phi ngữ cảnh xác suất Trong mô hình văn phạm phi ngữ cảnh xác suất, mỗi luật được gắn thêm một xác suất cho thấy luật đó có thường xuyên được sử dụng trong các cây ngữ cấu hay không. Σ: tập ký hiệu kết thúc (không giao với N).
R: tập luật, hay tập sản xuất dạng A → β | p |, trong đó A là ký hiệu không kết thúc, β là xâu gồm hữu hạn ký hiệu trên tập vô hạn (Σ ∪ N)*, p là số trong đoạn [0,1] biểu thị xác suất Pr ( β | A ). Xác suất của một cây ngữ cấu là tích các xác suất của n luật được sử dụng để mở rộng n nút trong của nó: Pr (T, S) = Pr (RHS |LHS ) ! LHSi và RHSi là vế trái và vế phải của sản xuất được dùng cho nút thứ i của cây ngữ cấu. Cây được chọn là cây có xác suất lớn nhất [41] Pr (T, S) "(S) = T argmax Pr (T | S) = argmax '(.S = yield(T) yêu cầu tính trên tất cả các cây ngữ cấu T có kết quả là câu S. Trong trường hợp lý tưởng, nếu có một treebank đủ lớn, có thể tính xác suất của mỗi luật theo công thức: Count(A → β) Count(A → β) Pr (β | A) = = ∑γ Count(A→γ) Count(A) Vấn đề là khi bắt đầu công việc, treebank chưa có hoặc chưa đủ lớn.
Do vậy cần chọn một bộ ngữ liệu, phân tích các câu của nó để bổ sung dần vào ngân hàng cây và tính ra các xác suất nói trên. Ta lại đối mặt với vấn đề khác, khi một câu có thể có nhiều phân tích: 23 phân tích nào sẽ được chọn? Việc giải quyết vấn đề nhập nhằng lại rơi vào tình thế “con gà và quả trứng”. Vấn đề nói trên được giải quyết bởi giải thuật trong - ngoài (Inside - Outside Algorithm) do Baker đề xuất năm 1979 cho văn phạm phi ngữ cảnh [81]. Đây thực chất là biến thể của giải thuật tiến - lùi của mô hình Markov ẩn (Hidden Markov Model - HMM).
Giải thuật cho phép tính xác suất trong và xác suất ngoài cho câu vào S theo cách đệ quy. Mô hình Markov ẩn được Manning và Schütze [87] giới thiệu, quan tâm đến dãy các quan sát O1,., Om sản sinh bởi các luật Ni → NjNk và Ni → wj. Trong đó Oi, i = 1, m thực chất là các ký hiệu kết thúc (từ) w1,., wm của xâu đưa vào. Theo mô hình HMM, ma trận tham số của văn phạm phi ngữ cảnh xác suất là α [i, j, k] và β [i, r] với: α [i, j, k] = Pr ( Ni → NjNk | G ) β [i, r] = Pr ( Ni→ r | G ) Để có thể xây dựng ma trận tham số như trên, văn phạm phi ngữ cảnh được giả thiết là ở dạng chuẩn Chomsky.
Điều này không làm giảm tính tổng quát của mô hình, vì theo [63], mọi văn phạm phi ngữ cảnh có thể chuyển về dạng chuẩn Chomsky. Ràng buộc sau là bắt buộc cho các tham số : ∑?,@ α 8i, j, k; + ∑> β 8i, r; = 1 với mọ i i Ràng buộc này (liên quan đến ký hiệu không kết thúc thứ i trong văn phạm) cho thấy mọi khả năng áp dụng sản xuất mà vế trái là ký hiệu không kết thúc thứ i chỉ có thể sinh ra hoặc hai ký hiệu không kết thúc hoặc một ký hiệu kết thúc (do văn phạm ở dạng chuẩn Chomsky). Dưới đây là quy ước về ký hiệu theo [87]: • Tập ký hiệu không kết thúc của văn phạm được ký hiệu là { N1,. Ký hiệu đầu là N1.
• Tập ký hiệu kết thúc của văn phạm là {w1,. • Câu được phân tích w1. • wpq là bộ phận của câu cần phân tích từ từ thứ p đến từ thứ q. NBC là ký hiệu không kết thúc Nj sinh ra dãy các từ ở vị trí từ p đến q trong câu.
? • • αj (p, q) là xác suất ngoài. • βj (p, q) là xác suất trong. 24 Xác suất trong βj (p, q) là xác suất để ký hiệu không kết thúc thứ j (Nj) sinh ra quan sát (dãy các từ) wp,. Một cách hình thức, βj ( p, q ) = Pr ( wpq | NBC , G ) ? Xác suất ngoài αj (p, q) là xác suất để xuất phát từ ký hiệu đầu N1 sinh ra ký hiệu không kết thúc NBC và các từ của xâu đưa vào nằm ngoài wp,.
Một cách hình thức, ta có : ? αj ( p, q ) = Pr ( w1(p-1), NBC , w(q+1)m | G ) ? Xác suất trong và xác suất ngoài là cơ sở để xây dựng giải thuật liên quan đến hai vấn đề chính trong phân tích cú pháp theo mô hình xác suất, đó là: 1. Đoán nhận (Recognition): Tính xác suất để ký hiệu đầu N1 sinh ra dãy quan sát O trong văn phạm G. Như vậy, với giải thuật trong (Inside Algorithm), xác suất để một câu có m từ w1. wm đúng (được sản sinh bởi văn phạm G) là: Pr ( w1m | G ) = Pr ( N1 ⇒ w1m | G ) = β 1 ( 1, m ) ∗ Xác suất nói trên là xác suất đúng của câu, tức là tổng xác suất của các phân tích.