Tóm tắt 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:27

Thêm vào BST

Báo xấu

17
lượt xem 4
download

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

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 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: Tóm tắt 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 Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9.46.01.10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2020
Công trình được hoàn thành tại: 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. Người hướng dẫn khoa học: TS. Vũ Tất Thắng Phản biện 1: … Phản biện 2: … Phản biện 3: …. Luận án sẽ được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Học viện, họp tại 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 vào hồi … giờ ..’, ngày … tháng … năm 202…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
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. 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”. 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ự. Hình 1.1: Danh sách trả về từ Keyword-SE ứng với query=”Việt Nam”, “Hà Nội”, “Pháp”. 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. Cũng theo thống kê, các câu truy vấn người dùng đưa vào thường ngắn, mơ hồ, đa nghĩa [1-6]. 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ụng1. Từ đó, có rất 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), đề xuất 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 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 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 1 https://static.googleusercontent.com/media/guidelines.raterhub.com/en//searchqualityevaluatorguidelines.pdf
2 là ai”, q2: “Ông ấy bao nhiêu tuổi”, q1, q2 có liên quan ngữ nghĩa. Tuy nhiên kết quả trả về cho 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. Hình 1.2: Danh sách trả về từ SE ứng với q1, q2. 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. 2. Mục tiêu nghiên cứ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. Các nội dung nghiên cứu chính của luận án 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 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 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 SE 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 mở rộng hoặc viết lại câu 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 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ể
3 đã biết2. 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) Xét input query chỉ gồm 3 thực thể q = “Mê Kông”:“Việt Nam”, “?”:“Trung Quốc”. Truy vấn q chỉ gồm 3 thực thể (“Mê Kông”:“Việt Nam”, “?”:“Trung Quốc”). Truy vấn q không mô tả quan hệ ngữ nghĩa (“sông dài nhất” hay “lớn nhất” hay “lưu vực rộng nhất”, .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ể “Trung Quốc”, đồng thời cặp “?”:“Trung Quốc” tương đồng với cặp “Mê Kông”:“Việt Nam”. 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, khó do nội tại thực thể có tên (tên cá nhân, tổ chức, địa danh, ..) vốn không phải các từ thông dụng hoặc có Hình 1.3: Input query: ”Cuba”, “José Marti”, “Ấn Độ” (ngữ trong từ điển. nghĩa ẩn: “anh hùng dân tộc”) 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ư, 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ứ năm, 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”. 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. Motive tìm kiếm của câu truy vấn có dạng: q = {(A, B), (C, ?)}, truy vấn chỉ gồm 3 thực thể: A, B, C. 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. Các nghiên cứu liên quan đến tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn 1.2.1. Lý thuyết ánh xạ cấu trúc (Structure Mapping Theory – 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); ...  Duy trì ánh xạ quan hệ: Revolves(Planet, Sun)  Revolves(Electron, Nucleus). 2 Birger Hjorland. Link: http://vnlp.net.
4 Hình 1.5 cho thấy do cùng cấu trúc s (subject), o (object), 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, Nucleus), (Planet, Electron) khác nhau về thuộc tính: HOT, MASSIVE, …Tham chiếu với mục tiêu nghiên cứu, nếu truy vấn là: ((Planet, Sun), (Electron, ?)), SMT sẽ kết xuất câu trả lời chính xác: “Nucleus”. Hình 1.5: Ánh xạ cấu trúc SMT. Nhưng SMT không khả thi với cấu trúc bậc thấp (thiếu quan hệ). Vì vậy SMT không khả thi với tìm kiếm thực thể dựa vào quan hệ ngữ nghĩa ẩn. 1.2.2. Tương đồng quan hệ dựa trên hệ thống phân loại tương đồng Wordnet Cao [20] và Agirre [21] đề xuất độ đo tương đồng quan hệ dựa trên hệ phân loại tương đồng trong Wordnet, tuy nhiên như các phương pháp trên, Wordnet không chứa thực thể có tên (Named Entity), vì vậy Wordnet không thích hợp với mô hình tìm kiếm thực thể. 1.2.3. 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 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. VSM 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. 1.2.4. Phân tích quan hệ tiềm ẩn (Latent Relational Analysis - LRA) Turney lai ghép VSM với LRA nhằm xác định mức tương đồng quan hệ [14-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 xét theo n- grams. Đồng thời, LRA áp dụng từ điển đồng nghĩa để mở rộng các biến thể của: A bought B, A acquired B; X headquarters in Y, X offices in Y, ... LRA áp dụng tìm n-grams thường xuyên nhất để gắn mẫu với cặp thực thể (A, B). Sau đó xây dựng ma trận mẫu - cặp thực thể, trong đó 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. Nhằm giảm chiều ma trận, LRA áp dụng SVD (Singular Value Decomposition) để giảm số cột trong ma trận. Cuối cùng, LRA áp dụng phép đo Cosine để tính độ tương đồng quan hệ giữa 2 cặp thực thể. 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 [17] cho biết LRA cần 8 ngày để thực hiện 374 SAT analogy questions. Đ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.5. Á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.
5 1.2.6. Quan hệ ngữ nghĩa tiềm ẩn (Latent Semantic Relation – LSR) Bollegala, Duc [17-18], Kato [19] sử dụng giả thuyết phân phối (Distributional hypothesis) ở mức context: Trong corpus, nếu 2 context pi, pj khác nhau nhưng thường đồng hiện với các cặp thực thể wm, wn thì 2 context pi, pj tương tự về ngữ nghĩa. Khi pi, pj tương tự về ngữ nghĩa, các cặp thực thể wm, wn tương đồng về quan hệ. Giả thuyết phân phối đòi hỏi các cặp thực thể phải luôn “đồng hiện” với các context, đồng thời giải thuật gom cụm Bollega đề xuất ở mức context (mức câu) chứ không thực hiện gom cụm ở mức terms trong câu. Độ tương đồng chỉ dựa trên giả thuyết phân phối mà không dựa trên tương đồng về term sẽ ảnh hưởng không nhỏ đến chất lượng của kỹ thuật gom cụm, từ đó ảnh hưởng đến chất lượng của hệ tìm kiếm. 1.2.7. Mô hình học biểu diễn vector từ Word2Vec Mô hình Word2Vec do Mikolov và các đồng sự đề xuất [22], là mô hình học biểu diễn mỗi từ thành một vector (ánh xạ một từ thành one-hot vector), Word2Vec diễn tả mối quan hệ (xác suất) giữa từ với ngữ cảnh của từ. Mô hình Word2Vec có 2 kiến trúc mạng nơ-ron đơn giản: Continous Bag-Of-Words (CBOW) và Skip-gram. Áp dụng Skip-gram, ở mỗi bước huấn luyện, mô hình Word2Vec dự đoán các ngữ cảnh trong vòng skip-gram nhất định. Giả sử từ huấn luyện input là “banking”, với cửa sổ trượt skip = m = 2, output ngữ cảnh trái sẽ kết xuất là “turning into”, output ngữ cảnh phải là “crises as”. Hình 1.6: Quan hệ giữa từ mục tiêu và ngữ cảnh trong mô hình Word2Vec. Để dự đoán, hàm mục tiêu trong Skip-gram thực hiện tối đa hóa xác suất. Với một chuỗi từ huấn luyện w1, w2, …, wT, Skip-gram áp dụng Maximum Likelihood: 𝑇 1 𝐽(𝜃) = ∑ ∑ log 𝑝(𝑤𝑡+𝑗 |𝑤𝑡 ) 𝑇 𝑡=1 −𝑚≤𝑗≤𝑚,𝑗≠0 trong đó: T: số lượng từ có trong data-set; t: từ được huấn luyện; m: window-side (skip); 𝜃: vector biểu diễn; Quá trình huấn luyện áp dụng giải thuật lan truyền ngược (back-propagation), Xác suất đầu ra p(wt+j|wt) xác định bởi hàm kích hoạt softmax: exp⁡(𝑢𝑜𝑇 ⁡𝑣𝑐 ) 𝑝(𝑜|𝑐) = ∑𝑊 𝑇 𝑤−1 exp⁡(𝑢𝑤 ⁡𝑣𝑐 )
6 trong đó: W: Vocabulary; c: từ được huấn luyện (input/center); o: output của c; u: Vector biểu diễn của o; v: Vector biểu diễn của c; Trong thực nghiệm, Mikolov et al. [22-25] xử lý cụm từ như một từ đơn, loại bỏ các từ lặp lại thường xuyên, sử dụng hàm Negative Sampling loss function chọn ngẫu nhiên n từ để xử lý tính toán thay vì toàn bộ các từ trong data-set, giúp cho thuật toán huấn luyện nhanh hơn so với hàm softmax nói trên. Hình 1.7: Word2Vec “học” quan hệ “ẩn” giữa từ mục tiêu và ngữ cảnh của từ3. Các phép toán vector như: vec(“king”) - vec(“man”) ≈ vec(“queen”) - vec(“woman”) cho thấy mô hình Word2Vec phù hợp với truy vấn dạng “A:B :: C:?”, nói cách khác, mô hình Word2Vec khá gần với hướng nghiên cứu của luận án. Điểm khác biệt: đầu vào Word2Vec (theo mô hình Skip-gram) là một từ, đầu ra là một ngữ cảnh. Đầu vào của mô hình tìm kiếm thực thể dựa trên ngữ nghĩa là 3 thực thể (A:B :: C:?), đầu ra là thực thể cần tìm kiếm (D). Về tìm kiếm thực thể dựa trên ngữ nghĩa, từ các vấn đề còn tồn tại, để tiệm cận đến một “trí thông minh nhân tạo” trong máy tìm kiếm, luận án nghiên cứu, áp dụng các kỹ thuật mô phỏng khả năng tự nhiên của con người: khả năng suy ra thông tin/tri thức không xác định bằng suy diễn tương tự. 1.3. Bài toán gợi ý truy vấn hướng ngữ cảnh Đối với SE, khả năng “hiểu” ý định tìm kiếm trong câu truy vấn của người sử dụng là một thách thức. Tập dữ liệu được sử dụng để khai phá là Query Log (nhật ký truy vấn, QLogs). Tập truy vấn trong quá khứ QLogs ghi lại các truy vấn và “tương tác” của người dùng với công cụ tìm kiếm, do vậy QLogs chứa các thông tin giá trị về nội dung truy vấn, mục đích, hành vi, thói quen, sở thích cũng như các phản hồi ngầm (implicit feedback) của người sử dụng trên tập kết quả mà SE trả về. Khai phá tập dữ liệu QLogs có ích trong nhiều ứng dụng: Phân tích truy vấn, quảng cáo, xu hướng, cá nhân hóa, gợi ý truy vấn, .v.v. Đối với gợi ý truy vấn, các kỹ thuật truyền thống như Explicit Feedback [30-32], Implicit Feedback [33- 36], User profile [37-39], Thesaurus [40-42], … chỉ đưa ra các gợi ý tương tự với input query của người dùng: Hình 1.12: Gợi ý truy vấn bằng các kỹ thuật truyền thống với input query “điện thoại di động”. 1.4. Các nghiên cứu liên quan đến gợi ý truy vấn Xoay quanh hạt nhân là Qlogs, có thể nói việc gợi ý truy vấn theo các kỹ thuật truyền thống thực hiện 2 chức năng chính: 3 https://cs224d.stanford.edu/lectures/CS224d-Lecture2.pdf
7  Kỹ thuật dựa trên cụm áp dụng phép đo độ tương đồng nhằm gom các truy vấn tương tự nhau thành từng cụm (nhóm).  Kỹ thuật dựa trên phiên với phiên tìm kiếm là một chuỗi liên tục các câu truy vấn. 1.4.1. Kỹ thuật gợi ý truy vấn dựa trên phiên (Session) a) Dựa vào các câu truy vấn đồng hiện (co-occurrence) hay liền kề (adjacency) thuộc các sessions trong Qlog: Trong cách tiếp cận dựa trên Session, các cặp truy vấn liền kề (adjacency) hoặc đồng hiện (co-occurrence) thuộc cùng một phiên đóng vai trò danh sách ứng viên cho đề xuất truy vấn. b) Dựa vào đồ thị (Query Flow Graph - QFG): Trên đồ thị QFG, 2 truy vấn qi, qj cùng thuộc ý đồ tìm kiếm (search mission) được biểu diễn như một cạnh có hướng từ qi tới qj. Mỗi node trên đồ thị tương ứng với một truy vấn, bất kỳ cạnh nào trên đồ thị cũng được xem như 1 hành vi tìm kiếm (searching behavior). Cấu trúc tổng quát phiên trong CFG được biểu diễn: QLog = ; Boldi et al. [50, 51] sử dụng cấu trúc phiên rút gọn QLog = để thực hiện gợi ý truy vấn, theo một dãy các bước:  Xây dựng đồ thị QFG với đầu vào là tập các phiên trong Query Logs.  Hai truy vấn qi và qj được nối với nhau nếu tồn tại ít nhất một phiên mà qi, qj xuất hiện liên tiếp.  Tính trọng số w(qi, qj) trên mỗi cạnh: 𝑓(𝑞𝑖 ,⁡𝑞𝑗 ) , 𝑖𝑓⁡(𝑤(𝑞𝑖 , 𝑞𝑗 ) > 𝜃) ∨ (𝑞𝑖 = 𝑠) ∨ (𝑞𝑖 = 𝑡) w(qi, qj) = { 𝑓(𝑞𝑖 ) (1.6) 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 trong đó: f(𝑞𝑖 ,⁡𝑞𝑗 ): số lần xuất hiện qj ngay sau qi trong phiên; f(qi): số lần xuất hiện qi trong QLogs; 𝜃: threshold; s, t: 2 node trạng thái bắt đầu, kết thúc của chuỗi truy vấn trong phiên;  Xác định các chuỗi thỏa điều kiện (1.6) để phân tích ý đồ của người dùng: Khi truy vấn mới đưa vào, dựa vào đồ thị, đưa ra các gợi ý truy vấn lần lượt có trọng số cạnh lớn nhất. 1.4.2. Kỹ thuật gợi ý truy vấn dựa trên cụm (Cluster)  K-means;  Hierarchical;  DB-SCAN; … Hình 1.9: Các phương pháp phân cụm [54]. Gợi ý truy vấn hướng ngữ cảnh (Context-aware Query Suggestion) là một nét mới, Context-aware xét các truy vấn đứng ngay trước truy vấn hiện hành như một ngữ cảnh tìm kiếm, nhằm “nắm bắt” ý định tìm kiếm của người dùng. Kế tiếp, khai phá các truy vấn đứng ngay sau truy vấn hiện hành - như danh sách gợi ý. Đây là ưu điểm riêng của cách tiếp cận này - so với cách tiếp cận chỉ gợi ý những truy vấn tương tự. Lớp truy vấn đứng ngay sau truy vấn hiện hành, một cách hình thức, phản ánh những vấn đề mà người dùng thường hỏi sau truy vấn hiện
8 hành. Đồng thời, lớp truy vấn ngay sau truy vấn hiện hành thường gồm những câu truy vấn (chuỗi truy vấn) tốt hơn, phản ánh rõ hơn ý đồ tìm kiếm. 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 Trong tự nhiên, tồn tại mối quan hệ giữa 2 thực thể, như: Khuê Văn các – Văn miếu; Stephen Hawking – Nhà vật lý; Thích Ca – phái Đại thừa; Apple – iPhone; ... Trong thế giới thực, tồn tại những câu hỏi dạng: “biết Fansipan là ngọn núi cao nhất Việt Nam thì ngọn núi nào cao nhất Ấn Độ?”, “nếu Biden là tổng thống đắc cử Hoa Kỳ thì ai là người quyền lực nhất Thụy Điển?”, … Trong cơ chế tìm kiếm theo từ khóa, theo thống kê, các truy vấn thường ngắn, mơ hồ và đa nghĩa [1-6]. Cũng 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]. Nếu người sử dụng nhập vào các thực thể: “Việt Nam”, “Hà Nội”, “Pháp” thì máy tìm kiếm chỉ đưa ra được kết quả là những tài liệu có chứa các từ khóa trên chứ không đưa ngay được câu trả lời “Paris”. Do chỉ tìm thực thể, các kỹ thuật mở rộng, viết lại câu 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. Nói cách khác, khi người sử dụng nhập vào truy vấn {(A, B), (C, ?)}, máy tìm kiếm có nhiệm vụ liệt kê danh sách các thực thể D, 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). Với đầu vào chỉ gồm 3 thực thể: “Việt Nam”, “Hà Nội”, “Pháp”, quan hệ ngữ nghĩa “là thủ đô” không được chỉ ra trong câu truy vấn. 2.2. Phương pháp tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn 2.2.1. Kiến trúc – Mô hình Khái niệm tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn là phân biệt rõ nhất đối với cơ chế tìm kiếm theo từ khóa. Hình 2.1 mô phỏng câu truy vấn chỉ gồm 3 thực thể, query = {(Việt Nam, Mê Kông), (Trung Quốc, ?)}, viết quy ước: q = {(A, B), (C, ?)}. Trong đó (Việt Nam, Mê Kông) là cặp thực thể nguồn, (Trung Quốc, ?) là cặp thực thể đích. Máy tìm kiếm có nhiệm vụ tìm ra thực thể (“?”) có quan hệ ngữ nghĩa với thực thể “Trung Quốc”, đồng thời cặp thực thể (Trung Quốc, ?) phải tương đồng quan hệ với cặp thực thể (Việt Nam, Mê Kông). Lưu ý rằng câu truy vấn trên không chứa một cách tường minh quan hệ ngữ nghĩa giữa 2 thực thể. Việc không tường minh quan hệ ngữ nghĩa bởi trên thực tế - quan hệ ngữ nghĩa được biểu đạt dưới nhiều cách khác nhau xung quanh cặp thực thể (Việt Nam, Mê Kông), ví dụ như “sông dài nhất”, “sông lớn nhất”, “lưu vực rộng nhất”… 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ể.
9 Do câu truy vấn chỉ gồm 3 thực thể không bao gồm quan hệ ngữ nghĩa, nên mô hình được gọi là mô hình tìm kiếm thực thể dựa trên ngữ nghĩa ẩn. Máy tìm kiếm có nhiệm vụ tìm ra thực thể (“?”) có quan hệ ngữ nghĩa với thực thể “Trung Quốc”, đồng thời cặp thực thể (Trung Quốc, ?) phải tương đồng quan hệ với cặp thực thể (Việt Nam, Mê Kông). Lưu ý rằng câu truy vấn trên không chứa một cách tường minh quan hệ ngữ nghĩa giữa 2 thực thể. Việc không tường minh quan hệ ngữ nghĩa bởi trên thực tế - quan hệ ngữ nghĩa được biểu đạt dưới nhiều cách khác nhau xung quanh cặp thực thể (Việt Nam, Mê Kông), ví dụ như “sông dài nhất”, “sông lớn nhất”, “lưu vực rộng nhất”…: Do o câu truy vấn chỉ gồm 3 thực thể không bao gồm quan hệ ngữ nghĩa, nên mô hình được gọi là mô hình tìm kiếm thực thể dựa trên ngữ nghĩa ẩn. Mô hình tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn (IRS) gồm 3 thành phần chính: Thành phần rút trích quan hệ ngữ nghĩa: Từ corpus, rút trích các mẫu (câu gốc chứa cặp thực thể và context), như: A sông dài nhất B, với A, B là 2 tên thực thể (Named Entity). Tập mẫu thu được gồm: các mẫu thực sự khác nhau, các mẫu giống nhau, các mẫu có độ dài và terms khác nhau nhưng biểu đạt cùng ngữ nghĩa, chẳng hạn: A là sông lớn nhất của B, A là sông thuộc B có lưu vực rộng nhất, hay B có sông dài nhất là A, .v.v. Thành phần gom cụm các quan hệ ngữ nghĩa: Từ tập mẫu thu được, thực hiện gom cụm để xác định các cụm chứa các mẫu (context), trong đó mỗi context thuộc cùng cụm có quan hệ tương đồng về ngữ nghĩa. Lập chỉ mục các mẫu và cặp thực thể tương ứng. Thành phần tính toán quan hệ tương đồng giữa 2 cặp thực thể: Thuộc phase online của mô hình IRS. Đón truy vấn q = {(A, B), (C, ?)}, IRS tìm kiếm trong bảng chỉ mục cặp thực thể (A, B) và tập quan hệ ngữ nghĩa (mẫu) tương ứng. Từ tập quan hệ ngữ nghĩa thu được, thực hiện tìm các cặp thực thể (C, Di) gắn với quan hệ. Áp dụng độ đo Cosine tính toán, xếp hạng mức tương đồng giữa (A, B) và (C, Di), đưa ra danh sách các thực thể Di đã xếp hạng để trả lời truy vấn. Query: {(Việt Nam, Mê Kông), (Trung Quốc, ?)} Xét truy vấn q = {(Việt Nam, Mê Kông), (Trung Quốc, ?)}, IRS tìm được cụm Corpus Tập kết quả trả về chứa cặp thực thể (Việt Nam, Mê Kông) và được phân hạng quan hệ ngữ nghĩa tương ứng: “sông dài nhất” (từ câu gốc: “Mê Kông là sông dài nhất Việt Rút trích quan Tính độ tương Nam”). Cụm này đồng thời chứa một quan hệ hệ ngữ nghĩa đồng quan hệ (RelSim) ngữ nghĩa tương tự: “sông lớn nhất”, trong đó quan hệ “sông lớn nhất” gắn với gặp thực thể Cặp thực thể - Tập kết quả ứng (Trung Quốc, Trường Giang) (từ câu gốc: Quan hệ ngữ viên “Trường Giang là sông lớn nhất Trung Quốc”). nghĩa IRS sẽ đưa “Trường Giang” vào danh sách ứng viên, xếp hạng quan hệ ngữ nghĩa theo phép đo Gom cụm quan Chỉ mục đảo Inverted độ tương đồng, trả kết quả về người tìm kiếm. hệ ngữ nghĩa Index for IRS 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.
10 2.2.2. Thành phần rút trích quan hệ ngữ nghĩa Nhận truy vấn q = {(A, B), (C, ?}, kiến trúc tổng quát của IRS được mô hình hóa:  Hàm Filter-Entities (Fe) lọc/tìm tập ứng viên S chứa các cặp thực thể (C, Di); trong đó (C, Di) quan hệ tương đồng với cặp thực thể đầu vào (A, B): 1, 𝑖𝑓⁡𝑅𝑒𝑙𝑒𝑣𝑎𝑛𝑡(𝑞, 𝐷) Fe(q, D) = Fe({(A, B), (C, ?)}, D) = { (2.1) 0, 𝑒𝑙𝑠𝑒  Hàm Rank-Entities (Re) tính RelSim, xếp hạng các thực thể Di, Dj trong tập ứng viên S theo phép đo RelSim (Relational Similarity), thực thể nào có RelSim cao hơn được xếp thứ tự thấp hơn (theo nghĩa gần top hơn, hay rank cao hơn): ∀ Di, Dj ∊ S, nếu: RelSim((A, B),(C, Di)) > RelSim((A, B),(C, Dj)) : Re(q, Di) < Re(q, Dj) (2.2) 2.2.3. Thành phần gom cụm các quan hệ ngữ nghĩa Tiến trình gom cụm thực hiện gom các phần tử “tương tự” nhau vào thành cụm. Trong mô hình tìm kiếm thực thể dựa trên ngữ nghĩa, các phần tử trong cụm là các câu context tương đồng về ngữ nghĩa. Độ tương đồng là một đại lượng dùng để so sánh 2 hay nhiều phần tử với nhau, phản ánh mối tương quan giữa 2 phần tử. Do đó, luận án khái quát các phép đo độ tương đồng về terms, độ tương đồng dựa trên không gian vector, độ tương đồng ngữ nghĩa – của 2 context. a) Các phép đo độ tương đồng giữa 2 context  Độ tương đồng về terms Hàm Zaro: Winkler4. Khoảng cách Zaro tính độ tương đồng giữa 2 xâu ký tự a, b: 0,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑖𝑓⁡𝑚 = 0 SimZaro(a,b) = {1 𝑚 𝑚 𝑚−𝑠𝑘𝑖𝑝 (2.6) ( + |𝑏| + 𝑚 ) ⁡⁡⁡⁡⁡⁡𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 3 |𝑎| Constrast model: Do Tversky đề xuất (“Features of similarity”, Psychological Review, 1977)5, áp dụng mô hình tương phản để tính độ tương đồng giữa 2 câu a, b: Sim(a, b)⁡=⁡α*f(a∩b) − 𝛽*f(a-b) − γ*f(b−a) (2.8) |𝑎∩𝑏| Khoảng cách Jaccard: Sim(a, b) = |𝑎∪𝑏| (2.9)  Độ tương đồng dựa trên không gian vector: Euclidean, Manhattan, Cosine.  Độ tương đồng ngữ nghĩa Theo Giả thuyết phân phối [17]: Các từ xảy ra trong cùng ngữ cảnh thì có xu hướng tương đồng ngữ nghĩa. Do tiếng Việt chưa có hệ thống Vietwordnet để tính toán độ tương đồng ngữ nghĩa giữa 2 terms, luận án sử dụng độ tương hỗ PMI để đo, đánh giá độ tương đồng ngữ nghĩa giữa 2 câu (context). Phương pháp PMI (Pointwise Mutual Information): Được đề xuất bởi Church and Hanks [1990]. Dựa vào xác suất đồng xảy ra giữa 2 terms t1, t2 trong kho ngữ liệu, độ tương hỗ t1, t2 được tính theo công thức: 𝑷(𝒕𝟏 ,𝒕𝟐 ) PMI(t1, t2) = log2( ) (2.16) 𝑷(𝒕𝟏 ).𝑷(𝒕𝟐 ) 4 https://en.wikipedia.org/wiki/Jaro-Winkler_distance 5 http://www.cogsci.ucsd.edu/~coulson/203/tversky-features.pdf
11 b) Thành phần gom cụm các quan hệ ngữ nghĩa  Áp dụng PMI cải tiến độ đo tương đồng theo giả thuyết phân phối: ∑𝑖(𝑃𝑀𝐼(𝑤𝑖 ,𝑝)∙𝑃𝑀𝐼(𝑤𝑖 ,𝑞)) SimDH(p,q) = Cosine(PMI(p, q)) =⁡ (2.25) ||𝑃𝑀𝐼(𝑤𝑖 ,𝑝)||||𝑃𝑀𝐼(𝑤𝑖 ,𝑞)||  Độ tương đồng theo terms của 2 context p, q: ∑n i=1(weighti (p)∙weighti (q)) Simterm (p, q) = ⁡ ||weight(p)||⁡||weight(q)|| (2.26)  Độ đo tương đồng kết hợp: Sim(p,q) = Max(SimDH(p, q),Simterm(p, q)) (2.27) c) Giải thuật gom cụm: - Đầu vào: Tập P = {p1, p2, …, pn}; Ngưỡng phân cụm θ1, ngưỡng heuristic θ2; Dmax: Đường kính cụm; Sim_cp: Kết quả hàm đo độ tương đồng kết hợp, áp dụng theo công thức (2.27). - Đầu ra: Tập cụm Cset (ClusterID, context, trọng số mỗi context. cặp thực thể tương ứng). Program Clustering_algorithm 01. Cset = {}; iCount=0; 02. for each context pi ∈ P do 03. Dmax = 0; c* = NULL; 04. for each cluster cj ∈ Cset do 05. Sim_cp=Sim(pi,Centroid(cj)) 06. if (Sim_cp > Dmax) then 07. Dmax = Sim_cp; c* ← cj; 08. end if 09. end for 10. if (Dmax > θ1) then 11. c*.append(pi) 12. else 13. Cset ∪= new cluster{c*} 14. end if 15. if (iCount > θ2) then 16. iCount++; 17. exit Current_Proc_Cluster_Alg(); 18. end if 19. end for 20. Return Cset; @CallMerge_Cset_from_OtherNodes() 2.2.4. Thành phần tính toán độ tương đồng giữa 2 cặp thực thể Thành phần tính toán độ tương đồng quan hệ giữa 2 cặp thực thể thực hiện 2 tác vụ: Lọc (tìm) và Phân hạng. Nhận vào q={(A, B), (C, ?)}, thông qua chỉ mục inverted index, IRS gọi hàm Filter-Entities Fe đặt lọc (tìm) tập ứng viên chứa các cặp thực thể (C, Di) và quan hệ ngữ nghĩa (context) tương ứng, với điều kiện (C, Di) tương đồng với (A, B). Kế tiếp, gọi hàm Rank-Entities Re để xếp hạng các thực thể Di, Dj trong tập ứng viên theo phép đo RelSim (Relational Similarity), trả về danh sách các {Di} đã xếp hạng. Giải thuật Filter-Entities: Lọc tìm tập ứng viên chứa câu trả lời: Đầu vào: Query q = (A, B)(C, ?) Đầu ra: Tập ứng viên S (gồm các thực thể Di và context tương ứng); Program Filter_Entities
12 01. S = {}; 02. P(w) = EntPair_from_Cset.Context(); 03. for each context pi ∈ P(w) do 04. W(p) = Context(pi).EntPairs(); 05. If (W(p) contains (C:Di)) then S ∪= W(p); 06. end for 07. retufn S Sau thực thi Filter-Entities, thu được tập con gồm các thực thể Di và context tương ứng. Tiến trình RelSim chỉ thực hiện xử lý, tính toán trên tập con này, đồng thời áp dụng ngưỡng α để loại các thực thể Di có giá trị RelSim thấp. Với: Fe(q,D) = Fe({(A, B),(C,?)}, D): 1, 𝑖𝑓⁡𝑅𝑒𝑙𝑆𝑖𝑚((𝐴, 𝐵), (𝐶, 𝐷𝑖 )) > α 𝐹𝑒 (𝑞, 𝐷𝑖 ) = { (2.29) 0, 𝑒𝑙𝑠𝑒 Giải thuật Rank-Entities: Giải thuật Rank-Entities có nhiệm vụ tính RelSim: Đầu vào gồm: Tập ứng viên S và: - Cặp thực thể nguồn (A, B), ký hiệu s; Các thực thể ứng viên (C, Di), ký hiệu c; - Các context tương ứng với s, c; Tập cụm thu được: Cset; - Các thực thể A, B, C đã biết  tập cụm tương ứng chứa A, B, C được xác định; - Ngưỡng α (so giá trị RelSim); Ngưỡng α xác định trong kiểm thử chương trình. - Khởi tạo tích vô hướng (β); tập used-context (γ); Đầu ra: Danh sách câu trả lời (danh sách thực thể được xếp hạng) Di; Ký hiệu: - P(s), P(c) được nêu trong công thức (2.19), (2.20); - f(s, pi), f(c, pi), ɸ(s), ɸ(c) nêu trong (2.21), (2.22); - γ: Biến (dạng tập hợp) giữ các context đã xét; - q: Biến trung gian (Context); Ω: Cụm; - Program Rank_Entities 01. for each context pi ∈ P(c) do 02. if (pi ∈ P(s)) then 03. β ← β + f(s, pi)·f(c, pi) 04. γ ← γ ∪ {p} 05. else 06. Ω ← cluster contains pi 07. max_co-occurs = 0; 08. q← NULL; 09. for each context pj ∈ (P(s)\P(c)\γ) do 10. if (pj ∈ Ω) & (f(s, pj) > max_co-occurs) 11. max_co-occurs ← f(s, pj); 12. q ← pj; 13. end if 14. end for 15. if (max_co-occurs > 0) then 16. β ← β + f(s, q)·f(c, pi)
13 17. γ ← γ ∪ {q} 18. end if 19. end if 20. end for 21. RelSim ← β/L2-norm(ɸ(s), ɸ(c)) 22. if (RelSim ≥ α) then return RelSim Diễn giải giải thuật: Trường hợp 2 cặp thực thể nguồn và đích cùng một quan hệ ngữ nghĩa (cùng chia sẻ chung một context, câu lệnh 1-2): pi ∊ P(s) ∩ P(c), tính tích vô hướng tương tự như công thức Cosine tính độ tương đồng. Trường hợp pi ∊ P(c) nhưng pi ∉ P(s), giải thuật tìm context pj (hay biến trung gian q, dòng 12), trong đó pi, pj thuộc cùng một cụm đã biết. Thân vòng lặp (từ lệnh 10-13) chọn ra context pj có số lần đồng hiện (co-occurs) với s lớn nhất. Theo giả thuyết phân phối, 2 context pi, pj đồng hiện trong càng nhiều cặp thực thể, độ tương đồng Cosine giữa 2 vector càng cao. Khi giá trị Cosine càng cao, pi, pj càng tương tự. Nói cách khác, cặp (C, Di) càng chính xác và nhất quán ngữ nghĩa với cặp thực thể nguồn (A, B). Dãy câu lệnh từ 15-18 tính tích vô hướng. Các câu lệnh 21-22 tính giá trị RelSim. Từ tập RelSim thu được, sắp xếp để thực thể Di nào có RelSim cao hơn được xếp thứ tự thấp hơn (theo nghĩa gần top hơn, hay rank cao hơn). Tập kết quả Di là danh sách câu trả lời cho truy vấn mà người dùng muốn tìm. 2.3. Kết quả thực nghiệm – Đánh giá 2.3.1. Dataset Tập dataset được xây dựng từ tập dữ liệu mẫu trong thực nghiệm, dựa vào 4 phân lớp thực thể có tên: PER; ORG; LOC và TIME; 2.3.2. Kiểm thử - Điều chỉnh tham số Để đánh giá hiệu quả của thuật toán phân cụm và thuật toán xếp hạng ứng viên Rank_Entities, Chương 2 thực hiện thay đổi các giá trị θ1 và α, sau đó tính các độ đo Precision, Recall, F-Score tương ứng với mỗi giá trị thay đổi của α, θ1. Hình 2.3 cho thấy tại α = 0.5, θ1 = 0.4, điểm F-Score đạt giá trị cao nhất. Hình 2.3: Giá trị F-Score tương ứng với mỗi giá trị thay đổi của α, θ1. Giải thuật Rank_Entities dòng 22 (if (RelSim ≥ α) return RelSim) cũng cho thấy, khi α nhỏ thì số lượng ứng viên tăng, có thể có nhiễu, đồng thời thời gian xử lý real-time tốn chi phí thời gian, do hệ thống xử lý nhiều truy vấn ứng viên. Ngược lại khi α lớn thì giá trị Recall nhỏ, kéo theo F-Score giảm đáng kể. 2.3.3. Đánh giá với độ đo MRR (Mean Reciprocal Rank) Đối với bộ truy vấn Q, nếu thứ hạng câu trả lời đúng đầu tiên trong truy vấn q ∈ Q là rq, thì độ đo MRR của Q được tính: 1 1 MRR(Q) = |𝑄| ∑𝑞∈𝑄 𝑟 (2.33) 𝑞 Với 4 phân lớp thực thể: PER; ORG; LOC và TIME; phương pháp dựa trên tần suất đồng hiện (f) đạt giá trị trung bình MRR ≈ 0.69; trong khi đó, phương pháp dựa trên PMI đạt 0,86. Điều này cho thấy PMI giúp cải thiện độ chính xác về tương đồng ngữ nghĩa tốt hơn tần suất đồng hiện của context-cặp thực thể.
14 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. 2.3.4. Hệ thống thực nghiệm Tập dữ liệu mẫu trong thực nghiệm được download từ các nguồn Viwiki (7877 files) và Vn-news (35440 files). Mục đích chọn nguồn Viwiki và Vn-news vì các dataset này chứa các mẫu gồm các thực thể có tên (Named Entity). Tiến trình đọc, lấy nội dung file, tách đoạn, tách câu (main-sentences, sub-sentences), thu được 1572616 câu. Các nhãn tổng quát của NER (Named Entity Recognition) gồm: PER: Tên người; ORG: Tên tổ chức; LOC: Địa danh; TIME: Kiểu thời gian; NUM: Kiểu số; CUR: Kiểu tiền tệ; PCT: Kiểu phần trăm; MISC: Kiểu thực thể khác; O: Không phải thực thể. Giải thuật rút trích patterns lưu vào database, sau khi thực hiện các bước xử lý và các điều kiện giới hạn, Database còn lại 404507 câu context. Từ tập context này, giải thuật gom cụm các quan hệ ngữ nghĩa gom được 124805 cụm. Hình 2.5: Thực nghiệm IRS với nhãn thực thể B-PER. Để đánh giá độ chính xác, thực nghiệm thực hiện 500 queries để kiểm thử, kết quả cho thấy độ chính xác đạt khoảng 92%. 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 ID A B C D .. German Angela Merkel Israel Benjamin Netanyahu .. Harry Kane Tottenham Messi Barca
15 .. Hoàng Công Lương Hòa Bình Thiên Sơn RO 2.4. Kết luận chương Khả năng suy ra thông tin/tri thức không xác định bằng suy diễn tương tự là một trong những khả năng tự nhiên của con người. Chương 2 trình bày mô hình tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn (IRS) nhằm mô phỏng khả năng trên. Mô hình IRS tìm kiếm thông tin/tri thức từ một miền không quen thuộc và không cần biết trước từ khóa, bằng cách sử dụng ví dụ tương tự (quan hệ tương đồng) từ một miền quen thuộc. Đóng góp chính của Chương 2: 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. Đồng thời, luận án đề xuất độ đo tương đồng kết hợp - theo terms và theo giả thuyết phân phối; Từ độ đo đề xuất, đồng thời áp dụng heuristic vào giải thuật gom cụm để cải thiện chất lượng cụm. CHƯƠNG 3: GỢI Ý TRUY VẤN HƯỚNG NGỮ CẢNH 3.1. Bài toán Trong lĩnh vực gợi ý truy vấn (query suggestion), các tiếp cận truyền thống như session-based, document- click based, .v.v. thực hiện khai phá tập truy vấn trong quá khứ (Query Logs) để kết xuất gợi ý. Cách tiếp cận “Gợi ý truy vấn hướng ngữ cảnh bởi khai phá dữ liệu phiên và các tài liệu chọn đọc” (gọi ngắn gọn: “cách tiếp cận hướng ngữ cảnh” của Huanhuan Cao cùng cộng sự [9], [10]) là một hướng đi mới - hướng này xét các truy vấn đứng ngay trước truy vấn vừa đưa vào (truy vấn hiện hành) như một ngữ cảnh tìm kiếm, nhằm “nắm bắt” ý định tìm kiếm của người dùng, nhằm đưa ra các gợi ý xác đáng hơn. Rõ ràng, lớp truy vấn đứng ngay trước có mối liên hệ ngữ nghĩa với truy vấn hiện hành. Kế tiếp, thực hiện khai phá các truy vấn đứng ngay sau truy vấn hiện hành - như một danh sách gợi ý. Phương pháp này tận dụng được “tri thức” của cộng đồng, vì lớp truy vấn đứng ngay sau truy vấn hiện hành phản ánh những vấn đề mà người dùng thường hỏi sau truy vấn hiện hành. Đóng góp chính của chương 3 gồm: 1) Ứ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). 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 ý. Ngoài ra, chương 3 cũng có các đóng góp bổ sung trong thực nghiệm: i) Tích hợp nhận dạng và tổng hợp tiếng nói tiếng Việt như một tùy chọn vào máy tìm kiếm để tạo thành một hệ tìm kiếm có tương tác tiếng nói. ii) Áp dụng cấu trúc dàn khái niệm để phân lớp tập kết quả trả về. 3.2. Phương pháp hướng ngữ cảnh 3.2.1. Định nghĩa – Thuật ngữ  Phiên tìm kiếm: Là chuỗi liên tục các câu truy vấn. Chuỗi truy vấn được biểu diễn với thứ tự thời gian. Mỗi phiên tương ứng với một người dùng.  Cấu trúc phiên tổng quát: {sessionID; queryText; queryTime; URL_clicked}  Ngữ cảnh: đặc tả chuỗi lân cận trước truy vấn hiện hành. Trong phiên tìm kiếm của một người dùng, ngữ cảnh là chuỗi truy vấn đứng ngay trước truy vấn vừa nhập. Lớp queries trước của qcurrent ↔ ngữ cảnh) .. qcurrent .. (Lớp queries sau)
16 3.2.2. Kiến trúc – Mô hình Phương pháp hướng ngữ cảnh dựa trên 2 phases: online và offline, khái quát: Trong 1 phiên tìm kiếm (online phase), tiếp cận gợi ý truy vấn hướng ngữ cảnh đón câu truy vấn hiện hành và xét chuỗi truy vấn đứng ngay trước truy vấn hiện hành như một ngữ cảnh. Chính xác hơn, diễn dịch chuỗi truy vấn đứng trước current query thành chuỗi khái niệm - chuỗi khái niệm này biểu đạt ý định tìm kiếm của người sử Hình 3.4: Mô hình Gợi ý truy vấn hướng ngữ cảnh. dụng. Khi có được ngữ cảnh tìm kiếm, hệ thống thực hiện so khớp với tập ngữ cảnh dựng sẵn (phase offline, tập ngữ cảnh dựng sẵn được xử lý tính toán sẵn trên tập truy vấn trong quá khứ - Query Logs. Về cấu trúc dữ liệu và lưu trữ, tập ngữ cảnh dựng sẵn được lưu trên cấu trúc dữ liệu cây hậu tố). Tiến trình so khớp (maximum matching) kết xuất danh sách ứng viên, danh sách này gồm các vấn đề mà đa số người dùng thường hỏi sau truy vấn vừa nhập. Sau bước ranking, danh sách ứng viên trở thành danh sách gợi ý. 3.2.4. Phase Offline - Giải thuật Gom cụm Ý tưởng của giải thuật gom cụm: Giải thuật quét toàn bộ các queries trong Query Logs một lần, các cụm sẽ được tạo ra trong tiến trình quét. Ban đầu, mỗi cụm được khởi tạo bằng một truy vấn, rồi mở rộng dần bởi các truy vấn tương tự. Quá trình mở rộng dừng khi đường kính cụm vượt ngưỡng Dmax. Do mỗi cụm (cluster) được xem như một khái niệm (concept), nên tập cụm là tập khái niệm. Đầu vào: Tập Query Logs Q, ngưỡng Dmax; Đầu ra: Tập cụm Cset; program Context_Aware_Clustering_alg // Khởi tạo mảng dim_array[d] = Ø, ∀d (d: document được click) // Mảng dim_array chứa số chiều các vectors. 01. for each query qi ∈ Q do 02. θ = Ø; 03. for each nonZeroDimension d of ⃗⃗⃗𝑞𝑖 do 04. θ ∪= dim_array[d]; C = arg minC’∈C-Setdistance(qi, C’); 05. if (diameter(C∪{qi}) ≤ Dmax) 06. C ∪= qi; cập nhật lại đường kính và tâm cụm C; 07. else C = new cluster({qi}); Cset ∪= C; 08. for each nonZeroDimension d of ⃗⃗⃗𝑞𝑖 do 09. if (C ∉ dim_array[d]) dim_array[d] ∪= C; end for 10. return Cset; 3.3.6. Phân tích ưu nhược điểm
17 Ưu điểm: - Với bài toán gợi ý truy vấn - đây là cách tiếp cận mới. Thực hiện gợi ý truy vấn, các tiếp cận kinh điển cũ thường lấy các truy vấn đã có trong Query Logs để đề xuất. Các đề xuất này chỉ tương tự hoặc có liên quan với truy vấn hiện hành, chứ không đưa ra được xu hướng mà tri thức số đông thường hỏi sau câu truy vấn hiện hành. Cũng như vậy, chưa có một tiếp cận nào đặt chuỗi truy vấn ngay trước truy vấn hiện hành vào một ngữ cảnh tìm kiếm - như một thể hiện liền mạch ý đồ tìm kiếm của người sử dụng. Kỹ thuật hướng ngữ cảnh, trên hết là ý tưởng gợi ý bằng những vấn đề mà người dùng thường hỏi sau truy vấn hiện hành, là một điểm độc đáo, hiệu quả, là “nét thông minh” trong lĩnh vực gợi ý truy vấn. Nhược điểm: - Khi người dùng đưa vào truy vấn đầu tiên hay một vài truy vấn là mới (mới so với các truy vấn trong quá khứ) hoặc thậm chí không mới - theo nghĩa không có mặt trong chuỗi khái niệm thường xuyên (chẳng hạn, trong tập dữ liệu mẫu, với 2 chuỗi khái niệm c2c3 và c1c2c3, giải thuật xác định chuỗi thường xuyên thu được là c2c3, trong trường hợp này - người sử dụng đưa vào c1). Tiếp cận hướng ngữ cảnh không đưa ra được gợi ý dù c1 đã có trong quá khứ (đã tồn tại trong QLogs). - Mỗi cụm (khái niệm) gồm một nhóm các truy vấn tương đồng. Độ đo tương đồng chỉ dựa trên URL click mà không dựa trên tương đồng về term, điều này có thể ảnh hưởng không nhỏ đến chất lượng của kỹ thuật gom cụm. - Ràng buộc mỗi truy vấn chỉ thuộc một cụm (khái niệm): quan điểm này không hợp lý và không tự nhiên đối với câu truy vấn đa nghĩa như “tiger” hoặc “gladitor”, hay rất nhiều từ đa nghĩa khác trong tiếng Việt, .v.v. - Chỉ xét đến gợi ý truy vấn (query suggestion) mà không xét đến gợi ý tài liệu (gợi ý URL - URL recommendation). Đồng thời, định hướng “click-through” nhưng không sử dụng các thông tin clicked Urls trong ngữ cảnh tìm kiếm (khi tìm kiếm trên cây hậu tố, Concept sequence đầu vào chỉ gồm các queries). - Trên đồ thị 2 phía, phía tập đỉnh Q các vector khá thưa (số chiều thấp), phía tập đỉnh URLs click cũng gặp phải vấn đề dữ liệu thưa (URL click thưa), khi các vectors thưa, chất lượng gom cụm sẽ bị ảnh hưởng. - Trong thuật giải gom cụm, khi Query Logs lớn, hoặc số chiều của mỗi vector lớn, mảng dim_array[d] sẽ có kích thước rất lớn, đòi hỏi cấp phát một lượng bộ nhớ lớn khi thực thi. Thực tế, trong một phiên tìm kiếm bất kỳ, người sử dụng nhập vào một hoặc khá nhiều truy vấn, cũng như vậy, người sử dụng có thể không hoặc click rất nhiều URL kết quả, trong đó mặc nhiên có những URL click không như ý, được xem như nhiễu (noise). Phương pháp hướng ngữ cảnh cần có chuỗi truy vấn liên tiếp mới hình thành ngữ cảnh không phản ảnh thực tế, khi người dùng chỉ nhập vào 1 truy vấn. Tuy nhiên, việc phụ thuộc vào URL click và không xét đến tính tương đồng term là nhược điểm rõ nhất của phương pháp này. 3.3.7. Các đề xuất kỹ thuật Khai phá Query Logs, bước gom cụm trong ứng dụng của luận án không đơn thuần dựa vào click-through mà tập trung vào ba thành phần cố định và chắc chắn, gồm: Câu truy vấn; Top N kết quả trả về; Tập URLs click. Đây là ba thành phần quan trọng nhất của tác vụ khai phá dữ liệu, với các tiền đề:  Nếu giao các từ khóa (terms) trong 2 truy vấn đạt tỷ lệ nhất định thì 2 truy vấn đó tương đồng.
18  Nếu giao trong top N kết quả của 2 truy vấn đạt tỷ lệ nhất định thì 2 truy vấn đó tương đồng.  Nếu giao tập các URLs click của 2 truy vấn vượt ngưỡng tương đồng thì 2 truy vấn tương đồng. Xét đồng thời tổ hợp các tiền đề nêu trên, kết hợp với các ngưỡng rút ra từ thực nghiệm, đảm bảo độ đo tương đồng chính xác, luận án liệt kê các công thức sau:  Độ tương đồng (Similarity) theo từ khóa của 2 truy vấn p, q: ∑n i=1 w(ki (p))+w(ki (q)) Simkeywords (p, q) = ⁡ 2×MAX(kn(p),kn(q)) (3.9) trong công thức trên: - kn(.): tổng trọng số các terms trong p, trong q; - w(ki(.)): trọng số term chung thứ i của p và q;  Độ tương đồng theo top50 URL kết quả của 2 truy vấn p, q: ∧(topUp,top⁡Uq) Simtop50URL (p, q) = ⁡ (3.10) 2×MAX(kn(p),kn(q)) ký hiệu:  (topUp, topUq): phần giao trong top50URL kết quả của p và q;  Độ tương đồng theo clickedUrls của 2 truy vấn p, q: ∧(U_click_p,U_click_q) SimURLsClicked (p, q) = ⁡ 2×MAX(kn(p),kn(q)) (3.11) ký hiệu:  (U_Clickp, U_Clickq): số URLs click chung của p và q; U_Clickp: số URL clicked trong 1 query;  Từ (3.9), (3.10), (3.11), đề xuất đẳng thức tính độ tương đồng tổ hợp: Sim(p, q) = α. Sim(p, q) + β. Sim(p, q) + γ. Sim(p, q)⁡ (3.12) 𝑐𝑜𝑚𝑏𝑖𝑛𝑎𝑡𝑖𝑜𝑛 keywords 𝑡𝑜𝑝50𝑈𝑅𝐿 URLsclicked Với α + β + γ = 1; α, β, γ là các tham số ngưỡng rút ra trong quá trình thực nghiệm. Trong ứng dụng máy tìm kiếm, α = 0,4; β = 0,4; γ = 0,2. 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 (Concept Lattice) Cấu trúc dàn có khả năng tự động phân nhóm tập kết quả trả về từ máy tìm kiếm. Việc phân nhóm tập kết quả vào các chủ đề giúp người sử dụng dễ dàng quan sát, đưa ra quyết định tài liệu nào thích hợp, hạn chế việc thông tin phù hợp bị vùi lấp bởi một danh sách quá dài. Phân tích khái niệm hình thức (Formal Concept Analysis - FCA) là một trong những kỹ thuật chính áp dụng trên dàn. FCA được ứng dụng để lập bảng với dòng mô tả đối tượng, cột mô tả thuộc tính, từ đó dựng lên dàn [88]. Trong tìm kiếm thông tin, FCA xét tương quan đối tượng - thuộc tính như tương quan tài liệu - thuật ngữ. Tiến trình dựng dàn, FCA quy ước mỗi nút trong dàn là một khái niệm. Thuật toán dựng dàn cài đặt vào mỗi khái niệm một cặp đôi: tập tài liệu có chung các thuật ngữ; tập thuật ngữ cùng xuất hiện trong các tài liệu. Mở rộng, có thể xem mỗi khái niệm (mỗi nút trong dàn) như một cặp câu hỏi, câu trả lời. Phép duyệt dàn bottom-up sẽ duyệt lên hoặc duyệt xuống trên dàn để đi đến khái niệm tổng quát hoặc khái niệm chi tiết. Tương ứng với khái niệm tổng quát sẽ là số lượng tài liệu kết quả nhiều hơn, và ngược lại. Với bộ dữ liệu thử (chuyên ngành hàng không), luận án sử dụng dàn để phân lớp tập kết quả trả về theo chủ đề định sẵn. a) Bài toán minh họa