Tìm hiểu thuật toán tìm kiếm toàn văn BM25
(emschwartz.me)- BM25 vẫn được sử dụng rộng rãi trong tìm kiếm toàn văn khi cần khớp từ khóa chính xác, và trở thành một trụ cột của tìm kiếm lai bổ trợ cho tìm kiếm độ tương đồng vector
- Để xếp hạng tài liệu mà không cần tính trực tiếp xác suất, BM25 cộng trọng số theo từng hạng mục truy vấn và đưa các tài liệu có vẻ liên quan hơn lên trước
- Điểm số được chia thành IDF, tần suất thuật ngữ trong tài liệu và chuẩn hóa độ dài tài liệu; từ hiếm được phản ánh mạnh hơn, còn các lần xuất hiện lặp lại được thưởng ít dần
k1điều chỉnh tốc độ giảm dần của phần thưởng cho xuất hiện lặp lại, cònbđiều chỉnh cường độ chuẩn hóa độ dài tài liệu; thông thường dùngk1=1.2~2,b=0.75- Điểm BM25 không phải là xác suất liên quan thực tế nên khó dùng như một giá trị so sánh phổ quát; nó có ý nghĩa khi so sánh trong cùng một tập tài liệu
Bài toán tìm kiếm mà BM25 muốn giải quyết
- BM25, hay Best Match 25, là một thuật toán được dùng rộng rãi trong tìm kiếm toàn văn
- Được dùng làm mặc định trong Lucene/Elasticsearch, SQLite, v.v.
- Gần đây, tìm kiếm lai kết hợp tìm kiếm toàn văn và tìm kiếm độ tương đồng vector đã trở nên phổ biến
- Trong feed nội dung cá nhân hóa, chỉ tìm kiếm độ tương đồng vector có thể không xử lý đủ chính xác từ khóa
- Nếu mối quan tâm là
Solid.js, khi chỉ dùng tìm kiếm độ tương đồng vector, nội dung liên quan đến React có thể xuất hiện nhiều hơn Solid
- Nếu mối quan tâm là
- Câu hỏi cốt lõi là liệu có thể so sánh điểm BM25 của một tài liệu giữa nhiều truy vấn để xác định tài liệu đó phù hợp nhất với truy vấn nào hay không
Nguyên lý xếp hạng theo xác suất và cách tiếp cận của BM25
- Mục tiêu của tìm kiếm toàn văn là tìm tài liệu liên quan nhất trong tập tài liệu có thể có dựa trên truy vấn
- Vì không thể biết chắc mức độ liên quan thực tế, tìm kiếm cố gắng sắp xếp theo xác suất tài liệu có liên quan đến truy vấn
- Ý tưởng này được gọi là Probability Ranking Principle
- Tìm kiếm dựa trên từ vựng như BM25 chỉ sử dụng truy vấn và các đặc tính của tài liệu trong tập tài liệu
- Tìm kiếm độ tương đồng vector có thể dùng mô hình embedding được huấn luyện trên kho văn bản bên ngoài để biểu diễn ý nghĩa của truy vấn và tài liệu
Các thành phần tạo nên điểm BM25
- BM25 tính điểm bằng cách kết hợp nhiều tín hiệu từ truy vấn và tập tài liệu
-
Hạng mục truy vấn
- Nếu truy vấn tìm kiếm gồm nhiều thuật ngữ, điểm cho từng thuật ngữ được tính rồi cộng lại
-
Tần suất tài liệu nghịch đảo (IDF)
- Biểu thị một từ khóa tìm kiếm cụ thể hiếm đến mức nào trong toàn bộ tập tài liệu
- Các từ phổ biến như
the,andđược xem là có lượng thông tin thấp, còn từ hiếm được tăng mức độ quan trọng
-
Tần suất thuật ngữ trong tài liệu
- Phản ánh số lần từ khóa tìm kiếm xuất hiện trong một tài liệu cụ thể
- Khi cùng một thuật ngữ lặp lại nhiều hơn, khả năng liên quan được xem là cao hơn, nhưng BM25 áp dụng hiệu ứng giảm dần cho các lần xuất hiện lặp lại
-
Độ dài tài liệu
- Tài liệu dài có thể chứa từ khóa tìm kiếm nhiều hơn chỉ vì nó dài
- BM25 so sánh độ dài tài liệu với độ dài tài liệu trung bình để chuẩn hóa, tránh việc tài liệu dài nhận điểm cao một cách không công bằng
Từng phần trong công thức BM25
- Điểm tổng thể của BM25 đối với tài liệu
Dvà truy vấnQđược tính bằng cách cộng điểm của từng hạng mục truy vấnq_iD: tài liệu mục tiêuQ: toàn bộ truy vấnn: số hạng mục truy vấnq_i: từng hạng mục truy vấn
-
IDF: phản ánh mạnh hơn các từ hiếm trong tập tài liệu
- Thành phần IDF tính mức độ hiếm của hạng mục truy vấn trong toàn bộ tập tài liệu
N: tổng số tài liệu trong tậpn(q_i): số tài liệu chứa hạng mục truy vấnN - n(q_i): số tài liệu không chứa hạng mục truy vấn- Thuật ngữ phổ biến xuất hiện trong nhiều tài liệu nên ảnh hưởng đến điểm số sẽ nhỏ hơn
- Thuật ngữ hiếm chỉ xuất hiện trong ít tài liệu nên được phản ánh mạnh hơn vào điểm số
0.5và1trong công thức có vai trò làm dịu để kết quả không dao động quá lớn khi thuật ngữ cực kỳ hiếm hoặc cực kỳ phổ biến
-
Tần suất thuật ngữ: phản ánh lặp lại nhưng không thưởng vô hạn
- Tần suất thuật ngữ trong tài liệu phản ánh một hạng mục truy vấn cụ thể xuất hiện thường xuyên đến mức nào trong một tài liệu cụ thể
f(q_i, D): tần suất hạng mục truy vấnq_ixuất hiện trong tài liệuDk1: tham số tinh chỉnh thường được đặt trong khoảng từ1.2đến2- BM25 phản ánh việc lặp lại thuật ngữ vào điểm số, nhưng khi số lần lặp tăng lên, mức tăng điểm bổ sung sẽ giảm dần
k1kiểm soát phần thưởng cho việc lặp lại thuật ngữ giảm nhanh đến mức nào
-
Chuẩn hóa độ dài tài liệu: điều chỉnh lợi thế của tài liệu dài
- Chuẩn hóa độ dài tài liệu so sánh độ dài của tài liệu mục tiêu với độ dài tài liệu trung bình của tập
|D|: độ dài của tài liệu mục tiêuavgdl: độ dài tài liệu trung bình của tậpb: tham số tinh chỉnh kiểm soát cường độ chuẩn hóa độ dài tài liệu- Tài liệu dài hơn trung bình có khả năng chứa từ khóa tìm kiếm thường xuyên hơn, nên bị bất lợi ở mẫu số của công thức cuối cùng
- Nếu
b=0, chuẩn hóa độ dài tài liệu bị tắt; nếub=1, nó được áp dụng hoàn toàn bthường được đặt là0.75
Ý tưởng cốt lõi của BM25
- BM25 dựa trên Probability Ranking Principle, nhưng gần như không thể tính xác suất thật về mức độ liên quan của tài liệu
- Trong tìm kiếm, điều quan trọng là thứ tự của tài liệu hơn là giá trị xác suất chính xác, vì vậy các thành phần không ảnh hưởng đến thứ tự được loại khỏi công thức để việc tính toán trở nên thực dụng
- Vì lý do này, BM25 tính trọng số chứ không phải bản thân xác suất
- Robertson/Sparck Jones Weight là cách ước lượng xác suất bằng cách dùng số tài liệu liên quan và số tài liệu chứa hạng mục truy vấn
r: số tài liệu liên quan chứa hạng mục truy vấnN: tổng số tài liệu trong tậpR: số tài liệu liên quan trong tậpn: số tài liệu chứa hạng mục truy vấn
- Hạn chế lớn của cách này là trước tiên phải biết tài liệu nào liên quan
Giả định “phần lớn tài liệu không liên quan”
- Các nhà phát triển BM25 giả định rằng với một truy vấn bất kỳ, phần lớn tài liệu không liên quan
- Nếu xem số tài liệu liên quan nhỏ đến mức có thể bỏ qua, có thể đặt
R = r = 0 - Khi thay giá trị này vào công thức Robertson/Sparck Jones Weight, ta thu được dạng gần như giống với thành phần IDF dùng trong BM25
- Vì không yêu cầu trước thông tin về mức độ liên quan mà vẫn giữ cùng nền tảng lý thuyết, BM25 trở nên thực tế hơn nhiều
- Victor Lavrenko mô tả điều này là "very impressive leap of faith"
Phạm vi so sánh điểm BM25
- Nhìn chung, điểm BM25 khó so sánh trực tiếp
- Nó không tạo ra điểm xác suất nằm trong khoảng từ 0 đến 1
- Đây cũng không phải thuật toán nhằm ước lượng xác suất thực tế rằng tài liệu có liên quan
- Nó tập trung vào việc xấp xỉ thứ tự khả năng liên quan đối với truy vấn trong một tập tài liệu cụ thể
- Điểm BM25 cao hơn là tín hiệu cho thấy tài liệu có khả năng liên quan hơn, nhưng không phải xác suất liên quan thực tế
- Với cùng một tài liệu trong cùng một tập tài liệu, có thể so sánh điểm BM25 của nhiều truy vấn
- Vì BM25 cộng điểm của từng hạng mục truy vấn, có thể xem là không có khác biệt về mặt ý nghĩa giữa việc so sánh điểm của hai hạng mục truy vấn và so sánh điểm của hai truy vấn đầy đủ
- Ràng buộc quan trọng là cùng tài liệu, cùng tập tài liệu
- BM25 sử dụng IDF và độ dài tài liệu trung bình trong tập
- Nếu tập tài liệu thay đổi, điểm số có thể thay đổi, nên không đảm bảo việc so sánh điểm theo thời gian
- Trong feed nội dung cá nhân hóa, có thể chạy tìm kiếm toàn văn cho từng mối quan tâm của người dùng và so sánh điểm BM25 để xác định nội dung nào phù hợp hơn với mối quan tâm nào
Tài liệu đọc thêm
- Nếu muốn đi sâu hơn vào lý thuyết và lịch sử của BM25, có thể xem bài thuyết trình năm 2016 của Britta Weber, kỹ sư Elastic, Improved Text Scoring with BM25
- The Probabilistic Relevance Framework: BM25 and Beyond của Stephen Robertson và Hugo Zaragoza đề cập đến framework liên quan xác suất của BM25
- Có thể xem phần so sánh BM25 với các thuật toán tìm kiếm toàn văn khác tại Comparing full text search algorithms: BM25, TF-IDF, and Postgres
1 bình luận
Các ý kiến trên Hacker News
Tôi đang dùng https://typesense.org/ cho tìm kiếm thông thường, giờ nó cũng hỗ trợ tìm kiếm lai, nên tò mò không biết đã có ai dùng thử chưa
Rất vui khi thấy Typesense được nhắc đến ở đây; với các dự án RAG quy mô nhỏ thì thường rất phù hợp, nhưng kỳ lạ là nó lại ít được biết đến
Dễ triển khai, các giá trị mặc định hợp lý, tài liệu tốt, clustering cũng khá dễ; và khi cần đào sâu hơn thì hiệu năng vẫn tốt và đủ mạnh
Tuy nhiên nếu dùng mô hình embedding từ nhà cung cấp bên ngoài thì độ trễ 500ms+ cao đến vô lý, nên tốt hơn là tự host trong cluster
Chất lượng tìm kiếm lai tốt, nhưng tùy chọn tinh chỉnh rất hạn chế, và điểm số cũng khá mù mờ ngoài việc xếp hạng bên trong tập kết quả
Trong bối cảnh tìm kiếm ngữ nghĩa dựa trên vector gần đây đã phát triển, tôi tò mò stack tìm kiếm hiện đại nào đang được dùng cho kiểu lai giữa từ khóa + tìm kiếm ngữ nghĩa
Gần đây tôi nhận khoảng 3 triệu khảo sát, mỗi khảo sát có khoảng 10 trường mô tả tự do, và phải tìm ra những mục mà công ty nên hành động
Dùng vài mô hình phân loại nhỏ, rồi sau khi xem nhiễu xuất hiện trong 10.000 bản ghi đầu tiên và loại thủ công các từ phổ biến, sau đó gán trọng số cho phản hồi của mô hình, thì nó hoạt động gần như hoàn hảo
Việc này không giống “lập trình” cho lắm, mà gần với việc điều chỉnh đầu ra hộp đen của nhiều công cụ cho đến khi trông ổn với test case và khách hàng
Nhân tiện, tôi đã xử lý bằng Node.js trên một server nhỏ, nối nhiều mô hình nhỏ của Hugging Face lại với nhau
Kết quả thường được hợp nhất bằng Reciprocal Rank Fusion (RRF)
Bài báo về RRF gây ấn tượng vì đơn giản đến bất ngờ, và cũng chỉ dài 2 trang: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
Với các tác vụ kiểu BM25 có thể dùng Elasticsearch, với tìm kiếm vector đơn giản và nhanh có thể dùng Turbopuffer, còn với kết quả truy vấn cụ thể được tính trước hoặc các thuộc tính động thay đổi thường xuyên như giá thì Redis cũng dùng được
Tôi cho rằng nên kết hợp các thứ này theo kiểu scatter/gather
Bên ngoài stack tìm kiếm hầu như luôn có một tầng dịch vụ suy luận để tái xếp hạng, và lý tưởng nhất là nó trở thành một dịch vụ đơn giản tương tự các hạ tầng machine learning khác
Gần như luôn cần cả routing: hiểu truy vấn của người dùng để gửi “tra cứu theo ID” sang một hệ thống, còn “tìm kiếm ngữ nghĩa mờ” sang hệ thống khác
Chúng có cấu trúc dữ liệu rất khác nhau, và tìm kiếm nói chung bao phủ rộng nhiều use case khác nhau
Tôi xem việc nhồi mọi thứ vào một hệ thống là anti-pattern
Mỗi hệ thống phù hợp với workload khác nhau, còn các chức năng suy luận tích hợp thì khó theo kịp tốc độ của các công cụ machine learning phổ thông mà các kỹ sư ML đã quen dùng
Tôi đã thử Elasticsearch Learning to Rank, nhưng đó là một việc không có triển vọng
Dù vậy, trong các nỗ lực giải quyết nhiều use case rộng bằng một stack duy nhất, Vespa có lẽ là lựa chọn tốt nhất
Với tư cách tác giả txtai, txtai triển khai chỉ mục BM25 hiệu năng cao trong Python thông qua package arrays, và lưu vector tần suất thuật ngữ vào SQLite
Cách lập chỉ mục lai của txtai hỗ trợ kết hợp lồi nếu điểm BM25 đã được chuẩn hóa, còn nếu chưa chuẩn hóa thì hỗ trợ Reciprocal Rank Fusion (RRF)
[1] https://github.com/neuml/txtai
[2] https://neuml.hashnode.dev/building-an-efficient-sparse-keyw...
[3] https://neuml.hashnode.dev/benefits-of-hybrid-search
[4] https://github.com/neuml/txtai/blob/master/src/python/txtai/...
Nó dùng nhiều kỹ thuật tìm kiếm: tìm kiếm dựa trên từ vựng (bm25, tìm kiếm mờ), tìm kiếm ngữ nghĩa (embedding), tái xếp hạng (cross-encoder, Reciprocal Rank Fusion), cũng như tái xếp hạng để đảm bảo tính đa dạng và giảm hiện tượng lost-in-the-middle
[1] Langroid - framework LLM đa tác nhân do các nhà nghiên cứu CMU/UW-Madison tạo ra https://github.com/langroid/langroid
[2] Triển khai DocChatAgent -
https://github.com/langroid/langroid/blob/main/langroid/agen...
Có thể bắt đầu từ phương thức answer_from_docs rồi lần theo tiếp
Nhân tiện, nếu bạn là nhà sáng lập Kadoa, Kadoa-snack là một trong những công cụ tôi thích dùng hằng ngày để tìm các thảo luận HN liên quan đến LLM
Bài viết hay
Nếu bổ sung thêm một chút bối cảnh khó tìm hơn, BM25 là viết tắt của “Best Matching 25”, và “best matching” nghĩa là một công thức dùng để khớp các thuật ngữ trong truy vấn với các thuật ngữ trong tài liệu, từ đó xếp hạng và gán trọng số cho thuật ngữ
Con số 25 chỉ là số thứ tự; trước đó đã có 24 biến thể công thức, sau đó cũng có các biến thể khác, nhưng phiên bản số 25 hoạt động tốt nhất nên được công bố
Nó do Stephen Robertson và Karen Spärck Jones (nổi tiếng với IDF) nghĩ ra, và được triển khai lần đầu trong hệ thống nghiên cứu truy xuất thông tin OKAPI của Robertson
Hệ thống OKAPI đã được benchmark trong nhiều năm tại TREC (Text Retrieval Conference) hằng năm của NIST Mỹ, gần giống như một “giải vô địch thế giới” quốc tế về phương pháp luận công cụ tìm kiếm
Tuy nhiên, sự kiện này nhằm mục đích so sánh và học hỏi lẫn nhau hơn là giành chiến thắng, và là một sự kiện đáng khuyến nghị, được tổ chức vào tháng 11 hằng năm tại Gaithersburg, Maryland
Ngoài mô hình không gian vector “túi từ” (vector thưa của các thuật ngữ) và mô hình xác suất mà BM25 thuộc về, còn có rất nhiều khung lý thuyết để xếp hạng tập tài liệu khi có truy vấn, nhiều đến đáng ngạc nhiên và vẫn tiếp tục tăng
Ví dụ có divergence from randomness, mô hình hóa ngôn ngữ thống kê, Learning to Rank, truy xuất thông tin lượng tử, xếp hạng bằng mạng nơ-ron, v.v.
Ở các hội nghị như ICTIR hay SIGIR, thỉnh thoảng đến nay vẫn xuất hiện những paradigm tìm kiếm hoàn toàn mới
Ở đây, “mô hình hóa ngôn ngữ thống kê” không có nghĩa là các mô hình ngôn ngữ lớn đang thịnh hành hiện nay; phần đó thuộc phạm trù “tìm kiếm bằng mạng nơ-ron”
Ngoài ra, nếu tìm “Quantum IR”, bạn có thể sẽ thấy phổ hồng ngoại hoặc một công ty xi măng cùng tên, chứ không phải tutorial về truy xuất thông tin lượng tử
Ngay cả trong thế kỷ 21, công nghệ tìm kiếm vẫn có những sắc thái tinh tế như vậy
Nếu muốn tự so sánh BM25 với các phương án thay thế, tôi khuyên dùng Terrier, một công cụ tìm kiếm mã nguồn mở kiêm nền tảng nghiên cứu do University of Glasgow phát triển
BM25 đã hơn 25 năm tuổi nhưng vẫn chứng minh là một baseline khó vượt qua, và thường được dùng làm mốc tham chiếu khi so sánh các phương pháp mới
Một biến thể gần đây hơn là BM24F có thể xử lý nhiều field như tiêu đề, nội dung, hyperlink, cũng như hypertext
Bài báo nên đọc là Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36(6): 779–808, cùng với Part 2 tiếp theo
Đáng tiếc là không phải open access
Bắt đầu ngày 18 và kết thúc ngày 22
Chi tiết: https://trec.nist.gov/
Tìm bằng Google và Google Scholar cũng không thấy nội dung liên quan
Hơi ngại nhưng xin phép quảng bá: https://github.com/jankovicsandras/plpgsql_bm25
https://github.com/jankovicsandras/bm25opt
https://github.com/softwaredoug/searcharray
Cũng xin quảng bá luôn BM25S rất phổ biến của Xing Han Lu, có mục tiêu tương tự
https://github.com/xhluca/bm25s
Tôi tò mò liệu có dự án wrapper thuần Python nào để quản lý nhiều văn bản và tài liệu PDF không
Tôi đã nghĩ đến Solr hoặc ElasticSearch, nhưng chúng có vẻ quá nặng cho việc tôi đang muốn làm
Vì SQLite dùng BM25 nên tôi đang cân nhắc dùng pysqlite3 cùng với PyPDF2
Hơi lệch chủ đề một chút, nhưng có lẽ nhiều người đang tìm công cụ để xây dựng ứng dụng hybrid BM25 / vector store / LLM
Tôi thắc mắc liệu độ dài tài liệu trung bình được nói đến trong phần chuẩn hóa độ dài tài liệu có phải là trung vị không
Để hạ trọng số của các tài liệu quá dài cho đúng, tôi nghĩ có lẽ phải là trung vị; nếu không, các tài liệu quá dài sẽ kéo trung bình lên một cách không công bằng
Dùng trung vị cũng có vẻ là một thử nghiệm thú vị
Tôi tò mò liệu bạn có biết dataset tìm kiếm nào mà độ dài tài liệu chênh lệch rất lớn không
Ví dụ MSMarco thì độ dài khá đồng đều
Bài viết hay
Tôi thật sự muốn học cách suy nghĩ về những vấn đề như thế này dưới dạng toán học và cách kiểm thử chúng; có tài liệu nào đáng tham khảo không?
Tìm kiếm hybrid giải quyết bài toán lâu đời về độ liên quan của kết quả tìm kiếm
Nếu dùng rank fusion giữa keyword và vector, ta có thể tạo ra tìm kiếm hybrid hoạt động trong hầu hết tình huống
BM25 là một thuật toán cũ được phát triển từ thập niên 1970
Về cơ bản, nó là một mô hình thống kê thô sơ, và các nhà thống kê ngày nay có thể làm tốt hơn nhiều
Tôi cho rằng tìm kiếm bị các phương pháp dựa trên học máy chi phối một cách nghiêm ngặt
Tất nhiên, việc học có thể dùng tìm kiếm làm đầu vào
Vẫn còn nhiều người chưa nhận ra điều này, hoặc có động cơ duy trì công nghệ cũ càng lâu càng tốt, nhưng áp lực thị trường cuối cùng sẽ thay đổi điều đó
Chẳng phải chính công nghệ đó đã khiến ta phải thêm “+reddit” vào mỗi truy vấn để tránh cuộc chiến SEO đối kháng sao?
Cũ không có nghĩa là xấu
Ta nên nhìn vào tính hữu dụng của một phát minh, khám phá hay kỹ thuật hơn là tuổi đời của nó; tôi thấy đáng lo về thái độ kỹ trị kỳ lạ cứ ám ảnh với tuổi đời
Những cách tiếp cận thống kê hiện đại cụ thể nào được xem là vượt trội đến mức có thể thay thế BM25 trong các ứng dụng thực tế?
Đặc biệt, chúng xử lý các trường hợp biên như thuật ngữ hiếm và chuẩn hóa độ dài tài liệu—những thứ BM25 vốn cố ý giải quyết—như thế nào?
Tôi đồng ý rằng các cách tiếp cận dựa trên học máy đã cho thấy kết quả ấn tượng, nhưng cũng muốn nghe thêm chính xác câu “tìm kiếm bị các phương pháp học máy chi phối một cách nghiêm ngặt” nghĩa là gì
Ý bạn là các benchmark cụ thể, hay các trường hợp vận hành thực tế?
Tôi nghĩ nhiều chuyên gia tìm kiếm sẽ không đồng ý
Tiêu đề một podcast rất hay của David Tippet (trước đây ở OpenSearch, hiện ở Github) và Nicolay Gerold là như sau:
“BM25 is the workhorse of search; vectors are its visionary cousin”
https://www.youtube.com/watch?v=ENFW1uHsrLM
Trong lĩnh vực tìm kiếm, suốt thời gian tôi làm việc đã có vô số trào lưu và công nghệ liên quan đến AI
Hiện nay, các công ty tìm kiếm vector nhận đầu tư VC khổng lồ đang dùng cả đội ngũ technical evangelist để thúc đẩy một góc nhìn nhất định
Trong khi đó, ở những nơi như Google, lượng công việc tuyển chọn thủ công và các hệ thống phân loại thủ công cơ bản, nhàm chán nhưng thực sự vận hành “tìm kiếm ngữ nghĩa” là rất lớn
Chỉ là những thứ đó không hấp dẫn nên ít được nói đến tại các hội nghị mà thôi