Chương 1 Tổng quan về cú pháp phụ thuộc Chương này sẽ trình bày các kiến thức cơ sở sử dụng trong các phần sau, đặc biệt là khái niệm liên quan tới phân tích cú pháp phụ thuộc và các thuật toán phân tích cú pháp phụ thuộc điển hình.1 Cú pháp phụ thuộc Cú pháp là chủ đề nghiên cứu của hai cộng đồng gồm những người làm ngôn ngữ và những người làm tin học. Cú pháp vừa là đối tượng nghiên cứu, vừa là một trong các cấp độ cần mô tả đối với cộng đồng những người làm ngôn ngữ. Đối với cộng đồng những người làm tin học, cần làm cho máy tính phân tích được cú pháp với hai mục tiêu là xây dựng các ứng dụng, giải quyết một số bài toán thực tế, đối tượng nghiên cứu của họ là các hệ hình thức và các thuật toán.1 Định nghĩa cú pháp phụ thuộc Kiến thức và ví dụ trong phần này trình bày theo tài liệu của các tác giả Joakim Nivre và Johan Hall cùng cộng sự [9]. Cú pháp là quy tắc dùng các tiếng để đặt câu văn cho chính xác.
Để sử dụng ngôn ngữ linh hoạt, ta phải hiểu rõ về cú pháp. Muốn hiểu rõ về cú pháp, ta phải hiểu thế nào là câu, các loại câu, mệnh đề, các loại mệnh đề, cùng cấu trúc của chúng. Với một câu có thể có hai cách phân tích cú pháp: phân tích cú pháp thành 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com phần và phân tích cú pháp phụ thuộc. Cú pháp thành phần là cấu trúc câu theo thứ bậc các thành phần của câu, sử dụng cấu trúc cụm từ.1: Cấu trúc cụm từ.
Cú pháp phụ thuộc là cấu trúc biểu diễn quan hệ giữa các từ trong câu dựa trên ngữ nghĩa. Quan hệ phụ thuộc giữa hai từ vựng là quan hệ nhị phân không đối xứng. Các quan hệ phụ thuộc này được đặt tên để làm rõ quan hệ giữa hai từ trong câu. Chúng ta cũng có thể định nghĩa một cách hình thức như sau: cú pháp phụ thuộc của một câu cho trước là một đồ thị có hướng với gốc root là một đỉnh giả, thường được chèn vào phía bên trái câu, các đỉnh còn lại là các từ của câu.
Cấu trúc phụ thuộc được xác định bởi mối quan hệ giữa một từ trung tâm (head ) và từ phụ thuộc (dependent) của nó. Theo quy ước phổ biến trong các tài liệu về cú pháp phụ thuộc thì từ nằm ở gốc của mũi tên là từ trung tâm, từ nằm ở đầu mũi tên là từ phụ thuộc. Cấu trúc phụ thuộc thường đơn giản hơn cấu trúc thành phần, dễ dàng hơn cho cả người và máy khi học một cấu trúc cú pháp. Hơn nữa, cấu trúc phụ thuộc thích hợp hơn với các ngôn ngữ có trật tự từ tự do, như tiếng Séc hay Thổ Nhĩ Kì.
Tuy nhiên, không phải vì thế mà các ngôn ngữ có trật tự từ tự do thì luôn dùng cú pháp phụ thuộc và ngược lại. Bài toán phân tích cú pháp phụ thuộc 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phân tích cú pháp phụ thuộc đưa ra mô tả về quan hệ và vai trò ngữ pháp của các từ trong câu, đồng thời đưa ra hình thái của câu. Bài toán phân tích cú pháp phụ thuộc là tìm đồ thị phụ thuộc cho một câu. Đầu vào của bài toán là câu đã được tách từ và gán nhãn từ loại, trong đó mỗi từ có đặc điểm hình thái xác định.
Mục tiêu của bài toán là tìm ra phương pháp sinh đồ thị phụ thuộc chính xác nhất cho một câu đầu vào, nghĩa là làm cực đại số cung chính xác trong đồ thị và số nhãn gán đúng cho các cung. Ta có: • Đầu vào: – Câu x = w1 , w2 , ., wn đã được tiền xử lý, tách từ và gán nhãn từ loại. – Kho ngữ liệu gồm các câu đã được gán nhãn phụ thuộc (phục vụ cho quá trình huấn luyện trong các thuật toán). • Đầu ra: Đồ thị phụ thuộc của câu x.2 Biểu diễn cú pháp phụ thuộc Cho một câu x gồm n từ w1 , w2 , ., wn , khi đó ta sẽ kí hiệu x như sau: x = (w1 , w2 ,.
Trong phân tích cú pháp phụ thuộc, cú pháp phụ thuộc của một câu được biểu diễn bởi một đồ thị có hướng, các đỉnh trong đồ thị tương ứng với các từ của một câu, các cung trong đồ thị được gán nhãn, các nhãn của cung tương ứng với loại phụ thuộc giữa hai từ. Cho một tập L = {r1 , ., r|L| } các loại phụ thuộc (các nhãn cung), đồ thị phụ thuộc của một câu x = (w1 , ., wn ) là một đồ thị có hướng được gán nhãn G = (V, E, R), trong đó: 1. R là một hàm xác định nhãn cung. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Tập đỉnh V là một tập Zn+1 = {0, 1, 2, ., n}, n ∈ Z + , là tập số nguyên không âm tăng dần tới n.
Điều này có nghĩa là tất cả các từ trong câu là một đỉnh (1 ≤ i ≤ n) và có một đỉnh đặc biệt 0, không tương ứng với bất kỳ từ nào của câu và luôn là gốc của đồ thị phụ thuộc. Sử dụng V + là tập tất cả các đỉnh tương ứng với các từ của câu cụ thể x = (w1 ,. Tập hợp các cung E là một cặp (i, j), trong đó i, j là các đỉnh, kí hiệu i → j có nghĩa là một cung nối giữa đỉnh i và đỉnh j, khi đó ta có: (i, j) ∈ E. Kí hiệu i →∗ j khi và chỉ khi i = j hoặc có một cung nối từ đỉnh i đến đỉnh j.
Hàm R chỉ một loại phụ thuộc r ∈ L tới mỗi cung e ∈ E. Kí hiệu i →r j có nghĩa là có một cung có nhãn r kết nối đỉnh i với đỉnh j (ví dụ i → j và R((i, j)) = r). Từ w0 là từ được thêm vào ngay đầu của câu và không bổ nghĩa cho bất cứ từ nào trong câu, đó chính là đỉnh gốc của đồ thị. Mỗi wi biểu diễn cho một từ, một dấu câu, một phụ tố, tiền tố hoặc bất cứ hình vị nào trong câu.
Quy ước 0 (tương ứng với từ w0 ) luôn là gốc của đồ thị phụ thuộc của câu cần phân tích. Ví dụ: Đồ thị phụ thuộc của câu "Bills on ports and immigration were sub- mitted by Senator Brownback, Republican of Kansas" trong Hình 1.2: Đồ thị phụ thuộc của một câu tiếng Anh. Trong ví dụ trên, tập L = {nsubjpass, auxpass, prep, pobj, nn, cc, conj, appos} 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com là các quan hệ phụ thuộc của các từ trong câu, và cũng là các nhãn cung của đồ thị phụ thuộc. Các từ ở gốc mũi tên là các từ trung tâm, các từ ở đầu mũi tên là các từ phụ thuộc.
Với một cung: “submitted −→ Bills”, thì “submitted” là từ trung tâm, “Bills” là từ phụ thuộc và quan hệ phụ thuộc giữa hai từ này được biểu thị bằng nhãn phụ thuộc nsubjpass. Một đồ thị phụ thuộc G xây dựng đúng nếu và chỉ nếu: 1. Đỉnh 0 là gốc (ROOT ). G liên thông yếu (CONNECTEDNESS ).
Mọi đỉnh đều có nhiều nhất một từ trung tâm, tức là nếu i → j thì với một từ bất kì khác trong câu, @ k thỏa mãn k 6= i và k → j (SINGLE-HEAD). Các đồ thị G là không có chu trình, tức là có i → j thì @j →∗ i (ACYCLIC- ITY ). Ngoài các tính chất trên của một đồ thị phụ thuộc, hầu hết các đồ thị còn thỏa mãn điều kiện xạ ảnh. Các đồ thị là xạ ảnh, nếu như có i → j thì i →∗ k, ∀k thỏa mãn i ≤ k ≤ j hoặc j ≤ k ≤ i (PROJECTIVITY ).
Tuy nhiên, không phải tất cả các câu đều thỏa mãn điều kiện này nên một số thuật toán được phát triển để giải quyết vấn đề không xạ ảnh trong phân tích cú pháp phụ thuộc. Nhờ cách mô hình hóa như trên, cú pháp phụ thuộc biểu diễn được những ngôn ngữ có trật tự từ tự do, đây là điều mà cú pháp cấu trúc cụm (vốn phù hợp với những ngôn ngữ có nhiều quy tắc chặt chẽ trong cấu thành câu) không làm được. Tuy vậy, không có nghĩa là phân tích ngôn ngữ có trật tự từ xác định thì chỉ dùng cấu trúc cụm hay phân tích ngôn ngữ có trật tự từ tự do thì chỉ dùng cấu trúc phụ thuộc.2 Các thuật toán phân tích cú pháp phụ thuộc Kiến thức trong phần này trình bày theo tài liệu của các tác giả Joakim Nivre và Johan Hall cùng cộng sự [9], Ryan McDonald cùng cộng sự [21], [22]. Có hai phương pháp phân tích cú pháp phụ thuộc cơ bản sau: 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com • Phân tích cú pháp phụ thuộc dựa vào đồ thị: phân tích cú pháp phụ thuộc thông qua tham số hóa mô hình phụ thuộc dựa vào các đồ thị con và huấn luyện các tham số trên toàn bộ các đồ thị.
Sử dụng suy luận toàn cục trong hệ thống để tìm những đồ thị có trọng số cao nhất trong số các cách thiết lập tất cả các đồ thị. Mô hình phân tích cú pháp phụ thuộc dựa trên đồ thị được Eisner (1996), McDonald cùng cộng sự (2005) phát triển. • Phân tích cú pháp phụ thuộc dựa vào bước chuyển: phân tích cú pháp phụ thuộc thông qua các bước chuyển từ trạng thái phân tích này tới trạng thái phân tích khác. Các tham số trong mô hình thường được huấn luyện sử dụng kĩ thuật phân lớp chuẩn để dự đoán bước chuyển tiếp theo từ một tập hợp các bước chuyển trước đó.
Sử dụng suy luận cục bộ, hệ thống bắt đầu từ một trạng thái ban đầu cố định và xây dựng các đồ thị bằng hàm điểm chuyển đổi cao nhất tại mỗi trạng thái cho đến khi một điều kiện được đáp ứng. Mô hình phân tích cú pháp phụ thuộc dựa trên các bước chuyển được Nivre cùng cộng sự (2004), Yamada và cộng sự (2003) phát triển. Cả hai phương pháp đều đưa ra kết quả phân tích với độ chính xác tương đương nhau, như đưa ra trong Bảng 1.1 một số ngôn ngữ khác nhau.1: Kết quả phân tích cú pháp phụ thuộc của hai mô hình cho hệ thống CoNLL-X (Buchholz và Marsi 2006). Ngôn ngữ Graph-based Transition-based Số câu Số nhãn (McDonald cùng cộng sự) (Nivre cùng cộng sự) tập huấn luyện phụ thuộc Arabic 66.68% 5000 25 Ngoài hai phương pháp khá phổ biến và đạt hiệu quả cao với nhiều ngôn ngữ 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.