3.4 TF-IDF và vector space model — tính bằng tay

BM25 không xuất hiện từ chân không. Nó là bản sửa lỗi của TF-IDF, nên hiểu TF-IDF trước thì BM25 không còn là công thức phải nhớ.

Ba trực giác, ghép lại thành một công thức:

Ký hiệu	Ý	Cách tính
tf(t,d)	term xuất hiện nhiều lần trong tài liệu → tài liệu nói về nó	đếm
idf(t)	term xuất hiện ở ít tài liệu → phân biệt tốt hơn	ln(N/df)
chuẩn hoá độ dài	tài liệu dài không được thắng chỉ vì dài	chia cho độ dài vector

$$w(t,d) = \mathrm{tf}(t,d) \cdot \mathrm{idf}(t), \qquad \mathrm{idf}(t) = \ln\frac{N}{\mathrm{df}(t)}$$

Tính đầy đủ trên ba tài liệu

N = 3. Vẫn ba tài liệu ở 1.6:

id	nội dung
d1	đổi mật khẩu trong phần cài đặt
d2	khôi phục mật khẩu khi quên mật khẩu
d3	bật xác thực hai lớp

Truy vấn: quên mật khẩu.

Bước 1 — idf.

term	df	idf = ln(3/df)
quên	1	ln 3 = 1,099
mật	2	ln 1,5 = 0,406
khẩu	2	ln 1,5 = 0,406

Bước 2 — trọng số tf · idf.

term	q	d1	d2
quên	1 × 1,099 = 1,099	0	1 × 1,099 = 1,099
mật	0,406	1 × 0,406 = 0,406	2 × 0,406 = 0,811
khẩu	0,406	0,406	0,811

Bước 3 — tích vô hướng (chỉ term chung có đóng góp):

q · d1 = 0,406·0,406 + 0,406·0,406                = 0,329
q · d2 = 1,099·1,099 + 0,406·0,811 + 0,406·0,811  = 1,865

Bước 4 — độ dài vector. Tính trên mọi term của tài liệu, không chỉ term truy vấn:

‖q‖  = √(1,099² + 0,406² + 0,406²)                         = 1,239
‖d1‖ = √(5 × 1,099² + 2 × 0,406²)   ← 5 term chỉ có ở d1  = 2,523
‖d2‖ = √(4 × 1,099² + 2 × 0,811²)   ← 4 term chỉ có ở d2  = 2,479

Bước 5 — cosine.

	tích vô hướng	‖d‖	cosine
d1	0,329	2,523	0,329 / (1,239 × 2,523) = 0,105
d2	1,865	2,479	1,865 / (1,239 × 2,479) = 0,607
d3	0	—	0

Ranking: d2 ≫ d1 ≫ d3 — đúng trực giác, d2 là tài liệu về việc quên mật khẩu.

Đọc thêm

• [EN] IR Book ch.6 — Scoring, term weighting and the vector space model — vector space model đầy đủ, kèm các biến thể chuẩn hoá
• [EN] IR Book §6.2.1 — Inverse document frequency — vì sao IDF là log, không phải nghịch đảo
• [VI] Full text search từ khái niệm đến thực tiễn (phần 4) — ktmt — TF-IDF bằng tiếng Việt, có ví dụ tính tay

Ba điều bảng trên vừa dạy

1. Chuẩn hoá là bắt buộc. Bỏ bước 4, chỉ dùng tích vô hướng, thì mọi tài liệu dài đều leo lên đầu chỉ vì chứa nhiều term hơn.
2. quên gánh gần hết điểm — 1,207 trong 1,865 của d2. Term hiếm mang thông tin, term phổ biến gần như miễn phí. Đây là idf làm việc, và là lý do không cần bỏ stopword khi đã có idf.
3. d3 không bao giờ được chạm tới — nó không nằm trong postings của cả ba term. Lợi thế cấu trúc của inverted index.

Vì sao TF-IDF bị BM25 thay

Khiếm khuyết của TF-IDF	BM25 sửa thế nào
tf tuyến tính: nhắc 20 lần = 20× liên quan	bão hoà tf·(k1+1)/(tf + k1·…) — có tiệm cận
Chuẩn hoá độ dài cứng (cosine), không xoay được	tham số b: 0 = mặc độ dài, 1 = chuẩn hoá tối đa
ln(N/df) xử lý kém khi df gần N	ln(1 + (N−df+0,5)/(df+0,5)) mượt ở hai đầu

Đo thực tế trên golden set của cẩm nang: đổi TF-IDF → BM25 được +1,2%, còn sửa tokenizer được +20,8%. Thứ tự ưu tiên nằm ở đó — không nằm ở công thức ranking.

Ba dòng trong bảng trên là mô tả chỗ BM25 khác TF-IDF. Còn vì sao nó khác đúng ở ba chỗ đó — bão hoà từ đâu ra, 0.5 trong idf là gì, khi nào idf âm — thì ở 3.4b.

Đọc thêm

• [EN] Practical BM25 — thuật toán và các biến của nó — Elastic — từ TF-IDF sang BM25: sửa đúng hai chỗ nào
• [VI] BM25 — thuật toán xếp hạng văn bản theo độ phù hợp — Viblo — BM25 giải thích từng số hạng