1 ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Dung

PHÁT HIỆN KẾ THỪA VĂN BẢN TIẾNG VIỆT
DỰA TRÊN HỌC MÁY SVM
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY
Ngành: Công nghệ Thông tin

HÀ NỘI – 2012
2

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Dung
Major: Information technology

Supervisor: Assoc. Prof. Ha Quang Thuy
Co-Supervisor: Masters. Pham Quang Nhat Minh
HA NOI – 2012
i

Lời cảm ơn

Lời đầu tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới PGS.TS Hà
Quang Thụy, Ths Phạm Quang Nhật Minh đã tận tình hướng dẫn và chỉ bảo tôi trong
suốt quá trình thực hiện khóa luận tốt nghiệp.
Tôi xin chân thành cảm ơn các thầy, cô trong trường đại học Công Nghệ - đại
học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi cho tôi học tập và nghiên cứu.
Tôi cũng xin gửi lời cảm ơn đến các thầy cô, các anh chị, các bạn trong phòng
thí nghiệm KT-Lab đã hỗ trợ tôi rất nhiều về kiến thức chuyên môn trong quá trình
thực hiện khóa luận. Tôi xin cảm ơn các bạn trong lớp K53CLC đã ủng hộ và khuyến
khích tôi trong suốt suốt quá trình học tập tại trường.
Cuối cùng, tôi xin được gửi cám ơn vô hạn tới gia đình và bạn bè, những người
đã luôn bên cạnh, giúp và động viên tôi trong quá trình học tập cũng như trong suốt
quá trình thực hiện khóa luận này.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 18 tháng 05 năm 2012
Sinh viên


RECOGNIZING VIETNAMESE TEXTUAL ENTAILMENT BASED ON SVM
Nguyen Thi Dung
QH-2008-I/CQ course, information technology faculty.
Abtract thesis:
Inference task relates the understanding and processing language in communication
which is an interesting task. Textual Inference plays an important role in Natural Language
Processing. Textual entailment derived from inference (entailment) in logic. Recognizing
Textual Entailment which focuses on detecting semantic inference has attracted a lot of
attention. The main idea behind RTE is concerned with inferring the meaning of the text from
that of another larger text.The concept of RTE explores the relationship between the text and
hypothesis, the text entails the hypothesis if the hypothesis can be inferred from the text.
Based on surveying and comparing some approaches proposed in the PASCAL RTE
challenge, the thesis focus on many Textual Entailment problems such as concept of Textual
Entailment, role of Textual Entailment and some approachs for RTE task. We then propose a
recognizing textual entailment model based on SVM model with lexical features and semantic
features. Our model is based Julio Javier Castillo’s model [10]. However, we use use many
SVM classifiers and combine them together when Julio Javier Castillo only used a SVM
classifier.
Thesis conduct experiments on system with Vietnamese RTE data which based on
English RTE data of the third PASCAL RTE challenge (RTE-3) by manually translating
RTE-3 development set and RTE3 test set to Vietnamese. There are four experiments with
cases: only use a SVM classifier, use many SVM classifiers and combine them together. Test
results are positive and they reveal that combining many classifiers can improve accuracy.

Keywords: RTE, SVM
iv

Lời cam đoan

Tôi xin cam đoan phương pháp phát hiện kế thừa văn bản tiếng Việt dựa trên

5
1.2. Phát biểu bài toán phát hiện kế thừa văn bản.
6
1.3. Bài toán phát hiện kế thừa văn bản trong hội nghị RTE.
6
1.4. Vai trò của phát hiện kế thừa văn bản.
8
1.5. Tóm tắt chương một.
9
Chương 2. Hướng tiếp cận học máy cho bài toán phát hiện kế thừa văn bản và
mô hình học máy SVM. 10
2.1. Giới thiệu chung về hướng tiếp cận sử dụng học máy
10
2.2.1. Các đặc trưng Intra-pair (In-pair features)
11
2.1.2. Các đặc trưng Cross-Pair
12
2.1.3. Các phương pháp học máy
13
2.2. Một số hệ thống phát hiện kế thừa văn bản có sử dụng học máy
13
2.2.1. Đối với văn bản là tiếng nước ngoài
13
2.2.2. Đối với văn bản là tiếng Việt
18
2.2.3. Nhận xét hướng tiếp cận học máy
19
2.3. Học máy SVM
19
2.4. Kết luận

37
Kết luận và định hướng nghiên cứu tiếp theo 38
Tài liệu tham khảo. 39

vii

Danh sách các bảng

Bảng 1: Một số ví dụ về RTE trong hội nghị RTE-3 5
Bảng 2: Các đặc trưng được sử dụng bởi phân lớp cây quyết định [5] 14
Bảng 3: Cấu hình phần cứng. 32
Bảng 4: Công cụ phần mềm. 32
Bảng 5: Ý nghĩa của các giá trị 34
Bảng 6: Giá trị độ đo của các tập dữ liệu khi sử dụng bộ phân lớp SVM
1
35
Bảng 7: Giá trị độ đo của các tập dữ liệu khi sử dụng bộ phân lớp SVM
2
35
Bảng 8: Giá trị độ đo của các tập dữ liệu khi sử dụng bộ phân lớp SVM
3
36
Bảng 9: Giá trị độ đo của các tập dữ liệu khi sử dụng ba bộ phân lớp SVM. 36

viii

Danh sách các hình vẽ.
Hình 1: Biểu đồ Venn của mối quan hệ kế thừa A→ B. 4
Hình 2: Cấu trúc hệ thống hỏi đáp. 8
Hình 3: Mô hình hệ thống phát hiện kế thừa văn bản tiếng Trung [14] 15


Một trong những vấn đề thường gặp trong xử lý ngôn ngữ tự nhiên là sự biến
thể biểu diễn của văn bản, trong đó nghĩa của một văn bản có thể được biểu diễn hoặc
có liên quan đến các văn bản khác. Vấn đề này thuộc vào vấn đề nhập nhằng trong
ngôn ngữ tự nhiên. Các ứng dụng trong xử lý ngôn ngữ tự nhiên như: hệ hỏi đáp
(Question Answering: QA), trích xuất thông tin (Information Extraction: IE), tóm tắt
văn bản (Summarization), và dịch máy (Machine Translation: MT) đòi hỏi một mô
hình phát hiện ra hiện tượng biến thể này nhằm tìm ra một ý nghĩa cụ thể nào đó có thể
được suy luận từ các biến thể khác nhau của văn bản. Bài toán phát hiện kế thừa văn
bản được hình thành để giải quyết vấn đề này: Cho hai đoạn văn bản, bài toán kế thừa
có mục đích xác định xem nghĩa của văn bản này có thể được suy luận (kế thừa) từ
một văn bản còn lại hay không.
Phát hiện kế thừa văn bản là một bài toán mới trong tiếng Việt. Tuy có những
phương pháp phát hiện kế thừa văn bản mang lại kết quả khả quan trong tiếng Anh
nhưng tính hiệu quả của chúng trong tiếng Việt còn cần được kiểm nghiệm. Vì thế, bài
toán phát hiện kế thừa văn bản đối với văn bản tiếng Việt hiện đang là một bài toán
khó.
Khóa luận giới thiệu khái quát về kế thừa văn bản và bài toán phát hiện kế thừa
văn bản trong các hội nghị RTE, đề nghị một mô hình phát hiện quan hệ kế thừa trong
văn bản tiếng Việt, cài đặt mô hình và tiến hành thực nghiệm kiểm định mô hình.
Khóa luận được chia thành bốn chương với các nội dung:
Chương 1: Giới thiệu khái quát về bài toán phát hiện kế thừa văn bản. Khóa
luận giới thiệu khái niệm kế thừa văn bản, phát biểu bài toán phát hiện kế thừa văn
bản, các ứng dụng thực tiễn và quá trình phát triển bài toán phát hiện kế thừa văn bản
trong các hội nghị RTE.
Chương 2: Trình bày hướng tiếp cận giải quyết bài toán phát hiện kế thừa văn
bản. Đầu tiên, khóa luận trình bày phương pháp phát hiện kế thừa văn bản dựa trên
việc sử dụng các mô hình học máy. Sau đó, khóa luận giới thiệu cụ thể một số hệ
thống phát hiện kế thừa văn bản có sử dụng học máy.Ở cuối chương, khóa luận trình
bày về mô hình học máy SVM.

• Biến đổi ngữ nghĩa:
o Italia trờ thành nhà vô địch thế giới lần thứ tư.
Trong câu đầu tiên, từ “Italia” được sử dụng thay cho “đội bóng Italia”. Trong
câu thứ hai thì biệt danh “Squadra Azzura” được sử dụng thay cho “Italia”. Trong câu
thứ ba, một loại suy luận ngữ nghĩa được sử dụng để suy luận rằng: nếu “X trở thành
một nhà vô địch” thì “X chiến thắng trong world cup”.
Vấn đề biến đổi ngôn ngữ được sử dụng rộng rãi trong nhiều khía cạnh của lĩnh
vực xử lý ngôn ngữ tự nhiên bao gồm: mở rộng truy vấn, phân tích ngữ nghĩa tiềm Nn
cho tìm kiếm thông tin; so khớp từ vựng, so khớp cú pháp và suy luận logic cho hệ
thống hỏi đáp; sử dụng độ trùng lặp n – gram cho hệ thống dịch máy; độ trùng lặp về
từ vựng, sự tương đồng về cú pháp, ngữ nghĩa cho kế thừa văn bản. Trong khóa luận
này, chúng tôi tập trung vào một bài toán con về biến đổi ngôn ngữ là bài toán phát
hiện quan hệ kế thừa văn bản.
Phát hiện kế thừa văn bản là bài toán mới trong lĩnh vực xử lý ngôn ngữ tự
nhiên và nhận được sự quan tâm rất lớn của các nhà nghiên cứu. Đặc biệt, từ năm 2005
tới nay, hội thảo RTE được tổ chức thường niên với mục đích là tổng hợp các phương
pháp phát hiện kế thừa văn bản cho kết quả tốt thông qua các cuộc thi và nhận được sự
quan tâm của nhiều nhóm nghiên cứu NLP trên thế giới. Hội thảo RTE được tiến hành
4

trong khuôn khổ các hội nghị thường niên Hiểu tài liệu (DUC: Document
Understanding Conference, 2001-2007) và Phân tích xử lý văn bản (TAC:Text
Analysis Conference, từ năm 2008 tới nay
1
).
1.1. Khái niệm kế thừa văn bản.
Hiện nay có khá nhiều cách tiếp cận về khái niệm kế thừa văn bản, tuy nhiên
chúng tôi sẽ trình bày khái niệm văn bản theo hướng tiếp cận của Kouylekov [12].
Đầu tiên tác giả giới thiệu về kế thừa trong logic, sau đó tác giả giới thiệu về kế thừa
trong văn bản.

, ….A
n
} và H = {B
1
, B
2
, …, B
n
} là các tập biểu thức
.
T → H nếu mọi mẫu A
1
, A
2
, ….A
n
thỏa mãn ít nhất một B
i
trong H (A
1
∧ . . . ∧ A
n
→
B
1
∨ . . . ∨ B
m
)
Hình 1 chỉ ra mối quan hệ kế thừa bằng biểu đồ Venn (biểu đồ dùng để biểu
diễn mối quan hệ của các tập hợp)

trong cuộc thi mang tên
Paganini tại Genoa.
Yes
David Golinkin là biên tập viên hay tác giả
của mười tám cuốn sách, và hơn 150 bài hỏi
đáp, bài viết, bài giảng và sách.
Golinkin đã viết mười tám
cuốn sách.
No
Giải bóng chày nhà nghề và các câu lạc bộ
của nó đã mua hơn 260 triệu hàng đôla hàng
hoá và dịch vụ từ các công ty nhỏ và do phụ
nữ sở hữu
Giải bóng chày nhà nghề
và các câu lạc bộ của nó đã
mua các công ty nhỏ và do
phụ nữ sở hữu
Yes
Thạch anh sông Ranh là một viên kim cương
giả được làm từ đá pha lê, thủy tinh hoặc
acrylic
Kim cương được làm cùng
với kính
No
Đảo Scott là một phần của Ross Dependency,
thuộc chủ quyền của New Zealand
Đảo Scott thuộc New
Zealand
No


bản đánh giá (nâng lên mức độ đoạn văn) tuy nhiên các ví dụ dùng để xây dựng dữ
liệu đào tạo và kiểm thử hầu hết ở dạng văn bản ngắn (câu). Các cặp dữ liệu được ghi
chú và phân lớp dựa theo các thao tác có liên quan như trích xuất thông tin (IE), thu
thập thông tin (IR), hệ thống hỏi đáp (QA) và tóm tắt (SUM) cũng như các phán quyết
kế thừa tương ứng của chúng (“Có” hoặc “Không” kế thừa).
7

RTE-4 (2008) tiếp tục phát triển từ các cuộc thi trước đó, với mục đích chính là
phân lớp được các phán quyết thành ba kiểu: “Có”, “Không” và “Không xác định” để
tăng tính chính xác trong việc phân biệt thông tin; tính chất kế thừa của một giả thuyết
là không rõ ràng khi thực hiện suy luận dựa trên một văn bản được phân biệt là khác
so với một giả thuyết có thể nhìn thấy rõ ràng là không đúng hoặc trái ngược so với
văn bản nguồn. Tập dữ liệu của RTE-4 gồm có 1000 cặp (300 đối với mỗi IE và IR,
400 đối với SUM, QA).
Bài toán của RTE-5 (2009) cũng giống với RTE-4 nhưng có một số thay đổi:
Độ dài trung bình của các văn bản là dài hơn. Các văn bản được thu thập từ nhiều
nguồn khác nhau và không được chỉnh sửa từ tài liệu nguồn của chúng. Do vậy, hệ
thống sẽ được yêu cầu xử lý văn bản thực sự, có thể bao gồm các lỗi đánh máy và các
câu không đúng ngữ pháp. Phát hiện kế thừa văn bản sẽ chỉ dựa trên ba cài đặt ứng
dụng là: hỏi đáp (QA), trích chọn thông tin (IE) và tìm kiếm thông tin (IR).
Hội nghị RTE-6 (2010) có một số khác biệt đáng kể so với RTE-5, đó là kế
thừa văn bản được thực thi trên toàn bộ tập corpus thực sự. Trong RTE-6, một giai
đoạn lọc tìm kiếm thông tin sơ bộ được thực hiện bằng cách sử dụng Lucene (Lucene
là một thư viện mã nguồn mở cho tìm kiếm toàn văn bản, được phát triển bởi Dough
Cutting, thư viện này cung cấp các hàm cơ bản hỗ trợ cho việc đánh chỉ mục và tìm
kiếm), để chọn cho H một tập các câu kế thừa ứng viên được đánh giá bởi các hệ
thống tham gia. Nhằm tiếp tục các nỗ lực thử nghiệm trong các ứng dụng NLP, tập
hợp cơ sở tri thức (Knowledge Base Population: KBP) được đề xuất. Cơ sở dữ liệu tri
thức sẽ giúp cho việc nâng cao kết quả cho bài toán phát hiện kế thừa văn bản.
Hội nghị RTE-7 (2011) tiếp tục phát triển những vấn đề trong hội nghị RTE-6.

Trong lĩnh vực dịch máy (Machine Translation), kế thừa văn bản dùng để đánh
giá sự tương đương về mặt ngữ nghĩa của các bản dịch. 9

1.5. Tóm tắt chương một.
Trong chương một, khóa luận đã trình bày một số nội dung xoay quanh vấn đề kế thừa
văn bàn: khái niệm kế thừa văn bản, phát biểu bài toán phát hiện kế thừa văn bản, sau
đó khóa luận giới thiệu khái quát về bài toán trong các hội nghị RTE. Cuối chương,
khóa luận trình bày về vai trò của phát hiện kế thừa văn bản.

10

Chương 2. Hướng tiếp cận học máy cho bài toán phát hiện kế
thừa văn bản và mô hình học máy SVM.
Từ năm 2005 tới nay, hội nghị khoa học quốc tế thường niên về RTE (nhánh
RTE của hội nghị phân tích văn bản (Text Analysis Conference: TAC)) đã tập hợp
được nhiều công trình nghiên cứu về RTE. Trải qua 7 kỳ hội nghị với hàng trăm bài
báo và nhiều công trình nghiên cứu được công bố, nhìn chung hướng tiếp cận mà các
tác giả sử dụng chủ yếu như: hướng tiếp cận sử dụng học máy với việc lựa chọn các
đặc trưng, hướng tiếp cận dựa trên đại diện ở các mức độ khác nhau của xử lý ngôn
ngữ tự nhiên (cú pháp, ngữ nghĩa), hướng tiếp cận dựa trên suy luận logic. Hầu hết các
hướng tiếp cận trên đều có thể dựa trên các cơ sở tri thức bên ngoài như WordNet
2

(một cơ sở dữ liệu từ vựng cho tiếng Anh. WordNet cung cấp các định nghĩa tổng quát
liên quan đến từ vựng, hữu ích trong việc xử lý ngôn ngữ tự nhiên). Một cơ sở dữ liệu
từ vựng tiếng Anh khác mà các tác giả cũng thường xuyên sử dụng là FrameNet
3

một số đặc trưng khác được tính dựa trên các đặc trưng giữa các cặp T-H với nhau
(đặc trưng cross-pair).
2.2.1. Các đặc trưng Intra-pair (In-pair features)
Các đặc trưng Intra-pair là các đặc trưng được trích xuất từ việc so sánh cặp câu
T và H. Nếu chúng ta coi các câu như một nhóm các token (đơn vị từ vựng) thì sự
trùng lặp từ vựng sẽ là một chỉ số tốt. Ngoài ra, các đặc trưng có thể được trích xuất
dựa từ cấu trúc cú pháp hoặc các đại diện ngữ nghĩa hoặc thậm chí cả các hình thức
logic. Nếu chúng ta coi các câu như các túi từ (bag of words) thì các đặc trưng được
xem xét bao gồm: số lượng các từ trùng lặp giữa T và H hoặc tỉ lệ của số lượng từ
trùng lặp với tổng số các từ trong T hoặc H.
J. Bos và K. Market [9] kết hợp phương pháp dựa trên trùng lặp từ và phương
pháp dựa trên suy luận logic. Một số tác giả sử dụng các đặc trưng phong phú ở các
cấp độ xử lý đa dạng khác nhau.Sự kết hợp giữa các từ trong T và H được phát hiện và
giúp cho việc phân lớp trong giai đoạn tiếp theo.
A. Newman và cộng sự [5] đề xuất ra hai hệ thống, hệ thống đầu tiên sử dụng
một số độ đo tương tự, bao gồm ROUGE (Recall-Oriented Understudy for Gisting
Evaluation: một gói phần mềm với một tập các độ đo được sử dụng cho việc đánh giá
tóm tắt tự động và phần mềm dịch máy trong xử lý ngôn ngữ tự nhiên), độ đo Cosin,
và độ đo tương đồng cho danh từ dựa trên WordNet. Với các đặc trưng dựa trên động
từ, các tác giả sử dụng mạng ngữ nghĩa VerbOcean (một tài nguyên từ vựng cung cấp
những mối quan hệ ngữ nghĩa giữa các động từ). Trên thực tế, hầu hết các nhóm sử
dụng các đặc trưng từ vựng đều áp dụng các độ tương đồng giữa các từ dựa vào từ
điển WordNet hoặc các nguồn tài nguyên từ vựng khác.
Theo Rui Wang [15] thì R. Adam sử dụng khoảng cách chỉnh sửa từ vựng như
là một đặc trưng. Về cơ bản, tác giả đếm số các token không được ánh xạ sau khi so
sánh cặp <T, H> và sau đó mở rộng độ dài của H bằng toán tử chèn từ phép chỉnh sửa.
T kế thừa H nếu có một chuỗi các phép chuyển đổi được áp dụng để biến T thành H
với tổng thể chi phí ở dưới ngưỡng cho phép. Sự khác biệt ở đây là các tác giả tính
toán khoảng cách chỉnh sửa dựa trên cây phụ thuộc, bao gồm các phép toán: chèn, xóa
12

các vị trí (anchor). Các vị trí này được sử dụng để kết nối toàn bộ T và H. Sau đó, một
hàm nhân dựa trên đặc trưng cross-pair được áp dụng để tính toán độ tương đồng. Các
tác giả xấp xỉ tổng độ tương đồng giữa hai câu T và hai câu H thành độ tương đồng
giữa hai cặp.
13

2.1.3. Các phương pháp học máy
Sau khi tiến hành trích xuất và lựa chọn đặc trưng thì quá trình chọn phương
pháp học (bộ phân lớp) sẽ được thực hiện. Các phương pháp học máy được các tác giả
sử dụng là rất đa dạng bao gồm: SVM, cực đại hóa Entropy, cây quyết định, … Trong
các loại học máy kể trên thì DT và SVM là hai phương pháp học máy được dùng phổ
biến nhất trong bài toán phát hiện kế thừa văn bản.
SVM là một phương pháp học máy dựa trên hàm nhân, nó biểu diễn tất cả các
đặc trưng thông qua việc chuyển đổi chúng thành một vector đặc trưng. Theo Rui
Wang [15], J. Herrera và cộng sựsử dụng cả hai loại đặc trưng: các mối quan hệ từ
vựng và các đặc trưng dựa vào nhận dạng thực thể để phân lớp và nhấn mạnh tầm
quan trọng của loại đặc trưng thứ hai. Kouyleko và Magnini có những cài đặt khác
nhau cho toán tử chèn của phép tính toán khoảng cách chỉnh sửa cây. Do đó, họ xây
dựng năm hệ thống đường cơ sở và kết hợp chúng lại như là các đặc trưng cho bộ phân
lớp SMO. SMO là thuật toán tối ưu thiểu tuần tự (Sequential Minimal Optimization)
của John Platt để đào tạo bộ phân lớp SVM. Schilder và McInnes [6] có hai hướng tiếp
cận dựa trên từ vựng và hai hướng tiếp cận dựa trên khoảng cách chỉnh sửa cây. Do
đó, các tác giả tiến hành kết hợp các hướng tiếp cận này vào một bộ phân lớp SVM.
Bài toán phát hiện quan hệ kế thừa có thể coi như một bài toán phân lớp nhị
phân. Vì vậy thuật toán cây quyết định được sử dụng rộng rãi bởi các nhóm lựa
chọn các đặc trưng ngôn ngữ. J. Bos và K. Markert [9] sử dụng cả đặc trưng nông
và đặc trưng sâu để xây dựng môt mô hình cây quyết định. Nicholson sử dụng các
mô hình cây quyết định khác nhau như: C4.5, C5 vào hệ thống phát hiện kế thừa
văn bản của mình.
2.2. Một số hệ thống phát hiện kế thừa văn bản có sử dụng học máy