Luận án Tiễn sĩ Khoa học Máy tính: Một số phương pháp phục vụ xếp hạng trang Web trong tìm kiếm xuyên ngữ Chuyên ngành Khoa học Máy tính

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG





Lâm Tùng Giang

MỘT SỐ PHƯƠNG PHÁP PHỤC VỤ XẾP HẠNG

CÁC TRANG WEB TRONG TÌM KIẾM XUYÊN NGỮ

Chuyên ngành : Khoa học máy tính

Mã số : 62 48 01 01

LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

ĐÀ NẴNG - 2017

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG



Lâm Tùng Giang

MỘT SỐ PHƯƠNG PHÁP PHỤC VỤ XẾP HẠNG

CÁC TRANG WEB TRONG TÌM KIẾM XUYÊN NGỮ

Chuyên ngành : Khoa học máy tính

Mã số : 62 48 01 01

LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

1. PGS.TS. Võ Trung Hùng

2. PGS.TS. Huỳnh Công Pháp

ĐÀ NẴNG - 2017

LỜI CAM ĐOAN

Tôi xin cam đoan: Luận án này là công trình nghiên cứu thực sự của cá nhân

tôi, được thực hiện tại Trường Đại học Bách khoa, Đại học Đà Nẵng dưới sự hướng

dẫn khoa học của PGS.TS. Võ Trung Hùng và PGS.TS. Huỳnh Công Pháp.

Các số liệu, những kết luận nghiên cứu được trình bày trong luận án này là

trung thực và chưa từng được công bố ở bất kỳ công trình nào của các tác giả khác.

Tôi xin chịu trách nhiệm về những lời cam đoan của tôi.

Tác giả,

Lâm Tùng Giang

- i -

MỤC LỤC

MỞ ĐẦU .................................................................................................................... 1

1. ĐẶT VẤN ĐỀ ....................................................................................................... 1

2. MỤC TIÊU, ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU ................................... 5

2.1. Mục tiêu ............................................................................................................ 5

2.2. Đối tượng .......................................................................................................... 5

2.3. Phạm vi ............................................................................................................. 5

3. ĐÓNG GÓP CỦA LUẬN ÁN ............................................................................... 6

4. BỐ CỤC CỦA LUẬN ÁN ..................................................................................... 8

CHƯƠNG 1: TỔNG QUAN VÀ ĐỀ XUẤT NGHIÊN CỨU .................................... 9

1.1. TRUY VẤN THÔNG TIN .................................................................................. 9

1.1.1. Khái niệm ....................................................................................................... 9

1.1.2. Định nghĩa hình thức .................................................................................... 10

1.1.3. Sơ đồ xử lý của hệ thống truy vấn thông tin .................................................. 10

1.1.4. Các mô hình truy vấn thông tin truyền thống ................................................ 12

1.1.5. Khai thác quan hệ giữa các thuật ngữ trong văn bản ..................................... 16

1.2. ĐÁNH GIÁ HỆ THỐNG TRUY VẤN THÔNG TIN ....................................... 19

1.2.1. Khái niệm ..................................................................................................... 19

1.2.2. Các độ đo ..................................................................................................... 20

1.2.3. Môi trường thực nghiệm ............................................................................... 22

1.3. TRUY VẤN THÔNG TIN XUYÊN NGỮ ........................................................ 24

1.3.1. Khái niệm ..................................................................................................... 24

1.3.2. Các hướng tiếp cận ....................................................................................... 24

1.3.3. Các kỹ thuật dịch tự động ............................................................................. 25

1.4. CÁC KỸ THUẬT XẾP HẠNG LẠI ................................................................. 25

- ii -

1.4.1. Xếp hạng và xếp hạng lại ............................................................................. 25

1.4.2. Khai thác thông tin của các máy tìm kiếm có sẵn ......................................... 26

1.4.3. Học xếp hạng ............................................................................................... 28

1.4.4. Khai thác thông tin người sử dụng ................................................................ 30

1.5. XẾP HẠNG TRANG WEB .............................................................................. 31

1.5.1. Đặc thù của tìm kiếm web ............................................................................ 31

1.5.2. Các phương pháp xếp hạng trang Web ......................................................... 32

1.5.3. Xếp hạng trang Web trong tìm kiếm xuyên ngữ ........................................... 36

1.6. CÁC HẠN CHẾ VÀ ĐỀ XUẤT NGHIÊN CỨU .............................................. 37

1.6.1. Hạn chế ........................................................................................................ 37

1.6.2. Đề xuất nghiên cứu ....................................................................................... 37

1.7. TIỂU KẾT CHƯƠNG....................................................................................... 41

CHƯƠNG 2: DỊCH TỰ ĐỘNG PHỤC VỤ TRUY VẤN XUYÊN NGỮ ................ 42

2.1. CÁC PHƯƠNG PHÁP DỊCH TỰ ĐỘNG......................................................... 42

2.1.1. Sử dụng máy dịch ......................................................................................... 42

2.1.2. Sử dụng kho ngữ liệu ................................................................................... 43

2.1.3. Sử dụng từ điển ............................................................................................ 44

2.1.4. Sử dụng ngôn ngữ trung gian ........................................................................ 44

2.1.5. Sử dụng không gian ngữ nghĩa ..................................................................... 45

2.1.6. Đánh giá chung ............................................................................................ 45

2.2. KHỬ NHẬP NHẰNG....................................................................................... 46

2.3. MÔ HÌNH SỬ DỤNG TỪ ĐIỂN MÁY ............................................................ 47

2.3.1. Xây dựng dữ liệu từ điển .............................................................................. 48

2.3.2. Khử nhập nhằng dựa trên độ đo mức độ liên quan của cặp từ ....................... 49

2.3.3. Các biến thể của công thức MI ..................................................................... 49

2.3.4. Thuật toán chọn bản dịch tốt nhất ................................................................. 51

- iii -

2.3.5. Xây dựng câu truy vấn.................................................................................. 58

2.4. THỰC NGHIỆM ÁP DỤNG CÔNG THỨC SMI ............................................. 62

2.4.1. Môi trường thực nghiệm ............................................................................... 62

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

2.5. THỰC NGHIỆM TẠO BẢN DỊCH CÂU TRUY VẤN CÓ CẤU TRÚC ......... 65

2.5.1. Môi trường thực nghiệm ............................................................................... 65

2.5.2. Cấu hình thực nghiệm .................................................................................. 65

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

2.6. TIỂU KẾT CHƯƠNG....................................................................................... 67

CHƯƠNG 3: HỖ TRỢ DỊCH CÂU TRUY VẤN .................................................... 69

3.1. CÁC KỸ THUẬT HỖ TRỢ DỊCH CÂU TRUY VẤN ..................................... 69

3.1.1. Phân đoạn câu truy vấn ở ngôn ngữ nguồn ................................................... 69

3.1.2. Mở rộng câu truy vấn ................................................................................... 70

3.1.3. Thu hẹp câu truy vấn .................................................................................... 71

3.1.4. Xử lý thuật ngữ không có trong từ điển ........................................................ 72

3.2. PHÂN ĐOẠN CÂU TRUY VẤN ..................................................................... 73

3.2.1. Sử dụng công cụ vnTagger ........................................................................... 73

3.2.2. Thuật toán WLQS ........................................................................................ 73

3.2.3. Kết hợp WLQS và công cụ vnTagger ........................................................... 75

3.3. ĐIỀU CHỈNH CÂU TRUY VẤN Ở NGÔN NGỮ ĐÍCH ................................. 78

3.3.1. Phản hồi ẩn ................................................................................................... 79

3.3.2. Phản hồi ẩn trong truy vấn xuyên ngữ .......................................................... 81

3.3.3. Điều chỉnh câu truy vấn có cấu trúc ở ngôn ngữ đích.................................... 82

3.4. THỰC NGHIỆM .............................................................................................. 86

3.4.1. Cấu hình thực nghiệm .................................................................................. 86

3.4.2. Kết quả ......................................................................................................... 87

- iv -

3.5. TIỂU KẾT CHƯƠNG....................................................................................... 89

CHƯƠNG 4: XẾP HẠNG LẠI ................................................................................. 91

4.1. HỌC XẾP HẠNG DỰA TRÊN LẬP TRÌNH DI TRUYỀN .............................. 91

4.1.1. Mô hình ứng dụng lập trình di truyền ........................................................... 93

4.1.2. Xây dựng công cụ và kết quả thực nghiệm ................................................... 94

4.1.3. Đánh giá ....................................................................................................... 96

4.2. ĐỀ XUẤT CÁC MÔ HÌNH LÂN CẬN ............................................................ 97

4.2.1. Mô hình CL-Büttcher ................................................................................... 98

4.2.2. Mô hình xếp hạng CL-Rasolofo ................................................................... 99

4.2.3. Mô hình xếp hạng CL-HighDensity ............................................................ 100

4.2.4. Thực nghiệm việc ứng dụng mô hình lân cận xuyên ngữ ............................ 101

4.3. HỌC XẾP HẠNG TRANG WEB ................................................................... 103

4.3.1. Các mô hình học xếp hạng .......................................................................... 103

4.3.2. Môi trường thực nghiệm ............................................................................. 106

4.3.3. Cấu hình thực nghiệm ................................................................................ 109

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

4.4. TIỂU KẾT CHƯƠNG..................................................................................... 110

CHƯƠNG 5: HỆ THỐNG TÌM KIẾM WEB XUYÊN NGỮ VIỆT-ANH ........... 111

5.1. THIẾT KẾ HỆ THỐNG .................................................................................. 111

5.1.1. Các thành phần hệ thống & sơ đồ thuật toán ............................................... 111

5.1.2. Dữ liệu từ điển ........................................................................................... 114

5.1.3. Dữ liệu đánh chỉ mục ................................................................................. 114

5.2. PHƯƠNG PHÁP THỰC NGHIỆM ................................................................ 115

5.3. THỰC NGHIỆM CÁC GIẢI PHÁP DỊCH CÂU TRUY VẤN ....................... 116

5.3.1. Cấu hình thực nghiệm ................................................................................ 116

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

- v -

5.3.3. Đánh giá ..................................................................................................... 119

5.4. THỰC NGHIỆM ĐIỀU CHỈNH CÂU TRUY VẤN ....................................... 119

5.4.1. Cấu hình thực nghiệm ................................................................................ 119

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

5.4.3. Đánh giá ..................................................................................................... 121

5.5. THỰC NGHIỆM XẾP HẠNG LẠI................................................................. 121

5.5.1. Cấu hình thực nghiệm ................................................................................ 122

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

5.5.3. Đánh giá ..................................................................................................... 125

5.6. ĐÁNH GIÁ HIỆU QUẢ KẾT HỢP CÁC KỸ THUẬT .................................. 125

5.7. TIỂU KẾT CHƯƠNG..................................................................................... 128

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN............................................................. 129

1. KẾT LUẬN ....................................................................................................... 129

1.1. Tóm tắt nội dung luận án ............................................................................... 129

1.2. Các kết quả đạt được ..................................................................................... 129

2. HƯỚNG PHÁT TRIỂN ..................................................................................... 132

TÀI LIỆU THAM KHẢO ..................................................................................... 133

- vi -

DANH MỤC HÌNH VẼ

Hình 1.1: Quá trình xử lý của hệ thống truy vấn thông tin .......................... 11

Hình 1.2: Biểu đồ trung bình 11 điểm ......................................................... 22

Hình 1.3: Mô hình xếp hạng tìm kiếm Web đa ngữ ..................................... 38

Hình 1.4: Sơ đồ xử lý giai đoạn truy vấn ..................................................... 39

Hình 3.1: Phân loại phương pháp mở rộng câu truy vấn .............................. 71

Hình 3.2: Phản hồi của người dùng ............................................................. 79

Hình 3.3: Phản hồi ẩn về độ phù hợp của kết quả tìm kiếm ban đầu ............ 79

Hình 3.4: Đồ thị trung bình 11 điểm ........................................................... 88

Hình 4.1: Hệ thống tìm kiếm Web đa ngữ Việt-Anh ................................. 107

Hình 5.1: Các thành phần của hệ thống tìm kiếm Web Việt - Anh ............ 111

Hình 5.2: Sơ đồ thuật toán của hệ thống .................................................... 112

Hình 5.3: So sánh các cấu hình dùng 1 bản dịch ....................................... 118

Hình 5.4: So sánh các cấu hình dùng 3 bản dịch ....................................... 119

Hình 5.5: Kết quả của 5 lần huấn luyện của các phương pháp ................... 124

Hình 5.6: Điểm MAP khi sử dụng phương án dịch Top_three_all ............. 127

Hình 5.7: Điểm MAP khi sử dụng phương án dịch Top_three_weight ...... 128

- vii -

DANH MỤC BẢNG

Bảng 1.1 Thông tin sử dụng & đặc điểm của các mô hình xếp hạng ............ 18

Bảng 2.1: Cấu hình thực nghiệm ................................................................. 63

Bảng 2.2: Kết quả thực nghiệm ................................................................... 64

Bảng 2.3: So sánh P@k và MAP các cấu hình ............................................ 66

Bảng 3.1: Điểm số MAP ............................................................................. 87

Bảng 3.2: Số lượng tài liệu phù hợp tải về .................................................. 88

Bảng 4.1 Ví dụ thuộc tính của bộ sưu tập OHSUMED ................................ 92

Bảng 4.2 So sánh giá trị MAP ..................................................................... 95

Bảng 4.3 So sánh giá trị NDCG@k ............................................................. 96

Bảng 4.4: So sánh giá trị P@k .................................................................... 96

Bảng 4.5: Điểm MAP của các cấu hình thực nghiệm ................................ 102

Bảng 4.6: Mức độ tăng hiệu quả khi áp dụng mô hình lân cận .................. 102

Bảng 4.7: Các phương án hàm distance .................................................... 105

Bảng 4.8: Kết quả thực nghiệm ................................................................. 109

Bảng 5.1: Các cấu hình đánh giá các giải pháp dịch câu truy vấn .............. 116

Bảng 5.2: So sánh các giải pháp dịch câu truy vấn .................................... 117

Bảng 5.3: Cấu hình đánh giá kết quả điều chỉnh câu truy vấn ................... 120

Bảng 5.4: So sánh các giải pháp điều chỉnh câu truy vấn .......................... 121

Bảng 5.5: Cấu hình thực nghiệm học xếp hạng ......................................... 122

Bảng 5.6: Kết quả thực nghiệm các phương pháp học xếp hạng ................ 123

Bảng 5.7: Đánh giá việc áp dụng các kỹ thuật đề xuất............................... 125

- viii -

DANH MỤC TỪ VIẾT TẮT

Average Precision AP

Cross Language Evaluation Forum CLEF

Cross Language Information Retrieval CLIR

Document frequency DF

Forum for Information Retrieval Evaluation FIRE

Genetic Programming GP

Hypertext Induced Topic Search HITS

Hyper Text Markup Language HTML

Inverse Document Frequency IDF

Information Retrieval IR

LEearning TO Rank LETOR

Language Models in Information Retrieval LMIR

Latent Sematic Indexing LSI

Mean Average Precision MAP

Mutual Information MI

Machine Readable Dictionary MRD

Normalized Discount Cumulative Gain NDCG

Pseudo-Relevance Feedback PRF

Summary Mutual Information SMI

Singular-Value Decomposition SVD

Term frequency TF

Text REtrieval Conference TREC

Universal Network Language UNL

Vector Space Model VSM

Word-Length-based Query Segmentation WLQS

WWW

Word Wide Web

- ix -

DANH MỤC THUẬT NGỮ

Anchor Mốc, neo

Authority Độ tin cậy

Average Precision Độ chính xác trung bình

Bag of Words Túi từ

Bilingual Machine Readable Dictionary Từ điển máy song ngữ

Binary Independence Retrieval – BIR Mô hình truy vấn nhị phân độc

lập

Boolean model Mô hình Boolean

Cohesion Score Điểm liên kết

Cross Language Information Retrieval - Truy vấn thông tin xuyên ngữ

CLIR

Cross-language Web Search Tìm kiếm web xuyên ngữ

Data sparsity Tính thưa thớt dữ liệu

Degree of similarity Mức độ tương tự

Discounted Cumulative Gain Độ lợi tích lũy giảm dần

Fuzzy-Logic model Mô hình lô-gic mờ

Gain Function Hàm lợi ích

Hub Trung tâm

Hyper Text Markup Language-HTML Ngôn ngữ siêu văn bản

Hyperlink Siêu liên kết

Information Retrieval – IR Truy vấn thông tin

Inverse document frequency – IDF Tần suất tài liệu nghịch đảo

IR model Mô hình truy vấn thông tin

Language Model – LMIR Mô hình ngôn ngữ

Latent Sematic Indexing - LSI Mô hình chỉ mục ngữ nghĩa ngầm

Learning to Rank Học xếp hạng

Loss Function Hàm tổn thất

Machine Learning - ML Học máy

- x -

Mean Average Precision Độ chính xác trung bình bình

quân

Thẻ cung cấp thông tin trang web Meta tag

Mutual Information - MI Thông tin tương hỗ

Precision Độ chính xác

Probabilistic model Mô hình xác suất

Proximity Model Mô hình lân cận

Pseudo-Relevance Feedback – PRF Phản hồi giả

Query Câu truy vấn

Recall Độ bao phủ

Regions models Mô hình vùng

Relevant information Thông tin phù hợp

Singular-Value Decomposition – SVD Phân tích giá trị đơn

Summary Mutual Information Tổng thông tin tương hỗ

Term frequency – TF Tần suất xuất hiện của thuật ngữ

trong tài liệu

Three-way data dữ liệu 3 hướng

True Relevance Feedback Phản hồi thực sự

Two-way data dữ liệu 2 hướng

Vector Space model – VSM Mô hình không gian vec-tơ

Word-length-based Query Segmentation Phân đoạn câu truy vấn dựa trên

độ dài từ

World Wide Web Mạng lưới thông tin toàn cầu

- xi -

MỞ ĐẦU

1. ĐẶT VẤN ĐỀ

Hơn hai mươi năm qua, chúng ta chứng kiến sự phát triển và lớn mạnh vượt

bậc của Internet và World Wide Web. Đến cuối năm 2015, chỉ riêng Google đã đánh chỉ mục được khoảng 47 tỷ trang web1. Bên cạnh kích thước khổng lồ, sự tăng

trưởng của World Wide Web còn thể hiện ở tính đa dạng của các ngôn ngữ được sử

dụng trong các trang web. Đến thời điểm này, tiếng Anh tiếp tục là ngôn ngữ phổ

biến nhất, được sử dụng tại 54% trong tổng số các website, tiếp theo là tiếng Nga và

tiếng Đức, tương ứng là 6,1% và 5,7%. Riêng tiếng Việt được sử dụng tại khoảng 0,6% tổng số các website2.

Cùng với sự đa dạng về ngôn ngữ, việc tìm kiếm thông tin không còn giới

hạn ở tiếng mẹ đẻ của người dùng mà đã được mở rộng ra các ngôn ngữ khác. Bài

toán tìm kiếm web xuyên ngữ (Cross-Language Web Search) đặt ra nhiệm vụ từ

nhu cầu thông tin của người dùng được trình bày ở một ngôn ngữ (gọi là ngôn ngữ

nguồn), thực hiện việc xác định các trang web phù hợp được viết bằng một ngôn

ngữ khác (gọi là ngôn ngữ đích). Việc giải quyết bài toán có ý nghĩa thực tế, cho

phép người sử dụng truy cập các nguồn tài nguyên thông tin ở các ngôn ngữ khác

nhau [134].

Nền tảng công nghệ để giải quyết bài toán tìm kiếm web xuyên ngữ là sự kết

hợp các kỹ thuật áp dụng trong truy vấn thông tin xuyên ngữ (Cross-language

Information Retrieval - CLIR) - một lĩnh vực con của truy vấn thông tin

(Information Retrieval - IR) - và việc khai thác các đặc thù riêng của các trang web.

Truy vấn thông tin quan tâm vấn đề tìm kiếm thông tin phù hợp hay tài liệu

chứa các thông tin như vậy dựa trên nhu cầu thông tin của người sử dụng từ một tập

hợp lớn các tài liệu (được gọi là kho tài liệu). Nhu cầu thông tin được biểu diễn

1 http://www.worldwidewebsize.com/ (truy cập 26/12/2015) 2 http://w3techs.com/technologies/overview/content_language/all (truy cập 26/12//2015)

dưới dạng câu truy vấn. Một tài liệu được coi là phù hợp nếu chứa thông tin phù

- 1 -

hợp với câu truy vấn. Mặc dù sự phù hợp là một khái niệm quan trọng trong truy

vấn thông tin và được đề cập tới trong mọi nghiên cứu liên quan, cho đến nay vẫn

tồn tại các cách hiểu khác nhau về thuật ngữ này [12], [105]. Một cách lý tưởng,

một hệ thống truy vấn thông tin cần có khả năng xác định các tài liệu phù hợp dựa

trên nội dung, ý nghĩa của tài liệu và câu truy vấn chứ không phải dựa theo cách

biểu diễn của chúng. Ví dụ, từ câu truy vấn "các thảm họa thiên nhiên", cần lọc ra

các tài liệu chứa các thông tin liên quan đến "động đất", "sóng thần", hay "núi lửa".

Tuy nhiên, trên thực tế hầu hết các hệ thống truy vấn thông tin tính toán mức độ phù

hợp của các tài liệu dựa trên cách thức biểu diễn văn bản (ví dụ thông qua các từ

khóa chứa bên trong) và chưa có khả năng phân tích ý nghĩa văn bản [4], [43],

[100]. Trong truy vấn thông tin xuyên ngữ, việc xác định tính phù hợp còn phức tạp

hơn do câu truy vấn và các tài liệu được viết bằng các ngôn ngữ khác nhau [113].

Xếp hạng trong truy vấn thông tin liên quan đến việc tạo lập kết quả khi thực

hiện một câu truy vấn ở dạng một danh sách các tài liệu theo thứ tự phù hợp với nhu

cầu truy vấn. Trong tìm kiếm web xuyên ngữ, hai vấn đề chính của việc xếp hạng

kết quả tìm kiếm bao gồm: (1) sự khác biệt về ngôn ngữ giữa câu truy vấn và các tài

liệu cần tìm kiếm; (2) nhu cầu hiển thị các tài liệu phù hợp nhu cầu truy vấn tại đầu

danh sách kết quả, tạo điều kiện truy cập thuận lợi cho người sử dụng. Nhằm giải

quyết các vấn đề này, cần thực hiện hai nhiệm vụ trọng tâm: Thứ nhất là nhiệm vụ

dịch thuật, thực hiện việc biểu diễn câu truy vấn và các tài liệu trong một không

gian chung, cụ thể là trong cùng một ngôn ngữ. Thứ hai là nhiệm vụ xếp hạng,

thông qua việc triển khai các giải pháp kỹ thuật và các thước đo, thực hiện việc

đánh giá, so sánh mức độ phù hợp giữa các tài liệu và câu truy vấn. Mục tiêu chung

của các nhiệm vụ này là nhằm nâng cao hiệu quả xếp hạng kết quả tìm kiếm.

Có nhiều thước đo khác nhau được sử dụng nhằm đánh giá các hệ thống truy

vấn thông tin, bao gồm kích thước kho tài liệu, thời gian đáp ứng, cách biểu diễn

kết quả, mức độ nỗ lực của người sử dụng, độ bao phủ, độ chính xác [26]; trong đó

hai thước đo cuối được sử dụng phổ biến nhất và được coi là các thước đo chính về

hiệu quả của một hệ thống [100], [155]. Đặc biệt, độ chính xác cao của một hệ

thống liên quan trực tiếp đến việc xếp hạng các kết quả tìm kiếm, đảm bảo các tài

- 2 -

liệu đứng đầu danh sách kết quả tìm kiếm là các tài liệu phù hợp với nhu cầu truy

vấn thông tin.

Vấn đề được quan tâm nhất trong các nghiên cứu về CLIR thường liên quan

chất lượng dịch thuật [128]. Để giải quyết vấn đề này, 3 hướng tiếp cận chủ yếu

trong CLIR là dịch câu truy vấn, dịch tài liệu hay chuyển cả câu truy vấn và các tài

liệu sang một ngôn ngữ trung gian [172]. Hướng tiếp cận phổ biến là dịch câu truy

vấn sang ngôn ngữ của các tài liệu cần tìm kiếm, sau đó sử dụng các công cụ truy

vấn đơn ngữ ở ngôn ngữ này. Công việc dịch thuật được thực hiện bằng nhiều

phương pháp khác nhau: sử dụng từ điển, sử dụng các kho ngữ liệu song song, áp

dụng công cụ dịch máy. Trong các phương pháp dịch tự động phục vụ truy vấn

thông tin xuyên ngữ, việc sử dụng từ điển để dịch câu truy vấn được áp dụng rộng

rãi nhờ tính đơn giản và sự có sẵn của các từ điển máy song ngữ (Machine Readable

Dictionary - MRD) [94], [119]. Các kết quả nghiên cứu cho thấy, do các khó khăn

gây ra bởi sự nhập nhằng ngữ nghĩa của các từ trong câu truy vấn và độ bao phủ của

từ điển, hiệu quả xếp hạng của các hệ thống CLIR dựa trên từ điển còn khá hạn chế

và phụ thuộc nhiều vào các cặp ngôn ngữ cụ thể [172]. Theo đánh giá của

Ballesteros và Croft [7], các hệ thống truy vấn xuyên ngữ dùng kỹ thuật dịch từ điển

có chất lượng dưới 60% so với các hệ thống đơn ngữ - đo bằng tỷ lệ giá trị độ chính

xác trung bình bình quân (Mean Average Precision – MAP) của hai hệ thống. Đối

với tiếng Việt, kết quả nghiên cứu của tác giả Ho Bao Quoc và các đồng sự [63] cho

thấy do ảnh hưởng của việc phân đoạn câu truy vấn cũng như chất lượng dịch thuật,

hiệu quả của hệ thống truy vấn xuyên ngữ Việt-Anh chỉ đạt 47,58% so với hệ thống

truy vấn đơn ngữ (trong khi hệ thống truy vấn xuyên ngữ Anh-Việt đạt 72,27%). Từ

đây có thể thấy, việc nghiên cứu nhằm phát triển các phương pháp tăng chất lượng

dịch câu truy vấn, đặc biệt khi ngôn ngữ câu truy vấn không phải tiếng Anh, là một

vấn đề cấp thiết và mang tính thời sự.

Bên cạnh vấn đề dịch thuật, nhiều nghiên cứu được triển khai nhằm tăng hiệu

quả xếp hạng. Hướng tiếp cận phổ biến là dựa trên các mô hình xếp hạng có sẵn

trong truy vấn đơn ngữ (thực hiện sau khi dịch câu truy vấn). Một số công trình

[11], [87], [157], [163] đề xuất tích hợp máy dịch thống kê vào mô hình xếp hạng

- 3 -

xuyên ngữ. Ngoài ra, kỹ thuật học xếp hạng cũng được áp dụng nhằm nâng cao hiệu

quả xếp hạng [96], [97], [122]. Nhìn chung, hầu hết các giải pháp xếp hạng đề xuất

được triển khai độc lập với việc nghiên cứu vấn đề dịch thuật. Việc nghiên cứu kết

nối, trao đổi thông tin giữa các mô-đun là cần thiết nhằm tăng hiệu quả của toàn hệ

thống nhưng chưa được chú ý nhiều. Trong luận án, tác giả mong muốn tiếp tục sử

dụng thông tin kết xuất từ quá trình dịch câu truy vấn phục vụ việc xếp hạng.

Tìm kiếm web có những điểm khác biệt so với truy vấn thông tin văn bản

truyền thống, vốn được áp dụng cho các hệ thống thư viện. Thứ nhất, người sử dụng

Web không có xu hướng tìm tất cả tài liệu thỏa mãn nhu cầu truy vấn, mà mong

muốn nhận được kết quả phù hợp trong khoảng 10 tài liệu đầu tiên trong danh sách

kết quả tìm kiếm [16]. Điều này đặt ra yêu cầu về độ chính xác cao đối với hệ thống

tìm kiếm Web. Thứ hai, trong cấu trúc một tài liệu siêu văn bản (Hyper Text

Markup Language - HTML) chứa các thành phần như tiêu đề, tóm tắt, nội dung.

Bên cạnh đó, nó cũng chứa các thành phần đặc biệt như hyperlinks, anchor, meta

tag. Các thành phần này có thể có mức độ tác động khác nhau trong việc tìm kiếm.

Trong các nghiên cứu [33], [70], [124], [145], việc xây dựng đa chỉ mục và gán

trọng số khác nhau cho các thành phần của trang web giúp tăng độ chính xác trong

kết quả tìm kiếm. Điều này cho thấy một hệ thống tìm kiếm web nên được thiết kế

khác biệt so với một hệ thống truy vấn thông tin văn bản truyền thống, khai thác cấu

trúc đặc thù của các tài liệu có cấu trúc, nhằm nâng cao hiệu quả tìm kiếm. Hầu hết

các giải pháp đã liệt kê đều giới hạn ở việc đề xuất gán trọng số một cách thủ công

và do đó, cần các nghiên cứu tiếp theo nhằm khắc phục các hạn chế này.

Xuất phát từ tình hình thực tiễn trên, đề tài "Một số phương pháp phục vụ

xếp hạng trang Web trong tìm kiếm xuyên ngữ" được chọn làm nội dung nghiên cứu

của luận án Tiến sĩ kỹ thuật của tác giả. Thông qua các công việc cải tiến chất lượng

dịch thuật, kết hợp thông tin của quá trình dịch thuật trong quá trình xếp hạng, đề

xuất phương án xếp hạng dựa trên việc sử dụng cấu trúc đặc thù của các trang web,

tác giả đặt mục tiêu nâng cao hiệu quả xếp hạng danh sách kết quả tìm kiếm; qua

đó, đóng góp các kết quả lý thuyết đối với các lĩnh vực nghiên cứu liên quan, cũng

- 4 -

như tạo ra khả năng ứng dụng thực tế trong việc xây dựng, triển khai các hệ thống

tìm kiếm web xuyên ngữ cho các cơ quan, tổ chức.

2. MỤC TIÊU, ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU

2.1. Mục tiêu

Luận án đặt mục tiêu đề xuất một mô hình tìm kiếm web xuyên ngữ và các

giải pháp kỹ thuật áp dụng tại các thành phần của mô hình nhằm nâng cao hiệu quả

xếp hạng danh sách kết quả tìm kiếm.

Các mục tiêu cụ thể của luận án bao gồm:

 Đề xuất các phương pháp phục vụ dịch thuật, bao gồm các kỹ thuật tiền

xử lý câu truy vấn ở ngôn ngữ nguồn, dịch câu truy vấn và xử lý câu truy vấn ở

ngôn ngữ đích;

 Đề xuất các phương pháp xếp hạng lại danh sách kết quả tìm kiếm trong

truy vấn xuyên ngữ, chú trọng việc xếp hạng các trang Web.

 Kết hợp áp dụng các giải pháp đề xuất trong một mô hình tìm kiếm web

xuyên ngữ nhằm nâng cao hiệu quả xếp hạng các tài liệu web trong danh sách kết

quả tìm kiếm, cụ thể là nâng cao độ chính xác, áp dụng cho cặp ngôn ngữ Việt-Anh.

2.2. Đối tượng

Các đối tượng nghiên cứu của luận án bao gồm:

 Các kỹ thuật dịch áp dụng trong truy vấn thông tin xuyên ngữ;

 Các kỹ thuật xử lý câu truy vấn trong truy vấn xuyên ngữ;

 Các kỹ thuật xếp hạng lại kết quả truy vấn thông tin.

2.3. Phạm vi

Với đối tượng nghiên cứu nêu trên và để đáp ứng mục tiêu nghiên cứu, luận

án xác định phạm vi nghiên cứu như sau:

 Luận án tập trung giải quyết hai bài toán dịch câu truy vấn và xếp hạng

kết quả tìm kiếm web xuyên ngữ ;

- 5 -

 Cặp ngôn ngữ được chú trọng nghiên cứu là cặp ngôn ngữ Việt-Anh; cụ

thể là với câu truy vấn tiếng Việt và các văn bản tìm kiếm được viết bằng tiếng

Anh;

 Thước đo được sử dụng nhằm đánh giá hiệu quả hệ thống tìm kiếm là độ

chính xác trung bình bình quân (Mean Average Precision - MAP) với 2 lý do chính:

thứ nhất, đây là độ đo được sử dụng phổ biến tại các nghiên cứu về truy vấn thông

tin; thứ hai, độ đo này liên quan trực tiếp tới khả năng các tài liệu đứng đầu danh

sách kết quả tìm kiếm được đánh giá phù hợp với yêu cầu truy vấn;

 Các kỹ thuật hỗ trợ truy vấn thông tin xuyên ngữ được tập trung nghiên

cứu và áp dụng bao gồm phân đoạn câu truy vấn, sử dụng phản hồi ẩn và mở rộng

câu truy vấn;

 Luận án chú trọng nghiên cứu kỹ thuật học xếp hạng dựa trên lập trình di

truyền;

 Luận án sử dụng các máy tìm kiếm đơn ngữ có sẵn và không đi sâu

nghiên cứu các vấn đề liên quan kỹ thuật được sử dụng trong các máy tìm kiếm đơn

ngữ.

3. ĐÓNG GÓP CỦA LUẬN ÁN

Trên cơ sở so sánh các kết quả đạt được với tình hình nghiên cứu hiện tại,

luận án có những đóng góp trong việc nâng cao chất lượng dịch thuật và nâng cao

hiệu quả xếp hạng lại kết quả tìm kiếm trong lĩnh vực tìm kiếm web xuyên ngữ, cụ

thể như sau:

 Đề xuất được các phương pháp khử nhập nhằng mới trong mô-đun dịch

câu truy vấn trên nền tảng của khái niệm Mutual Information về sự cùng xuất hiện

của các thuật ngữ trong văn bản (chương 2). Phương pháp thứ nhất dựa trên hàm

Summary Mutual Information (SMI) cho phép chọn một bản dịch tốt nhất cho mỗi

từ khóa truy vấn và cho kết quả tốt hơn thuật toán khử nhập nhằng greedy được sử

dụng rộng rãi [99]. Phương pháp thứ hai áp dụng thuật toán chọn bản dịch một cách

tuần tự (SeQuential Translation - SQ), xác định danh sách các bản dịch tốt nhất

- 6 -

được xếp theo thứ tự phù hợp cho mỗi từ khóa truy vấn, phục vụ việc xây dựng câu

truy vấn có cấu trúc;

 Đề xuất được phương pháp hiệu quả phục vụ tiền xử lý câu truy vấn

(chương 3). Một cách cụ thể, tác giả đã đề xuất thuật toán phân đoạn WLQS (viết

tắt của Word-length-based Query Segmentation) dựa trên độ dài của từ khóa; thuật

toán được sử dụng đồng thời cùng công cụ mã nguồn mở vnTagger [89], thực hiện

việc phân tích câu truy vấn thành các cụm từ cần dịch, đi kèm với các danh sách

bản dịch ứng viên. Kết quả này phục vụ như đầu vào cho các phương pháp khử

nhập nhằng trình bày trong chương 2;

 Đề xuất được các phương pháp phục vụ xây dựng, cải tiến câu truy vấn

tại ngôn ngữ đích (chương 3). Trên cơ sở câu truy vấn có cấu trúc được tạo lập bằng

phương pháp chọn bản dịch một cách tuần tự trình bày tại chương 2, tác giả đề xuất

mô hình hai bước dựa trên kỹ thuật phản hồi ẩn, tính toán lại trọng số các từ khóa

truy vấn và áp dụng các công thức tính toán trọng số các thuật ngữ chứa trong các

văn bản để mở rộng câu truy vấn. Thông qua thực nghiệm, tác giả xác định công

thức kết hợp trọng số tf-idf cục bộ và trọng số idf toàn cục của các từ khóa mang lại

hiệu quả tốt nhất, khi tăng điểm MAP của hệ thống lên đến 12%.

 Đề xuất được các mô hình lân cận xuyên ngữ (chương 4). Các mô hình

lân cận xuyên ngữ lần đầu tiên được xây dựng dựa trên cơ sở của các hàm xếp hạng

lân cận đơn ngữ đã có và ý tưởng xem xét các bản dịch của một từ khóa như cùng

một từ ảo. Trong luận án, điểm xếp hạng lân cận xuyên ngữ của tài liệu so với câu

truy vấn được tính toán dựa trên khoảng cách giữa các bản dịch ứng viên của các từ

khóa truy vấn. Các mô hình lân cận xuyên ngữ cho phép định nghĩa các hàm xếp

hạng mới cho máy tìm kiếm và được sử dụng trong quá trình xếp hạng lại;

 Đề xuất được phương pháp học xếp hạng dựa trên lập trình di truyền

(chương 4). Hai phương pháp học xếp hạng (giám sát và không giám sát) được áp

dụng nhằm xây dựng hàm xếp hạng tổng hợp dưới dạng tổ hợp tuyến tính của các

mô hình xếp hạng cơ sở TF-IDF, BM25 và các mô hình xếp hạng lân cận xuyên

ngữ, phục vụ việc xếp hạng lại kết quả tìm kiếm web;

 Thiết kế một mô hình tìm kiếm web xuyên ngữ cho cặp ngôn ngữ Việt-

- 7 -

Anh, tích hợp các đề xuất kỹ thuật đã nêu (chương 5). Mô hình được sử dụng nhằm

so sánh với các giải pháp kỹ thuật khác cũng như để kiểm tra tính hiệu quả tổng thể

việc kết hợp sử dụng các kỹ thuật đề xuất tại các chương 2, 3, 4.

4. BỐ CỤC CỦA LUẬN ÁN

Ngoài phần mở đầu và kết luận, luận án được tổ chức thành 5 chương với

cấu trúc như sau:

Chương 1: Tổng quan và đề xuất nghiên cứu. Chương này trình bày kết quả

nghiên cứu tổng quan về các vấn đề nghiên cứu trong luận án; thực hiện việc phân

tích, đánh giá các công trình nghiên cứu liên quan, chỉ ra một số vấn đề tồn tại. Trên

cơ sở các phân tích, đánh giá, tác giả đề xuất mô hình hệ thống tìm kiếm web xuyên

ngữ và các nội dung nghiên cứu được triển khai tại các thành phần của mô hình.

Chương 2: Dịch tự động phục vụ truy vấn xuyên ngữ. Chương này trình bày

tổng quan các phương pháp dịch tự động, bao gồm dịch máy, sử dụng từ điển và sử

dụng kho ngữ liệu. Nội dung tiếp theo trình bày các đề xuất của tác giả liên quan kỹ

thuật khử nhập nhằng phục vụ dịch câu truy vấn và kỹ thuật xây dựng câu truy vấn

có cấu trúc.

Chương 3 : Hỗ trợ dịch câu truy vấn. Chương này trình bày kết quả nghiên

cứu của tác giả liên quan việc xử lý câu truy vấn. Cụ thể, tác giả đề xuất kỹ thuật

phân đoạn câu truy vấn nhằm xác định các từ khóa ở ngôn ngữ nguồn phục vụ việc

dịch thuật cũng như kỹ thuật điều chỉnh, tối ưu câu truy vấn có cấu trúc ở ngôn ngữ

đích.

Chương 4: Xếp hạng lại. Chương 4 trình bày kết quả nghiên cứu của tác giả

về các phương pháp xếp hạng lại, bao gồm đề xuất các mô hình lân cận xuyên ngữ

và áp dụng kỹ thuật học máy phục vụ việc xây dựng hàm xếp hạng lại kết quả tìm

kiếm web.

Chương 5: Hệ thống tìm kiếm web xuyên ngữ Việt Anh. Chương 5 trình bày

thiết kế hệ thống tìm kiếm web xuyên ngữ Việt-Anh và các kết quả thực nghiệm

nhằm kiểm nghiệm ảnh hưởng của việc áp dụng các giải pháp kỹ thuật đề xuất trong

luận án cũng như so sánh hiệu quả với các giải pháp kỹ thuật khác.

- 8 -

CHƯƠNG 1 TỔNG QUAN VÀ ĐỀ XUẤT NGHIÊN CỨU

Trong chương 1, tác giả trình bày cơ sở lý thuyết, kết quả nghiên cứu tổng

quan về các vấn đề nghiên cứu trong luận án; thực hiện việc phân tích, đánh giá các

công trình nghiên cứu liên quan và chỉ ra một số hạn chế trong lĩnh vực tìm kiếm

web xuyên ngữ. Trên cơ sở các phân tích, đánh giá, tác giả đề xuất mô hình hệ

thống tìm kiếm web xuyên ngữ và xác định các nội dung nghiên cứu sẽ được triển

khai.

1.1. TRUY VẤN THÔNG TIN

1.1.1. Khái niệm

Truy vấn thông tin (Information Retrieval – IR) là ngành khoa học liên quan

đến việc phân tích, thiết kế và triển khai các hệ thống máy tính nhằm biểu diễn, tổ

chức và truy cập khối lượng lớn thông tin được số hoá. Thuật ngữ Information

Retrieval được phát biểu như sau: "truy vấn thông tin là tìm kiếm tư liệu (thường

dưới dạng tài liệu), với bản chất không có cấu trúc (thường dưới dạng văn bản)

thoả mãn được nhu cầu thông tin từ một bộ sưu tập lớn (thường được lưu trữ trong

máy tính)" [104]. Định nghĩa này đề cập đến cả hai khía cạnh hướng hệ thống và

hướng người dùng của tìm kiếm thông tin và là cơ sở phát triển các hướng nghiên

cứu và ứng dụng khác nhau.

Các hệ thống truy vấn thông tin tự động ban đầu được phát triển nhằm giúp

quản lý các hệ thống tài liệu khoa học [43]. Ngày nay, nhiều trường đại học, công ty

và thư viện sử dụng các hệ thống truy vấn thông tin phục vụ việc truy cập sách, tạp

chí và các loại tài liệu khác; các hệ thống tìm kiếm thương mại cung cấp cơ sở dữ

liệu chứa hàng triệu tài liệu trong lĩnh vực được quan tâm; ngoài ra có hàng trăm

triệu người hàng ngày thực hiện việc tìm kiếm thông tin trên World Wide Web.

Sự bùng nổ kể cả về số lượng và chủng loại thông tin trên World Wide Web

từ những năm 2000, cùng với các tiến bộ trong công nghệ phần cứng và phần mềm,

- 9 -

đã tạo ra các cơ hội cũng như các thách thức và đã biến truy vấn thông tin trở thành

một lĩnh vực nghiên cứu được đặc biệt quan tâm; kết hợp và ứng dụng kết quả của

nhiều ngành khoa học khác như xử lý ngôn ngữ tự nhiên, giao tiếp người và máy,

thiết kế giao diện.

1.1.2. Định nghĩa hình thức

Một cách hình thức, hệ thống truy vấn thông tin được mô tả như sự kết hợp

của 4 thành phần f(D,Q,F, R(q,d)) [4], trong đó:

 D là tập hợp biểu diễn lô-gíc cho các tài liệu (thành phần biểu diễn tài

liệu);

 Q là tập hợp biểu diễn lô-gíc cho nhu cầu người sử dụng (thành phần biểu

diễn truy vấn);

 F là khung cơ sở cho việc mô hình hoá biểu diễn tài liệu, biểu diễn truy

vấn và quan hệ giữa chúng (thành phần lý luận);

 R(q,d) là hàm xếp hạng, tương ứng với mỗi truy vấn qQ và một tài liệu

dD, trả lại một giá trị là số thực. Một hàm như vậy xác định thứ tự giữa các tài

liệu tương ứng với truy vấn q.

1.1.3. Sơ đồ xử lý của hệ thống truy vấn thông tin

Sơ đồ tổng quát mô tả quá trình xử lý trong một hệ thống truy vấn thông tin

được trình bày trong Hình 1.1[4].

Để đáp ứng nhu cầu truy vấn thông tin của người sử dụng, các giải pháp truy

vấn thông tin được chia thành 2 giai đoạn thực hiện độc lập:

 Giai đoạn I: Thu thập, xử lý, đánh chỉ mục, lưu trữ tài liệu.

 Giai đoạn II: Truy vấn; thực hiện việc xử lý câu truy vấn, trả về danh

sách kết quả.

Mục đích của giai đoạn I là xây dựng một cơ sở dữ liệu quản lý các tài liệu.

Các thao tác xử lý văn bản và đánh chỉ mục được thực hiện để đưa các văn bản

trong kho tài liệu vào bộ chỉ mục. Việc đánh chỉ mục cho tài liệu được thực hiện

nhằm tạo lập biểu diễn lô-gíc cho các tài liệu, đảm bảo tiết kiệm không gian lưu trữ

- 10 -

và phục vụ truy xuất nhanh. Sau khi bộ chỉ mục cho các tài liệu được định nghĩa, có

THU THẬP, XỬ LÝ, ĐÁNH CHỈ MỤC, LƯU TRỮ DỮ LIỆU

1.1: Xử lý văn bản

1.2: Đánh chỉ mục

Biểu diễn văn bản

Kho tài liệu

Bộ chỉ mục

Tài liệu tải về

Giao diện

2.3: Tìm kiếm

2.4: Xếp hạng

2.2: Xử lý truy vấn

2.1: Xử lý văn bản

Biểu diễn văn bản

Biểu diễn truy vấn

Yêu cầu thông tin

Nội dung phản hồi

Danh sách tài liệu được xếp hạng

TRUY VẤN

thể thực hiện việc truy vấn.

Hình 1.1: Quá trình xử lý của hệ thống truy vấn thông tin [4]

Trong giai đoạn II, người sử dụng được cung cấp một giao diện để thực hiện

việc trình bày yêu cầu thông tin cũng như tiếp nhận kết quả tìm kiếm. Tại giao diện,

người sử dụng xác định nhu cầu thông tin dưới dạng câu truy vấn. Các thao tác xử

lý văn bản và xử lý truy vấn được áp dụng nhằm tạo lập một dạng biểu diễn lô-gíc

cho nhu cầu thông tin của người dùng. Quá trình tìm kiếm được thực hiện bởi hệ

thống dựa trên việc so sánh biểu diễn của câu truy vấn và của các tài liệu được đánh

chỉ mục. Trước khi được trả về cho người sử dụng, các tài liệu được sắp xếp theo

thứ tự phù hợp so với nhu cầu truy vấn thông qua quá trình xếp hạng. Tiếp theo,

một quá trình xử lý thông tin phản hồi có thể được thực hiện nhằm giúp hệ thống

- 11 -

thực hiện lại các thao tác xử lý truy vấn, tìm kiếm, xếp hạng và tạo lập một danh

sách kết quả mới có chất lượng tốt hơn. Có hai loại thông tin phản hồi: phản hồi

thực sự dựa trên sự đánh giá của người dùng khi nhận được danh sách kết quả tài

liệu; ngược lại, phản hồi giả được tạo lập bằng cách khai thác thông tin từ các tài

liệu đứng đầu danh sách kết quả tìm kiếm ban đầu.

1.1.4. Các mô hình truy vấn thông tin truyền thống

Mô hình truy vấn thông tin đóng vai trò như một bản thiết kế, định nghĩa và

giải thích các nội dung công việc được thực hiện trong một hệ thống truy vấn thông

tin, bao gồm cách biểu diễn tài liệu, biểu diễn truy vấn, tính điểm xếp hạng các tài

liệu so với câu truy vấn.

Các mô hình truy vấn thông tin truyền thống bao gồm mô hình Boolean, mô

hình không gian vec-tơ, mô hình xác suất [4]. Trừ mô hình Boolean, các mô hình

khác sử dụng công thức xếp hạng mức độ phù hợp của tài liệu so với câu truy vấn;

thông qua đó người sử dụng nhận được danh sách các tài liệu được xếp hạng theo

mức độ phù hợp.

1.1.4.1 Mô hình Boolean

Mô hình Boolean là mô hình cơ bản và đơn giản dựa trên đại số Bool, sử

dụng nguyên tắc so sánh chính xác khi tìm kiếm văn bản [4]. Mỗi tài liệu và câu

truy vấn được biểu diễn dưới dạng kết hợp của các từ chứa bên trong. Ví dụ, tài liệu

D = t1 ∩ t2 ∩ t3, với t1, …t3 là các thuật ngữ chứa trong tài liệu, một câu truy vấn Q

có thể có dạng t1 ∪ t3. Tài liệu D được xác định phù hợp với câu truy vấn Q nếu và

chỉ nếu D→Q.

Điểm hạn chế lớn nhất của mô hình Boolean là nó không hỗ trợ việc xếp

hạng các văn bản, không xử lý được vấn đề đồng nghĩa và đa nghĩa, có cú pháp

phức tạp và dễ gây nhầm lẫn. Một số mở rộng của mô hình này bao gồm mô hình

vùng, coi bộ sưu tập tài liệu như một chuỗi từ liên tục, mỗi chuỗi tuỳ ý các từ nối

tiếp là một vùng [62]; mô hình lô-gic mờ gộp các từ đồng nghĩa và các từ liên quan

- 12 -

vào các nhóm với trọng lượng tương ứng tần suất xuất hiện của từ, nhằm phát huy

ưu điểm về tính đơn giản và khắc phục các hạn chế vốn có của mô hình gốc [76].

1.1.4.2 Mô hình không gian vec-tơ

Mô hình không gian vec-tơ khắc phục các hạn chế của mô hình Boolean

bằng cách gán trọng số cho các thuật ngữ trong tài liệu và câu truy vấn. Các trọng

số này được sử dụng để tính mức độ tương tự giữa tài liệu và câu truy vấn.

Ký hiệu {w1, w2,…,wn} là tập hợp các thuật ngữ được sử dụng trong các tài

liệu. Giá trị n tương ứng với kích thước tập hợp thuật ngữ. Với một văn bản dj và

⃗, ⃗ của trong mô câu truy vấn q, mức độ tương tự được ký hiệu là

hình không gian véc-tơ và được tính toán bằng cách sử dụng công thức cô-sin [4]

dưới dạng sau:

∑ ,

× ∑ ,

∑ , × , ⃗, ⃗ = cos () = = (1.1) ⃗ ∙ ⃗ ⃗ × |⃗|

, câu truy vấn q được biểu

Ở đây, tài liệu dj được biểu diễn bằng vec-tơ ⃗

và ⃗; wi,j là trọng số thuật ngữ wi trong tài liệu dj; wi,q là trọng số thuật ngữ wi trong câu truy vấn q. Giá trị công thức là một

diễn bằng vec-tơ ⃗;  là góc giữa 2 vec-tơ ⃗

số thực trong đoạn [0,1]. Các tài liệu được coi là phù hợp một phần nếu như giá trị ⃗, ⃗ vượt quá một ngưỡng xác định trước và được sắp xếp theo giá trị

⃗, ⃗. giảm dần của

Một mô hình khác do Gerard Salton đề xuất và được sử dụng rộng rãi với tên

gọi mô hình tf-idf [136]. Mô hình sử dụng chủ yếu hai thước đo về tần suất xuất

hiện của thuật ngữ trong các tài liệu và giá trị tần suất tài liệu chứa thuật ngữ để xác

định mức độ tương tự của một tài liệu so với câu truy vấn. Ký hiệu tft,d là tần suất

xuất hiện của thuật ngữ t trong tài liệu d, ký hiệu dft là tần suất tài liệu chứa thuật

ngữ t và N là tổng số tài liệu trong toàn bộ kho tài liệu, mô hình đưa ra khái niệm

tần suất tài liệu nghịch đảo idft cho thuật ngữ t như sau:

- 13 -

) (1.2) = log (

Từ đây và cùng sử dụng các ký hiệu đã được định nghĩa, công thức tf-idf xác

định mức độ tương tự (, ) của văn bản d và câu truy vấn q có dạng:

∈

(, ) = , × (1.3)

Mô hình không gian véc-tơ có nhiều ưu điểm: nó đưa ra khái niệm phù hợp

một phần; các công thức xếp hạng trình bày ở trên cho phép đồng thời xác định sự

phù hợp và phục vụ sắp xếp danh sách kết quả. Điểm hạn chế của mô hình này là

các từ khoá được giả định độc lập và mô hình không đánh giá được ngữ nghĩa của

câu truy vấn.

1.1.4.3 Mô hình xác suất

Mô hình xác suất được xây dựng dựa trên ý tưởng: dựa trên các thuộc tính

của văn bản và câu truy vấn, có thể đưa ra xác suất hay các chứng cứ thống kê về sự

phù hợp của văn bản đối với câu truy vấn. Nền tảng toán học của mô hình xác suất

là công thức Bayes tính xác suất với điều kiện có dạng như sau [53]:

(1.4) (|) = (|) × () ()

Ở đây, P(E) là xác suất của sự kiện E, P(E|F) là xác suất của sự kiện E, cho

trước sự kiện F. Với câu truy vấn Q, một tài liệu D có các xác suất P(rel│D,Q) và

P(irrel│D,Q) = 1- P(rel│D,Q) tương ứng với sự kiện phù hợp rel hoặc sự kiện

không phù hợp irrel của tài liệu so với câu truy vấn

Mô hình xác suất đơn giản nhất là mô hình truy vấn nhị phân độc lập [130]

giả định về sự độc lập của các thuật ngữ trong câu truy vấn. Trong mô hình này,

một tài liệu D được biểu diễn như tập hợp các sự kiện {x1,...,xn}, trong đó xi=1 và

xi=0 tương ứng với sự xuất hiện hay không xuất hiện của từ khóa ti trong tài liệu D..

Một trong những mô hình truy vấn xác suất được sử dụng rộng rãi hiện nay

là OKAPI BM25 [131]. Mô hình này sử dụng số lần xuất hiện của từ khóa trong tài

- 14 -

liệu, độ dài tài liệu để tính trọng số các từ khóa trong tài liệu và trong câu truy vấn.

Trong luận án sử dụng phương pháp triển khai mô hình OKAPI BM25 được trình

bày tại công trình [125] với chi tiết như sau:

Với một thuật ngữ ti, trong tài liệu d, trọng số wi của ti được tính bằng công

thức:

(1.5) = ( + 1) × +

với k1 là hằng số (được gán giá trị 1.2), tfi là tần suất xuất hiện của thuật ngữ

ti trong tài liệu d và K được tính bằng công thức:

(1.6) = × ((1 − ) + × )

Ở đây, k là hằng số (được gán giá trị 2), b là hằng số (được gán giá trị 0.9),

l là độ dài tài liệu, avdl là độ dài trung bình của các tài liệu.

Với một từ khóa ti trong câu truy vấn q, trọng số qwi được tính bằng công

thức sau:

(1.7) × ( ) = + −

trong đó qtfi là tần suất xuất hiện của từ khóa ti trong câu truy vấn, dfi là số

tài liệu chứa từ khóa ti, k3 là hằng số (được gán giá trị 1000), N là số tài liệu trong

kho tài liệu. Với câu truy vấn q chứa m từ khóa t1,…tm, điểm số scoreokapi của tài

liệu d đối với câu truy vấn q khi đó được tính bằng công thức sau:

(1.8) (, ) = ×

với giá trị wi tính theo công thức (1.5) và qwi tính theo công thức (1.7).

1.1.4.4 Mô hình ngôn ngữ

Mô hình ngôn ngữ là một ứng dụng của mô hình thống kê ngôn ngữ ứng

dụng trong lĩnh vực truy vấn thông tin [120]. Ý tưởng của mô hình ngôn ngữ là sử

- 15 -

dụng xác suất P(d|q) để xác định mức độ phù hợp của văn bản d so với câu truy vấn

q. Trong mô hình ngôn ngữ, với giả định về tính độc lập của các thuật ngữ, xác suất

văn bản d phù hợp với câu truy vấn q được ký hiệu là P(d|q) và có dạng như sau:

∈

(|) = ∝ (|) × () = (|) × () (1.9) (|) × () ()

Ở công thức trên, ký hiệu ∝ thể hiện sự tương đương của 2 biểu thức do có

thể bỏ qua xác suất P(q) ở biểu thức đầu vì giá trị này không đổi đối với mọi tài

liệu. Bên cạnh đó, có thể giả định các tài liệu được phân phối đều và suất P(d) bằng

nhau với mọi tài liệu. Xác suất P(t|d) được xác định bởi một mô hình ngôn ngữ của

tài liệu (ví dụ mô hình unigram).

1.1.5. Khai thác quan hệ giữa các thuật ngữ trong văn bản

Các mô hình đã trình bày ở phần 1.1.4 được coi là nền tảng của truy vấn

thông tin dựa trên tính phù hợp của văn bản so với câu truy vấn nhưng có hạn chế

do giả định về sự độc lập của các thuật ngữ. Một số mô hình khác được đề xuất với

mục tiêu khắc phục hạn chế này. Mô hình chỉ mục ngữ nghĩa ngầm (Latent Sematic

Indexing-LSI) và mô hình lân cận được trình bày sau đây xem xét tính phụ thuộc

lẫn nhau và mối quan hệ ngữ nghĩa giữa các thuật ngữ trong văn bản.

1.1.5.1 Mô hình chỉ mục ngữ nghĩa ngầm

Cùng sử dụng cấu trúc tính toán như mô hình không gian véc-tơ nhưng khác

biệt với giả định tính độc lập của các thuật ngữ, phương pháp chỉ mục ngữ nghĩa

ngầm LSI khai thác cấu trúc ngầm của các thuật ngữ trong văn bản [35]. Trong mô

hình này, một ma trận thuật ngữ - văn bản được sử dụng để xây dựng một không

gian "ngữ nghĩa", trong đó các thuật ngữ và văn bản có liên quan được đặt trong

cùng chiều không gian. Kỹ thuật phân tích giá trị đơn (Singular-Value

Decomposition - SVD) được sử dụng cho phép biểu diễn các văn bản trong một

không gian với số lượng chiều được thu hẹp, đảm bảo phản ánh sự liên quan giữa

thuật ngữ và văn bản, dựa trên các mẫu liên quan chính và bỏ qua các ảnh hưởng

nhỏ.

- 16 -

So với các phương pháp trình bày trong phần 1.1.4, Scott Deerwester [35]

cho rằng ưu điểm chính của LSI là khả năng trích xuất nội dung ngữ nghĩa của nội

dung và do đó giải quyết các vấn đề đồng nghĩa và đa nghĩa; bên cạnh đó các thuật

ngữ được đặt chung trong các chiều thu hẹp cũng phản ánh sự liên quan giữa các

thuật ngữ. Hạn chế của phương pháp LSI là việc tính toán giá trị SVD của ma trận

thuật ngữ - tài liệu phụ thuộc kích thước của ma trận và do đó rất tốn kém: trong ma

trận số lượng cột tương ứng số lượng tài liệu trong kho tài liệu, số lượng hàng tương

ứng số lượng thuật ngữ - tương đương kích thước của từ điển từ vựng. Chính từ hạn

chế này LSI chỉ ứng dụng hiệu quả với các bộ sưu tập tài liệu nhỏ và không thực sự

phù hợp nếu kho tài liệu thường xuyên được cập nhật.

1.1.5.2 Mô hình lân cận

Trong các mô hình truy vấn thông tin truyền thống, các tài liệu được biểu

diễn như túi từ (bag of words) và được tính điểm dựa trên các số liệu thống kê như

tần suất xuất hiện của từ, độ dài văn bản, giá trị nghịch đảo tần suất tài liệu. Hạn chế

căn bản của các mô hình này là chúng không khai thác mối liên quan giữa các thuật

ngữ xuất hiện trong câu truy vấn và trong các tài liệu. Từ một góc độ khác, khoảng

cách giữa các từ trong tài liệu là một yếu tố thể hiện mối liên quan giữa các từ. Một

cách cảm quan, nếu trong một tài liệu các từ khóa truy vấn đứng sát nhau thì tài liệu

đó sẽ phù hợp hơn đối với câu truy vấn so với một tài liệu khác chứa cùng số lượng

từ khóa truy vấn nhưng các từ này lại đứng xa nhau.

Những nghiên cứu nhằm mô hình hóa mối liên hệ giữa các từ trong văn bản

được thực hiện khá sớm. Năm 1987, Fagan [39] đề xuất hai phương pháp đánh chỉ

mục ngữ dựa trên phương pháp thống kê và phân tích cấu trúc văn bản. Sau đó,

Croft Bruce [32] đề xuất việc đánh chỉ mục ngữ như một dạng đặc biệt của mô hình

lân cận khi các từ đứng kế sát nhau.

Hai xu hướng phổ biến khác bao gồm tính điểm lân cận dựa trên đoạn và dựa

trên cặp từ [154]. Trong xu hướng thứ nhất, thuật ngữ span được định nghĩa như

một đoạn văn bản chứa tất cả các từ khóa truy vấn trong tài liệu. Điểm lân cận của

một tài liệu tương ứng với một câu truy vấn tỷ lệ thuận với số span và tỷ lệ nghịch

- 17 -

với độ dài của span [55], [150]. Trong xu hướng thứ hai, các tác giả đưa ra các công

thức để tính điểm lân cận cho từng cặp từ trong tài liệu, sau đó tính điểm lân cận

của tài liệu bằng cách cộng dồn các điểm lân cận của tất cả các cặp từ khóa truy vấn

xuất hiện trong tài liệu [19], [125]. Một mô hình lân cận có thể được áp dụng để xếp

hạng lại các tài liệu truy vấn sau lần tìm đầu tiên, hoặc có thể được xây dựng trong

quá trình đánh chỉ mục văn bản.

Bảng 1.1 mô tả các thông tin được sử dụng trong công thức xếp hạng của

mỗi mô hình xếp hạng cũng như trình bày đặc trưng nổi bật của các mô hình. Trong

số này, các mô hình TF-IDF và BM25 được sử dụng rộng rãi trong các máy tìm kiếm. Ví dụ, các máy tìm kiếm Solr3 áp dụng mô hình TF-IDF; máy tìm kiếm

SMART được sử dụng phổ biến trước đây áp dụng mô hình BM25. Máy tìm kiếm Elastic4 cho phép tùy biến chọn áp dụng mô hình TF-IDF hoặc BM25. Trong các

mô hình khai thác mối liên hệ giữa các từ khóa, mô hình LSI thường dừng ở mức độ

thử nghiệm do khối lượng tính toán lớn, mô hình lân cận chỉ giới hạn ở việc được

sử dụng như một thước đo bổ sung trong công thức xếp hạng của máy tìm kiếm do

không xem xét trực tiếp mức độ ảnh hưởng của mỗi từ khóa đối với tài liệu.

Bảng 1.1 Thông tin sử dụng & đặc điểm của các mô hình xếp hạng

Mô hình Thông tin sử dụng Đặc điểm

Boolean Sự tồn tại của từ khóa + Đơn giản

- Các từ khóa độc lập

- Không phục vụ xếp hạng

VSM - Số lần xuất hiện của từ khóa + Giá trị

trong tài liệu - Các từ khóa độc lập

- Khối lượng tính toán lớn

TF-IDF - Số lần xuất hiện của từ khóa + Đơn giản, được sử dụng phổ

trong tài liệu biến

3 http://lucene.apache.org/solr/ 4 https://www.elastic.co

- Độ dài tài liệu - Các từ khóa độc lập

- 18 -

- Số lượng tài liệu chứa từ khóa

BM25 - Số lần xuất hiện của từ khóa + Là mô hình được sử dụng phổ

trong tài liệu và trong kho tài biến

liệu - Các từ khóa độc lập

- Độ dài tài liệu - Xác định các tham số điều chỉnh

- Các tham số điều chỉnh khi khởi tạo hệ thống

LSI - Trọng số theo các chiều trong + Các văn bản được biểu diễn lại

không gian ngữ nghĩa trong không gian với số lượng

chiều thu hẹp.

+ Giảm khối lượng tính toán sau

khi đã đánh chỉ mục

- Chỉ phù hợp với kho tài liệu có

kích thước nhỏ

Lân cận - Khoảng cách giữa các từ khóa + Xem xét mối liên hệ thông qua

vị trí, khoảng cách giữa các thuật trong tài liệu

ngữ - Độ dài tài liệu

- Chỉ được sử dụng như thước đo

phụ

Ở bảng trên, trong cột đặc điểm, các ưu điểm được đánh dấu cộng (+) và các

hạn chế được đánh dấu (-) phía trước.

1.2. ĐÁNH GIÁ HỆ THỐNG TRUY VẤN THÔNG TIN

1.2.1. Khái niệm

Việc đánh giá các hệ thống truy vấn thông tin đóng vai trò quan trọng, giúp

so sánh, chọn lựa mô hình, giải pháp phù hợp cũng như phục vụ quá trình thiết kế,

phát triển và bảo trì hệ thống [100]. Công việc này liên quan đến việc xác định các

tiêu chuẩn thành công (có thể đo được) của một hệ thống. Có thể đánh giá các tính

chất như kích thước dữ liệu, tính hiệu quả truy vấn của hệ thống, hay sự thỏa mãn

và chấp nhận của người dùng thông qua thời gian thực hiện, các nỗ lực của người

dùng, hay cách thể hiện kết quả [29]. Việc đánh giá đòi hỏi sự kết hợp người sử

- 19 -

dụng trong một môi trường đánh giá nhằm tiến hành đối chiếu, so sánh các kết quả

nghiên cứu với các kiểm tra trong thực tế.

1.2.2. Các độ đo

Hai thước đo cơ bản để đánh giá chất lượng của các mô hình truy vấn thông

tin là độ chính xác và độ bao phủ, được sử dụng tương ứng với trường hợp đơn giản

nhất khi hệ thống truy vấn thông tin trả lại tập hợp các tài liệu cho một câu truy vấn.

Độ chính xác (Precision) là tỷ lệ số tài liệu phù hợp trong so với số các tài liệu

được trả về, được ký hiệu là P:

(1.10) = #_ #_

với #retrieved_relelevantdocs là số tài liệu phù hợp được trả về và

#retrieved_docs là số tài liệu được trả về.

Độ bao phủ (Recall) là tỷ lệ số tài liệu phù hợp được tải về, ký hiệu là R:

(1.11) = #_ #

với #retrieved_relelevantdocs là số tài liệu phù hợp trả về và #relevantdocs

là tổng số tài liệu phù hợp.

Độ chính xác và độ bao phủ đề cập ở trên hạn chế ở việc được sử dụng trên

tập hợp tài liệu không được sắp xếp. Các độ đo cơ sở này được mở rộng thành các

độ đo khác, phục vụ việc đánh giá chất lượng danh sách kết quả xếp hạng của các

máy tìm kiếm [100].

Độ chính xác tại mức k được tính toán nhằm xác định trong k kết quả tìm

kiếm đầu tiên, có bao nhiêu tài liệu thỏa mãn nhu cầu thông tin. Công thức độ chính

xác tại mức k ký hiệu là P@k và có dạng sau:

(1.12) @ = #()

với #relevantdocs(k) là số văn bản phù hợp trong danh sách k văn bản đầu

tiên.

- 20 -

Độ chính xác trung bình AP (Average Precision) là giá trị trung bình của

các giá trị P@k tại các mức k nhằm đánh giá hiệu quả của một câu truy vấn. Gọi

I(K) là hàm xác định đối tượng ở vị trí hạng K, nếu phù hợp thì I(K) = 1 và ngược

lại I(K) = 0, n là số tài liệu tải về bởi câu truy vấn. Công thức độ chính xác trung

∑

bình AP cho một câu truy vấn có dạng:

= (1.13) @ × () ∑ ()

Trên cơ sở các định nghĩa trên, Độ chính xác trung bình trên tất cả các

truy vấn MAP (Mean Average Precision) được định nghĩa nhằm đánh giá hiệu quả

bình quân trên tập hợp các câu truy vấn. Công thức MAP có dạng:

∑

(1.14) =

trong đó giá trị APi là độ chính xác trung bình của câu truy vấn thứ i, giá trị

m là số lượng các truy vấn.

Nếu trong một hệ thống có nhiều mức độ phù hợp khi so sánh các tài liệu với

câu truy vấn (ví dụ các mức độ 4, 3, 2, 1 tương ứng với rất phù hợp, phù hợp, liên

quan, không liên quan), với mức độ phù hợp reli của văn bản thứ i, giá trị

Discounted Cumulative Gain – DCG cho một mức xếp hạng p ký hiệu là DCGp và

được tính bằng công thức:

(1.15) 2 − 1 (1 + ) =

Trên cơ sở đó, giá trị Normalize Discounted Cumulative Gain NDCG được

tính bằng công thức:

(1.16) =

trong đó IDCG là giá trị DCG trong trường hợp kết quả đưa ra là hoàn hảo,

nhận được khi tất cả các văn bản đều được xếp đúng vị trí tương ứng với độ phù

hợp của chúng. Trong khi độ đo P@k được sử dụng khi các tài liệu chỉ được đánh

- 21 -

giá phù hợp hay không so với câu truy vấn, thước đo nDCG được áp dụng khi xem

1

0.9

0.8

0.7

0.6

0.5

xét các tài liệu có nhiều hơn 2 mức phù hợp so với câu truy vấn.

í

0.4

c á x h n h c ộ Đ

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Độ bao phủ

Hình 1.2: Biểu đồ trung bình 11 điểm

Bên cạnh các thước đo đã nêu, để mô tả sự quan hệ giữa độ chính xác và độ

bao phủ, biểu đồ trung bình 11 điểm thường được sử dụng bằng cách tính giá trị

trung bình của độ chính xác nội suy tương ứng 11 mức bao phủ (0.0, 0.1,…., 0.9,

1.0) trên một tập hợp các câu truy vấn. Hình 1.2 mô tả một ví dụ cho biểu đồ trung

bình 11 điểm.

1.2.3. Môi trường thực nghiệm

Việc nghiên cứu và phát triển các hệ thống truy vấn thông tin luôn kết hợp

với việc phát triển các mô hình, công cụ và kỹ thuật phục vụ truy vấn nhằm nâng

cao khả năng đáp ứng nhu cầu tìm kiếm thông tin của người dùng. Môi trường thực

nghiệm được xây dựng nhằm giúp cho việc kiểm tra, đánh giá cũng như hoàn chỉnh

các mô hình, công cụ và kỹ thuật [129].

Để thực hiện thực nghiệm, cần một bộ dữ liệu đánh giá, được biểu diễn như

là một tập hợp (D, Q, R, M), trong đó D là kho tài liệu được tìm kiếm, Q là tập hợp

các chủ đề được xác định trước, biểu diễn dưới dạng các câu truy vấn, R là tập kết

quả đánh giá về sự phù hợp của các tài liệu và câu truy vấn, M là thước đo hiệu quả

của hệ thống [69].

- 22 -

Bộ dữ liệu đánh giá truy vấn thông tin đầu tiên được tạo ra tại Trường Cao

đẳng Hàng không Cranfield. Tổng cộng 1400 tài liệu nghiên cứu khí động học được

xem xét, mức độ phù hợp của tất cả các tài liệu tương ứng với mỗi truy vấn được

thực hiện thủ công bởi chuyên gia [129].

Với các kho tài liệu lớn hơn, phương pháp pooling được đề xuất bởi Jones và

Van Rijsbergen được áp dụng với mục tiêu giảm số lượng các đánh giá thủ công

cần thực hiện [147]. Trong phương pháp này, với mỗi câu truy vấn, n tài liệu được

xếp hạng đầu tiên trả về bởi hệ thống truy vấn khác nhau được lựa chọn và trộn, loại

bỏ các văn bản trùng, tạo thành danh sách tài liệu cần phải được đánh giá bởi các

chuyên gia. Phương pháp này được áp dụng rộng rãi tại các hội nghị nghiên cứu

khác nhau như Text REtrieval Conference (TREC), Cross Language Evaluation

Forum (CLEF), Forum for Information Retrieval Evaluation (FIRE), NACSIS Test

Collection for Information Retrieval (NTCIR), Chinese Web Information Retrieval

Forum (CWIRF) và IR Initiative for Evaluation of XML retrieval (INEX) [106]. Tại

các hội nghị này, điểm số MAP là độ đo chính được sử dụng để đánh giá chất lượng

các hệ thống.

Trong những năm gần đây, một số nghiên cứu trong truy vấn thông tin liên

quan đến tiếng Việt đã và đang được triển khai [63], [109], [112]. Do sự khác biệt

trong cấu trúc ngữ pháp của tiếng Việt so với tiếng Anh hoặc các ngôn ngữ châu Âu

khác, các kỹ thuật mã hóa tài liệu, lập chỉ mục, so sánh tài liệu phục vụ truy vấn

thông tin cũng có những điểm khác biệt. Các bộ dữ liệu đánh giá được các tác giả

sử dụng vẫn giới hạn ở một số lượng nhỏ các câu truy vấn. Hơn nữa, các bộ dữ liệu

này chưa được công bố và chưa được cho phép sử dụng rộng rãi. Việc thiếu một

môi trường đánh giá chung gây khó khăn cho việc so sánh hiệu quả của các phương

pháp, các hướng tiếp cận khác nhau và do đó chưa thúc đẩy việc hình thành một

môi trường cộng tác cho các nhà nghiên cứu trong lĩnh vực này.

- 23 -

1.3. TRUY VẤN THÔNG TIN XUYÊN NGỮ

1.3.1. Khái niệm

Truy vấn thông tin xuyên ngữ là một lĩnh vực con của truy vấn thông tin, giải

quyết trường hợp khi tài liệu cần truy vấn được viết bằng ngôn ngữ khác với ngôn ngữ

câu truy vấn [113], [142].

Vấn đề cốt lõi trong lĩnh vực truy vấn thông tin liên quan đến việc trình bày

nội dung thông tin. Một tài liệu và một câu truy vấn có thể cùng mô tả một nội

dung, một vấn đề nhưng lại có thể được trình bày bằng các từ ngữ khác nhau. Điều

này gây khó khăn cho việc xác định tài liệu phù hợp với câu truy vấn. Đối với truy

vấn thông tin xuyên ngữ, vấn đề lại càng trở nên khó khăn hơn do sự khác biệt về

ngôn ngữ giữa câu truy vấn và các tài liệu cần tìm kiếm.

1.3.2. Các hướng tiếp cận

Để thực hiện việc xác định các tài liệu phù hợp với câu truy vấn, các giải

pháp được đề xuất đều cố gắng biểu diễn câu truy vấn và các tài liệu trong một

không gian chung, cho phép so sánh các tài liệu và câu truy vấn.

Hai hướng tiếp cận chủ yếu trong CLIR là dịch câu truy vấn và dịch tài liệu.

Trong hướng thứ nhất, câu truy vấn được dịch từ ngôn ngữ nguồn sang ngôn ngữ

đích của các tài liệu cần tìm kiếm. Hướng thứ hai thực hiện việc dịch các tài liệu ở

ngôn ngữ đích sang ngôn ngữ nguồn của câu truy vấn [172]. Bên cạnh đó, ở hướng

tiếp cận thứ ba của CLIR, cả câu truy vấn và các tài liệu được chuyển sang một

ngôn ngữ trung gian phục vụ việc so sánh và đánh giá.

Hướng tiếp cận dịch câu truy vấn được nghiên cứu rộng rãi và áp dụng phổ

biến nhất do tính đơn giản và hiệu quả. Hạn chế chủ yếu của hướng tiếp cận này là

vấn đề nhập nhằng nghĩa, có nguyên nhân từ sự hạn chế thông tin và ngữ cảnh trong

câu truy vấn. Từ cách nhìn này, hướng tiếp cận dịch tài liệu dựa vào các hệ thống

dịch máy tự động hứa hẹn một chất lượng cao hơn. Tuy nhiên, các kết quả nghiên

cứu cho thấy chưa có ưu thế rõ ràng của giải pháp dịch tài liệu so với dịch câu truy

- 24 -

vấn. Bên cạnh đó, việc dịch tài liệu tốn kém hơn nhiều về cả yếu tố thời gian và tài

nguyên [172].

1.3.3. Các kỹ thuật dịch tự động

Các kỹ thuật dịch được sử dụng phục vụ truy vấn thông tin xuyên ngữ được

phân thành hai nhóm: dịch trực tiếp và dịch gián tiếp [172]. Nhóm dịch trực tiếp

bao gồm các kỹ thuật sử dụng máy dịch, dựa trên các kho ngữ liệu song song hay

kho ngữ liệu so sánh, hoặc sử dụng từ điển, dựa trên các kho tri thức nhằm mô tả

văn bản. Nhóm dịch gián tiếp sử dụng ngôn ngữ trung gian để dịch văn bản. Chi tiết

các nhóm kỹ thuật được trình bày trong chương 2.

1.4. CÁC KỸ THUẬT XẾP HẠNG LẠI

1.4.1. Xếp hạng và xếp hạng lại

Trong truy vấn thông tin, thông thường việc xếp hạng được thực hiện thông

qua việc tính toán điểm số đo mức độ phù hợp giữa tài liệu và câu truy vấn, phục vụ

mục tiêu tạo lập một danh sách các tài liệu theo thứ tự giảm dần của điểm số [97].

Khi thực hiện câu truy vấn, danh sách kết quả tìm kiếm ban đầu có thể chưa

đảm bảo chất lượng hoặc chưa thực sự phù hợp với nhu cầu đa dạng của những

người dùng khác nhau. Các nghiên cứu liên quan kỹ thuật xếp hạng lại được thực

hiện nhằm tăng độ chính xác ở đầu danh sách kết quả tìm

kiếm [6], [22], [92], [123], [162].

Trong khi các kỹ thuật xếp hạng cơ sở đã trình bày liên quan nhiều đến việc

tạo lập chỉ mục hay đánh giá cho một tập hợp lớn các văn bản, quá trình xếp hạng

lại thường chỉ xem xét một số hữu hạn, có thể giới hạn ở vài chục đến vài nghìn văn

bản. Đây chính là cơ hội để có thể áp dụng các thuật toán phức tạp hơn, từ các

phương pháp thống kê, các phương pháp sử dụng phản hồi, cho đến việc áp dụng

các thuật toán xử lý ngôn ngữ tự nhiên, phân tích ngữ nghĩa, ngữ cảnh, áp dụng kỹ

thuật học máy trong việc điều chỉnh các tham số trong công thức xếp hạng, hoặc tạo

lập công thức tổng hợp các phương pháp đã nêu.

- 25 -

Một số các phương pháp xếp hạng lại danh sách kết quả tìm kiếm được trình

bày tiếp theo bao gồm:

 Khai thác thông tin của các máy tìm kiếm có sẵn;

 Học xếp hạng;

 Khai thác thông tin người sử dụng.

1.4.2. Khai thác thông tin của các máy tìm kiếm có sẵn

Kỹ thuật trộn kết quả và xếp hạng lại được sử dụng rộng rãi trong các hệ

thống tìm kiếm liên hợp [101] hoặc phân tán [20]. Các hệ thống này không lập chỉ

mục cho các văn bản mà khai thác thông tin của các máy tìm kiếm có sẵn.

1.4.2.1 Kết hợp điểm xếp hạng có sẵn

Phương pháp đơn giản nhất để trộn các kết quả xếp hạng là Raw-score, sử

dụng trực tiếp điểm xếp hạng trong từng danh sách kết quả tìm kiếm gốc [139].

Phương pháp CombSUM được đề nghị bởi Fox và Shaw, thực hiện việc lấy tổng

điểm số của văn bản trong các máy tìm kiếm khác nhau để xác định điểm xếp hạng

CombSUM cho một tài liệu [144]:

∈

= (1.17)

với IR Servers là tập hợp các máy tìm kiếm, scorei là điểm của tài liệu được

gán bởi máy tìm kiếm i.

Điểm số score được gán bởi một máy tìm kiếm có thể được chuẩn hoá thành

điểm NormalizedScore [90] để tránh sự khác biệt về chuẩn điểm của các máy tìm kiếm:

(1.18) = − −

với MinScore và MaxScore là các giá trị nhỏ nhất và lớn nhất trong điểm số

của tất cả các tài liệu được gán bởi máy tìm kiếm.

Để khắc phục hạn chế khi cộng điểm xếp hạng của các máy tìm kiếm vốn

khác nhau về chất lượng xếp hạng, cách tính điểm, cách thức trình bày, công thức

- 26 -

trộn xếp hạng với trọng số máy chủ Weighted CombSUM bổ sung các tham số tương

ứng với giá trị xếp hạng cho các máy chủ [56]. Điểm xếp hạng WeightedCombSUM

của một tài liệu được tính bằng công thức:

(1.19) ℎ = × ∈

Ở đây, wi là trọng số được gán trước cho máy tìm kiếm i trong tập hợp các

máy tìm kiếm IR Servers; NormalizedScorei là điểm chuẩn hóa của được gán bởi

máy chủ i cho tài liệu như ở công thức (1.18).

Tương tự, một số nghiên cứu [66], [159] đề xuất hàm tuyến tính kết hợp

điểm xếp hạng của các máy tìm kiếm dạng:

(1.20) (, ) = × (, )

Ở đây M(d,q) là điểm xếp hạng cuối cùng, si(d,q) là điểm xếp hạng (được

chuẩn hóa) của máy tìm kiếm i, là trọng số được gán cho máy tìm kiếm i. Điểm

hạn chế của các phương pháp này nằm ở việc phải xác định các giá trị bằng các

phương pháp thủ công hoặc dựa trên việc quan sát dữ liệu huấn luyện.

1.4.2.2 Sử dụng thông tin về thứ tự xếp hạng

Một số giải pháp sử dụng thông tin về thứ tự xếp hạng trong danh sách tìm

kiếm gốc bao gồm phương pháp Round Robin và phương pháp trộn Borda.

Phương pháp Round Robin [139] là phương pháp trộn đơn giản nhất, được

thực hiện như sau: cho m danh sách kết quả trả về từ các máy chủ tìm kiếm gốc L1,

L2, ... , Lm; trước hết ta lấy m kết quả đầu tiên là R1 từ các danh sách Li, sau đó lấy m

kết quả thứ hai là R2 từ các danh sách Li và tiếp tục như vậy. Kết quả cuối cùng của

quá trình trộn có dạng L1R1, ..., LmR1, L1R2 , ..., LmR2, ... Đây là giải pháp phù hợp

nhằm đảm bảo tốc độ tìm kiếm khi các nguồn thông tin có chất lượng tương đương.

Trên thực tế, các máy tìm kiếm quản lý các kho tài liệu với chất lượng khác nhau và

cách thức xếp hạng khác nhau và khi đó phương pháp trộn này trở nên không phù

hợp.

- 27 -

Phương pháp trộn Borda [66] sử dụng điểm đánh giá của các chuyên gia.

Mỗi chuyên gia xếp hạng một số lượng c tài liệu. Với mỗi chuyên gia, tài liệu đứng

đầu được tính c điểm, tài liệu thứ hai được gán c-1 điểm và cứ thế tiếp tục. Nếu có

một số tài liệu không được xếp hạng, điểm còn lại được chia đều cho tất cả các tài

liệu không xếp hạng. Cuối cùng, các tài liệu được xếp hạng theo dựa trên tổng số

điểm được gán.

Các phương pháp trộn sử dụng thông tin về thứ hạng hữu dụng trong trường

hợp không có thông tin về điểm xếp hạng của các máy tìm kiếm. Tuy nhiên, các

nghiên cứu cho thấy phương pháp trộn này không hiệu quả bằng các phương pháp

kết hợp điểm xếp hạng [126].

1.4.3. Học xếp hạng

Trong một hệ thống tìm kiếm cục bộ, các văn bản có thể được đánh chỉ mục

theo nhiều phương pháp khác nhau (VSM, LSI, LMIR,..) như đã trình bày tại phần

1.1.4 và 1.1.5. Điểm xếp hạng của văn bản so với câu truy vấn theo các phương

pháp khác nhau có thể được coi như các thuộc tính (features) khác nhau của văn

bản. Các hệ thống truy vấn thông tin hiện nay có khuynh hướng áp dụng kỹ thuật

học máy (machine learning) để xác lập mô hình hoặc tạo công thức xếp hạng trên

cơ sở các thuộc tính này.

Quá trình học xếp hạng gồm 2 bước: huấn luyện và kiểm tra. Dữ liệu đầu vào

của quá trình huấn luyện là D cấu thành từ tập hợp { }, trong đó q là câu

truy vấn, d là văn bản được biểu diễn dưới dạng danh sách các thuộc tính

{f1,f2,...,fm}, r là mức độ phù hợp của văn bản d so với truy vấn q. Bước huấn luyện

thực hiện việc xây dựng một mô hình xếp hạng F, dựa trên cơ sở dữ liệu huấn luyện

xác định mối liên hệ giữa các thuộc tính của văn bản với mức độ phù hợp của văn

bản so với câu truy vấn. Tại bước kiểm tra, mô hình xếp hạng được áp dụng trên bộ

dữ liệu thực nghiệm T cấu thành từ tập hợp {}, giá trị rpredict là mức

độ phù hợp văn bản dtest đối với truy vấn qtest - được tính toán bởi mô hình xếp hạng

F - sẽ được so sánh với giá trị rtest để đánh giá chất lượng của mô hình xếp hạng. Dữ

liệu phục vụ huấn luyện D và dữ liệu phục vụ thực nghiệm T thường được tạo lập

- 28 -

bằng cách biên tập các kết quả tìm kiếm trong thực tế, sau đó được đánh giá thủ

công bởi các chuyên gia.

Các phương pháp học xếp hạng thường có chung một cách tiếp cận thông

qua việc tối ưu hóa hàm mục tiêu: tìm giá trị cực đại của hàm lợi ích (gain function)

hoặc tìm giá trị cực tiểu của hàm tổn thất (loss function).

Các kỹ thuật học xếp hạng được chia thành 3 nhóm: point-wise, pair-wise và

list-wise [97]. Với cách tiếp cận point-wise, mỗi đối tượng huấn luyện tương ứng

với một văn bản được gán kèm theo giá trị xếp hạng. Quá trình học thực hiện tìm

một mô hình có thể ánh xạ mỗi đối tượng tới một giá trị xếp hạng gần với giá trị

thật của nó. Cách tiếp cận pair-wise sử dụng các cặp văn bản kèm theo quan hệ thứ

tự xếp hạng (trước hoặc sau) như các đối tượng huấn luyện. Trong cách tiếp cận

list-wise, đối tượng huấn luyện là bản thân danh sách các văn bản đã được xếp hạng

tương ứng với câu truy vấn.

Đại diện đặc trưng của nhóm giải pháp point-wise là PRank được giới thiệu

bởi K.Crammer và Y.Singer [30] thông qua sử dụng phương pháp phân tích hồi

quy.

Trong nhóm pair-wise, Herbrich [60] và Joachims [68] xây dựng thuật toán

xếp hạng RankSVM với mục tiêu giảm thiểu sai lệch trong danh sách các cặp sắp

xếp. Phương pháp này thường được tham chiệu trong các nghiên cứu như một cơ sở

để so sánh. Freund áp dụng giải pháp tăng tốc (boosting) và giới thiệu giải thuật

RankBoost [44]. Ưu điểm của phương pháp này là dễ triển khai và có thể chạy song

song để kiểm tra. Một ví dụ khác là FRank [156] do Tsai Ming Feng đề xuất được

xây dựng trên mô hình xếp hạng xác suất.

Trong phương pháp ListNet [22] do Zhe Cao và các đồng sự đề xuất, thuộc

nhóm list-wise, bản thân danh sách văn bản được coi là đối tượng huấn luyện. Các

tác giả sử dụng phương pháp xác suất để tính hàm tổn thất đối với danh sách, được

xác định bởi sự khác biệt giữa danh sách sắp xếp dự kiến và danh sách sắp xếp

đúng. Các mô hình mạng nơ-ron và Gradient Descent được sử dụng trong các thuật

toán triển khai để xác định mô hình xếp hạng.

- 29 -

Trong khi các phương pháp trình bày tại phần 1.4.2 có thể áp dụng phục vụ

trộn kết quả từ nhiều máy tìm kiếm, các phương pháp học máy trình bày tại phần

1.4.3 được áp dụng cho trường hợp hệ thống tìm kiếm cục bộ và các văn bản được

đánh chỉ mục theo nhiều phương pháp khác nhau. Theo Liu và các đồng sự [98],

các phương pháp học xếp hạng với dữ liệu huấn luyện (gọi là học xếp hạng có giám

sát) được đánh giá hiệu quả hơn so với các phương pháp đã trình bày tại phần 1.4.2

(có thể coi là học xếp hạng không giám sát).

1.4.4. Khai thác thông tin người sử dụng

Một cách mặc định, các máy tìm kiếm web truyền thống thực hiện việc truy

vấn dựa trên từ khóa. Tuy nhiên, hai người dùng khác nhau, với chủ đề quan tâm

khác nhau, có thể dùng chung các từ khóa với mục tiêu tìm kiếm khác nhau. Để có

thể đáp ứng tốt hơn nhu cầu tìm kiếm của cá nhân người dùng, thông tin khai báo

của người sử dụng, thói quen hành vi của người dùng trong quá trình thao tác tìm

kiếm đã trở thành một đối tượng nghiên cứu phục vụ cá nhân hóa kết quả xếp hạng

[52], [158] hay xếp hạng hợp tác [24].

Việc cá nhân hóa kết quả xếp hạng thực hiện việc truy vấn thông tin và xếp

hạng kết quả cho người sử dụng dựa trên mối quan tâm riêng biệt của từng người sử

dụng và được thực hiện thông qua hai quá trình : (1) thu thập thông tin mô tả mối

quan tâm của người sử dụng và (2) suy luận dữ liệu thu thập nhằm dự đoán các nội

dung gần với mong muốn của người sử dụng [54].

Những giải pháp thu thập thông tin ban đầu yêu cầu người sử dụng khai báo

mối quan tâm thông tin thông qua bảng đăng ký, và người dùng có thể thay đổi

thông tin này [25], [121]. Vấn đề tồn tại của giải pháp này là người sử dụng không

muốn, hoặc gặp khó khăn khi cung cấp thông tin phản hồi về kết quả tìm kiếm cũng

như mối quan tâm của họ. Một hướng đi khác, phổ biến hơn, thực hiện việc "học",

tạo lập hồ sơ người sử dụng thông qua lịch sử tìm kiếm [152], dữ liệu nhấp chuột

(clickthough data) [149] hay các trang web đã truy cập [38] nhằm phân loại, tạo lập

nhóm các chủ đề quan tâm của người sử dụng với mục tiêu cung cấp thêm thông tin

cho việc xếp hạng. Dựa trên các dữ liệu thu thập, các tác giả xây dựng mô hình mô

- 30 -

tả và khai thác các quan hệ giữa người sử dụng, câu truy vấn và các trang Web,

phục vụ việc xếp hạng kết quả tìm kiếm phù hợp với nhu cầu người sử dụng. Về

đặc tính, các mô hình có thể giới hạn ở việc khai thác "dữ liệu 2 hướng" (two-way

data) khai thác mối quan tâm của người sử dụng đối với các chủ đề thông tin, hoặc

"dữ liệu 3 hướng" (three-way data) kết hợp thêm thông tin về các trang web [149].

Bên cạnh giải pháp sử dụng thông tin của bản thân người sử dụng đã nêu,

một số giải pháp khai thác thông tin nhóm người sử dụng, được tạo lập thông qua

việc phân tích các nội dung tìm kiếm đã được thực hiện của tập hợp nhóm người sử

dụng có chung đặc điểm (vị trí địa lý, nghề nghiệp, sở thích) hoặc có chung thói

quen tìm kiếm, ví dụ như nhóm giải pháp "lọc cộng tác" (Collaborative Filtering -

CF) [14]. Các trang web đáp ứng yêu cầu thông tin của một người trong nhóm sẽ

được coi như phù hợp đối với những người khác trong cùng nhóm.

Do tính thưa thớt của dữ liệu huấn luyện (data sparsity), thuật toán đánh chỉ

mục ngữ nghĩa ẩn (Latent Semantic Indexing) được sử dụng rộng rãi như kỹ thuật

chính phục vụ xây dựng mô hình dữ liệu nhằm tối ưu hóa cách biểu diễn cũng như

khối lượng tính toán [149].

Các phương pháp được trình bày trong phần 1.4.4 được triển khai trong điều

kiện sử dụng các tập tin log của các máy chủ tìm kiếm hoặc đòi hỏi thao tác của

người sử dụng và nằm ngoài khuôn khổ nghiên cứu của luận án.

1.5. XẾP HẠNG TRANG WEB

1.5.1. Đặc thù của tìm kiếm web

Hiện nay, tìm kiếm web được coi là đối tượng nghiên cứu trong nhiều lĩnh

vực, từ khoa học máy tính (cho các vấn đề kỹ thuật) đến xã hội nhân văn (ví dụ cho

các vấn đề liên quan thói quen, hành vi của người sử dụng) [148]. Chỉ riêng ở mức

độ kỹ thuật, tìm kiếm web có những điểm khác biệt so với truy vấn thông tin văn

bản truyền thống, vốn được áp dụng cho các hệ thống thư viện, ở nhiều khía cạnh

như cấu trúc tài liệu, cách tương tác giữa người sử dụng và cách hoạt động của hệ

thống [95].

- 31 -

Một tài liệu HTML chứa các thành phần như tiêu đề, tóm tắt, nội dung. Bên

cạnh đó, nó cũng chứa các thành phần đặc biệt như hyperlinks, anchor, meta tag.

Các thành phần này ảnh hưởng khác nhau đối với việc tìm kiếm. Ví dụ, tài liệu chứa

từ khóa truy vấn trong tiêu đề thường được coi là phù hợp hơn so với tài liệu chứa

từ khóa truy vấn trong nội dung.

Một cách truyền thống, câu truy vấn có độ dài là 2-3 từ khóa. Tuy nhiên, một

nghiên cứu của Fabio Crestani cùng đồng sự [31] cho thấy đang có xu hướng "chép

và dán" câu truy vấn trong tìm kiếm web, dẫn đến độ dài phổ biến của các câu truy

vấn (dưới dạng viết) là khoảng 7,5 đến 9,5 từ. Trong luận án, tác giả tập trung xem

xét các câu truy vấn trong nhóm này.

Trong tìm kiếm web, người sử dụng có nhu cầu về độ chính xác cao ở các tài

liệu đứng đầu danh sách kết quả, điều này khác biệt so với các hệ thống truy vấn

thông tin, vốn chú trọng nhiều đến việc tạo lập tập hợp toàn bộ các tài liệu phù hợp

với câu truy vấn [95].

1.5.2. Các phương pháp xếp hạng trang Web

1.5.2.1 Khai thác cấu trúc tập tin HTML

Việc khai thác cấu trúc tập tin HTML là một mở rộng của phương pháp

truyền thống thực hiện việc đánh chỉ mục văn bản. Trong tập tin HTML, nội dung

tương ứng với một số các thẻ được nhóm thành các lớp khác nhau và được đánh chỉ

mục riêng biệt. Bằng các phương pháp khác nhau, mức độ quan trọng của mỗi lớp

được xác định nhằm xây dựng một công thức xếp hạng, kết hợp điểm số xếp hạng

của từng lớp thành công thức xếp hạng cho tập tin HTML [2], [33], [71]. Mức độ

quan trọng của mỗi lớp có thể được xác định một cách thủ công [33], hoặc bằng

cách áp dụng kỹ thuật học máy [71].

1.5.2.2 Khai thác mức độ quan trọng của văn bản

Các thuật toán tìm kiếm trên Web phổ biến hiện nay như PageRank và HITS

tạo lập thứ tự xếp hạng dựa trên việc xem xét mối quan hệ giữa các trang web để

đánh giá mức độ quan trọng của các trang web [73], [116]. Nếu coi WWW là một

- 32 -

đồ thị, mỗi trang web có thể được coi là một đỉnh của đồ thị. Các liên kết trong

trang web được biểu diễn dưới dạng cung (có hướng) kết nối các đỉnh. Hai khái

niệm quan trọng trong đồ thị này là authority và hub. Authority tương ứng với một

văn bản có một số liên kết tới, còn hub tương ứng với văn bản có các liên kết ra bên

ngoài.

a. Thuật toán PageRank

Thuật toán PageRank được đề xuất bởi Larry Page và Sergey Brin [116]. Giá trị

PageRank được gán trước cho mỗi trang web trong quá trình tạo chỉ mục giúp khi máy

tìm kiếm tiếp nhận câu truy vấn, kết quả được trả về một cách hầu như tức thì. Mức độ

quan trọng của mỗi trang được tính dựa trên số liên kết từ các trang web khác tới nó.

Mỗi trang P được gán điểm xếp hạng r(P) và được tính bằng công thức đệ quy sau:

∈()

() = (1.21) () ||

trong đó B(P) là tập hợp các trang liên kết tới P. Với mỗi trang Q trong tập

hợp B(P), |Q| là số các liên kết ra từ trang Q, r(Q) điểm xếp hạng của trang Q.

Thuật toán PageRank được sử dụng như một thành phần quan trọng của máy tìm kiếm Google5 đồng thời với các độ đo trong truy vấn thông tin truyền thống dựa

trên nội dung tài liệu. Giá trị PageRank được tính trong quá trình tạo lập chỉ mục và

được tính trên toàn thể tập hợp tài liệu, do đó giúp giảm thời gian truy vấn. Hạn chế

của thuật toán này là nó bỏ qua việc xác định mức độ phù hợp về nội dung của các

trang. Các trang có nội dung phù hợp nhưng không liên kết ra ngoài (tới các trang

khác) lại có giá trị PageRank thấp [36] .

b. Thuật toán HITS

HITS - Hypertext Induced Topic Search - được phát triển năm 1997 bởi Jon

Kleinberg [73]. HITS coi rằng các đỉnh hub tốt sẽ chỉ tới các đỉnh authority tốt và

5 http://www.google.com (truy cập ngày 15/01/2016)

ngược lại các đỉnh authority tốt được chỉ tới từ các đỉnh hub tốt.

- 33 -

Thuật toán HITS được thực hiện theo hai bước: đầu tiên, các tài liệu có nội

dung phù hợp được tập hợp; tiếp theo, một vòng lặp được thực hiện đối với các tài

liệu này nhằm xác định điểm hub score và authority score của mỗi trang dựa trên

→

→

. Ở đây, ai và hi lần lượt là authority công thức đệ quy = ∑ ℎ và ℎ = ∑

score và hub score của trang i. Ký hiệu → nghĩa là trang i có liên kết tới trang j.

Ưu điểm của thuật toán này là giá trị xếp hạng của trang phụ thuộc vào nội

dung truy vấn và có thể được kết hợp với các độ đo trong truy vấn thông tin truyền

thống. Một số hạn chế của thuật toán bao gồm: nó cho kết quả không chính xác khi

một trang có liên kết tới rất nhiều chủ đề được xác định là trang phù hợp, tốc độ tính

toán chậm hơn so với thuật toán PageRank vì việc tính điểm cho các trang được

thực hiện sau khi truy vấn.

c. Thuật toán SimRank

Cùng cách tiếp cận với các giải pháp trên, đánh giá mức độ tương tự các

trang web dựa trên cấu trúc liên kết giữa các trang trong hệ thống chứ không dựa

trên sự giống nhau về nội dung như các giải pháp truyền thống, SimRank là giải

pháp được đề xuất bởi các tác giả G. Jeh và J. Widom [67], xác định độ giống nhau

giữa hai đỉnh trên một đồ thị. Ý tưởng chính của SimRank là “hai đỉnh là tương tự

nếu được tham chiếu (có cạnh đi tới) từ các đỉnh tương tự”, hay rộng ra “hai đối

tượng là tương tự nếu cùng có chung quan hệ với các đối tượng tương tự”. Ví dụ,

các giáo viên cùng trường, dạy các học sinh giống nhau thì tương đồng; hoặc các

bài báo có danh sách tài liệu tham khảo trùng lắp là các bài báo có tính tương đồng.

Để thực hiện việc tìm kiếm các trang Web, có thể coi các trang web là đối tượng,

các liên kết chứa bên trong các trang web được sử dụng phục vụ việc so sánh giữa

các đối tượng.

SimRank ứng dụng mô hình đồ thị để xác định mức độ tương tự giữa các đối

tượng. Đồ thị có hướng G=(V,E) chứa các đỉnh V tương ứng với các đối tượng và

các cạnh E tương ứng với quan hệ giữa các đối tượng. Với một đỉnh vV, gọi I(v)

và O(v) là tập hợp các đỉnh lân cận (tương ứng có quan hệ tới hoặc từ đối tượng v),

- 34 -

khi đó mức độ tương tự giữa 2 đối tượng a và b được xác định bằng một trong hai

|()|

|()|

công thức s1(a,b) hay s2(a,b) như sau:

(, ) = |()||()| ((), ())

|()|

|()|

Hoặc

(, ) = |()||()| ((), ())

với C1, C2 là hằng số thỏa mãn 0 ≤ C1, C2 ≤ 1; Ii(a) và Ij(b) tương ứng với các

đỉnh lân cận của a và b trong tập hợp I(v); Oi(a) và Oj(b) là các đỉnh lân cận của a

và b trong tập hợp O(v). Trường hợp đặc biệt, nếu I(a)=0 hoặc I(b)=0 thì s1(a,b) =

0; nếu O(a)=0 hoặc O(b)=0 thì s2(a,b) = 0. Ngoài ra s(a,a) = 1.

Các công thức trên được triển khai tính toán theo cơ chế vòng lặp. Xuất phát

từ giá trị gán ban đầu R0(a,b)= 0 nếu a≠b và R0(a,b)=1 nếu a=b, có thể tính giá trị

|()|

|()|

Rk+1(a,b) dựa trên giá trị Rk(a,b) bằng công thức:

(, ) = |()||()| ((), ())

Dựa trên kết quả thí nghiệm, tác giả đánh giá công thức trên hội tụ khá nhanh

và chọn thực hiện k=5 vòng lặp để xác định mức độ tương tự giữa các đối tượng.

Ngoài ra, tác giả cũng đề xuất giải pháp giảm khối tượng tính toán bằng cách chỉ

xem xét các đỉnh gần nhau trên đồ thị.

Trên cơ sở thuật toán này, các nghiên cứu khác [141], [153], [167] được thực

hiện nhằm giải quyết hạn chế “tương tự zero” (zero-similarity) của SimRank khi

tính toán mức độ tương tự của các đỉnh xa nhau, tăng ngữ nghĩa của độ đo, cũng

như đề xuất các phương pháp tính toán hiệu quả. Các kết quả nghiên cứu được ứng

dụng trong các lĩnh vực như tìm kiếm web, hệ tư vấn, phân tích trích dẫn.

- 35 -

1.5.3. Xếp hạng trang Web trong tìm kiếm xuyên ngữ

Trên môi trường Internet, Google6 vào năm 2007 đã giới thiệu công cụ

Google Language Tools hỗ trợ tìm kiếm web xuyên ngữ [23], cho phép người sử

dụng nhập câu truy vấn ở một ngôn ngữ và xác định ngôn ngữ của các tài liệu cần

tìm kiếm. Đây là một trường hợp hạn hữu của mô hình tìm kiếm và xếp hạng kết

quả tìm kiếm trang Web trong môi trường xuyên ngữ. Đến năm 2013, công cụ này

không còn hoạt động. Không có thông tin chính thức về lý do của sự kiện này.

Đối với các hệ thống máy chủ Web cục bộ, các máy chủ tìm kiếm (Search Server) phổ biến như Apache Solr7 , Elastic8, Lemur Indri9 đều giới hạn ở việc phục

vụ tìm kiếm đơn ngữ. Việc thiếu vắng một giải pháp tìm kiếm web xuyên ngữ là

một hạn chế cần được khắc phục trong bối cảnh các cơ quan, tổ chức, cơ sở đào tạo

đang nỗ lực xây dựng các kho kiến thức chứa tài liệu được viết bằng các ngôn ngữ

khác nhau và đang hết sức có nhu cầu về các giải pháp kỹ thuật hỗ trợ quản lý, vận

hành và khai thác các kho kiến thức này.

Về mặt nghiên cứu, các nhà khoa học tập trung giải quyết các vấn đề trong

truy vấn thông tin xuyên ngữ, đặc biệt là các vấn đề liên quan việc dịch thuật nhưng

lại ít quan tâm đến việc mô hình hóa các hệ thống tìm kiếm web xuyên ngữ và giải

quyết các vấn đề kỹ thuật đặc thù của mô hình này. Từ một góc nhìn, một hệ thống

tìm kiếm web xuyên ngữ có thể được phân rã thành các thành phần độc lập, tương

ứng với các chuyên ngành nghiên cứu khác nhau như xử lý ngôn ngữ tự nhiên, dịch

tự động, truy vấn thông tin, học máy. Từ một góc nhìn khác, việc nghiên cứu kết

hợp các vấn đề trong cùng một hệ thống cho phép đề xuất các giải pháp kỹ thuật đặc

thù, kết nối kết quả nghiên cứu của nhiều lĩnh vực, nhằm mục tiêu tối ưu hóa hệ

6 http://www.google.com (truy cập ngày 15/01/2016) 7 http://lucene.apache.org/solr/ (truy cập ngày 15/01/2016) 8 https://www.elastic.co/ (truy cập ngày 15/01/2016) 9 http://www.lemurproject.org/indri.php (truy cập ngày 15/01/2016)

thống.

- 36 -

1.6. CÁC HẠN CHẾ VÀ ĐỀ XUẤT NGHIÊN CỨU

1.6.1. Hạn chế

Một số hạn chế liên quan lĩnh vực tìm kiếm web xuyên ngữ, bao gồm cả xử

lý ngôn ngữ tự nhiên, dịch tự động và truy vấn thông tin, đặc biệt là các nghiên cứu

liên quan tiếng Việt, bao gồm:

 Phần lớn các nghiên cứu tập trung xử lý các tài liệu dạng văn bản thuần

túy, chưa khai thác đặc thù của tìm kiếm web là các tài liệu có định dạng HTML;

 Các nghiên cứu về dịch thuật và xếp hạng kết quả tìm kiếm có tính độc

lập, bước thực hiện sau chưa khai thác thông tin kết xuất của bước trước. Các mô

hình kết hợp các kỹ thuật này đòi hỏi sử dụng máy dịch thống kê;

 Các nghiên cứu liên quan tiếng Việt còn hạn chế, chưa thu hút được sự

quan tâm và việc công bố còn manh múm. Chất lượng dịch câu truy vấn còn chưa

cao, gây ảnh hưởng đến hiệu quả của toàn hệ thống. Tài nguyên liên quan tiếng Việt

(từ điển, công cụ phân tích câu tiếng Việt, bộ dữ liệu phục vụ thực nghiệm) còn

chưa phong phú, gây cản trở cho việc nghiên cứu.

1.6.2. Đề xuất nghiên cứu

Trên cơ sở nghiên cứu cơ sở lý thuyết cũng như phân tích thực tiễn và một số

nghiên cứu đã được triển khai, tác giả xác định 2 vấn đề cần thực hiện nghiên cứu

bao gồm vấn đề dịch thuật nhằm tạo môi trường cho phép so sánh câu truy vấn với

các tài liệu cần tìm kiếm và vấn đề cải tiến chất lượng xếp hạng, đảm bảo hệ thống

tìm kiếm được xây dựng phù hợp với loại tài liệu lưu trữ (trong trường hợp của luận

án là các tài liệu web) và đạt hiệu quả cao dựa trên các thước đo đánh giá hệ thống

đã trình bày.

1.6.2.1 Mô hình xếp hạng

Từ đây, tác giả đề xuất xây dựng mô hình xếp hạng phục vụ tìm kiếm web

xuyên ngữ. Mô hình được trình bày trong khuôn khổ bài toán cụ thể tìm kiếm web

xuyên ngữ Việt-Anh, với các cải tiến tại các thành phần chức năng và khai thác đặc

thù của tìm kiếm web.

- 37 -

Mô hình xếp hạng phục vụ tìm kiếm web xuyên ngữ mô tả tại Hình 1.3, được

xây dựng trên nền tảng sơ đồ xử lý truy vấn thông tin trình bày trong Hình 1.1 với

các điều chỉnh để phù hợp với bối cảnh kho tài liệu chứa các tập tin HTML và sự

THU THẬP, XỬ LÝ, ĐÁNH CHỈ MỤC, LƯU TRỮ DỮ LIỆU

1.1: Xử lý văn bản HTML

1.2: Tạo lập đa chỉ mục

Biểu diễn văn bản

Kho tài liệu HTML

Các bộ chỉ mục

Giao diện

2.2: Dịch câu

2.5: Xếp hạng lại

2.4: Tìm kiếm

2.3: Xử lý truy vấn

truy vấn

Bản dịch

Biểu diễn truy vấn

Biểu diễn văn bản

2.1: Tiền xử lý câu truy vấn

Danh sách tài liệu

được xếp hạng

Yêu cầu thông tin

Nội dung phản hồi

TRUY VẤN

khác biệt ngôn ngữ giữa câu truy vấn và tài liệu cần tìm kiếm.

Hình 1.3: Mô hình xếp hạng tìm kiếm Web đa ngữ

Trong mô hình, tại giai đoạn thu thập, xử lý dữ liệu, các tập tin HTML được

xử lý, phân tích thành các trường tương ứng với các thành phần nội dung trong tập

tin và được đánh chỉ mục theo các trường.

Giai đoạn truy vấn bao gồm các bước chính: tiền xử lý câu truy vấn, dịch câu

truy vấn, xử lý câu truy vấn ở ngôn ngữ đích, thực hiện tìm kiếm và cuối cùng là xếp

hạng lại (xem Hình 1.4).

- 38 -

Tiền xử lý câu truy vấn

Câu

truy vấn

Dịch câu truy vấn

Xử lý câu truy vấn

Bộ

chỉ mục

Thực hiện tìm kiếm

Xếp hạng lại

Danh sách kết quả

Hình 1.4: Sơ đồ xử lý giai đoạn truy vấn

Bước tiền xử lý câu truy vấn thực hiện việc phân tích câu truy vấn tiếng Việt

,

, …

qv thành một tập hợp ((v1,L1),(v2,L2), ….,(vn,Ln)) chứa các từ khóa tiếng Việt v1,..vn } chứa mi phương án và các danh sách bản dịch L1,…,Ln. Cụ thể = {

dịch của từ tiếng Việt vi.

Bước dịch câu truy vấn xác định các phương án dịch phù hợp cho mỗi từ

khóa tiếng Việt vi từ danh sách Li; sắp xếp các phương án dịch này theo mức độ

phù hợp và tạo lập câu truy vấn.

Bước xử lý câu truy vấn kế thừa kết quả của bước dịch câu truy vấn và

hoàn thiện câu truy vấn ở ngôn ngữ đích.

Bước thực hiện tìm kiếm sử dụng các công thức của mô hình xếp hạng

trong máy tìm kiếm nhằm lọc các tài liệu phù hợp với câu truy vấn. Bước xếp

hạng lại áp dụng các kỹ thuật nhằm sắp xếp lại danh sách kết quả tìm kiếm trả

về từ máy tìm kiếm.

- 39 -

Phân tích về mặt công nghệ, giai đoạn truy vấn thông tin trong mô hình đề

xuất bao gồm 3 nhóm thành phần kỹ thuật. Thành phần dịch thuật phục vụ việc

biểu diễn các tài liệu và câu truy vấn trong một không gian chung (cụ thể là trong

cùng một ngôn ngữ) để cho phép so sánh, xác định mức độ phù hợp. Trong luận án,

tác giả triển khai nghiên cứu phương án sử dụng từ điển. Đây là công cụ có sẵn và

có thể dễ dàng triển khai trong thực tế.

Thành phần hỗ trợ dịch thuật kết hợp các kỹ thuật phân tích, xử lý câu truy

vấn ở ngôn ngữ nguồn (ngôn ngữ câu truy vấn) trước khi dịch, rồi điều chỉnh câu

truy vấn tại ngôn ngữ đích (ngôn ngữ tài liệu) sau khi dịch nhằm tối ưu câu truy

vấn.

Sau khi thực hiện truy vấn ở ngôn ngữ đích sử dụng máy tìm kiếm, thành

phần xếp hạng lại thực hiện việc cải tiến chất lượng xếp hạng. Trong khuôn khổ

luận án, tác giả đề xuất các hàm xếp hạng cơ sở và áp dụng kỹ thuật học máy bằng

lập trình di truyền nhằm xây dựng hàm xếp hạng cuối cùng.

1.6.2.2 Xác định nội dung nghiên cứu

Để đạt mục tiêu xây dựng mô hình tìm kiếm web xuyên ngữ, các nội dung

được tác giả thực hiện nghiên cứu bao gồm:

 Các kỹ thuật dịch tự động, được trình bày ở chương 2;

 Các kỹ thuật hỗ trợ dịch câu truy vấn, được trình bày ở chương 3, bao

gồm tiền xử lý câu truy vấn tại ngôn ngữ nguồn và tối ưu hóa câu truy vấn tại ngôn

ngữ đích;

 Các phương pháp xếp hạng lại, trong đó chú trọng việc học xếp hạng,

được trình bày ở chương 4;

 Xây dựng hệ thống tìm kiếm web xuyên ngữ bằng cách tích hợp các kỹ

thuật dịch tự động, hỗ trợ dịch thuật và xếp hạng lại nhằm triển khai thực nghiệm và

đánh giá mô hình đề xuất, được trình bày trong chương 5.

- 40 -

1.7. TIỂU KẾT CHƯƠNG

Nội dung chương 1 trình bày cơ sở lý thuyết về truy vấn thông tin và truy

vấn thông tin xuyên ngữ; các độ đo phổ biến được sử dụng để đánh giá và cách thức

tạo lập môi trường đánh giá. Bên cạnh đó, tác giả giới thiệu các hướng tiếp cận

trong truy vấn thông tin xuyên ngữ, giới thiệu tổng quan về các phương pháp xếp

hạng lại kết quả tìm kiếm và vấn đề xếp hạng kết quả tìm kiếm web.

Trên cơ sở nghiên cứu cơ sở lý thuyết và phân tích các kết quả nghiên cứu đã

có, tác giả xác định 2 vấn đề cần thực hiện nghiên cứu bao gồm vấn đề dịch thuật

nhằm tạo môi trường cho phép so sánh câu truy vấn với các tài liệu cần tìm kiếm và

vấn đề cải tiến chất lượng xếp hạng. Từ đó, tác giả đề xuất một mô hình tìm kiếm

web xuyên ngữ và xác định các nội dung nghiên cứu phục vụ việc thiết kế mô hình,

bao gồm các kỹ thuật dịch tự động, các kỹ thuật hỗ trợ dịch câu truy vấn và các

phương pháp học xếp hạng lại.

- 41 -

CHƯƠNG 2 DỊCH TỰ ĐỘNG PHỤC VỤ TRUY VẤN XUYÊN NGỮ

Nội dung chương 2 trình bày nghiên cứu của tác giả liên quan các kỹ thuật

dịch tự động phục vụ truy vấn xuyên ngữ, bao gồm các phương pháp dịch khác

nhau áp dụng trong CLIR, các kỹ thuật khử nhập nhằng trong phương pháp sử dụng

từ điển. Trọng tâm của chương 2 trình bày các đề xuất của tác giả phục vụ việc dịch

câu truy vấn bằng từ điển, cụ thể là các phương pháp khử nhập nhằng nhằm chọn

các bản dịch tốt nhất cho các từ trong câu truy vấn dựa trên việc sử dụng thông tin

đo mức độ liên quan của cặp từ Mutual Information và các phương pháp xây dựng

bản dịch câu truy vấn ở ngôn ngữ đích (ngôn ngữ tài liệu cần tìm kiếm).

2.1. CÁC PHƯƠNG PHÁP DỊCH TỰ ĐỘNG

2.1.1. Sử dụng máy dịch

Sử dụng máy dịch được nhận định là một sự lựa chọn khá tự nhiên và độc

lập với mô hình tìm kiếm. Phương pháp này đặc biệt phù hợp và hiệu quả đối với

việc dịch tài liệu. Trong những năm gần đây, các hệ thống máy dịch trở nên phổ

biến và đạt được các kết quả rất khả quan. Tại hội thảo CLEF 2008, các hệ thống

CLIR sử dụng máy dịch có thể đạt hiệu quả tới 90- 99% so với hệ thống IR đơn ngữ

trên các tập tài liệu tiếng Pháp, tiếng Anh và tiếng Đức. Máy dịch Google Translate10 được đánh giá vượt trội so với các máy dịch khác [42].

Trong một thực nghiệm do tác giả tiến hành, sử dụng công cụ máy dịch

Google Translate nhằm tăng hiệu quả của truy vấn xuyên ngữ [79] cho cặp ngôn

ngữ Anh-Pháp, bên cạnh việc áp dụng kỹ thuật sử dụng phản hồi ẩn trong mô-đun

tiền xử lý câu truy vấn, tác giả dịch một số tài liệu đứng đầu danh sách kết quả tìm

kiếm ở ngôn ngữ nguồn, so sánh với các tài liệu trong kết quả tìm kiếm ở ngôn ngữ

10 http://translate.google.com (truy cập ngày 16/01/2016)

đích nhằm xếp hạng lại kết quả tìm kiếm ở ngôn ngữ đích. Kết quả thực nghiệm cho

- 42 -

thấy việc chỉ áp dụng công cụ Google Translate chưa đảm bảo cho một kết quả tìm

kiếm tốt. Việc áp dụng các kỹ thuật loại bỏ các từ phổ biến trong tập hợp các văn

bản, sử dụng phản hồi ẩn, kết xuất từ khóa để mở rộng câu truy vấn có tác dụng

nhất định trong việc tăng chất lượng xếp hạng. Đặc biệt, việc xếp hạng lại các văn

bản tiếng Pháp dựa trên nội dung các văn bản trong danh sách kết quả tìm kiếm

tiếng Anh làm tăng đáng kể chất lượng xếp hạng.

Bên cạnh các thành công, sử dụng máy dịch trong CLIR cũng có hạn chế,

đặc biệt với các ngôn ngữ không phổ biến: các hệ thống máy dịch chỉ cho ra một

phương án dịch và có thể bỏ qua một số phương án dịch khác; bên cạnh đó, các hệ

thống này đặt sự chú ý quá cao đến chính tả, vốn là một yếu tố không quan trọng

trong CLIR.

2.1.2. Sử dụng kho ngữ liệu

Văn bản song song là các văn bản có cùng nội dung, được trình bày bằng các

ngôn ngữ khác nhau. Một kho tài liệu chứa một số lượng lớn các văn bản song song

được gọi là kho ngữ liệu song song. Trong CLIR, các kho ngữ liệu so sánh được

khai thác nhằm đánh giá sự liên quan giữa các từ khóa thông qua xác suất cùng xuất

hiện của chúng trong các ngôn ngữ khác nhau để xây dựng một từ điển từ vựng

tương đương [143], [172].

Các kho ngữ liệu song song có thể được thu thập từ nhiều nguồn: các tổ chức

quốc tế định kỳ công bố các tài liệu được viết bằng nhiều thứ tiếng; các tác phẩm

văn học nổi tiếng cũng được dịch sang các ngôn ngữ khác nhau. Nhiều kỹ thuật,

công cụ được áp dụng nhằm xây dựng kho ngữ liệu song song từ WWW, trong đó

có thể kể đến các kết quả nghiên cứu của Nie và Resnik [114], [127], thực hiện đầu

tiên việc xác định các website ứng viên, phân tích nội dung chuỗi ký tự địa chỉ trang

Web, cấu trúc nội dung trang Web, sau đó so sánh các văn bản để bóc tách các cặp

tài liệu song song. Đối với tiếng Việt, các nghiên cứu của Đặng Văn Bắc và Huỳnh

Công Pháp [34], [65] cũng thực hiện các mục đích tương tự cho cặp song ngữ Việt-

- 43 -

Anh. Tác giả Ngo Quoc Hung và các đồng sự [108] công bố các công cụ tạo lập và một phần của kho ngữ liệu song ngữ Việt-Anh trên Internet11.

Hạn chế cơ bản của các kho ngữ liệu song song là chúng không có sẵn và

khó tạo lập. Thay vào đó, có thể sử dụng các kho chứa các tài liệu có chung chủ đề,

nội dung (ví dụ nhiều bài báo mạng hàng ngày cùng nói về các sự kiện xảy ra trên

thế giới) và chứa các từ khóa quan trọng tương đương ở các ngôn ngữ khác nhau,

hay nói cách khác là có thể so sánh được.

2.1.3. Sử dụng từ điển

Các từ điển máy được lưu trữ trong máy tính và có thể được khai thác như

một cơ sở dữ liệu để phục vụ việc tra cứu bản dịch của một từ ở một ngôn ngữ này

trong một ngôn ngữ khác (ví dụ từ điển Anh-Việt cho phép tra cứu bản dịch tiếng

Việt của các từ tiếng Anh).

Sử dụng từ điển là kỹ thuật phổ biến trong CLIR, chủ yếu do sự có sẵn của

các loại từ điển máy và tính chất đơn giản của việc sử dụng CLIR thông qua việc

chọn lựa bản dịch trong từ điển cho các từ khóa trong câu truy vấn để tạo lập bản

dịch câu truy vấn ở ngôn ngữ khác: có thể chọn bản dịch là phương án đầu tiên xuất

hiện trong mục từ, chọn tất cả các phương án dịch, hay sử dụng các thông tin thống

kê nhằm chọn lựa bản dịch phù hợp nhất. Kỹ thuật này tương đối đơn giản so sánh

với việc sử dụng kho ngữ liệu và có ưu điểm là thường tăng độ bao phủ (recall) của

kết quả. Các vấn đề chủ yếu cần giải quyết trong kỹ thuật sử dụng từ điển bao gồm

việc khử nhập nhằng và độ bao phủ của từ điển [94], [172].

2.1.4. Sử dụng ngôn ngữ trung gian

Ngôn ngữ trung gian thường được sử dụng khi không có các tài nguyên phục

vụ việc dịch trực tiếp giữa hai ngôn ngữ [172]. Trong trường hợp dịch chuyển tiếp,

câu truy vấn được dịch từ ngôn ngữ trung gian nhằm thực hiện việc so sánh với các

tài liệu ở ngôn ngữ đích khác với ngôn ngữ trung gian. Trong trường hợp dịch đồng

11 https://code.google.com/p/evbcorpus (truy cập ngày 16/01/2016)

thời, cả câu truy vấn và tài liệu đều được dịch sang ngôn ngữ trung gian.

- 44 -

Ngôn ngữ trung gian có thể là một ngôn ngữ phổ biến (thường là tiếng Anh),

hoặc là hệ thống các khái niệm như các ontology hay ngôn ngữ UNL. Trong một số

giải pháp, Wikipedia cũng được sử dụng như một ngôn ngữ trung gian: câu truy vấn

và các tài liệu được biểu diễn thông qua các tài liệu trong Wikipedia và sau đó sử

dụng các liên kết ngôn ngữ để tính toán độ phù hợp [59], [110], [111].

Các nghiên cứu [75], [93] cho rằng chất lượng các hệ thống truy vấn xuyên

ngữ sử dụng ngôn ngữ trung gian làm công cụ dịch phụ thuộc vào tài nguyên phục

vụ dịch (kho ngữ liệu song song, từ điển). Nếu có đủ tài nguyên, các hệ thống này

có thể có chất lượng gần bằng (nhưng không vượt) các hệ thống dịch trực tiếp.

2.1.5. Sử dụng không gian ngữ nghĩa

Nhằm tiến tới một giải pháp CLIR chung cho nhiều ngôn ngữ và vượt qua

hạn chế về nhập nhằng ngữ nghĩa, một hướng tiếp cận mới được đề xuất dựa trên

việc biểu diễn văn bản và câu truy vấn không phải bằng các từ khóa chứa bên trong,

mà bởi các khái niệm trong một không gian ngữ nghĩa. Các khái niệm trong không

gian này được thiết lập quan hệ ngữ nghĩa, trên cơ sở đó xây dựng sự tương tự ngữ

nghĩa giữa các tài liệu, hay giữa câu truy vấn và tài liệu cần tìm kiếm. Những kỹ

thuật nằm trong hướng tiếp cận này bao gồm sử dụng các trang liên kết ngôn ngữ

trong Wikipedia [59], [110], [111], sử dụng Ontology [58],[64], [164], hay sử

dụng ngôn ngữ UNL [107].

2.1.6. Đánh giá chung

Nhằm xử lý sự khác biệt ngôn ngữ giữa câu truy vấn và tài liệu trong CLIR,

nhiều kỹ thuật dịch được đề xuất. Trong mọi trường hợp, yếu tố tài nguyên phục vụ

dịch thuật (độ bao phủ của từ điển, kích thước và chất lượng của kho ngữ liệu song

song hay có thể so sánh) đóng vai trò then chốt đối với chất lượng dịch thuật.

Các giải pháp sử dụng máy dịch, sử dụng kho ngữ liệu hay sử dụng không

gian ngữ nghĩa có các hiệu quả nhất định, tuy nhiên việc xây dựng đòi hỏi các kho

ngữ liệu lớn, có chất lượng. Nhằm tránh khó khăn này, luận án chọn hướng tiếp cận

sử dụng từ điển số và tập trung giải quyết vấn đề nhập nhằng ngữ nghĩa.

- 45 -

2.2. KHỬ NHẬP NHẰNG

Khi triển khai phương pháp sử dụng từ điển song ngữ, ba vấn đề chính có

khả năng gây ảnh hưởng giảm hiệu quả của hệ thống bao gồm độ bao phủ của từ

điển, việc phân đoạn câu truy vấn thành các phần có nghĩa và việc xác định bản

dịch phù hợp [119]. Theo Ballesteros và Croft [8], xuất phát từ các nguyên nhân

này, các hệ thống truy vấn xuyên ngữ dùng kỹ thuật dịch từ điển có chất lượng dưới

60% so với các hệ thống đơn ngữ (đo bằng tỷ lệ giá trị MAP của hai hệ thống). Gao

Jianfeng và các đồng sự cũng có một kết luận tương tự [49]. Khử nhập nhằng chính

vì thế là một ứng dụng quan trọng trong truy vấn thông tin xuyên ngữ.

Có hai nhóm giải pháp khử nhập nhằng: dựa trên học máy hoặc dựa trên từ

điển [138]. Trong nhóm giải pháp dựa trên học máy, hệ thống được huấn luyện dựa

trên các kho ngữ, thông tin về cách kết hợp từ, tính chất cùng xuất hiện của các từ

lân cận nhằm xây dựng các mô hình xác suất, thống kê hay bộ luật phục vụ khử

nhập nhằng. Nhóm giải pháp thứ hai dựa vào các quan hệ ngữ nghĩa được định

nghĩa trong các từ điển như Wordnet [151], hay các cơ sở dữ liệu đặc biệt về từ

vựng.

Tác giả Nguyen Han Doan [109] sử dụng mô hình xác suất để triển khai kỹ

thuật khử nhập nhằng. Cho câu truy vấn tiếng Việt được biểu diễn dưới dạng tập

hợp các từ khóa (v1,…,vn) và các bản dịch ứng viên có dạng (e1,…,en), trong đó ei là

bản dịch của vi. Xác suất P(E) = P(e1,…,en) của việc lựa chọn bản dịch (e1,…,en)

được ước lượng bằng công thức:

(2.1) (, , … , ) = () (|)

Trong đó, P(e) là xác suất thuật ngữ e xuất hiện trong kho tài liệu huấn

luyện, P(e|e’) được xác định bằng công thức:

(2.2) (|′) = max , 0 + () × () (, ) − 1

- 46 -

Với f(e,e’) là tần suất hai thuật ngữ e và e’ cùng xuất hiện trong kho tài liệu.

N là số thuật ngữ xuất hiện trong kho tài liệu huấn luyện.

Tác giả Hồ Bảo Quốc và các đồng sự [63] đề xuất kết hợp cả hai kỹ thuật sử

dụng từ điển và kho ngữ liệu song song. Đầu tiên một kho ngữ liệu song song

Anh-Việt được tạo lập, chứa 120.000 cặp câu song song. Một mô hình dịch xác suất

được huấn luyện dựa trên kho ngữ liệu này bằng cách sử dụng mô hình dịch

IBM1 [17]. Từ khóa truy vấn đầu tiên được tìm trong từ điển và nếu xuất hiện nhiều

hơn một phương án, mô hình dịch xác suất được sử dụng để chọn bản dịch phù hợp.

Trong nghiên cứu [63], các tác giả không chú trọng việc phân đoạn câu truy vấn nên

kết quả đạt được còn chưa cao. Điểm MAP của hệ thống truy vấn xuyên ngữ Việt-

Anh chỉ bằng 47,58% so với hệ thống truy vấn đơn ngữ.

Các tác giả Zhou và Gao [47], [171] đề xuất xây dựng mô hình dịch dưới

dạng đồ thị, với đỉnh biểu diễn các phương án dịch và các cạnh mô tả quan hệ giữa

các phương án này, nhằm xác định xác suất liên kết của các phương án dịch, từ đó

xác định tập hợp các bản dịch phù hợp nhất. Hạn chế lớn nhất của các mô hình này

là khối lượng tính toán lớn kể cả khi câu truy vấn ngắn, mô hình được đơn giản hóa

thông qua việc giả định chỉ xác định xác suất liên kết giữa các cặp từ.

Một phương pháp khác, khai thác các thông tin thống kê về việc “cùng xuất

hiện” của các từ khóa trong văn bản được sử dụng bởi các tác giả Ballesteros, Gao

và Mirna [9], [48], [103] nhằm chọn lựa bản dịch cho các từ khóa truy vấn. Giả

thuyết đứng sau nhóm kỹ thuật này là bản dịch đúng của các từ khóa trong câu truy

vấn thường cùng xuất hiện trong một phần của văn bản (cùng câu, cùng đoạn) ở

ngôn ngữ đích, trong khi các từ dịch sai không như vậy. Nói một cách khác, hướng

tiếp cận này xác định bản dịch tiềm năng nhất bằng việc kiểm tra tần suất cùng xuất

hiện của các từ khóa trong một kho văn bản nào đó (có thể được tính toán trước).

2.3. MÔ HÌNH SỬ DỤNG TỪ ĐIỂN MÁY

Mô hình sử dụng từ điển máy bao gồm ba bước chính [119]. Tại bước phân

đoạn, câu truy vấn được chia thành các phần nhỏ là các từ khóa có ý nghĩa. Tiếp

theo, bản dịch các từ khóa này được kết xuất từ từ điển. Tại bước cuối cùng, tương

- 47 -

ứng với mỗi từ khóa trong câu truy vấn, một hoặc một số bản dịch phù hợp được

lựa chọn. Sự kết hợp các bản dịch cho kết quả là biểu diễn của câu truy vấn tại ngôn

ngữ chứa các tài liệu cần tìm kiếm.

Trong từ điển, mỗi mục từ thường tương ứng với nhiều phương án dịch khác

nhau, do đó cần chọn bản dịch phù hợp nhất. Hai phương án đối lập nhau bao gồm:

chọn một bản dịch hoặc chọn nhiều bản dịch [172].

Luận án tập trung xử lý trường hợp truy vấn song ngữ Việt-Anh. Từ một câu

truy vấn ở ngôn ngữ nguồn, các thuật toán sẽ được mô tả tại chương 3 thực hiện

việc bóc tách các từ khóa trong câu truy vấn kèm với danh sách các phương án dịch

của từ khóa. Trong chương này, tác giả tập trung trình bày mô-đun dịch thuật, chịu

trách nhiệm chọn lựa từ các phương án dịch một hay một số phương án tốt nhất để

xây dựng câu truy vấn tại ngôn ngữ đích. Nội dung mô hình và kết quả thực nghiệm

được trình bày tại các bài báo của tác giả [81], [83].

2.3.1. Xây dựng dữ liệu từ điển

Nhằm xây dựng một từ điển đủ lớn từ các nguồn tài nguyên mã nguồn mở,

một cơ sở dữ liệu chứa các cặp từ Việt-Anh được tạo lập, kết xuất dữ liệu từ dự án từ điển miễn phí cho tiếng Việt12 của tác giả Hồ Ngọc Đức và các cặp từ trong cơ sở

dữ liệu cặp từ liên kết của Wikipedia. Với nguồn dữ liệu đầu tiên, tương ứng với

mỗi mục từ trong từ điển Anh-Việt và Việt-Anh, các bản dịch được bóc tách và

cùng với mục từ tạo thành cặp từ Việt-Anh để đưa vào cơ sở dữ liệu cặp từ. Với nguồn dữ liệu Wikipedia, bản sao các cặp từ liên kết13 được phân tích nhằm bóc

tách các cặp từ Việt-Anh. Các cặp từ được lưu trữ trong các bảng riêng nhằm khai

thác theo thứ tự ưu tiên: đầu tiên từ được tìm kiếm trong Wikipedia, tiếp theo là từ

12 http://www.informatik.uni-leipzig.de/~duc/Dict (truy cập ngày 15/01/2016) 13 http://dumps.wikimedia.org/viwiki (truy cập ngày 15/01/2016)

điển Việt-Anh và cuối cùng là từ điển Anh-Việt.

- 48 -

Trên cơ sở phân tích cấu trúc dữ liệu của các tập tin từ điển và dữ liệu

Wikipedia, các mô-đun phần mềm được xây dựng chuyển đổi các mục từ trong từ

điển sang dạng cơ sở dữ liệu riêng phục vụ luận án.

2.3.2. Khử nhập nhằng dựa trên độ đo mức độ liên quan của cặp từ

Mỗi từ khóa thuộc câu truy vấn ở ngôn ngữ nguồn có thể có các phương án

dịch khác nhau. Để chọn lựa phương án dịch phù hợp với nhu cầu thông tin, cần xác

định ngữ cảnh sử dụng từ khóa. Từ các giải pháp khử nhập nhằng được trình bày tại

phần 2.2, có thể thấy sự liên quan giữa các cặp từ (cùng xuất hiện trong kho ngữ

liệu, trong cùng văn bản hoặc cùng câu) đóng vai trò quan trọng trong việc cung cấp

thêm thông tin về ngữ cảnh sử dụng từ khóa, thông qua đó giúp xác định bản dịch

phù hợp cho các từ khóa trong câu truy vấn. Bên cạnh đó, trong bối cảnh thiếu vắng

các kho ngữ liệu song song lớn, với chất lượng tốt, cách tiếp cận sử dụng thông tin

liên quan giữa các cặp từ thể hiện rõ ưu điểm do thông tin này được khai thác từ các

kho ngữ liệu đơn ngữ có thể dễ dàng tạo lập.

Trong luận án, mức độ liên quan của cặp từ được xác định bằng độ đo thông

tin tương hỗ (Mutual Information-MI) của cặp từ và được sử dụng để thực hiện khử

nhập nhằng và chọn lựa bản dịch phù hợp. Trên cơ sở độ đo này, độ đo tính điểm

liên kết (cohesion score) được tính toán nhằm xác định mức độ phù hợp với ngữ

cảnh của các phương án dịch, từ đó cho phép chọn lựa bản dịch tốt nhất.

2.3.3. Các biến thể của công thức MI

Phần này giới thiệu các phương án xây dựng công thức đo thông tin tương hỗ

của cặp từ được sử dụng trong luận án.

2.3.3.1 Sử dụng tần xuất cùng xuất hiện của cặp từ

Đầu tiên, quá trình huấn luyện được thực hiện trên một kho tài liệu tiếng Anh

nhằm xây dựng mô hình quan hệ của các cặp từ. Với mỗi từ tiếng Anh, số lần từ đó

cùng xuất hiện cùng một từ khác trong cùng câu và trong phạm vi cửa sổ [-5,5]

được ghi nhận trong một bảng dữ liệu. Kết quả, mỗi dòng trong bảng dữ liệu chứa

một cặp từ và số lần chúng cùng xuất hiện trong cùng câu và có khoảng cách không

- 49 -

quá 5 từ. Với hai từ x và y, công thức phổ biến tính giá trị Micooc thể hiện quan hệ

cặp từ có dạng sau:

(2.3) = log (, ) () × ()

trong đó, p(x,y) là xác suất hai từ x,y xuất hiện trong cùng câu với khoảng

cách không quá 5 từ, p(x) và p(y) là xác suất xuất hiện từ x và y trong kho ngữ liệu.

Gọi N là kích thước kho ngữ liệu, nx, ny là số lần xuất hiện của mỗi từ x và y

trong kho ngữ liệu, nxy là số lần xuất hiện của cặp từ x và y trong cùng câu và cách

nhau không quá 5 từ, công thức (2.3) có thể được tính như sau:

(2.4) = log + log () = log × ×

Cùng sử dụng các ký hiệu trên, luận án thực nghiệm một biến thể khác (ký

hiệu là MInxy có dạng sau:

(2.5) + ) (, ) = × ( 1 1

2.3.3.2 Sử dụng máy tìm kiếm

Một công thức tính giá trị MI dựa trên hệ thống truy vấn đơn ngữ tiếng Anh,

ký hiệu là MIir, được trình bày như sau: Với 2 từ x và y, giá trị MIir(x,y) được xác

định như sau: các chuỗi x,y và 'x AND y' được dùng như các câu truy vấn gửi tới

máy tìm kiếm. Các giá trị n(x), n(y) tương ứng sẽ là số tài liệu chứa các chuỗi x, y.

Gía trị n(x,y) là số tài liệu có x,y cùng xuất hiện. Nếu n(x) hay n(y) bằng 0, giá trị

MIir trả về được tính bằng 0. Trong trường hợp ngược lại:

(2.6) = (, ) () × ()

- 50 -

Ưu điểm của công thức này là nó được tính toán ngay trên hệ thống các văn

bản cần tìm kiếm và do đó giúp loại bỏ các cặp từ không cùng xuất hiện trong các

văn bản.

Trong các thuật toán tiếp theo, có thể sử dụng một trong các biến thể của

hàm MI(x,y) đã trình bày để xác định mức độ liên quan giữa hai từ x và y. Trong

một trường hợp riêng, giá trị MI(x,y) với y là từ đa âm tiết được tính bằng giá trị nhỏ

nhất của các giá trị MI(x,e) với e là từ thành phần của y.

2.3.4. Thuật toán chọn bản dịch tốt nhất

Các thuật toán trong phần này được thực hiện khi câu truy vấn tiếng Việt qv

đã được phân tích thành một tập hợp ((v1,L1),(v2,L2), ….,(vn,Ln)) chứa các từ khóa

tiếng Việt v1,..vn và các danh sách bản dịch tương ứng L1,…,Ln, trong đó

= (, … , ) là danh sách chứa các bản dịch ứng viên của vi. Ví dụ, với câu truy vấn tiếng Việt "quản lý quy trình sản xuất", tập hợp ((v1,L1),(v2,L2),(v3,L3)) tương

ứng các giá trị v1="quản lýverb", v2="quy trìnhnoun”, v3="sản xuấtverb" và các phương

án dịch của tương ứng là L1= (manage, administor, control, management, regulate),

L2 = (method, process, instruction) và L3 = (make, produce, manufacture,

fabricate).

Việc áp dụng thuật toán nhằm mục tiêu chọn lựa một hay một số bản dịch tốt

nhất cho mỗi từ khóa tiếng Việt.

2.3.4.1 Thuật toán Greedy

Thuật toán Greedy sau được sử dụng rộng rãi để xác định bản dịch phù hợp:

Thuật toán Greedy

Input: câu truy vấn q = {q1,q2,…,qn}

Output: tập hợp các phương án dịch T = {t1,….,tn}

begin

(1) Với mỗi từ qi của q, xác định tập hợp các bản dịch Ti =

{ti,1,ti,2,…,ti,m} từ tài nguyên dịch thuật (ví dụ từ điển)

(2) Đối với mỗi tập hợp Ti:

- 51 -

(a) Với mỗi ti,m  Ti định nghĩa mức tương tự giữa bản

dịch ti,m và các tập hợp Tj khác (Tj ≠ Ti)

,, = ,, , ,∈

(b) Tính điểm liên kết (cohesion score) cho ti,m

(2.7)

, = (,, )

(c) Lựa chọn ti,m có điểm liên kết cao nhất

= , ,

(2.8)

(2.9)

return {t1,…,tn}

end

Các thuật toán khác nhau để tính giá trị ,, , đo sự tương tự giữa

hai từ ti,m và tj,n có thể được sử dụng. Các thuật toán phổ biến bao gồm khai thác

thông tin chung Mutual Information, hệ số Dice, tỷ lệ tương tự log và kiểm tra Chi

bình phương [99].

Trong thuật toán Greedy, với n là số thuật ngữ trong câu truy vấn, ta cần tìm

bản dịch tốt nhất cho từng thuật ngữ; Với mỗi thuật ngữ cần xem xét các phương án

dịch của (n-1) thuật ngữ khác. Từ đây cho thể thấy thuật toán có độ phức tạp là

(n2). Thuật toán Greedy được sử dụng như cơ sở so sánh với các thuật toán do tác

giả đề xuất.

2.3.4.2 Thuật toán SMI

Như đã trình bày tại phần 2.3.4.1, thuật toán Greedy thực hiện việc xác định

phương án dịch tốt nhất cho từng từ (ở ngôn ngữ nguồn) một cách độc lập trên cơ

sở mức độ quan hệ của phương án dịch của từ đó với các phương án dịch của các từ

khác. Hạn chế của thuật toán xác định bản dịch tốt nhất một cách độc lập cho từng

từ nằm ở chỗ nó chưa thể hiện mối ràng buộc giữa phương án dịch giữa tất cả các từ

khóa truy vấn. Bên cạnh đó, công thức (2.7) bao hàm điểm liên kết của một bản

dịch với tất cả các phương án dịch của một từ khác (bao gồm cả bản dịch phù hợp

hoặc không phù hợp) và do đó tiềm ẩn việc chứa đựng thông tin không chính xác.

- 52 -

Thuật toán SMI (viết tắt của Summary Mutual Information) do tác giả đề

xuất, được trình bày tại [81], thực hiện việc khử nhập nhằng dựa trên ý tưởng xây

dựng hàm tính tổng độ đo mức độ liên quan của các cặp từ nhằm mục tiêu xây dựng

mối ràng buộc giữa các phương án dịch được chọn lựa của tất cả các từ khóa truy

vấn ở ngôn ngữ nguồn.

Thuật toán SMI

Input: câu truy vấn qv = {v1,v2,…,vn}

Output: tập hợp các phương án dịch qe = {e1,….,en}

begin

(1) Với mỗi từ vi của q, xác định tập hợp các bản dịch Li

= {ti,1,ti,2,…,ti,m} từ tài nguyên dịch thuật (ví dụ từ

điển)

(2) Với mỗi tập hợp qtrane={e1,….,en} | eiLi

() = (, )

(2.10)

, ∈

(3) Lựa chọn qtrane có điểm SMI cao nhất = (())

(2.11)

return qe

end

Sau khi thực hiện bước phân đoạn câu truy vấn, mỗi câu truy vấn tiếng Việt

qv được biểu diễn như tập hợp ((v1, L1), ..., (vn, Ln)), trong đó vi là từ tiếng Việt và

= (, … , ) là danh sách chứa các bản dịch ứng viên của vi. Để tiết kiệm chi phí tính toán, mỗi danh sách Li chỉ chứa tối đa 3 phương án dịch có giá trị phân bố

cao nhất (xuất hiện nhiều nhất) trong kho tài liệu huấn luyện.

Mỗi bản dịch ứng viên qtrane của câu truy vấn tiếng Việt qv có thể biểu diễn

dưới dạng mảng qtrane = (e1, ..., en), trong đó ei được chọn từ danh sách Li. Với các

bản dịch ứng viên này, hàm SMI kết hợp thông tin liên quan giữa các cặp từ thành

phần được định nghĩa tại công thức (2.10). Kết quả, bản dịch ứng viên với giá trị

SMI cao nhất được chọn là bản dịch tiếng Anh cho câu truy vấn tiếng Việt qv ban

đầu.

- 53 -

Để minh họa cho thuật toán, ta xem xét câu truy vấn tiếng Việt "ăn chuối

mỗi ngày để giảm nguy cơ đột quỵ". Giai đoạn tiền xử lý tách câu truy vấn thành

các từ khóa và phương án dịch như sau:

v1 = ăn L1 = (To eat, to feed, to take, to have, ate , eaten , eating , finish ,

get , grip , had , has , have , horse , jump , knife , knives , meal ,

pick , put , stomach , taken , took , touch , tuck , hand-feed)

v2=chuối L2=(Banana)

v3=mỗi ngày L4=(each day, everyday)

v4=giảm L3=(to lessen, to reduce, to decrease, commutation , commute ,

cut , cutting , depression , diminish , discount , drawback , drop,

fade , lower , pull , reduce , retrench , subduce , subduct,

subduction , subside , subsidence , take , taken , took , wane)

v5=nguy cơ L5=(danger , jeopardy , liability)

V6=đột quỵ L6=(stroke)

Tất cả các phương án tổ hợp bản dịch của các từ khóa tiếng Việt dạng qtrane

= (e1, ..., en), trong đó ei được chọn từ danh sách Li, được xem xét và tính giá trị

SMI. Kết quả, phương án dịch tốt nhất tương ứng với giá trị SMI cao nhất là (eat,

banana, everyday, reduce, danger, stroke).

Phương pháp xác định bản dịch tốt nhất này khác với các phương pháp sử

dụng thuật toán greedy được trình bày tại phần 2.3.4.1. Trong thuật toán greedy,

bản dịch được xác định cho mỗi từ khóa một cách độc lập. Trong giải pháp tác giả

đề xuất, mọi phương án kết hợp các bản dịch được xem xét để cho phương án tốt

nhất dựa trên việc xem xét giá trị hàm SMI, từ đó xác định bản dịch tốt nhất.

Hạn chế của thuật toán SMI liên quan độ phức tạp. Nếu xem xét 3 bản dịch

cho mỗi thuật ngữ trong câu truy vấn, độ phức tạp của thuật toán là (3n), do đó

thuật toán này chỉ phù hợp với giá trị n nhỏ. Trên thực tế, luận án giới hạn xem xét

- 54 -

các câu truy vấn có độ dài trung bình và khi đó, giá trị n thường giao động từ 3

đến 7 (do câu truy vấn tiếng Việt chứa nhiều thuật ngữ có độ dài 2 âm).

2.3.4.3 Thuật toán chọn bản dịch một cách tuần tự

Ý tưởng chính của thuật toán chọn bản dịch một cách tuần tự (SeQuential

Translation - SQ) là lần lượt kết xuất bản dịch của các từ khóa truy vấn sao cho mối

quan hệ giữa các bản dịch là "tốt nhất". Mức độ "tốt" của mối quan hệ giữa các từ

được đo bằng một hàm được tính toán dựa trên giá trị Mutual Information của các

cặp từ trong nhóm. Thuật toán được trình bày và triển khai thực nghiệm tại [83].

Biểu diễn danh sách các từ khóa của câu truy vấn (tại ngôn ngữ nguồn) dưới

dang các cột. Tập hợp AllColumns chứa chỉ mục của tất cả các cột: AllColumns =

{1…n|n: số lượng từ khóa của câu truy vấn}. Đầu tiên, một danh sách tất cả các cặp

bản dịch ( k it , j it 1 ) của tất cả các cặp 2 cột liền kề (i, i+1) được tạo lập. Trong danh

sách này, cặp bản dịch có giá trị hàm MI cao nhất được chọn là bản dịch tương ứng

với 2 cột i0 và i0+1. Tập hợp GoodColumns chứa chỉ mục của các cột đã xác định

của từ khóa ti0+1.

được bản dịch được tạo và ban đầu sẽ chứa các giá trị i0 và i0+1, tương ứng với các

của từ khóa vi0 và

bản dịch tốt nhất được ký hiệu là

, xác định mối liên quan

Tiếp theo, bản dịch tốt nhất từ 2 cột liền kề với các cột trong tập hợp GoodColumns

cho một từ khóa vi với phương án dịch được coi là tốt

được xác định dựa trên giá trị của một hàm ℎ

được tính bằng

giữa một phương án dịch

nhất của các cột trong tập hợp GoodColumns. Hàm ℎ

)

,

công thức:

= ( ∈

;

ℎ (2.12)

Gọi cột chứa bản dịch tốt nhất từ 2 cột liền kề là i1, bản dịch tốt nhất là

giá trị i1 được thêm vào tập hợp GoodColumns. Quá trình này tiếp tục cho đến khi

mọi cột đều được kiểm tra (tương ứng với GoodColumns == AllColumns). Trong

bước tiếp theo, các bản dịch trong mỗi cột được sắp xếp lại dựa theo công thức

(2.13), nhằm sắp xếp lại các phương án dịch của mỗi cột theo mức độ liên quan với

- 55 -

phương án dịch được coi là tốt nhất của các cột khác. Cuối cùng, tương ứng với mỗi

từ tiếng Việt, ta nhận được một danh sách các bản dịch tốt nhất được sắp xếp theo

thứ tự giảm dần mức độ phù hợp.

Thuật toán chọn bản dịch một cách tuần tự được phát triển dựa trên một kết

quả nghiên cứu của Sadat [133]. Trong thuật toán xếp hạng và khử nhập nhằng dựa

, n jt ) và chọn trên bản dịch, Sadat lần lượt xem xét tất cả các cặp phương án dịch ( m it

cặp bản dịch có giá trị MI cao nhất. Trong luận án, tác giả chỉ xem xét các cặp từ

đứng liền nhau trong câu truy vấn nhằm mục tiêu tránh các ảnh hưởng của việc

chọn các cặp từ ít liên quan, đứng xa nhau trong câu truy vấn. Bên cạnh đó, với mỗi

từ khóa ở ngôn ngữ nguồn (tiếng Việt), thuật toán sẽ kết xuất một số các phương án

dịch ở ngôn ngữ đích (tiếng Anh).

Thuật toán được trình bày chi tiết như sau:

Thuật toán SQ: Chọn bản dịch một cách tuần tự

Input: danh sách các phần tử chứa từ tiếng Việt và các bản

dịch ứng viên

Output: danh sách các phần tử, chứa từ tiếng Việt và các

bản dịch tốt nhất

Begin

Bước 1:

Tạo tập hợp AllColumns từ chỉ mục của danh sách đầu vào

Tạo danh sách các cặp từ liền kề

Với mỗi cặp từ (vi,vi+1)

Với mỗi bản dịch k

it của vi và l +it

1 của vi+1:

Tính giá trị MI( k

it , l

+it 1 )

Chọn cặp bản dịch ( best

it 0 , best +it 10 ) có giá trị MI cao nhất

TranslationSet = [(vi0, best

it 0 ), (vi0+1, best +it 10 )]

Tạo tập hợp GoodColumns chứa 2 giá trị i0 và i0+1

Bước 2:

- 56 -

while GoodColumns <> AllColumns

1 = (, ∈ ) − 1

2 = (, ∈ ) + 1

Với mỗi danh sách ứng viên tại cột i, ∈ [1, 2]

Với mỗi bản dịch k

it

,

ℎ

= ∈

Chọn best

it 1 với giá trị cohesion cao nhất

Thêm (vi1, best

it 1 ) vào TranslationSet

Thêm giá trị i1 vào tập hợp GoodColumns

Gán điểm cohesion cho mỗi phương án dịch của từng từ

(2.13)

,

ℎ

=

Sắp xếp các bản dịch trong mỗi cột i (tập hợp Li) theo giá

trị cohesion giảm dần

Tạo lại TranslationSet ={ (, ) |i=0..n} return TranslationSet

End

Ký hiệu m là số tối đa phương án dịch cho mỗi thuật ngữ (luận án sử dụng

giá trị m=5), n là số thuật ngữ trong câu truy vấn (ở ngôn ngữ nguồn), vòng lặp xác định cặp bản dịch tốt nhất đầu tiên có độ phức tạp là m*n2, vòng lặp thêm bản dịch

tốt nhất từ các từ lân cận các từ đã xem xét có độ phức tạp là m*n, việc sắp xếp lại

điểm cohesion cho các từ có độ phức tạp là m*n. Từ đây xác định được thuật toán có độ phức tạp là O(n2), tốt hơn so với thuật toán SMI và có thể áp dụng trong

trường hợp câu truy vấn dài.

Để minh họa cho thuật toán, ta xem xét câu truy vấn tiếng Việt “Khánh Hòa

cố gắng phát triển kinh tế biển”. Giai đoạn tiền xử lý phân tách câu truy vấn thành

các từ khóa "Khánh Hòa/Np", "cố gắng/V", "phát triển/V", "kinh tế biển/N" cùng

với các phương án dịch tương ứng:

- 57 -

v1=Khánh Hòa L1=('Khanh Hoa Province')

v2=cố gắng L2=('attempt', 'to endeavour', 'to make every effort', 'To try')

v3=phát triển L3=('Develop', 'enlarge', 'expand', 'expand trade', 'expansion',

'expansion plan', 'evolutional', 'evolutionary', 'evolve',

'extend','grow')

v4=kinh tế biển L4=('marine economy')

Xem xét các cặp bản dịch của 2 từ liên tiếp, thuật toán chọn được cặp bản

dịch (develop, marine economy) có giá trị cohesion cao nhất cho 2 từ khóa "phát

triển" và "kinh tế biển". Tiếp tục xem xét các từ còn lại, thuật toán chọn lựa bản

dịch "make every effort" cho từ khóa "cố gắng" và sau đó, chọn bản dịch duy nhất

"Khanh Hoa province" từ từ điển Wiki. Sau khi thực hiện lại việc sắp xếp các bản

dịch trong mỗi cột, bản dịch "try" được chọn thay thế cho bản dịch "make every

effort" cho từ khóa "cố gắng". Kết quả cuối cùng, tương ứng với các từ khoá của

câu truy vấn, các bản dịch như sau được lựa chọn:

 Khánh Hòa ['Khanh Hoa Province']

 cố gắng ['To try', 'to endeavour', 'to make every effort']

 phát triển ['Develop', 'expand', 'expand trade']

 kinh tế biển ['marine economy']

Các phương án dịch được sắp xếp theo thứ tự giảm dần mức độ phù hợp.

2.3.5. Xây dựng câu truy vấn

Cho trước câu truy vấn qv và tập hợp ((v1,L1),(v2,L2), ….,(vn,Ln)) chứa các từ

khóa tiếng Việt v1,..vn và các danh sách bản dịch L1,…,Ln. Sau quá trình khử nhập

nhằng (mô tả tại phần 2.3.4), các bản dịch trong mỗi danh sách Li được điều chỉnh:

giới hạn số lượng phương án dịch và được sắp xếp theo thứ tự giảm dần mức độ

phù hợp. Từ đây, 3 nhóm phương án xây dựng câu truy vấn có thể được triển khai:

 Sử dụng 1 bản dịch cho mỗi từ vi để tạo lập câu truy vấn;

 Nối tất cả các bản dịch của các từ thành câu truy vấn ở ngôn ngữ đích;

- 58 -

 Xây dựng câu truy vấn có cấu trúc từ các bản dịch.

Xây dựng câu truy vấn có cấu trúc là một kỹ thuật được đề xuất khá sớm

trong các nghiên cứu của Pirkola [118] và của Bruce Croft và đồng sự [115] nhằm

mục tiêu sử dụng các toán tử lô-gíc cũng như trọng số của các từ khóa để xây dựng

câu truy vấn và đã cho thấy sự vượt trội của phương pháp này so với câu truy vấn

không cấu trúc (không sử dụng các toán tử lô-gíc). Một ví dụ điển hình là máy tìm

kiếm INQUERY[21] hỗ trợ việc xây dựng câu truy vấn có cấu trúc thông qua các

toán tử như #and, #or, #not, #syn. Trong khi các toán tử giúp xác định sự liên quan

của các từ khóa trong các tài liệu tìm kiếm (ví dụ cùng xuất hiện, không xuất hiện,

chọn một trong các phương án), trọng số từ khóa cho phép xác định mức ảnh hưởng

của một từ khóa lên điểm xếp hạng. Máy tìm kiếm tích hợp các toán tử và trọng số

vào các công thức tính toán điểm xếp hạng. Trong khuôn khổ luận án, nhằm phát huy thế mạnh của câu truy vấn có cấu trúc, tác giả sử dụng máy tìm kiếm Solr14 là

một phần mềm mã nguồn mở của Apache. Máy tìm kiếm Solr hỗ trợ nhiều cú pháp

tìm kiếm, đặc biệt là hỗ trợ xây dựng câu truy vấn có cấu trúc; cho phép tạo lập

nhiều kiểu đầu ra như Json, XML, PHP, và có khả năng tích hợp với các ứng dụng

web một cách đơn giản.

Để minh họa cho các nội dung tiếp theo, ta sử dụng câu truy vấn ví dụ tiếng

Việt “quản lý quy trình sản xuất”. Các từ "quản lýverb", "quy trìnhnoun", "sản

xuấtverb" có các phương án dịch là (management, regulate, control), (method,

process, instruction) và (production, manufacture, fabricate).

Với máy tìm kiếm Solr, có thể sử dụng các toán tử lô-gíc AND, OR cũng

như sử dụng cú pháp a^m để gán trọng số m cho từ khóa a [146]. Ví dụ, trong câu

truy vấn "management^2 method^4 production^2", các từ khóa "management" và

"production" có trọng số là 2 và từ khóa "method" có trọng số là 4.

2.3.5.1 Sử dụng một bản dịch

14 http://lucene.apache.org/solr/ (truy cập ngày 15/01/2016)

Với việc áp dụng công thức SMI, mỗi từ khóa ở ngôn ngữ nguồn tương ứng

- 59 -

với một bản dịch ở ngôn ngữ đích. Ví dụ, bản dịch của các từ "quản lýverb", "quy

trìnhnoun", "sản xuấtverb" tương ứng sẽ là "management", "method" và "production".

Câu truy vấn tiếng Anh lúc đó sẽ là "management method production".

2.3.5.2 Nối bản dịch của các từ thành câu truy vấn

Phương án nối tất cả các bản dịch của các từ thành câu truy vấn ở ngôn ngữ

đích có thể được sử dụng mà không cần áp dụng bất kỳ thuật toán khử nhập nhằng

nào. Câu truy vấn được tạo tại ngôn ngữ đích có dạng:

…

…

…

…

là các phương án dịch của vi trong danh sách Li. Câu

(2.14)

,

, … truy vấn ví dụ sẽ có bản dịch tiếng Anh như sau:

trong đó

management regulate control method process instruction production

manufacture fabricate

2.3.5.3 Nhóm các bản dịch của từng từ bằng toán tử OR

Bản dịch câu truy vấn có cấu trúc có thể được tạo bằng cách nhóm các

phương án dịch của từng từ khóa bằng toán tử OR có dạng:

)

) … (

) (

…

…

…

(2.15) (

Đối với câu truy vấn ví dụ, bản dịch tiếng Anh như sau:

(management OR regulate OR control) (method OR process OR instruction)

(production OR manufacture OR fabricate)

Cách định nghĩa câu truy vấn cho máy tìm kiếm Solr như thế này tương tự

phương pháp của Pirkola [118].

2.3.5.4 Gán trọng số thủ công cho các phương án dịch

Phương pháp gán trọng số thủ công ưu tiên phương án dịch được coi là tốt

nhất bằng cách gán trọng số 1 cho phương án đầu tiên trong danh sách các phương

án dịch; các phương án dịch khác được giữ trong danh sách được gán trọng số 0.5.

Với cú pháp sử dụng tại máy tìm kiếm Solr, câu truy vấn tiếng Anh lúc đó có dạng:

- 60 -

^0.5)

^0.5) … (

^1

^1

^0.5 …

^0.5 …

(2.16) (

Bản dịch tiếng Anh của câu truy vấn ví dụ như sau:

(management^1 OR regulate^0.5 OR control^0.5) (method^1 OR process^0.5

OR instruction^0.5) (production^1 OR manufacture^0.5 OR fabricate^0.5)

2.3.5.5 Gán trọng số thủ công cho các từ trong câu truy vấn.

Khi thực hiện thuật toán bóc tách từ khóa, nhãn từ đã được xác định và được

dùng làm cơ sở gán trọng số trong câu truy vấn tiếng Anh. Trong luận án, nhóm các

phương án dịch của từ được gán thẻ Np (noun phrase) được gán trọng số 8. Trọng

số cho các thẻ N (noun), V (verb) lần lượt là 4 và 2. Các thẻ khác có trọng số 1. Với

máy tìm kiếm Solr, câu truy vấn có dạng:

)^ … (

)^

)^ (

…

…

…

là các phương án dịch của vi trong danh sách Li. Giá trị

(2.17) (

,

, … wi là trọng số của từ vi trong câu truy vấn.

Ở đây,

Với câu truy vấn tiếng Việt “quản lý quá trình sản xuất”, quá trình bóc tách

từ khóa có kết quả là 3 từ khóa và thẻ tương ứng: “quản lý”-động từ, “quá trình”-

danh từ, “sản xuất”-động từ, có các trọng số tương ứng là 2, 4, 2. Do đó, bản dịch

tiếng Anh của câu truy vấn ví dụ có dạng như sau:

(management OR regulate OR control)^2 (method OR process OR

instruction)^4 (production OR manufacture OR fabricate)^2

2.3.5.6 Kết hợp 2 phương pháp gán trọng số thủ công

,

trọng số cho các phương án dịch khác nhau. Gọi

, … của vi trong danh sách Li với các trọng số tương ứng là

,

, …

Ta có thể kết hợp việc gán trọng số cho các từ trong câu truy vấn và gán là các phương án dịch . Giá trị wi là

trọng số của từ vi trong câu truy vấn. Các phương án dịch của từ được gán thẻ Np

được gán trọng số 8. Trọng số cho các thẻ N, V lần lượt là 4 và 2. Các thẻ khác có

trọng số 1. Khi đó, bản dịch tiếng Anh của câu truy vấn có dạng:

- 61 -

…

…

) ) Với máy tìm kiếm Solr, câu truy vấn ví dụ có dạng:

(2.18) = ( … (

(management^1 OR regulate^0.5 OR control^0.5)^2 (method^1 OR

process^0.5 OR instruction^0.5)^4 (production^1 OR manufacture^0.5 OR

fabricate^0.5)^2.

2.3.5.7 Gán trọng số dựa trên kết quả quá trình khử nhập nhằng

của từ tiếng Việt vi được gán giá

Trong thuật toán Chọn bản dịch một cách tuần tự (2.3.4.3), tại bước sắp xếp

lại các phương án dịch, mỗi phương án dịch điểm cohesion bằng cách sử dụng công thức (2.13), đo mức độ liên quan của

phương án dịch này với phương án dịch được coi là tốt nhất của các từ tiếng Việt

. Gọi là các phương án dịch của vi trong danh sách Li với các trọng số tương . Khi đó, bản dịch tiếng Anh của câu truy vấn được xây dựng

, … ứng là

,

, …

khác. Giá trị này có để được sử dụng như trọng số của phương án dịch ,

dưới dạng:

= ( … (

…

) )

… Với máy tìm kiếm Solr, câu truy vấn ví dụ được tạo dựng trong thực nghiệm

(2.19)

với giá trị sau:

((control)^0.556445681271 OR (manage)^0.268952911452 OR

(supervise)^0.174601407277) ((process)^0.60852654056 OR

(method)^0.203213625283 OR (procedure)^0.188259834156)

((production)^0.512249748308 OR (manufacture)^0.262275130029 OR

(fabrication)^0.225475121664)

2.4. THỰC NGHIỆM ÁP DỤNG CÔNG THỨC SMI

2.4.1. Môi trường thực nghiệm

Để thiết lập môi trường thực nghiệm việc áp dụng công thức SMI, một bộ dữ

- 62 -

liệu đánh giá được xây dựng, chứa một danh sách các câu truy vấn và một tập hợp

tài liệu phục vụ truy vấn theo phương pháp pooling. Các kho tài liệu tiếng Việt

(5.000 tài liệu) và tiếng Anh (8.000) tài liệu được đánh chỉ mục, sử dụng các hệ

thống tìm kiếm đơn ngữ áp dụng mô hình xếp hạng LSI được xây dựng bằng ngôn ngữ Python15, sử dụng thư viện Gensim16.

Các câu truy vấn tiếng Việt được dịch thủ công sang tiếng Anh bởi các

chuyên gia ngôn ngữ. Tương ứng với mỗi câu truy vấn tiếng Anh, 100 kết quả tìm

kiếm tương ứng mỗi mô hình xếp hạng được kết xuất và trộn thành một danh sách

chung. Từng tài liệu được đánh giá lại một cách thủ công để kiểm tra có phù hợp

hay không với câu truy vấn.

Một ứng dụng Web được xây dựng nhằm hỗ trợ người đánh giá. Với mỗi câu

truy vấn, danh sách các kết quả tìm kiếm tốt nhất được hiển thị, kèm theo các thông

tin về số hiệu, tiêu đề, trích yếu và nội dung, điểm số. Người đánh giá dùng chuột

hoặc bấm phím tại để đánh dấu đối với các tài liệu được xác định là phù hợp với câu

truy vấn. Với kích thước hạn chế của bộ dữ liệu thực nghiệm, môi trường đánh giá

này chưa thực sự hoàn thiện và cần được cải thiện, tuy nhiên nó vẫn đảm bảo sự

hữu ích trong thực nghiệm được tiến hành [82].

Các cấu hình khác nhau được đánh giá được liệt kê trong Bảng 2.1. Trong

bảng này, phương pháp nMI sử dụng kỹ thuật phân đoạn câu truy vấn thành các từ

khóa cần dịch (sẽ được trình bày trong chương 3), sau đó áp dụng thuật toán greedy

(2.3.4.1) để chọn bản dịch tốt nhất.

Bảng 2.1: Cấu hình thực nghiệm

Cấu hình Diễn giải STT

Sử dụng thuật toán greedy 1 nMI

15 http://www.python.org/ (truy cập ngày 15/01/2016) 16 https://radimrehurek.com/gensim/ (truy cập ngày 15/01/2016)

Do tác giả đề xuất 2 SMI

- 63 -

3 Dịch Google Dùng máy dịch Googe

4 Dịch thủ công Chuyên gia dịch

Cấu hình SMI cũng áp dụng kỹ thuật phân đoạn câu truy vấn, sau đó áp dụng

thuật toán SMI (2.3.4.2) để xác định bản dịch tốt nhất với mỗi từ khóa. Hai phương

pháp cuối không áp dụng các kỹ thuật phân đoạn và khử nhập nhằng: Phương pháp

thứ ba sử dụng máy dịch Google; phương pháp thứ tư sử dụng các bản dịch thủ

công được tạo bởi các chuyên gia tiếng Anh nhằm làm cơ sở so sánh hiệu quả các

cấu hình đề xuất.

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

Để đánh giá chất lượng của phương pháp xếp hạng, các chỉ số thông dụng

phục vụ việc đánh giá độ chính xác xếp hạng bao gồm độ chính xác mức k ký hiệu

P@k, độ chính xác trung bình AP, độ chính xác trung bình bình quân MAP [4].

Kết quả thực nghiệm tương ứng với các cấu hình khác nhau được trình bày

tại Bảng 2.2. Các chỉ số độ chính xác mức k P@k, độ chính xác trung bình bình

quân MAP được tính toán nhằm so sánh với phương pháp sử dụng dịch thủ công

(tương đương với tình huống truy vấn đơn ngữ).

Bảng 2.2: Kết quả thực nghiệm

STT Cấu hình P@1 P@5 P@10 MAP So sánh

1 nMI 0.497 0.482 0.429 0.436 74.79%

2 SMI 0.511 0.488 0.447 0.446 76.50%

3 Dịch Google 0.489 0.535 0.505 0.499 85.59%

4 Dịch thủ công 0.605 0.605 0.563 0.583 100%

Kết quả thực nghiệm cho thấy cấu hình SMI sử dụng phương pháp khử nhập

nhằng đề xuất tỷ lệ lớn hơn 75% so với truy vấn đơn ngữ và tốt hơn cấu hình nMI.

- 64 -

2.5. THỰC NGHIỆM TẠO BẢN DỊCH CÂU TRUY VẤN CÓ CẤU

TRÚC

2.5.1. Môi trường thực nghiệm

Bộ công cụ Solr phiên bản 4.3.1017 được sử dụng để xây dựng các máy tìm

kiếm đơn ngữ cho tiếng Việt và tiếng Anh. Đây là một công cụ mã nguồn mở viết

bằng ngôn ngữ Java, được sử dụng khá rộng rãi, với hàm xếp hạng được phát triển

dựa trên mô hình TF-IDF. Điểm phù hợp của bộ công cụ đối với luận án là nó tiếp

nhận và xử lý các câu truy vấn có cấu trúc.

Dữ liệu được đánh chỉ mục được thu thập từ 2 nguồn. Đối với tiếng Việt,

200.000 tài liệu của website http://vietnamplus.vn được sử dụng. Đối với tiếng Anh,

tiêu đề của một số bài báo tiếng Anh được sử dụng như câu truy vấn gửi tới máy

tìm kiếm Google. Một chương trình được viết để nhận các địa chỉ trong danh sách

kết quả và tải các trang web tương ứng. Kết quả, 24.000 trang web tiếng Anh được

tải về. Nội dung của các trang web bao gồm tiêu đề và toàn văn được bóc tách sử dụng công cụ Boilerpipe18. Mỗi tài liệu web trong kho tài liệu được bóc tách các

thành phần tiêu đề (tương ứng thẻ