Tóm tắt Luận á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

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. Xét truy vấn q = {(Việt Nam, Mê Kông), (Trung Quốc, ?)}, IRS tìm được cụm chứa cặp thực thể (Việt Nam, Mê Kông) và 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 Nam”). Cụm này đồng thời chứa một quan hệ 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ể (Trung Quốc, Trường Giang) (từ câu gốc: “Trường Giang là sông lớn nhất Trung Quốc”). 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 độ tương đồng, trả kết quả về người tìm kiếm. 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. Cặp thực thể - Quan hệ ngữ nghĩa Corpus Chỉ mục đảo Inverted Index for IRS Rút trích quan hệ ngữ nghĩa Gom cụm quan hệ ngữ nghĩa Tính độ tương đồng quan hệ (RelSim) Tập kết quả ứng viên Tập kết quả trả về được phân hạng Q u er y : { (V iệ t N am , M ê K ô n g ), ( T ru n g Q u ố c, ? )} 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): Fe(q, D) = Fe({(A, B), (C, ?)}, D) = { 1, 𝑖𝑓⁡𝑅𝑒𝑙𝑒𝑣𝑎𝑛𝑡(𝑞, 𝐷) 0, 𝑒𝑙𝑠𝑒 (2.1)  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: SimZaro(a,b) = { 0,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑖𝑓⁡𝑚 = 0 1 3 ( 𝑚 |𝑎| + 𝑚 |𝑏| + 𝑚−𝑠𝑘𝑖𝑝 𝑚 ) ⁡⁡⁡⁡⁡⁡𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 (2.6) 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 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: Simterm(p, q) = ⁡ ∑ (weighti(p)∙weighti(q)) n i=1 ||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, 𝑖𝑓⁡𝑅𝑒𝑙𝑆𝑖𝑚((𝐴, 𝐵), (𝐶, 𝐷𝑖)) > α 0, 𝑒𝑙𝑠𝑒 (2.29) 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: MRR(Q) = 1 |𝑄| ∑ 1 𝑟𝑞 𝑞∈𝑄 (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ử dụng. Hình 3.4: Mô hình Gợi ý truy vấn hướng ngữ cảnh. 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ôn