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

ính toán: Giải thuật gồm 2 vòng lặp for lồng nhau, trong thân vòng lặp có câu lệnh so sánh. Vì vậy, đánh giá cận trên độ phức tạp tính toán của giải thuật là O(n2), với n là số lần đồng hiện của wi và pj trong cùng một câu context f(wi, pj), như công thức (2.21) đã nêu. Tuy nhiên, như đã phân tích trong giải thuật Filter-Entities lượng context đồng hiện với cặp (A, B) đã biết bị giới hạn bởi hằng số, như vậy, n là hằng số và rất nhỏ so với kích thước toàn bộ data-set. Nói cách khác, thời gian tính của giải thuật Rank- Entities là hằng số, tăng chậm khi kích thước dữ liệu mẫu (corpus) tăng. Giải thuật Rank-Entities đảm bảo được tốc độ tính toán RelSim, phân hạng kết quả Di là danh sách câu trả lời tức thờ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á Mục đích kiểm thử, đánh giá để tìm ra giá trị phù hợp của các tham số như: Ngưỡng θ1 trong giải thuật Phân cụm, ngưỡng α trong giải thuật Rank_Entities. Từ tập dữ liệu mẫu trong thực nghiệm, luận án xây dựng dataset, tập mẫu này gồm các thực thể và kiểu quan hệ ngữ nghĩa trong cặp thực thể. Áp dụng các độ đo Precision, Recall, F-Score trên train-set và test-set để điều chỉnh tham số, nhằm tìm ra giá trị tối ưu cho θ1 và α. Để so sánh, đánh giá giữa tần suất (số lần đồng hiện) và độ tương hỗ PMI trong 44 tính toán độ tương đồng ngữ nghĩa của 2 context, luận án sử dụng độ đo MRR (Mean Reciprocal Rank), độ đo MRR được biết là độ đo phản ánh cả đặc tính recall và precision, thường dùng cho các kỹ thuật tìm kiếm có độ chính xác cao [68]. 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; Các phân lớp này thường được sử dụng để đánh giá trong các hệ thống trích xuất quan hệ [69], [70], các thuật giải đo lường độ tương đồng quan hệ [71], [72], các hệ tìm kiếm quan hệ ẩn [19]. Mỗi phân lớp gồm 50 truy vấn, theo [73], [74] một bộ 50 truy vấn được coi là đủ lớn để đánh giá một hệ thống truy xuất thông tin. Các truy vấn được rút trích ngẫu nhiên, có dạng q={(Trung Quốc:Đôn Hoàng),(Nara:?)}. Các truy vấn có thể duy nhất 1 câu trả lời chính xác, ví dụ q={(Vietnam:2/9):(Hong Kong:?)}, cũng có thể có nhiều câu trả lời chính xác, ví dụ với context=“văn hào”, thực thể có tên “Hemingway” có thể ghép cặp với nhiều thực thể khác như: “Chuông nguyện hồn ai”, “Ông già và biển cả”, “Giã từ vũ khí”, .v.v. Các phân lớp này và các cặp thực thể gắn context tương ứng với mỗi phân lớp được minh họa trong Bảng 2.2: Bảng 2.2: Các phân lớp NER (Location, Organization, Personal, Time) Stt Phân lớp NER Context Entity-pair Example 1 LOC bích họa Phật giáo Đôn Hoàng:Trung Quốc Bích họa Phật giáo Đôn Hoàng ở Trung Quốc. Nara:Nhật Bản Bích họa Phật giáo Nara tại Nhật Bản. 2 ORG đặt trụ sở tại WHO:Geneva WHO đặt trụ sở tại Geneva. Unesco:Paris Unesco đặt trụ sở tại Paris. 3 PER tác phẩm kinh điển Don Quixote : Cervantes Don Quixote là tác phẩm kinh điển của Cervantes. Oliver Twist : Oliver Twist là tác phẩm kinh điển của Charles Dickens. 45 Charles Dickens 4 TIME Ngày Quốc khánh Hong Kong:1/7 Ngày Quốc khánh Hong Kong là 1/7. Macedonia:8/9 Ngày Quốc khánh Macedonia là 8/9. 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 đó đo độ Precision, Recall, F-Score tương ứng với mỗi giá trị thay đổi của θ1. Precision(Q) = Số truy vấn có ít nhất 1 câu trả lời đúng Tổng số truy vấn (2.30) Recall(Q) = Số truy vấn có ít nhất 1 câu trả lời đúng Tổng số truy vấn có ít nhất một câu trả lời (2.31) F-Score(Q) = 2⨉ Precision(Q)⨉Recall(Q) Precision(Q)+Recall(Q) (2.32) Kết quả thực nghiệm tại 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) cho thấy, khi α quá 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 46 lại khi α lớn thì giá trị Recall rất 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 bộ truy vấn Q được tính: MRR(Q) = 1 |𝑄| ∑ 1 𝑟𝑞 𝑞∈𝑄 (2.33) Trong thực nghiệm, với mục đích so sánh, giải thuật Rank_Entities (dòng lệnh 03, 16) tính tích vô hướng của f(s,p)·f(c,p) và tích vô hướng của PMI(s,p)·PMI(c,p). 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(f) ≈ 0.69; trong khi đó, phương pháp dựa trên PMI đạt MRR(PMI) ≈ 0,86. Điều này cho thấy PMI giúp cải thiện độ chính xác tốt hơn tần suất đồng hiện. . 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 gồm các mẫu chứa 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. Việc phân lớp các thực thể có tên NER (Named Entity Recognition), thực nghiệm chọn phân lớp ở mức tổng quát, với 9 nhãn: B-LOC; B-MISC; B-ORG; B- 47 PER; I-LOC; I-MISC; I-ORG; I-PER và O, trong đó tiếp đầu ngữ B- Begin và I- Inner tương ứng vị trí bắt đầu và bên trong tên thực thể. Các nhãn tổng quát của NER: 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. Theo hiện biết, với tiếng Việt, chưa có một mô hình tìm kiếm thực thể dựa trên quan hệ ngữ nghĩa ẩn. Do đó, luận án chưa có điều kiện để so sánh, kiểm thử với các phương pháp khác. Hình 2.5: Thực nghiệm IRS với nhãn thực thể B-PER. Hình 2.6: Thực nghiệm IRS với thực thể kiểu thời gian. Để đá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%. 48 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 .. Chí Anh Khánh Thi Khắc Việt Tuấn Hưng .. .. Hà Nội Kim Quy Hoàn Kiếm Gươm Thần Kim Quy (Magical sword – Golden Turtle) .. Hoàng Công Lương Hòa Bình Thiên Sơn RO Một vài ngoại lệ cần giải quyết trong phạm vi nghiên cứu, khi người dùng đưa vào câu truy vấn ngẫu nhiên, tùy ý, không theo motive q = {(A, B), (C, ?)}. Trong câu truy vấn, mối quan hệ ngữ nghĩa của cặp thực thể đầu vào (A, B) bằng 0, nói cách khác trong corpus không tồn tại quan hệ ngữ nghĩa (A, B) hoặc thậm chí không tồn tại cặp thực thể (A, B), mô hình IRS sẽ biến đổi thành cơ chế tìm kiếm theo từ khóa và áp dụng hướng ngữ cảnh. Trong trường hợp, 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. Với ràng buộc là thực thể C đã biết, giải thuật Rank-Entities tìm kiếm các cụm ứng viên, trả về kết quả là danh sách các thực thể {Di} được tối đa hóa tương đồng với ngữ nghĩa của cặp quan hệ (A, B). Nói cách khác, về bản chất, IRS dựa vào tương đồng ngữ nghĩa cặp thực thể (A, B) + thực thể ràng buộc C. Nếu ngữ nghĩa trong truy vấn (A, B) là đa nghĩa  (A, B) thuộc nhiều cụm (ngữ nghĩa) khác nhau  kết quả trả về có tính đa dạng, phủ các khía cạnh ngữ nghĩa khác nhau (với điều kiện thỏa ràng buộc C). 49 Ngoài ra, để tường minh về mặt ngữ nghĩa trong danh sách kết quả này, câu context gắn kèm Di được kết xuất dưới dạng snippet. 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. Bên cạnh khả năng tìm kiếm thông tin/tri thức bằng cách sử dụng quan hệ tương đồng, mô hình IRS còn có khả năng ánh xạ cơ sở tri thức từ miền ngữ nghĩa quen thuộc vào một miền ngữ nghĩa không quen thuộc để khai phá và thu thập tri thức. Hướng phát triển của đề tài, một mặt - xét thêm các loại ánh xạ quan hệ, thêm yếu tố thời gian để kết quả tìm kiếm được cập nhật và chính xác. Mặt khác, có thể mở rộng tìm kiếm thực thể với truy vấn đầu vào chỉ gồm một thực thể, ví dụ: “Sông nào dài nhất Trung Quốc?”, mô hình tìm kiếm thực thể dựa trên ngữ nghĩa ẩn sẽ đưa ra được câu trả lời chính xác: “Trường Giang”, dù Corpus chỉ có câu gốc “Trường Giang là sông lớn nhất Trung Quốc”. 50 CHƯƠNG 3: GỢI Ý TRUY VẤN HƯỚNG NGỮ CẢNH Khắc phục các vấn đề còn tồn tại trong các nghiên cứu liên quan về gợi ý truy vấn, chương này trình bày hướng nghiên cứu về phương pháp hướng ngữ cảnh trong gợi ý truy vấn. Phân tích các ưu nhược điểm của phương pháp hướng ngữ cảnh, đưa ra các đề xuất kỹ thuật khắc phục nhược điểm, đề xuất phương pháp cải tiến và công thức tổ hợp mới. Thực nghiệm trên một máy tìm kiếm tiếng Việt chuyên ngành hàng không. Cải thiện tiến trình hậu xử lý (nghiên cứu, hiện thực cấu trúc Dàn khái niệm để phân lớp kết quả tìm kiếm.). Thực hiện tích hợp tổng hợp, nhận dạng tiếng nói như một tùy chọn trong máy tìm kiếm hướng ngữ cảnh. So sánh đánh giá, kết quả thực nghiệm, hướng phát triển được trình bày ở cuối chương. 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 truyền thống thường áp dụng các kỹ thuật như gom cụm, đo độ tương đồng, .v.v. của truy vấn [9], [10]. Tuy nhiên, các tiếp cận 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 liên tiếp từ người sử dụng như một ngữ cảnh tìm kiếm, trong khi việc nắm bắt ngữ cảnh tìm kiếm phản ánh việc nắm bắt ý đồ tìm kiếm của người sử dụng. 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, để “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 ý. Có thể nó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ự với truy vấn hiện hành. Lớp truy 51 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 câu truy vấn hiện 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 tốt hơn, phản ánh rõ hơn ý đồ tìm kiếm. Rõ ràng, nắm bắt được ngữ cảnh tìm kiếm, sẽ hiểu được ý định tìm kiếm, cô gọn được tập kết quả trả về, hiển thị những kết quả thích đáng với mối quan tâm tìm kiếm của người sử dụng. Tuy nhiên, cách tiếp cận hướng ngữ cảnh cũng có một vài nhược điểm: khi người sử dụng đưa vào một hoặc một chuỗi truy vấn mà không thuộc bất cứ một ngữ cảnh tìm kiếm nào đã có trong quá khứ, phương pháp này không đưa ra được gợi ý. Kỹ thuật gom cụm trong tiếp cận hướng ngữ cảnh chỉ đơn thuần dựa trên các URLs click (các tài liệu người dùng chọn đọc) mà không xét đến tính tương đồng của từ, cụm từ (terms) trong các câu truy vấn mà người dùng đưa vào. Đây là vấn đề ảnh hưởng đến chất lượng khi gom cụm, chất lượng cụm không tốt sẽ ảnh hưởng đến chất lượng câu gợi ý không tốt, đặc biệt với những ngôn ngữ bản địa như tiếng Việt. Một vấn đề khác: Khi kích thước dữ liệu tăng cao, việc tổ chức, lưu trữ trên cây hậu tố sao cho đáp ứng tức thời việc gợi ý truy vấn. Mỗi câu truy vấn đa nghĩa chỉ thuộc duy nhất một cụm cũng không thực sự chính xác. Do đó, Chương 3 đặt mục đích nghiên cứu và ứng dụng phương pháp hướng ngữ cảnh, xác định các ưu nhược điểm, nêu các đề xuất cải thiện kỹ thuật, cũng như bước đầu đưa ra các phân tích, chứng minh bằng thực nghiệm. Đặ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. Bên cạnh phương pháp hướng ngữ cảnh, Chương 3 nghiên cứu các phương pháp thống kê ứng dụng trong nhận dạng và tổng hợp tiếng nói để tương tác với người sử dụng qua ngôn ngữ tự nhiên, qua tiếng nói. Như một tùy chọn cho máy tìm kiếm, luận án trình bày quá trình tích hợp kỹ thuật nhận dạng và tổng hợp tiếng nói tiếng Việt vào máy tìm kiếm [75], [76], tạo thành một máy tìm kiếm có tương tác giọng nói. Với mục đích tương tác hai chiều với người dùng, chức năng nhận dạng (Speech To Text) cung cấp khả năng truy vấn bằng tiếng nói, chức năng tổng hợp (Text To Speech) trả lời bằng giọng nói với độ chính xác cao. Đóng góp chính của chương 3 bao 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 52 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ề. Bố cục chương 3 gồm: Phần 3.1 đặt vấn đề. Phần 3.2 trình bày phương pháp gợi ý truy vấn hướng ngữ cảnh. Nêu các ưu nhược điểm của phương pháp hướng ngữ cảnh, các đề xuất kỹ thuật khắc phục nhược điểm, thực nghiệm trên một máy tìm kiếm tiếng Việt, đề xuất tiến trình hậu xử lý (phân nhóm kết quả sau tìm kiếm), giới thiệu phương pháp cải thiện và công thức tổ hợp mới. Thực hiện tích hợp tổng hợp, nhận dạng tiếng nói như một tùy chọn trong máy tìm kiếm hướng ngữ cảnh. Nghiên cứu, hiện thực cấu trúc Dàn khái niệm để phân lớp kết quả tìm kiếm. Phần 3.3 thực nghiệm, đánh giá trên một máy tìm kiếm tiếng Việt phụ thuộc lĩnh vực (hàng không). Kết luận và hướng đi kế tiếp trình bày trong phần 3.4. 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} trong đó: - Session ID: Định danh của phiên tìm kiếm (mã tự sinh từ Web-server); - queryTime: Nhãn thời gian (thời gian khi truy vấn được gửi đi); - queryText: câu truy vấn; - URL_clicked: ID của các URL được nhấn từ người sử dụng; Ngoài ra, phiên có thể có thêm các thuộc tính khác như: Result-List (tập kết quả mà SE đáp ứng q), Location, Regions, Search device, User_ID, .v.v. 53 Bảng 3.2: Cấu trúc (dạng rút gọn) của phiên tìm kiếm sessionID queryText queryTime URL_clicked User 1 khủng bố 2011-05-15 10:47 1491| User 2 Vietnam Airlines 2011-05-15 10:48 2096|19730 User 1 Bin Laden bị tiêu diệt 2011-05-15 10:50 58896|337  Ý đồ tìm kiếm: Là chuỗi con của phiên. Các truy vấn trong một ý đồ sẽ liên tiếp về thời gian, liên quan về ý nghĩa, được phát ra từ cùng một người dùng. Xét trong tầm vực Gợi ý truy vấn hướng ngữ cảnh, ý đồ tìm kiếm được phản ánh bởi một hoặc một nhóm các truy vấn đại diện.  Ngữ cảnh (context): Thuật ngữ 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) Hình 3.1: Ngữ cảnh truy vấn.  Khái niệm (concept): Khi gom cụm, mỗi cụm là một nhóm các truy vấn tương tự nhau. Trong tiếp cận gợi ý truy vấn hướng ngữ cảnh, mỗi cụm được thuật ngữ hóa bởi khái niệm.  Timeout: Ngưỡng thời gian phân biệt giữa hai phiên tìm kiếm. Ngưỡng là một tham số được sử dụng trong tiến trình khai phá Query Logs, được đặc tả trong mã nguồn, thời gian mặc định bằng 30 phút. 3.2.2. Đề dẫn - Ví dụ minh họa  Ví dụ 1: Xét truy vấn đầu vào: “gladiator”, rất khó để đưa ra gợi ý với câu truy vấn này (Lịch sử đấu sĩ? Một đấu sĩ nổi tiếng? Tiêu đề một bộ phim?). Nếu tìm được truy vấn ngay trước đó: “beautiful mind”, thì gần như chắc chắn người sử dụng đang tìm kiếm một bộ phim, dẫn đến việc gợi ý truy vấn hiệu quả hơn. 54 Hình 3.2: Ví dụ minh họa với truy vấn “gladiator”.  Ví dụ 2: Với truy vấn: “tiger”, ý đồ tìm kiếm trong trường hợp này sẽ là: Một loài động vật? Một hãng hàng không? Một vận động viên? Một hệ điều hành? Việc không xác định được ngữ cảnh tìm kiếm sẽ gây khó khăn khi đưa ra gợi ý xác đáng. Nếu biết truy vấn ngay trước đó là “Woods” hoặc “golf”, thì gần như chắc chắn người sử dụng đang tìm kiếm thông tin về một vận động viên. Tương tự với truy vấn “Jordan”, nếu biết lớp truy vấn ngay trước là “NBA” hoặc “basketball”, một cách tự nhiên, ta biết ý định tìm kiếm của người sử dụng về “Michel Jordan”. Do đó dưới góc nhìn của hệ thống, ý đồ tìm kiếm đã hiển thị rõ ràng hơn. Hình 3.3: Ví dụ minh họa với truy vấn “tiger”. Trên đây là hai ví dụ dẫn để minh họa cho tiếp cận hướng ngữ cảnh, trong thực tế có rất nhiều ví dụ tương tự. Phần tiếp theo, luận án trình bày motivation, mô hình và chi tiết của tiếp cận hướng ngữ cảnh. 55 3.2.3. Kiến trúc – Mô hình Phương pháp hướng ngữ cảnh dựa trên hai phases: online và offline, khái quát: Hình 3.4: Mô hình của tiếp cận gợi ý truy vấn hướng ngữ cảnh. Trong một 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. 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 Pha offline có mục đích xây dựng cây hậu tố từ tập dữ liệu mẫu (Query Logs, ký hiệu Q). Pha offline thực hiện tuần tự các bước: Xây dựng đồ thị 2 phía (bipartite graph); Gom cụm trên đồ thị 2 phía; Xây dựng tập chuỗi khái niệm, rút trích tập chuỗi 56 khái niệm thành tập chuỗi khái niệm thường xuyên (ngắn gọn: chuỗi thường xuyên); Dựng cây hậu tố. Trong đó gom cụm và dựng cây hậu tố là hai thành phần quan trọng nhất của pha offline. a) Đồ thị 2 phía – Gom cụm trên đồ thị 2 phía Theo lý thuyết đồ thị, một đồ thị vô hướng G:=(V, E) được gọi là 2 phía nếu tồn tại một phân hoạch của tập đỉnh V=V1∪V2 sao cho V1 và V2 là các tập độc lập (không giao nhau, thỏa điều kiện không có cạnh nối giữa 2 đỉnh bất kỳ thuộc cùng một tập). Nếu |V1|=|V2| thì G là đồ thị 2 phía cân bằng. Một đồ thị 2 phía đầy đủ (biclique) là một đồ thị 2 phía đặc biệt, trong đó mỗi đỉnh của tập thứ nhất nối với mọi đỉnh của tập thứ hai. Như đã biết, khi người dùng đưa ra câu truy vấn, máy tìm kiếm sẽ đáp ứng bằng một tập các URLs kết quả. Trong đó URLs click là những urls mà người dùng click chọn đọc trên tập kết quả trả về, URLs click phản ánh mối quan tâm của người dùng trên một tài liệu cụ thể. Tham chiếu với lý thuyết, đồ thị 2 phía trong tiếp cận hướng ngữ cảnh được xây dựng với Q và U là 2 tập đỉnh, E là tập cạnh. Cụ thể, mỗi node truy vấn trong tập đỉnh Q tương ứng với một query, mỗi node URL trong tập đỉnh U tương ứng một url được click. Cạnh eij nối qi với uj nếu uj được click bởi qi. Trọng số trên cạnh eij (ký hiệu wij) là tổng số lần uj được click bởi qi, trọng số này được tính trên toàn Query Logs. Xuất phát từ ý tưởng căn bản: Trong Query Logs Q, nếu 2 truy vấn chia sẻ chung các URLs click (thuộc tập U) thì 2 truy vấn đó được xét là tương đồng [63], [64]. Một cách hình thức, 2 truy vấn – đặc biệt là 2 truy vấn tương đồng về ngữ nghĩa có thể không có term(s) chung, nhưng chúng chia sẻ chung các thuật ngữ trong các tài liệu (URLs click) mà người tìm kiếm chọn đọc. Hình 3.5: Đồ thị 2 phía (tập đỉnh Q – tập đỉnh U) 57  Trên đồ thị 2 phía, mỗi query q có thể nối với một hoặc nhiều urlClicks, ngược lại, mỗi urlClick có thể nối với một hoặc một vài queries. Khi tiến hành gom cụm, mỗi query qi (qi ∈ Q) được xét như một vector, mỗi chiều của vector qi tương ứng với một url uj trên tập U (uj ∈ U, U là tập các urlClicks). Theo [77], chiều thứ j của qi được tính bởi công thức: 𝑞𝑖⃗⃗⃗ ⃗[j] = norm(wij) = wij √∑ wij′ 2 uj′∈U 2 (3.1) trong đó: - wij: tổng số lần uj được click bởi qi; - uj’: các urls khác uj, được click bởi qi. (các chiều còn lại của vector qi)  Khoảng cách giữa 2 truy vấn qi và qj được đo bằng khoảng cách Euclide (theo urlClicks) giữa 2 vector qi, qj: distance(qi, qj) = √∑ (𝑞𝑖⃗⃗⃗ ⃗[k] − 𝑞𝑗⃗⃗⃗⃗ [k])2𝑢𝑘∈𝑈 2 (3.2)  Mỗi cụm C gồm một tập các câu truy vấn, tâm cụm được vector hóa: C⃗⃗ = norm( ∑ qi⃗⃗⃗⃗⃗qi∈C |C| ) (3.3) với |C| là số queries chứa trong C.  Theo (3.2), ta có khoảng cách giữa truy vấn q và tâm cụm C: distance(q, C) = √∑ (�⃑�[k] − 𝐶[k])2𝑢𝑘∈𝑈 2 (3.4)  Đường kính (D, diameter) của một cụm được tính bởi công thức: D = √ ∑ ∑ (�⃗⃑�[i] − �⃑⃗�[j])2 |𝐶| 𝑗=1 |𝐶| 𝑖=1 |𝐶|(|𝐶|−1) 2 (3.5) Giải thuật gom cụm sử dụng tham số Dmax như một ngưỡng để kiểm soát, sao cho với mỗi cụm có đường kính D, D luôn nhỏ hơn hoặc bằng Dmax. b) 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) 58 đượ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; Giải thuật: program Context_Aware_Clustering_alg // Khởi tạo mảng dim_array[d] = Ø, ∀d (d: click-document). // Mảng dim_array chứa số chiều các vectors. // Giải thuật Context_Aware_Clustering_alg thực hiện thêm dần // các query trong QLogs vào tập cụm Cset; 01. for each query qi ∈ Q do 02. θ = Ø; 03. for each nonZeroDimension d of 𝑞𝑖⃗⃗⃗⃗ do { 04. θ ∪= dim_array[d]; } 05. C = arg-minC’∈θdistance(qi, C’); 06. if (diameter(C ∪ {qi}) ≤ Dmax) { 07. C ∪= qi; cập nhật lại đường kính và tâm cụm C; } 08. else { C = new cluster({qi}); Cset ∪= C; } 09. for each nonZeroDimension d of 𝑞𝑖⃗⃗⃗⃗ do { 10. if (C ∉ dim_array[d]) dim_array[d] ∪= C; } end for 11. return Cset; end. Diễn giải giải thuật: Với mỗi truy vấn qi