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

Nguyễn Việt Hùng

NGHIÊN CỨU XÁC ĐỊNH ĐỒNG SỞ CHỈ
VÀ ỨNG DỤNG CHO 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

Trong quá trình học tập và nghiên cứu, em đã nhận được sự hướng dẫn tận
tình của thầy Lê Hồng Phương và cô Nguyễn Thị Minh Huyền. Em xin chân
thành cảm ơn thầy, cô đã giúp đỡ em rất nhiều trong học tập cũng như trong
công việc.
Em xin gửi lời cảm ơn tới các thầy, cô giáo đã nhiệt tình giảng dạy các chuyên
đề Cao học cho chúng em.
Em cũng xin được cảm ơn gia đình, bạn bè, đồng nghiệp, những người luôn
quan tâm, động viên em trong quá trình học tập và làm luận văn.
Hà Nội, ngày 29 tháng 11 năm 2015
Học viên


Cách giải quyết bài toán xác định đồng sở chỉ . . . . . . . . . .

7

1.2.1

Xác định các đề cập . . . . . . . . . . . . . . . . . . . .

7

1.2.2

Xác định quan hệ đồng sở chỉ . . . . . . . . . . . . . . .

8

Phương pháp xác định đồng sở chỉ . . . . . . . . . . . . . . . .

11

1.3.1

Phương pháp phân loại . . . . . . . . . . . . . . . . . . .

11

1.3.2

Phương pháp phân cụm . . . . . . . . . . . . . . . . . .


22

2.1

Kiến trúc hệ thống . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.2

Một số quá trình xử lý của hệ thống . . . . . . . . . . . . . . .

25

2.2.1

Xác định các đề cập . . . . . . . . . . . . . . . . . . . .

25

2.2.2

Xử lý các cụm đơn . . . . . . . . . . . . . . . . . . . . .

26

2.2.3

Đầu vào và đầu ra của mỗi bước sàng . . . . . . . . . . .

27

2.3.1

Xác định người nói . . . . . . . . . . . . . . . . . . . . .

28

2.3.2

So khớp chuỗi chặt . . . . . . . . . . . . . . . . . . . . .

29

2.3.3

So khớp chuỗi nới lỏng . . . . . . . . . . . . . . . . . . .

29

2.3.4

Một số trường hợp chính xác cao . . . . . . . . . . . . .

29

2.3.5

So khớp từ chính chặt . . . . . . . . . . . . . . . . . . .


2.4.1

Ngữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.4.2

Kết quả . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3 Ứng dụng cho tiếng Việt
3.1

3.2

3.3

33

Các công cụ đã có cho xử lý tiếng Việt . . . . . . . . . . . . . .

33

3.1.1

Công cụ tách từ, gán nhãn từ loại . . . . . . . . . . . . .

33


Xác định đặc trưng của các đề cập cho tiếng Việt . . . .

41

Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

3.3.1

Ngữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

3.3.2

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

42

Kết luận

43

Tài liệu tham khảo

45
iii



15

2.1

Các lượt sàng trong tiếng Anh . . . . . . . . . . . . . . . . . . .

28

2.2

Các bộ dữ liệu thử nghiệm . . . . . . . . . . . . . . . . . . . . .

32

2.3

Kết quả hệ thống hệ thống Stanford với một số bộ dữ liệu . . .

32

2.4

Kết quả hệ thống Stanford tại cuộc thi năm 2013 . . . . . . . .

32

3.1

Các lượt sàng áp dụng cho tiếng Việt . . . . . . . . . . . . . . .



Danh sách hình vẽ
1.1 Phân tích cú pháp thành phần của một câu trong tiếng Việt . . . . . .

7

2.1 Kiến trúc hệ thống xác định đồng sở chỉ của Stanford [17] . . . . . . .

23

3.1 Phân tích cú pháp câu "Tôi đã mua quyển sách mà thầy giáo giới thiệu." 37
3.2 Phân tích cú pháp câu "Quyển sách rất hay." . . . . . . . . . . . . . . 38
3.3 Phân tích cú pháp câu "Hà Nội, thủ đô của Việt Nam, đang bị ô nhiễm." 39
3.4 Phân tích cú pháp câu "Hà Nội là thủ đô của Việt Nam." . . . . . . . 40
3.5 Câu tiếng Anh được gán nhãn vai nghĩa.

vi

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

54


Giới thiệu

Trong ngôn ngữ học, thuật ngữ đồng sở chỉ được dùng để nói về quan hệ giữa
các cụm từ cùng chỉ tới một thực thể. Xác định đồng sở chỉ là quá trình tìm các
cụm từ trong văn bản cùng tham chiếu tới một thực thể.
Xác định đồng sở chỉ là một vấn đề cơ bản trong ngôn ngữ tự nhiên. Đây là

Theo mô hình thứ nhất, bài toán này được đưa về bài toán phân lớp. Còn
theo mô hình thứ hai, ta có một bài toán phân cụm. Một số hệ thống có thể sử
dụng cả hai mô hình trên. Tiêu biểu là hệ thống xác định đồng sở chỉ với kiến
trúc sàng nhiều lượt của nhóm xử lý ngôn ngữ trường Đại học Stanford cho kết
quả tốt với tiếng Anh và đã được áp dụng cho các ngôn ngữ khác với kết quả
khả quan [17].
Với tiếng Việt, các nghiên cứu về đồng sở chỉ chưa nhiều, và chỉ tập trung vào
một số bài toán riêng như xác định các thực thể định danh [23] [15] [22] [20],
xác định hồi chỉ của một số đại từ đặc biệt. Do vậy, mục tiêu của luận văn là
nghiên cứu xây dựng một hệ thống xác định đồng sở chỉ trong văn bản tiếng
Việt.
Yêu cầu đầu tiên cho mọi hệ thống xác định đồng sở chỉ là xác định đặc trưng
cho xác đề cập (hoặc cụm đề cập). Trong luận văn này, bộ đặc trưng của tiếng
Anh được sử dụng làm cơ sở để xây dựng bộ đặc trưng cho tiếng Việt với một
số thay đổi cho phù hợp với đặc điểm ngôn ngữ.
Quá trình xác định các đặc trưng của đề cập (hoặc cặp đề cập) cần rất nhiều
thông tin, càng nhiều thông tin được xác định, kết quả xác định đồng sở chỉ
sẽ càng chính xác. Trong tiếng Anh, đã có rất nhiều các công cụ hỗ trợ để xác
định các đặc trưng này. Với tiếng Việt, có rất nhiều hạn chế về các công cụ xử
lý ngôn ngữ cơ bản: chưa có WordNet cho tiếng Việt, cũng chưa có các công
cụ có độ chính xác cao được chia sẻ để thực hiện các công việc như xác định
2


các thực thể định danh (NER), chưa có các từ điển thống nhất để xác định các
thông tin hình thái như giống đực/cái, chỉ người/chỉ vật,... Một công việc cần
thiết để xác định đồng sở chỉ cho tiếng Việt là cần xây dựng bộ các công cụ để
hỗ trợ xác định các quan hệ và đặc trưng của các đề cập.
Trong quá trình ứng dụng cho tiếng Việt, thực nghiệm được tiến hành trên
kho ngữ liệu Viettreebank [16] thuộc đề tài VLSP 1 gồm 10000 câu đã được phân

nhưng đã rút gọn lại chứ không nhắc lại nguyên vẹn cả chuỗi. Trong ví dụ (2),
đại từ [Hắn] được dùng để nhắc lại về [Người đàn ông mặc đồ đen].
Hiện tượng các cụm từ trong văn bản cùng chỉ tới một thực thể (sự vật, sự
việc, ...) được gọi là đồng sở chỉ. Xác định đồng sở chỉ là một trong những bước
đầu tiên để phân tích và hiểu ngữ nghĩa văn bản. Chương này sẽ trình bày tổng
quan về bài toán xác định đồng sở chỉ cho văn bản.

4


1.1

Bài toán xác định đồng sở chỉ

Xác định đồng sở chỉ là quá trình tìm tất cả các cụm từ trong văn bản cùng
tham chiếu tới một thực thể. Một cụm từ trong văn bản tham chiếu tới một
thực thể gọi là một (sự) đề cập.
Ví dụ: Linh đến trường bằng xe buýt. Cô ấy thường đi chuyến xe số 22.
Trong đó,
• [Linh], [trường], [xe buýt], [cô ấy], [chuyến xe số 22] là các đề cập.
• [Linh] và [cô ấy] cùng chỉ đến thực thể là cô gái tên là Linh. Hay có thể nói,
[cô ấy] và [Linh] có quan hệ đồng sở chỉ.
[Linh], [trường], [xe buýt], [cô ấy], [chuyến xe số 22] là các đề cập trong ví dụ
trên và được phân thành các cụm:
• {[Linh], [cô ấy]}
• {[trường]}
• {[xe buýt]}
• {[chuyến xe số 22]}
Trong đa số các trường hợp, khi nói đến xác định đồng sở chỉ, kết quả được
quan tâm tới là các (nhiều) đề cập cùng tham chiếu tới một thực thể trong

Ví dụ:
Tổng thống Obama gặp Nelson Maldela. Cháu gái của người đàn ông già nua
ấy bị dính líu đến một tai nạn.
Ở đây, để xác định người đàn ông già nua tham chiếu đến Obama hay Nelson
Maldela có thể cần thêm cả tri thức về thế giới: Nelson Maldela lớn tuổi hơn
Obama và có độ tuổi phù hợp để được nhắc đến như là người đàn ông già nua
hơn Obama.
Ngoài ra, bài toán đồng sở chỉ không chỉ xuất hiện trong một văn bản mà
có thể có phạm vi trong nhiều văn bản. Ví dụ: Hai bài báo cùng nói về một sự
việc, sẽ có nhiều đề cập ở hai bài báo cùng tham chiếu tới một thực thể. Các đề
cập trong văn bản thông thường là cụm danh từ nhưng cũng có trường hợp là
cụm động từ, tính từ, ... Ví dụ: Anh ấy đi siêu thị. Anh ấy làm việc đó với các
bạn anh ấy. Trong ví dụ này, việc đó và đi siêu thị cùng trỏ đến việc đi siêu thị
trong thực tế.
6


Trong phạm vi của luận văn này, chúng tôi chỉ xét tới hiện tượng
đồng sở chỉ với đề cập là các cụm danh từ từ và trong phạm vi một
văn bản.

1.2

Cách giải quyết bài toán xác định đồng sở chỉ

Bài toán xác định đồng sở chỉ được giải quyết thông qua hai bước:
• Xác định các đề cập: các đề cập thường là các cụm danh từ.
• Xác định quan hệ đồng sở chỉ giữa các đề cập.
1.2.1


V-H

không

còn

N-H

N-H

đạn

bom

NP-DOB
N-H

A

người

nghèo

.
.

Hình 1.1: Phân tích cú pháp thành phần của một câu trong tiếng Việt

Tuy nhiên, trong một số trường hợp, không phải tất cả các cụm danh từ thu
được từ việc phân tích cú pháp đều có thể được coi là các đề cập.

trưng bao gồm vị trí, hình thái, từ vựng, cú pháp, ngữ nghĩa và thậm chí cả
thông tin thực tế [14]. Hầu hết các hệ thống hiện nay được xây dựng trên bộ
đặc trưng này với một vài thay đổi và bổ sung nhỏ. Bảng 1.2.2 chứa danh sách
các đặc trưng này.
8


Bảng 1.1: Các đặc trưng cơ bản của mô hình xác định đồng sở chỉ học máy
Đặc trưng
Đặc trưng vị trí
*Span
Distance
*Gender
*Number
Animacy
String matching
Alias
Minimum edit distance
Part-of-speech

Đặc trưng cú pháp
*Apposition
*Predicate nominal
construction
*Binding
*Contra-indices

Maximal NP projection
Parse tree similarity
Collocation Match

Sự tương đồng giữa các cây con bao phủ tiền đề và sự nhắc lại.
(Yang et al., 2006)
Hai cụm danh từ đứng trước hoặc theo sau bởi cùng một động từ.
Hai cụm danh từ có cùng một vai trò ngữ pháp.

Phân lớp theo NER bao gồm người, tổ chức, địa danh, phương
tiện và các thực thể địa lý - chính trị.
Hai cụm NP có cùng một lớp nghĩa trong WordNet.

9


Phân lớp các cặp đề cập

Để xác định các đề cập cùng chỉ đến một thực thể, có thể kiểm tra từng cặp
đề cập có quan hệ đồng sở chỉ hay không. Một đề cập sẽ được xét lần lượt với
các đề cập trước đó để tìm ra đề cập có quan hệ đồng sở chỉ. Một cặp đề cập
này còn được gọi là một liên kết.
Các phương pháp xác định đồng sở chỉ di theo hướng tiếp cận này sẽ tiến
hành phân lớp các cặp đề cập vào hai lớp: lớp các đề cập có quan hệ đồng sở
chỉ và lớp các đề cập không có quan hệ đồng sở chỉ. Sau khi phân lớp các cặp
này, kết quả xác định đồng sở chỉ được tổng kết lại từ các cặp đề cập có quan
hệ đồng sở chỉ.
Ví dụ: Với 4 đề cập A, B, C, D, E, F.
Sẽ có 10 cặp đề cập có thể gồm: (B, A), (C, A), (D, A), (E, A) (C, B), (D,
B), (E, B), (D, C), (E, C). (E, D).
Sau khi tiến hành xác định đồng sở chỉ, thu được kết quả các cặp có quan hệ
đồng sở chỉ là: (B, A), (D, A), (E, C).
Như vậy, kết quả của bài toán xác định đồng sở chỉ là:
• Lớp 1: A, B, D;

trên thuật toán ID3.
Nhiều hệ thống lựa chọn C4.5 bởi có thể lựa chọn xác đặc trưng hữu ích và
xây dựng các cây ngắn gọn.
Mô hình tuyến tính logarit

Nhược điểm của phương pháp cây quyết định là chỉ xét từng đặc trưng một
trong một lần, và có thể bỏ qua các tổ hợp đặc trưng hữu ích [10]. Bởi các đặc
trưng của bài toán xác định đồng sở chỉ có sự chồng lấn, mô hình tuyến tính
logarit trở thành một lựa chọn tự nhiên.
Khoảng cách dựa trên nhân

Năm 2006, Yang và cộng sự đưa ra các đặc trưng dựa trên cây cú pháp [24].
Sự khác biệt giữa hai cây cú pháp được tính bởi thuật toán so sánh cây, và giá
trị sai khác này được sử dụng như giá trị nhân của SVM. Sự tương đồng của
hai cây được định nghĩa dựa trên số lượng đã chuẩn hóa các cây con. Có ba loại
cây được trích xuất từ cây cú pháp là:
• Min-Expansion: chỉ chứa các nút xuất hiện trên đường đi ngắn nhất từ đại
từ đến một ứng viên (Một ứng viên là một đề cập có thể có quan hệ đồng
sở chỉ với đề cập đang xét).
• Simple-Expansion: chứa các nút con của các nút trong Min-Expansion.
• Full-Expansion: Chứa các nút bao phủ toàn bộ các từ thuộc cả đại từ và
các ứng viên trong Simple-Expansion.
11


Phương pháp ứng viên kép

Năm 2003, Yang và cộng sự chỉ ra một vấn đề của các mô hình đơn ứng viên,
đó là, các hệ phân loại xác định khả năng một ứng viên có quan hệ đồng sở chỉ
với một đề cập tại một thời điểm chứ không phải so sánh giữa hai ứng viên [25].



giữa một đề cập và một cụm. Thông tin môt tả về một cụm sẽ nhiều hơn thông
tin mô tả về một đề cập đơn.
Phân cụm kết tụ - Agglomerative Clustering

Năm 2007, Cullotta và cộng sự giới thiệu mô hình xác suất bậc một (firstorder probabilistic model) [2]. Mô hình tính xác suất của một tập hợp các đề
cập có quan hệ đồng sở chỉ sử dụng một mô hình tuyến tính logarit.
Các phương pháp khác

Năm 2004, McCallum và Wellner mô hình xác suất kết hợp các lớp phân
hoạch sử dụng một mô hình tuyến tính logarit [9].
Năm 2005, Daume và Marcu kết hợp quá trình xác định các thực thể và quá
trình xác định đồng sở chỉ thành một hệ thống và giải quyết hai vấn đề đồng
thời [3].
Năm 2005, Ng thử nghiệm phương pháp siêu phân cụm bằng cách so sánh 54
tổ hợp của ba thuật toán (C4.5, RIPPER và Maximum Entropy) [13].
Năm 2004, Luo và cộng sự, và Florian và cộng sự thử nghiệm giải bài toán
xác định đồng sở chỉ như một bào toán tìm kiếm. Khoảng cách tìm kiếm được
biểu diễn bằng cây Bell [7]. Xác định các cặp đồng sở chỉ tương đương với việc
tìm đường đi trong cây Bell.
1.3.3

Phương pháp lai

Các phương pháp xác định đồng sở chỉ dựa trên luật, cần có nhiều thông tin,
đặc biệt là các thông tin về tri thức bên ngoài và phụ thuộc nhiều vào đặc điểm
riêng của từng ngôn ngữ. Các phương pháp học máy cần có quá trình xây dựng
đặc trưng cho từng phần tử. Điều này là không dễ dàng và sẵn có với một số
ngôn ngữ (thiếu các công cụ ngôn ngữ cơ bản và không có WordNet). Trong đó,

Với tiếng Việt, chưa có bộ dữ liệu chuẩn được công bố. Hầu hết các nhóm chỉ
thực nghiệm trên dữ liệu riêng của mình.
1.4.2

Độ đo đánh giá

Các đơn giản nhất để đánh giá một hệ thống xác định đồng sở chỉ là đánh
giá thông qua các cặp đề cập là đồng sở chỉ.
right_searched 1
1
right_searched
, precision =
,
=
+
recall =
total_right
total_seached F 1
recall
1
precision
trong đó,
• total_right là số lương các cặp đề cập có quan hệ đồng sở chỉ theo đáp án.
14


Bộ dữ liệu
MUC-6 (1995)
MUC-7 (1998)
ACE-2002

Broadcast news
Newspaper
Newswire
EELD data
Broadcast news
Newswire
Other
Broadcast news
Broadcast conversations
Newswire
Weblog
Usenet
Conversational telephone speech
Broadcast news
Broadcast conversations
Newswire
Weblog
Usenet
Conversational telephone speech

Dữ liệu huấn luyện
12.4K
19K
60K
60K
60K
30K
65K
65K
15K

25K
N/A
25K
25K
N/A
10K
7.5K
10K
7.5K
7.5K
7.5K
10K
7.5K
10K
7.5K
7.5K
7.5K


• total_searched là số cặp đề cập có quan hệ đồng sở chỉ tìm được.
• right_searched là số cặp đề cập có quan hệ đồng sở chỉ tìm được là đúng
theo đáp án.
Ví dụ: Ta có danh sách các sự đề: m11 , m22 ,m13 , m34 , m25 .
Trong đó, chỉ số dưới là số thứ tự của các đề cập, chỉ số trên là chỉ số nhóm
(cụm) đúng của đề cập. Tức là:
• Nhóm 1: m1 , m3
• Nhóm 2: m2 , m5
• Nhóm 3: m4 .
Kết quả tìm được là:
• Nhóm 1: m1 , m3

• Các độ đo dựa trên liên kết
• Các độ đo dựa trên tập hợp
• Các độ đo dựa trên việc gióng hàng
Một số độ đo khác thường được sử dụng là [19]
• MUC
• B-Cubed
• ACE
• CEAF
• BLANC
• CoNLL
MUC

Độ bao phủ recall:
Giả sử:
• S là tập hợp các đề cập sinh ra bởi các khóa.
• R1 , R2 , ..., Rm là các lớp sinh ra bởi kết quả tìm được.
• p(S) là phân hoạch của S tương ứng với kết quả tìm được.
• c(S) là số lượng liên kết tối thiểu của các liên kết cần thiết để sinh ra S. Ta
có: c(S) = (|S| − 1)

17


• m(S) là số lượng các liên kết bị thiếu trong các kết quả tìm được so với
khóa. Ta có: m(S) = (|p(S)| − 1)
Khi đó, chỉ số bao phủ:
|S| − |p(S)|
c(S) − m(S)
=
recall =


N
i=1 wi

N
i=1 wi

∗ precisioni

∗ recall

với, wi là trọng số của đề cập thứ i trong văn bản. Thông thường, nếu không
nói thêm, wi = df rac1N
18