BM25 thuật toán xếp hạng các văn bản theo độ phù hợp
BM25 thu t toán x p h ng các văn b n theo đ phù h pậ ế ạ ả ộ ợ
Gi i thi uớ ệ
Trong tìm ki m thông tin, Okapi BM25 là hàm tính th h ng đ c các côngế ứ ạ ượ
c tìm ki m s d ng đ x p h ng các văn b n theo đ phù h p v i truy ụ ế ử ụ ể ế ạ ả ộ ợ ớ
v n nh t đ nh. Hàm x p h ng này d a trên mô hình xác su t, đ c phát ấ ấ ị ế ạ ự ấ ượ
minh ra vào nh ng năm 1970 – 1980. Ph ng pháp có tên BM25 (BM – bestữ ươ
match), nh ng ng i ta th ng g i "Okapi BM25", vì l n đ u tiên công ư ườ ườ ọ ầ ầ
th c đ c s d ng trong h th ng tìm ki m Okapi, đ c sáng l p t i ứ ượ ử ụ ệ ố ế ượ ậ ạ
tr ng đ i h c London nh ng năm 1980 và 1990.ườ ạ ọ ữ
BM25 là m t ph ng pháp x p h ng đ c s d ng r ng rãi trong tìm ộ ươ ế ạ ượ ử ụ ộ
ki m. Trong Web search nh ng hàm x p h ng này th ng đ c s d ng ế ữ ế ạ ườ ượ ử ụ
nh m t ph n c a các ph ng pháp tích h p đ dùng trong machine ư ộ ầ ủ ươ ợ ể
learning, x p h ng.ế ạ
M t trong nh ng k thu t tìm ki m n i ti ng hi n nay đang s d ng thu t ộ ữ ỹ ậ ế ỗ ế ệ ử ụ ậ
toán này là Elasticsearch. Khi tìm ki m, Elascticsearch tr v cho mình ế ả ề
ngoài các k t qu tìm đ c, còn có đánh giá đ liên quan c a k t qu d a ế ả ượ ộ ủ ế ả ự
trên giá tr th c d ng score. Elasticsearch s s p x p các k t qu tr v ị ự ươ ẽ ắ ế ế ả ả ề
c a các query theo th t score gi m d n. Đây là đi m mà mình th y r t ủ ứ ự ả ầ ể ấ ấ
thú v trong Elasticsearch, và mình s dành bài vi t này đ nói v cách làm ị ẽ ế ể ề
th nào ng i ta tính toán và đ a ra đ c giá tr score và t đó hi u đ c ế ườ ư ượ ị ừ ể ượ
thu t toán BM25.ậ
L u ýư
M t s thu t ng r t hay đ c s d ng trong Elasticsearch:ộ ố ậ ữ ấ ượ ử ụ
1. relevance (đ liên quan)ộ
2. index (t ng đ ng v i database trong mysql)ươ ươ ớ
3. type (t ng đ ng v i table trong mysql)ươ ươ ớ
4. document (t ng ng v i record trong mysql)ươ ứ ớ
5. term (t , t khóa)ừ ừ
6. field (có th g i là tr ng)ể ọ ườ
Th c ch t, BM25 d a trên n n t ng c a TF/IDF, và c i ti n d a trên lý ự ấ ự ề ả ủ ả ế ự
thuy tế probabilitistic information retrieval. Vì v y đ hi u đ c g c r c aậ ể ể ượ ố ễ ủ
nó tr c tiên chúng ta c n ph i bi t TF/IDF là gì.ướ ầ ả ế
TF/IDF
TF/IDF vi t t t c a thu t ng ti ng Anh term frequency – inverse ế ắ ủ ậ ữ ế
document frequency là tr ng s c a m t t trong văn b n thu đ c qua ọ ố ủ ộ ừ ả ượ
th ng kê th hi n m c đ quan tr ng c a t này trong m t văn b n, mà ố ể ệ ứ ộ ọ ủ ừ ộ ả
b n thân văn b n đang xét n m trong m t t p h p các văn b n.ả ả ằ ộ ậ ợ ả
Các tính tr ng s tf-idf:ọ ố
Term frequency
Inverse document frequency
Document Length
Term frequency
Y u t này đánh giá t n su t xu t hi n c a term trong field. Càng xu t ế ố ầ ấ ấ ệ ủ ấ
hi n nhi u, relevance càng cao. Dĩ nhiên r i, m t field mà t khoá xu t ệ ề ồ ộ ừ ấ
hi n 5 l n s cho relevance cao h n là field mà t khoá ch xu t hi n 1 l n.ệ ầ ẽ ơ ừ ỉ ấ ệ ầ
Thông qua th nghi m th c th và kh o sát ng i dùng thì Information ử ệ ự ế ả ườ
Retrieval nh n ra r ng:ậ ằ N u m t bài vi t xu t hi n t "dog" 6 l n thì nó cóế ộ ế ấ ệ ừ ầ
liên quan g p đôi bài vi t xu t hi n t "dog" 3 l n không.ấ ế ấ ệ ừ ầ Thì h u h t m i ầ ế ọ
ng i đ u nói không. Ch c ch n bài vi t xu t hi n t "dog" 6 l n s liên ườ ề ắ ắ ế ấ ệ ừ ầ ẻ
quan nhi u h n nh ng không th nói nó có liên quan g p 2 l n so v i bài ề ơ ư ế ấ ầ ớ
vi t xu t hi n t "dog" 3 l n đ c. Chính vì th TF không còn đ c l y ế ấ ệ ừ ầ ượ ế ượ ấ
tr c ti p, thay vào đó TF đ c tính theo công th c sau:ự ế ượ ứ
tf(t, d) = √frequency
Gi i thích:ả term frequency (tf) c a t trong document d đ c tính b ng căn ủ ượ ằ
b c hai c a s l n t xu t hi n trong d.ậ ủ ố ầ ấ ệ
Inverse document frequency
Inverse document frequency dùng đ đánh giá đ đ c bi t c a m t t d a ể ộ ặ ệ ủ ộ ừ ự
vào t n su t xu t hi n c a term trên toàn b index. Càng xu t hi n nhi u ầ ấ ấ ệ ủ ộ ấ ệ ề
thì bài vi t càng ít liên quan. Nghe có v h i ng c ng o nh th t s nó ế ẻ ơ ượ ạ ư ậ ự
r t h p lý:ấ ợ
Ví d :ụ B n mu n tìm ki m thu t toán BM25 là gì. Khi b n tìm ki m ạ ố ế ậ ạ ế
gooogle v i t khóa "thu t toán" thì s nh n đ c r t nhi u k t qu ớ ừ ậ ẻ ậ ượ ấ ề ế ả
nh ng l i có r t ít k t qu b n mong mu n. Còn khi b n tìm ki m v i t ư ạ ấ ế ả ạ ố ạ ế ớ ừ
khóa "BM25" thì nh n đ c ít k t qu h n nh ng b n s th y rõ ràng các ậ ượ ế ả ơ ư ạ ẻ ấ
k t qu tìm ki m s sát v i k t qu b n mong mu n. Suy ra t khóa ế ả ế ẻ ớ ế ả ạ ố ừ
"thu t toán" s có giá tr th p h n t khóa "BM25", "BM25" s cho ra k t ậ ẻ ị ấ ơ ừ ẻ ế
qu có relevance cao h n vì nó xu t hi n ít h n trên toàn b index.ả ơ ấ ệ ơ ộ
T ng t , ng i dùng cho r ng không th k t lu n 1 t xu t hi n trong 10ươ ự ườ ằ ể ế ậ ừ ấ ệ
bài vi t s đ c bi t h n 10 l n m t t xu t hi n trong 100 bài vi t.T ng ế ẻ ặ ệ ơ ầ ộ ừ ấ ệ ế ổ
h p d li u th c t công th c c a Inverse document frequency đ c tính ợ ữ ệ ự ế ứ ủ ượ
nh sau:ư
log ( numDocs / docFreq + 1) + 1
Gi i thích:ả inverse document frequency (idf) c a t là logarit c s e (logarit ủ ơ ố
t nhiên) c a th ng gi a t ng s documents trong index và s documents ự ủ ươ ữ ổ ố ố
xu t hi n t (giá tr công thêm 1 đây đ tránh x y ra l i Division by zero).ấ ệ ị ở ể ả ỗ
Document Length
Y u t này đánh giá đ dài c a field. Field càng ng n, thì term s có giá tr ế ố ộ ủ ắ ẽ ị
càng cao; và ng c l i. Đi u này hoàn toàn d hi u, b n có th th y m t ượ ạ ề ễ ể ạ ể ấ ộ
t xu t hi n trong title s có giá tr h n r t nhi u cũng t đó nh ng xu t ừ ấ ệ ẽ ị ơ ấ ề ừ ư ấ
hi n trong content.ệ
Kết quả trung bình được tính từ dữ liệu khảo sát người dùng như
sau:
Raw Length Field Norm Score
1 1.0
2 0.707
4 0.5
64 0.125
128 0.088
256 0.0625
norm(d) = 1 / √numTerms
Gi i thích:ả field-length norm (norm) là ngh ch đ o c a căn b c hai s ị ả ủ ậ ố
l ng term trong field. (có th hi u là s l ng ch c a field đó)ượ ể ể ố ượ ữ ủ
All Together
score cu i cùng s là tích c a 3 giá tr trên:ố ẽ ủ ị
IDF score * TF score * fieldNorms
Hay
log(numDocs / (docFreq + 1)) * √frequency * (1 / √numTerms)
Trong đó:
numDocs chính là maxDocs, đôi khi bao g m c nh ng document đã ồ ả ữ
b deleteị
fieldNorm đ c tính toán và l u tr d i d ng 8 bit floating point ượ ư ữ ướ ạ
number. Nên khi tính toán, h th ng s encode và decode giá tr c a ệ ố ẽ ị ủ
fieldNorm v 8 bit, và theo đó, b n s th y giá tr filedNorm đôi khi ề ạ ẽ ấ ị
h i khác so v i tính toán m t chút xíu xíu thôi. ơ ớ ộ
BM25
IDF trong BM25
Bi u để ồ
Trên bi u đ cho th y IDF trong BM25 khá gi ng IDF trong TF/IDF. Tuy ể ồ ấ ố
nhiên BM25 đã ch nh s a công th c tính l i đ thêm kh năng đ a ra score ỉ ử ứ ạ ể ả ư
âm khi t n su t xu t hi n c a term trên toàn b index r t cao(term r t ít ầ ấ ấ ệ ủ ộ ấ ấ
đ c bi t).ặ ệ
Công th c:ứ
idf(t) = log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))
Trong đó:
docCount: s l ng documentố ượ
docFreq: s l ng document ch a termố ượ ứ
TF trong BM25
Bi u để ồ
Trên bi u đ cho th y: Đ i v i TF/IDF thì score t TF s tăng vô h n khi ể ồ ấ ố ớ ừ ẻ ạ
TF tăng lên. Đ gi m tác đ ng c a TF v i relevance thì BM25 đã ch nh s aể ả ộ ủ ớ ỉ ử
công th c c a TF l i. K t qu score c a TF s gi i h n t i 1 đi m c c ứ ủ ạ ế ả ủ ẻ ớ ạ ớ ể ự
đ i, và chúng ta có th tùy ch nh gi i h n này:ạ ể ỉ ớ ạ
Công th c:ứ
((k + 1) * tf) / (k + tf)
*Trong đó: *
k: h ng s (th ng là 1.2)ằ ố ườ
freq: frequency c a term trong documentủ
Document Length trong BM25
có thể bạn quan tâm
TỔNG HỢP CHỨNG TỪ KẾ TOÁN HÀNG TỒN KHO THEO THÔNG TƯ 133/2016/TT-BTC T...
1
740
313
Kế toán, kiểm toán
1
(New)
Hạch toán kế toán phải thu của khách hàng theo Thông tư 133/2016
5
745
307
Kế toán, kiểm toán
5
(New)
Hạch toán kế toán hàng mua đang đi đường theo Thông tư 133/2016
2
823
309
Kế toán, kiểm toán
2
(New)
Hạch toán Kế toán doanh thu bán hàng và cung cấp dịch vụ theo Thông tư...
9
804
296
Kế toán, kiểm toán
9
(New)
Hạch toán kế toán tài khoản tiền gửi ngân hàng theo thông tư 133/2016
4
781
330
Kế toán, kiểm toán
4
(New)
Hạch toán kế toán hàng hóa theo Thông tư 133/2016
8
727
274
Kế toán, kiểm toán
8
(New)
Hạch toán kế toán hàng gửi bán theo Thông tư 133/2016
2
699
269
Kế toán, kiểm toán
2
(New)
Hạch toán kế toán mua hàng theo Thông tư 133/2016
3
607
260
Kế toán, kiểm toán
3
(New)
thông tin tài liệu
BM25 là một phương pháp xếp hạng được sử dụng rộng rãi trong tìm kiếm. Trong Web search những hàm xếp hạng này thường được sử dụng như một phần của các phương pháp tích hợp để dùng trong machine learning, xếp hạng.
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Tâm lý xã hội VÀ Hệ tư tưởng
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Trắc nghiệm kinh tế
Địa lý 12 Phát triển cây công nghiệp lâu năm Tây Nguyên
Mẫu slide về các môn thể thao
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
