چطور یک ایرانی جست‌وجو در دنیای میلیون‌بعدی داده‌ها را ۴۰ برابر سریع‌تر کرد؟

به گزارش گروه دانشگاه خبرگزاری دانشجو؛ وقتی روی یک خط مستقیم ایستاده‌اید و می‌خواهید نزدیکترین فرد به خود را پیدا کنید، کار ساده است: فقط کافی است به چپ و راست نگاه کنید و فاصله‌تان را با افراد اطراف مقایسه کنید. حال اگر در یک اتاق باشید، باید نزدیکترین فرد را در فضای دوبعدی پیدا کنید. باز هم مشکل چندانی وجود ندارد— با چرخیدن به دور خود و بررسی فاصله‌ها در جهات مختلف، می‌توانید جواب را بیابید.

اما اگر افراد بتوانند در فضای سه‌بعدی شناور شوند، چه؟ در این صورت، مسئله پیچیده‌تر می‌شود، چون باید جست‌و‌جو را در ارتفاع، عمق و عرض انجام دهید. اگر بعد زمان را هم اضافه کنیم، اوضاع کاملاً بغرنج می‌شود. حتی اگر تمام عمرتان هم وقت داشته باشید، آیا می‌توانید نزدیکترین فرد را در یک فضای چهاربعدی پیدا کنید؟

واقعیت شوکه‌کننده اینجاست: بسیاری از داده‌های دنیای واقعی در ابعاد بسیار بالاتری وجود دارند - گاهی ۱۰۰ بعد یا حتی بیشتر. این داده‌ها نفرین شده‌اند!

در این میان، دکتر وهاب میررکنی، پژوهشگر ایرانی و دانش آموخته دانشگاه صنعتی شریف و موسسه فناوری ماساچوست (MIT)، با ارائه الگوریتم «هش حساس به مجاورت» (LSH) راهکاری موثر برای جستجوی سریع داده‌های مشابه در مجموعه‌های عظیم ارائه کرد؛ دستاوردی که امروز از فناوری‌های کلیدی در پردازش کلان‌داده و هوش مصنوعی به شمار می‌رود. میررکنی که اکنون از پژوهشگران ارشد گوگل می‌باشد، به پاس این دستاورد در سال ۲۰۲۵ به عنوان یکی از برگزیدگان جایزه مصطفی (ص) معرفی شد.

برای درک بهتر این دستاورد بهتر است ابتدا با یکی از چالش‌های بنیادین عصر داده بیشتر آشنا شویم؛ مسئله‌ای که یافتن یک قطعه اطلاعات ارزشمند در میان انبوهی از داده‌ها را به جستجوی سوزنی در انباری عظیم از کاه تبدیل کرده است.

داده‌های نفرین شده

با پیشرفت فناوری و ورود داده‌های مختلف به دنیای محاسبات و پردازش، با انواع مختلفی از داده‌های نفرین‌شده مواجه شده‌ایم. یک تصویر رنگی ۱۰۰۰×۱۰۰۰ پیکسلی (که هر پیکسل در آن یک بعد است) در کامپیوتر، داده‌ای سه میلیون بعدی محسوب می‌شود! چراکه برای نگهداری هر پیکسل، باید ترکیب سه تایی قرمز، سبز و آبی که یکی از روش‌های استاندارد نگهداری تصاویر رنگی است، ذخیره گردد. حتی با استفاده از روش‌های کاهش ابعاد، باز هم در مسائل پردازش تصویر با صد‌ها یا هزاران بعد سروکار داریم.

زمانی که قصد پردازش فایل‌های متنی را داریم، در واقع وارد فضای مسائلی می‌شویم که به آن پردازش زبان طبیعی گفته می‌شود. در این گونه موارد، کلمات با روش‌هایی تبدیل به بردار عددی می‌شوند. به هر کلمه یک بردار عددی n-بعدی (۱۰۰-۳۰۰ بعدی) نسبت داده می‌شود به گونه‌ای که کلمات مشابه، بردار‌های مشابهی داشته باشند. سپس برای پردازش یک متن، کلمات اصلی شناسایی، استخراج شده و مورد بررسی قرار می‌گیرند. با این روش‌ها یک متن که ترکیبی از چندین کلمه است، داده‌ای با ابعاد بسیار بالا خواهد بود. یک پاراگراف می‌تواند ده‌ها هزار بعد داشته باشد! 

نمونه‌ای دیگر از داده‌هایی که در دهه اخیر بسیار مورد توجه قرار گرفته، داده‌های ژنتیکی هستند. در هر سلول از هر موجود زنده‌ای، مولکولی به نام DNA وجود دارد که از به هم پیوستن ۴ نوع مولکول ساده‌تر که به «باز» معروفند، تشکیل شده است. با توجه به این‌که طول آن در انسان به حدود ۳ میلیارد تکرار از این باز‌ها می‌رسد، به لحاظ نظری می‌تواند تنوع بسیار بالایی برای آن در نظر گرفت. بخش‌هایی از DNA در طی نسل‌ها تا حد بسیار زیادی حفظ می‌شوند و عملکرد بدن موجود زنده را تعیین می‌کنند که به آنها ژن گفته می‌شود. نگهداری اطلاعات DNA هر انسان می‌تواند به دو شکل صورت گیرد: یا کل توالی مولکولی آن نگهداری شود و یا تنها بخش‌های ژن که حدودا ۲۵۰۰۰ بخش با طول‌های متفاوت هستند نگهداری شود. در هر صورت با حجم اطلاعات بسیار بالایی مواجه خواهیم بود.

چالش جست‌و‌جو در داده‌های پرابعاد؛ همه نزدیکند و همه دور!

در چنین فضای پرابعادی، "نفرین ابعاد بالا" رخ می‌دهد. نفرین این‌چنین است که داده‌ها به شکل عجیبی پراکنده می‌شوند، طوری که تقریباً همه چیز به یک اندازه از هم فاصله دارند. به عبارت دیگر، مفهوم "شباهت" از بین می‌رود، چون همه داده‌ها تقریباً یکسان به نظر می‌رسند و جستجوی نزدیکترین همسایه یا شبیه‌ترین داده، به یک مأموریت غیرممکن تبدیل می‌شود و محاسبات، غیرعملی می‌گردند.

مسئله جستجوی نزدیک‌ترین همسایه یکی از مسائل کلیدی در علوم داده، یادگیری ماشین، و بازیابی اطلاعات است. هدف اصلی این مسئله، یافتن نزدیک‌ترین نقطه (یا نقاط) به یک نقطه داده‌شده است که می‌تواند بر اساس یک معیار شباهت مطرح شود. معیار‌های مختلفی برای سنجش فاصله داده‌ها وجود دارد دو نوع از ساده‌ترین آن‌ها فاصله اقلیدسی و فاصله منهتن است. در فاصله اقلیدسی طول پاره خطی که آن دو نقطه را در فضا مستقیما به یکدیگر وصل می‌کند، مد نظر است و در فاصله منهتن فاصله پلکانی برای رسیدن از یک نقطه به نقطه دیگر در نظر گرفته می‌شود؛ یعنی حاصل جمع اختلاف داده‌ها در ابعاد مختلف.

یافتن شبیه‌ترین تصویر به تصویر مدنظر ما از میان یک پایگاه داده تصویری و یا یافتن شبیه‌ترین موجودات به یکدیگر به لحاظ ژنتیکی و ساخت شجره‌نامه موجودات از دیدگاه تکامل، به نظر صورت مسئله‌های ساده‌ای می‌آیند، اما چالش‌های بسیار پیچیده‌ای دارند. گاهی حتی نیاز‌هایی مبنی بر تشخیص شباهت متنی و تقلب علمی مطرح می‌شود و یا تحلیلی از احساسات بیان‌شده در متن‌ها، مدنظر است. بازار تبلیغات و آگهی و سیستم‌های پیشنهاددهنده اگر بخواهند بنا بر سلیقه شما و کاربران مشابه، محصولی پیشنهاد دهند نیز از این چالش‌ها مستثنی نیستند. در واقع در تمام این مسائل مطرح‌شده ما تنها به دنبال شبیه‌ترین داده به یک داده خاص هستیم که اگر ابعاد داده‌ها کم بود، با روش‌های سنتی و الگوریتم‌های سریع، پاسخ در زمان معقولی آماده بود، اما آنچه که ما را در پاسخ دادن به این سوالات دچار مشکل می‌کند، ابعاد بسیار بالای آنهاست. 

شباهت در دنیایی دیگر!

محققان بسیاری سعی در ارائه راه حلی برای این مسئله داشته‌اند و با توجه به فضای بسیار پیچیده مسئله، صورت‌مسئله را به جای یافتن "نزدیک‌ترین داده"، به یافتن "داده به اندازه کافی نزدیک" تغییر دادند. اما باز هم از پیچیدگی موضوع کم نشد. یکی از موثرترین افراد این حوزه وهاب میررکنی است که این داده‌ها را می‌شناخت و می‌دانست که نمی‌توان مستقیم با آن‌ها دست و پنجه نرم کرد چرا که نفرین آنها به این راحتی شکسته نمی‌شود؛ فضا بسیار پیچیده‌تر از آن است که بتوان مستقیم وارد عمل شد. 

شاید اگر مسئله را به این شکل نگاه کنیم بتوانیم درک خوبی از تحقیقات این دانشمند پیدا کنیم: کتابی خوانده‌اید که شما را به‌شدت به خود جذب کرده است. پس از اتمام کتاب به دنبال خواندن کتاب دیگری می‌گردید که فضای ذهنی شما را به همان شکل به خود جذب کند. چگونه می‌توان چنین کتابی را از میان میلیون‌ها کتاب با انواع و اقسام نویسنده و موضوع و عنوان و ... یافت؟ مسلما عاقلانه نخواهد بود اگر یک نفر زمان خود را صرف آن کند که تمام کتاب‌های کتابخانه را بخواند و ببیند کدام یک به کتاب مورد علاقه او شبیه‌تر است! 

در سال ۱۹۹۸، ایده مبتنی بر "هش حساس به مجاورت" به نام LSH مطرح شد که شیوه جست‌و‌جو در داده‌ها را متحول کرد: به جای مقایسه مستقیم میلیون‌ها معیار، می‌توان از روش دسته‌بندی هوشمندانه استفاده کرد. تصور کنید کتابخانه‌ای عظیم دارید. به جای بررسی تک‌تک کتاب‌ها، ابتدا آنها را بر اساس موضوع دسته‌بندی می‌کنید: تاریخی، فلسفی، ادبی و ... و زمانی به دنبال کتابی مشابه می‌گردید، فقط در بخش مربوطه جست‌و‌جو می‌کنید. این همان ایده تبدیل داده‌های پیچیده به فضایی ساده‌تر است؛ کاری که با توابع هش ممکن می‌شود.

البته این ایده در ابتدا خام بود. دسته‌بندی‌های تک‌بعدی (مثلا فقط براساس موضوع) ممکن بود ناقص باشد. برای حل این مشکل، از چندین روش دسته‌بندی همزمان استفاده شد. مثلاً کتاب‌ها را نه‌تنها بر اساس موضوع، بلکه براساس حجم (رمان بلند، داستان کوتاه) و دوره تاریخی (رنسانس، معاصر) نیز طبقه‌بندی می‌کردند. حالا هر کتاب در چندین گروه قرار می‌گرفت. به عنوان نمونه، رمان بلندی با موضوع فلسفی و متعلق به قرن پنجم، تنها با کتاب‌های هم‌گروه خود مقایسه می‌شد. به این ترتیب، داده‌های میلیون‌بعدی به چند بعد ساده تقلیل می‌یافتند و جست‌و‌جو بسیار سریع‌تر انجام می‌شد.

اما یافتن چنین توابع هشی در ریاضیات کار ساده‌ای نبود. چرا که باید از توابعی استفاده می‌شد که شباهت در دنیای اصلی را حفظ می‌کرد و داده‌های شبیه به هم را به مکانی نزدیک به هم در دنیای جدید می‌برد. راه حل، استفاده از توابع هش تصادفی بود. چرا تصادفی؟ چون داده‌ها آنقدر پیچیده هستند که پیش‌بینی بهترین روش دسته‌بندی غیرممکن است. از طرفی توابع تصادفی با ایجاد نمای غیرقابل پیش‌بینی از داده‌ها، گاهی دسته‌بندی‌های بهتری ارائه می‌دادند.

LSH تا بدینجا خوب عمل کرده بود، اما محدود بود و برای حفظ شباهت، عموما از توابع هش شبیه‌تر استفاده می‌کرد و از توابع نادر کمتر بهره می‌گرفت. درواقع، به نوعی توابع هش مورد استفاده بر مبنای توزیع نرمال تولید می‌شدند؛ بنابراین، تنها می‌توانست روی دو معیار محاسبه فاصله یا متر معروف اقلیدسی و منهتن پاسخ مناسب ارائه دهد. از این رو، این روش برای هر نوع داده و هر متری کارائی لازم را نداشت و حفظ شباهت در فضای جدید را برای هر نوع داده‌ای تضمین نمی‌کرد.

در سال ۲۰۰۴ بود که وهاب میررکنی و همکارانش با ارائه تعمیمی نوآورانه، همه‌چیز را تغییر دادند. آنها با معرفی LSH مبتنی بر توزیع‌های پایدار، سیستمی ساختند که تقریباً با هر نوع داده و معیاری سازگار بود. در این روش، تولید توابع هش تنها متمرکز بر توزیع نرمال نبود و توابع هش نادر هم امکان استفاده بیشتری داشت و در نتیجه داده‌ها را با توابع عجیب‌تر بیشتری می‌شد دسته بندی کرد و بسته به نوع معیار محاسبه فاصله مدنظر می‌توانست توزیع توابع را تغییر دهد. در واقع هنر میررکنی این بود که به لحاظ ریاضی امکان استفاده از روش‌های متنوع و حتی نادرتری برای دسته بندی داده‌ها را فراهم کرد. 

میررکنی و همکارانش با بهره‌گیری از توزیع‌های پایدار، این اطمینان را دادند که داده‌های مشابه در فضای جدید نیز نزدیک به هم باقی می‌مانند. زیبایی کار این بود که این روش برای هر معیاری، از اقلیدسی و منهتن تا معیار‌های محاسبه فاصله پیچیده دیگر نیز قابل‌استفاده بود.

نتایج شگفت‌انگیز بود: روش جدید تا ۴۰ برابر سریع‌تر از روش‌های سنتی عمل می‌کرد. میررکنی با این نوآوری، دستاورد برجسته‌ای در دنیای جستجوی داده‌های پرابعاد ایجاد کرد. دیگر سرعت و دقت جست‌و‌جو به تعداد ابعاد داده وابسته نبود. حالا می‌شد در میان میلیون‌ها کتاب، به‌راحتی و با سرعت بالا، کتاب بعدی را سریعا برای مطالعه پیدا کرد و نگران نفرین ابعاد بالا نبود. این همان هنر تبدیل جهان پیچیده داده‌ها به فضایی ساده و قابل‌مدیریت بود. با ارائه این راهکار، زمینه‌ای فراهم شد تا افرادی که روی داده‌هایی با ابعاد بالا، از تصویر گرفته تا صدا و متن و داده‌های ژنتیکی و نظرسنجی‌های سایت‌ها و پیشنهاد دهنده‌های محصول و... مطالعه می‌کنند بتوانند هر زمان لازم بود، از این ایده استفاده کنند. 

منابع:
[۱]Hastie, T. , et al. (۲۰۰۹). The Elements of Statistical Learning (۲nd ed.). Springer. (Chapter ۲)
[۲]Aggarwal, C. C. (۲۰۰۱). "On the Surprising Behavior of Distance Metrics in High Dimensions. " ICDT.
[۳]Gonzalez, R. C. , & Woods, R. E. (۲۰۱۸). Digital Image Processing (۴th ed.). Pearson. (Chapter ۲) 
[۴]Mikolov, T. , et al. (۲۰۱۳). "Efficient Estimation of Word Representations in Vector Space. " arXiv:۱۳۰۱.۳۷۸۱.
[۵]Stephens, Z. D. , et al. (۲۰۱۵). "Big Data: Astronomical or Genomical?" PLOS Biology, ۱۳ (۷).
[۶]Koren, Y. , et al. (۲۰۰۹). "Matrix Factorization Techniques for Recommender Systems. " Computer, ۴۲ (۸).
[۷]Indyk, Piotr, and Rajeev Motwani. "Approximate nearest neighbors: towards removing the curse of dimensionality. " Proceedings of the thirtieth annual ACM symposium on Theory of computing. ۱۹۹۸.
[۸]Datar, M. , Immorlica, N. , Indyk, P. and Mirrokni, V.S. (۲۰۰۴) Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. Proceedings of Symposium on Computational Geometry (SoCG'۰۴) , ۲۵۳-۲۶۲.