رفتن به محتوا
پارسا علیزاده
منو
بلاگهوش مصنوعی

جست‌وجوی برداری چگونه همسایه‌ها را سریع پیدا می‌کند: تعبیه‌ها، شباهت و HNSW

چرا جست‌وجوی دقیق نزدیک‌ترین همسایه مقیاس‌پذیر نیست، جست‌وجوی تقریبی چه چیزی را فدا می‌کند، و گراف HNSW از مقاله‌ی Malkov و Yashunin چگونه بردارهای نزدیک را سریع پیدا می‌کند.

۴ دقیقه مطالعه

نمودار یک گراف سلسله‌مراتبی دنیای کوچک پیمایش‌پذیر با سه لایه؛ جست‌وجو از لایه‌ی بالایی و کم‌تراکم وارد می‌شود و تا لایه‌ی پایینی و پرتراکم پایین می‌آید تا به نزدیک‌ترین همسایه برسد
در این صفحه

در قلب هر سامانه‌ی هوش مصنوعی مبتنی بر بازیابی یک پرسش یکسان نشسته است: با داشتن یک بردار پرسش، کدام بردارهای ذخیره‌شده به آن نزدیک‌ترند؟ پاسخ دادن سریع به این پرسش، آن هم در میان میلیون‌ها بردار، کار نمایه‌ی برداری (vector index) است. این نوشته مسئله را توضیح می‌دهد و یکی از پرکاربردترین راه‌حل‌های آن را معرفی می‌کند: گراف سلسله‌مراتبی دنیای کوچک پیمایش‌پذیر (Hierarchical Navigable Small World) یا HNSW.

تعبیه‌ها و شباهت#

یک تعبیه (embedding) فهرستی از اعداد، یعنی یک بردار، است که یک تکه متن، یک تصویر یا چیز دیگری را نمایش می‌دهد. مدل‌های تعبیه طوری آموزش می‌بینند که بردار چیزهایی که معنای مشابهی دارند به هم نزدیک باشد.

«نزدیک» نیاز به تعریف دارد. یکی از تعریف‌های رایج شباهت کسینوسی (cosine similarity) است، یعنی کسینوس زاویه‌ی میان دو بردار:

cosine(a, b) = (a · b) / (‖a‖ · ‖b‖)

مقدار آن از منفی ۱ تا ۱ است و وقتی دو بردار در یک جهت باشند برابر ۱ می‌شود. برای بردارهایی که به طول ۱ نرمال‌سازی شده‌اند، شباهت کسینوسی با ضرب نقطه‌ای برابر است؛ به همین دلیل بسیاری از سامانه‌ها تعبیه‌ها را یک بار نرمال‌سازی می‌کنند و سپس با ضرب نقطه‌ای مقایسه‌شان می‌کنند.

چرا جست‌وجوی دقیق مقیاس‌پذیر نیست#

محاسبه‌ی پاسخ دقیق ساده است: پرسش را با تک‌تک بردارهای ذخیره‌شده مقایسه کنید و بهترین را نگه دارید. این کار برای هر پرسش به ازای هر بردار ذخیره‌شده یک مقایسه هزینه دارد، پس حجم کار به‌طور خطی با اندازه‌ی مجموعه رشد می‌کند. وقتی با میلیون‌ها بردار و تعداد زیادی پرسش در ثانیه سروکار داریم، همین به گلوگاه تبدیل می‌شود.

جست‌وجوی نزدیک‌ترین همسایه‌ی تقریبی (approximate nearest neighbour) یا ANN یک بده‌بستان را می‌پذیرد: ممکن است گاهی یک نزدیک‌ترین همسایه‌ی واقعی را از دست بدهد، در عوض بسیار سریع‌تر پاسخ می‌دهد. کیفیت این بده‌بستان معمولاً با فراخوانی (recall) گزارش می‌شود، یعنی سهمی از نزدیک‌ترین همسایه‌های واقعی که نمایه واقعاً برمی‌گرداند.

HNSW از دل مقاله#

HNSW را Yu. A. Malkov و D. A. Yashunin در مقاله‌ی «Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs» معرفی کردند که نخستین بار در ۳۰ مارس ۲۰۱۶ منتشر شد [1].

مقاله آن را ساختاری چندلایه توصیف می‌کند که از مجموعه‌ای سلسله‌مراتبی از گراف‌های مجاورت (proximity graphs) تشکیل شده است؛ برای هر لایه یک گراف، روی زیرمجموعه‌های تودرتو از عناصر ذخیره‌شده [1]. دو ایده آن را کارآمد می‌کند.

۱. لایه‌های تصادفی، مانند فهرست پرشی#

وقتی عنصری درج می‌شود، بالاترین لایه‌ای که در آن حضور دارد به‌طور تصادفی و با یک توزیع احتمال نمایی نزولی انتخاب می‌شود [1]. بیشتر عناصر فقط در لایه‌ی پایینی هستند و تنها تعداد کمی به لایه‌های بالاتر و کم‌تراکم‌تر می‌رسند.

نویسندگان این شباهت را صریحاً بیان می‌کنند: HNSW را «می‌توان گسترشی از ساختار احتمالاتی فهرست پرشی (skip list) دانست که در آن به‌جای فهرست‌های پیوندی از گراف‌های مجاورت استفاده شده است» [2].

۲. جست‌وجو از بالا به پایین#

جست‌وجو از لایه‌ی بالایی آغاز می‌شود [1]. در آنجا پیوندها بلندند، پس یک پیمایش حریصانه (greedy) مسافت‌های زیادی را سریع طی می‌کند. وقتی دیگر نتواند نزدیک‌تر شود، یک لایه پایین می‌آید و با پیوندهای کوتاه‌تر ادامه می‌دهد تا به لایه‌ی پایینی برسد که همه‌ی عناصر را در خود دارد. مقاله گزارش می‌دهد که شروع از لایه‌ی بالایی همراه با این تفکیک مقیاس، پیچیدگی‌ای با رشد لگاریتمی را ممکن می‌کند [1].

پارامترهایی که با آن‌ها روبه‌رو می‌شوید#

کتابخانه‌هایی که HNSW را پیاده‌سازی می‌کنند پارامترهایی را در اختیار می‌گذارند که در الگوریتم درج مقاله نام‌گذاری شده‌اند [2]:

پارامترمعنا در مقاله
Mتعداد اتصال‌هایی که برای هر عنصر جدید برقرار می‌شود
Mmaxبیشینه‌ی تعداد اتصال‌های هر عنصر در هر لایه
efConstructionاندازه‌ی فهرست پویای نامزدها هنگام ساختن نمایه
efاندازه‌ی فهرست پویای نامزدها هنگام جست‌وجو؛ کیفیت جست‌وجو را کنترل می‌کند
mLضریب نرمال‌سازی برای انتخاب بالاترین لایه‌ی هر عنصر

برای mL، مقاله انتخابی ساده پیشنهاد می‌کند: 1 / ln(M) [2]. کیفیت جست‌وجو با ef کنترل می‌شود [2]: فهرست نامزدهای بزرگ‌تر بخش بیشتری از گراف را می‌کاود، که معمولاً فراخوانی را بالا می‌برد و زمان بیشتری می‌گیرد. به همین دلیل این مقادیر معمولاً بر اساس یک هدف فراخوانی تنظیم می‌شوند، نه اینکه یک بار تعیین شوند و رها شوند.

جایگاه آن در کل ماجرا#

جست‌وجوی برداری همان گام «بازیابی» در تولید تقویت‌شده با بازیابی است. اگر نمایه بخش درست را از دست بدهد، مدل زبانی هرگز آن را نمی‌بیند. بقیه‌ی این پایپ‌لاین را در تولید تقویت‌شده با بازیابی و سمت مدل را در ترنسفورمر از دل مقاله‌ی اصلی پوشش داده‌ام.

جمع‌بندی#

  • تعبیه‌ها چیزها را به بردار تبدیل می‌کنند؛ شباهت، که اغلب کسینوسی است، میزان نزدیکی را می‌سنجد.
  • جست‌وجوی دقیق با همه‌ی بردارها مقایسه می‌کند، پس هزینه‌اش به‌طور خطی با اندازه‌ی مجموعه رشد می‌کند.
  • HNSW گراف‌های مجاورت لایه‌لایه با لایه‌های تصادفی، شبیه فهرست پرشی، می‌سازد و از لایه‌ی بالایی و کم‌تراکم به پایین جست‌وجو می‌کند [1][2].
  • ef کیفیت جست‌وجو را کنترل می‌کند؛ آن را همراه با M و efConstruction بر اساس یک هدف فراخوانی تنظیم کنید [2].

منابع#

  1. Malkov, Yu. A., Yashunin, D. A. “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.” 2016. Abstract: https://arxiv.org/abs/1603.09320
  2. The same paper, full text (sections on the algorithm and Algorithm 1): https://arxiv.org/pdf/1603.09320

مقاله‌های مرتبط

مدل‌های زبانی متن را چطور می‌خوانند: توکن، BPE و اینکه چرا فارسی گران‌تر تمام می‌شود

توکن چیست، BPE چطور واژگان می‌سازد، چرا فارسی و ترکی توکن بیشتری از انگلیسی می‌گیرند، و چطور به‌جای حدس زدن توکن‌ها را بشماریم.

هوش مصنوعی۴ دقیقه مطالعه

چگونه یک سامانه‌ی RAG را ارزیابی کنیم: معیارهای بازیابی، وفاداری و داوران LLM

بازیابی و تولید را جداگانه بسنجید: recall@k، MRR و nDCG برای بازیاب و وفاداری برای پاسخ؛ و آنچه پژوهش‌ها درباره‌ی استفاده از مدل‌های زبانی به‌عنوان داور می‌گویند.

هوش مصنوعی۶ دقیقه مطالعه

کوانتیزه‌سازی مدل‌های زبانی بزرگ: وزن‌های ۸ بیتی و ۴ بیتی چگونه کار می‌کنند

چرا یک مدل ۷ میلیارد پارامتری در حالت ۱۶ بیتی به ۱۴ گیگابایت حافظه نیاز دارد، کوانتیزه‌سازی چطور آن را کوچک می‌کند، چرا داده‌های پرت کار را دشوار می‌کنند و هر یک از روش‌های LLM.int8()، GPTQ، AWQ و QLoRA چه چیزی را تغییر دادند.

هوش مصنوعی۶ دقیقه مطالعه