Luận án Tiến sĩ Toán học: Một số kỹ thuật tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn và gợi ý truy vấn hướng ngữ cảnh

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:117

Thêm vào BST

Báo xấu

38
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án tập trung nghiên cứu, xác định và thực nghiệm các phương pháp, các nguyên lý nhằm giải quyết 2 bài toán nêu trên. Cài đặt thực nghiệm các phương pháp và áp dụng các đề xuất cải thiện kỹ thuật. Phân tích, đánh giá kết quả sau thực nghiệm và so sánh với các kỹ thuật khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Một số kỹ thuật tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn và gợi ý truy vấn hướng ngữ cảnh

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Trần Lâm Quân MỘT SỐ KỸ THUẬT TÌM KIẾM THỰC THỂ DỰA TRÊN QUAN HỆ NGỮ NGHĨA ẨN VÀ GỢI Ý TRUY VẤN HƯỚNG NGỮ CẢNH LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Trần Lâm Quân MỘT SỐ KỸ THUẬT TÌM KIẾM THỰC THỂ DỰA TRÊN QUAN HỆ NGỮ NGHĨA ẨN VÀ GỢI Ý TRUY VẤN HƯỚNG NGỮ CẢNH Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9.46.01.10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Vũ Tất Thắng Hà Nội – 2020
i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, được hoàn thành dưới sự hướng dẫn của TS Vũ Tất Thắng. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Tôi xin chịu trách nhiệm về những lời cam đoan của mình. Hà nội, tháng 12 năm 2020 Tác giả Trần Lâm Quân
ii LỜI CẢM ƠN Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự giúp đỡ hết mình từ thầy hướng dẫn, gia đình, bạn bè và đồng nghiệp. Đầu tiên, tác giả xin bày tỏ lời tri ân tới TS Vũ Tất Thắng, Thầy đã tận tình hướng dẫn tác giả hoàn thành luận án này, Thày đã kiên trì và đặc biệt, đã định hướng cho nghiên cứu sinh suốt quá trình nghiên cứu. Tác giả xin gửi lời cảm ơn tới các Thầy, Cô và cán bộ của Viện Công nghệ thông tin, Học viện Khoa học và Công nghệ (Viện Hàn lâm Khoa học và Công nghệ Việt Nam) đã nhiệt tình giúp đỡ và tạo ra môi trường nghiên cứu tốt để tác giả hoàn thành công trình nghiên cứu; đã có những góp ý chính xác để tác giả có được những công bố như ngày hôm nay. Tác giả xin cảm ơn tới Ban Lãnh đạo Tổng công ty Hàng không Việt Nam (Vietnam Airlines), Trung tâm Nghiên cứu Ứng dụng và các đồng nghiệp nơi tác giả công tác đã ủng hộ để luận án được hoàn thành. Cuối cùng, xin gửi lời cảm ơn đến tất cả các thành viên trong gia đình, các bạn bè đã luôn ủng hộ, chia sẻ, động viên và khích lệ tôi học tập, nghiên cứu Hà Nội, tháng 12 năm 2020 Trần Lâm Quân
iii MỤC LỤC Trang phụ bìa Lời cam đoan i Lời cảm ơn ii Mục lục iii Danh mục các ký hiệu, các chữ viết tắt v Danh mục các bảng vii Danh mục các hình vẽ, đồ thị viii MỞ ĐẦU 01 CHƯƠNG 1: TỔNG QUAN 1.1. Bài toán tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn 05 1.2. Các nghiên cứu liên quan đến tìm kiếm thực thể dựa trên ngữ nghĩa ẩn 07 1.2.1. Lý thuyết ánh xạ cấu trúc (Structure Mapping Theory – SMT) 07 1.2.2. Mô hình không gian vector (Vector Space Model - VSM) 08 1.2.3. Phân tích quan hệ tiềm ẩn (Latent Relational Analysis - LRA) 09 1.2.4. Ánh xạ quan hệ tiềm ẩn (Latent Relational Mapping Engine - LRME) 09 1.2.5. Quan hệ ngữ nghĩa tiềm ẩn (Latent Semantic Relation – LSR) 11 1.2.6. Tương đồng quan hệ dựa trên Wordnet 11 1.2.7. Mô hình học biểu diễn vector từ Word2Vec 12 1.3. Phương pháp tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn với các nghiên cứu liên quan 14 1.4. Bài toán gợi ý truy vấn hướng ngữ cảnh 14 1.5. Các nghiên cứu liên quan đến gợi ý truy vấn 15 1.5.1. Kỹ thuật gợi ý truy vấn dựa trên phiên (Session-based) 15 1.5.2. Kỹ thuật gợi ý truy vấn dựa trên cụm (Cluster-based) 18 1.6. Phương pháp gợi ý truy vấn dựa trên hướng ngữ cảnh với các nghiên cứu liên quan 22 1.7. Các kết quả đạt được của luận án 24 CHƯƠNG 2: TÌM KIẾM THỰC THỂ DỰA TRÊN QUAN HỆ NGỮ NGHĨA ẨN 2.1. Bài toán 25 2.2. Phương pháp tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn 27
iv 2.2.1. Kiến trúc – Mô hình 27 2.2.2. Thành phần rút trích quan hệ ngữ nghĩa 30 2.2.3. Thành phần gom cụm các quan hệ ngữ nghĩa 32 2.2.4. Thành phần tính toán độ tương đồng quan hệ giữa 2 cặp thực thể 39 2.3. Kết quả thực nghiệm - Đánh giá 43 2.3.1. Dataset 44 2.3.2. Kiểm thử - Điều chỉnh tham số 45 2.3.3. Đánh giá với độ đo MRR 46 2.3.4. Hệ thống thực nghiệm 46 2.4. Kết luận chương 49 CHƯƠNG 3: GỢI Ý TRUY VẤN HƯỚNG NGỮ CẢNH 3.1. Bài toán 50 3.2. Phương pháp hướng ngữ cảnh 52 3.2.1. Định nghĩa – Thuật ngữ 52 3.2.2. Đề dẫn – Ví dụ minh họa 53 3.2.3. Kiến trúc – Mô hình 55 3.2.4. Offline phase 55 3.2.5. Online phase – Giải thuật gợi ý truy vấn 63 3.2.6. Phân tích ưu nhược điểm 64 3.2.7. Các đề xuất kỹ thuật 66 3.2.8. Kỹ thuật phân lớp kết quả tìm kiếm dựa trên dàn khái niệm 73 3.3. Kết quả thực nghiệm - Đánh giá 84 3.3.1. Dataset 85 3.3.2. Đánh giá, so sánh 85 3.3.3. Hệ thống thực nghiệm 88 3.4. Kết luận chương 92 CHƯƠNG 4: KẾT LUẬN VÀ KIẾN NGHỊ 4.1. Kết luận 94 4.2. Kiến nghị 95 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 96 TÀI LIỆU THAM KHẢO 97
v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Ký hiệu Tên tiếng Anh Tên tiếng Việt CBOW Continous Bag-Of-Words Mô hình Túi từ liên tục áp dụng trong Word2Vec C Cluster, Clustering Cụm, Phân cụm CL Concept Lattice Dàn khái niệm Dataset Data-set Tập dữ liệu mẫu FCA Formal Concept Analysis Phân tích khái niệm hình thức Fe Filter-Entities Hàm lọc tìm các cặp thực thể ứng viên FC Formal Context Khái niệm hình thức IRES Implicit Relational Entity Tìm kiếm thực thể dựa trên quan hệ ẩn; Search IR Information Retrieval Tìm kiếm thông tin IRS Implicit Relational Search Tìm kiếm dựa trên quan hệ ẩn LM Language Model Mô hình ngôn ngữ LRME Latent Relation Mapping Ánh xạ quan hệ tiềm ẩn Engine LRA Latent Relational Analysis Phân tích quan hệ tiềm ẩn LSR Latent Semantic Relation Quan hệ ngữ nghĩa tiềm ẩn MRR Mean Reciprocal Rank Trung bình của RR (Reciprocal Rank) tập truy vấn NE Named Entity Thực thể có tên PMI Pointwise Mutual Độ đo thông tin tương hỗ Information q Query Câu truy vấn QLogs Query Log Tập truy vấn trong quá khứ Q-suggest Query suggestion Gợi ý truy vấn; Đề xuất truy vấn Re Rank-Entities Hàm xếp hạng các thực thể trong tập ứng viên RelSim Relational Similarity Tương đồng quan hệ
vi RR Reciprocal Rank Thứ hạng phù hợp của một đối tượng (truy vấn) SE Search Engine Máy tìm kiếm SL Semantic relation Quan hệ ngữ nghĩa Session Session Phiên tìm kiếm SR Similarity relation Quan hệ tương đồng SMT Structure Mapping Theory Lý thuyết ánh xạ cấu trúc term Term(s) Từ, cụm từ, thuật ngữ mining Text mining Khai phá dữ liệu văn bản VS Voice search Tìm kiếm bằng giọng nói VSM Vector Space Model Mô hình không gian vector Word2Vec Word to Vector Mô hình học biểu diễn từ thành vector
vii DANH MỤC CÁC BẢNG Bảng 1.1: Tìm tương quan giữa các thuật ngữ trong 2 danh sách 9 Bảng 1.2: Kết quả tương quan giữa các thuật ngữ trong 2 danh sách 10 Bảng 2.1: Kết quả giải thuật rút trích quan hệ ngữ nghĩa 31 Bảng 2.2: Các phân lớp NER (Location, Organization, Personal, Time) 44 Bảng 2.3: Các ví dụ kết quả thực nghiệm với input q = {A, B, C} và output D 48 Bảng 3.1: Cấu trúc rút gọn của phiên tìm kiếm 53 Bảng 3.2: Bảng ngữ cảnh 1 75 Bảng 3.3: Bảng so sánh tìm kiếm hướng ngữ cảnh và Lucene-Nutch 86
viii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Danh sách trả về từ Keyword-SE ứng với query: “Việt Nam”, “Hà Nội”, “Pháp” 1 Hình 1.2: Danh sách trả về từ Keyword-SE ứng với q1, q2 3 Hình 1.3: Input: “Cuba”, “José Marti”, “Ấn Độ” (ngữ nghĩa ẩn: “anh hùng dân tộc”) 5 Hình 1.4: Tìm kiếm dựa trên quan hệ ngữ nghĩa với truy vấn đầu vào gồm 3 thực thể 6 Hình 1.5: Ánh xạ cấu trúc SMT 8 Hình 1.6: Quan hệ giữa từ mục tiêu và ngữ cảnh trong mô hình Word2Vec 12 Hình 1.7: Word2Vec “học” quan hệ “ẩn” giữa từ mục tiêu và ngữ cảnh của từ 13 Hình 1.8: QFG sử dụng trọng số 17 Hình 1.9: Các phương pháp phân cụm 18 Hình 1.10: Các đối tượng Core, Border, Noise phân cụm DBSCAN 21 Hình 1.11: Khả năng Directly Density-reachable và Density-reachable 21 Hình 1.12: Gợi ý truy vấn bằng các kỹ thuật truyền thống 22 Hình 1.13: Ngữ cảnh truy vấn 23 Hình 1.14: Minh họa truy vấn “tiger” 23 Hình 2.1: Tìm kiếm dựa trên quan hệ ngữ nghĩa với đầu vào gồm 3 thực thể 27 Hình 2.2: Kiến trúc tổng quát mô hình tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn 29 Hình 2.3: Giá trị F-Score tương ứng với mỗi giá trị thay đổi của α, θ1 45 Hình 2.4: So sánh PMI với f: tần suất (số lần đồng hiện) dựa trên MRR 46 Hình 2.5: Thực nghiệm IRS với nhãn thực thể B-PER 47 Hình 2.6: Thực nghiệm IRS với thực thể kiểu thời gian 47 Hình 3.1: Ngữ cảnh truy vấn 53 Hình 3.2: Ví dụ minh họa với truy vấn “gladiator” 54 Hình 3.3: Ví dụ minh họa với truy vấn “tiger” 54 Hình 3.4: Mô hình của tiếp cận gợi ý truy vấn hướng ngữ cảnh 55 Hình 3.5: Đồ thị 2 phía (tập đỉnh Q – tập đỉnh U) 56 Hình 3.6: Sử dụng cấu trúc dữ liệu mảng để phân cụm 59 Hình 3.7: Mô phỏng trực quan tiến trình dựng cây hậu tố 62 Hình 3.8: Phase online: Tiến trình gợi ý truy vấn 63
ix Hình 3.9: Áp dụng random walk cải thiện vấn đề dữ liệu thưa 69 Hình 3.10: Dựng dàn khái niệm từ bảng ngữ cảnh 1 75 Hình 3.11: Tìm kiếm và phân lớp kết quả với truy vấn “jaguar” 76 Hình 3.12: Tìm kiếm trên dàn 83 Hình 3.13: Mô hình hệ thống thực nghiệm kỹ thuật tìm kiếm hướng ngữ cảnh 84 Hình 3.14: (a): Độ đo tính đa dạng; 14 (b): Độ đo tính thích đáng 87 Hình 3.15: Silverlight đề nghị truy xuất camera, microphone trên máy client 88 Hình 3.16: ARS Server thực hiện speech to text 89 Hình 3.17: Tìm kiếm hướng ngữ cảnh tương tác giọng nói 89 Hình 3.18: Gợi ý truy vấn (gõ không dấu) 90 Hình 3.19: Tìm kiếm áp dụng phương pháp hướng ngữ cảnh 90 Hình 3.20: Gợi ý nhanh 91 Hình 3.21: Phân loại kết quả 91
1 MỞ ĐẦU 1. Tính cấp thiết của luận án Trong kỷ nguyên big-data, trên không gian Internet, lượng dữ liệu mới sinh ra không ngừng, Search Engine là cốt lõi để đáp ứng nhu cầu tìm kiếm thông tin của người sử dụng. Đồng thời, nhu cầu tìm kiếm thông tin với yêu cầu cao ngày càng cấp bách. Cơ chế tìm kiếm dựa vào từ khóa ít có khả năng suy diễn thông tin chưa biết. Ngoài ra, câu truy vấn người dùng đưa vào trên thực tế thường ngắn, mơ hồ và đa nghĩa [1 – 6]. Do đó, cần thiết phải tập trung nghiên cứu cách thức cải tiến để đưa ra các gợi ý truy vấn hiệu quả hơn, hoặc hình thái tìm kiếm mới như tìm ra tên các thực thể dựa trên ngữ nghĩa ẩn. Theo thống kê, xấp xỉ 71% câu tìm kiếm trên web có chứa tên thực thể [7], [8]. Khi xét truy vấn chỉ gồm tên thực thể: “Việt Nam”, “Hà Nội”, “Pháp”, về trực quan, ta thấy ngữ nghĩa tiềm ẩn sau truy vấn này. Nói cách khác, tiềm ẩn một quan hệ tương tự giữa cặp tên thực thể “Việt Nam”:“Hà Nội” và cặp tên thực thể “Pháp”:“?”. Nếu chỉ xét trực quan, đây là một trong những khả năng “tự nhiên” của con người - khả năng suy ra thông tin/tri thức chưa biết bằng suy diễn tương tự. Với truy vấn trên, con người có khả năng đưa ra đáp án tức thời, nhưng máy tìm kiếm Search Engine (SE) chỉ tìm được những tài liệu chứa các từ khóa nói trên, SE không đưa ngay ra được câu trả lời “Paris”. Hình 1.1: Danh sách trả về từ Keyword-SE ứng với query=”Việt Nam”, “Hà Nội”, “Pháp”.
2 Cũng như vậy, thế giới thực tồn tại những câu hỏi dạng: “nếu Fansipan cao nhất Việt Nam, thì đâu là đỉnh của Tây Tạng?”, “biết Elizabeth là nữ hoàng Anh thì quốc vương Nhật Bản là ai?”, .v.v. Đối với những truy vấn tồn tại quan hệ tương đồng như trên, cơ chế tìm kiếm theo từ khóa khó khăn trong việc đưa ra đáp án, trong khi con người có thể dễ dàng suy luận tương tự. Nghiên cứu, mô phỏng khả năng tự nhiên của con người khi suy diễn từ một miền ngữ nghĩa quen thuộc (“Việt Nam”, “Hà Nội”) sang một miền ngữ nghĩa không quen thuộc (“Pháp”, “?”) - là mục đích của bài toán thứ nhất. Bài toán thứ 2 về gợi ý truy vấn. Trong các phiên tìm kiếm, lượng kết quả trả về nhiều nhưng phần lớn không thích hợp với ý định tìm kiếm của người sử dụng 1. Từ đó, có nhiều hướng nghiên cứu đặt ra nhằm cải thiện kết quả, hỗ trợ người tìm kiếm. Các hướng nghiên cứu này bao gồm: gợi ý truy vấn (query suggestion), viết lại truy vấn (rewriting query), mở rộng truy vấn (query expansion), cá nhân hóa (personalized recommendations), phân hạng kết quả (ranking/re-ranking search results), .v.v. Hướng nghiên cứu về gợi ý truy vấn thường áp dụng các kỹ thuật truyền thống như gom cụm, đo độ tương đồng, .v.v. của các truy vấn [9], [10]. Tuy nhiên, các kỹ thuật truyền thống có ba nhược điểm: Thứ nhất, chỉ đưa ra được các câu gợi ý tương tự hoặc có liên quan với truy vấn vừa nhập - mà chất lượng chưa chắc đã tốt hơn truy vấn vừa nhập. Thứ hai, không đưa ra được xu hướng mà tri thức số đông thường hỏi sau truy vấn hiện hành. Thứ ba, những cách tiếp cận này không xét chuỗi truy vấn một cách liền mạch từ người sử dụng để nắm bắt ý định tìm kiếm của người dùng. Chẳng hạn, trên các Search Engine (SE) thông dụng, gõ 2 truy vấn liên tiếp q1: “Joe Biden là ai”, q2: “Ông ấy bao nhiêu tuổi”, rõ ràng q1, q2 có liên quan ngữ nghĩa. Tuy nhiên kết quả trả về của q1, q2 là 2 tập kết quả rất khác nhau. Điều này cho thấy nhược điểm của cơ chế tìm kiếm theo từ khóa. Nắm bắt chuỗi truy vấn liền mạch, nói cách khác, nắm bắt được ngữ cảnh tìm kiếm, SE sẽ “hiểu” được ý định tìm kiếm của người sử dụng. Hơn nữa, nắm bắt chuỗi truy vấn, SE có thể gợi ý truy vấn theo chuỗi, chuỗi gợi ý này là tri thức số đông, cộng đồng thường hỏi sau q1, q2. Đây là mục đích của bài toán thứ hai. 1 https://static.googleusercontent.com/media/guidelines.raterhub.com/en//searchqualityevaluatorguidelines.pdf
3 Hình 1.2: Danh sách trả về từ SE ứng với q1, q2. 2. Mục tiêu của luận án Mục tiêu tổng quát của luận án là tập trung nghiên cứu, xác định và thực nghiệm các phương pháp, các nguyên lý nhằm giải quyết 2 bài toán nêu trên. Cài đặt thực nghiệm các phương pháp và áp dụng các đề xuất cải thiện kỹ thuật. Phân tích, đánh giá kết quả sau thực nghiệm. So sánh với các kỹ thuật khác. 3. Đóng góp của luận án Luận án nghiên cứu giải quyết vấn đề tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa và gợi ý truy vấn hướng ngữ cảnh. Đóng góp chính của luận án gồm: 1) Xây dựng kỹ thuật tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn sử dụng phương pháp phân cụm nhằm nâng cao hiệu quả tìm kiếm. 2) Đề xuất độ đo tương đồng tổ hợp trong bài toán gợi ý truy vấn theo ngữ cảnh nhằm nâng cao chất lượng gợi ý. 3) Ứng dụng kỹ thuật hướng ngữ cảnh, xây dựng máy tìm kiếm chuyên sâu áp dụng hướng ngữ cảnh trong miền cơ sở tri thức riêng (dữ liệu hàng không). 4. Đối tượng nghiên cứu Thuộc lớp bài toán khai phá dữ liệu, khai phá ngữ nghĩa và xử lý ngôn ngữ tự nhiên, đối tượng nghiên cứu trong luận án gồm: - Phương pháp tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn. - Phương pháp gợi ý truy vấn hướng ngữ cảnh.
4 5. Phạm vi của luận án Với phương pháp tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn, bộ dữ liệu thử nghiệm là các tập data-set trích rút từ Viwiki, Vn-news, dữ liệu ngành hàng không (Vietnam Airlines). Miền ngôn ngữ tiếng Việt. Với phương pháp gợi ý truy vấn hướng ngữ cảnh, đặt trọng tâm vào phương pháp hướng ngữ cảnh nên các kỹ thuật chỉnh sửa, viết lại truy vấn không được đề cập trong khuôn khổ luận án. 6. Phương pháp luận Luận án giải quyết các vấn đề nghiên cứu đặt ra theo cách tiếp cận sau: - Khảo sát các kết quả nghiên cứu của một số tác giả đã công bố. - Phân tích, đề xuất giải pháp cho từng vấn đề. - Công bố, trao đổi, thảo luận và báo cáo tại các buổi seminar, hội thảo, hội nghị khoa học, .v.v. - Sử dụng phương pháp nghiên cứu lý thuyết, xây dựng và kiểm thử các mô hình đề xuất trên dữ liệu đã được công bố và dữ liệu tự thu thập. - Kết quả được báo cáo dưới dạng số liệu hoặc trực quan hóa để thuận tiện cho việc đánh giá, kiểm chứng. 7. Cấu trúc luận án Ngoài phần mở đầu, luận án được tổ chức thành 4 chương có bố cục như sau: Chương 1 giới thiệu tổng quan vấn đề nghiên cứu trong luận án, trình bày và phân tích các vấn đề còn tồn tại trong các nghiên cứu liên quan để làm rõ câu hỏi nghiên cứu. Khắc phục các vấn đề còn tồn tại trong các nghiên cứu liên quan, chương 2: Tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa, mục đích giải quyết bài toán thứ nhất. Chương 3: Gợi ý truy vấn hướng ngữ cảnh trong bài toán tìm kiếm, mục đích giải quyết bài toán thứ hai. So sánh đánh giá, kết quả thực nghiệm, kết quả nghiên cứu của luận án được nêu ở cuối mỗi chương. Chương 4 kết luận, nêu ưu nhược điểm, hướng phát triển của luận án và tài liệu tham khảo.
5 CHƯƠNG 1: TỔNG QUAN 1.1. Bài toán tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn Luận án đặt mục tiêu nghiên cứu về tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn (Implicit Relational Search) mô phỏng khả năng suy ra thông tin/tri thức chưa biết bằng suy diễn tương tự, như một khả năng “tự nhiên” của con người. Xét truy vấn gồm các thực thể: “Kinh Qur’an”:“Đạo Hồi”, “sách Phúc Âm”:”?”, con người có khả năng suy diễn tức thời cho dấu “?”, nhưng máy tìm kiếm chỉ đưa ra kết quả là những tài liệu có chứa các từ khóa trên, không đưa ngay được câu trả lời “Kitô giáo”. Do chỉ tìm thực thể, các kỹ thuật như mở rộng truy vấn hoặc viết lại truy vấn không áp dụng với dạng quan hệ có ngữ nghĩa ẩn trong cặp thực thể. Từ đó, một hình thái tìm kiếm mới được nghiên cứu, motive của câu truy vấn tìm kiếm có dạng: {(A, B), (C, ?)}, trong đó (A, B) là cặp thực thể nguồn, (C, ?) là cặp thực thể đích. Đồng thời, hai cặp (A, B), (C, ?) có quan hệ tương đồng về ngữ nghĩa. Cụ thể, khi người sử dụng nhập vào truy vấn gồm 3 thực thể {(A, B), (C, ?)}, máy tìm kiếm có nhiệm vụ liệt kê, tìm kiếm trong danh sách ứng viên các thực thể D (thực thể dấu ?), mỗi thực thể D thỏa điều kiện có quan hệ ngữ nghĩa với C, đồng thời cặp (C, D) có quan hệ tương đồng với cặp (A, B). Quan hệ ngữ nghĩa - theo nghĩa hẹp và dưới góc nhìn từ vựng - được biểu diễn bởi ngữ cảnh gồm các từ/cụm từ (terms/patterns/context) xung quanh (trước, giữa và sau) cặp thực thể đã biết. Vì quan hệ ngữ nghĩa, quan hệ tương đồng không nêu tường minh trong truy vấn (câu truy vấn chỉ gồm 3 thực thể: A, B, C), nên hình thái tìm kiếm theo motive được gọi là mô hình tìm kiếm thực thể dựa trên ngữ nghĩa ẩn (Implicit Relational Entity Search hay Implicit Relational Search, ngắn gọn: IRS). Hình 1.3: Truy vấn: ”Cuba”, “José Marti”, “Ấn Độ” (ngữ nghĩa ẩn: “anh hùng dân tộc”).
6 Tương tự, xét truy vấn chỉ gồm 3 thực thể query q = “Truyện Kiều”:“Nguyễn Du”, “?”:“Victor Hugo”, truy vấn q không mô tả quan hệ ngữ nghĩa (“là kiệt tác”, “tác phẩm nổi tiếng”, “sáng tác bởi” hay “di sản văn hóa”, .v.v.). Mô hình tìm kiếm thực thể dựa trên ngữ nghĩa có nhiệm vụ tìm ra thực thể “?”, thỏa điều kiện có quan hệ ngữ nghĩa với thực thể “Victor Hugo”, đồng thời cặp “?”:“Victor Hugo” tương đồng với cặp “Truyện Kiều”:“Nguyễn Du”. Truyện Kiều là kiệt tác của Nguyễn Du Text Corpus Notre-Dame de Paris là tác phẩm nổi tiếng của Victor Hugo ? = Notre-Dame de Paris (Nguyễn Du, Truyện Kiều) Implicit input Relational output Search Engine (Victor Hugo, ?) (IRS) Hình 1.4: Tìm kiếm dựa trên quan hệ ngữ nghĩa ẩn với truy vấn đầu vào chỉ gồm 3 thực thể. Tìm/tính toán độ tương đồng quan hệ giữa 2 cặp thực thể là một bài toán khó, khó vì: Thứ nhất, độ tương đồng quan hệ biến đổi theo thời gian, xét 2 cặp thực thể (Joe Biden, tổng thống Mỹ) và (Elizabeth, nữ hoàng Anh), độ tương đồng quan hệ biến đổi theo nhiệm kỳ. Thứ hai, do yếu tố thời gian, 2 cặp thực thể có thể không chia sẻ hoặc chia sẻ rất ít ngữ cảnh xung quanh cặp thực thể, như: Apple:iPod (vào 2010s) và Sony:Walkman (vào 1980s), dẫn đến kết quả 2 cặp thực thể không tương đồng. Thứ ba, trong một cặp thực thể, có thể có nhiều quan hệ ngữ nghĩa khác nhau, như: “Ổ dịch Corona khởi phát từ Vũ Hán”; “Corona cô lập thành phố Vũ Hán”; “Số ca lây nhiễm Corona giảm dần ở Vũ Hán”; .v.v. Thứ tư, cặp thực thể chỉ có một quan hệ ngữ nghĩa nhưng có hơn một cách biểu đạt: “X was acquired by Y” và “X buys Y”. Thứ năm, khó do nội tại thực thể có tên (tên cá nhân, tổ chức, địa danh, ..) vốn
7 không phải các từ thông dụng hoặc có trong từ điển. Và cuối cùng, khó do thực thể D chưa biết, thực thể D đang trong tiến trình tìm kiếm. Một trường hợp khác, câu truy vấn theo motive: q = {(A, B), (C, ?)}, nhưng thực tế quan hệ của cặp thực thể (A, B) không chỉ là đơn nghĩa mà có thể là đa nghĩa, lúc này sẽ có nhiều quan hệ ngữ nghĩa khác nhau trong cùng một cặp thực thể. Ví dụ cặp thực thể (Notre Dame:Paris) sẽ có các quan hệ ngữ nghĩa như “vụ cháy”, “biểu tượng”, “tác phẩm văn học”, “chuyện tình thằng gù”, “vương miện gai”, .v.v. Mô hình IRS có nhiệm vụ giải bài toán tìm kiếm như vậy. Mô hình IRS là mô hình sử dụng quan hệ tương đồng từ miền ngữ nghĩa quen thuộc, từ đó suy luận, tìm kiếm thông tin/tri thức trong một miền ngữ nghĩa không quen thuộc. 1.2. Các nghiên cứu liên quan đến tìm kiếm thực thể dựa trên ngữ nghĩa ẩn Motive tìm kiếm của câu truy vấn có dạng: q = {(A, B), (C, ?)}, trong đó (A, B) là cặp thực thể nguồn, (C, ?) là cặp thực thể đích, câu truy vấn chỉ gồm 3 thực thể: A, B, C. Quan hệ ngữ nghĩa, quan hệ tương đồng không được nêu tường minh trong truy vấn. Mô hình tìm kiếm thực thể dựa trên ngữ nghĩa ẩn IRS có nhiệm vụ tìm kiếm thực thể D (thực thể dấu hỏi chấm) chưa biết. Xác định mối quan hệ tương đồng giữa cặp thực thể (A, B), (C, ?) là điều kiện cần để xác định thực thể cần tìm. Thuộc lớp bài toán xử lý ngôn ngữ tự nhiên, độ tương đồng quan hệ là một trong những tác vụ quan trọng nhất của tìm kiếm dựa trên ngữ nghĩa. Do đó, luận án liệt kê các hướng nghiên cứu chính về độ tương đồng quan hệ. 1.2.1. Lý thuyết ánh xạ cấu trúc (Structure Mapping Theory – SMT) Nghiên cứu trong [11] viết: AI và Khoa học nhận thức (Cognitive scientists) cho rằng tương tự là cốt lõi của nhận thức. Nguyên lý có ảnh hưởng nhất đến mô hình tính toán của lập luận tương tự là Lý thuyết ánh xạ cấu trúc (SMT). SMT [12] coi độ tương đồng là ánh xạ “tri thức” (mapping of knowledge) từ miền nguồn vào miền đích, theo luật ánh xạ: Loại bỏ các thuộc tính của đối tượng nhưng vẫn duy trì được ánh xạ quan hệ giữa các đối tượng từ miền nguồn vào miền đích.  Luật ánh xạ (Mapping rules): M: si  ti; (trong đó s: source, t: target).  Loại bỏ thuộc tính: HOT(si) ↛HOT(ti); MASSIVE(si) ↛MASSIVE(ti); ...
8  Duy trì ánh xạ quan hệ: Revolves(Planet, Sun)  Revolves(Electron, Nucleus). Hình 1.5: Ánh xạ cấu trúc SMT. Hình 1.5 cho thấy do cùng các cấu trúc s (subject), o (object), nên SMT xét các cặp: (Planet, Sun) và (Electron, Nucleus) là tương đồng quan hệ, dù cặp đối tượng nguồn và đích - Sun và Nucleus, Planet và Electron rất khác nhau về thuộc tính, như HOT, MASSIVE, … Phân tích: Tham chiếu với mục tiêu nghiên cứu, nếu câu truy vấn là: ((Planet, Sun), (Electron, ?)), SMT sẽ kết xuất câu trả lời chính xác: “Nucleus”. Tuy nhiên, SMT không khả thi với các cấu trúc bậc thấp (thiếu quan hệ). Vì vậy, SMT không khả thi với bài toán tìm kiếm thực thể dựa vào quan hệ ngữ nghĩa ẩn. 1.2.2. Mô hình không gian vector (Vector Space Model - VSM) Áp dụng mô hình không gian vector, Turney [13] đưa ra khái niệm vector mẫu – tần suất, trong đó mỗi vector được tạo thành bởi mẫu (pattern) chứa cặp thực thể (A, B) và tần suất xuất hiện của mẫu. Mô hình không gian vector thực hiện phép đo độ tương đồng quan hệ như sau: Các mẫu được tạo thủ công, query đến Search Engine (SE), số kết quả trả về từ SE là tần suất xuất hiện của mẫu. Từ đó, độ tương đồng quan hệ của 2 cặp thực thể được tính bởi Cosine giữa 2 vector. Ví dụ, xét cặp (traffic, street) và cặp (water, riverbed), 2 cặp này nhiều khả năng cùng xuất hiện trong câu,
9 như: “traffic in the street” và “water in the riverbed”. Độ đo Cosine giữa 2 vector (traffic, street) và (water, riverbed) sẽ quyết định 2 vector có tương đồng hay không. 1.2.3. Phân tích quan hệ tiềm ẩn (Latent Relational Analysis - LRA) Mở rộng VSM, Turney lai ghép VSM với LRA để xác định mức tương đồng quan hệ [14], [15], [16]. Như VSM, LRA sử dụng vector được tạo thành bởi mẫu (pattern/context) chứa cặp thực thể (A, B) và tần suất của mẫu, mẫu được xét theo n- grams. Nói cách khác, phương pháp LRA xác định các n-grams thường xuyên nhất để gắn mẫu với cặp thực thể (A, B). Đồng thời, LRA áp dụng thêm từ điển đồng nghĩa để mở rộng các biến thể như: A bought B, A acquired B; X headquarters in Y, X offices in Y,... Sau đó, LRA xây dựng ma trận mẫu - cặp thực thể, với mỗi phần tử của ma trận biểu diễn tần suất xuất hiện cặp (A, B) thuộc mẫu. Tiến trình LRA thực hiện tương tự với cặp (C, D). Nhằm giảm chiều ma trận, LRA áp dụng SVD (Singular Value Decomposition) để giảm số cột. Cuối cùng, LRA áp dụng phép đo Cosine trên các dòng của ma trận (row vectors) chứa các cặp (A, B) và (C, D) để tính độ tương đồng quan hệ giữa 2 cặp thực thể. Phân tích: Tuy là cách tiếp cận hiệu quả để xác định độ tương đồng quan hệ, LRA đòi hỏi thời gian tính toán, xử lý khá dài, tham khảo trong [17] cho biết với 374 SAT analogy questions (các câu hỏi loại suy của kỳ thi đánh giá năng lực SAT – Scholastic Aptitude Test), kỹ thuật LRA cần 8 ngày để thực hiện. Điều này không khả thi với một hệ tìm kiếm đáp ứng thời gian thực. 1.2.4. Ánh xạ quan hệ tiềm ẩn (Latent Relation Mapping Engine – LRME) Để cải thiện việc dựng các luật ánh xạ, các cấu trúc s (subject), o (object) một cách thủ công trong SMT, Turney áp dụng phép ánh xạ quan hệ tiềm ẩn LRME [11], bằng cách kết hợp SMT và LRA. Mục đích: Tìm mối quan hệ giữa 2 terms A, B (xét terms như là thực thể). Với đầu vào (bảng 1.1) là 2 danh sách các terms từ 2 miền (nguồn và đích), đầu ra (bảng 1.2) là kết quả ánh xạ 2 danh sách: Bảng 1.1: Tìm tương quan giữa các thuật ngữ (terms) trong 2 danh sách Miền nguồn Miền đích planet revolves attracts atom revolves attracts