ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← RAG & Agents

AI Builder

BM25 - Xếp hạng từ khoá kinh điển

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Thuật toán xếp hạng văn bản dựa trên tần suất từ khóa, là nền tảng của các công cụ tìm kiếm truyền thống.

lesson94 minRAG & AgentsAI Engineer

Dự đoán

Bạn tìm 'luật lao động 2025' trên VnExpress. Bài nào nên xếp trên? Bài A nhắc 'luật lao động' 5 lần (200 từ) hay bài B nhắc 3 lần (5000 từ)?

BM25 xét 3 yếu tố: tần suất từ (TF), độ hiếm của từ (IDF), và chuẩn hoá theo độ dài. Bài A có mật độ cao hơn (2.5% vs 0.06%) nên xếp trên!

Khám phá

Tham sốÝ nghĩaKhoảng thường dùngTác dụng
k1Bão hoà TF: từ lặp nhiều lần tăng điểm đến đâu1,2–2,0k1 thấp → bão hoà sớm; 3 lần gần bằng 10 lần
bChuẩn hoá độ dài0–1 (mặc định 0,75)b = 1 phạt doc dài nặng; b = 0 bỏ qua độ dài
Bạn muốn từ lặp nhiều lần không được cộng quá nhiều điểm. Nên chỉnh tham số nào?

Thử tay trên công thức: khi b = 0, độ dài không bị phạt nên doc dài có điểm cao hơn; khi k1 = 1,2, từ lặp nhiều lần không còn được cộng nhiều. BM25 là TF-IDF có điều chỉnh.

Khoảnh khắc Aha

BM25 giống chấm bài thi tự luận: đếm số lần nhắc đến chủ đề (TF), coi trọng thuật ngữ chuyên ngành hơn từ phổ biến (IDF), và không thiên vị bài dài (length norm). Là hậu duệ trực tiếp của TF-IDF, BM25 vẫn là baseline cực mạnh mà nhiều hệ thống semantic search hiện đại cũng khó thắng ở bài toán khớp chính xác, nên cả hai thường được kết hợp trong hybrid search.

Điểm "aha": k1k_1 không phải con số ma thuật — nó là cách bạn nói với hệ thống "tôi muốn nhấn mạnh từ lặp nhiều lần bao nhiêu". bb cũng vậy — "tôi muốn phạt doc dài bao nhiêu". Hai núm vặn, hai câu hỏi ngôn ngữ tự nhiên, một công thức đẹp.

Thử thách

Người dùng tìm 'thú cưng đáng yêu' nhưng tài liệu viết 'chó mèo dễ thương'. BM25 tìm được không?

BM25 là lexical search — chỉ khớp chính xác chuỗi ký tự. Không hiểu đồng nghĩa, viết tắt, hay ngữ cảnh. Đây là lý do cần Semantic Search bổ sung, tạo thành Hybrid Search!

Bạn tune BM25 cho corpus sản phẩm e-commerce với mô tả dài 200-2000 từ. Seller hay nhồi keyword ('áo thun áo thun áo thun...'). Nên chỉnh k1 và b thế nào?

Khi có keyword stuffing, bạn muốn TF bão hoà nhanh → giảm k1 xuống 1.0-1.2. Nếu doc dài có lý do chính đáng (mô tả chi tiết sản phẩm), giảm b xuống 0.5-0.6 để không phạt quá mức. Luôn A/B test trên queries thật.

Lý thuyết

BM25 (Best Matching 25) là thuật toán xếp hạng kinh điển trong Information Retrieval, nền tảng của Elasticsearch, Solr, Lucene, OpenSearch và nhiều search engine. Được Stephen Robertson và Karen Spärck Jones phát triển ở Cambridge từ những năm 1970-1990, BM25 đến nay vẫn là strong baseline mà mọi retrieval system mới đều phải so sánh.

Công thức BM25 đầy đủ:

score(D,Q)=∑i=1nIDF(qi)⋅f(qi,D)⋅(k1+1)f(qi,D)+k1⋅(1−b+b⋅∣D∣avgdl)\text{score}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}

Công thức IDF (Okapi variant):

IDF(qi)=ln⁡(N−n(qi)+0.5n(qi)+0.5+1)\text{IDF}(q_i) = \ln\left(\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1\right)

Trong đó: f(qi,D)f(q_i, D) = tần suất từ qiq_i trong tài liệu DD; n(qi)n(q_i) = số tài liệu chứa qiq_i; NN = tổng số tài liệu; ∣D∣|D| = độ dài tài liệu; avgdl\text{avgdl} = độ dài trung bình. k1k_1 thường trong khoảng 1.2-2.0; bb trong khoảng 0-1, mặc định 0.75.

Hiểu từng phần của công thức:

  • Tử số f(qi,D)⋅(k1+1)f(q_i, D) \cdot (k_1 + 1): tăng tuyến tính theo TF, nhân với hằng số để scale.
  • Mẫu số f(qi,D)+k1⋅(1−b+b⋅∣D∣/avgdl)f(q_i, D) + k_1 \cdot (1 - b + b \cdot |D|/\text{avgdl}): khi TF tăng, mẫu cũng tăng → phần TF bão hoà. ∣D∣/avgdl|D|/\text{avgdl} đưa thông tin độ dài vào, nhân với bb để kiểm soát mức ảnh hưởng.
  • Khi b=0b = 0: length không ảnh hưởng → giống Robertson-TF cổ điển.
  • Khi b=1b = 1: length phạt tối đa, doc dài gấp đôi trung bình bị phạt nặng.
  • Khi k1→∞k_1 \to \infty: TF gần tuyến tính, giống TF-IDF cổ điển.
  • Khi k1=0k_1 = 0: chỉ dùng IDF (có hay không có từ, không quan tâm tần suất).

So sánh chi tiết TF-IDF vs BM25 — bảng cheat sheet:

Tiêu chíTF-IDF (cổ điển)BM25 (Okapi)
Công thức TF1+log⁡(tf)1 + \log(\text{tf}) hoặc tf\text{tf}tf⋅(k1+1)tf+k1(… )\frac{\text{tf} \cdot (k_1+1)}{\text{tf} + k_1(\dots)}
Bão hoà TFKhông (hoặc log rất nhẹ)Có — kiểm soát bằng k1k_1
Length normKhông, hoặc cosine sau chuẩn hoáCó — kiểm soát bằng bb
IDF smoothingKhông — log⁡(N/df)\log(N/\text{df}) có thể âmCó — +0.5+0.5 smoothing Robertson-SJ
Parameters tune0 (không có)2 (k1,bk_1, b) — tune được
Probabilistic foundationHeuristicCó — Probabilistic Relevance Model
Benchmark winsBaseline cũ+5-20% nDCG@10 trên TREC/BEIR

Một cách đơn giản để nhớ: BM25 = TF-IDF sau khi đi học về xác suất. Robertson và nhóm Cambridge đã chính thức hoá TF-IDF trong khung Probabilistic Relevance Framework, và mỗi "hack" của BM25 (saturation, length norm, IDF smoothing) đều có giải thích toán học — không phải magic number.

Ví dụ code

BM25 với rank_bm25 — ví dụ đầy đủ

from rank_bm25 import BM25Okapi
import numpy as np

# 1. Tokenize corpus — quan trọng: lowercase, loại stopwords nếu cần
corpus_raw = [
    "Luật lao động Việt Nam quy định quyền người lao động.",
    "Bộ luật lao động mới đã cập nhật điều khoản lương tối thiểu vùng.",
    "Luật lao động bảo vệ quyền lợi chính đáng của người lao động.",
    "Luật giao thông đường bộ quy định về tốc độ tối đa.",
    "Quyền và nghĩa vụ người lao động theo quy định của pháp luật.",
]
corpus = [doc.lower().split() for doc in corpus_raw]

# 2. Tạo BM25 index
#    rank_bm25 mặc định: k1=1.5, b=0.75, epsilon=0.25
bm25 = BM25Okapi(corpus, k1=1.5, b=0.75)

# 3. Tìm kiếm
query = "quyền người lao động".lower().split()
scores = bm25.get_scores(query)
print("Raw scores:", scores)
# → [array of 5 floats]

# 4. Top-K kết quả
top_k = 3
top_indices = np.argsort(scores)[::-1][:top_k]
for rank, idx in enumerate(top_indices, 1):
    print(f"#{rank} score={scores[idx]:.3f} → {corpus_raw[idx]}")

# 5. Nếu cần xếp hạng doc mới không có trong index:
new_docs = [
    "Quy định pháp luật bảo vệ quyền người lao động.".lower().split(),
    "Cách nấu phở bò theo công thức truyền thống.".lower().split(),
]
new_scores = bm25.get_batch_scores(query, new_docs)
# Chú ý: get_batch_scores reuse IDF từ index gốc.
# Muốn IDF tính lại với corpus mới → tạo BM25Okapi mới.

# 6. Variant BM25L (cho doc rất dài/ngắn)
from rank_bm25 import BM25L
bm25_l = BM25L(corpus, k1=1.5, b=0.75, delta=0.5)
# BM25L thêm parameter delta để tránh over-penalize doc dài.

# 7. Variant BM25Plus (Lv & Zhai 2011)
from rank_bm25 import BM25Plus
bm25_plus = BM25Plus(corpus, k1=1.5, b=0.75, delta=1.0)
# BM25Plus sửa lỗi "unfair" với doc dài ở TF thấp.

BM25 trong Elasticsearch + Hybrid Search với embedding

# Elasticsearch dùng BM25 làm default similarity từ ES 5.0+
# Mọi query "match" chạy BM25 dưới nền.

from elasticsearch import Elasticsearch
es = Elasticsearch("http://localhost:9200")

# 1. Tạo index với custom BM25 params
es.indices.create(
    index="vnexpress",
    body={
        "settings": {
            "index": {
                "similarity": {
                    "custom_bm25": {
                        "type": "BM25",
                        "k1": 1.2,   # bão hoà TF
                        "b": 0.75,   # length norm
                    }
                }
            }
        },
        "mappings": {
            "properties": {
                "title": {
                    "type": "text",
                    "similarity": "custom_bm25",
                    "analyzer": "vietnamese",
                },
                "body": {
                    "type": "text",
                    "similarity": "custom_bm25",
                    "analyzer": "vietnamese",
                },
                "embedding": {
                    "type": "dense_vector",
                    "dims": 768,
                    "index": True,
                    "similarity": "cosine",
                },
            }
        },
    },
)

# 2. Hybrid Search: BM25 + vector với RRF
def hybrid_search(query_text: str, query_embedding: list[float], k: int = 10):
    response = es.search(
        index="vnexpress",
        body={
            "size": k,
            "query": {
                "bool": {
                    "should": [
                        # BM25 branch
                        {
                            "multi_match": {
                                "query": query_text,
                                "fields": ["title^3", "body"],  # title boost 3x
                                "type": "best_fields",
                            }
                        },
                        # Vector branch
                        {
                            "knn": {
                                "field": "embedding",
                                "query_vector": query_embedding,
                                "k": k * 2,
                                "num_candidates": 200,
                            }
                        },
                    ]
                }
            },
        },
    )
    return response["hits"]["hits"]

# 3. Reciprocal Rank Fusion (RRF) nếu muốn fuse thủ công
def rrf_fuse(bm25_results, vector_results, k: int = 60):
    """
    RRF score(d) = Σ 1/(k + rank_i(d))
    Ít sensitive với raw score scale → tốt cho hybrid.
    """
    scores = {}
    for rank, hit in enumerate(bm25_results):
        doc_id = hit["_id"]
        scores[doc_id] = scores.get(doc_id, 0) + 1 / (k + rank + 1)
    for rank, hit in enumerate(vector_results):
        doc_id = hit["_id"]
        scores[doc_id] = scores.get(doc_id, 0) + 1 / (k + rank + 1)
    return sorted(scores.items(), key=lambda x: -x[1])

Các variant của BM25

BM25 có nhiều họ hàng đã được đề xuất để khắc phục các khiếm khuyết nhỏ. Biết chúng giúp bạn chọn đúng cho use case:

  • BM25 Okapi: phiên bản gốc, mặc định của Elasticsearch/Lucene.
  • BM25L (Lv & Zhai 2011): thêm hằng số δ\delta để tránh phạt quá mức doc dài. Dùng khi corpus có phân phối độ dài rất lệch.
  • BM25+: thêm δ\delta vào phần TF để sửa lỗi "unfair" với doc dài tại TF thấp.
  • BM25F: mở rộng cho doc có nhiều field với weight khác nhau.
  • BM25T: dùng term-specific k1k_1 — mỗi từ có k1k_1 riêng, tune từ data.
  • BM25-adpt: adaptive k1 theo document length — hiếm khi cần trong thực tế.

Thực tế: 95% use case (ước lượng theo nguồn bài, chưa kiểm chứng) dùng BM25 Okapi mặc định là đủ tốt. Chỉ nghĩ đến variant khác khi bạn đã có evaluation pipeline chặt chẽ và thấy BM25 baseline fail ở pattern cụ thể.

Chi tiết về BM25F (multi-field scoring):

Document thực tế hầu như không bao giờ là "một khối văn bản đồng nhất". Bài báo có title, body, tags, author; sản phẩm có name, description, specs, reviews. Mỗi field có độ dài khác nhau, mức độ quan trọng khác nhau. Nếu dùng BM25 phẳng (ghép tất cả thành một chuỗi), match trong title bị "pha loãng" bởi body dài.

Công thức BM25F (đơn giản hoá):

f~(q,D)=∑c∈fieldswc⋅f(q,Dc)1−bc+bc⋅∣Dc∣/avgdlc\tilde{f}(q, D) = \sum_{c \in \text{fields}} w_c \cdot \frac{f(q, D_c)}{1 - b_c + b_c \cdot |D_c|/\text{avgdl}_c}
BM25F(q,D)=∑qi∈QIDF(qi)⋅f~(qi,D)⋅(k1+1)f~(qi,D)+k1\text{BM25F}(q, D) = \sum_{q_i \in Q} \text{IDF}(q_i) \cdot \frac{\tilde{f}(q_i, D) \cdot (k_1+1)}{\tilde{f}(q_i, D) + k_1}

Điểm quan trọng: length normalization và weighting xảy ra TRƯỚC bão hoà. Nếu bão hoà từng field riêng rồi cộng, match 5 lần ở title sẽ không khác 1 lần ở title + 4 lần ở body — sai. BM25F gộp "pseudo-TF" có trọng số trước, rồi mới bão hoà một lần.

Tune trong thực tế: title thường có wc=3−5w_c = 3-5, body wc=1w_c = 1, tags wc=2w_c = 2. Elasticsearch expose qua multi_match với fields: ["title^3", "body"] — số sau ^ là boost tương đương wcw_c.

Chi tiết về BM25+ (Lv & Zhai 2011):

Quan sát của Lv & Zhai: BM25 Okapi phạt quá mức các doc dài có TF thấp. Ví dụ một bài luận 2000 từ có 1 lần nhắc "BM25" vẫn có thể relevant cao, nhưng BM25 chuẩn cho điểm gần như 0. Họ đề xuất thêm hằng số δ\delta (thường ~1.0):

BM25+(qi,D)=IDF(qi)⋅[f(qi,D)⋅(k1+1)f(qi,D)+k1(1−b+b∣D∣/avgdl)+δ]\text{BM25+}(q_i, D) = \text{IDF}(q_i) \cdot \left[\frac{f(q_i, D) \cdot (k_1+1)}{f(q_i, D) + k_1(1 - b + b|D|/\text{avgdl})} + \delta\right]

δ\delta là một "hằng số công bằng" đảm bảo doc chứa từ query luôn có điểm tối thiểu dương. Trên TREC robust track, BM25+ cho +2-3% MAP (theo nguồn bài, chưa kiểm chứng) vs BM25 — không khổng lồ nhưng ổn định.

Khi nào dùng BM25+? Corpus có doc rất dài (>5000 từ) và bạn muốn recall cao hơn — news articles, research papers, legal documents. Với e-commerce descriptions ngắn, BM25+ không khác biệt rõ.

Chi tiết về BM25L (Lv & Zhai 2011):

BM25L thay biến "TF chuẩn hoá độ dài" bằng một biến có shift δ\delta để giảm phạt doc dài ở TF cao. Khác với BM25+ (shift điểm cuối), BM25L shift biến trung gian trong công thức TF. Hiệu quả tương tự, khác nhau ở chỗ curve nào bị ảnh hưởng nhiều hơn. Thực tế: chọn BM25+ vì đơn giản hơn, dễ implement.

Proximity và phrase matching

BM25 gốc là bag-of-words: "machine learning" khớp với doc chứa "machine" ở đầu và "learning" ở cuối (cách 500 từ) y như với doc có hai từ đó cạnh nhau. Thực tế proximity mang tín hiệu relevance mạnh. Các mở rộng:

  • Phrase query: đóng query trong dấu nháy "machine learning" → chỉ match khi hai từ liền kề. Lucene dùng positional inverted index.
  • Sloppy phrase: cho phép khoảng cách ≤k\leq k từ giữa hai term. Elasticsearch: match_phrase với slop: 3.
  • BM25 + proximity bonus: cộng một bonus vào điểm BM25 nếu các query term xuất hiện gần nhau. Công thức: score=BM25(Q,D)+λ⋅prox(Q,D)\text{score} = \text{BM25}(Q, D) + \lambda \cdot \text{prox}(Q, D), thường λ=0.1−0.3\lambda = 0.1-0.3.
  • Span queries (Lucene): specify pattern phức tạp (A gần B, không có C ở giữa). Dùng cho legal search, biomedical.

Đánh đổi: proximity tính toán chậm hơn (cần positional postings), index lớn hơn 2-3 lần. Với corpus <10M docs, chấp nhận được; với web-scale thì phải cân nhắc.

Tokenization tiếng Việt cho BM25

BM25 phụ thuộc cực lớn vào tokenizer. Tiếng Việt có đặc điểm: dấu cách giữa tiếng ("lao động" là 1 khái niệm nhưng 2 token nếu tách theo space). Nếu tokenize sai, BM25 không khớp được.

Các lựa chọn:

  • Whitespace tokenize: đơn giản nhưng "lao động" thành 2 token — query "luật lao động" vẫn match nhưng không "hiểu" cụm.
  • Word segmentation (underthesea, pyvi): tách theo ranh giới từ tiếng Việt thực — "lao_động" thành 1 token. Match chính xác hơn.
  • Character n-gram: fallback khi không có tokenizer — bắt được cả từ viết sai chính tả.
  • Elasticsearch analyzer: dùng vi_analyzer hoặc plugin elasticsearch-analysis-vietnamese.

Lời khuyên: luôn đo tokenization quality trước khi tune BM25. Một tokenizer tốt thường cải thiện nDCG hơn nhiều so với tune k1/b.

BM25 trong thực tế

BM25 trong thực tế production: không phải ai cũng viết BM25 từ đầu. Các hệ thống phổ biến:

  • Elasticsearch / OpenSearch: default similarity, tune qua settings.
  • Lucene / Solr: cùng nhân, API thấp hơn.
  • Tantivy (Rust): nhân tìm kiếm nhanh hơn Lucene ~2x (theo nguồn bài, chưa kiểm chứng), cũng BM25 default.
  • MeiliSearch / Typesense: BM25 kết hợp typo tolerance.
  • rank_bm25 (Python): thư viện nhẹ cho prototype/research.
  • BM25S (Python, 2024): implementation với sparse matrix, nhanh hơn rank_bm25 10-100x (theo nguồn bài, chưa kiểm chứng), phù hợp corpus lớn.
  • Vespa / Qdrant / Weaviate: vector DB hiện đại cũng tích hợp BM25 để làm hybrid search.

BM25S — implementation cực nhanh với sparse matrix (2024)

# BM25S (Lu 2024) — reimagine BM25 dùng scipy.sparse
# GitHub: xhluca/bm25s — nhanh hơn rank_bm25 10-100x trên corpus lớn.
# Ý tưởng chính: precompute IDF × (k1+1) / (TF + k1·len-norm) dưới dạng
# sparse CSR matrix, query thành nhân vector sparse—sparse (cực nhanh).

import bm25s
import Stemmer  # optional — giảm số token độc nhất

# 1. Dataset
corpus = [
    "Luật lao động Việt Nam quy định quyền người lao động",
    "Bộ luật lao động mới cập nhật lương tối thiểu vùng",
    "Luật giao thông quy định tốc độ tối đa ô tô xe máy",
    "Quyền và nghĩa vụ người lao động theo pháp luật Việt Nam",
    "Hướng dẫn cách nấu phở bò truyền thống Hà Nội",
]

# 2. Tokenize với optional stemmer (tiếng Anh). Tiếng Việt: custom tokenizer.
stemmer = Stemmer.Stemmer("english")  # None cho tiếng Việt
corpus_tokens = bm25s.tokenize(corpus, stopwords="en", stemmer=stemmer)

# 3. Index — tạo sparse matrix, tính sẵn IDF
retriever = bm25s.BM25(k1=1.5, b=0.75)
retriever.index(corpus_tokens)

# 4. Query — nhanh hơn rank_bm25 ở batch mode
query = "quyền người lao động"
query_tokens = bm25s.tokenize(query, stemmer=stemmer)

# Top-K với scores
results, scores = retriever.retrieve(query_tokens, k=3)
for i, (idx, score) in enumerate(zip(results[0], scores[0])):
    print(f"#{i+1} score={score:.3f} → {corpus[idx]}")

# 5. Save / Load index — chỉ một thư mục sparse files
retriever.save("bm25s_index")
retriever = bm25s.BM25.load("bm25s_index")

# 6. Batch query — nhanh nhất khi bạn có 1000+ queries
queries = ["lương tối thiểu", "phở bò", "giao thông đường bộ"]
query_tokens_batch = bm25s.tokenize(queries, stemmer=stemmer)
results_batch, scores_batch = retriever.retrieve(query_tokens_batch, k=2)

# So sánh benchmark (từ paper BM25S):
# | Library    | 1M docs, 1k queries | speedup |
# | rank_bm25  | 120s                | 1x      |
# | BM25S      | 1.3s                | ~90x    |
# | PISA (C++) | 0.8s                | ~150x   |
#
# BM25S cân bằng tốt giữa ease-of-use (pure Python) và speed.

Lịch sử ngắn: BM25 là kết tinh từ dòng nghiên cứu Probabilistic Retrieval Model của Stephen Robertson, Karen Spärck Jones và team Cambridge/City University. "BM" là viết tắt của "Best Matching" — số 25 là phiên bản thứ 25 trong chuỗi thử nghiệm. Phiên bản này "may mắn" vừa đơn giản, vừa robust, vừa có parameter tune được → trở thành chuẩn de-facto trong 30 năm.

Bài học: đôi khi thuật toán tốt nhất không phải thuật toán mới nhất. BM25 vẫn là strong baseline mà LLM-era retrieval vẫn phải kính nể. Học BM25 kỹ là đầu tư có lãi suốt sự nghiệp.

Tóm tắt

  • BM25 = TF (tần suất, bão hoà) × IDF (độ hiếm) × Length Normalization (chuẩn hoá độ dài).
  • Parameter k1 kiểm soát bão hoà TF (1.2-2.0), b kiểm soát phạt theo độ dài (0-1, mặc định 0.75).
  • IDF của BM25 dùng công thức Okapi ln((N-df+0.5)/(df+0.5)+1) — an toàn với df lớn, không âm.
  • Giỏi khớp chính xác: tên riêng, mã sản phẩm, thuật ngữ. Yếu: đồng nghĩa, paraphrase, ngữ cảnh.
  • Vẫn là baseline mạnh, kết hợp semantic search trong Hybrid Search là chuẩn hiện đại.
  • Biến thể (BM25F, BM25L, BM25+, BM25T) giải quyết case đặc biệt; mặc định BM25 Okapi đủ tốt cho 95% tình huống.

Continue the module

Lesson 10 of 16