i

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Chu Thị Thủy TRÍCH CHỌN TỰ ĐỘNG QUAN HỆ PHƯƠNG THỨC TỪ
VĂN BẢN TIẾNG VIỆT DỰA TRÊN THUẬT TOÁN SVM
VÀ THỬ NGHIỆM ĐÁNH GIÁ
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ Thông tin

Hà Nội - 2011
ii

ĐẠI HỌC QUỐC GIA HÀ NỘI

và hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp.
Tôi chân thành cảm ơn các thầy, cô đã tạo những điều kiện thuận lợi cho tôi học
tập, nghiên cứu tại trường Đại Học Công Nghệ và sự hỗ trợ từ đề tài QG.10.38.
Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong nhóm
“Khai phá dữ liệu” SIS-KTLab đã giúp tôi rất nhiều trong việc hỗ trợ kiến thức chuyên
môn để hoàn thành tốt khoá luận.
Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người
thân yêu luôn bên cạnh và động viên 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!
Sinh viên
Chu Thị Thủy
ii

Tóm tắt
Trích chọn các mối quan hệ ngữ nghĩa từ văn bản ngày càng trở nên quan trọng
đối với các ứng dụng như hệ thống hỏi đáp, trích chọn thông tin, tóm tắt văn bản và
hiểu văn bản. Khóa luận này đề xuất một phương pháp để tự động trích chọn quan hệ
phương thức từ văn bản dựa trên học máy SVM. Đưa ra một tập các ký hiệu liên quan
tới quan hệ phương thức, bao gồm DOMAIN và RANGE. Phân tích sự gắn kết của
quan hệ phương thức với những quan hệ khác. Đồng thời, chúng tôi cũng trình bày các
mẫu từ vựng – cú pháp cơ bản biểu diễn quan hệ phương thức. Một tập các đặc trưng
riêng được trích chọn làm tăng độ chính xác và tính khả thi của mô hình.
Thực nghiệm bước đầu trên tập dữ liệu tiếng Việt gồm khoảng 300 câu
chứa/không chứa quan hệ phương thức cho thấy phương pháp đề xuất đạt được một
kết quả nhất định: độ đo F trong khoảng 60 - 70%. Dựa vào đó, chúng tôi nhận thấy
phương pháp trích chọn quan hệ phương thức đã đề xuất và triển khai là khả quan.


Mục lục
Tóm tắt ii
Lời cam đoan iii
Mục lục iv
Danh sách các bảng vi
Danh sách các hình vẽ vii
Danh sách các hình vẽ vii
Danh sách các chữ viết tắt viii
Danh sách các chữ viết tắt viii
Mở đầu 1
CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN TRÍCH CHỌN QUAN HỆ PHƯƠNG
THỨC 4
1.1 Khái niệm Quan hệ phương thức 4
1.2 Bài toán Trích chọn quan hệ phương thức 5
1.3 Một số ký hiệu 7
1.4 Sự gắn kết của quan hệ phương thức với những quan hệ khác 9
CHƯƠNG 2. PHƯƠNG PHÁP TRÍCH CHỌN QUAN HỆ PHƯƠNG THỨC 11
2.1 Các mẫu từ vựng – cú pháp biểu diễn quan hệ phương thức 11
2.1.1 Các mẫu từ vựng – cú pháp cơ bản 11
2.1.2 Nhập nhằng trong các mẫu từ vựng – cú pháp 15
2.2 Hướng tiếp cận giải quyết vấn đề 15
2.2.1 Mô hình phân lớp SVM nhị phân 15
2.2.2 Trích chọn đặc trưng 19
2.2.3 Quan hệ phương thức trong tiếng Việt 22
CHƯƠNG 3. MÔ HÌNH GIẢI QUYẾT BÀI TOÁN TRÍCH CHỌN QUAN HỆ
PHƯƠNG THỨC TỪ VĂN BẢN TIẾNG VIỆT 24
CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ 28
4.1 Mô tả thực nghiệm 28
4.1.1 Môi trường thực nghiệm 28

Hình 1. Quá trình trích chọn các mối quan hệ ngữ nghĩa [4] 6

Hình 2. Kiến trúc cơ bản của bộ phân tích ngữ nghĩa [4] 7

Hình 3. Mô hình máy vector hỗ trợ khả tách tuyến tính 16

Hình 4. Phương pháp lề mềm 18

Hình 5. Mô hình trích chọn quan hệ phương thức từ văn bản tiếng việt 25

viii

Danh sách các chữ viết tắt
SVM Support Vector Machines
POS Part – Of – Speech
NE Named Entities
ntao Non Temporal Abstract Objects
MNR Manner
CAU Cause-Effect
LOC Location
1

Mở đầu
Các khái niệm có chứa trong một tập câu hay tập tài liệu luôn có liên hệ với
nhau thông qua các mối quan hệ ngữ nghĩa. Các mối quan hệ này thường được Nn giấu
trong các câu, việc tìm ra các mối quan hệ ngữ nghĩa là rất cần thiết, nhằm phục vụ
cho quá trình xử lý ngôn ngữ. Vì thế, bài toán trích chọn mối quan hệ ngữ nghĩa được
đặt ra và đã nhận được sự quan tâm rất lớn từ các nhà nghiên cứu, các hội nghị lớn trên
thế giới trong những năm gần đây như: Colling, ACL, Senseval… Đồng thời, cũng là
một phần trong các dự án quan trọng mang tầm cỡ quốc tế trong lĩnh vực khai phá tri

[2]
như CAUSE-EFFECT (Chang và Choi, 2006), INTENT
(Tatu, 2005), PART-WHOLE (Girju và cộng sự, 2006).

1

http://www.itl.nist.gov/iad/894.01/tests/ace/

2

http://infowar.net/tia/www.darpa.mil/iao/EELD.htm
3

http://www.globalwordnet.org/

2

Xét các nghiên cứu về quan hệ phương thức: Girju và cộng sự (2003)
[3]
sử
dụng mô hình phân lớp Naïve Bayes và đưa ra một tập các đặc trưng để trích chọn
quan hệ phương thức nhưng chưa xét tới những cụm giới từ, hệ thống cho độ chính
xác 0.644, độ hồi tưởng 0.687 và độ đo F là 0.665. Eduardo Blanco và Dan Moldovan
(2010)
[2]
đã bổ sung thêm những đặc trưng riêng của quan hệ phương thức, tăng độ
chính xác tới 0.759, độ hồi tưởng 0.626 và độ đo F là 0.686. Nghiên cứu của Gildea và
Jurasky (2002)
[6]
, Giuglea và Moschitti (2006)

Chương 4: Thực nghiệm và đánh giá. Mô tả thực nghiệm từ quá trình chuNn
bị dữ liệu tới quá trình thực nghiệm. Từ đó, thống kê độ chính xác, độ hồi tưởng của
hệ thống và rút ra các đánh giá tổng quan trong quá trình trích chọn quan hệ phương
thức.
Phần kết luận và hướng phát triển khoá luận: Tóm lược những điểm chính
của khoá luận. Chỉ ra những điểm cần khắc phục, đồng thời đưa ra những hướng
nghiên cứu trong thời gian sắp tới.
4 CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN TRÍCH CHỌN
QUAN HỆ PHƯƠNG THỨC
Phát hiện ra được các mối quan hệ trong văn bản là một điều hết sức quan trọng
cho các mô hình mà muốn hiểu được ngôn ngữ của con người. Hơn thế nữa, các quan
hệ về mặt ngữ nghĩa thể hiện các thành phần cốt lõi trong việc tổ chức của cơ sở tri
thức ngữ nghĩa từ vựng. Trong cơ sở tri thức này, thông tin được biểu diễn dưới dạng
các khái niệm và liên kết nhau bởi các mối quan hệ ngữ nghĩa. Các khái niệm có thể là
một đơn vị văn bản đơn giản như là các từ, tới một cấu trúc phức tạp hơn như là một
mệnh đề danh từ phức tạp. Một số quan hệ ngữ nghĩa quan trọng nhất trong ngôn ngữ
tự nhiên là quan hệ tổng quát – cụ thể (IS-A), quan hệ tổng thể – bộ phận (WHOLE-
PART), quan hệ phương thức (MANNER), quan hệ nguyên nhân – kết quả (CAUSE-
EFFECT)…
1.1 Khái niệm Quan hệ phương thức
Nói một cách chung nhất, quan hệ phương thức biểu diễn cách thức, nét đặc
trưng, phương pháp thực hiện hoặc kiểu cách của một sự vật nào đó đã xảy ra
[2]
.
Theo WordNet
4
, quan hệ phương thức được định nghĩa như phương pháp thực

“how”.
Ví dụ: Q: How do Democrats want to work?
A: work together (with Republicans).
Q: How do Democrats want to create jobs?
A: by investing in technology.
Q: How do Democrats want America to lead the world?
A: in growth and opportunity.
Quan hệ phương thức xuất hiện thường xuyên trong văn bản và 2 ngân hàng dữ
liệu phổ biến chứa quan hệ phương thức là FrameNet http://framenet.icsi.berkeley.edu/
và PropBank http://verbs.colorado.edu/~mpalmer/projects/ace.html. Theo thống kê,
PropBank chứa 8037 câu chứa quan hệ phương thức (10.7%) trên tổng số 74980 câu
chứa các thành phần giống như bổ ngữ (adjunct-like arguments).
Có rất nhiều mẫu từ vựng – cú pháp để biểu diễn một quan hệ phương thức,
nhưng chủ yếu là các cụm trạng từ và cụm giới từ.
Ví dụ: The company said Mr. Stronach will personally direct the restructuring
assisted by Manfred Gingl.
(Công ty nói rằng ông Stronach sẽ một mình trực tiếp quản lý việc cơ cấu lại được sự
giúp đỡ của Manfred Gingl.)
Độ khó trong việc trích chọn tăng lên khi cùng một mẫu từ vựng – cú pháp biểu
diễn nhiều quan hệ khác nhau trong các ngữ cảnh khác nhau. Một cách có thể để kiểm
tra một mẫu biểu diễn quan hệ phương thức hay không là tìm câu trả lời đúng cho câu
hỏi “In what manner/how <to_verb> ?”. Ví dụ, “He run quickly” và câu hỏi là “How
to run?”. Phân biệt với câu trả lời cho các câu hỏi “Where <verb> ?” hoặc “When
<verb> ?”. Ví dụ, “He runs on the field”, “He runs quite often”.
1.2 Bài toán Trích chọn quan hệ phương thức
Roxana Girju đã phát biểu bài toán trích chọn các mối quan hệ ngữ nghĩa
[4]

như sau: Nhận đầu vào là các khái niệm hay thực thể, thông qua tập tài liệu không có
6

Tin tức
Thư viện số
Thông tin
không c
ấ
u trúc

- KB (Ontology)
- Văn bản đã được
gán nhãn ngữ
nghĩa
-Tri thức có cấu
trúc

7 Hình 2. Kiến trúc cơ bản của bộ phân tích ngữ nghĩa
[4]

Quá trình phân tích ngữ nghĩa bao gồm các bước:
1. Tiền xử lý văn bản: phân tích từ tố, gán nhãn từ loại, cây cú pháp, phân
biệt nhập nhằng giữa các từ đồng nghĩa, nhận diện tên thực thể…
2. Lựa chọn đặc trưng: quyết định một tập các đặc trưng ràng buộc của
danh từ và ngữ cảnh dùng để phân lớp các mối quan hệ ngữ nghĩa khác
nhau.
3. Bộ phân lớp: phân lớp các câu đầu vào vào những lớp quan hệ ngữ nghĩa

được gắn liền với các khái niệm khác, như “slowly” (chậm chạp), “abruptly” (đột
ngột). Các đối tượng trừu tượng không chứa thời gian biểu diễn những thực thể vô
hình không thể nhìn thấy, sờ thấy được, như “odor” (mùi thơm), “disease” (bệnh tật),
“mile” (dặm Anh) và không phải là “book” (quyển sách) hoặc “car” (xe ôtô) bởi vì
những thực thể này có thể sờ thấy được. Bằng cách này hay cách khác, thì những đối
tượng đó là sản phNm từ lập luận của con người và không thể định nghĩa một cách rõ
ràng. Chúng không biểu diễn thời gian (thời kỳ hoặc thời điểm) như “week” (tuần),
“yesterday” (ngày hôm qua).
Sau đây là bảng biểu diễn luật phân tích các lớp ngữ nghĩa (tình huống, đặc
tính, đối tượng trừu tượng không chứa thời gian, trạng thái) được sử dụng trong định
nghĩa DOMAIN và RANGE, ký hiệu –NE chỉ loại tên thực thể, ký hiệu isHypo(x) của
từ w chỉ ra w có quan hệ tổng quát – cụ thể (IS-A) với x trong WordNet 2.0:
Bảng 1. Phân tích các lớp ngữ nghĩa được sử dụng trong định nghĩa
DOMAIN(MNR) và RANGE(MNR)
Lớp ngữ nghĩa Luật
situation state || event
state POStag=verb || isHypo(state.n.4)
event POStag=verb && in(verb_events)) || (POStag=noun
&& !animate_object && (isHypo(phenomenon.n.1) ||
isHypo(event.n.1) || in(noun_events))
animate_object livingNE || (POStag=noun && (isHypo(entity.n.1) &&
!isHypo(thing.n.9) && !isHypo(anticipation.n.4) ||
isHypo(social_group.n.1)))
livingNE neType=(human | organization | country | town |
province | other-loc
9

quality POStag=(adverb | gerund) || headPP = (with | without)
Non_temporal_abstract_object abstract_object && !temporal
abstract_object neType=money || isHypo(thing.n.9) ||

.
(John có thói quen chạy đều đặn.)
Một cách để giải quyết nhập nhằng là xét độ ưu tiên giữa các mối quan hệ ngữ
nghĩa. Tuy nhiên, tồn tại một khó khăn lớn là quan hệ phương thức có độ ưu tiên thấp
hơn quan hệ địa điểm và quan hệ thời gian. Vì vậy, trong rất nhiều trường hợp thì cách
giải quyết này không đạt hiệu quả.
10

Một cách giải quyết khác ở đây là sử dụng các định nghĩa mở rộng ở trên. Ví
dụ: cái búa không phải là một từ chỉ đặc tính, không phải là từ chỉ đối tượng trừu
tượng không chứa thời gian, cũng không phải là từ chỉ trạng thái, mà nó là một đối
tượng sờ thấy được. Do đó, xét theo mục 1.3 thì các ký hiệu MNR(with a hammer,y),
MNR(over the fence,y), MNR(every other week,y) không có ý nghĩa sử dụng và các
câu đó cũng không phải là câu biểu diễn quan hệ phương thức.
Một mối quan hệ khác cũng liên quan tới quan hệ phương thức là quan hệ
nguyên nhân – kết quả (CAUSE-EFFECT) và độ ưu tiên cũng không giải quyết được
nhập nhằng trong trường hợp này.
Ví dụ: The legislation itself noted that it [was introduced]
y
[“by request”]
x
.
(Tự pháp luật lưu ý rằng nó đã được xây dựng bởi yêu cầu.)
=> Cụm giới từ “by request” chỉ ra mối quan hệ nguyên nhân – kết quả
(CAUSE-EFFECT), mà không phải là mối quan hệ phương thức bởi vì “request”
chính là nguyên nhân ảnh hưởng tới sự xây dựng pháp luật. Theo định nghĩa mở rộng
trong mục 1.3, “request” là một sự kiện – nó ngụ ý một sự thay đổi nên MNR(by
request,y) bị loại bỏ do vi phạm điều kiện về DOMAIN.
11


Khảo sát với tiếng Anh trên tập dữ liệu PropBank, Eduardo Blanco và Dan
Moldovan
[2]
đã đưa ra thống kê sau:

6

http://wordnet.princeton.edu/~geo/

7

http://wordnet.princeton.edu/~fellbaum/

8

http://wordnet.princeton.edu/~rit/

12

Bảng 2. Các mẫu cú pháp biểu diễn quan hệ phương thức trong PropBank, số
câu xuất hiện và ví dụ (Khảo sát với 7852/8037 câu chứa quan hệ phương thức
trong PropBank). Trong tất cả các ví dụ về MNR(x,y), x đã được in đậm.
Mẫu cú
pháp
#Số câu
xuất hiện
%Số câu
xuất hiện
Câu ví dụ
ADVP


run by former CBS Inc. President Jon Backe.
(Backe là một hãng truyền thông được tổ chức
chặt chẽ điều hành bởi người sáng lập cựu chủ
tịch tập đoàn CBS Jon Backe.)
S (mức
câu)
148 1.9% Salomon [posted]
y
an unexpectedly big gain in
quarterly earnings, [aided by its securities
trading and investments banking activities]
S
.
(Salomon đã công khai sự thành công ngoài
sức mong đợi trong doanh thu hàng quý, được
hỗ trợ bởi các hoạt động an ninh thương mại
và đầu tư ngân hàng.)
NP (cụm
danh từ)
120 1.5% He [graduated]
y
[Phi Beta Kappa]
NP
from the
University of Kentucky at age 18, after
spending only 2 ½ years in college.
(Anh ấy đã tốt nghiệp Phi Beta Kappa từ
trường đại học Kentucky ở tuổi 18 chỉ sau 2 ½
năm học.)

ADVP
[merged]
y
with
Bristol-Myers Co. earlier this month]
VP
.
(Công ty [được chính thức sát nhập với Công ty
Bristol-Myers đầu tháng này]
VP
.)
3107 PP
This is something P&G [would [do]
y
[with or
without Kao]
PP
]
VP
, says Mr. Zurkuhlen.
(Ông Zurkuhlen nói rằng một vài hoạt động P&Q
[sẽ được làm mà có hoặc không có Kao]
VP
.)
S (mức
câu)
215 ADVP [[
Vi
rtually word by word
]

17 ADVP Two former ministers [were]
y
[[so heavily]
ADVP

implicated]
ADJP
in the Koskotas affair that PASOK
members of Parliament voted
(Hai bộ trưởng cũ đã [liên quan quá nặng nề]
ADJP

đến vấn đề những thành viên POSOK của quốc
hội được bầu cử ở Koskotas)
4 PP ABC touted “Call to Glory.” But the military
drama was [[missing]
y
[in action]
PP
]
ADJP
within
weeks.
(ABC đã giới thiệu “Call to Glory”. Nhưng bộ
phim truyền hình quân sự này đang bị [lãng quên
trong hành động]
ADJP
của tuần.)
PP (cụm
giới từ)


2.1.2 Nhập nhằng trong các mẫu từ vựng – cú pháp
Những cụm trạng từ và giới từ thường có độ nhập nhằng cao khi tác vụ xác
định ngữ nghĩa của nó. Trong PropBank, chỉ có 22.2% số câu chứa cụm trạng từ biểu
diễn quan hệ phương thức (30.3% biểu diễn quan hệ thời gian), và 6.6% cụm giới từ
bắt đầu với “in”, 6.1% cụm giới từ bắt đầu với “at” biểu diễn quan hệ phương thức
[2]
.
Như vậy, có thể kết luận là quan hệ phương thức khó được phát hiện từ cụm giới từ.
Ngay cả những cụm bắt đầu với “with”, “like”, “under” và “over” cũng có thể biểu
diễn quan hệ phương thức.
Ví dụ: A majority of an NIH-appointed panel recommended late last year that
the research continue under carefully controlled conditions.
(Phần lớn danh sách thiết bị NIH được đề nghị vào cuối năm ngoái để nghiên cứu tiếp
tục dưới những điều kiện được kiểm soát cn thận.)
Ví dụ: Bars where Japanese revelers sing over recorded music.
(Những quán bar nơi mà người Nhật tổ chức hát trên những bài hát được thu âm
lại.)
=> Trong cả 2 trường hợp, thì danh từ chính được chứa trong cụm giới từ là
“conditions” và “music”, những danh từ này đều thuộc các đối tượng trừu tượng không
chứa thời gian.
2.2 Hướng tiếp cận giải quyết vấn đề
2.2.1 Mô hình phân lớp SVM nhị phân
SVM ra đời từ lý thuyết học thống kê do Vapnik và Chervonenkis
[10]
xây dựng
và có nhiều tiềm năng phát triển về mặt lý thuyết cũng như ứng dựng trong thực tiễn.
Tư tưởng chung của học máy SVM như sau:
- Giai đoạn xây dựng mô hình: Cho một tập mẫu dữ liệu huấn luyện đã được gán
nhãn lớp, như vậy có một tập nhãn lớp tương ứng xác định tên tập mẫu. Mỗi