›

Bài giảng Tìm kiếm và trình diễn thông tin - Bài 10: Mô hình nhị phân độc lập - Nguyễn Bá Ngọc

pdf 34 trang huongle 3820
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tìm kiếm và trình diễn thông tin - Bài 10: Mô hình nhị phân độc lập - Nguyễn Bá Ngọc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tim_kiem_va_trinh_dien_thong_tin_bai_10_mo_hinh_nh.pdf

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 10: Mô hình nhị phân độc lập - Nguyễn Bá Ngọc

  1. (IT4853) Tỡm kiếm và trỡnh diễn thụng tin Mụ hỡnh nhị phõn độc lập
  2. Giảng viờn  TS. Nguyễn Bỏ Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: 2
  3. Nội dung chớnh  Tỡm kiếm dựa trờn xỏc suất  Mụ hỡnh nhị phõn độc lập  Mụ hỡnh (Okapi) BM25 3
  4. Xỏc suất trong tỡm kiếm thụng tin Khụng bảo toàn Nhu cầu thụng tin Biểu diễn logic ngữ nghĩa người dựng truy vấn So sỏnh Kết luận phự hợp là khụng chắc chắn Văn bản Biểu diễn logic văn bản  So sỏnh văn bản và truy vấn dựa trờn ký tự.  Kết quả so sỏnh thể hiện khả năng phự hợp về ngữ nghĩa.  Hoàn toàn cú thể sử dụng xỏc suất để định lượng sự khụng chắc chắn trong tỡm kiếm. 4
  5. Tỡm kiếm dựa trờn xỏc suất  Nguyờn tắc xếp hạng xỏc suất  Mụ hỡnh nhị phõn độc lập BIM  Okapi BM25  Mụ hỡnh ngụn ngữ. 5
  6. Nguyờn tắc  Đỏnh giỏ trọng số từ:  “Với một truy vấn đó cho, nếu cú thể khẳng định một văn bản là phự hợp, thỡ từ xuất hiện trong văn bản đú phải cú trọng số lớn hơn những từ khỏc.”  Thứ tự sắp xếp văn bản là thứ tự giảm dần xỏc suất phự hợp:  P(R=1|văn bảni, truy vấn) 6
  7. Nội dung chớnh  Tỡm kiếm dựa trờn xỏc suất  Mụ hỡnh nhị phõn độc lập  Mụ hỡnh (Okapi) BM25 7
  8. Lý thuyết xỏc suất căn bản  Quy tắc nhõn xỏc suất (luật chuỗi): p(A, B) p(A  B) p(A, B) p(A | B) p(B) p(A, B) p(B | A) p(A)  Luật Bayes p(B | A) p(A) p(A | B) p(B) 8
  9. Lý thuyết xỏc suất căn bản  Quy tắc phõn tớch xỏc suất (luật phõn tớch): p(B) p(A, B) p(A, B)  Kết hợp luật Bayes và luật phõn tớch p(B | A) p(A| B) p(A) p(B | X ) p(X ) X A,A 9
  10. Lý thuyết xỏc suất căn bản  Cơ hội (Odds): p(A) p(A) O(A) p(A) 1 p(A) Liờn hệ giữa O và p 10
  11. Mụ hỡnh nhị phõn độc lập  Nhị phõn: Văn bản được biểu diễn như vec-tơ nhị phõn đỏnh dấu sự xuất hiện của từ d (x1,, xn )  xi = 1 nếu thuật ngữ thứ i xuất hiện trong d, 0 nếu ngược lại  Độc lập: Sự xuất hiện của mỗi từ trong văn bản là độc lập với những từ cũn lại  Những văn bản khỏc nhau cú thể cú cựng một biểu diễn vec-tơ 11
  12. Mụ hỡnh nhị phõn độc lập (1)  Cho truy vấn q  Với mỗi văn bản d cần tớnh p(R|q, d)  Chỉ quan tõm tới thứ hạng  Sử dụng cơ hội (Odds) và luật Bayes p(R 1| q) p(d | R 1,q) p(R 1| q,d) p(d | q) O(R | q,d) p(R 0 | q,d) p(R 0 | q) p(d | R 0,q) p(d | q) 12
  13. Mụ hỡnh nhị phõn độc lập (2) p(R 1| q,d) p(R 1| q) p(d | R 1,q) O(R | q,d)  p(R 0 | q,d) p(R 0 | q) p(d | R 0,q) Hằng số với một truy vấn Cần xỏc định  Sử dụng giả thuyết độc lập p(d | R 1,q) n p(x | R 1,q)  i p(d | R 0,q) i 1 p(xi | R 0,q) n p(x | R 1,q) O(R | q,d) O(R | q) i i 1 p(xi | R 0,q) 13
  14. Mụ hỡnh nhị phõn độc lập (3) n p(x | R 1,q) O(R | q,d) O(R | q) i i 1 p(xi | R 0,q) Vỡ x chỉ nhận giỏ trị 1 hoặc 0 i p(x 1| R 1,q) p(x 0 | R 1,q) O(R | q,d) O(R | q) i  i xi 1 p(xi 1| R 0,q) xi 0 p(xi 0 | R 0,q)  Đặt: pi p(xi 1| R 1,q); ri = p(xi =1| R= 0,q);  Giả sử với thuật ngữ khụng cú trong truy vấn thỡ pi = ri p (1 p ) O(R | q,d) O(R | q) i  i xi 1 ri xi 0 (1 ri ) qi 1 qi 1 14
  15. Cỏc đại lượng xỏc suất cơ bản pi p(xi 1| R 1,q) 1 pi p(xi 0 | R 1,q) ri p(xi 1| R 0,q) 1 ri p(xi 0 | R 0,q) 15
  16. Mụ hỡnh nhị phõn độc lập (4) p 1 p O(R | q,d) O(R | q)  i  i xi qi 1 ri xi 0 1 ri qi 1 Từ truy vấn cú Từ truy vấn khụng trong văn bản cú trong văn bản p 1 r 1 p 1 p O(R | q,d) O(R | q) i  i  i i  r  1 p 1 r  1 r xi 1 i xi 1 i i xi 0 i qi 1 qi 1 qi 1 p (1 r ) 1 p O(R | q,d) O(R | q)  i i  i xi qi 1 ri (1 pi ) qi 1 1 ri Từ truy vấn cú Tất cả từ truy vấn trong văn bản 16
  17. Mụ hỡnh nhị phõn độc lập (5) p (1 r ) 1 p O(R | q,d) O(R | q)  i i  i xi qi 1 ri (1 pi ) qi 1 1 ri Hằng số với một truy vấn Đại lượng duy nhất cần xỏc định cho mục đớch xếp hạng Hàm xếp hạng p (1 r ) p (1 r ) Rank(d,q) log  i i  log i i xi qi 1 ri (1 pi ) xi qi 1 ri (1 pi ) 17
  18. Mụ hỡnh nhị phõn độc lập (6)  Kết quả tỡm kiếm được xỏc định dựa trờn Rank p (1 r ) p (1 r ) Rank(d,q) log  i i  log i i xi qi 1 ri (1 pi ) xi qi 1 ri (1 pi ) pi (1 ri ) Rank(d,q) ci ; ci log xi qi 1 ri (1 pi ) ci cú vai trũ như trọng số thuật ngữ trong mụ hỡnh này Tớnh ci ntn từ bộ dữ liệu sẵn cú. 18
  19. Những số liệu thống kờ cơ bản Đại lượng thống kờ ứng với từ thứ i: Văn bản Phự hợp Khụng phự Tổng hợp xi=1 s n-s n xi=0 S-s N-n-S+s N-n Tổng S N-S N s n s • Xỏc định: p r i S i N S s (S s) w K(N,n,S,s) log i (n s) (N n S s) 19
  20. Trọng số của thuật ngữ  Cú thể thờm 0.5 vào mỗi tham số để đảm bảo cỏc trọng số khụng trở thành vụ cựng khi S, s nhỏ: (s 0.5)(N S n s 0.5) w log t (n s 0.5)(S s 0.5) 20
  21. Tớnh toỏn xỏc suất/từ  Khi bắt đầu thực hiện truy vấn  Hoàn toàn khụng biết về R N n 0.5 w log i n 0.5 Tương tự trọng số idf. Cú thể sử dụng giỏ trị này để tớnh hạng ban đầu 21
  22. Vớ dụ mụ hỡnh xỏc suất N n 0.5 wt log n 0.5 22
  23. Cải thiện xếp hạng  Nếu người dựng phản hồi về văn bản phự hợp  Xỏc định lại pi và ri dựa trờn thụng tin này  Hoặc cú thể kết hợp với thụng tin mới |VR | p(1) s p(1) p(2) i i i κ là trọng i |VR |  S  số đó biết  Lặp lại để xỏc định chớnh xỏc hơn những văn bản phự hợp 23
  24. Vớ dụ trọng số phự hợp (s 0.5)(N S n s 0.5) w log Văn bản số 2 là văn bản phự hợp t (n s 0.5)(S s 0.5) 24
  25. Xỏc định pi và ri nhờ vũng lặp Phự hợp phản hồi giả lập  1. Giả sử pi là hằng số với mọi xi trong truy vấn. Vớ dụ, pi = 0.5 với văn bản bất kỳ  2. Giả sử tập V với những văn bản được xếp hạng cao nhất theo mụ hỡnh này là những văn bản phự hợp.  3. Cần xỏc định lại pi và ri, sử dụng phõn bố từ trong V. Đặt Vi là tập văn bản cú chứa xi , chỳng ta cú pi = |Vi| / |V|  4. Giả sử khụng được trả về đồng nghĩa với khụng phự hợp, ri = (ni – |Vi|) / (N – |V|)  5. Lặp cỏc bước 2-4 cho tới khi hội tụ và trả về kết quả. 25
  26. Tổng kết mụ hỡnh BIM  Mụ hỡnh xỏc suất dựa trờn lý thuyết xỏc suất để mụ hỡnh húa sự khụng chắc chắn trong quỏ trỡnh tỡm kiếm  Sử dụng cỏc giả thuyết về sự độc lập trong quỏ trỡnh ước lượng giỏ trị xỏc suất  Trọng số ban đầu của thuật ngữ khi chưa cú thụng tin về văn bản phự hợp được xỏc định tương tự idf.  Phự hợp phản hồi giả lập cú thể giỳp cải thiện xếp hạng bằng cỏch xỏc định lại xỏc suất thuật ngữ  Khụng sử dụng cỏc tần suất thuật ngữ nội văn bản hoặc độ dài văn bản 26
  27. Nội dung chớnh  Tỡm kiếm dựa trờn xỏc suất  Mụ hỡnh nhị phõn độc lập  Mụ hỡnh (Okapi) BM25 27
  28. Okapi BM25  BM25 “Best Match 25”  Được phỏt triển trong hệ thống Okapi (City University London)  Hiệu quả đó được xỏc nhận trong thực nghiệm  Sử dụng tần suất từ và độ dài văn bản, nhưng khụng bổ xung quỏ nhiều tham số so với BIM (Robertson and Zaragoza 2009; Spọrck Jones et al. 2000) 28
  29. Trọng số Okapi VRt 1/ 2 / VNRt 1/ 2 RSVd log  df VR 1/ 2 / N df VR VR 1/ 2 t q t t t t VRt – tập văn (k1 1)tft,d k3 1 tft,q bản phự hợp cú chứa t k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q VNRt – khụng s 1/ 2 / S s 1/ 2 chứa t RSVd  log t q n s 1/ 2 / N n S s 1/ 2 (k1 1)tft,d k3 1 tft,q k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q 29
  30. Trọng số Okapi BM25  Khi từ xuất hiện trong quỏ nửa số văn bản và S = s = 0, thành phần: s 1/ 2 / S s 1/ 2 log n s 1/ 2 / N n S s 1/ 2 cú thể nhận giỏ trị õm  Trong trường hợp khụng cú thụng tin về văn bản phự hợp, cú thể sử dụng cụng thức: N (k1 1)tft,d k3 1 tft,q RSVd  log  t q dft k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q 30
  31. Trọng số Okapi  Trọng số Okapi sử dụng  thành phần “tf” tương tự như VSM  chuẩn húa độ dài văn bản và độ dài truy vấn độc lập  một vài tham số phụ thuộc bộ dữ liệu s 1/ 2 / S s 1/ 2 RSVd  log t q n s 1/ 2 / N n S s 1/ 2 (k1 1)tft,d k3 1 tft,q k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q 31
  32. Tớnh trọng số Okapi BM25 k1 = 1.2 k3 = 7 N (k1 1)tft,d k3 1 tft,q RSVd  log  b = 0.75 t q dft k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q avdl = 3.66 32
  33. Khi cú thụng tin về văn bản phự hợp s 1/ 2 / S s 1/ 2 RSVd  log k1 = 1.2 k3 = 7 t q n s 1/ 2 / N n S s 1/ 2 b = 0.75 (k1 1)tft,d k3 1 tft,q k1 (1 b) b (Ld / Lave ) tft,d k3 tft,q (Lave) avdl = 3.66 33