Chuyển tới nội dung chính

BM25 và hai chỗ tf-idf chấm hỏng

Sáu tài liệu sửa đượcHai thanh k1 và bSo thẳng với tf-idf

BM25 và hai chỗ tf-idf chấm hỏng

Cùng một kho tài liệu, cùng một câu truy vấn, hai cách chấm điểm cho hai bảng xếp hạng khác nhau. Chỗ khác nhau nằm ở hai con số bạn kéo được bằng tay.

Khi máy tìm kiếm nhận một câu truy vấn, nó không chỉ cần biết tài liệu nào có chứa từ khoá, nó cần xếp hạng. tf-idf làm được việc cộng điểm, nhưng đem đi xếp hạng thì lộ hai chỗ hỏng. Thứ nhất, điểm tăng tuyến tính theo số lần xuất hiện, nên một tài liệu nhồi từ khoá hai mươi lần được hai mươi phần điểm. Thứ hai, nó không biết tài liệu dài hay ngắn, mà tài liệu càng dài thì càng dễ vô tình chứa nhiều từ khoá, nên tài liệu dài thắng chỉ vì nó dài.

BM25 vá đúng hai chỗ đó bằng hai tham số. k1 bắt phần tần suất bão hoà, tức là chạm trần rồi thôi, thay vì cứ tăng mãi. b chia độ dài tài liệu cho độ dài trung bình của kho rồi lấy đó làm hình phạt. Kéo hai thanh dưới đây và nhìn cột điểm, cả hai chỗ vá đều hiện ra thành số.

BM25 · bão hoà tần suất và chuẩn hoá độ dài
Hạng 1 là tài liệu 6 với 1.7794
N = 6avgdl = 13.50k1 = 1.2b = 0.75trần bão hoà = k1 + 1 = 2.2log cơ số e
Xếp hạng: BM25 so với tf-idf trên cùng bộ tài liệu
Hạng BM25Tài liệudldl/avgdlĐiểm BM25độ lớnHạng tf-idfĐiểm tf-idf
190.671.779421.6219
270.521.742931.2164
3392.891.704114.4601
4120.891.003440.8109
570.520.668150.4055
670.520.092360.0000
Hai cách chấm đang xếp khác nhau. Dòng tô nền là những tài liệu có hạng BM25 khác hạng tf-idf. Kéo b về 0 để BM25 quên hẳn độ dài, lúc đó hai bảng thường trùng nhau trở lại.
Mổ xẻ tài liệu 3: từng từ khoá đóng góp bao nhiêu
Từ khoátfdfidfk1(1-b+b·dl/avgdl)tf(k1+1)tf + phần độ dàiphần bão hoàđóng góp BM25đóng góp tf-idf
mô440.44182.90008.80006.90001.27540.56351.6219
hình440.44182.90008.80006.90001.27540.56351.6219
họcdf = N360.07412.90006.60005.90001.11860.08290.0000
máy340.44182.90006.60005.90001.11860.49431.2164
Độ dài tài liệu đang mổ xẻ (dl)39
Độ dài trung bình của kho (avgdl)13.50
Phần độ dài trong mẫu số, chung cho mọi từ của tài liệu này2.9000
Tổng điểm BM25 của tài liệu này1.7041
Đóng góp tăng thế nào khi tf tăng
00.97tf = 0tf = 12
BM25tf-idftrần idf·(k1+1) = 0.9720
Từ mô ở tf = 2 đóng góp0.3967
Cũng từ đó ở tf = 10, tức gấp 5 lần số lần xuất hiện0.7535
Nghĩa là gấp bấy nhiêu lần, không phải gấp 51.90x
Cùng chỗ đó tf-idf gấp đúng5.00x
Biểu đồ và bốn dòng ngay trên đóng băng độ dài tài liệu: chỉ có tf chạy, còn dl = 39 và avgdl = 13.50 đứng yên. Một tài liệu thật lặp thêm mười lần từ khoá thì cũng dài thêm mười token và bị phạt độ dài nặng hơn, nên đường cong này tách riêng hiệu ứng bão hoà chứ không mô tả một tài liệu đang phình ra.
Từ học có mặt trong cả N = 6 tài liệu, tức df = N. tf-idf cho nó log(N/N) = 0 và xoá sổ luôn, còn BM25 vẫn cho log(0.5/6.5 + 1) = 0.0741, nhỏ nhưng dương. Chính cái + 1 trong log giữ nó không âm.
Sửa truy vấn và sửa cả sáu tài liệu, xoá trắng một ô nếu muốn kho chỉ còn năm tài liệu, khi đó N và avgdl tụt theo. Công thức dùng ở đây là bản Robertson và Sparck Jones với idf = log((N - df + 0.5)/(df + 0.5) + 1). Tách token chỉ là cắt theo khoảng trắng nên mô hình thành hai token: quy ước của bài này, không phải chân lý. Kho chỉ có sáu ô nên df chỉ nhận được bảy giá trị từ 0 tới 6, biên độ idf ở đây hẹp hơn hẳn một kho thật hàng triệu tài liệu.

Bảng đang nói gì ở trạng thái mặc định​

Kho có N = 6 tài liệu, tổng 81 token nên avgdl = 13.50. Truy vấn mô hình học máy tách thành bốn từ khoá. Tài liệu 3 dài 39 token, gần gấp ba avgdl và gấp hơn năm lần tài liệu ngắn nhất.

Nhìn hai cột hạng cạnh nhau. tf-idf xếp tài liệu 3 hạng 1 với 4,4601 điểm, bỏ xa tài liệu 6 chỉ được 1,6219, tức gấp 2,75 lần. BM25 xếp tài liệu 3 xuống hạng 3 với 1,7041, sau tài liệu 6 được 1,7794 và tài liệu 2 được 1,7429. Cả ba nằm gọn trong khoảng 0,0752 điểm.

Vì sao hai bảng lệch nhau như vậy. Tài liệu 3 có tf cao nhất kho: mô và hình mỗi từ 4 lần, học và máy mỗi từ 3 lần. Với tf-idf thì 11 lần xuất hiện của ba từ còn có idf khác 0 được nhân thẳng vào điểm, không có gì hãm lại, và 11 * log(1,5) cho đúng 4,4601. Với BM25 thì tài liệu đó dài 39 token, cột dl/avgdl ghi 2,89, nên phần độ dài trong mẫu số phình lên 2,9000 và dìm mọi phần bão hoà của nó xuống.

Bấm vào tài liệu 3 để mở bảng mổ xẻ. Từ mô có tf = 4, tử số tf(k1+1) bằng 8,8000, mẫu số 4 + 2,9000 bằng 6,9000, phần bão hoà 1,2754, nhân với idf = 0,4418 ra đóng góp 0,5635. Bốn dòng cộng lại đúng bằng 1,7041 ở ô tổng.

Có một dòng đáng nhìn kỹ hơn cả. Từ học cũng xuất hiện 3 lần trong tài liệu 3, nhưng nó nằm trong cả sáu tài liệu nên df = 6 = N, idf chỉ còn 0,0741, và đóng góp của nó là 0,0829 trên tổng 1,7041, chưa tới 5 phần trăm. Trong cột tf-idf ngay bên cạnh, cũng từ đó đóng góp đúng 0,0000. Hai công thức xử lý một từ có mặt khắp nơi theo hai kiểu khác hẳn nhau, và phần dưới sẽ nói vì sao.

Bão hoà tần suất: lần thứ mười gần như vô nghĩa​

Biểu đồ nhỏ vẽ đóng góp của một từ khoá khi tf chạy từ 0 tới 12, giữ nguyên mọi thứ khác. Đường liền là BM25, đường đứt nét là tf-idf.

Ở mặc định k1 = 1.2, từ mô trong tài liệu 3 đóng góp 0,3967 khi tf = 2 và 0,7535 khi tf = 10. Số lần xuất hiện gấp 5, điểm chỉ gấp 1,90. Cùng chỗ đó tf-idf đi từ 0,8109 lên 4,0547, gấp đúng 5,00, vì nó là đường thẳng qua gốc toạ độ.

Kéo k1 xuống 0.3 rồi nhìn lại hai dòng đó: 0,4216 và 0,5356, gấp 1,27. Xuất hiện 10 lần gần như không hơn xuất hiện 2 lần thật. Kéo k1 lên 3 thì tỉ lệ nới ra thành 2,68, đường cong duỗi thẳng hơn nhưng vẫn không bao giờ thành đường thẳng.

Lý do nằm ở dạng của công thức. Phần tần suất là tf * (k1 + 1) / (tf + ...), một phân thức chứ không phải một phép nhân. Khi tf lớn dần, tử và mẫu cùng lớn, và tỉ số tiến tới k1 + 1 rồi dừng. Đường nét chấm nằm ngang trong biểu đồ chính là cái trần idf * (k1 + 1), ở mặc định nó bằng 0,9720. Đường BM25 bò lên sát nó nhưng không chạm tới, còn đường tf-idf thì phóng thẳng qua.

Trường hợp cực đoan đáng thử: bấm nút k1 = 0. Phần bão hoà lập tức bằng đúng 1 với mọi tf dương, đường cong dẹt hoàn toàn ở mức 0,4418 tức là đúng idf của từ đó, và điểm của cả tài liệu rút về tổng idf của những từ khoá mà nó có. Lúc này BM25 chỉ còn đếm có hay không có, hoàn toàn không quan tâm có bao nhiêu.

Chuẩn hoá độ dài: kéo b thì thứ hạng đảo​

Phần độ dài trong mẫu số là k1 * (1 - b + b * dl/avgdl). Cách nhanh nhất để hiểu nó là kéo b về hai đầu.

Bấm b = 0. Biểu thức trong ngoặc thành 1 - 0 + 0 bằng 1, mẫu số rút gọn còn tf + k1, và độ dài tài liệu biến mất hẳn khỏi công thức. Cột dl vẫn hiện nhưng không còn tác dụng. Bảng xếp hạng lúc này là 3, 6, 2, 4, 1, 5, tài liệu dài quay lại hạng 1 với 2,3062 điểm, và trùng khít với thứ tự của tf-idf. Đó không phải trùng hợp: bỏ chuẩn hoá độ dài đi thì BM25 chỉ còn khác tf-idf ở phần bão hoà, mà phần bão hoà giữ nguyên thứ hạng trong ví dụ này.

Bấm b = 1. Biểu thức thành dl/avgdl trọn vẹn, phạt tối đa. Bảng thành 2, 6, 3, 4, 1, 5: tài liệu 2 dài 7 token leo lên hạng 1 với 1,8981, còn tài liệu 3 rơi xuống 1,5680. So với b = 0 thì ba vị trí đầu đảo ngược hoàn toàn, từ 3, 6, 2 thành 2, 6, 3.

Điều đáng nhớ là cả hai đầu đều là lựa chọn, không có đầu nào đúng sẵn. Ở b = 0 bạn tin rằng tài liệu dài chứa nhiều thông tin hơn thật. Ở b = 1 bạn tin rằng độ dài chỉ là nhiễu. Giá trị 0.75 mặc định của BM25 là một thoả hiệp rút ra từ thực nghiệm trên tập TREC, không phải một hằng số của tự nhiên, và với kho của bạn thì nó phải được chỉnh lại.

Có một ca đặc biệt gọn đến mức nên nhớ: nếu mọi tài liệu trong kho dài bằng nhau thì dl/avgdl luôn bằng 1, biểu thức trong ngoặc thành 1 - b + b bằng 1 với mọi b, và mẫu số về đúng k1 + tf. Nói cách khác, khi độ dài đồng đều thì b không làm gì cả, kéo thanh trượt chỉ tốn công.

Cái + 1 trong idf và vì sao nó ở đó​

BM25 có nhiều biến thể, và chỗ chúng khác nhau nhiều nhất là idf. Bản dùng trong bài này là bản Robertson và Sparck Jones ở dạng đã chặn dưới:

idf = log((N - df + 0.5)/(df + 0.5) + 1)

Hãy thử bỏ cái + 1 cuối cùng đi và tính lại cho từ học, từ có mặt trong cả sáu tài liệu. Không có + 1 thì đối số của log là 0.5/6.5 bằng khoảng 0,0769, nhỏ hơn 1, nên idf âm. Một tài liệu sẽ bị trừ điểm vì chứa từ khoá mà người dùng vừa gõ. Đó là hành vi vô lý mà bản gốc thật sự mắc phải khi hơn nửa kho chứa từ đó.

Có + 1 thì đối số thành 1 + 0,0769 bằng 1,0769, luôn lớn hơn 1, nên idf luôn dương. Với học nó ra 0,0741, nhỏ xíu nhưng không phải 0. So với tf-idf ở cột bên: log(6/6) = log(1) = 0, xoá sổ hoàn toàn. Hệ quả thấy ngay ở tài liệu 5 sinh viên học cách đọc dữ liệu: nó chỉ chứa đúng từ học trong bốn từ khoá, nên tf-idf chấm nó 0,0000, không phân biệt được nó với một tài liệu hoàn toàn lạc đề. BM25 chấm nó 0,0923, vẫn thấp nhất bảng nhưng ít ra là một con số dương và có thứ tự.

Vài chỗ dễ vấp​

  • b và k1 không độc lập về cảm giác. Phần độ dài được nhân với k1, nên khi k1 = 0 thì b mất tác dụng hoàn toàn. Bấm k1 = 0 rồi kéo b, bảng đứng yên. Đó không phải núm hỏng, đó là công thức.
  • Biểu đồ giữ nguyên độ dài tài liệu khi cho tf chạy. Trong thực tế, một tài liệu lặp thêm mười lần từ khoá thì cũng dài thêm mười token, và hình phạt độ dài sẽ tăng theo. Biểu đồ cố tình đóng băng dl để tách riêng hiệu ứng bão hoà. Số của nó là đúng với giả định đó, không phải với một tài liệu thật đang phình ra.
  • Thêm một bản sao vào kho có làm đảo thứ hạng của các tài liệu khác không. Trực giác nói không, nhưng câu trả lời đúng là có thể, và chính bộ mặc định này là ví dụ. Sim chỉ có đúng sáu ô cố định nên bạn không dán thêm được tài liệu thứ bảy, con số dưới đây là do cổng kiểm dựng lại: thứ tự của năm tài liệu còn lại đi từ 6, 2, 3, 4, 5 thành 2, 6, 3, 4, 5. Lý do là bản sao kéo df của học từ 6 lên 7 và df của máy từ 4 lên 5 trong khi mô và hình đứng yên, đồng thời avgdl tụt từ 13,50 xuống khoảng 12,57. Các từ khoá bị cân lại với nhau, nên thứ hạng đổi theo.
  • Rút truy vấn về đúng một từ cũng không cứu được chuyện đó. Lập luận nghe rất xuôi: một từ thì mọi tài liệu cùng nhân với một idf duy nhất, mà nhân chung một số dương thì không đảo được thứ tự của ai. Vế đầu đúng, kết luận thì sai. idf đúng là thừa số chung, nhưng avgdl thì không: nó nằm trong mẫu số riêng của từng tài liệu, ngay cạnh dl của chính tài liệu đó, nên khi avgdl xê dịch thì mỗi tài liệu bị đẩy một kiểu. So hai tài liệu A và B, điều kiện để A trên B là k1(1-b)·avgdl·(tfA - tfB) + k1·b·(tfA·dlB - tfB·dlA) > 0: số hạng đầu có avgdl, số hạng sau không, nên khi hai số hạng trái dấu thì avgdl đổi là thứ tự đổi. Vẫn trên bộ mặc định, vẫn cổng kiểm dựng lại: truy vấn một từ máy, k1 = 1.2, b = 0.20, nhân bản tài liệu 1, thì năm tài liệu còn lại đi từ 3, 6, 2, 4, 5 thành 6, 3, 2, 4, 5. Quét hết lưới thanh trượt mà bạn kéo được, k1 từ 0 tới 3 và b từ 0 tới 1, trên cả bốn từ khoá của truy vấn mặc định và cả sáu tài liệu có thể đem nhân bản, có 252 tổ hợp làm đúng chuyện đó; riêng cặp máy với tài liệu 1 đã chiếm 31 trong số ấy. Bất biến chỉ đứng vững ở ba chỗ hẹp: b = 0 vì độ dài rời khỏi công thức và thứ tự chỉ còn theo tf, b = 1 vì số hạng chứa avgdl triệt tiêu khi so từng cặp, và khi bản sao dài đúng bằng avgdl nên avgdl không nhúc nhích.
  • BM25 vẫn không hiểu nghĩa. Nó đếm chuỗi ký tự y như tf-idf. học và học tập là hai chiều rời nhau. Nó chỉ chấm điểm khớp từ khoá cho khéo hơn, chứ không đọc hiểu gì cả.
  • Con số trên trang này gắn với sáu tài liệu tí hon. Kho thật có hàng triệu tài liệu, idf sẽ dàn ra rộng hơn nhiều và avgdl ổn định hơn nhiều. Hiệu ứng ở đây thật nhưng biên độ thì nhỏ hơn hẳn thực tế, vì N = 6 làm mọi df chỉ có bảy giá trị khả dĩ.
Điều rút ra

tf-idf cộng điểm, BM25 xếp hạng. Khác biệt nằm ở hai chỗ và cả hai đều kéo được bằng tay: k1 bắt tần suất chạm trần k1 + 1 rồi dừng, b quy độ dài tài liệu về tỉ lệ so với avgdl rồi phạt. Kéo b từ 0 lên 1 trên bộ mặc định là thấy ba vị trí đầu đảo ngược, và điều đó cho thấy thứ hạng bạn nhận được là hệ quả của tham số bạn chọn, không phải một sự thật khách quan về kho tài liệu.

Câu hỏi tự kiểm0/3 đúngchưa trả lời
  1. 1Ở mặc định, tf-idf xếp tài liệu 3 (39 token) hạng 1 còn BM25 xếp nó hạng 3. Bấm nút b = 0 thì chuyện gì xảy ra với bảng BM25?
  2. 2Với k1 = 0.3, một từ khoá xuất hiện 10 lần thay vì 2 lần thì đóng góp của nó tăng bao nhiêu lần?
  3. 3Từ "học" có mặt trong cả 6 tài liệu nên df = N. Hai công thức chấm nó ra bao nhiêu?
Cập nhật lần cuối vào