ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
---------------------

TRẦN LIÊN THẮNG

DỊCH CÂU TRUY VẤN BẰNG NGÔN NGỮ TỰ
NHIÊN SANG ĐỒ THỊ Ý NIỆM
Chuyên ngành: Khoa học máy tính
Mã số ngành: 604801

LUẬN VĂN THẠC SĨ

TP. Hồ Chí Minh, tháng 07 năm 2007


LỜI CẢM ƠN
Trước tiên, tôi xin chân thành cảm ơn thầy Cao Hồng Trụ đã nhiệt tình hướng dẫn và định
hướng để tơi hồn thành luận văn này.
Xin chân thành cảm ơn giám đốc công ty phát triển phầm mềm Trần Nguyễn đã tạo mọi
điều kiện thuận lợi nhất để tơi có thời gian nghiên cứu hồn thành luận văn này.
Xin chân thành biết ơn sự tận tình dạy dỗ của tất cả các quý thầy cô tại trường Đại học
Bách Khoa, đặc biệt là các thầy cô trong khoa công nghệ thông tin. Tất cả các kiến thức
mà nhà trường và quý thầy cô đã truyền đạt là hành trang to lớn để tôi mang theo trên con
đường học tập, làm việc và nghiên cứu.


TÓM TẮT
Xuất phát từ nhu cầu khai thác một cách có hiệu quả nguồn thơng tin khổng lồ trên internet
đã thúc đẩy sự ra đời các của các ứng dụng rút trích thơng tin tự động và web có ngữ
nghĩa. Đồng thời, nhiều nhà nghiên cứu cũng đã nghiên cứu các kỹ thuật để biểu diễn một

cách có hiệu quả nguồn thông tin khổng lồ trên internet, nhằm giúp cho máy tính có thể xử
lý nguồn dữ liệu này một cách hiệu quả, một trong số các phương pháp này có đồ thị ý
niệm.
Đồ thị ý niệm biểu diễn tri thức dưới dạng quan hệ giữa các khái niệm. Trong câu truy vấn,
quan hệ giữa các khái niệm sẽ giúp xác định đối tượng cần tìm kiếm. Do đó đã có nhiều
cơng trình nghiên cứu về vấn đề chuyển đổi câu sang đồ thị ý niệm. Tuy nhiên các cơng
trình mà các tác giả nghiên cứu chủ yếu tập trung vào chuyển đổi câu văn bản thô sang đồ
thị ý niệm. Mục tiêu của luận văn này cũng là nghiên cứu vấn đề chuyển đổi câu truy vấn
sang đồ thị ý niệm, nhằm tạo ra đồ thị ý niệm giúp cho q trình tìm kiếm thơng tin.
Trong đề tài này, chúng tơi nghiên cứu q trình chuyển đổi câu truy vấn sang đồ thị ý
niệm dùng phương pháp kết hợp giữa xây dựng tập luật và áp dụng phương pháp học máy
để giải quyết nhập nhằng. Trong quá trình xây dựng tập luật, chúng tơi cố gắng phân tích
các trường hợp riêng nhằm để xây dựng được một tập luật tổng quát. Trong phương pháp
giải quyết nhập nhằng bằng học máy, chúng tôi đề ra phương pháp ứng dụng mạng Bayes
để giải quyết nhập nhằng.


MỤC LỤC
DANH MỤC HÌNH ............................................................................................................vi
DANH MỤC BẢNG..........................................................................................................viii
DANH MỤC BẢNG..........................................................................................................viii
CHƯƠNG 1 GIỚI THIỆU.................................................................................................5
U

1.1

Tổng quan ..........................................................................................................5

1.2


Mục tiêu và phạm vi ..........................................................................................6

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

Sơ lược về đồ thị ý niệm....................................................................................8

2.2

Một số phương pháp nhận diện thực thể có tên.................................................9

2.3

Một số phương pháp rút trích quan hệ.............................................................10

2.4

GATE...............................................................................................................12

2.5

KIM..................................................................................................................16

2.6

ANTLR ............................................................................................................17

2.7

JavaBayes.........................................................................................................20


CHƯƠNG 3 PHƯƠNG PHÁP ĐỀ NGHỊ ......................................................................23
3.1

Tổng quan ........................................................................................................23

3.2

Phương pháp nhận biết thực thể và từ quan hệ................................................24

3.3

Xây dựng văn phạm câu truy vấn ....................................................................26

3.4

Phương pháp phân rã câu truy vấn ..................................................................27

3.5

Phương pháp xây dựng tập luật .......................................................................30

3.6

Phương pháp chuyển đổi câu truy vấn có cấu trúc song song .........................39

3.7

Phương pháp giải quyết nhập nhằng bằng học máy ........................................39


CHƯƠNG 4 HIỆN THỰC, THỬ NGHIỆM VÀ ĐÁNH GIÁ......................................46


4.1

Kỹ thuật hiện thực các q trình chính của hệ thống.......................................46

4.2

Giao diện các lớp chính trong hệ thống ...........................................................48

4.3

Các tiêu chuẩn đánh giá ...................................................................................52

4.4

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

CHƯƠNG 5 KẾT LUẬN .................................................................................................54
TÀI LIỆU THAM KHẢO.................................................................................................55
PHỤ LỤC A Văn phạm của câu truy vấn ......................................................................60
PHỤ LỤC B Tập luật chuyển đổi câu truy vấn ............................................................61
PHỤ LỤC C Tập câu truy vấn mẫu...............................................................................69


DANH MỤC HÌNH
Hình 2.1

Ví dụ về đồ thị ý niệm .......................................................................................8


Hình 2.2

Đồ thị ý niệm mẫu trong luận văn .....................................................................9

Hình 2.3

Q trình xử lý trong ANNIE ..........................................................................14

Hình 2.4

Ví dụ một tập tin danh sách của Gazetteer ......................................................15

Hình 2.5

Ví dụ một tập tin chỉ mục ................................................................................15

Hình 2.6

Q trình chú thích ngữ nghĩa trong KIM .......................................................17

Hình 2.7

Ví dụ về khái báo phần options trong chương trình ANTLR ..........................18

Hình 2.8

Khn mẫu của một chương trình ANTLR.....................................................19

Hình 2.9


Ví dụ phần khái báo tokens trong chương trình ANTLR ................................20

Hình 2.10

Cú pháp tổng quá của một luật trong chương trình ANTLR...........................20

Hình 2.11

Ví dụ luật nhận biết số ngun trong chương trình ANTLR...........................20

Hình 2.12

Ví dụ định nghĩa đối tượng DiscreteVariable..................................................22

Hình 2.13

Ví dụ định nghĩa đối tượng DiscreteFunction .................................................22

Hình 2.14

Ví dụ q trình tính tốn xác suất phân bổ bằng Ebayes.................................22

Hình 3.1

Mơ hình giải quyết bài tốn .............................................................................24

Hình 3.2

Ví dụ định nghĩa tập tin chỉ mục trong Gazetteer............................................26


Hình 3.3

Kết quả đồ thị mong muốn ..............................................................................28

Hình 3.4

Đồ thị ý niệm câu “company located in Yonkers, USA” ................................29

Hình 3.5

Đồ thị ý niệm câu “person is CEO of Zygo Corporation”...............................29

Hình 3.6

Đồ thị ý niệm câu “person is CEO of Zygo Corporation in USA”..................30

Hình 3.7

Cấu trúc tập phần tử TransformRules và rule.................................................33

Hình 3.8

Cấu trúc của phần tử điều kiện luật .................................................................34

Hình 3.9

Ví dụ về phần tử premise.................................................................................35

Hình 3.10


Cấu trúc của phần tử hành động ......................................................................35

Hình 3.11

Ví dụ một luật hồn chỉnh................................................................................37

Hình 3.12

Ví dụ một luật đặc biệt.....................................................................................37

Hình 3.13

Cấu trúc từ điền quan hệ ..................................................................................38

Hình 3.14

Ví dụ một số phần tử trong từ điển ..................................................................38

Hình 3.15

Mơ hình mạng Bayes cho quan hệ born_in .....................................................42

Hình 3.16

Mơ hình mạng Bayes cho quan hệ live_in.......................................................43

Hình 3.17

Mơ hình mạng Bayes cho quan hệ work_in ....................................................44


Hình 3.18

Mơ hình mạng Bayes tổng hợp ba quan hệ......................................................44


Hình 4.1

Quá trình nhận biết thực thể và quan hệ ..........................................................46

Hình 4.2

Quá trình phân rã câu truy vấn.........................................................................47

Hình 4.3

Quá trình nhận biết quan hệ.............................................................................47

Hình 4.4

Quá trình chuyển đổi sang đồ thị ý niệm dạng đồ họa ....................................48


DANH MỤC BẢNG
Bảng 3.1

Bảng thuộc tính phần tử premise .....................................................................34

Bảng 3.2


Mơ tả các thuộc tính của phần tử entry............................................................38

Bảng 3.3

Kết quả đo đạc các phần tử cha của born_in ...................................................42

Bảng 3.4

Kết quả đo đạc quan hệ born_in ......................................................................42

Bảng 3.5

Kết quả đo đạc các phần tử cha của live_in.....................................................43

Bảng 3.6

Kết quả đo đạc quan hệ live_in........................................................................43

Bảng 3.7

Kết quả đo đạc các phần tử cha của work_in ..................................................44

Bảng 3.8

Kết quả đo đạc xác suất các phần tử cha trong mạng tổng hợp.......................45

Bảng 3.9

Kết quả đo đạc quan hệ work_in .....................................................................45


Bảng 4.1

Giao diện lớp KIMNER...................................................................................48

Bảng 4.2

Giao diện lớp AnnieER....................................................................................49

Bảng 4.3

Giao diện lớp GrammarChecking....................................................................49

Bảng 4.4

Giao diện lớp ProcessingQuery .......................................................................50

Bảng 4.5

Giao diện lớp QueryTriple...............................................................................51

Bảng 4.6

Giao diện lớp MLRelationExtraction ..............................................................51

Bảng 4.7

Giao diện lớp QueryOutput .............................................................................52

Bảng 4.8


Bảng đánh giá kết quả chương trình học máy .................................................53


Chương 1: Giới thiệu

5

CHƯƠNG 1
GIỚI THIỆU
1.1 Tổng quan
Web có ngữ nghĩa là Web mà trong đó có sự bổ sung thêm các ngữ nghĩa hình thức (siêu
dữ liệu, tri thức) vào nội dung các trang Web ([4]). Như vậy, nó là sự mở rộng của mơ hình
Web truyền thống trước đây vốn được biểu diễn dưới dạng văn bản thô mà chỉ có con
người mới đọc hiểu được. Mục đích của Web có ngữ nghĩa là cho phép quản lý và truy cập
thông tin một cách dễ dàng và hiệu quả hơn bằng cách giúp cho máy tính cũng có thể đọc
hiểu thơng tin trên Web. Nhờ đó nó có thể khai thác thông tin một cách dễ dàng hơn và trợ
giúp quy trình tự động hóa cơng việc.
Tổ chức W3C đã nghiên cứu các chuẩn và kỹ thuật để cho phép dữ liệu trên Web được
định nghĩa và liên kết theo cách mà nó có thể được sử dụng một cách tự động, hợp nhất,
và hiệu quả hơn, đồng thời có thể dùng lại trong nhiều ứng dụng. Web sẽ đạt được các tiềm
năng của nó, khi nó trở thành mơi trường mà ở đó dữ liệu có thể được chia sẻ và xử lý
bằng các công cụ tự động cũng như con người. Nhiều cộng động các nhà nghiên cứu đã
đóng góp các nghiên cứu của họ nhằm đạt được tham vọng trên. Trong đó các nhà nghiên
cứu trong lĩnh vực biểu diễn tri thức đã nhận ra được vai trò quan trọng của các phương
pháp biểu diễn hình thức, một trong số các phương pháp có phương pháp dùng đồ thị ý
niệm (Conceptual Graph - CG) ([32]). Do đó nhiều cơng trình nghiên cứu liên quan đến đồ
thị ý niệm đã ra đời.
Cộng đồng các nhà nghiên cứu đồ thị ý niệm đã nghiên cứu các hướng khác nhau trong
việc ứng dụng đồ thị ý niệm vào trong Web có ngữ nghĩa. Một số nhà nghiên cứu đã chọn
đồ thị ý niệm cho việc biểu diễn hình thức các ontology và chú thích ngữ nghĩa cho Web

có ngữ nghĩa như WebKB ([23]). Một số khác thì dựa trên sự tương đồng giữa đồ thị ý
niệm và RDF(S) – ngôn ngữ được W3C đề xuất cho việc mô tả tài nguyên trên Web. Đồ
thị ý niệm đóng vai trị như một ngơn ngữ trung gian để chuyển đổi giữa ngôn ngữ tự nhiên


Chương 1: Giới thiệu

6

và những mơ hình xử lý hướng máy tính. Như vậy để tạo ra mơ hình tổng qt trong biểu
diễn tri thức mà máy tính có thể dễ dàng hiểu được thì ta cần xây dựng đồ thị ý niệm. Mục
tiêu của đề tài này là nghiên cứu cách chuyển câu truy vấn bằng ngôn tự nhiên sang đồ thị
ý niệm. Đồ thị ý niệm biểu diễn tri thức dưới dạng quan hệ giữa các ỳ niệm, trong câu truy
vấn quan hệ giữa các ý niệm góp phần xác định đối tượng cần tìm kiếm.
Việc chuyển đổi câu từ ngôn ngữ tự nhiên sang đồ thị ý niệm cũng đã được nghiên cứu
theo nhiều hướng khác nhau. Tác giả hệ thống [44] thì để ra phương pháp phân tích câu
bằng văn phạm liên kết (link grammar) và áp dụng học máy để ánh xạ văn phạm thành đồ
thị ý niệm. Hệ thống [3] thì đề ra phương pháp ánh xạ cây cú pháp thành đồ thị ý niệm cú
pháp (syntactic conceptual graph), sau đó đồ thị ý niệm cú pháp sẽ được chuyển thành đồ
thị ý niệm thực (real conceptual graph), phương pháp được áp dụng chủ yếu là dựa vào
luật ánh xạ. Hệ thống [17] thì dựa vào VerbNet và WordNet để xác định vai trò ngữ nghĩa
(semantic roles) của động từ trong câu và dùng vào đó để xây dựng đồ thị ý niệm. Các
phương pháp mà các nhà nghiên cứu trên đề xuất chủ yếu là chuyển đổi câu dạng văn bản
thô sang đồ thị ý niệm không phải là chuyển đổi câu truy vấn sang đồ thị ý niệm. Mục tiêu
của luận văn này là sẽ nghiên cứu phương pháp chuyển câu truy vấn sang đồ thị ý niệm.
Chúng tôi sẽ không nhận biết các khái niệm bằng cách dùng phương pháp phân tích văn
phạm hay cú pháp của câu như các tác giả trên đã dùng, mà thay vào đó chúng tơi sẽ dùng
phương pháp nhận biết thực thể có tên, và q trình nhận biết quan hệ chính là q trình
xác định mối quan hệ ngữ nghĩa giữa các thực thể có tên này. Như vậy chúng tơi sẽ tập
trung vào hai cơng việc chính đó là: nhận biết thực thể có tên trong câu truy vấn và nhận

biết mối quan hệ ngữ nghĩa giữa các thực thể có tên đó.

1.2 Mục tiêu và phạm vi
Mục tiêu của đề tài là chuyển đổi câu truy vấn sang đồ thị ý niệm. Đồ thị ý niệm sinh ra
được dùng cho quá trình tìm kiếm trong Web có ngữ nghĩa. u cầu đề tài là chuyển đổi
được những câu truy vấn đơn giản và những câu truy vấn phức tạp có cấu trúc song song
và đề ra được giải pháp giải quyết nhập nhằng cho câu truy vấn.
Đề tài được giới hạn trong phạm vi những câu truy vấn bằng tiếng Anh trên miền ontology
của KIM. Tập các quan hệ ngữ nghĩa cũng là tập các quan hệ trong ontology của KIM, và
có mở rộng thêm ba quan hệ mới born_in, work_in, live_in nhằm minh họa quá trình giải


Chương 1: Giới thiệu

7

quyết nhập nhằng bằng học máy cho giới từ “in” trong quan hệ giữa con người và nơi chốn
(person – in – location). Trong đề tài này, tơi chủ yếu tập trung vào vấn đề tìm quan hệ
giữa các thực thể có tên, cịn q trình nhận biết thực thể có tên sẽ module trong KIM đảm
nhận, do đó tơi sẽ khơng giải quyết những khuyết điểm do module nhận diện thực thể trong
KIM gây ra. Hệ thống không xử lý các dạng câu truy vấn dạng hỏi đáp (WH-question), để
có thể đưa chúng vào hệ thống ta cần phải chuyển đổi trước các câu truy vấn này thành các
dạng câu thích hợp với hệ thống.


Chương 2: Các nghiên cứu liên quan

8

CHƯƠNG 2

CÁC NGHIÊN CỨU LIÊN QUAN
2.1 Sơ lược về đồ thị ý niệm
Đồ thị ý niệm (conceptual graph) là một dạng biểu diễn tri thức do John F. Sowa đưa ra
vào năm 1976. Trong bài báo đầu tiên [31] công bố liên quan tới đồ thị ý niệm, Sowa đã
định nghĩa đồ thị ý niệm như sau:
Đồ thị ý niệm là một đồ thị hữu hạn, liên thơng, khơng có hướng, lưỡng phân với
những nút thuộc một loại được gọi là ý niệm (hoặc khái niệm - concepts) và những
nút thuộc loại còn lại được gọi là quan hệ ý niệm (conceptual relations). Một đồ thị
ý niệm có thể chứa duy nhất một khái niệm, nhưng nó khơng thể có những quan hệ ý
niệm khơng được liên kết.
Đồ thị ý niệm có khả năng diễn đạt ngữ nghĩa một cách chính xác, dễ hiểu đối với con
người và khả năng xử lý đối với máy tính. Chính vì vậy, nó thường được dùng như một
ngôn ngữ trung gian để chuyển đổi giữa ngôn ngữ tự nhiên và những mơ hình xử lý hướng
máy tính. Hình 2.1 là một ví dụ về đồ thị ý niêm.

Nam

chủ thể

đi

khách thể

Trường

Hình 2.1 Ví dụ về đồ thị ý niệm
Đồ thị ý niệm trên biểu diễn cho câu “Nam đi đến trường”, hành động “đi” có hai liên kết,
một chủ thể của hành động và một cho khách thể của hành động.
Trong luận văn này đồ thị ý niệm đã được bổ sung thêm một số thuộc tính như sau:
•


Tất cả các khái niệm và quan hệ đều phải thuộc một miền xác định trước. Miền
xác định này chính là ontology của toàn bộ hệ thống KIM.


Chương 2: Các nghiên cứu liên quan
•

9

Mỗi khái niệm được xác định bởi hai yếu tố: lớp và định danh. Mỗi khái niệm
đều thuộc một lớp nhất định trong ontology, nhưng có thể có hoặc khơng có định
danh. Trong trường hợp này, định danh có giá trị là “?” hoặc “*”

•

Một đồ thị ý niệm là hợp lệ nếu tất cả các quan hệ đều thỏa mãn các ràng buộc về
miền của chủ thể và khách thể. Chiều từ chủ thể đến khách thể sẽ được biểu diễn
bằng các đường liên kết có hướng

Hình 2.2 là một ví dụ đồ thị ý niệm sẽ được sinh ra cho câu truy vấn “tìm thủ đơ của Việt
Nam”.
Capital: ?

hasCapital

Country: VietNam

Hình 2.2 Đồ thị ý niệm mẫu trong luận văn
Đồ thị ý niệm trên có hai khái niệm và một quan hệ. Chiều của mũi tên biểu diễn chiều đi

từ chủ thể đến khách thể. Trong ví dụ này, chủ thể có nhãn là “Country: VietNam”, cịn
khách thể có nhãn là “Capital: ?”. Khái niệm “Country: VietNam” cho biết, khái niệm này
thuộc lớp “Country” và có một định danh. Do định danh thường dài và không gợi nhớ nên
hệ thống đã chọn tên của đối tượng ứng với định danh đó làm nhãn cho khái niệm. Trong
trường hợp này, tên được chọn làm nhãn là “VietNam”. Còn khái niệm “Capital: ?” cho
biết, khái niệm này thuộc lớp “Capital” nhưng khơng có định danh. Dấu chấm hỏi cho biết
đây là khái niệm được truy vấn. Trong trường hợp ta không quan tâm đến kết quả truy vấn
của đối tượng đó, dấu “?” sẽ được thay bằng dấu “*”.

2.2 Một số phương pháp nhận diện thực thể có tên
Thực thể có tên là một từ, hay một chuỗi các từ mà có thể được phân loại như tên người, tổ
chức, nơi chốn, ngày tháng, thời gian hay số lượng, v.v…([16]). Thực thể có tên có nhiều
ứng dụng đặc biệt là trong các ứng dụng xử lý ngơn ngữ tự nhiên. Chẳng hạn, trong hệ
thống tóm tắt văn bản tự động có thể nâng cao chất lượng bằng cách dùng thực thể có tên
như là dấu hiệu nhận biết các đoạn văn trong văn bản. Một số khác thì dùng phương pháp
đánh tag thực thể có tên (NE Tagger) để truy hồi thơng tin, rút trích thông tin, nhận biết
văn bản tự động, xây dựng hệ thống hỏi đáp hay dịch máy.


Chương 2: Các nghiên cứu liên quan

10

Trong các hệ thống rút trích thơng tin thì nhận biết hay phân loại chính xác thực thể có tên
là rất quan trọng vì nó có thể giúp chúng ta rút trích chính xác thơng tin mong muốn. Nhận
biết thực thể có tên là q trình tìm kiếm, định vị trí và phân loại các phần tử nguyên tố
trong văn bản thành các lớp đã được định nghĩa trước như con người, tổ chức, nơi chốn,
thời gian, giá trị tiền tệ, v.v...
Các hệ thống nhận biết thực thể có tên đã được xây dựng dùng các kỹ thuật khác nhau như
áp dụng văn phạm hay mơ hình thống kê. Các hệ thống dùng luật văn phạm viết tay thì

thường đạt được kết quả rất tốt nhưng thường phải tốn rất nhiều công sức. Mô hình thống
kê thì thường địi hỏi một số lượng lớn dữ liệu huấn luyện đã được đánh chú thích nhưng
có thể chuyển sang các ngôn ngữ khác, phân loại dữ liệu theo miền thường ít tốn cơng sức
hơn.
Dưới đây là một số phương pháp nhận biết thực thể của một số tác giả:
•

Hệ thống [28] đề ra phương pháp nhận biết cả thực thể lẫn quan hệ dùng công
thức đại số tuyến tính (linear programming formulation).

•

Hệ thống [27] thì áp dụng học máy dựa trên xác suất để xác định thực thể có tên
và quan hệ.

•

Hệ thống [46] đưa ra phương pháp nhận biết thực thể có tên chủ yếu dựa vào tập
ngữ liệu và tập mẫu trên miền Web, đồng thời nó cịn cho phép ta thay đổi tập
ngữ liệu và mẫu nhằm đáp ứng yêu cầu hệ thống chúng ta. Hệ thống này có tên là
ESPotter (Adaptive Named Entity Recognition for Web Browsing), nó cũng có
tính dễ tích hợp và dễ mang đi. Tuy nhiên nó chỉ thích hợp cho các ứng dụng
Web.

•

Hế thống [13] có tên là ANNIE (A Nearly-New Information Extraction system)
là một phần trong kiến trúc GATE, được thiết kế dưới dạng hệ thống rút trích
thơng tin có thể dùng lại và có nhiều ứng dụng khác nhau. Hệ thống này được
chọn để nhận biết thực thể không tên trong luận văn này. Ta sẽ tìm hiểu kỹ ở

phần tiếp theo sau.

2.3 Một số phương pháp rút trích quan hệ
Rút trích quan hệ là xác định mối quan hệ ngữ nghĩa giữa cặp các thành phần khơng có cấu
trúc hay bán cấu trúc trong văn bản ngơn ngữ tự nhiên ([35]). Rút trích quan hệ dựa trên


Chương 2: Các nghiên cứu liên quan

11

ontology liên quan tới hai cơng việc chính: xác định mối quan hệ giữa hai thành phần đã
biết chủ yếu dựa trên miền ontology và khám phá các mối quan hệ mới giữa hai khái niệm
khơng có trên miền ontology.
Rút trích quan hệ có thể phân ra làm ba phương pháp chính: kỹ thuật tri thức (knowledge
engineering), học máy và phương pháp kết hợp. Sau đây ta sẽ tìm hiểu các lần lượt các
phương pháp:
•

Kỹ thuật tri thức là phương pháp áp dụng luật như: luật định nghĩa trên tập các
thành phần ngữ liệu, luật định nghĩa dựa vào phân tích văn phạm, v.v…

•

Học máy là phương pháp nhận biết quan hệ dựa trên xác suất hay ước lượng.

•

Phương pháp kết hợp là phương pháp áp dụng cả hai kỹ thuật trên.


Những lợi ích mà rút trích quan hệ mang lại:
•

Hệ thống [11] là một ứng dụng về rút trích thơng tin y học.

•

Hệ thống [24] là một ứng dụng rút trích quan hệ để tìm các mối liên kết giữa các
bài báo với nhau, như dựa trên thông tin là tên tác giả, nơi phát hành.

•

Hệ thống [2] là một ứng dụng trong việc xây dựng một hệ thống rút trích thơng
tin tự động dựa trên tập các ontology quan hệ.

•

Hệ thống [5] là một ứng dụng rút trích thơng tin để xây dựng ontology .

•

Hệ thống [29] là một ứng dụng để mở rộng tài nguyên ngữ liệu.

•

Hệ thống [21], [22], [39] là các ứng dụng rút trích quan hệ để xây dựng hệ thống
hỏi đáp.

•


Hệ thống [35] là một ứng dụng rút trích thơng tin để mở rộng thêm chú thích ngữ
nghĩa cho web có ngữ nghĩa.

Các cơng trình nghiên cứu của một số tác giả về rút trích quan hệ:
•

Tác giả của hệ thống [3] áp dụng phương pháp kỹ thuật tri thức để nhận biết quan
hệ dựa trên các từ liên hệ như giới từ hay liên từ.

•

Tác giả hệ thống [24] áp dụng học máy theo phương pháp thống kê để tiên đốn
và rút trích các địa chỉ website trên các site.

•

Tác giả hệ thống [39] áp dụng phương pháp học máy không giám sát dựa trên
WordNet, cung cấp cho hệ thống trước một tập mẫu gọi là seed-pattern, đây là
các mẫu mà ta mong muốn hệ thống tìm. Các mẫu này sau đó được so trùng với


Chương 2: Các nghiên cứu liên quan

12

những cái khác trong corpus và những cái tương đồng với mẫu nhất sẽ được
thêm vào tập mẫu ban đầu.
•

Tác giả hệ thống [6] đề ra phương pháp tìm ngữ cảnh mà các thực thể xuất hiện

đồng thời, gom cụm các ngữ cảnh theo phương pháp thống kê, áp dụng giải thuật
xác định các nét thích hợp để đặt nhản cho quan hệ.

•

Tác giả hệ thống [28] đề ra phương pháp dùng đại số tuyến tính để nhận biết thực
thể và quan hệ.

•

Tác giả hệ thống [27] áp dụng học máy dựa trên phương pháp xác suất để nhận
biết thực thể và quan hệ.

•

Tác giả hệ thống [2] đưa ra mơ hình tự động để rút trích thơng tin bằng cách so
trùng các động từ và các cặp thực thể với quan hệ ontology được xây dựng trước.

•

Tác giả hệ thống [37] đưa ra phương pháp học máy dựa và tập các nét như từ
vựng, thực thể, ngữ nghĩa.

•

Tác giả các hệ thống [33], [34], [35] đề ra phương pháp tổng hợp, đầu tiên câu
cần phân tích sẽ được đưa qua bộ phận phân tích cú pháp LC hay Manipar để tìm
ra các bộ ba ngữ nghĩa, sau đó dựa vào các bộ ba tìm đựợc áp dụng RSS (relation
semilarity service) để tìm sự tương đồng với các mẫu có trong tập các ngữ liệu và
cơ sở tri thức của hệ thống, hệ thống cịn có thể nhận biết được quan hệ mới dựa

và phương pháp học máy theo RSS.

•

Hệ thống [29] được dùng để rút trích quan hệ, mục đích để mở rộng ontology
bằng cách rút trích các cụm từ, cụm động từ, từ tập các văn bản và xác định quan
hệ dựa vào phân tích cú pháp và phương pháp thống kê.

2.4 GATE
GATE (General Architecture for Text Engineering) được phát triển bởi đại học Sheffield
từ năm 1995 và đã được dùng rộng rãi trong nghiên cứu và phát triển các dự án. GATE là
một cơ sở hạ tầng để xây dựng và phát triển các thành phần phần mềm xử lý ngôn ngữ tự
nhiên ([13]). Nó giúp các nhà khoa học và nhà phát triển theo ba cách sau đây:
•

Cung cấp một kiến trúc, hoặc một cấu trúc tổ chức cho những phần mềm xử lý
ngôn ngữ.


Chương 2: Các nghiên cứu liên quan
•

13

Cung cấp một nền (framework), hoặc một thư viện hiện thực kiến trúc. Các thư
viện này có thể được sử dụng để nhúng chức năng xử lý ngơn ngữ vào một phần
mềm nào đó.

•


Cung cấp một môi trường phát triển (development environment) được xây dựng
trên nền (framework). Môi trường này cung cấp một giao diện đồ họa cho việc
xây dựng các thành phần dễ dàng hơn.

Xét trên phương diện kiến trúc phần mềm, GATE chia hệ thống phầm mềm thành các
thành phần khác nhau được gọi là tài nguyên (resource). Các thành phần là các đơn vị phần
mềm có thể dùng lại và đã được định nghĩa giao diện (interface) một cách rạch ròi. Có ba
loại tài ngun chính trong GATE:
•

Tài ngun ngơn ngữ (Language Resource – LRs): lưu trữ một số loại dữ liệu
ngôn ngữ như văn bản, corpora, ontology và cung cấp các dịch vụ để xử lý
chúng.

•

Tài nguyên xử lý (Processing Resource – PRs): là những tài nguyên mà đặc tính
của nó chủ yếu là các ngun tắc lập trình hay thuật tốn, ví dụ như POS Tagger
hay một bộ phân tích văn phạm.

•

Tài ngun hiển thị (Visual Resource – VRs): là những thành phần đồ hoạ do
phần mềm GATE hổ trợ và được thể hiện trên giao diện người dùng. Nó giúp cho
việc sử dụng GATE dễ dàng và hiệu quả hơn.

Khi chúng ta muốn dùng GATE để xây dựng các chức năng xử lý ngơn ngữ cho ứng dụng,
thì ta cần phải có các loại tài ngun trên. Mơi trường phát triển GATE cũng cung cấp cho
ta một công cụ trực quan để tạo ra các tài nguyên này. Tuy nhiên, ta cũng có thể dùng tập
các tài nguyên đã được tích hợp sẵn trong GATE được gọi là CREOLE (Collection of

Reusable Objects for Language Engineering). Tất cả tài ngun này được viết bằng ngơn
ngữ Java và được đóng gói dưới dạng tập tin JAR, mỗi tài nguyên có một tập tin cấu hình
dạng XML. Sau đây tơi sẽ trình bày hệ thống rút trích thơng tin ANNIE đã được dùng để
nhận biết thực thể không tên trong luận văn.


Chương 2: Các nghiên cứu liên quan

14

ANNIE
ANNIE (A Nearly-New Information Extraction system) ([13]) là hệ thống rút trích thơng
tin bao gồm tập hợp các tài nguyên xử lý. ANNIE dựa trên giải thuật trạng thái hữu hạn và
ngôn ngữ JAPE. Quá trình xử lý trong ANNIE được minh bằng hình 2.3.

Hình 2.3 Quá trình xử lý trong ANNIE
Tokeniser chia văn bản thành tập các token đơn giản như: các từ, số, ký tự đặc biệt, dấu
câu và khoảng cách bằng tập luật.
Gazetteer là tập những văn bản thô chứa tập các tên, như tên thành phố, tổ chức, con
người, nghề nghiệp, v.v… Mỗi tập tin trong Gazetteer có nhiều hàng, mỗi hàng mơ tả một
phần tử. Hình 2.4 là một ví dụ một tập tin Gazetteer chứa tập danh sách các thực thể không
tên.


Chương 2: Các nghiên cứu liên quan

15

City
State

Country
Continent
Hình 2.4 Ví dụ một tập tin danh sách của Gazetteer
Tập tin chỉ mục (lists.def) được dùng để truy xuất đến tập các danh sách này. Cấu trúc của
tập tin chỉ mục như sau: gồm nhiều hàng, mỗi hàng mô tả một danh sách bao gồm: tên tập
tin liệt kê các từ trong danh sách, kiểu chính (major type) và kiểu phụ (minor type) của
những từ được liệt kê trong danh sách đó, các thông tin này được ngăn cách nhau bằng dấu
hai chấm. Kiểu chính là bắt buộc phải có nhưng kiểu phụ có thể khơng cần. Hình 2.5 là
một ví dụ về tập tin chỉ mục.
unknownentity.lst:UE
relation.lst:RW
conjunction_cap.lst:CONJ
Hình 2.5 Ví dụ một tập tin chỉ mục
Dòng đầu tiên cho biết tập tin unknowentity.lst là tên tập tin văn bản thô liệt kê danh sách
các thực thể khơng tên kiểu chính là UE và khơng có kiểu phụ.
Sentence Splitter là q trình phân chia văn bản thành các câu, công việc này là cần thiết
cho quá trình tagger. Việc phân chia này chủ yếu dựa vào các dấu câu chẳng hạn như dấu
chấm hay dấu xuống hàng.
Part of Speech Tagger là quá trình tìm kiếm từ loại cho các từ trong văn bản dựa trên định
nghĩa hay ngữ cảnh, nghĩa là quan hệ với các từ xung quanh trong cụm từ, câu hay văn
bản.
Semantic Tagger trong ANNIE dựa trên văn phạm JAPE. Tổng hợp các chú thích sinh ra ở
các giai đoạn trước để tạo ra tập các thực thể được chú thích ngữ nghĩa.


Chương 2: Các nghiên cứu liên quan

16

2.5 KIM

KIM (Knowledge and Information Management) ([19]) cung cấp cơ sở hạ tầng và các dịch
vụ để chú thích ngữ nghĩa tự động, đánh chỉ mục và truy hồi thông tin cho các nội dung
không cấu trúc hoặc bán cấu trúc. KIM kết hợp kỹ thuật rút trích thơng tin, chú thích ngữ
nghĩa và quản lý dữ liệu dựa trên nền GATE.
KIM thực hiện việc rút trích thơng tin dựa trên Ontology & KB. KIM Ontology (KIMO)
chứa định nghĩa các lớp thực thể có tên, các thuộc tính và các quan hệ giữa các thực thể.
KIMO chứa khoảng 250 lớp thực thể, 100 quan hệ và thuộc tính. KB mơ tả ngữ nghĩa của
các thực thể và ngữ nghĩa của các quan hệ giữa các thực thể này. KIM KB đầy đủ chứa
khoảng 205287 thực thể bao gồm: 35590 nơi chốn, 261 quốc gia, 4262 tỉnh, 4417 thành
phố, 146969 tổ chức, 6354 tên người và 429035 bí danh, các số liệu này được cơng bố vào
tháng 9 năm 2006.
Dựa vào số liệu trên, cho ta thấy KIM không thể chứa đầy đủ tất cả các thực thể có tên, nó
chỉ chứa những thực thể phổ biến trên toàn cầu và các thực thể thường xuất hiện trên các
bản tin hàng ngày thuộc nhiều thể loại khác nhau. Do đó, sẽ có nhiều trường hợp nhiều
thực thể có tên khơng thể nhận ra được hay nhận ra khơng đúng.
Q trình rút trích thơng tin và chú thích ngữ nghĩa trong KIM được biểu diễn trong hình
2.6. Các bước Tokeniser, Gazetteer, Sentence Splitter, POS Tagger cũng tương tự như
trong GATE đã được trình bày ở phần 2.4. Bước Ontology-aware NER pattern-matching
grammars là bước nhận diện tên bằng phương pháp so trùng mẫu kết hợp với KIM
Ontology và KIM KB. Các bước còn lại Simple Disambigution và NE Coreference là quá
trình loại bỏ nhập nhằng và giải quyết vấn đề đồng tham chiếu.
Trong luận văn này KIM được chọn làm module nhận biết thực thể có tên. Như ta đã biết,
vấn đề nhận diện thực thể có tên cũng là một bài tốn lớn, do đó trong luận văn này sẽ
dùng module nhận biết thực thể đã được xây dựng sẵn và chấp nhận những sai sót do
module này mang lại. Mặc dù module nhận diện thực thể trong KIM cũng có nhiều khuyết
điểm, tuy nhiên với tập quan hệ trong ontology hiện thời có trong KIM cũng đủ để tìm ra
một giải pháp tổng quát bài toán này.


Chương 2: Các nghiên cứu liên quan


17

Hình 2.6 Quá trình chú thích ngữ nghĩa trong KIM

2.6 ANTLR
ANTLR (ANother Tool for Language Recognition) là ngôn ngữ cung cấp một khung sườn
để xây dựng bộ phân tích cú pháp, bộ biên dịch, hay bộ chuyển đổi từ những đặc tả có quy
tắc theo cú pháp riêng của nó. Nó sử dụng bộ phân tích cú pháp từ trên xuống hay cịn gọi
LL(k). Nó có thể được dùng với nhiều ngơn ngữ lập trình khác nhau.
Q trình biên dịch ngơn ngữ lập trình đã trở thành một công việc chung. Trong khi để xây
dựng lại một phần bộ phân tích cú pháp cho các ngôn ngữ truyền thống (chằng hạn C++,
Java), đôi khi ta cần phải xây dựng lại từ đầu, và hàng ngàn công việc khác nhau liên quan
tới việc xây dựng bộ nhận diện và bộ thông dịch vẫn đang được phát triển. Các lập trình
viên muốn xây dựng bộ chuyển đổi cho các tập tin có định dạng cơ sở dữ liệu, đồ hoạ hay
các ngôn ngữ siêu văn bản, đều phải xây dựng lại từ đầu thì rất mất thời gian và cơng sức.
Mục đích của ANTLR là giúp ta xử lý tất cả các công việc này một cách hiệu quả và nhanh
nhất.
ANTLR cho phép ta định nghĩa các luật mà bộ phân tích từ vựng sẽ dùng để nhận biết ra
các token và các luật mà bộ phân tích cú pháp sẽ dùng để diễn dịch chuỗi token này. Sau
đó, nó sẽ tạo ra bộ phân tích từ vựng, bộ phân tích cú pháp hay cây AST (Abstract Syntax


Chương 2: Các nghiên cứu liên quan

18

Tree) theo ngôn ngữ mà ta mong muốn, và chúng ta có thể dùng độc lập hay tích hợp vào
trong chương trình khác.
Văn phạm ANTLR gồm nhiều thành phần khác nhau, có một số là tùy chọn và một số là

bắt buộc. Khuôn mẫu văn phạm hình 2.8 chỉ ra tất cả thành phần cần thiết để tạo nên một
chương trình.
•

Phần header chứa thơng tin ghi chú hay các nội dung khác, mà nó sẽ được sao y

nguyên bản vào đầu của tất cả các tập tin được sinh ra bởi ANTLR.
•

Phần options ở sau header và các options trong các lớp YourLexerClass,

YourParserClass và YourTreeParserClass liệt kê các tùy chọn chung và riêng đối với
từng lớp. Ý nghĩa các tùy chọn này ta có thể tìm thấy trong các tài liệu về ANTLR.
Hình 2.7 là ví dụ minh họa khai báo phần options trong chương trình ANTLR.
•

Phần tokens trong các lớp YourLexerClass, YourParserClass, YourTreeParserClass

dùng để định nghĩa các hằng hay các token ảo. Token ảo được dùng khi đặc tả luật văn
phạm. Hình 2.9 là một ví dụ minh họa khai báo phần tokens trong chương trình
ANTLR.
•

Phần luật trong các lớp YourLexerClass được dùng để định nghĩa các luật để nhận

biết các token. Phần luật trong lớp YourParserClass được dùng để định nghĩa các luật
cú pháp văn phạm cụ thể theo các token. Phần luật trong lớp YourTreeParserClass định
nghĩa các luật để xây dựng cây AST (Abstract Syntax Tree). Hình 2.10 là ví dụ minh
họa cú pháp tổng quát của một luật. Trong đó rulename là tên luật, args là thông số của
luật, retval là giá trị trả về sau khi luật thực thi xong, options là các tùy chọn,

alternative là phần thân của luật. Hình 2.11 là một ví dụ minh họa luật nhận biết số
nguyên.
Sau khi đã xây dựng được chương trình ANTLR theo khn mẫu trên, ta sẽ dùng trình
biên dịch ANTLR để dịch, nó sẽ tạo ra các bộ phân tích từ vựng, phân tích cú pháp hay cây
AST thỏa mãn yêu cầu đã được đặc tả.
options {
k = 2;
// nhìn trước 2 token
defaultErrorHandler = false; // khơng sinh ra lỗi tự động
khi phân tích cú pháp
}

Hình 2.7 Ví dụ về khái báo phần options trong chương trình ANTLR


Chương 2: Các nghiên cứu liên quan

header {
// các ghi chú hay đoạn code sẽ được sao y nguyên bản vào đầu các
tập tin được sinh ra bởi ANTLR
}
options { tùy chọn cho tồn bộ chương trình }
{ optional class preamble - output to generated classfile
immediately before the definition of the class }
class YourLexerClass extends Lexer;
// definition extends from here to next class definition
// (or EOF if no more class defs)
options { tùy chọn riêng cho lớp }
tokens...
lexer rules...

myrule[args] returns [retval]
options { defaultErrorHandler=false; }
:

// phần thân của luật...

;
{ optional class preamble - output to generated classfile
immediately before the definition of the class }
class YourParserClass extends Parser;
options { tùy chọn riêng cho lớp }
tokens...
parser rules...
{ optional class preamble - output to generated classfile
immediately before the definition of the class }
class YourTreeParserClass extends TreeParser;
options { tùy chọn riêng cho lớp }
tokens...
tree parser rules...
// arbitrary lexers, parsers and treeparsers may be included

Hình 2.8 Khn mẫu của một chương trình ANTLR.

19


Chương 2: Các nghiên cứu liên quan

tokens {
EXPR;

THIS="that";
INT="int";
}

20

// định nghĩa token ảo
// định nghĩa hằng
// định nghĩa hằng

Hình 2.9 Ví dụ phần khái báo tokens trong chương trình ANTLR

rulename [args] returns [retval]
options { defaultErrorHandler=false; }
{ optional initiation code }
:
alternative_1
|
alternative_2
...
|
alternative_n
;

Hình 2.10 Cú pháp tổng quá của một luật trong chương trình ANTLR

INT: ('0'..'9')+;

Hình 2.11 Ví dụ luật nhận biết số ngun trong chương trình ANTLR.


2.7 JavaBayes
JavaBayes là một hệ thống xử lý mạng Bayes. Nó tính các xác suất phân bổ và thực hiện
các ước tính, sinh ra các giải thích, thực hiện các phân tích, và cho phép người sử dụng tạo,
sửa, nhập hay xuất các mạng Bayes. Nó được hiện thực bằng ngơn ngữ Java do đó chúng
ta có thể dễ dàng tích hợp vào các ứng dụng mà cần một công cụ để suy diễn trên miền xác
định nào đó.
Hệ thống JavaBayes là một tập hợp các cơng cụ giúp cho việc tạo và xử lý mạng Bayes.
Nó bao gồm ba bộ phận chính: giao diện đồ hoạ, bộ phận suy diễn trung tâm và tập hợp
các bộ phân tích định dạng. Giao diện đồ hoạ cho phép chúng ta tạo và thay đổi mạng
Bayes một cách dễ dàng. Bộ phân tích định dạng cho phép ta nạp các mạng Bayes có các
định dạng khác nhau. Bộ suy diễn chịu trách nhiệm việc xử lý các cấu trúc dữ liệu thể hiện
mạng Bayes và thực hiện các quá trình tính tốn xác suất phân bổ cho các biến, ước lượng
giá trị và cấu hình hệ thống.


Chương 2: Các nghiên cứu liên quan

21

JavaBayes tính các xác suất phân bổ và ước lượng dựa vào hai giải thuật chính: loại trừ
biến (variable elimination) và loại trừ cây thùng (bucket tree elimination). Ở trường hợp
thứ nhất, mỗi lần cần xử lý cho câu truy vấn thì quá trình suy diễn được sinh ra. Ở trường
hợp thứ hai, cấu trúc dữ liệu sẽ được tạo ra một lần, các câu truy vấn sẽ được xử lý dựa
trên cấu trúc dữ liệu này. Phương pháp loại trừ biến tốn ít bộ nhớ hơn, nhưng sẽ mất thời
gian hơn nếu ta cần xử lý nhiều câu truy vấn trên cùng một mạng với tập hợp các biến điều
kiện là như nhau
Hệ thống có thể nạp mạng Bayes với các định dang khác nhau: định dạng BIF 0.1, BIF
0.15, XMLBIF 0.2, XMLBIF 0.3. Ta cũng có thể lưu trữ lại mạng đã thiết kế với các định
dạng: định dạng BIF 0.15, XMLBIF 0.3 và BUGS. Định dạng XMLBIF lưu trữ dữ liệu
dưới dạng XML. Định dạng BUGS được đặc tả trong các tài liệu về hệ thống BUGS, nó

bao gồm tập giao diện (interface) đầy đủ và hệ thống suy diễn Bayes dựa trên giải thuật
Gibbs sampling, định dạng này có thể được dùng để xử lý mạng Bayes bất kỳ được sinh ra
từ JavaBayes
JavaBayes cung cấp công cụ và giao diện đồ hoạ để xử lý mạng Bayes. Tuy nhiên, trong
một số ứng dụng chúng ta lại cần một hệ thống suy diễn có thể dễ dàng nhúng vào ứng
dụng với yêu cầu tiết kiệm bộ nhớ và thực thi hiệu quả. EBayes là hệ thống suy diễn mạng
Bayes đáp ứng được yêu cầu đó. Bộ phận suy diễn của EBayes dựa trên hệ thống
JavaBayes, nó có các chức năng tương tự như JavaBayes nhưng được xây dựng một cách
tối ưu hơn.

Hệ thống EBayes có kích thước khá nhỏ, khả năng liên kết động do đó nó tiết kiệm được
bộ nhớ. Mục tiêu của EBayes tạo ra một cơ sở hạ tầng tổng quát cho việc ứng dụng mạng
Bayes trong các thiết bị mà cần hệ thống suy diễn trên những yếu tố khơng chắc chắn nào
đó. Ý tưởng của EBayes là xây dựng được hệ thống hiệu quả để có thể ứng dụng mạng
Bayes vào những thiết bị nhỏ cho tới thiết bị lớn.
Những nhà phát triển muốn dùng EBayes hiệu quả cần phải hiểu rỏ ba kiểu đối tượng sau:
•

Đối tựong BayesNet, thể hiện mạng Bayes. Trong đối tượng này có phương thức

add dùng thể nhập đối tượng DiscreteVariable và DiscreteFunction