BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
-----------*****------------

SAM CHANRATHANY

TRÍCH RÚT THỰC THỂ CÓ TÊN VÀ QUAN HỆ
THỰC THỂ TRONG VĂN BẢN TIẾNG VIỆT

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

Hà Nội - 2012


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

---------------

SAM CHANRATHANY

TRÍCH RÚT THỰC THỂ CÓ TÊN VÀ QUAN HỆ
THỰC THỂ TRONG VĂN BẢN TIẾNG VIỆT

Chuyên ngành: Hệ thống Thông tin
Mã số

: 62.48.05.01

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. GS.TS. Nguyễn Thanh Thủy

2. PGS.TS. Lê Thanh Hương

HÀ NỘI - 2012


LỜI CẢM ƠN
Luận án được hoàn thành tại trường Đại học Bách khoa Hà Nội. Để hoàn thành
luận án này, tác giả đã nhận được sự chỉ bảo tận tình, cùng những yêu cầu nghiêm
khắc của GS. TS. Nguyễn Thanh Thủy, PGS.TS. Lê Thanh Hương. Thầy, Cô đã
truyền đạt rất nhiều kiến thức quí báu cũng như những kinh nghiệm nghiên cứu
khoa học trong suốt thời gian tác giả làm nghiên cứu sinh. Lời đầu tiên, tác giả xin
bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy và Cô.
Tác giả xin chân thành gửi lời biết ơn đến: Ban lãnh đạo Viện Công nghệ
thông tin và Truyền thông, Bộ môn Hệ thống Thông tin, Viện Đào tạo Sau đại học,
Trung tâm Tính toán Hiệu năng cao, thuộc trường Đại học Bách khoa Hà Nội đã
tạo điều kiện thuận lợi trong quá trình học tập, nghiên cứu và hoàn thành luận án.
Tác giả cảm ơn các Thầy giáo, Cô giáo ở Bộ môn Hệ thống Thông tin-Viện
Công nghệ Thông tin và Truyền thông, trường Đại học Bách khoa Hà Nội đã động
viên và trao đổi kinh nghiệm để tác giả có thể hoàn thiện luận án.
Tác giả cảm ơn TS. Nguyễn Hữu Đức và các cán bộ các anh chị em ở Trung
tâm Tính toán Hiệu năng cao, đã tạo điều kiện, nhiệt tình giúp đỡ và trao đổi học
hỏi trong quá trình làm luận án.
Sự quan tâm, mong mỏi của mọi thành viên trong gia đình là một trong động
cơ để tác giả nỗ lực học tập, nghiên cứu. Luận án này như một món quà tinh thần,
xin đáp lại những niềm quan tâm, mong mỏi đó.
Cuối cùng, tác giả xin bày tỏ lòng biết ơn tới những người thân và bạn bè đã
ưu ái, giúp đỡ, động viên, khích lệ để tác giả hoàn thành luận án này.



LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào
luận án. Các kết quả trong luận án là trung thực và chưa từng được công bố trong
bất kỳ công trình nào khác.
Tác giả luận án

Sam Chanrathany


MỤC LỤC
Trang bìa phụ ........................................................................................
Lời cảm ơn

i

................................................................................................................... ii

Lời cam đoan ........................................................................................ iii
Mục lục ................................................................................................... v
Danh mục các chữ viết tắt .................................................................... x
Danh mục các bảng .............................................................................. xi
Danh mục các hình ............................................................................. xii
CHƯƠNG 1 MỞ ĐẦU .....................................................................................................1

1.1 Động cơ nghiên cứu của luận án ........................................................................ 1
1.2 Mục tiêu và phạm vi nghiên cứu của luận án ..................................................... 5
1.2.1 Mục tiêu nghiên cứu ...................................................................................... 5
1.2.2 Phạm vi nghiên cứu ...................................................................................... 6

1.3 Đóng góp chính của luận án ............................................................................... 7
1.4 Cấu trúc của luận án ........................................................................................... 8
1.5 Các thuật ngữ được sử dụng trong luận án ......................................................... 8
CHƯƠNG 2 CÁC NGHIÊN CỨU LIÊN QUAN .........................................................10

2.1 Bài toán trích rút thông tin ............................................................................... 10
2.2 Bài toán trích rút thực thể ................................................................................. 12
2.2.1 Các đặc trưng được sử dụng trong bài toán NER........................................ 13
2.2.2 Tình hình nghiên cứu ngoài nước về bài toán NER sử dụng học máy ....... 14
2.2.3 Tình hình nghiên cứu trong nước về bài toán NER ................................... 17
2.3 Bài toán trích rút mối quan hệ giữa các thực thể (RE) ..................................... 18
2.3.1 Các đặc trưng được sử dụng trong bài toán RE .......................................... 18
2.3.2 Tình hình nghiên cứu ngoài nước về bài toán RE ....................................... 19
2.3.3 Tình hình nghiên cứu trong nước về bài toán RE ....................................... 23


2.4

Một số phương pháp học bán giám sát khác.. ............................................. 25

2.5

Các phương pháp đánh giá kết quả trích rút ................................................ 26

2.5.1 Cách đánh giá dựa trên độ trùng khớp ........................................................ 27
2.5.2 Cách đánh giá của MUC.............................................................................. 28
2.6

Kết luận chương 2 ....................................................................................... 28


CHƯƠNG 3 CÁC PHƯƠNG PHÁP HỌC MÁY DÙNG TRONG LUẬN ÁN.........29

3.1

Mô hình trường ngẫu nhiên có điều kiện .................................................... 29

3.1.1 Khái niệm mô hình trường ngẫu nhiên có điều kiện CRF .......................... 29
3.1.2 Huấn luyện CRF ......................................................................................... 31
3.1.3 Gán nhãn cho dữ liệu dạng chuỗi ................................................................ 33
3.2

Mô hình máy vectơ hỗ trợ .......................................................................... 33

3.3

Mô hình Dirichlet ẩn ................................................................................... 37

3.4

Các phương pháp học bán giám sát ............................................................. 40

3.4.1 Phương pháp lan truyền nhãn ..................................................................... 40
3.4.2 Phương pháp bootstrapping ......................................................................... 42
3.5

Kết luận chương 3 ....................................................................................... 43

CHƯƠNG 4 TRÍCH RÚT THỰC THỂ TỪ VĂN BẢN TIẾNG VIỆT .................. 45

4.1


Một số đặc điểm tiếng Việt ảnh hưởng đến việc trích rút thực thể ............. 45

4.2

Trích rút thực thể sử dụng trường ngẫu nhiên có điều kiện ....................... 50

4.2.1 Mô hình học bán giám sát dựa trên kết hợp luật đồng tham chiếu về tên
với CRF ....................................................................................................... 50
4.2.2 Mô hình học bán giám sát sử dụng CRF theo dạng Bagging ...................... 56
4.3

Trích rút thực thể sử dụng phương pháp lan truyền nhãn ........................... 57

4.3.1 Phương pháp đo mức độ tương đồng giữa các từ........................................ 58
4.3.2 Điểm yếu của giải thuật lan truyền nhãn và cách cải tiến ........................... 61
4.4

Thử nghiệm và đánh giá .............................................................................. 61

4.4.1 Tập dữ liệu và phương pháp thử nghiệm .................................................... 61
4.4.2 Kết quả thực nghiệm ................................................................................... 62
4.5

Kết luận chương 4 ....................................................................................... 65


CHƯƠNG 5 TRÍCH RÚT MỐI QUAN HỆ TỪ VĂN BẢN TIẾNG VIỆT ............ 67

5.1


Tính chất quan hệ giữa các thực thể trong văn bản tiếng Việt .................... 67

5.2

Trích rút mối quan hệ dựa trên máy vectơ hỗ trợ SVM .............................. 69

5.2.1 Mô hình học có giám sát dựa trên phương pháp ngôn ngữ mức nông ........ 70
5.2.2 Mô hình học bán giám sát dựa trên phương pháp ngôn ngữ mức nông
theo kiểu Bagging Bootstrapping ................................................................ 73
5.3

Trích rút mối quan hệ dựa trên phương pháp lan truyền nhãn .................... 74

5.3.1 Đo độ tương đồng giữa hai câu dựa trên phương pháp so trùng thuộc
tính từ .......................................................................................................... 75
5.3.2 Đo độ tương đồng giữa hai câu dựa trên phương pháp LDA ...................... 79
5.4

Thử nghiệm và đánh giá .............................................................................. 80

5.4.1 Tập dữ liệu và phương pháp thử nghiệm .................................................... 80
5.4.2 Kết quả thực nghiệm ................................................................................... 82
5.5

Kết luận chương 5 ....................................................................................... 84

CHƯƠNG 6 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ......................................... 86

6.1


Các kết quả đạt được……………………………………………………....86

6.1.1 Kết quả về thuật giải……………………………………………………….86
6.1.2 Kết quả thử nghiệm………………………………………………………...87
6.2 Hướng phát triển……………………………………………………………..88
TÀI LIỆU THAM KHẢO………………………………………………………………90
CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ………………………………......99
PHỤ LỤC
Phụ lục 1 TẬP D

LIỆU……………………………………………….......................100

Phụ lục 2 GIAO DIỆN CHƯƠNG TRÌNH HỖ TRỢ GÁN NHÃN…………..........109


DANH MỤC CH

VIẾT TẮT

ACE

Automatic Context Extraction

BIO

Begin Inside Outside

CRFs


Conditional Random Fields

CONLL

Computational Natural Language Learning

EM

Expectation Maximization

GLK

Global Context Kernel

HMM

Hidden Markov Model

IE

Information Extraction

JSRE

Java Simple Relation Extraction

MEMM

Maximum Entropy Markov Model


NP

Noun Phrase

LCK

Local Context Kernel

LDA

Latent Direchlet Alocattion

MUC

Message Understanding Conference

NER

Named Entity Regconition


RE

Relaiton Extraction

SLK

Shallow Linguistic Kernel

SVM


Support Vector Machine


DANH MỤC CÁC BẢNG
Bảng 2.1 Định dạng từ . ...................................................................................................13
Bảng 2.2 Đặc trưng từ điển . ............................................................................................14
Bảng 2.3 Bảng so sánh nhãn của hệ thống so với nhãn được gán bằng tay,
kèm theo mô tả lỗi tương ứng .........................................................................27
Bảng 4.1 Định dạng về tên thực thể ................................................................................45
Bảng 4.2 Nhóm luật nhận dạng thực thể (Nhóm luật 2 ) .................................................47
Bảng 4.3 Kết quả thực nghiệm của hệ thống NER sử dụng phương pháp học
bán giám sát ......................................................................................................63
Bảng 4.4 So sánh kết quả lần lặp thứ 9 của 3 phương pháp nói trên ..............................63
Bảng 4.5 So sánh kết quả trích rút thực thể CRF có giám sát với lan truyền nhãn .........64
Bảng 5.1 So sánh hệ thống RE có giám sát các hàm nhân ngữ cảnh tổng hợp ...............82
Bảng 5.2 So sánh kết quả hệ thống bán giám sát với hệ thống có giám sát .....................82
Bảng 5.3 So sánh kết quả khi chưa chuẩn hoá và sau khi chuẩn hoá ma trận ..................83
Bảng 5.4 So sánh kết quả phương pháp so trùng thuộc tính từ với LDA .........................83
Bảng 5.5 So sánh độ đo F của ba phương pháp lan truyền nhãn sử dụng so trùng thuộc tính từ,
SVM, và SVM kết hợp Bootstrapping………………………………………….84


DANH MỤC CÁC HÌNH
Hình 1.1 Phạm vi nghiên cứu của luận án .........................................................................6
Hình 2.1 Các thao tác chính của bài toán trích rút thông tin ..........................................11
Hình 2.2 Đồ thị phụ thuộc của ví dụ 2.4 ..........................................................................19
Hình 3.1 Đồ thị vô hướng mô tả CRF..............................................................................30
Hình 3.2 Siêu phẳng phân chia tập mẫu huấn luyện ....................................................... 34
Hình 3.3 Mô hình sinh LDA ............................................................................................38

Hình 3.4 Biểu diễn trực quan của phương pháp Bootstrapping ........................................43
Hình 4.1 Câu trúc trong cây phân cấp ngữ nghĩa ............................................................. 60
Hình 5.1 Các mẫu kernel ngữ cảnh toàn cục của ví dụ 5.9..............................................71
Hình 5.2 Các mẫu kernel ngữ cảnh cục bộ của ví dụ 5.9 ................................................73


1

CHƯƠNG 1
MỞ ĐẦU

1.1 Động cơ nghiên cứu của luận án
Hiện nay, với sự phát triển của Internet và việc kết nối băng thông rộng, khả năng tiếp cận
thông qua máy tính được kết nối Internet với khối lượng lớn các kho dữ liệu văn bản khắp
nơi trên thế giới là rất lớn. Tuy nhiên, chính khối lượng dữ liệu quá lớn có thể làm người
dùng bị “chìm ngập” trong thông tin hoặc mất quá nhiều thời gian để có được thông tin
mong muốn. Vấn đề này được quan tâm giải quyết trong các hệ thống trích rút thông tin
(Information Extraction – IE) theo miền ứng dụng nhằm trích rút thông tin từ các dữ liệu
phi cấu trúc hoặc bán cấu trúc, chuyển thành dữ liệu có cấu trúc. Trên cơ sở đó, ta có thể
thực hiện các truy vấn đa dạng và phức tạp hơn với việc tìm kiếm theo từ khóa đơn thuần
hiện có, hoặc xây dựng các ứng dụng như khai phá dữ liệu, hỏi đáp, mạng ngữ nghĩa, …
Vấn đề trích rút thông tin đang được quan tâm nghiên cứu nhiều trên thế giới. Mặc dù vậy,
các kết quả đạt được vẫn còn hạn chế. Các bài toán được đặt ra trong trích rút thông tin từ
dữ liệu văn bản là: trích rút thực thể có tên, trích rút các thuộc tính của thực thể, trích rút
thông tin về thời gian và trích rút thông tin về mối quan hệ giữa các thực thể. Trong thực
tế, các hệ thống trích rút thông tin thường được cài đặt cho một ứng dụng cụ thể. Các ứng
dụng khác nhau sẽ được giải quyết ở các khía cạnh và mức độ khác nhau. Phần lớn các hệ
thống trích rút thông tin hiện nay chỉ trích rút được các thông tin theo một khuôn dạng nhất
định, như thời gian (dd/mm/yy), mã vùng, mã nước, v.v… Có rất nhiều dạng thực thể và
thuộc tính mà các hệ thống IE chưa khai thác được.

Quá trình trích rút thông tin bao gồm các bước chính là: (1) Tiền xử lý văn bản (2)
nhận dạng thực thể (3) phân tích đồng tham chiếu (4) trích rút mối quan hệ giữa các thực
thể và (5) xuất ra theo khuôn dạng định nghĩa trước (có thể là cơ sở dữ liệu hoặc ontology).
Tiền xử lý là bước phân tách câu, phân tách từ, gán nhãn từ loại … cho văn bản hoặc tập
văn bản đầu vào. Thực thể được quan tâm ở đây là những đối tượng được tham chiếu qua
tên gọi như tên người, tên tổ chức, tên địa điểm, hoặc các đối tượng khác được tham chiếu
theo tên riêng [21]. Khái niệm thực thể có thể mở rộng, kèm theo cả thời gian và số lượng.


2
Nhiệm vụ của công việc nhận dạng thực thể là định vị và phân lớp các từ và cụm từ
được trích rút thành các lớp thực thể.
Bước phân tích đồng tham chiếu nhằm giải quyết các tham chiếu trùng nhau thông
qua các đại từ và các thực thể cần trích rút.
Trích rút mối quan hệ giữa các thực thể có tên là việc xác định mối quan hệ giữa các
thực thể trong văn bản. Ví dụ, câu “Ông Kiên làm việc ở trường ĐHBKHN” có hai thực thể
thuộc kiểu tên người là “Kiên” và thuộc kiểu tên tổ chức là “trường ĐHBKHN”. Trong câu
này tồn tại một quan hệ làm việc cho (tên người – tên tổ chức) giữa thực thể này.
Bài toán trích rút mối quan hệ giữa các thực thể khác với bài toán trích rút thực thể ở
chỗ trích rút thực thể là bài toán quan tâm đến các chuỗi từ, tức là tìm và phân lớp chuỗi từ
hoặc, nói cách khác, gán nhãn cho các chuỗi từ, trong khi đó bài toán trích rút mối quan hệ
giữa các thực thể lại không gán nhãn cho dãy từ, mà quan tâm đến xác định mối quan hệ
giữa các thực thể.
Trong hơn một thập niên qua đã có nhiều nghiên cứu về trích rút thực thể [17, 25, 28,
58] và trích rút mối quan hệ giữa các thực thể [15, 16, 86, 101, 102]. Phần lớn các nghiên
cứu được chia thành hai hướng: đó là tiếp cận dựa trên học luật thủ công và tiếp cận học
máy. Chẳng hạn, đối với bài toán trích rút thực thể, dữ liệu đầu vào (văn bản thông thường
hoặc hoặc văn bản trên trang web) được tách thành các từ hoặc cụm từ, sau đó dựa vào các
dấu hiệu đặc biệt để xác định các từ hay cụm từ là thực thể. Các dấu hiệu xác định thực thể
có thể được xây dựng một cách thủ công hoặc một cách tự động, dựa trên các kỹ thuật học

máy. Việc xây dựng luật xác định giá trị thuộc tính của thực thể một cách thủ công dựa
trên các đặc điểm của thực thể cần trích rút. Ví dụ, một địa chỉ ở trong tiếng Việt thường
chứa các xâu ký tự như phố, đường, ngách, hẻm,…Vì vậy, các từ khóa này có thể sử dụng
để xác định thông tin về địa chỉ.
Do luật được xây dựng dựa trên việc quan sát dữ liệu nên thường có độ chính xác
cao. Tuy nhiên, cách tiếp cận này không xử lý được các trường hợp chưa được nhắc đến
trong tập luật. Hơn nữa, với các trường dữ liệu không có khuôn dạng nhất định như lĩnh
vực nghiên cứu thì cách tiếp cận này không khả thi. Ở Việt Nam đã có một số công ty xây
dựng hệ thống trích rút thông tin theo cách tiếp cận này. Dữ liệu sau khi trích rút được lưu
trong CSDL và giao diện người dùng là giao diện truy vấn CSDL thông thường.
Trong khi đó, các kĩ thuật học máy thường sử dụng một tập các dữ liệu đã được gán
nhãn cho trước để xây dựng nên một mô hình phục vụ cho mục đích của bài toán (học có


3
giám sát). Đây là cách tiếp cận tự động, cho phép học những luật, xuất hiện trong dữ liệu
huấn luyện, nhưng khó có thể phát hiện được bằng quan sát thủ công của con người. Ban
đầu khi dữ liệu mẫu dùng để học còn ít, cách tiếp cận này có thể cho kết quả không chính
xác như cách tiếp cận dựa trên tập luật được xây dựng thủ công. Tuy nhiên, khi dữ liệu học
nhiều, độ chính xác của hệ thống sẽ tăng. Ngoài ra, hệ thống còn cho phép xử lý được các
loại dữ liệu không có khuôn dạng nhất định.
Một thách thức lớn trong thực tế áp dụng tiếp cận học máy là đòi hỏi tập dữ liệu
được gán nhãn (khi đó ta nói học máy có giám sát) có kích cỡ cực lớn, phục vụ cho việc
huấn luyện mô hình trích rút. Để có được tập dữ liệu huấn luyện lớn, chúng ta thường phải
đầu tư nhiều thời gian và công sức. Đây là điểm thật sự đáng lưu ý đối với tiếng Việt, do
thiếu các tri thức chuyên sâu và các tập dữ liệu huấn luyện cỡ lớn. Bên cạnh tiếp cận thủ
công và tiếp cận học máy có giám sát đã nêu trên, những năm gần đây bắt đầu xuất hiện
một số hệ thống sử dụng cách tiếp cận học máy không giám sát nhằm giải quyết bài toán
trích rút thực thể và quan hệ giữa các thực thể. Lợi thế của các hệ thống học máy không
giám sát là không đòi hỏi dữ liệu huấn luyện, nhưng thường cho một hiệu năng trích rút

không cao, không đáp ứng được các yêu cầu về độ chính xác cần thiết.
Những hạn chế của các cách tiếp cận đã được đề cập ở trên gợi ý cho ta ý tưởng lựa
chọn một giải pháp mềm dẻo hơn cho bài toán trích rút thông tin đó là sử dụng phương
pháp học máy bán giám sát, chỉ đòi hỏi một tập nhỏ dữ liệu huấn luyện để định hướng cho
quá trình trích rút, đồng thời tận dụng các tri thức chuyên sâu sẵn có để khai thác dữ liệu
bán huấn luyện với các văn bản đầu vào chưa gán nhãn nhằm nâng cao hiệu năng trích rút
thực thể và các mối quan hệ giữa chúng của hệ thống.
Đối với hướng tiếp cận học máy, nhiều kỹ thuật đã được áp dụng cho bài toán trích
rút thông tin như mô hình trường ngẫu nhiên có điều kiện (Conditional Random Fields –
CRF) [58, 63], máy vectơ hỗ trợ (Support Vector Machine – SVM) [89, 92], mô hình
markov ẩn (Hidden Markov Model –HMM) [62], mô hình markov entropy cực đại
(Maximum Entropy Markov Model- MEMM) [13], v.v…. Bản chất của trích rút thực thể
là gán nhãn các từ, cụm từ trong văn bản với loại thực thể tương ứng (như tên người, tên tổ
chức). Vì vậy, có thể coi bài toán trích rút thực thể là bài toán phân lớp dữ liệu, tức là phân
lớp mỗi từ thành kiểu thực thể mà nó thuộc vào. SVM là phương pháp phân lớp dữ liệu,
nên được coi là một giải pháp cho bài toán này. Vấn đề khó khăn là việc gán nhãn kiểu
thực thể cho một từ phụ thuộc vào nhãn của các từ xung quanh nó. Ví dụ, từ "phát triển"


4
trong cụm từ "công ty phát triển phần mềm FPT " có từ bên trái và từ bên phải được gán
nhãn là tên tổ chức nên từ "phát triển" cũng được gán nhãn là tên tổ chức. Hạn chế của
SVM là không giải quyết được vấn đề phụ thuộc nhãn giữa các từ. Vì vậy ta cần đến một
mô hình khác có thể giải quyết được vấn đề này, đó là mô hình CRF. CRF có ưu điểm hơn
các phương pháp khác như SVM hay HMM ở chỗ nó có thể giải quyết được vấn đề phụ
thuộc giữa các từ. Ngoài ra nó có ưu điểm hơn phương pháp MEMM ở chỗ có thể giải
được vấn đề sai lệch nhãn. CRF cho phép ta tích hợp nhiều đặc trưng của bản thân từ, cũng
như các từ xung quanh của nó, để làm cơ sở cho việc xây dựng mô hình nên thích hợp hơn
cho bài toán này. SVM phù hợp với bài toán trích rút mối quan hệ giữa các thực thể hơn do
bài toán trích rút mối quan hệ giữa các thực thể không gán nhãn cho chuỗi từ mà chỉ quan

tâm đến xác định mối quan hệ giữa các thực thể, cụ thể là xác định xem một câu có thuộc
mối quan hệ đang xét hay không. Do SVM và CRF đều là các phương pháp học có giám
sát, ta sẽ sử dụng các phương pháp này dưới dạng học bán giám sát, kết hợp với kỹ thuật
khác như kỹ thuật Bootstrapping1, do các tác giả trong [7] đề xuất.
Ở Việt Nam, các nghiên cứu xung quanh lĩnh vực này còn ít và chưa có nhiều kết
quả thực tiễn. Theo luận án được biết, hầu hết các nghiên cứu về trích rút thông tin đều tập
trung vào trích rút thực thể và chỉ có một nghiên cứu liên quan đến trích rút quan hệ [88]
với mục đích xác định mối quan hệ giữa các thực thể trong câu hỏi của hệ thống hỏi đáp.
Ngoài ra, chúng ta chưa có một tập dữ liệu tiếng Việt đã gán nhãn nào được công bố phục
vụ cho bài toán trích rút thông tin. Như trên đã nói, việc xây dựng từ đầu một tập ngữ liệu
đủ lớn cho phương pháp học có giám sát phục vụ bài toán trích rút thông tin mất rất nhiều
thời gian và công sức.
Trên cơ sở các vấn đề còn tồn tại trong trích rút thông tin nói chung và trích rút
thông tin cho tiếng Việt nói riêng như đã trình bày ở trên, luận án muốn tập trung nghiên
cứu các vấn đề sau:
-

Nghiên cứu các phương pháp học bán giám sát để giải quyết vấn đề thiếu tập dữ
liệu tiếng Việt đã gán nhãn,

-

Đề xuất các phương pháp nhằm nâng cao độ chính xác của trích rút thực thể cho
văn bản tiếng Việt,

-

Đề xuất các phương pháp trích rút mối quan hệ giữa các thực thể cho văn bản
tiếng Việt.


1

Khái niệm được định nghĩa ở mục 1.5


5
1.2 Mục tiêu và phạm vi nghiên cứu của luận án
1.2.1

Mục tiêu nghiên cứu

Từ động cơ nghiên cứu nêu trên, luận án đề xuất mở rộng một số phương pháp học máy
bán giám sát cho bài toán trích rút thực thể có tên và trích rút mối quan hệ giữa các thực
thể có tên. Đây là vấn đề cốt lõi và đồng thời là mục tiêu nghiên cứu của luận án.
Theo các tác giả trong [61, 87, 99], học bán giám sát có nhiều phương pháp khác
nhau và cũng đã có một số phương pháp được sử dụng trong trích rút thông tin [18, 28, 58,
22, 47, 100]. Ở đây, luận án đề xuất sử dụng hai phương pháp là phương pháp
Bootstrapping và phương pháp lan truyền nhãn.
Mỗi phương pháp trên đều có ưu điểm và nhược điểm như đã được phân tích trong
Chương 2 và Chương 3. Trên cơ sở việc nghiên cứu các phương pháp này (xem Chương 2
và Chương 3) và những giải pháp đã được công bố trên thế giới [7, 12, 22, 45, 58, 63, 96,
100], luận án đề xuất cách tiếp cận trong việc biểu diễn dữ liệu, các thuộc tính cho quá
trình trích rút thực thể và mối quan hệ giữa các thực thể và phương pháp huấn luyện các hệ
thống đó.
Định hướng đến tính khả thi trong nghiên cứu lý thuyết và thử nghiệm đạt được kết
quả mong muốn, luận án tập trung vào:
(a) Nghiên cứu và phát triển phương pháp trích rút thực thể, dựa trên học bán giám
sát, kết hợp CRF với các luật tìm đồng tham chiếu về tên.
(b) Kết hợp kỹ thuật Bagging2 [12] với phương pháp nghiên cứu ở (a) cho bài toán
trích rút thực thể có tên nhằm nâng cao độ chính xác.

(c) Nghiên cứu và phát triển phương pháp trích rút mối quan hệ giữa các thực thể,
dựa trên học bán giám sát sử dụng kỹ thuật Bagging-Bootstrapping [7, 12].
(d) Nghiên cứu phương pháp đo mức độ tương đồng giữa các từ và các câu áp dụng
cho bài toán trích rút thực thể và trích rút mối quan hệ giữa chúng sử dụng phương pháp
lan truyền nhãn.

2

Khái niệm được định nghĩa ở mục 1.5


6
Phạm vi nghiên cứu

1.2.2

Luận án tập trung vào việc trích rút thực thể và quan hệ giữa chúng từ văn bản phi cấu trúc
thuộc lĩnh vực tin tức. Các tập dữ liệu thử nghiệm được thu thập từ các tờ báo điện tử trực
tuyến. Hệ thống sẽ trích rút từ văn bản phi cấu trúc này các thực thể : tên người, tên tổ
chức, tên địa điểm, chức vụ và từ đó, tìm mối quan hệ giữa các thực thể như : làm việc tại
(tên người-tên tổ chức), sống ở (tên người-tên địa điểm), chức vụ (tên người-chức vụ). Như
đã nói ở trên, hệ thống trích rút thông tin bao gồm năm bước chính là: tiền xử lý, trích rút
thực thể, phát hiện đồng tham chiếu, trích rút mối quan hệ giữa các thực thể và xuất ra theo
khuôn dạng định nghĩa trước. Do phần mềm tiền xử lý trong văn bản tiếng Việt (tách câu,
tách từ, phân tích từ loại) đã đạt được độ chính xác khá cao (> 93%), nên luận án sử dụng
lại các công cụ sẵn có đó và nếu có lỗi thì sẽ sửa lại trực tiếp bằng tay.
Phạm vi nghiên cứu của luận án được thể hiện trong hình 1.1.

Văn bản thô


Tách câu
Tách Từ
Phần tích từ loại
…………

Nhận dạng thực
thể có tên
Nhận dạng mối
quan hệ giữa các
thực thể

Bảng dữ
liệu

Tiền Xử Lý

Hình 1.1.Phạm vi nghiên cứu của luận án

Luận án sẽ tập trung giải quyết các bước sau (xem Hình 1.1):
-

Nhận dạng thực thể, tập trung vào các thực thể đã liệt kê ở trên.

-

Nhận dạng mối quan hệ giữa các thực thể, tập trung vào quan hệ giữa các thực thể
nằm trong cùng một câu. Vì lý do đó, trong bước phân tích đồng tham chiếu luận
án chỉ tập trung vào tìm các đồng tham chiếu về tên, nhằm phục vụ cho bài toán
tìm thực thể có tên và coi như là một phần trong bước nhận dạng thực thể. Các



7
phát hiện đồng tham chiếu chung chung (phục vụ bước nhận dạng mối quan hệ đã
nói ở trên) sẽ bỏ qua.
-

Kết xuất kết quả dưới dạng bảng dữ liệu.

1.3 Đóng góp chính của luận án
Luận án đã đạt được một số đóng góp mới về mặt khoa học như sau:


Với bài toán trích rút thực thể
-

Đề xuất thuật giải kết hợp 11 luật đồng tham chiếu về tên với mô hình CRF
cho quá trình học bán giám sát cho tiếng Việt. 11 Luật đồng tham chiếu về
tên này được áp dụng trong việc phát hiện thêm thực thể để bổ sung dữ liệu
huấn luyện. Các dữ liệu này sẽ được tăng cường vào tập dữ liệu huấn luyện,
phục vụ quá trình huấn luyện hệ thống ở các vòng lặp sau.

-

Đề xuất thuật giải kết hợp sử dụng luật đồng tham chiếu về tên và CRF với
phương pháp Bagging [12] nhằm nâng cao độ chính xác của hệ thống và đồng
thời bổ sung thêm dữ liệu huấn luyện mới.

-

Đề xuất thuật giải lan truyền nhãn [96] cho bài toán trích rút thực thể sử dụng

phương pháp học bán giám sát. Ba đóng góp chính là: (i) đề xuất lựa chọn các
cụm danh từ thành ứng cử viên cho việc nhận dạng thực thể; (ii) đề xuất các
phương pháp đo độ tương tự ngữ nghĩa giữa các từ; (iii) đề xuất phương pháp
giảm ảnh hưởng của các nhãn có tần suất xuất hiện lớn đến quá trình lan
truyền nhãn.



Với bài toán trích rút mối quan hệ giữa các thực thể:
-

Đề xuất thuật giải học có giám sát dựa trên phương pháp hàm hạt nhân mức
nông.

-

Đề xuất thuật giải tích hợp học có giám sát dựa trên phương pháp hàm hạt
nhân mức nông với phương pháp Bagging Bootstrapping [7, 12] cho việc
huấn luyện hệ thống học bán giám sát.

-

Áp dụng và cải tiến thuật giải lan truyền nhãn cho bài toán trích rút mối quan
hệ giữa các thực thể sử dụng phương pháp học bán giám sát. Đề xuất các
phương pháp đo độ tương đồng giữa các câu phục vụ cho thuật toán này.


8
1.4 Cấu trúc của luận án
Luận án được chia thành sáu chương và phụ lục. Chương 1 trình bày mục tiêu, phạm vi,

những đóng góp chính, cấu trúc của luận án.
Chương 2 giới thiệu tổng quan về trích rút thông tin, các nghiên cứu ở trong nước và
ngoài nước về bài toán trích rút thực thể và trích rút mối quan hệ giữa các thực thể và các
phương pháp đánh giá kết quả trích rút.
Chương 3 giới thiệu các phương pháp học máy sử dụng trong luận án bao gồm: CRF,
SVM, LDA và một số phương pháp học bán giám sát.
Chương 4 trình bày phương pháp học máy bán giám sát cho bài toán trích rút thực
thể từ văn bản tiếng Việt. Luận án đề xuất ba phương pháp để giải quyết bài toán này là: (i)
tiếp cận sử dụng CRF kết hợp với các luật đồng tham chiếu về tên; (ii) sử dụng phương
pháp CRF kết hợp với kỹ thuật Bagging-Bootstrapping; (iii) sử dụng phương pháp lan
truyền nhãn. Các thuộc tính được sử dụng trong quá trình huấn luyện cũng được trình bày
trong chương này.
Chương 5 trình bày cách tiếp cận và kết quả của luận án trong bài toán trích rút mối
quan hệ giữa các thực thể. Chương này mô tả kiến trúc hệ thống trích rút mối quan hệ giữa
các thực thể. Luận án đưa ra giải pháp phù hợp với văn bản tiếng Việt, đề xuất các đặc
trưng mới phục vụ cho việc trích rút quan hệ thực thể. Giải pháp học bán giám sát sử dụng
phương pháp Bagging-bootstrpping [7, 12] và phương pháp ngôn ngữ mức nông cũng
được đưa ra. Một kết quả khác của luận án là kỹ thuật lan truyền nhãn sử dụng độ tương
đồng giữa các câu, cũng được trình bày ở trong chương này.
Chương 6 tổng kết lại các kết quả đạt được của luận án và đề xuất các hướng nghiên
cứu trong tương lai có liên quan đến luận án.

1.5 Các thuật ngữ được sử dụng trong luận án
-

Phân lớp thực thể: bài toán trích rút thực thể có thể coi là bài toán tìm và phân
lớp các từ hoặc cụm từ cho trước thành các lớp như tên người, tên tổ chức,…Vì
vậy, trong luận án khi đề cập đến phân lớp thực thể có thể hiểu là trích rút thực thể.

-


Phân lớp quan hệ: bài toán trích rút mối quan hệ giữa các thực thể có thể coi là
bài toán tìm và phân lớp các câu thành lớp quan hệ như sống ở, làm việc cho. Vì


9
vậy, trong luận án khi đề cập đến phân lớp quan hệ có thể hiểu là trích rút mối
quan hệ giữa các thực thể.
-

Bộ phân lớp hoặc mô hình phân lớp hoặc mô hình trích rút: chỉ tới mô hình
hoặc hệ thống nhận được trong quá trình huấn luyện.

-

Tập dữ liệu huấn luyện: chỉ tới các dữ liệu đã gán nhãn.

-

Bagging: là phương pháp tạo thêm một số mẫu từ một mẫu ban đầu, sau đó sử
dụng các mẫu này để huấn luyện các mô hình phân lớp. Sử dụng các mô hình
phân lớp vừa học được để phân lớp mẫu mới nhằm để tìm mẫu tốt nhất, dựa trên
việc tính trung bình kết quả của các mô hình phân lớp.

-

Bootstrapping (Tự nâng): là phương pháp huấn luyện hệ thống cải tiến dần, bằng

cách học lặp đi lặp lại trên tập dữ liệu gán nhãn và chưa gán nhãn.



10

CHƯƠNG 2
CÁC NGHIÊN CỨU LIÊN QUAN

Trong chương này, luận án sẽ trình bày các kiến thức cơ bản về trích rút thông tin và các
nghiên cứu trong nước và ngoài nước về trích rút thông tin, bao gồm: các định nghĩa trích
rút thông tin, trích rút thực thể, trích rút mối quan hệ giữa các thực thể, các phương pháp
đánh giá chất lượng hệ thống và các cách tiếp cận đã được đề xuất nhằm giải quyết bài
toán trong các tài liệu chuyên môn trong nước và ngoài nước.

2.1 Bài toán trích rút thông tin
Có nhiều định nghĩa về trích rút thông tin. Trên cơ sở nghiên cứu các nghiên cứu liên quan
[14, 23, 24, 86], có thể định nghĩa trích rút thông tin như sau :
Định nghĩa 2.1: Trích rút thông tin (Information Extraction - IE) là việc nhận biết các
đoạn văn bản ứng với các lớp thực thể và mối quan hệ giữa các thực thể từ dữ liệu dạng
văn bản và chuyển chúng sang dạng biểu diễn có cấu trúc (ví dụ, cơ sở dữ liệu).
Việc trích rút ra các thông tin có cấu trúc từ dữ liệu phi cấu trúc là một công việc rất
khó khăn, thu hút được sự quan tâm của cộng đồng các nhà nghiên cứu trong hai thập kỉ
qua. Bắt nguồn từ cộng đồng các nhà xử lý ngôn ngữ tự nhiên, IE đã nhanh chóng được
quan tâm chú ý bởi những cộng đồng nghiên cứu khác nhau về học máy, truy vấn thông
tin, cơ sở dữ liệu, Web và phân tích văn bản. Hai hội nghị quan trọng về các nghiên cứu về
trích rút thông tin là: Message Understanding Conference (MUC) [25, 44, 46, 103, 104] và
Automatic Content Extraction (ACE) [6, 75].
Có nhiều mức độ trích rút thông tin từ văn bản như: trích rút thực thể (Named Entity
Recognition – NER), trích rút quan hệ giữa các thực thể (Relation Extraction - RE), phân
giải đồng tham chiếu (Co-Reference Resolution)…Các kĩ thuật được sử dụng trong trích
rút thông tin gồm có: phân đoạn, phân lớp, kết hợp và phân cụm.
IE có nhiều ứng dụng rộng rãi và hữu ích. Trên thế giới, IE được ứng dụng khá nhiều

vào việc trích rút thông tin trên Internet. Các ứng dụng thực tế bao gồm: lấy thông tin về
tên của các công ty, tên người điều hành công ty, theo dõi thông tin về các dịch bệnh, theo
dõi các sự kiện khủng bố… IE còn được ứng dụng vào việc chăm sóc khách hàng, đó là
việc tìm kiếm và trích rút ra các thông tin của khách hàng như: họ tên, địa chỉ, email, số
điện thoại rồi lưu vào cơ sở dữ liệu (CSDL) hay phục vụ các hệ thống quản lý thông tin cá


11
nhân. Gần đây IE đặc biệt được chú trọng trong lĩnh vực y học. Đã có khá nhiều nghiên
cứu được tiến hành nhằm ứng dụng IE vào việc trích rút các thực thể trong y học như tên
các protein và gene.
Theo MUC [31, 44, 47, 103, 104], hệ thống trích rút thông tin có các thao tác chính
như sau:
Hệ thống trích rút thông tin
Văn bản đầu vào
Tiền xử lý
Trích rút thực thể
Giải quyết đồng tham chiếu
Xây dựng mẫu phần tử
Xây dựng mẫu quan hệ

Trích rút quan hệ

Đưa ra mẫu kịch bản
Mẫu trích rút

Hình 2.1. Các thao tác chính của bài toán trích rút thông tin

Như đã trình bày ở trên, mục tiêu của luận án là bài toán trích rút thực thể và trích
rút mối quan hệ giữa các thực thể. Các bài toán đó sẽ được phân tích kỹ hơn ở phần sau.

Phần 2.2 trình bày khái niệm về trích rút thực thể, các nghiên cứu liên quan về trích rút
thực thể và các đặc trưng hay được sử dụng trong trích rút thực thể. Phần 2.3 trình bày khái
niệm về trích rút mối quan hệ các thực thể, các nghiên cứu liên quan về trích rút mối quan
hệ giữa các thực thể và các đặc trưng được sử dụng để giải quyết vấn đề này. Phần 2.4
trình bày các phương pháp đánh giá hiệu quả của các hệ thống trích rút. Cuối cùng, Phần
2.5 sẽ tóm lược những vấn đề đã trình bày trong chương này.


12
2.2 Bài toán trích rút thực thể
Định nghĩa 2.2: Trích rút thực thể (Entity Extraction), còn được gọi là nhận dạng thực
thể có tên (Named Entity Regconition-NER) hoặc xác định thực thể (Entity Identification),
là việc xác định các từ, cụm từ trong văn bản đóng vai trò là thực thể thuộc một lớp định
nghĩa trước. Khái niệm này thường được nhắc đến trong các bài báo tiếng Anh với tên viết
tắt là NER. Vì vậy sau này luận án gọi bài toán trích rút thực thể là bài toán NER.
Có thể coi trích rút thực thể là việc tìm kiếm và phân lớp các từ (cụm từ) trong văn
bản vào các nhóm thực thể như tên người (person), tên địa điểm (location), tên tổ chức
(organization), ngày tháng (date), thời gian (time), tỷ lệ (percentage), tiền tệ (monetary)…
Hiện nay, trích rút thực thể được mở rộng sang nhiều lớp khác như tên protein, chủ đề bài
báo, tên tạp chí,… Hội thảo MUC-6 [44] đã phân bài toán NER thành ba loại: trích rút tên
các thực thể bao gồm: tên người, tên tổ chức, tên địa điểm, nhận dạng các biểu thức thời
gian như “9-2-2000”, “09/02/2000”, ”10h:20’” và trích rút các biểu thức số, như “45%”,
“15m”, “25kg”,…Dưới đây là văn bản ví dụ được trích từ [86], được gán nhãn theo 3 loại
thực thể là: Per (tên người), Loc (tên địa điểm), Org (tên tổ chức).
Ví dụ 2.1:
According to <Per>Robert Callahan</Per>, president of <Org> Eastern’s
</Org>

light attendants union, the past practice of <Org> Eastern’s</Org>


parent, <Loc> Houston </Loc>-based <Org> Texas Air Corp.</Org>, has
involved ultimatums to unions to accept the carrier’s terms.
NER là bước cơ bản và quan trọng trước khi giải quyết các bài toán phức tạp hơn.
Rõ ràng là trước khi nhận dạng được các quan hệ giữa các thực thể ta phải xác định được
đâu là các thực thể tham gia vào mối quan hệ đó. Ban đầu, NER được xem là một thao tác
đơn giản trong IE. Nhưng hiện nay, NER có một vai trò quan trọng quyết định đến các bài
toán khác có độ phức tạp cao hơn như truy vấn thông tin (Information Retrieval-IR) hay
các hệ hỏi đáp (Question Answering Systems - QA).
Các phương pháp được đề xuất để giải quyết cho bài toán trích rút thực thể được chia
thành hai nhóm: nhóm các phương pháp dựa trên tri thức [2, 29, 35, 74, 77] và nhóm các
phương pháp dựa trên kỹ thuật học máy [17, 18, 90, 91]. Các hệ thống dựa trên tri thức chủ
yếu dựa trên tập luật được xây dựng một cách thủ công, sử dụng các ngôn ngữ đặc thù như
văn phạm JAPE [29, 30, 35]. Ý tưởng của kỹ thuật học máy là học các đặc trưng (sử dụng
để mô tả thuộc tính của từ ) của mẫu dương (lớp tương ứng với các nhãn quan tâm chẳng


13
hạn như tên người, tên địa điểm) và mẫu âm (lớp không tương ứng với nhãn quan tâm, qui
ước là nhãn O) từ tài liệu đã được gán nhãn. Trong luận án sẽ tập trung vào nhóm các kỹ
thuật học máy.
2.2.1

Các đặc trưng được sử dụng trong bài toán NER

Sau đây là các đặc trưng hay được sử dụng trong bài toán NER:
Từ loại: mỗi từ được gán một nhãn, xác định kiểu từ loại của từ đó trong câu dựa trên sử
dụng từ điển các nhãn đã được định nghĩa sẵn. Thông thường, từ điển từ loại có các nhãn
sau: Danh từ, Động từ, Tính từ, Mạo từ, Đại từ, Giới từ, Phó từ, Trạng từ, Liên từ.
Định dạng từ: liên quan đến đặc điểm cấu tạo của từ, như là chữ viết hoa, là số.
Bảng 2.1. Định dạng từ (Othorgraphic)


Các đặc trưng
Case

Ví dụ
-

Bắt đầu bằng chữ viết hoa

-

Toàn bộ các chữ trong từ là chữ viết hoa

-

Bao gồm các chữ viết hoa và chữ thường (ví
dụ, ProSys, eBay)

Punctuation

-

Kết thúc bằng dấu chấm, có dấu chấm bên
trong (ví dụ: St.,I.B.M)

Digit

-

Dạng thức ngày tháng ( 23/5/2004)


-

Bao gồm cả chữ cái, lẫn chữ số (ví dụ:
W3C,..)

Morphology

-

Tiền tố, hậu tố

-

Từ kết thúc bằng một cụm chữ chung (ví dụ:
Các từ kết thúc bằng chữ ish trong tiếng Anh
là Spanish, Danish,…)

Token

-

Từ (Ví dụ: Nguyễn Văn Nam,..)

Đặc trưng từ điển: trong tiếng Anh, đặc trưng này còn được gọi là “gazetteer”, ”lexicon”,
“dictionary” và gọi chung là danh sách.
Bảng 2.2. Đặc trưng từ điển

Các đặc trưng
Danh sách chung


Ví dụ
-

Danh sách từ đệm, hư từ (stop word)


14
-

Danh sách chữ viết hoa, ngày tháng (ví dụ
trong tiếng Anh: January, March, …)

Danh sách các thực thể

Danh sách từ gợi ý về thực thể

2.2.2

-

Danh sách chữ viết tắt

-

Tên tổ chức: government, airline, ..

-

Họ, tên đệm, tên


-

Tên địa điểm: Hà Nội, Việt Nam,…

-

Từ viết tắt chung cho một loại tổ chức ( Inc.,..)

-

Từ viết cùng với tên người như: Mr, Ms,..

Tình hình nghiên cứu ngoài nước về bài toán NER sử dụng học máy

Phần lớn các nghiên cứu về NER hiện nay đều sử dụng các cách tiếp cận dựa trên học máy,
bao gồm học có giám sát, học không giám sát và học bán giám sát. Trong phần này, luận
án sẽ giới thiệu và phân tích ưu nhược điểm của từng cách tiếp cận.
Học có giám sát
Ý tưởng của học có giám sát như sau: Cho tập các đối tượng và nhãn của chúng, xác
định qui luật gán nhãn của dữ liệu. Trên cơ sở đó, cho một đối tượng mới, hệ thống có thể
gán nhãn cho đối tượng này dựa trên qui luật gán nhãn vừa học được.
Hiện nay, phần lớn các công trình giải quyết bài toán trích rút thực thể thường sử
dụng các kỹ thuật học máy có giám sát như mô hình Markov ẩn [17, 62], cây quyết định,
mô hình Maximum entropy [13, 55], máy vectơ hỗ trợ (SVM) [66, 92], mô hình trường
ngẫu nhiên có điều kiện CRF [11, 60, 63, 82].
Phương pháp học có giám sát cho kết quả chính xác, nhưng đòi hỏi một tập dữ liệu
huấn luyện được gán nhãn có kích cỡ lớn. Hiệu quả trích rút của hệ thống phụ thuộc nhiều
vào việc tập dữ liệu huấn luyện đủ lớn để bao quát được các hiện tượng phức tạp trong
ngôn ngữ. Thông thường, để xây dựng được những tập dữ liệu huấn luyện lớn như vậy, đòi

hỏi tồn nhiều thời gian, công sức cũng như đòi hỏi phải có các kiến thức chuyên sâu có liên
quan. Bên cạnh đó, việc gán nhãn bằng tay cho các dữ liệu tương đối buồn tẻ, có thể xảy ra
những sai lầm ngoài ý muốn, do sự mất tập trung của các chuyên gia gán nhãn. Những khó
khăn kể trên làm cho các tập dữ liệu huấn luyện được gán nhãn đảm bảo chất lượng tương
đối khan hiếm. Mặt khác, các kho dữ liệu chưa gán nhãn ngày càng xuất hiện nhiều và
chưa được khai thác một cách tương xứng. Thực tế này đòi hỏi phải tìm cách giảm yêu cầu