ارزیابی BM25 در برابر TF-IDF: تابع اشباعی که مشکل بمباران کلمات کلیدی در جستجو را حل کرد

وقتی کاربری یک خطای فنی خاص را جستجو می‌کند، دیگر اولین نتیجه صفحه‌ای نیست که کد خطا را ۵۰۰ بار تکرار کرده باشد، بلکه سندی است که کد را در کنار اصطلاحات عیب‌یابی مرتبط در خود جای داده است. این تغییر در کیفیت بازیابی، ناشی از یک مرز ریاضی مشخص است که توسط الگوریتم Okapi BM25 معرفی شد. پیش از پذیرش گسترده آن، موتورهای جستجویی که بر پایه «فرکانس عبارت-فرکانس معکوس سند» (TF-IDF) کار می‌کردند، به تکرار کلمات پاداش خطی می‌دادند: سندی با ۵۰ بار تکرار یک کلمه، امتیاز بسیار بالاتری نسبت به سندی با ۵ بار تکرار می‌گرفت. الگوریتم BM25 با معرفی یک منحنی اشباع، این معیار پایه را تغییر داد؛ ارزش کلمات تکراری را محدود کرد و سیستم‌های بازیابی را مجبور ساخت تا اسنادی را در اولویت قرار دهند که با چندین کلمه مختلف از پرس‌وجوی کاربر مطابقت دارند.[4]

پایه و اساس هر دو مدل بر معیار «فرکانس معکوس سند» (IDF) استوار است که در سال ۱۹۷۲ توسط کارن اسپارک جونز فرمول‌بندی شد. معیار IDF بر یک فرض ساده عمل می‌کند: کلماتی که تقریباً در هر سندی ظاهر می‌شوند، مانند «الگوریتم» یا حروف ربط، وزن اطلاعاتی بسیار کمی دارند. در مقابل، یک عبارت نادر مانند «اشباع» وزن بالایی دارد. همان‌طور که نشریه Journal of Documentation در مقاله «درک فرکانس معکوس سند: درباره استدلال‌های نظری برای IDF» اشاره می‌کند، میزان تخصصی بودن یک عبارت با تعداد اسنادی که آن را در بر دارند، نسبت عکس دارد.[2][3]

جایی که این مدل‌ها از هم فاصله می‌گیرند، نحوه برخورد آن‌ها با نیمه اول معادله است: فرکانس عبارت (TF). در TF-IDF استاندارد، این محاسبه اغلب یک شمارش ساده است. اگر سند الف کلمه «پایگاه داده» را سه بار و سند ب آن را ۳۰ بار داشته باشد، سند ب امتیاز عبارت بسیار بالاتری دریافت می‌کند. این مقیاس‌پذیری خطی و بدون محدودیت، یک آسیب‌پذیری عظیم در جستجوهای اولیه وب ایجاد کرد و به ناشران اجازه داد تا صرفاً با پنهان کردن صدها کلمه کلیدی نامرئی در پایین یک صفحه وب، رتبه‌بندی‌ها را دستکاری کنند.[4][5]

مدل Okapi BM25 که توسط استیون رابرتسون و تیمش در دانشگاه سیتی لندن برای کنفرانس بازیابی متن در سال ۱۹۹۴ (TREC-3) معرفی شد، به جای رویکرد هندسی، با رویکردی احتمالی به این مشکل پرداخت. به جای پرسیدن این که «این کلمه چند بار ظاهر می‌شود»، BM25 می‌پرسد «با توجه به فرکانس عبارات، چقدر احتمال دارد که این سند به نیاز اطلاعاتی کاربر مرتبط باشد؟»[1]

برای پاسخ به این سوال، BM25 یک پارامتر اشباع غیرخطی به نام k1 را معرفی کرد. این پارامتر که معمولاً بین ۱٫۲ تا ۲٫۰ کالیبره می‌شود، تعیین می‌کند که ارزش یک تطابق کلمه کلیدی اضافی با چه سرعتی کاهش می‌یابد. اولین باری که یک عبارت جستجو شده در یک سند ظاهر می‌شود، سهم زیادی در امتیاز دارد. حضور دوم آن امتیاز کمتری اضافه می‌کند. زمانی که عبارت برای ششمین یا هفتمین بار ظاهر می‌شود، امتیاز به یک مجانب ریاضی سخت نزدیک می‌شود.[4][6]

همان‌طور که گروه پردازش زبان طبیعی استنفورد (Stanford NLP Group) در تحلیل خود از این الگوریتم با عنوان «Okapi BM25: یک مدل غیرباینری» اشاره می‌کند، منحنی اشباع به طور مؤثری مؤلفه فرکانس عبارت را محدود می‌کند. اگر k1 روی ۱٫۲ تنظیم شود، حداکثر ضریب ممکن برای فرکانس عبارت - حتی اگر کلمه یک میلیون بار ظاهر شود - برابر با ۲٫۲ است. این تابع اشباع فوراً بمباران ابتدایی کلمات کلیدی را خنثی کرد، زیرا یک سند اسپم که یک کلمه را ۱۰۰ بار تکرار می‌کند، رتبه پایین‌تری نسبت به یک سند معتبر می‌گیرد که سه کلمه مختلف از پرس‌وجوی کاربر را تنها یک بار در خود جای داده است.[4]

دومین نقص ساختاری عمده در TF-IDF، سوگیری آن به سمت اسناد طولانی بود. یک دفترچه راهنمای فنی ۱۰,۰۰۰ کلمه‌ای، صرفاً به دلیل داشتن دایره لغات بزرگ‌تر، از نظر آماری بسیار بیشتر از یک چکیده ۵۰۰ کلمه‌ای احتمال دارد که هر عبارت جستجویی را در خود داشته باشد. مدل TF-IDF استاندارد به طور معمول اسناد مختصر و بسیار مرتبط را زیر متون حجیم و پراکنده‌ای که به طور تصادفی تطابق‌های خام بیشتری از کلمات را جمع‌آوری کرده بودند، دفن می‌کرد.[1][5]

الگوریتم BM25 این مشکل را از طریق یک پارامتر نرمال‌سازی طول سند به نام b حل کرد. پارامتر b که معمولاً روی پیش‌فرض ۰٫۷۵ تنظیم می‌شود، فرکانس عبارت را بر اساس طول سند خاص نسبت به میانگین طول اسناد در کل مجموعه تنظیم می‌کند. اگر سندی طولانی‌تر از حد میانگین باشد، الگوریتم از نظر ریاضی شمارش فرکانس عبارت آن را کاهش می‌دهد و برای رسیدن به همان امتیاز ارتباطی یک سند کوتاه‌تر، نیازمند تکرار بیشتر آن کلمه است.[1][5]

ایوان شوارتز، مهندس نرم‌افزار، در مقاله «مقایسه الگوریتم‌های جستجوی متن کامل» خاطرنشان می‌کند که سیستم‌های پایگاه داده مدرن تقریباً به طور جهانی به BM25 مهاجرت کرده‌اند. به عنوان مثال، Postgres از BM25 برای قابلیت‌های جستجوی متن کامل خود استفاده می‌کند، در حالی که غول‌های جستجوی سازمانی یعنی Elasticsearch و Lucene به طور رسمی TF-IDF را کنار گذاشتند تا BM25 را به عنوان الگوریتم امتیازدهی پیش‌فرض خود به ترتیب در نسخه‌های ۵٫۰ و ۶٫۰ جایگزین کنند.[5]

با وجود این که بیش از سه دهه از عمر BM25 می‌گذرد، این الگوریتم همچنان معیاری است که تمام مدل‌های مدرن جستجوی مبتنی بر هوش مصنوعی با آن سنجیده می‌شوند. در حالی که امبدینگ‌های برداری متراکم و مدل‌های جستجوی عصبی در تطابق معنایی عالی عمل می‌کنند - مثلاً درک این که «کتانی» و «کفش مخصوص دویدن» به هم مرتبط هستند - اغلب در تطابق دقیق کلمات کلیدی برای اسامی خاص نادر یا شماره سریال‌ها با مشکل مواجه می‌شوند.[6]

محققان Google Cloud که در حال بررسی گذار «از BoW به BM25» هستند، تأکید می‌کنند که فقدان درک معنایی در این الگوریتم، در واقع در زمینه‌های خاص یک ویژگی مثبت محسوب می‌شود. از آنجا که BM25 صرفاً بر تطابق دقیق توکن‌ها وزن‌دهی شده با میزان نادر بودن در مجموعه اسناد تکیه دارد، ارتباطات را توهم نمی‌کند (hallucinate) یا از محدودیت‌های صریح پرس‌وجوی کاربر منحرف نمی‌شود.[6]

تغییر از TF-IDF به BM25 نشان‌دهنده گذار از یک مکانیزم شمارش ساده‌لوحانه به یک چارچوب احتمالی کالیبره‌شده است. الگوریتم BM25 با تحمیل ریاضی این واقعیت که پنجاهمین حضور یک کلمه، ۵۰ برابر آموزنده‌تر از اولین حضور آن نیست، مکانیک پایه بازیابی اطلاعات مدرن را پایه‌گذاری کرد که حتی شبکه‌های عصبی چند میلیارد پارامتری نیز هنوز مجبور به رقابت با آن هستند.[1]