Bài giảng Tìm kiếm và trình diễn thông tin: Bài 10 - TS.Nguyễn Bá Ngọc

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

Thêm vào BST

Báo xấu

108
lượt xem 9
download

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

Bài 10 - Mô hình nhị phân độc lập là nội dung chính mà bộ bài giảng Tìm kiếm và trình diễn thông tin hướng đến trình bày với các vấn đề chính về tìm kiếm dựa trên xác suất; xác suất trong tìm kiếm thông tin; mô hình nhị phân độc lập; lý thuyết xác suất căn bản;...

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Tìm kiếm và trình diễn thông tin: Bài 10 - TS.Nguyễn Bá Ngọc

(IT4853) Tìm kiếm và trình diễn thông tin Mô hình nhị phân độc lập
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: http://is.hust.edu.vn/~ngocnb 2
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
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
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
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
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
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
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)   X  A, A p( B | X ) p( X )  9
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
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
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
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( xi | R  1, q)  p(d | R  0, q) i 1 p( xi | R  0, q) n p( xi | R  1, q) O ( R | q, d )  O ( R | q )   i 1 p( xi | R  0, q) 13
Mô hình nhị phân độc lập (3) n p( xi | R  1, q) O ( R | q, d )  O ( R | q )   i 1 p( xi | R  0, q) Vì xi chỉ nhận giá trị 1 hoặc 0 p( xi  1 | R  1, q) p( xi  0 | R  1, q) O ( R | q, d )  O ( R | q )    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 pi (1  pi ) O ( R | q, d )  O ( R | q )     xi 1 ri xi  0 (1  ri ) qi 1 qi 1 14
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
Mô hình nhị phân độc lập (4) pi 1  pi O ( R | q, d )  O ( R | q )   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 pi  1  ri 1  pi  1  pi O ( R | q, d )  O ( R | q )        xi 1 ri xi 1  1  pi 1  ri  xi 0 1  ri qi 1 qi 1 qi 1 pi (1  ri ) 1  pi O ( R | q, d )  O ( R | q )    xi  qi 1 ri (1  pi ) qi 1 1  ri Từ truy vấn có trong văn bản Tất cả từ truy vấn 16
Mô hình nhị phân độc lập (5) pi (1  ri ) 1  pi O ( R | q, d )  O ( R | q )    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 pi (1  ri ) pi (1  ri ) Rank (d , q )  log    log xi  qi 1 ri (1  pi ) xi  qi 1 ri (1  pi ) 17
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 pi (1  ri ) pi (1  ri ) Rank (d , q )  log    log 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
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: pi  ri  S N S s ( S  s) wi  K ( N , n, S , s)  log (n  s) ( N  n  S  s) 19
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) wt  log (n  s  0.5)(S  s  0.5) 20