ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
——————————

Hà Mỹ Linh

PHÂN TÍCH CÚ PHÁP PHỤ THUỘC
TIẾNG VIỆT

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
——————————

Hà Mỹ Linh

PHÂN TÍCH CÚ PHÁP PHỤ THUỘC
TIẾNG VIỆT

Chuyên ngành: Cơ sở toán cho tin học
Mã số: 60460110

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Lê Hồng Phương

Hà Nội - 2015

Lời cảm ơn
Em xin gửi lời cảm ơn tới các thầy giáo, cơ giáo, cán bộ khoa Tốn - Cơ Tin học, trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội đã tận
tình dạy dỗ và giúp đỡ em trong suốt thời gian học cao học và làm việc tại Bộ
mơn Tin học.
Trong q trình thực hiện luận văn này cũng như trong suốt những năm học
vừa qua, em đã nhận được sự chỉ bảo và hướng dẫn nhiệt tình của TS. Lê Hồng
Phương và TS. Nguyễn Thị Minh Huyền. Em xin gửi tới Thầy Cô lời cảm ơn
chân thành nhất.
Em cũng xin gửi lời cảm ơn tới gia đình, bạn bè đã động viên, khuyến khích
và tạo điều kiện cho em trong q trình học tập và thực hiện luận văn này.
Mặc dù đã cố gắng để hoàn thành luận văn, nhưng do hạn chế về kinh nghiệm
và thời gian, nên luận văn không thể tránh khỏi những thiếu sót. Em mong nhận
được sự cảm thơng và những ý kiến đóng góp của các thầy cô và các bạn.
Hà Nội, tháng 9 năm 2015
Học viên

Hà Mỹ Linh

i


Mục lục
Danh sách bảng

iv

Danh sách hình vẽ


v

Lời mở đầu

1

1 Tổng quan về cú pháp phụ thuộc

3

1.1

1.2

Cú pháp phụ thuộc . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1

Định nghĩa cú pháp phụ thuộc . . . . . . . . . . . . . . .

3

1.1.2

Biểu diễn cú pháp phụ thuộc

. . . . . . . . . . . . . . .


5

Các thuật tốn phân tích cú pháp phụ thuộc . . . . . . . . . . .

7

1.2.1

Phân tích cú pháp phụ thuộc dựa trên đồ thị . . . . . .

9

1.2.2

Phân tích cú pháp phụ thuộc dựa trên các bước chuyển .

11

2 Xây dựng tập nhãn phụ thuộc cho tiếng Việt

16

2.1

Kho ngữ liệu tiếng Việt - Viettreebank . . . . . . . . . . . . . .

16

2.2


Tập nhãn quan hệ phụ thuộc đa ngôn ngữ . . . . . . . . . . . .

19

2.3

Tập nhãn quan hệ phụ thuộc cho tiếng Việt . . . . . . . . . . .

23

3 Thực nghiệm
3.1

3.2

33

Các công cụ phân tích cú pháp phụ thuộc . . . . . . . . . . . .

33

3.1.1

MSTParser . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.1.2

MaltParser . . . . . . . . . . . . . . . . . . . . . . . . .


35

Thuật toán xây dựng tài nguyên tiếng Việt tự động . . . . . . .

39

3.2.1

40

Tập luật tìm phần tử trung tâm . . . . . . . . . . . . . .

ii


3.2.2
3.3

Thuật toán chuyển tự động từ Viettreebank sang cú pháp
phụ thuộc . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . .

45

Kết luận


48

Các cơng trình cơng bố liên quan đến luận văn

49

Tài liệu tham khảo

50

Phụ lục

54

iii


Danh sách bảng
1.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). . . . . . . . . . . . .

8

1.2

Các đặc trưng dùng trong MSTParser . . . . . . . . . . . . . . .

10


1.3

Các đặc trưng dùng trong MaltParser . . . . . . . . . . . . . . .

14

1.4

Ví dụ về phân tích cú pháp dựa vào các bước chuyển. . . . . . .

15

2.1

Tập nhãn từ loại tiếng Việt. . . . . . . . . . . . . . . . . . . . .

18

2.2

Tập nhãn cụm từ tiếng Việt. . . . . . . . . . . . . . . . . . . . .

19

2.3

Tập nhãn mệnh đề tiếng Việt. . . . . . . . . . . . . . . . . . . .

19


2.4

Tập nhãn chức năng cú pháp tiếng Việt. . . . . . . . . . . . . .

20

2.5

So sánh tập nhãn phụ thuộc tiếng Việt với tập nhãn phụ thuộc
đa ngôn ngữ (UD) và tập nhãn phụ thuộc tiếng Anh (SD). . . .

32

3.1

Kết quả của MSTParser. . . . . . . . . . . . . . . . . . . . . . .

35

3.2

Kết quả của MaltParser. . . . . . . . . . . . . . . . . . . . . . .

39

3.3

Tập quy tắc xác định phần tử trung tâm. . . . . . . . . . . . . .


40

3.4

Câu tiếng Việt theo định dạng CoNLL-X chưa được phân tích. .

45

3.5

Câu tiếng Việt theo định dạng CoNLL-X đã được phân tích phụ
thuộc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.6

Kết quả phân tích cú pháp phụ thuộc với tập dữ liệu 2700 . . .

46

3.7

Kết quả phân tích cú pháp phụ thuộc với tập dữ liệu 6546 câu .

47

iv



Danh sách hình vẽ
1.1

Cấu trúc cụm từ. . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Đồ thị phụ thuộc của một câu tiếng Anh. . . . . . . . . . . . . .

6

1.3

Ví dụ về phân tích cú pháp dựa trên đồ thị. . . . . . . . . . . .

11

3.1

Cú pháp thành phần của một câu tiếng Việt . . . . . . . . . . .

41

v


Lời mở đầu
Xử lí ngơn ngữ tự nhiên (Natural Language Processing - NLP) là một nhánh

trong trí tuệ nhân tạo, tập trung các ứng dụng nhằm giúp các hệ thống máy
tính hiểu và xử lí được ngơn ngữ của con người. Xử lí ngơn ngữ tự nhiên là một
trong những vấn đề khó và thu hút rất nhiều nhóm nghiên cứu vì nó liên quan
đến việc phải hiểu ý nghĩa ngơn ngữ - là cơng cụ hồn hảo nhất của tư duy và
giao tiếp. Phân tích cú pháp là một trong những vấn đề quan trọng trong lĩnh
vực xử lí ngơn ngữ tự nhiên. Với một bộ phân tích cú pháp tốt, chúng ta có thể
tích hợp vào nhiều ứng dụng trong xử lí ngơn ngữ tự nhiên như dịch máy, tóm
tắt văn bản, các hệ thống hỏi đáp, trích chọn thơng tin,... để tăng tính chính
xác của các ứng dụng đó.
Trong phân tích cú pháp, phân tích cú pháp phụ thuộc nghiên cứu về sự phụ
thuộc giữa các từ trong câu dựa trên ngữ nghĩa. Gần đây, phân tích cú pháp
phụ thuộc thu hút được sự quan tâm của nhiều nhóm nghiên cứu ngơn ngữ tự
nhiên trên thế giới bởi quan hệ phụ thuộc giữa hai từ trong câu nghiên cứu
khử nhập nhằng ngữ nghĩa của câu và cú pháp này có khả năng mơ hình hóa
các ngơn ngữ có trật tự từ tự do. Đối với nhiều ngơn ngữ như tiếng Anh, tiếng
Pháp, tiếng Trung,... đã có rất nhiều nghiên cứu và các cơng cụ phân tích cú
pháp phụ thuộc với hiệu quả cao. Tuy nhiên, các tiếp cận cho bài toán này hầu
hết dựa trên học máy và địi hỏi kho ngữ liệu với nhiều thơng tin về từ loại và
quan hệ phụ thuộc nên có rất ít công bố nghiên cứu về phân tích cú pháp phụ
thuộc tiếng Việt.
Hiện nay, các cơng cụ phân tích cú pháp phụ thuộc cho tiếng Việt đã đạt
được một số kết quả nhất định. Nhóm tác giả Nguyễn Lê Minh và cộng sự [1]
sử dụng thuật tốn phân tích cú pháp dựa vào đồ thị, thực nghiệm với công cụ
1


MSTParser và bộ dữ liệu khá hạn chế gồm 450 câu làm bằng tay với độ chính
xác là 63.11%. Nhóm tác giả Lê Hồng Phương và cộng sự [20] nghiên cứu phân
tích cú pháp phụ thuộc dựa vào văn phạm kết nối cây từ vựng hóa, thực nghiệm
huấn luyện với 8637 câu trong kho ngữ liệu cú pháp thành phần tiếng Việt, phân

tích 441 câu có độ dài nhỏ hơn 30 từ và đạt độ chính xác là 73.21%. Gần đây
nhất là cơng bố của nhóm nghiên cứu của tác giả Nguyễn Quốc Đạt và cộng sự
[7], tác giả đã chuyển tự động kho ngữ liệu cú pháp thành phần sang kho ngữ
liệu cú pháp phụ thuộc, cùng với tập 33 nhãn quan hệ phụ thuộc với độ chính
xác là 71.66%. Tuy nhiên, hầu hết các nghiên cứu đối với tiếng Việt đều chưa
thống nhất được tập nhãn phụ thuộc, các nhãn phụ thuộc chưa được mô tả một
cách rõ ràng và hiệu quả phân tích cịn khá hạn chế.
Luận văn sẽ trình bày về vấn đề phân tích cú pháp phụ thuộc, tập trung vào
việc xây dựng tập nhãn phụ thuộc cho tiếng Việt và thử nghiệm trên hai cơng
cụ phân tích cú pháp là MaltParser và MSTParser. Nội dung chính của luận
văn gồm có 3 chương:
• Chương 1. Tổng quan: Chương này trình bày những vấn đề liên quan tới
cú pháp phụ thuộc, các khái niệm cơ bản về phân tích cú pháp phụ thuộc.
Và một số những thuật tốn phân tích cú pháp phụ thuộc tốt nhất hiện
nay.
• Chương 2. Xây dựng tập nhãn phụ thuộc cho tiếng Việt: Chương
này trình bày về việc nghiên cứu và xây dựng tập nhãn phụ thuộc cho tiếng
Việt có đối sánh với tập nhãn phụ thuộc đa ngôn ngữ của nhóm nghiên cứu
trường Đại học Stanford. Ngồi ra, Chương này cũng so sánh sự khác nhau
giữa hai bộ nhãn để thấy được những đặc trưng trong tiếng Việt.
• Chương 3: Thực nghiệm: Chương này trình bày về một số cơng cụ phân
tích cú pháp phụ thuộc hiệu quả nhất hiện nay: MSTParser và MaltParser.
Tiếp theo là thuật toán chuyển tự động từ kho ngữ liệu cú pháp thành phần
Viettreebank sang kho ngữ liệu cú pháp phụ thuộc. Tiến hành thực nghiệm
phân tích cú pháp phụ thuộc cho tiếng Việt với hai cơng cụ trên, sau đó
so sánh kết quả đạt được giữa những tập dữ liệu khác nhau và đưa ra kết
luận.
2



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 tốn
phân tích cú pháp phụ thuộc điển hình.

1.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 tốn.
1.1.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



phần và phân tích cú pháp phụ thuộc.
Định nghĩa 1.1.1 (Cú pháp thành phần). 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ừ. Ví dụ: Hình
1.1.

Hình 1.1: Cấu trúc cụm từ.

Định nghĩa 1.1.2 (Cú pháp phụ thuộc). 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ì ln dùng cú pháp phụ thuộc và ngược lại.
Bài tốn phân tích cú pháp phụ thuộc
4


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 tố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 tố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
q trình huấn luyện trong các thuật tốn).
• Đầu ra: Đồ thị phụ thuộc của câu x.
1.1.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 , ..., wn ).
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ừ.
Định nghĩa 1.1.3 (Đồ thị phụ thuộc). 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. V = Zn+1 .
2. E ⊆ V × V.
3. R là một hàm xác định nhãn cung.

5


Tập đỉnh V là một tập Zn+1 = {0, 1, 2, ..., n}, n ∈ Z + , là tập số ngun 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 , ..., wn ). Thỏa mãn: |V + | = n và
|V | = n + 1.
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 submitted by Senator Brownback, Republican of Kansas" trong Hình 1.2.

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


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.
Định nghĩa 1.1.4 (Đồ thị phụ thuộc xây dựng đúng). 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 ).
2. G liên thông yếu (CONNECTEDNESS ).
3. 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 = i và k → j (SINGLE-HEAD).

4. Các đồ thị G là khơng có chu trình, tức là có i → j thì j →∗ i (ACYCLICITY ).
Ngồ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 tố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.

1.2

Các thuật tố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



• 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.
Bảng 1.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ữ
Arabic
Bulgarian
Chinese
Czech
Danish
Dutch
German
Japanese
Portuguese
Slovene

Spanish
Swedish
Turkish

Graph-based
(McDonald cùng cộng sự)
66.91%
87.57%
85.90%
80.18%
84.79%
79.19%
87.34%
90.71%
86.82%
73.44%
82.25%
82.55%
63.19%

Transition-based
(Nivre cùng cộng sự)
66.71%
87.41%
86.92%
78.42%
84.77%
78.59%
85.82%
91.65%

87.60%
70.30%
81.29%
84.58%
65.68%

Số câu
tập huấn luyện
1500
14400
57000
72700
5200
13300
39200
17000
9100
1500
3300
11000
5000

Số nhãn
phụ thuộc
27
18
82
78
52
26

46
7
55
25
21
56
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


trên, phân tích cú pháp phụ thuộc cịn được phát triển dựa vào một phương
pháp mới, được tác giả Danqi Chen và Christopher D. Manning xây dựng và
thử nghiệm vào năm vào năm 2014. Phương pháp này mang lại hiệu quả khá
cao (92.00%) khi thử nghiệm với Penntreebank [6]. Kết quả của phương pháp
này đối với tiếng Anh tốt hơn 2% so với phân tích cú pháp phụ thuộc dựa vào
bước chuyển và khoảng 0.2% với thuật tốn phân tích cú pháp phụ thuộc dựa
vào đồ thị. Tuy nhiên, luận văn tập trung trình bày hai phương pháp dựa trên
đồ thị và dựa trên các bước chuyển, thực nghiệm với hai công cụ tương ứng với
hai phương pháp này và đưa ra so sánh, nhận xét trong Chương 3.
1.2.1

Phân tích cú pháp phụ thuộc dựa trên đồ thị

Cho một câu đầu vào x = w0 , w1 , ..., wn có tập đỉnh là Vx , ta định nghĩa lại
tập cung Ex của đồ thị phụ thuộc cho câu x như sau:
Ex = {(i, j, r)|i, j ∈ Vx và r ∈ L}
Gx là những đồ thị phụ thuộc đúng của câu x. D(Gx ) là những đồ thị con
của Gx . Vì Gx chứa tất cả những cung được gán nhãn, tập D(Gx ) phải chứa tất

cả những đồ thị phụ thuộc của x.
Giả sử đã tồn tại một hàm tính trọng số của cạnh phụ thuộc, s : V ×V ×L −→
R. Định nghĩa trọng số của một đồ thị là tổng các trọng số của cạnh trong đồ
thị đó:
s(Gx = (Vx , Ex )) =

(i,j,r)∈Ex

s(i, j, r).

Trọng số của một cạnh, s(i, j, r) biểu diễn khả năng tạo ra quan hệ phụ thuộc
r giữa từ trung tâm wi với từ phụ thuộc wj trong đồ thị phụ thuộc. Trọng số
của cạnh được định nghĩa là tích của véc-tơ đặc trưng f với véc-tơ tham số w:
s(i, j, r) = w.f (i, j, r).
Các đặc trưng đại diện f (i, j) được trình bày trong Bảng 1.2 cho một cung
không được gán nhãn (i, j). Những đặc trưng này đại diện cho các thông tin liên
quan đến từ trung tâm trong quan hệ phụ thuộc, nhãn phụ thuộc. Ngồi ra cịn
có cả những đặc trưng về nhãn từ loại của các từ kế tiếp (bao gồm cả nhãn thô
và nhãn mịn). Cụ thể với một cung (i, j), ta có:
• Nhóm đặc trưng (a) và (b): xét cho từ loại và từ vựng của cung (i, j) trong
9


Bảng 1.2: Các đặc trưng dùng trong MSTParser
(a) Đặc trưng Uni-gram

(b) Đặc trưng Bi-gram

(c) Đặc trưng từ loại


xi − word, xi − pos

xi − word, xi − pos, xj − pos, xj − word

xi − pos, xb − pos, xj − pos

xi − word

xi − pos, xj − pos, xj − word

xi − pos, xi+1 − pos, xj−1 − pos, xj − pos

xi − pos

xi − word, xj − pos, xj − word

xi−1 − pos, xi − pos, xj−1 − pos, xj − pos

xj − word, xj − pos

xi − word, xi − pos, xj − pos

xi − pos, xi+1 − pos, xj − pos, xj+1 − pos

xj − word

xi − word, xi − pos, xj − word

xi−1 − pos, xi − pos, xj − pos, xj+1 − pos


xj − pos

xi − word, xj − word

xi−1 − pos, xi − pos, xj − pos, xj+1 − pos

xi − pos, xj − pos

ngữ cảnh Uni-gram và Bi-gram.
• Nếu từ i hay j có nhiều hơn 5 kí tự thì xét thêm đặc trưng 5-gram phía
trước từ đó.
• Nhóm (c): bổ sung cho bối cảnh đồ thị phụ thuộc (nhóm (a) và (b)), ta xét
các từ trong bối cảnh câu, cụ thể là thông qua từ loại của các từ nằm giữa
từ i và j, cùng với từ loại của các từ nằm bên trái và bên phải từ i và từ j.
Các tác giả đã thử thêm bớt hoặc thay đổi nhiều lần các đặc trưng và chứng
minh bằng thực nghiệm rằng các đặc trưng này là hiệu quả nhất đối với phân
tích cú pháp phụ thuộc cho tiếng Anh.
Véc-tơ w là một véc-tơ trọng số được đưa ra cho mỗi câu bằng phương pháp
học máy (MIRA - Margin Infused Relaxed Algorithm) [13]. Phương pháp học
máy MIRA được lựa chọn vì nó có nhiều những đặc tính phù hợp với bài tốn
phân tích cú pháp phụ thuộc.
Khi hàm trọng số của cạnh đã có, thì việc phân tích cú pháp có thể được biểu
diễn:
G∗ = argmaxG∈D(Gx ) s(G) = argmaxG∈D(Gx )

(i,j,r)∈Ex

s(i, j, r).

McDonald cùng cộng sự (2005) chỉ ra vấn đề này là tương đương với việc tìm

ra cây bao trùm cực đại có hướng của đồ thị Gx ban đầu.
Thuật tốn Chu-Liu-Edmonds được sử dụng để tìm ra cây bao trùm lớn nhất
trong đồ thị có hướng với trường hợp khơng xạ ảnh. Thuật tốn Eisner cũng
được sử dụng để tìm ra cây bao trùm lớn nhất trong đồ thị có hướng với trường
hợp xạ ảnh.
10


Một ví dụ của đồ thị đầy đủ Gx và đồ thị phụ thuộc có hàm trọng số cao
nhất được đưa ra trong Hình 1.3 cho câu “John saw Mary”. Hình 1.3 gồm đồ
thị đầy đủ Gx chứa trọng số trên các cạnh, sau đó dựa vào thuật tốn phân tích
cú pháp phụ thuộc trên đồ thị để chuyển thành đồ thị phụ thuộc chính xác của
câu.

Hình 1.3: Ví dụ về phân tích cú pháp dựa trên đồ thị.

1.2.2

Phân tích cú pháp phụ thuộc dựa trên các bước chuyển

Thuật toán Shift - Reduce (phân tích cú pháp phụ thuộc dựa vào các bước
chuyển) là một thuật toán cơ bản và có hiệu quả cao với rất nhiều các ngơn ngữ
khác nhau. Thuật tốn này phân tích câu đầu vào từ bên trái sang bên phải sử
dụng hai cấu trúc dữ liệu chính: một vùng đệm lưu trữ những dữ liệu đầu vào
còn lại và một ngăn xếp lưu trữ những dữ liệu đã xử lý một phần. Giống như
hầu hết các thuật tốn sử dụng cho phân tích cú pháp phụ thuộc trong thực tế,
thuật toán này thường sử dụng với đồ thị phụ thuộc xạ ảnh. Chúng ta bắt đầu
bằng cách xác định một cấu hình phân tích cú pháp cho một câu x = (w1 , ..., wn )
liên quan tới tập L các loại phụ thuộc (bao gồm cả một kí hiệu đặc biệt r0 là
nhãn phụ thuộc của gốc). Một trong những thuật toán dựa vào bước chuyển tốt

nhất hiện nay là thuật toán arc-eager được phát triển bởi Nivre.J và cộng sự
(2003).
Thuật tốn được mơ tả như sau:
Trong một hệ thống arc-eager, cho tập L = (r0 , ..., rm ) là tập nhãn phụ thuộc
và một câu x = (w0 , ...., wn ), một cấu hình phân tích cú pháp phụ thuộc là một
11


bộ ba: c = {σ, β, A}. Trong đó, c chứa một ngăn xếp σ, một vùng đệm β và một
tập các cung phụ thuộc A.
Cấu hình ban đầu của một câu s = w1 , w2 , ..., wn là:
• σ = ROOT
• β = [w1 , w2 , ..., wn ]
• A=∅
Một cấu hình c là cấu hình kết nếu như vùng đệm rỗng và ngăn xếp chứa duy
nhất một phần tử ROOT. Sử dụng kí hiệu v|β để chỉ ra rằng phần từ đầu tiên
của vùng đệm là từ v, kí hiệu σ|u để chỉ ra rằng phần từ trên cùng của ngăn
xếp là từ u, và Ac = (x, y), trong đó x, y là các từ của câu cần được phân tích
để chỉ ra tập cung phụ thuộc của một cấu hình c.
Thuật tốn phân tích cú pháp phụ thuộc arc-eager định nghĩa bốn loại hàm
chuyển như sau:
1. LEFT-ARC(r):
(σ|u, v|β, A) → (σ, v|β, A ∪ (v, u)) với điều kiện k : (k, u) ∈ A.
2. RIGHT-ARC(r):
(σ|u, v|β, A) → (σ|u|v, β, A ∪ (u, v)) với điều kiện k : (k, v) ∈ A.
3. REDUCE:
(σ|u, β, A) → (σ, β, A) với điều kiện ∃v : (v, u) ∈ A.
4. SHIFT:
(σ, v|β, A) → (σ|v, β, A).
Bốn hàm chuyển trên có thể được giải thích một cách rõ ràng như sau:

• Bước chuyển LEF T − ARC(r) : u ← v là nếu khơng tồn tại bất kì cung
nào đi đến u hay nói cách khác u khơng phải là phụ thuộc của bất cứ từ
nào thì phân tích của u sẽ được thực hiện, có một cung đi từ v đến u với
nhãn r. Khi đó u sẽ được lấy ra khỏi ngăn xếp .

12


• Bước chuyển RIGHT − ARC(r) : u → v là nếu khơng tồn tại bất kì cung
nào đến v thì v được đưa vào trong ngăn xếp để xét các từ tiếp theo. Chú
ý rằng có thể có nhiều cung đi ra từ u.
• Bước chuyển REDU CE: Là bước lấy một từ u ra khỏi ngăn xếp nếu như có
một quan hệ phụ thuộc giữa từ u và từ v trong bước chuyển RIGHT −ARC
trước đó.
• Bước chuyển SHIF T : Là bước lấy phần tử đầu tiên của vùng đệm và đẩy
nó vào trong ngăn xếp. Quá trình chuyển này khơng địi hỏi bất cứ điều
kiện tiên quyết nào.
Hệ thống bước chuyển được xác định là không đơn định, vì thế thường có
nhiều hơn một bước chuyển đối với một cấu hình nhất định. Để thực hiện phân
tích cú pháp đơn định, hệ thống các bước chuyển cần phải bổ sung một kĩ thuật
để dự đoán bước chuyển tiếp theo ở mỗi lựa chọn không đơn định, cũng như lựa
chọn một loại phụ thuộc r cho quá trình chuyển đổi LEFT-ARC(r) và RIGHTARC(r). Nếu trạng thái phân tích cú pháp chưa phải là trạng thái kết, thì hệ
thống sẽ tiếp tục thực hiện các trạng thái tiếp theo, nếu ngăn xếp rỗng thì sẽ
thực hiện bước chuyển SHIFT, ngược lại sẽ thực hiện một hàm chức năng để
đưa ra bước chuyển kế tiếp, hàm này được dự đoán bằng các thuật toán huấn
luyện dựa vào các đặc trưng của mơ hình. Khi thực hiện đến cấu hình kết, thì
ta thu được đồ thị phụ thuộc của câu đầu vào. Đồ thị phụ thuộc được đưa ra
cuối cùng đảm bảo khơng có chu trình và khơng xạ ảnh.
Các mơ hình đặc trưng cho phân tích cú pháp phụ thuộc dựa vào bước chuyển
thường kết hợp các đặc trưng từ loại, từ vựng với các đặc trưng phụ thuộc như

nhãn phụ thuộc hay từ trung tâm trong quan hệ phụ thuộc của các từ trong
ngăn xếp hay trong bộ đệm. Mơ hình đặc trưng chuẩn là mơ hình kết hợp các
đặc trưng từ loại, từ vựng và loại phụ thuộc, theo Bảng 1.3.
Mơ hình này chứa 6 đặc trưng từ loại, là từ loại của hai từ trên cùng của ngăn
xếp là (p(σ0 ), p(σ1 )) và 4 từ đầu tiên của đầu vào là p(τ0 ), p(τ1 ), p(τ2 ), p(τ3 ). Các
đặc tính loại phụ thuộc bao gồm từ trên đầu của ngăn xếp d(σ0 ), và con trái
nhất, con phải nhất của nó là (d(r(σ0 ), d(l(σ0 ))) và con trái nhất của từ tiếp
13


Bảng 1.3: Các đặc trưng dùng trong MaltParser
p(σ1 )

w(h(σ0 ))

d(l(σ0 ))

p(σ0 )

w(σ0 )

d(σ0 )

p(τ0 )

w(τ0 )

d(r(σ0 ))

p(τ1 )


w(τ1 )

d(l(τ0 ))

p(τ2 )
p(τ3 )

theo của đầu vào là d(l(τ0 )). Cuối cùng, mơ hình chuẩn chứa 4 đặc tính từ vựng,
là dạng từ của từ đầu tiên trong ngăn xếp w(σ0 ), đầu của từ đầu tiên trong
ngăn xếp w(h(σ0 )), và hai từ tiếp theo ở đầu vào là (w(τ0 ), w(τ1 )).
Khi dùng các đặc trưng này, các từ trong câu thường được mã hóa và biểu
diễn bằng một véc-tơ nóng (one-hot vector ) hay cũng được gọi là véc-tơ chỉ số
với các giá trị trong véc-tơ là 0 hoặc 1. Đây là cách biểu diễn này khá đơn giản
và dễ hiểu, được áp dụng trong rất nhiều những hệ thống của xử lý ngôn ngữ
tự nhiên. Tuy nhiên, biểu diễn theo dạng này gặp phải hai vấn đề lớn. Một là,
dữ liệu thưa, các thông số tương ứng với các từ hiếm hoặc các từ không xác
định thường được ước tính kém. Hai là, nó khơng có khả năng nắm bắt sự giống
nhau về ngữ nghĩa giữa các từ có liên quan chặt chẽ đến nhau. Sự hạn chế này
đã thúc đẩy các phương pháp giám sát để tạo ra một biểu diễn từ tốt hơn. Gần
đây, biểu diễn phân tán từ được chứng minh là đã đạt được nhiều kết quả tốt
trong các bài tốn xử lý ngơn ngữ tự nhiên. Biểu diễn phân tán (hay còn được
gọi là nhúng từ - Word embedding) có thể được sử dụng cho các đơn vị khác
nhau của ngôn ngữ như từ, cụm từ, câu và các tài liệu. Sử dụng biểu diễn phân
tán, các đơn vị ngôn ngữ được nhúng trong một khơng gian ít chiều và liên tục.
Mỗi chiều của biểu diễn phân tán đại diện cho một tính năng tiềm ẩn của từ
và hi vọng có thể nắm bắt được các đặc tính về cú pháp và tương đồng ngữ
nghĩa [23]. Thông thường, các biểu diễn phân tán từ thường được tạo ra bằng
cách sử dụng mơ hình mạng nơ-ron, trong đó các mạng nơ-ron được sử dụng để
dự đốn. Một số những mơ hình đã được phát triển để tạo ra biểu diễn phân

tán từ như: mô hình skip-gram và mơ hình bag-of-word [24]. Phương pháp này
đã và đang được sử dụng trong nhiều vấn đề liên quan đến phân tích cú pháp
phụ thuộc. Nó được chứng minh rằng đã đạt được hiệu quả cao và có thể áp
14


dụng cho nhiều ngộn ngữ khác nhau. Ngoài ra, biểu diễn phân tán cịn được sử
dụng để phân tích cú pháp phụ thuộc đa ngôn ngữ [8]. Phương pháp này cũng
đã được nhóm tác giả Lê Hồng Phương và cộng sự sử dụng và đem lại kết quả
khá khả quan đối với tiếng Việt [14].
Dựa vào các đặc trưng, vấn đề huấn luyện được chuyển thành vấn đề phân
loại, trong đó đầu vào là các véc-tơ đặc trưng và các lớp đầu ra là những quyết
định trong phân tích cú pháp. Huấn luyện mơ hình phân tích cú pháp phụ thuộc
là bước quan trọng để có một kết quả tốt. Việc phân lớp từ dữ liệu đã được gán
nhãn sử dụng bài toán phân lớp dựa vào một số thư viện có sẵn như LIBSVM
(Support Vector Machine), TiMBL (K - láng giềng gần nhất) và LibLinear.
Ví dụ phân tích cú pháp phụ thuộc dựa vào các bước chuyển đối với câu: "He
had good control." [6] trong Bảng 1.4.
Bảng 1.4: Ví dụ về phân tích cú pháp dựa vào các bước chuyển.
Trasition
SHIFT
SHIFT
LEFT-ARC(nsubj)
SHIFT
SHIFT
LEFT-ARC(amod)
RIGHT-ARC(dobj)
...
RIGHT-ARC(root)


Stack
[ROOT]
[ROOT He]
[ROOT He has]
[ROOT has]
[ROOT has good]
[ROOT has good control]
[ROOT has control]
[ROOT has]
...
[ROOT]

Buffer
[He has good control .]
[has good control .]
[good control .]
[good control .]
[control .]
[.]
[.]
[.]
...
[]

A
∅

A ∪ nsubj(has, He)

A ∪ amod(control, good)

A ∪ dobj(has, control)
...
A ∪ root(ROOT, has)

Như vậy, trong Chương 1, luận văn đã trình bày những kiến thức tổng quát
liên quan đến phân tích cú pháp phụ thuộc, các thuật tốn để giải quyết bài
tốn phân tích cú pháp phụ thuộc. Tiếp theo trong Chương 2, luận văn sẽ trình
bày về các tập nhãn quan hệ phụ thuộc và cách xây dựng tập nhãn quan hệ phụ
thuộc đối với tiếng Việt.

15


Chương 2

Xây dựng tập nhãn phụ thuộc cho
tiếng Việt
Muốn phân tích cú pháp phụ thuộc có độ chính xác cao, chúng ta phải đề
cập đến hai vấn đề chính: tài ngun cho phân tích cú pháp phụ thuộc và cơng
cụ phân tích cú pháp phụ thuộc. Tài nguyên cú pháp phụ thuộc chính là dữ liệu
huấn luyện, dữ liệu để kiểm tra tính chính xác và dữ liệu đầu vào của cơng cụ
phân tích cú pháp. Tiếng Việt có những đặc trưng riêng, vì thế việc chuẩn bị tài
nguyên phân tích cú pháp phụ thuộc tiếng Việt là giai đoạn quan trọng. Việc
chuẩn bị dữ liệu đầu vào còn phụ thuộc vào nhiều yếu tố như kho ngữ liệu tiếng
Việt hiện có là gì, tập nhãn quan hệ phụ thuộc như thế nào, công cụ chuyển tự
động ra sao? Chương này sẽ trình bày về tập nhãn quan hệ phụ thuộc đa ngơn
ngữ (Universal Dependency) của nhóm nghiên cứu trường Đại học Standford
và cách xây dựng nhãn quan hệ phụ thuộc cho tiếng Việt dựa vào kho ngữ liệu
VietTreebank và bộ nhãn chuẩn trên. Sau đó đưa ra sự so sánh giữa hai tập
nhãn để thấy được những đặc trưng của tiếng Việt.


2.1

Kho ngữ liệu tiếng Việt - Viettreebank

Kiến thức trong phần này trình bày theo tài liệu của tác giả Nguyễn Phương
Thái cùng cộng sự [3].
Trong các phương pháp giải các bài tốn cơ bản của phân tích ngơn ngữ thì

16


phương pháp thống kê trên một tập dữ liệu mẫu được các nhà nghiên cứu đặc
biệt quan tâm hơn cả. Các phương pháp thống kê trong phân tích cú pháp sẽ
cho kết quả ổn định và độ chính xác cao nếu có tập dữ liệu mẫu đủ lớn. Tập
dữ liệu mẫu này chính là kho ngữ liệu. Kho ngữ liệu mà trong đó mỗi câu được
chú giải cấu trúc cú pháp là nguồn tài nguyên rất hữu ích trong lĩnh vực xử lý
ngôn ngữ tự nhiên. Kho ngữ liệu này được gọi là treebank. Treebank có nhiều
ứng dụng quan trọng như đánh giá, kiểm định các cơng cụ xử lí ngơn ngữ tự
động, các phần mềm dịch máy, tóm tắt văn bản, các hệ thống hỏi đáp,... Các hệ
thống treebank cho các thứ tiếng được nghiên cứu nhiều như Anh, Pháp, Trung
quốc,... đã được xây dựng từ lâu.
Đối với tiếng Việt, việc xây dựng treebank cũng đã có một số kết quả nhất
định. Với tiếng Việt, treebank được nghiên cứu xây dựng trong khn khổ đề
tài VLSP và có tên là Vietreebank. Mục tiêu của Vietreebank là xây dựng được
lược đồ giải thích cú pháp với hơn 10000 câu.
Tập nhãn của Vietreebank được thiết kế gồm có:
• Tập nhãn từ loại: Về ngun tắc, các thơng tin về từ có thể được chứa trong
nhãn từ loại bao gồm: từ loại cơ sở (danh từ, động từ,... ), thơng tin hình
thái (số ít, số nhiều, thì, ngơi,... ), thơng tin về phân loại con (ví dụ động

từ đi với danh từ, động từ đi với mệnh đề,... ), thông tin ngữ nghĩa, hay
một số thông tin cú pháp khác. Với đặc điểm của tiếng Việt, tập nhãn từ
loại chỉ chứa thông tin về từ loại cơ sở mà không bao gồm các thơng tin
như hình thái, phân loại con,...
Tiếng Việt có hệ thống từ loại được đưa ra trong Bảng 2.1.
• Tập nhãn các thành phần cú pháp: Tập nhãn này chứa các nhãn mô tả các
thành phần cú pháp cơ bản là cụm từ và mệnh đề. Nhãn thành phần cú
pháp là thông tin cơ bản nhất trên cây cú pháp, nó tạo thành xương sống
của cây cú pháp.
Các nhãn cụm từ của tiếng Việt được đưa ra trong Bảng 2.2.
Các nhãn mệnh đề của tiếng Việt được đưa ra trong Bảng 2.3.
17


Bảng 2.1: Tập nhãn từ loại tiếng Việt.
STT

Tên

Chú thích

1

N

Danh từ

2

Np


Danh từ riêng

3

Nc

Danh từ chỉ loại

4

Nu

Danh từ đơn vị

5

V

Động từ

6

A

Tính từ

7

P


Đại từ

8

L

Định từ

9

M

Số từ

10

R

Phụ từ

11

E

Giới từ

12

C


Liên từ

13

I

Thán từ

14

T

Trợ từ, tiểu từ, từ tình thái

15

U

Từ đơn lẻ

16

Y

Từ viết tắt

17

X


Các từ khơng phân loại được

• Tập nhãn chức năng ngữ pháp: Nhãn chức năng của một thành phần cú
pháp cho biết vai trò của nó trong thành phần cú pháp mức cao hơn. Nhãn
chức năng cú pháp được gán cho các thành phần chính trong câu như chủ
ngữ, vị ngữ, tân ngữ. Nhờ thơng tin do nhãn chức năng cung cấp ta có thể
xác định các loại quan hệ ngữ pháp cơ bản sau đây:
– Chủ-vị
– Đề-thuyết
– Phần chêm
– Bổ ngữ
– Phụ ngữ
– Sự kết hợp
Các nhãn chức năng cú pháp của tiếng Việt được đưa ra trong Bảng 2.4.

18