BM25 फुल-टेक्स्ट सर्च एल्गोरिदम को समझना
(emschwartz.me)- BM25 आज भी फुल-टेक्स्ट सर्च में, जहाँ सटीक keyword matching ज़रूरी होती है, व्यापक रूप से इस्तेमाल होता है और vector similarity search को पूरक करने वाले hybrid search का एक महत्वपूर्ण हिस्सा है
- probability को सीधे गणना किए बिना भी दस्तावेज़ों की ranking तय करने के लिए, BM25 query terms के weights जोड़ता है और अधिक relevant दिखने वाले documents को ऊपर रखता है
- score मुख्य रूप से IDF, document के भीतर term frequency, और document length normalization से बनता है; दुर्लभ शब्दों को अधिक महत्व मिलता है और बार-बार आने पर reward धीरे-धीरे कम होता जाता है
k1repeated occurrences के reward के कम होने की गति को नियंत्रित करता है, औरbdocument length normalization की strength को; आमतौर परk1=1.2~2,b=0.75इस्तेमाल होते हैं- BM25 score वास्तविक relevance probability नहीं होता, इसलिए इसे किसी सार्वभौमिक comparison value की तरह इस्तेमाल करना कठिन है; यह उसी document collection के भीतर तुलना करने पर अर्थपूर्ण होता है
BM25 किस search problem को हल करना चाहता है
- BM25 या Best Match 25 फुल-टेक्स्ट सर्च में व्यापक रूप से इस्तेमाल होने वाला एल्गोरिदम है
- यह Lucene/Elasticsearch और SQLite आदि में default के रूप में उपयोग होता है
- हाल के समय में फुल-टेक्स्ट सर्च और vector similarity search को मिलाने वाला hybrid search आम हो गया है
- personalized content feeds में केवल vector similarity search से सटीक keyword handling पर्याप्त नहीं हो सकती
- अगर रुचि
Solid.jsमें है, तो सिर्फ vector similarity search इस्तेमाल करने पर Solid की तुलना में React से जुड़ा content अधिक आ सकता है
- अगर रुचि
- मुख्य प्रश्न यह है कि क्या किसी document के BM25 score को कई queries के बीच compare करके यह तय किया जा सकता है कि वह document किस query से सबसे बेहतर मेल खाता है
Probability Ranking Principle और BM25 का तरीका
- फुल-टेक्स्ट सर्च का लक्ष्य query के आधार पर संभावित documents के set में से सबसे relevant document ढूँढना है
- क्योंकि वास्तविक relevance को निश्चित रूप से जानना संभव नहीं होता, search इस आधार पर sort करने की कोशिश करता है कि किसी document के query से relevant होने की probability कितनी है
- इस विचार को Probability Ranking Principle कहा जाता है
- BM25 जैसी lexical search systems केवल query और document collection के भीतर मौजूद document characteristics का उपयोग करती हैं
- vector similarity search बाहरी text corpora पर trained embedding models का उपयोग करके query और document के अर्थ को व्यक्त कर सकती है
BM25 score के घटक
- BM25 query और document collection के कई signals को मिलाकर score की गणना करता है
-
Query terms
- अगर search query कई terms से बनी है, तो हर term का score अलग से निकाला जाता है और फिर उन्हें जोड़ा जाता है
-
Inverse Document Frequency (IDF)
- यह दिखाता है कि कोई विशेष search term पूरे document collection में कितना दुर्लभ है
the,andजैसे आम शब्दों को कम informational value वाला माना जाता है, जबकि दुर्लभ शब्दों का महत्व बढ़ाया जाता है
-
Document के भीतर term frequency
- यह दर्शाता है कि search term किसी विशेष document में कितनी बार आता है
- एक ही term जितनी अधिक बार दोहराई जाती है, relevance की संभावना उतनी बढ़ सकती है, लेकिन BM25 repeated occurrences पर diminishing returns लागू करता है
-
Document length
- लंबे documents में केवल लंबा होने की वजह से search terms अधिक बार आ सकते हैं
- BM25 document length को average document length से compare करके normalize करता है, ताकि लंबे documents को अनुचित रूप से बहुत ऊँचा score न मिल जाए
BM25 formula के प्रत्येक भाग
- BM25 का कुल score document
Dऔर queryQके लिए प्रत्येक query termq_iके score को जोड़कर निकाला जाता हैD: target documentQ: पूरी queryn: query terms की संख्याq_i: प्रत्येक query term
-
IDF: collection के भीतर दुर्लभ शब्दों को अधिक वज़न देना
- IDF term यह गणना करता है कि query term पूरे document collection में कितनी दुर्लभ है
N: collection में documents की कुल संख्याn(q_i): उन documents की संख्या जिनमें query term शामिल हैN - n(q_i): उन documents की संख्या जिनमें query term शामिल नहीं है- आम terms कई documents में आती हैं, इसलिए score पर उनका प्रभाव कम हो जाता है
- दुर्लभ terms केवल कुछ documents में आती हैं, इसलिए score में उनका योगदान अधिक होता है
- formula में
0.5और1smoothing का काम करते हैं, ताकि term बहुत दुर्लभ या बहुत आम होने पर result बहुत अधिक unstable न हो
-
Term frequency: repetition को गिनना, लेकिन असीमित reward न देना
- document के भीतर term frequency यह दर्शाती है कि कोई query term किसी विशेष document में कितनी बार आती है
f(q_i, D): query termq_iकी documentDमें आने की frequencyk1: एक tuning parameter, जिसे आमतौर पर1.2से2के बीच set किया जाता है- BM25 term repetition को score में शामिल करता है, लेकिन repetition बढ़ने पर अतिरिक्त score increment धीरे-धीरे घटता जाता है
k1नियंत्रित करता है कि term repetition का reward कितनी तेजी से कम हो
-
Document length normalization: लंबे documents के लाभ को समायोजित करना
- document length normalization target document की length को collection की average document length से compare करता है
|D|: target document की lengthavgdl: collection की average document lengthb: एक tuning parameter जो document length normalization की strength को नियंत्रित करता है- average से लंबे documents में search term अधिक बार आने की संभावना होती है, इसलिए final formula के denominator में उन्हें penalty मिलती है
b=0होने पर document length normalization बंद हो जाता है, औरb=1होने पर यह पूरी तरह लागू होता हैbआमतौर पर0.75पर set किया जाता है
BM25 का मुख्य विचार
- BM25 Probability Ranking Principle पर आधारित है, लेकिन document relevance की वास्तविक probability की गणना करना लगभग असंभव है
- search में सटीक probability value से अधिक महत्वपूर्ण documents का order होता है, इसलिए formula से उन terms को हटा दिया जाता है जो ranking को प्रभावित नहीं करते, ताकि गणना व्यावहारिक बन सके
- इसी कारण BM25 probability नहीं बल्कि weight की गणना करता है
- Robertson/Sparck Jones Weight relevant documents की संख्या और query term शामिल करने वाले documents की संख्या का उपयोग करके probability estimate करने का एक तरीका है
r: query term शामिल करने वाले relevant documents की संख्याN: collection में documents की कुल संख्याR: collection में relevant documents की संख्याn: query term शामिल करने वाले documents की संख्या
- इस तरीके की बड़ी सीमा यह है कि पहले से यह जानना पड़ता है कि कौन से documents relevant हैं
“ज़्यादातर documents relevant नहीं होते” की धारणा
- BM25 के developers ने माना कि किसी भी arbitrary query के लिए अधिकांश documents relevant नहीं होते
- यदि relevant documents की संख्या नगण्य मानी जाए, तो
R = r = 0रखा जा सकता है - इन values को Robertson/Sparck Jones Weight formula में रखने पर लगभग वही रूप मिलता है जो BM25 में इस्तेमाल होने वाले IDF term का है
- relevance information पहले से माँगे बिना भी उसी theoretical foundation को बनाए रखने के कारण BM25 कहीं अधिक practical बन जाता है
- Victor Lavrenko ने इसे "very impressive leap of faith" कहा है
BM25 score comparison की सीमा
- BM25 score को सामान्य रूप से सीधे compare करना कठिन होता है
- यह 0 से 1 के बीच probability score नहीं बनाता
- यह ऐसा एल्गोरिदम भी नहीं है जो document के relevant होने की वास्तविक probability estimate करने की कोशिश करे
- इसका ध्यान किसी विशेष collection के भीतर query के लिए relevance likelihood के order को approximate करने पर होता है
- अधिक BM25 score इस बात का संकेत है कि document के अधिक relevant होने की संभावना है, लेकिन यह वास्तविक relevance probability नहीं है
- उसी document collection के भीतर, उसी document के लिए, कई queries के BM25 scores की तुलना की जा सकती है
- क्योंकि BM25 प्रत्येक query term के scores को जोड़ता है, इसलिए दो query terms के scores की तुलना और दो पूरी queries के scores की तुलना के बीच अर्थ की दृष्टि से विशेष अंतर नहीं माना जा सकता
- महत्वपूर्ण constraint है same document, same collection
- BM25 collection के भीतर के IDF और average document length का उपयोग करता है
- collection बदलने पर score बदल सकता है, इसलिए समय के साथ score comparison की गारंटी नहीं होती
- personalized content feeds में, प्रत्येक user interest के लिए फुल-टेक्स्ट search चलाकर BM25 scores compare किए जा सकते हैं, ताकि यह तय किया जा सके कि कौन सा content किस interest से बेहतर मेल खाता है
आगे पढ़ने के लिए सामग्री
- BM25 के theory और history में और गहराई से जाने के लिए Elastic engineer Britta Weber की 2016 की प्रस्तुति Improved Text Scoring with BM25 देखी जा सकती है
- Stephen Robertson और Hugo Zaragoza का The Probabilistic Relevance Framework: BM25 and Beyond BM25 के probabilistic relevance framework पर चर्चा करता है
- BM25 और अन्य फुल-टेक्स्ट search algorithms की तुलना Comparing full text search algorithms: BM25, TF-IDF, and Postgres में देखी जा सकती है
1 टिप्पणियां
Hacker News की राय
सामान्य search के लिए मैं https://typesense.org/ इस्तेमाल करता हूँ, और अब यह hybrid search भी support करता है, इसलिए जानना चाहता हूँ कि किसी ने इसे आज़माया है या नहीं
Typesense का यहाँ ज़िक्र देखना अच्छा लगा; छोटे पैमाने के RAG project के लिए यह अक्सर काफ़ी उपयुक्त होता है, लेकिन अजीब बात है कि यह उतना जाना-पहचाना नहीं है
इसे deploy करना आसान है, defaults भी समझदारी भरे हैं, documentation अच्छी है, और clustering भी अपेक्षाकृत आसान है; फिर भी जब ज़्यादा गहराई में जाने की ज़रूरत पड़े, तब भी यह काफ़ी performant और powerful है
लेकिन अगर embedding model किसी external provider से लिया जाए, तो latency 500ms+ तक बेतुकी तरह से बढ़ जाती है, इसलिए इसे cluster के अंदर ही host करना बेहतर है
hybrid search की quality अच्छी है, लेकिन tuning options बहुत सीमित हैं, और scoring भी result set के अंदर ranking के अलावा काफ़ी अपारदर्शी है
हाल में vector-based semantic search में हुई प्रगति को देखते हुए, आजकल keyword + semantic search hybrid के लिए लोग कौन-सा आधुनिक search stack इस्तेमाल कर रहे हैं, यह जानने की उत्सुकता है
हाल में मुझे लगभग 30 लाख survey responses मिले, जिनमें हर एक में 10 free-text fields थे, और उनमें से ऐसे items ढूँढ़ने थे जिन पर कंपनी को action लेना चाहिए
मैंने कुछ छोटे classifier models इस्तेमाल किए, पहले 10,000 records में दिखे noise को देखकर common words को manually हटाया, फिर model responses को weight दिया, और यह लगभग पूरी तरह सही चला
यह “programming” से ज़्यादा कई tools के black-box outputs को test cases और customer feedback के हिसाब से तब तक tune करने जैसा था, जब तक नतीजे अच्छे न लगें
संदर्भ के लिए, यह सब मैंने एक छोटे server पर Node.js में कई छोटे Hugging Face models को जोड़कर किया
results को आमतौर पर Reciprocal Rank Fusion (RRF) से combine किया जाता है
RRF पर paper हैरान कर देने वाली हद तक सरल है, और paper भी सिर्फ़ 2 पन्नों का है: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
BM25 जैसे कामों के लिए Elasticsearch, simple और fast vector search के लिए Turbopuffer, और कुछ queries के results को पहले से compute करके रखने या price जैसी अक्सर बदलने वाली dynamic properties के लिए Redis भी इस्तेमाल किया जा सकता है
मुझे लगता है कि इन्हें scatter/gather तरीके में जोड़ना अच्छा है
search stack के बाहर लगभग हमेशा reranking के लिए एक inference service layer होती है, और आदर्श रूप से वह दूसरे machine learning infrastructure जैसी एक simple service होनी चाहिए
user query को समझकर “ID lookup” को एक system में, और “fuzzy semantic search” को दूसरे system में भेजने जैसी routing भी लगभग हमेशा ज़रूरी होती है
इन सबकी data structures बहुत अलग होती हैं, और search आम तौर पर काफ़ी अलग-अलग use cases को व्यापक रूप से cover करता है
हर चीज़ को एक ही system में ठूँस देना एक anti-pattern है
हर system अलग workload के लिए बना है, और built-in inference features के लिए machine learning engineers जिन सामान्य ML tools के आदी होते हैं, उनकी speed तक पहुँचना मुश्किल होता है
मैंने Elasticsearch Learning to Rank के साथ यह करने की कोशिश की, लेकिन वह एक बेनतीजा काम था
फिर भी, व्यापक use cases को एक ही stack से हल करने की कोशिशों में Vespa शायद सबसे बेहतर है
txtai के लेखक के रूप में, txtai Python में arrays package के ज़रिए high-performance BM25 index implement करता है, और term frequency vectors को SQLite में store करता है
txtai का hybrid indexing approach, BM25 scores normalized हों to convex combination ko, और normalized न हों तो Reciprocal Rank Fusion (RRF) को support करता है
[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/...
यह कई search techniques इस्तेमाल करता है: lexical search (bm25, fuzzy search), semantic search (embeddings), reranking (cross-encoder, Reciprocal Rank Fusion), और diversity बनाए रखने व lost-in-the-middle को कम करने के लिए reranking
[1] Langroid - CMU/UW-Madison के शोधकर्ताओं द्वारा बनाया गया multi-agent LLM framework https://github.com/langroid/langroid
[2] DocChatAgent implementation -
https://github.com/langroid/langroid/blob/main/langroid/agen...
answer_from_docsmethod से शुरू करके आगे देखा जा सकता हैऔर हाँ, अगर आप Kadoa के founder हैं, तो Kadoa-snack उन tools में से एक है जिन्हें मैं LLM से जुड़ी HN चर्चाएँ खोजने के लिए रोज़ाना पसंद से इस्तेमाल करता हूँ
बढ़िया लेख है
थोड़ा और मुश्किल से मिलने वाली पृष्ठभूमि जोड़ें तो, BM25 का मतलब “Best Matching 25” है, और “best matching” से आशय उस फ़ॉर्मूला से है जो query के terms और document के terms को मिलाकर ranking और term weighting तय करता है
25 सिर्फ़ एक क्रम संख्या है; इससे पहले 24 फ़ॉर्मूला variants थे और बाद में भी बदलाव हुए, लेकिन 25वाँ संस्करण सबसे अच्छा काम करता था इसलिए वही प्रकाशित हुआ
इसे Stephen Robertson और Karen Spärck Jones (जो IDF के लिए प्रसिद्ध हैं) ने बनाया था, और इसे पहली बार Robertson के OKAPI information retrieval research system में लागू किया गया
OKAPI system को अमेरिका के NIST की वार्षिक TREC (Text Retrieval Conference) में कई वर्षों तक benchmark किया गया, और यह search engine methodology की अंतरराष्ट्रीय “world championship” जैसी है
हालाँकि इस आयोजन का मकसद जीतना नहीं, बल्कि तुलना और आपसी सीख है, और यह हर साल नवंबर में Maryland के Gaithersburg में होता है—सिफ़ारिश करने लायक आयोजन है
“bag-of-words” vector space model (terms के sparse vectors) और BM25 जैसे probabilistic model के अलावा भी, query दिए जाने पर documents के set को rank करने के सैद्धांतिक ढाँचे चौंकाने वाली संख्या में हैं और लगातार बढ़ रहे हैं
उदाहरण के लिए divergence from randomness, statistical language modeling, Learning to Rank, quantum information retrieval, और neural ranking जैसे तरीके हैं
ICTIR या SIGIR जैसी conferences में आज भी कभी-कभी बिल्कुल नए search paradigms सामने आते हैं
यहाँ “statistical language modeling” से मतलब आजकल लोकप्रिय बड़े language models नहीं हैं; वे “neural search” की श्रेणी में आते हैं
और अगर आप “Quantum IR” खोजेंगे तो quantum information retrieval tutorial की जगह infrared spectroscopy या उसी नाम की किसी cement company के नतीजे दिख सकते हैं
21वीं सदी में भी search technology में ऐसी बारीकियाँ हैं
अगर आप BM25 और उसके alternatives की सीधे तुलना करना चाहते हैं, तो University of Glasgow द्वारा विकसित open source search engine और research platform Terrier की सिफ़ारिश है
BM25 को 25 साल से ज़्यादा हो चुके हैं, लेकिन यह अब भी एक ऐसा baseline साबित हुआ है जिसे पार करना आसान नहीं, और नए तरीकों की तुलना में इसे अक्सर reference point की तरह इस्तेमाल किया जाता है
नया variant BM24F title, body, hyperlink जैसे कई fields और hypertext को संभाल सकता है
सुझाया गया paper है 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, और उसका अगला Part 2
दुर्भाग्य से यह open access नहीं है
18 तारीख़ को शुरू हुआ और 22 को ख़त्म होगा
विवरण: https://trec.nist.gov/
Google और Google Scholar से खोजने पर भी इससे जुड़ी जानकारी नहीं मिली
शर्माते हुए self-promo: https://github.com/jankovicsandras/plpgsql_bm25
https://github.com/jankovicsandras/bm25opt
https://github.com/softwaredoug/searcharray
इसी तरह के लक्ष्य वाला Xing Han Lu का बेहद लोकप्रिय BM25S भी साथ में promote कर देता हूँ
https://github.com/xhluca/bm25s
मैं सोच रहा हूँ कि क्या बहुत सारे text और PDF documents संभालने के लिए कोई pure Python wrapper project मौजूद है
Solr या ElasticSearch के बारे में सोचा था, लेकिन जो काम अभी करना है उसके लिए वे कुछ ज़्यादा भारी लगते हैं
चूँकि SQLite BM25 इस्तेमाल करता है, इसलिए pysqlite3 और PyPDF2 को साथ में इस्तेमाल करने का विकल्प देख रहा हूँ
विषय से थोड़ा हटकर है, लेकिन लगता है बहुत से लोग hybrid BM25 / vector store / LLM applications बनाने के लिए tools ढूँढ रहे होंगे
document length normalization में जिस average document length की बात होती है, क्या वह median होता है?
बहुत लंबे documents का weight ठीक से कम करना हो तो लगता है median होना चाहिए; नहीं तो क्या बहुत लंबे documents average को अनुचित रूप से ऊपर नहीं खींच लेते?
median का उपयोग भी एक दिलचस्प प्रयोग हो सकता है
क्या आप कोई ऐसा search dataset जानते हैं जिसमें document length का अंतर बहुत बड़ा हो?
उदाहरण के लिए MSMarco में length काफ़ी एक जैसी है
बढ़िया लेख है
मैं सच में सीखना चाहता हूँ कि ऐसे problems को mathematical form में कैसे सोचा जाए और उन्हें test कैसे किया जाए; क्या कोई ऐसी सामग्री है जिसे आप recommend करेंगे?
Hybrid search search result relevance की पुरानी समस्या को हल करता है
keyword और vector के बीच rank fusion का उपयोग करें तो ज़्यादातर स्थितियों में काम करने वाली hybrid search बनाई जा सकती है
BM25 1970 के दशक में विकसित किया गया एक पुराना algorithm है
मूल रूप से यह एक काफी साधारण statistical model है, और आज के statisticians इससे कहीं बेहतर कर सकते हैं
मेरा मानना है कि search पर learning-based methods का कड़ा प्रभुत्व है
बेशक, learning search को input के रूप में इस्तेमाल कर सकती है
अभी भी बहुत से लोग या तो यह बात नहीं समझ पाए हैं, या उनके पास पुरानी तकनीक को जितना हो सके उतना लंबे समय तक बनाए रखने का प्रोत्साहन है, लेकिन बाज़ार का दबाव आखिरकार इसे बदल देगा
क्या उसी तकनीक की वजह से लोग adversarial SEO की लड़ाई से बचने के लिए हर search query के साथ “+reddit” जोड़ने लगे?
पुराना होना अपने-आप में बुरा नहीं है
किसी invention, discovery, या technique की उम्र से ज़्यादा उसकी उपयोगिता देखनी चाहिए; उम्र पर अटक जाने वाला यह अजीब technologist रवैया चिंताजनक है
कौन-से ठोस आधुनिक statistical approaches हैं जिन्हें आप वास्तविक applications में BM25 की जगह लेने लायक बेहतर मानते हैं?
खासकर यह जानना दिलचस्प होगा कि वे rare terms और document length normalization जैसे edge cases को कैसे संभालते हैं, जिन्हें BM25 ने स्पष्ट रूप से address करने की कोशिश की थी
मैं मानता हूँ कि learning-based approaches ने प्रभावशाली नतीजे दिखाए हैं, लेकिन यह भी और सुनना चाहूँगा कि search के learning methods द्वारा “कड़े प्रभुत्व” में होने से आपका सटीक मतलब क्या है
क्या आप किसी खास benchmark की बात कर रहे हैं, या वास्तविक production cases की?
लगता है बहुत से search experts इससे सहमत नहीं होंगे
David Tippet (पूर्व OpenSearch, वर्तमान Github) और Nicolay Gerold के एक शानदार podcast का शीर्षक ही है:
“BM25 is the workhorse of search; vectors are its visionary cousin”
https://www.youtube.com/watch?v=ENFW1uHsrLM
search क्षेत्र में, जितने समय से मैं काम कर रहा हूँ, उतने समय में अनगिनत trends और AI-related technologies आती रही हैं
अभी भारी VC funding पाने वाली vector search कंपनियाँ technology evangelists की पूरी फ़ौज के साथ एक खास नज़रिया आगे बढ़ा रही हैं
दूसरी ओर, Google जैसी जगहों पर “semantic search” को वास्तव में चलाने वाली manual curation और बुनियादी, उबाऊ manual taxonomies की मात्रा बहुत बड़ी है
बस वे चीज़ें इतनी sexy नहीं लगतीं, इसलिए conferences में उनके बारे में ज़्यादा बात नहीं होती