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

CHỬ ĐĂNG ĐỊNH
ĐỀ TÀI:

HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN
TIẾNG VIỆT

LUẬN VĂN THẠC SỸ
NGÀNH: CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
LÊ THANH HƯƠNG

HÀ NỘI – 2010


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

LỜI CAM ĐOAN

Tôi Chử Đăng Định – học viên lớp Cao học CNTT 2008-2010 xin cam kết:
1. Luận văn tốt nghiệp Thạc sĩ này là công trình nghiên cứu của bản thân tôi dưới sự
hướng dẫn của TS. Lê Thanh Hương.
2. Các kết quả trong luận văn tốt nghiệp là trung thực, không phải sao chép toàn văn
của bất kỳ công trình nào khác.
Hà Nội, ngày 29 tháng 10 năm 2010
Tác giả LVTN

Chử Đăng Định

1


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

LỜI CẢM ƠN
Em xin chân thành gửi lời cảm ơn chân thành và sâu sắc nhất tới cô giáo TS. Lê
Thanh Hương đã tận tình hướng dẫn và giúp đỡ trong quá trình làm luận văn này.
Em chân thành cảm ơn các thầy cô trong Viện Công nghệ Thông tin và Truyền
thông đã cung cấp kiến thức quý báu cho em trong những năm học vừa qua.
Xin chân thành cảm ơn tác giả Lê Hồng Phương (tác giả bộ công cụ gán nhãn từ
loại tiếng Việt vnTagger) đã cho phép sử dụng và có sự hỗ trợ kịp thời đối với bộ
công cụ vnTagger.
Xin chân thành cảm ơn các thành viên trong nhóm xử lý ngôn ngữ tự nhiên của
Viện Công nghệ Thông tin và Truyền thông đã đưa ra góp ý, nhận xét về giải pháp
cũng như kết quả của đề tài.
Mặc dù em đã cố gắng hoàn thành luận văn này trong phạm vi khả năng cho phép
nhưng chắc chắn không không thể tránh được những thiếu sót. Em kính mong được
nhận được sự thông cảm và sự chỉ bảo tận tình của các thầy cô và các bạn.

Hà Nội 10/2010
Học viên:

Chử Đăng Định

Lớp:


Cao học CNTT 2008-2010

2


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

MỤC LỤC

LỜI CAM ĐOAN.............................................................................................1
LỜI CẢM ƠN .................................................................................................2
MỤC LỤC.......................................................................................................3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ..............................................6
DANH MỤC CÁC BẢNG ..................................................................................8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ................................................................9
PHẦN MỞ ĐẦU............................................................................................11
CHƯƠNG 1 TỔNG QUAN VỀ TRÍCH RÚT THÔNG TIN VÀ CÁC MÔ HÌNH
HỌC QUAN HỆ.............................................................................................14

1.1. Tổng quan về trích rút thông tin .................................................................... 15
1.1.1. Trích rút thông tin....................................................................................... 15
1.1.2. Trích rút thông tin và thu thập thông tin .................................................... 16
1.2. Kỹ thuật học quan hệ kiểu ký hiệu (symbolic).............................................. 17
1.2.1. Các vấn đề về thiết kế giải thuật tổng thể................................................... 18
1.2.2. FOIL ........................................................................................................... 20
1.2.3. GOLEM ...................................................................................................... 23
1.2.4. CHILLIN .................................................................................................... 26
1.2.5. PROGOL .................................................................................................... 27

1.3. Các phương pháp học...................................................................................... 28
1.4. Các nguồn lực xử lý ngôn ngữ tự nhiên......................................................... 29
1.4.1. Phân tách từ vựng (Word Segmentation) ................................................... 30
1.4.2. Gán nhãn từ loại (Part-of-speech tagger) ................................................... 31
1.4.3. Từ điển từ vựng (Lexicon) ......................................................................... 33

3


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

1.4.4. Nhận dạng thực thể có tên (Named-Entity Recognition) ........................... 35
1.5. Kết chương ....................................................................................................... 36
CHƯƠNG 2

HƯỚNG TIẾP CẬN RAPIER CHO BÀI TOÁN TRÍCH RÚT

THÔNG TIN.................................................................................................37

2.1. Biểu diễn luật.................................................................................................... 38
2.2. Giải thuật học ................................................................................................... 39
2.2.1. Các lựa chọn thiết kế giải thuật .................................................................. 39
2.2.2. Tổng quan về giải thuật .............................................................................. 41
2.2.3. Xây dựng tập luật khởi đầu ........................................................................ 42
2.2.4. Cô đọng tập luật.......................................................................................... 43
2.2.5. Tiêu chuẩn đánh giá luật............................................................................. 48
2.2.6. Tính toán mẫu khái quát hóa của hai mẫu.................................................. 51
2.2.7. Pha chuyên biệt hóa.................................................................................... 61
2.3. Áp dụng phương pháp học tích cực với RAPIER......................................... 65

2.3.1. Lấy mẫu có lựa chọn .................................................................................. 66
2.3.2. Áp dụng phương pháp lấy mẫu có lựa chọn vào RAPIER......................... 67
Độ không chắc chắn trong RAPIER ...........................................................................68
Trang bị khả năng học tăng cường cho RAPIER........................................................69

2.4. Kết chương ....................................................................................................... 70
CHƯƠNG 3 ĐỀ XUẤT MÔ HÌNH RAPIER CHO TRÍCH RÚT THÔNG TIN
TIẾNG VIỆT.................................................................................................72

3.1. Các điều chỉnh khi áp dụng mô hình RAPIER với tiếng Việt..................... 73
3.1.1. Công cụ tách từ tiếng Việt.......................................................................... 73
3.1.2. Công cụ gán nhãn từ loại tiếng Việt........................................................... 74
3.1.3. Cây ngữ nghĩa và từ điển ngữ nghĩa tiếng Việt.......................................... 74
3.2. Các cải tiến cho mô hình ................................................................................. 74
3.2.1. Tích hợp nhận dạng thực thể có tên ........................................................... 74
3.2.2. Sinh luật trích rút gần đúng ........................................................................ 77
3.2.3. Tùy biến độ rộng cửa sổ so khớp theo từng trường thông tin .................... 78

4


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

3.3. Kết chương ....................................................................................................... 78
CHƯƠNG 4 PHÂN TÍCH VÀ THIẾT KẾ HỆ THỐNG ........................................79

4.1. Xác định yêu cầu .............................................................................................. 80
4.2. Phân tích thiết kế hệ thống.............................................................................. 81
4.2.1. Thiết kế tổng thể của hệ thống trích rút thông tin tiếng Việt ..................... 81

4.2.2. Chức năng tiền xử lý văn bản..................................................................... 83
4.2.3. Chức năng học luật..................................................................................... 86
4.2.4. Chức năng trích rút thông tin...................................................................... 91
4.2.5. Chức năng đánh giá luật ............................................................................. 92
4.3. Kết chương ....................................................................................................... 93
CHƯƠNG 5 – CÀI ĐẶT MÔ HÌNH VÀ KIỂM THỬ KẾT QUẢ ...........................94

5.1. Cài đặt chương trình ....................................................................................... 95
5.2. Phương pháp thực nghiệm.............................................................................. 95
Các độ đo thực nghiệm......................................................................................... 95
Các phiên bản thực nghiệm .................................................................................. 96
5.3. Ngữ liệu thực nghiệm....................................................................................... 97
5.4. Kết quả thực nghiệm ....................................................................................... 98
5.5. Đánh giá thực nghiệm.................................................................................... 101
5.5.1. Về thời gian thực hiện .............................................................................. 101
5.5.2. Về công cụ tách từ và gán nhãn từ loại .................................................... 101
5.5.3. Về từ điển ngữ nghĩa và tác vụ gán nhãn thực thể có tên ........................ 102
5.5.4. Về các luật trích rút gần đúng .................................................................. 103
KẾT LUẬN VÀ ĐỊNH HƯỚNG PHÁT TRIỂN ................................................104
TÀI LIỆU THAM KHẢO...............................................................................106
PHẦN PHỤ LỤC .........................................................................................108

PHỤ LỤC 1 - TẬP CÁC NHÃN TỪ LOẠI TIẾNG VIỆT ĐƯỢC SỬ DỤNG109
PHỤ LỤC 2 - TẬP LUẬT KẾT QUẢ THỰC NGHIỆM.................................. 110

5


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT

Từ viết tắt

1.

CFG

Giải nghĩa
Context Free Grammar
Văn phạm phi ngữ cảnh

2.

filler

3.

FOIL

Thông tin điền hay thông tin cần trích rút
First Order Inductive Learning
Học quy nạp bậc 1
Hidden Markov Model

4.

HMM

Mô hình Markov ẩn
Hệ trích rút thông tin

5.

IE
Information Extraction
Trình logic quy nạp

6.

ILP
Inductive Logic Programming
Hệ thu thập thông tin

7.

IR
Information Retrieval

8.

LGG

Phép tổng quát hóa ít khái quát nhất
Least-general generalization

9.

literal


Ký hiệu mệnh đề

6


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

STT

Từ viết tắt

Giải nghĩa

10.

MUC

Message Understanding Conferences

11.

NER

Named-Entity Recognition
Nhận dạng thực thể có tên

12.


NLP

Natural Language Processing
Xử lý ngôn ngữ tự nhiên

13.

POS

14.

RAPIER

Part of Speech - Từ loại
Robust Automated Production of Information Extraction Rules
Tự động linh hoạt sinh luật trích rút thông tin

15.

slot-filler

16.

SVM

Thông tin cần trích rút của trường
Support Vector Machine
Mô hình máy vector hỗ trợ

7



LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

DANH MỤC CÁC BẢNG
Bảng 1.1: Đánh giá một số hệ thống tách từ tiếng Việt ............................................31
Bảng 5.1: Kết quả đo theo từng trường thông tin trong trường hợp có sử dụng luật
trích rút gần đúng...............................................................................................98
Bảng 5.2: Kết quả đo tổng thể và thời gian thực hiện trung bình trong trường hợp có
sử dụng luật trích rút gần đúng ..........................................................................99
Bảng 5.3: Kết quả đo theo từng trường thông tin trong trường hợp không sử dụng
luật trích rút gần đúng........................................................................................99
Bảng 5.4: Kết quả đo tổng thể và thời gian thực hiện trung bình trong trường hợp
không sử dụng luật trích rút gần đúng ...............................................................99

8


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Thu thập thông tin .....................................................................................16
Hình 1.2. Trích rút thông tin .....................................................................................16
Hình 1.3. Mối quan hệ giữa IR, IE và Full Text Understanding[3]..........................17
Hình 1.4: Giải thuật bao phủ FOIL ...........................................................................21
Hình 1.5: Bước “tìm mệnh đề” trong giải thuật FOIL..............................................22
Hình 1.6: Hai trường hợp cụ thể của mối quan hệ uncle ..........................................24
Hình 1.7: Mệnh đề LGG của các mệnh đề trong Hình 1.6 .......................................24

Hình 1.8: Kết quả của việc đơn giản hóa các mệnh đề bằng cách loại bỏ các literal
dư thừa ...............................................................................................................25
Hình 1.9: Giải thuật xây dựng mệnh đề của GOLEM ..............................................25
Hình 1.10: Giải thuật gộp của CHILLIN ..................................................................27
Hình 2.1: Ví dụ về các mẫu và các ràng buộc trong 1 luật .......................................39
Hình 2.2: Giải thuật RAPIER....................................................................................41
Hình 2.3: Giải thuật RAPIER để qui nạp các luật trích rút.......................................47
Hình 2.4: Một ví dụ về việc khái quát hóa hai phần tử mẫu.....................................54
Hình 2.5: Ví dụ về việc khái quát hóa một cặp hai mẫu cùng độ dài .......................55
Hình 2.6: Hai mẫu khác độ dài. Các đường thẳng chỉ các các phần tử khác nhau có
thể được nhóm cùng nhau để khái quát hóa ......................................................56
Hình 2.7: Sáu cách có thể có các phần tử của các mẫu trong Hình 2.6 có thể được so
sánh để khái quát hóa.........................................................................................57
Hình 2.8: Cách nhóm thu được từ việc tìm một so khớp chính xác giữa phần tử 3
của mẫu dài với phần tử 2 của mẫu ngắn trong Hình 2.6. Khi các phần tử giống
nhau đã được ghép cặp, phần còn lại chỉ còn lại một cách ghép nhóm.............58
Hình 2.9: Khái quát hóa của một mẫu hai phần tử với một mẫu không có phần tử
nào......................................................................................................................59
Hình 2.10: Khái quát hóa của mẫu hai phần tử với mẫu có một phần tử. Vì mẫu B là
mẫu dạng danh sách có độ dài 3, các khái quát hóa cũng phải có độ dài 3.......59
Hình 2.11: Giải thuật RAPIER để chuyên biệt hóa mẫu pre-filler của luật..............63
Hình 2.12: Giải thuật RAPIER để chuyên biệt hóa mẫu post-filler của luật ............64
Hình 2.13: Các pha trong giải thuật học RAPIER ....................................................65
Hình 3.1: Giải thuật gộp theo nhãn thực thể .............................................................76
Hình 4.1. Các chức năng hệ thống trích rút thông tin vnRAPIER............................81
Hình 4.2: Sơ đồ hệ thống trích rút thông tin vnRAPIER ..........................................82

9



LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

Hình 4.3: Tiền xử lý văn bản đã gán nhãn thực thể có tên .......................................84
Hình 4.4: File văn bản đầu vào đã được gán nhãn thực thể bằng tay .......................84
Hình 4.5: File văn bản sau khi gán nhãn từ loại .......................................................85
Hình 4.6: Sơ đồ chức năng học luật trích rút ............................................................86
Hình 4.7: Ví dụ về khuôn mẫu thông tin trích rút.....................................................89
Hình 4.8: Một ví dụ về file chú thích cho văn bản huấn luyện.................................89
Hình 4.9: Mỗi ví dụ huấn luyện gồm văn bản và phần chú thích .............................89
Hình 4.10: Sơ đồ chức năng trích rút thông tin.........................................................91
Hình 4.11: Sơ đồ chức năng đánh giá luật ................................................................93
Hình 5.1: Độ đo F thu được theo số lượng ví dụ huấn luyện..................................100

10


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

PHẦN MỞ ĐẦU
Trong những năm gần đây, với sự phát triển không ngừng của Internet, dẫn tới sự
tăng trưởng chóng mặt về số lượng thông tin sẵn có trên mạng, trong đó phần nhiều
là dưới dạng văn bản ngôn ngữ tự nhiên. Với các cỗ máy tìm kiếm thông minh như
Google, Yahoo… đã giúp chúng ta thu thập được các văn bản liên quan đến yêu cầu
tìm kiếm. Vấn đề đặt ra là làm sao chúng ta thu thập được đúng và đủ những thông
tin cần thiết từ mỗi văn bản mà cỗ máy đó tìm kiếm đem về. Đó chính là công việc
của trích rút thông tin (Information Extraction - IE).
Các nghiên cứu gần đây về ngôn ngữ học tính toán cho thấy rằng các phương pháp
dựa trên thực nghiệm hoặc dựa trên ngữ liệu là cách tiếp cận hứa hẹn nhất để phát

triển các hệ thống xử lý ngôn ngữ tự nhiên (NLP) mạnh mẽ, hiệu quả. Các phương
pháp đó thu được một cách tự động hoá nhiều tri thức phức tạp cần thiết cho NLP
bằng cách huấn luyện kho ngữ liệu ngôn ngữ tự nhiên phù hợp đã được chú thích
(annotate).
Hầu hết các phương pháp NLP dựa trên thực nghiệm đó sử dụng các kỹ thuật thống
kê như mô hình n-gram, mô hình Markov ẩn (HMMs), và văn phạm phi ngữ cảnh
kết hợp xác suất (PCFGs). Cũng đã có các nghiên cứu quan trọng áp dụng các
phương mạng nơ-ron để xử lý ngôn ngữ (Reilly & Sharkey, 1992; Miikkulainen,
1993). Ngoài ra, đã có nghiên cứu sử dụng học dựa trên ký hiệu (symbolic learning)
như sử dụng cây quyết định (Magerman 1995; Aone & Bennett, 1995), luật chuyển
đổi (Brill, 1993, 1995), và các phương pháp dựa trên ký hiệu khác (Wermter, Rilo,
& Scheler, 1996).
Trước các thành công của các phương pháp xử lý ngôn ngữ tự nhiên mang tính thực
nghiệm, các nhà nghiên cứu đã bắt đầu áp dụng các phương pháp học để xây dựng
các hệ thống trích rút thông tin (McCarthy & Lehnert, 1995; Soderland, Fisher,
Aseltine & Lehnert, 1995, 1996; Rilo, 1993, 1996; Kim & Moldovan, 1995;

11


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

Huffman, 1996). Một trong số đó là nghiên cứu của tác giả Mary Elaine Califf (Đại
học Texas), có tên RAPIER (Robust Automated Production of Information
Extraction Rules)[2]. RAPIER học các luật đối với tác vụ trích rút thông tin, các
luật đó tạo ra các mục thông tin mong muốn một cách trực tiếp từ các tài liệu mà
không có phân tích cú pháp trước hay bất cứ khâu hậu xử lý nào. Thay vì học phân
loại, RAPIER thực hiện học theo dạng biểu diễn ký hiệu có cấu trúc (có biểu thị
mối quan hệ).

Xuất phát từ ngữ liệu các tài liệu đi đôi với các khuôn mẫu thông tin điền sẵn (filled
templale), RAPIER học các mẫu dạng Eliza (Weizenbaum, 1966) tạo ra các thông
tin ràng buộc về cú pháp và ngữ nghĩa, bằng cách sử dụng các nguồn tri thức linh
hoạt, sẵn có và miễn phí như bộ gán nhãn từ loại (POS tagger) hay bộ từ vựng. Các
luật được xây dựng từ các mẫu đó có thể xem xét một ngữ cảnh không giới hạn, trao
cho chúng một lợi thế so với các cách biểu diễn có giới hạn mà chỉ xem xét một số
lượng từ cố định. Cách biểu diễn tương đối phong phú này đòi hỏi một giải thuật
học có khả năng giải quyết những phức tạp rắc rối của nó. Do đó, RAPIER sử dụng
một giải thuật học mối quan hệ mà kết hợp các kỹ thuật từ một số hệ thống ILP
(Inductive Logic Programming). Các kỹ thuật đó là phù hợp vì chúng được phát
triển để làm việc với cách biểu diễn phong phú, có biểu thị quan hệ (các mệnh đề
logic bậc 1). RAPIER sử dụng chủ yếu dạng tìm kiếm từ cụ thể đến khái quát hay
dưới-lên (bottom-up).
Trên thế giới đã có nhiều nghiên cứu về bài toán IE và đã có thành tựu đáng kể. Tuy
nhiên, các nghiên cứu về tiếng Việt thì còn khá mới mẻ và còn hạn chế. Vì vậy,
người viết luận văn xin thực hiện đề tài “Học mối quan hệ trong trích rút thông
tin tiếng Việt”. Mục đích của đề tài là tìm hiểu về các kỹ thuật học, cụ thể là học
mối quan hệ, áp dụng mô hình học RAPIER vào tiếng Việt và đưa ra một số đóng
góp cải tiến cho mô hình này.
Hướng tiếp cận của người viết luận văn là sử dụng các thành quả đã đạt được về xử
lý văn bản tiếng Việt như bài toán phân tách từ, bài toán gán nhãn từ loại, đồng thời

12


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

sử dụng các tài nguyên sẵn có về tiếng Việt để tự xây dựng từ điển ngữ nghĩa tiếng
Việt (ở mức sơ khai). Từ đó có đủ các điều kiện cần thiết để áp dụng mô hình học

RAPIER. Dựa trên giải thuật đưa ra trong mô hình RAPIER, người viết cũng xây
dựng chương trình thực nghiệm với lĩnh vực thực nghiệm là trích rút thông tin từ
các trang web cá nhân của các nhà khoa học người Việt trong và ngoài nước.
Ngoài việc kế thừa các giải thuật mà mô hình đã có, người viết đã có các cải tiến,
đóng góp mới của mình, đó là:
+ tích hợp tác vụ nhận dạng thực thể có tên (Named-Entity Recognition - NER) vào
khâu tiền xử lý văn bản;
+ bổ sung chức năng sinh luật trích rút gần đúng với các mục thông tin trích rút có
cấu trúc đặc biệt;
+ bổ sung khả năng tùy biến độ rộng cửa sổ so khớp theo từng trường thông tin cần
trích rút.
Nội dung của luận văn gồm có 5 chương trong đó:
Chương 1. Trình bày về các cơ sở lý thuyết của lĩnh vực trích rút thông tin, các mô
hình học quan hệ và các công cụ và nguồn lực xử lý ngôn ngữ tự nhiên mà mô hình
đề cập có thể sử dụng.
Chương 2. Hướng tiếp cận RAPIER cho bài toán trích rút thông tin. Phần này trình
bày cách biểu diễn luật, tiêu chuẩn đánh giá luật, giải thuật học và áp dụng phương
pháp học chủ động vào mô hình.
Chương 3. Trình bày đề xuất mô hình RAPIER cho trích rút thông tin tiếng Việt
(vnRAPIER), trong đó đề cập tới các điều chỉnh khi áp dụng mô hình RAPIER vào
tiếng Việt đồng thời đưa ra các đóng góp cải tiến đối với mô hình.
Chương 4. Trình bày về phân tích và thiết kế tổng thể hệ thống trích rút thông tin
tiếng Việt thực nghiệm dựa trên mô hình đề xuất vnRAPIER.
Chương 5. Cài đặt mô hình và kiểm thử kết quả.

13


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”


CHƯƠNG 1
TỔNG QUAN VỀ TRÍCH RÚT THÔNG TIN VÀ CÁC MÔ
HÌNH HỌC QUAN HỆ

NỘI DUNG:
1.1. Tổng quan về trích rút thông tin
1.2. Kỹ thuật học quan hệ kiểu ký hiệu (symbolic)
1.3. Các phương pháp học
1.4. Các nguồn lực xử lý ngôn ngữ tự nhiên
1.5. Kết chương

14


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

1.1. Tổng quan về trích rút thông tin
1.1.1. Trích rút thông tin
Trích rút thông tin là quá trình lấy ra các mẩu thông tin cần thiết từ các dữ liệu thô
hoặc dữ liệu bán cấu trúc (văn bản ngôn ngữ tự nhiên). Thông tin được lấy ra là
những thông tin có cấu trúc. Thông tin trích rút sau đó có thể được lưu trong cơ sở
dữ liệu mà có thể được truy vấn bằng các ngôn ngữ truy vấn cơ sở dữ liệu hoặc một
giao diện cơ sở dữ liệu ngôn ngữ tự nhiên.
Tác vụ trích rút thông tin rất hữu ích trong các tình huống nơi một tập hợp các tài
liệu văn bản có chứa thông tin có thể được sử dụng dễ dàng hơn bởi con người hay
máy tính nếu các thông tin đã có sẵn trong một định dạng cơ sở dữ liệu thống nhất.
Như vậy, một hệ thống trích rút thông tin được đưa ra tập hợp các tài liệu và một
khuôn mẫu các trường thông tin (slot) để được điền thông tin từ tài liệu đó. Các hệ

thống trích rút thông tin sẽ xác định vị trí và tìm cách xác định cụ thể phần thông tin
cần thiết từ mỗi tài liệu.
Dữ liệu được trích rút từ văn bản có hai dạng khác nhau: dạng phổ biến là hệ thống
xác định và lấy trực tiếp một chuỗi từ văn bản; dạng thứ hai là hệ thống chọn từ một
tập các giá trị có thể điền được vào trường thông tin đó. Một ví dụ cho dạng thứ hai
này là các mục thông tin ngày tháng cần định dạng thống nhất, hoặc đơn giản là các
mục cung cấp các giá trị thống nhất cho thông tin thể hiện trong văn bản.
Dữ liệu được trích rút có thể được chỉ rõ theo một trong hai cách. Hệ thống có thể
điền vào một mẫu với các giá trị lấy từ văn bản, hoặc trong trường hợp tất cả các
trường thông tin được điền trực tiếp bởi các chuỗi từ văn bản, hệ thống có thể tạo
chú thích trực tiếp trên văn bản đó.
Trích rút thông tin có thể hữu ích trong nhiều lĩnh vực. Các hội thảo Message
Understanding Conferences (MUC) từ những năm 90 về lĩnh vực xử lý ngôn ngữ tự
nhiên đã áp dụng vào các lĩnh vực như chủ nghĩa khủng bố khu vực Mỹ Latinh, liên
doanh, vi điện tử. Một số khác đã sử dụng trích rút thông tin để theo dõi hồ sơ y tế

15


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THƠNG TIN TIẾNG VIỆT”

bệnh nhân (Soderland et al., 1995) và để theo dõi các vụ hợp nhất cơng ty
(Huffman, 1996). Gần đây hơn, các nhà nghiên cứu đã áp dụng khai thác thơng tin
cho các thể loại văn bản khơng chính thức như quảng cáo cho th (Soderland,
1998) và các trang web (Freitag, 1998a; Hsu & Dung, 1998; Muslea, Minton, &
Knoblock, 1998). Năm 2007, nhóm tác giả Tianhao Wu, Stephen V. Zanias,
William M.Pottenger đã xây dựng hệ thống Phần mềm để trích rút thơng tin trong
Hệ thống Thơng tin Tư pháp hình sự [3].


1.1.2. Trích rút thơng tin và thu thập thơng tin
Trích rút thơng tin là cơng việc khác với thu thập thơng tin (IR). IR là tìm các tài
liệu, thường là văn bản, mà có liên quan tới nhu cầu thơng tin của người dùng[3].
Google, một hệ thống IR trên web nổi tiếng, là một ví dụ điển hình về hệ thống IR.
Giống như các kết quả tạo ra bởi bộ tìm kiếm web Google, đầu ra của một hệ thống
IR là một tập con các văn bản mà có liên quan tới truy vấn của người dùng. Ngược
lại, mục tiêu của hệ thống IE khơng phải là để trích rút bản thân các tài liệu mà là
trích rút các đặc trưng định trước từ các tài liệu đó. Trong một hệ thống IE, các
thuộc tính thơng tin được trích rút đó thường được đưa vào cơ sở dữ liệu một cách
tự động. Nói một cách ngắn gọn, IR thu thập tài liệu trong khi IE thu thập đặc trưng.

Tậ
p con cá
c tà
i liệ
u

Cá
c tà
i liệ
u

Hình 1.1. Thu thập thơng tin
Name

Cá
c tà
i liệ
u


Diploma

Wiliam

Doctor

Martin

Master

Cá
c đặ
c trưng từcá
c tà
i liệ
u

Hình 1.2. Trích rút thơng tin
16


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

Theo [3], mức độ cao hơn IE là Full Text Understanding, tức là đòi hỏi máy tính
hiểu được văn bản ngôn ngữ tự nhiên. Đây là công việc rất khó vì văn bản ngôn ngữ
tự nhiên thường quá phức tạp để hiểu một cách đầy đủ ngay cả với con người chứ
chưa nói tới máy tính. Có thể xem Full Text Understanding, IE và IR là ba dạng
khác nhau của việc lấy thông tin văn bản, vì chúng đều cần hiểu thông tin văn bản ở
mức độ nào đó. Mối quan hệ giữa ba dạng này có thể minh họa như trên Hình 1.3.


Information
Retrieval

Cụ thể
hơn

Information
Extraction

Cụ thể
hơn

Full Text
Understanding

Hình 1.3. Mối quan hệ giữa IR, IE và Full Text Understanding[3]

1.2. Kỹ thuật học quan hệ kiểu ký hiệu (symbolic)
Từ nhiều công trình thực nghiệm về xử lý ngôn ngữ tự nhiên đã sử dụng các kỹ
thuật thống kê (Charniak 1993; Miller, Stallard, Bobrow, & Schwartz, 1996;
Smadja, McKeown, & Hatzivas siloglou-1996; Wermter et al, 1996), phần này thảo
luận về lợi thế tiềm tàng của việc học quan hệ kiểu ký hiệu (Symbolic relational
learrning). Để đánh giá chính xác xác suất từ dữ liệu có giới hạn, hầu hết các kỹ
thuật thống kê đều đưa ra các quyết định dựa trên một bối cảnh rất hạn chế, chẳng
hạn như các bộ đôi (bigram) hay bộ ba (trigram) (các ngữ cảnh 2 hoặc 3 từ). Tuy
nhiên, các quyết định xử lý ngôn ngữ tự nhiên thường xuyên phải dựa trên ngữ cảnh
lớn hơn nhiều bao gồm một loạt các dấu hiệu về cú pháp, ngữ nghĩa, và dụng ngôn
(pragmatic). Do đó, các nhà nghiên cứu đã bắt đầu sử dụng các kỹ thuật học mà có
thể xử lý những ngữ cảnh lớn hơn, chẳng hạn như cây quyết định (Magerman 1995;

Miller et al., 1996; Aone & Bennett, 1995), phương pháp mẫu điển hình (dựa trên
tình huống) (Cardie 1993; Ng & Lee, 1996), và phương pháp mô hình entropy cực
đại (Ratnaparkhi, 1997). Tuy nhiên, những kỹ thuật này vẫn còn đòi hỏi người phát
triển hệ thống xác định một tập hợp hữu hạn, có thể quản lý được các đặc trưng để
sử dụng trong việc ra quyết định. Việc phát triển này tập hợp các đặc trưng này có
17


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

thể đòi hỏi cơ chế biểu diễn có ý nghĩa thống kê (significant) và vẫn có thể loại trừ
thông tin quan trọng theo ngữ cảnh.
Ngược lại, các phương pháp học quan hệ (Birnbaum & Collins, 1991) cho phép qui
nạp trên các ví dụ có cấu trúc mà có thể bao gồm các vị từ logic bậc 1 và các cấu
trúc dữ liệu không giới hạn như là danh sách và cây. Đặc biệt, kỹ thuật lập trình
Inductive Logic Programming (ILP) cho phép học qui nạp các luật dạng logic bậc 1
(các chương trình Prolog).
Hai lợi thế khác của các kỹ thuật dựa trên ILP là tính hiểu được (comprehensibility)
và khả năng sử dụng tri thức cơ sở. Tính hiểu được của các luật dạng ký hiệu giúp
cho người phát triển dễ hiểu và dễ xác minh được hệ thống kết quả và thậm chí là
chỉnh sửa tri thức đã học được (Cohen, 1996). Đối với kiến thức cơ sở, các hệ thống
ILP được trao cho các định nghĩa Prolog đối với một tập các vị từ mà có thể được
sử dụng trong thân các luật học được. Điều này cho phép hệ thống tận dụng các
khái niệm đã bao gồm trong các vị từ cơ sở mà có liên quan đối với khái niệm đang
được học.
Tuy RAPIER không phải là một hệ thống ILP, nhưng nó là một giải thuật học quan
hệ học kiểu biểu diễn luật có cấu trúc và các giải thuật của nó được lấy ý tưởng từ
các hệ thống ILP. Các ý tưởng dựa trên ILP là phù hợp vì chúng được phát triển để
làm việc với cách biểu diễn phong phú, có biểu thị quan hệ. Các phần sau đây sẽ

thảo luận về các vấn đề thiết kế tổng thể để phát triển ILP và các hệ thống học luật
khác, sau đó mô tả một số hệ thống ILP mà ảnh hưởng tới giải thuật học RAPIER,
bao gồm ba mô hình mà RAPIER trực tiếp phỏng theo: GOLEM, CHILLIN, và
PROGOL.

1.2.1. Các vấn đề về thiết kế giải thuật tổng thể
Một trong số các vấn đề thiết kế trong các hệ thống học luật là cấu trúc tổng thể của
giải thuật. Có hai dạng chính là cô đọng lại (compression) và bao phủ (covering).
Hệ thống sử dụng dạng cô đọng bắt đầu bằng cách tạo một tập ban đầu các luật có

18


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

mức độ cụ thể cao, thường là một luật cho mỗi ví dụ. Ở mỗi bước lặp, một luật khái
quát hơn được xây dựng, thay thế các luật nó đã bao gộp, vì thế tập luật được cô
đọng lại. Ở mỗi bước lặp, tất cả các ví dụ dương đang được xem xét tới phạm vi nào
đó và độ đo để đánh giá các luật mới là thiên về tập luật được cô đọng nhiều hơn.
Việc học luật kết thúc khi không tìm được các luật mới cô đọng hơn. Các hệ thống
sử dụng dạng cô đọng lại bao gồm DUCE, hệ thống học luật mệnh đề sử dụng phân
tích nghịch đảo (Muggleton, 1987), CIGOL, một hệ thống ILP sử dụng phân tích
nghịch đảo (Muggleton & Buntine, 1988) và CHILLIN (Zelle & Mooney, 1994).
Các hệ thống sử dụng dạng bao phủ thì bắt đầu với một tập ví dụ dương. Sau đó, khi
mỗi luật được học, tất cả các ví dụ dương luật mới bao phủ sẽ được loại bỏ khi xem
xét để tạo luật tiếp theo. Việc học luật kết thúc khi tất cả các ví dụ dương đã được
bao phủ. Đây có lẽ là cách phổ biển hơn để tổ chức một hệ thống học luật. Các ví dụ
về dạng này bao gồm FOIL (Quinlan, 1990), GOLEM (Muggleton & Feng, 1992),
PROGOL (Muggleton, 1995), Claudien (De Raedt & Bruynooghe, 1993) và các hệ

thống khác dựa trên FOIL như FOCL (Pazzani, Brunk, & Silverstein, 1992), mFOIL
(Lavrac & Dzeroski, 1994) và FOIDL (Mooney & Califf, 1995).
Có sự thỏa hiệp giữa hai dạng thiết kế nói trên. Sự khác biệt chính là sự thỏa hiệp
giữa một phép tìm kiếm hiệu quả hơn hoặc một phép tìm kiếm kỹ lưỡng hơn. Các
hệ thống dạng bao phủ có xu hướng có phần hiệu quả hơn, vì chúng không tìm đến
để học các luật đối với các ví dụ mà đã được bao phủ. Tuy nhiên, phép tìm kiếm của
hệ thống dạng này ít kỹ lưỡng hơn so với các hệ thống dạng cô đọng lại, vì chúng
có thể không “thích” các luật mà vừa bao phủ các ví dụ còn lại vừa bao gộp các luật
đang tồn tại. Do đó, các hệ thống dạng bao phủ có thể kết thúc với một tập luật khá
cụ thể trong các trường hợp một phép tìm kiếm kỹ lưỡng hơn có thể đã phát hiện ra
một luật khái quát hơn bao phủ cùng một tập ví dụ.
Một vấn đề thiết kế cơ bản nữa là quyết định lựa chọn là xu hướng của phép tìm
kiếm được sử dụng để xây dựng các luật cá thể. Các hệ thống thường làm việc theo
hai hướng:

19


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

-

các hệ thống dưới-lên (từ cụ thể đến khái quát) tạo các luật rất cụ thể sau đó
khái quát các luật đó để bao phủ các ví dụ dương thêm vào;

-

các hệ thống trên-xuống (từ khái quát đến cụ thể) khởi đầu với các luật rất
khái quát, các luật tiêu biểu bao phủ tất cả các ví dụ, âm và dương, sau đó

chuyên biệt hóa các luật đó, cố gắng để không bao phủ các ví dụ âm trong khi
vẫn tiếp tục bao phủ nhiều ví dụ dương.

Trong số các hệ thống trên, DUCE, CIGOL, và GOLEM là các hệ thống dưới-lên
thuần túy, trong khi FOIL và các hệ thống dựa trên FOIL là các hệ thuần túy trênxuống. CHILLIN và PROGOL kết hợp cả hai phương pháp dưới-lên và trên-xuống.
Rõ ràng, việc lựa chọn xu hướng tìm kiếm cũng dẫn đến các thỏa hiệp. Các hệ
thống trên-xuống thường tốt hơn về việc tìm các luật khái quát bao phủ số lượng lớn
các ví dụ, vì chúng khởi đầu với một luật khái quát nhất và chuyên biệt hóa nó chỉ
đủ để tránh các ví dụ âm. Các hệ thống dưới-lên có thể tạo ra các luật quá cụ thể đến
nỗi không hoạt động tốt trên dữ liệu không so sánh được bởi vì chúng có thể không
thành công khi khái quát hóa các luật khởi đầu một cách đầy đủ. Với một không
gian tìm kiếm khá nhỏ các hằng và các mối liên hệ cơ sở thì phép tìm kiếm trênxuống có thể hiệu quả hơn. Tuy nhiên, khi hệ số rẽ nhánh cho phép tìm kiếm trênxuống rất cao (như là khi có nhiều cách để chuyên biệt hóa một luật), thì tìm kiếm
kiểu dưới-lên thường sẽ hiệu quả hơn. Các hệ thống sử dụng kết hợp cả hai kỹ thuật
tìm kiếm dưới-lên và trên-xuống sẽ cố gắng khai thác lợi thế của từng kỹ thuật.
Các phần tiếp theo sẽ giới thiệu tóm tắt về mô hình FOIL và ba mô hình mà ảnh
hưởng trực tiếp nhất tới giải thuật của RAPIER.

1.2.2. FOIL
FOIL là một ví dụ nguyên mẫu của một giải thuật ILP trên-xuống mà sử dụng giải
thuật dạng bao phủ. Nó học một định nghĩa dạng hàm tự do mệnh đề chuẩn HORN
bậc 1 của vị từ đích dưới dạng chính nó và các vị từ cơ sở khác. Đầu vào gồm có
các định nghĩa mở rộng những vị từ này thành các bộ hằng số của các kiểu cụ thể.

20


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

Chẳng hạn, một đầu vào tương thích để học một định nghĩa về danh sách thành viên

như sau:
member(Elt, Lst): { <a, [a]>, <a, [a, b]>, <b, [a, b]>, <a, [a, b, c]>, ...}
components(Lst, Elt, Lst): { <[a], a, []>, <[a, b], a, [b]>, <[a, b, c], a, [b, c]> ...}

trong đó Elt là một kiểu biểu thị các phần tử có thể tồn tại bao gồm a, b, c và d;
Lst là một kiểu được định nghĩa là bao gồm các danh sách có chứa ba trong số các
phần tử đó;
components(A,B,C) là một vị từ cơ sở mà là đúng nếu A là một danh sách mà phần
tử đầu tiên của nó là B và phần còn lại của nó là danh sách C.
FOIL cũng đòi hỏi các ví dụ âm của khái niệm đích mà có thể được cung cấp trực
tiếp hoặc được tính toán sử dụng một giả thiết đóng (closed-world assumption).
Chẳng hạn, giả thiết đóng sẽ tạo ra toàn bộ các cặp dạng <Alt, Lst> mà không được
qui định một cách rõ ràng như các ví dụ dương (ví dụ <b, [a]>). Với đầu vào này,
FOIL học chương trình một mệnh đề duy nhất vào mỗi thời điểm sử dụng giải thuật
tham lam dạng bao phủ (như mô tả trong Hình 1.4).
Khởi tạo
Definition := null
Remaining := tất cả các ví dụ dương
While Remaining không rỗng
Tìm một mệnh đề, C, mà bao phủ một số ví dụ trong Remaining,
nhưng không bao phủ các ví dụ âm.
Loại bỏ các ví dụ được bao phủ bởi C khỏi Remaining.
Thêm C vào Definition.

Hình 1.4: Giải thuật bao phủ FOIL
Chẳng hạn, một mệnh đề có thể được học cho định nghĩa member trong một bước
lặp của vòng lặp này là:
member(A,B) :- components(B,A,C).

21



LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

vì nó bao phủ tất cả các ví dụ dương có phần tử này là phần tử đầu tiên trong danh
sách mà không bao phủ bất cứ ví dụ âm nào. Một mệnh đề có thể được học để bao
phủ ví dụ còn lại là:
member(A,B) :- components(B,C,D), member(A,D).

Hai mệnh đề kết hợp cùng nhau tạo thành một chương trình đúng đắn cho định
nghĩa member.
Bước “tìm mệnh đề” được thực hiện bởi một phép tìm kiếm kiểu leo đồi từ khái
quát tới cụ thể mà bổ sung mỗi lần một “tổ tiên” vào mệnh đề đang phát triển. Tại
mỗi bước, nó đánh giá các ký hiệu mệnh đề (literal) khả dĩ mà có thể được bổ sung
và lựa chọn một literal mà cực đại hóa hàm trọng số lợi ích thông tin (informationgain). Giải thuật duy trì một tập các bộ dữ liệu mà thỏa mãn mệnh đề hiện thời và
bao gồm các ràng buộc cho bất cứ biến mới nào được đưa vào bên trong thân giải
thuật. Hình 1.5 mô tả thủ tục này.
Khởi tạo C to R(V1; V2; :::; Vk) :-. Trong đó R là vị từ mục tiêu với bậc là k.
Khởi tạo T để chứa các bộ dữ liệu dương trong positives-to-cover và tất cả
các bộ dữ liệu âm.
While T chứa các bộ dữ liệu âm
Tìm literal tốt nhất L để bổ sung vào mệnh đề.
Tạo tập vị từ mới T’ chứa thay cho mỗi bộ dữ liệu t trong T mà thỏa L,
tất cả các bộ dữ liệu có dạng t.b (t và b được nối vào nhau) trong
đó b là một tập vị từ sinh đối với các biến mới đưa vào bởi L để
cho literal này được thỏa.
Thay thế T bằng T’.

Hình 1.5: Bước “tìm mệnh đề” trong giải thuật FOIL

Các literal được đánh giá dựa trên số lượng bộ dữ liệu dương và âm được bao phủ,
ưu tiên các literal bao phủ nhiều dương hơn âm. Đặt T+ biểu thị số lượng bộ dữ liệu
dương trong tập T; thì độ đo thông tin của mệnh đề được định nghĩa là:

22


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

I(T) = -log2(T+ / |T|)
Literal được chọn là literal đạt cực đại hóa đại lượng sau:
gain(L) = s . (I(T) - I(T’))
trong đó s là số lượng bộ dữ liệu dương được L bao phủ.
Phép tìm kiếm một literal tốt để thêm vào mệnh đề có thể gây bùng nổ không gian
bài toán khi số lượng vị từ cơ sở lớn, bậc của các vị từ lớn hoặc có số lượng rất lớn
các hằng số lý thuyết (các hằng số có thể xuất hiện trong các mệnh đề).

1.2.3. GOLEM
Golem (Muggleton & Feng, 1992) cũng sử dụng một giải thuật tham lam dạng bao
phủ rất giống với của FOIL. Tuy nhiên, việc xây dựng các mệnh đề cá thể là dạng
dưới-lên, dựa trên xây dựng các phép tổng quát hóa ít khái quát nhất (LGGs - leastgeneral generalization) của nhiều mệnh đề cụ thể (Plotkin, 1970). Một mệnh đề G
bao gộp mệnh đề C nếu có một sự thay thế các biến trong G để làm cho các literal
trong G thành một tập con của các literal trong C. Nói một cách nôm na, chúng ta
có thể đưa C trở về G bằng cách ngắt bỏ một số điều kiện và thay đổi một số hằng
số thành các biến. Nếu G bao gộp C, bất cứ thứ gì có thể được chứng minh từ C
cũng có thể được chứng minh từ G, vì G áp đặt ít điều kiện hơn. Do đó G được gọi
là khái quát hơn C.
LGG của các mệnh đề C1 và C2 được định nghĩa là mệnh đề ít khái quát nhất mà
bao gộp cả C1 và C2. Một mệnh đề LGG được tính toán một cách dễ dàng bằng

cách “so khớp” các literal tương thích (để tạo thành cặp) của các mệnh đề; bất cứ
chỗ nào các literal có cấu trúc khác nhau, LGG sẽ chứa một biến. Khi nào các cặp
giống hệt nhau của các cấu trúc khác nhau xuất hiện, biến đó được sử dụng cho cặp
ở tất cả các vị trí.

23


LUẬN VĂN THẠC SỸ KHOA HỌC
ĐỀ TÀI: “HỌC MỐI QUAN HỆ TRONG TRÍCH RÚT THÔNG TIN TIẾNG VIỆT”

uncle(john,deb) :sibling(john,ron), sibling(john,dave),
parent(ron,deb), parent(ron,ben),
male(john), male(dave), female(deb).
uncle(bill,jay):sibling(bill,bruce),
parent(bruce,jay), parent(bruce,rach),
male(bill), male(jay).

Hình 1.6: Hai trường hợp cụ thể của mối quan hệ uncle
Ví dụ, hãy xem xét các mệnh đề trong Hình 1.6. Hai mệnh đề cụ thể đó mô tả khái
niệm uncle trong ngữ cảnh về các mối quan hệ gia đình nào đó đã biết. Mệnh đề
LGG phức tạp hơn của các mệnh đề đó được trình bày trong Hình 1.7.
uncle(A,B):sibling(A,C), sibling(A,D),
parent(C,B), parent(C,E), parent(C,F), parent(C,E),
male(A), male(G), male(H), male(I).

Hình 1.7: Mệnh đề LGG của các mệnh đề trong Hình 1.6
Ở đây, A thay thế cho cặp (john, bill), B thay cho cặp (deb, jay), C thay cho cặp
(ron, bruce)… Chú ý rằng kết quả chứa bốn literal parent (hai trong số đó giống hệt
nhau) tương ứng với bốn cách so khớp các cặp literal parent từ các mệnh đề ban

đầu. Tương tự, có bốn literal đối với male. Trong trường hợp xấu nhất, kết quả của
một phép tính LGG có thể chứa n2 literal cho hai mệnh đề đầu vào có độ dài n.
Trong ví dụ trên LGG không chứa literal female vì mệnh đề thứ hai không chứa
literal tương thích. Đơn giản hóa một cách dễ dàng kết quả này bằng cách loại bỏ
các literal dư thừa sẽ được mệnh đề như trong Hình 1.8.

24