Tìm kiếm và trình diễn thông tin - Mô hình nhị phân độc lập

(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: 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 Kết luận phù hợp là không chắc chắn Không bảo toàn ngữ nghĩaNhu cầu thông tin người dùng Văn bản Biểu diễn logic truy vấn Biểu diễn logic văn bản So sánh  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  Quy tắc nhân xác suất (luật chuỗi): Lý thuyết xác suất căn bản )(),( BApBAp  )( )()|( )|( Bp ApABp BAp   Luật Bayes )()|(),( BpBApBAp  )()|(),( ApABpBAp  8 Lý thuyết xác suất căn bản ),(),()( BApBApBp   Quy tắc phân tích xác suất (luật phân tích): )( )()|( )|( )|( , Ap XpXBp ABp BAp AAX             Kết hợp luật Bayes và luật phân tích 9 Lý thuyết xác suất căn bản )(1 )( )( )( )( Ap Ap Ap Ap AO    Cơ hội (Odds): 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ừ  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ơ ),,( 1 nxxd  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 )|( ),0|()|0( )|( ),1|()|1( ),|0( ),|1( ),|( qdp qRdpqRp qdp qRdpqRp dqRp dqRp dqRO       12 Mô hình nhị phân độc lập (2)  Sử dụng giả thuyết độc lập Hằng số với một truy vấn Cần xác định      n i i i qRxp qRxp qROdqRO 1 ),0|( ),1|( )|(),|(        n i i i qRxp qRxp qRdp qRdp 1 ),0|( ),1|( ),0|( ),1|( ),0|( ),1|( )|0( )|1( ),|0( ),|1( ),|( qRdp qRdp qRp qRp dqRp dqRp dqRO          13 Mô hình nhị phân độc lập (3)      n i i i qRxp qRxp qROdqRO 1 ),0|( ),1|( )|(),|(         01 ),0|0( ),1|0( ),0|1( ),1|1( )|(),|( ii x i i x i i qRxp qRxp qRxp qRxp qROdqRO Vì xi chỉ nhận giá trị 1 hoặc 0 );,1|1( qRxpp ii  ri = p(xi =1|R= 0,q);         1 0 1 1 )1( )1( )|(),|( i i i i q x i i q x i i r p r p qROdqRO  Đặt:  Giả sử với thuật ngữ không có trong truy vấn thì pi = ri 14 ),1|1( qRxpp ii  ),0|1( qRxpr ii  ),1|0(1 qRxpp ii  ),0|0(1 qRxpr ii  Các đại lượng xác suất cơ bản 15 Mô hình nhị phân độc lập (4) Từ truy vấn có trong văn bản Từ truy vấn không có trong văn bản Từ truy vấn có trong văn bản Tất cả từ truy vấn                      1 0 1 1 1 1 1 1 1 1 1 1 )|(),|( i i i i i i q x i i q x i i i i q x i i r p r p p r r p qROdqRO         11 1 1 )1( )1( )|(),|( iii q i i qx ii ii r p pr rp qROdqRO       1 01 1 1 )|(),|( i iii q x i i qx i i r p r p qROdqRO 16 Mô hình nhị phân độc lập (5) 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         11 1 1 )1( )1( )|(),|( iii q i i qx ii ii r p pr rp qROdqRO Hàm xếp hạng         11 )1( )1( log )1( )1( log),( iiii qx ii ii qx ii ii pr rp pr rp qdRank 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         11 )1( )1( log )1( )1( log),( iiii qx ii ii qx ii ii pr rp pr rp qdRank    1 ;),( ii qx icqdRank )1( )1( log ii ii i pr rp c    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ù hợp Tổng xi=1 s n-s n xi=0 S-s N-n-S+s N-n Tổng S N-S N S s pi  SN sn ri    )()( )( log),,,( sSnNsn sSs sSnNKwi    • Xác định: 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ỏ: )5.0)(5.0( )5.0)(5.0( log    sSsn snSNs wt 20 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 5.0 5.0 log    n nN wi Tương tự trọng số idf. Có thể sử dụng giá trị này để tính hạng ban đầu 21 Ví dụ mô hình xác suất          5.0 5.0 log n nN wt 22 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  Lặp lại để xác định chính xác hơn những văn bản phù hợp           S ps VR pVR p iiii )1()1( )2( || || κ là trọng số đã biết 23 Ví dụ trọng số phù hợp Văn bản số 2 là văn bản phù hợp )5.0)(5.0( )5.0)(5.0( log    sSsn snSNs wt 24 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 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 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 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 Trọng số Okapi                                        qt qt dtaved dt qt tttt tt d tfk tfk tfLLbbk tfk VRVRdfNVRdf VNRVR RSV ,3 ,3 ,1 ,1 1 )/()1( )1( 2/1/2/1 2/1/2/1 log                                    qt qt dtaved dt qt d tfk tfk tfLLbbk tfk sSnNsn sSs RSV ,3 ,3 ,1 ,1 1 )/()1( )1( 2/1/2/1 2/1/2/1 log VRt – tập văn bản phù hợp có chứa t VNRt – không chứa t 29 Trọng số Okapi BM25  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:                   qt qt qt dtaved dt t d tfk tfk tfLLbbk tfk df N RSV ,3 ,3 ,1 ,1 1 )/()1( )1( log  Khi từ xuất hiện trong quá nửa số văn bản và S = s = 0, thành phần:               2/1/2/1 2/1/2/1 log sSnNsn sSs có thể nhận giá trị âm 30 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                                    qt qt dtaved dt qt d tfk tfk tfLLbbk tfk sSnNsn sSs RSV ,3 ,3 ,1 ,1 1 )/()1( )1( 2/1/2/1 2/1/2/1 log 31 Tính trọng số Okapi BM25 k1 = 1.2 k3 = 7 b = 0.75 avdl = 3.66                   qt qt qt dtaved dt t d tfk tfk tfLLbbk tfk df N RSV ,3 ,3 ,1 ,1 1 )/()1( )1( log 32 Khi có thông tin về văn bản phù hợp k1 = 1.2 k3 = 7 b = 0.75 (Lave) avdl = 3.66                                    qt qt dtaved dt qt d tfk tfk tfLLbbk tfk sSnNsn sSs RSV ,3 ,3 ,1 ,1 1 )/()1( )1( 2/1/2/1 2/1/2/1 log 33 34