پادکست‌های جایزه مصطفی (ص)

تصور کنین توی یه اتاق کنترل بزرگ نشستین و وظیفه نظارت یه آزمایشگاه زیرزمینی و مخفی رو بر عهده دارین، جایی پر از مانیتور که هر کدوم میلیون‌ها داده رو نمایش میدن. تصاویر، صداها، مدارک پزشکی، پیام‌ها… همه چیز مثل یه رودخونه همیشه خروشان از جلوی چشماتون می‌گذره. توی یه چشم بهم زدن، یه هشدار به صدا درمیاد و چراغ قرمز بالای سرتون شروع می‌کنه به چشمک زدن و توجهتون رو به سمت خودش جلب می‌کنه. شما باید داده خرابکار رو توی کل این آشوب پیدا کنین، اما نه اسم مشخصی وجود داره، نه مختصات و نه کلمه‌ای برای توضیح.
فقط یه توصیف مبهم از متن هشدار رو می‌بینین:
" این ارور رو قبلاً دیدیم… شبیه اینه… اما دقیقاً همین نیست!" . اینجاست که شما به عنوان یه موتور جست و جوی انسانی با این سوال مواجه می‌شین: “چطور می‌شه بین میلیاردها داده، چیزی رو پیدا کرد که حتی نمی‌تونی تعریفش کنی؟”

سلام اینجا رصدخانه‌ست و ما قراره با هم به تماشای زیبایی‌های علم بنشینیم.

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

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

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

الگوریتم بعدی جست‌وجوی نزدیک‌ترین همسایه مبتنی بر فضای درختیه . 
این الگوریتم بجای گشتن خطی تموم داده‌ها، اول یه "ساختار درختی" سلسله مراتبی می‌سازه که فضا رو به مناطق کوچیک‌تر تقسیم می‌کنه. هر شاخه یا گره توی این درخت، نماینده یه بخش از فضا و تموم نقاط داده‌ای هستش که تو اون بخش قرار گرفتن.
جست‌وجو توی این روش مثل "آدرس پرسیدن" توی یه شهر بزرگه که در اون به جای چک کردن تک تک ساختمون‌ها و خونه‌ها، اول منطقه درست رو انتخاب می‌کنین، بعد خیابون درست رو پیدا می‌کنید و در نهایت به خونه مورد نظر می‌رسین. ساختار درختی به الگوریتم این اجازه رو می‌ده که به‌سرعت "منطقه" درست رو پیدا کنه.
بیاین ساختارش رو دقیق‌تر بررسی کنیم.. خب اول که باید درخت ساخته شه. برای این کار الگوریتم به‌صورت بازگشتی فضا رو تقسیم می‌کنه. یعنی فضا رو تیکه تیکه می‌کنه و هر تیکه رو دوباره بازم تیکه تیکه می‌کنه تا به قسمتای کوچیک و قابل مدیریت برسه. بازگشتی اینجا ینی الگوریتم یه عمل رو بارها روی خروجیش انجام میده. بعد از اون جست‌‌وجوی دقیق یا اصطلاحا MT-DFS انجام می‌شه. توی این مرحله، درخت پیمایش می‌شه و بهترین گزینه‌ای که تا اون لحظه پیدا شده رو به‌عنوان "کاندیدا" نگه می‌داره. بعد به سمت پایین درخت پیمایش می‌کنه و اگه ببینه فاصله یه شاخه جدید از فاصله شاخه کاندیدا به پرسش ما، یعنی همون میزان شباهت از فاصله شاخه کاندیدا بیشتره، اون شاخه رو کلا هرس میکنه و اصلا بررسیش نمی‌کنه. و بعد یک جست‌وجوی تقریبی روی درخت انجام می‌ده.
این روش چه مزایایی داره؟ سازگاری با ابعاد بالا، سرعت خیلی زیاد، عملکرد نسبتا خوب و دقت قابل قبول.
معایبش؟ این‌که این روش ذاتا "تقریبیه" و دقت رو فدای سرعت می‌کنه. علاوه بر اون هزینه هم‌پوشانی بالایی داره؛ یعنی یه داده ممکنه مجبور بشه همزمان توی چند شاخه یا ناحیه بررسی بشه که برای ما از نظر هزینه محاسباتی مطلوب نیست. 
 

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

نتیجه پژوهش‌های میررکنی تکنیک “پی-پایدار” در الگوریتم LSH هستش که نیاز به اون ترجمه سخت و زمانبر رو از بین می‌بره. این دانشمند روشی رو ابداع کرد که می‌تونه داده‌ها رو همونطور که هستن و بدون نیاز به ترجمه‌شون به 0 و 1، به‌صورت مستقیم دسته‌‌بندی کنه.خب خب می‌دونین که وقت چیه… وقت یه مثال دیگه: فرض کنین کلی توپ رنگی توی فضای یه اتاق معلقن، اینها همون داده‌هامونن. حالا می‌خوایم توپ‌های نزدیک به هم رو پیدا کنیم. به‌صورت تصادفی توی نقطه‌ای از سقفمون یه لامپ قرار می‌دیم. حالا چند تا کار باید انجام بشه: این لامپ یه خط یا بردار تصادفی رو توی فضا رسم می‌کنه. البته باید دقت کنیم که این خط براساس فرمول ریاضیاتی به اسم "توزیع پی-پایدار" انتخاب می‌شه که بخش مهم ماجراست. حالا تصور کنین نوری تو فضا بتابونیم تا سایه تموم توپ‌ها روی اون خط بیفته. توی دنیای ریاضی به این کار "تصویر کردن یا Projection می‌گن. حالا اون خط رو به قطعات مساوی مثل خط‌کش تقسیم می‌کنیم. نتیجه‌ش این میشه که اگه دو توپ توی فضا خیلی به هم نزدیک باشن، سایه‌هاشون هم روی اون خط توی یه خونه از شبکه‌ای که خط‌‌‌کشی کردیم میفته. اگر هم از هم دور باشن، سایه‌هاشونم احتمالا دور از هم میفتن. این فرمول ریاضی "پی-پایدار" شانسی نبودن این "سایه انداختن" رو تضمین می‌کنه و فاصله و شباهت واقعی اجسام رو حفظ می‌کنه.
این روش سرعت فوق‌العاده بالایی داره. تو آزمایشایی که میررکنی انجام داده مشخصه که این روش تا 40 برابر سریع‌تر از روش‌های کلاسیک عمل کرده و علاوه‌بر اون، پیاده‌سازیش برای برنامه‌نویسا خیلی راحته چون نیاز به تبدیل داده‌های پیچیده نیست. همچنین این روش مستقیما روی فاصله‌های دنیای واقعی (مثل فاصله مستقیم یا اقلیدسی) کار می‌کنه که برای جست‌و‌جوی عکس، ویدیو و اسناد متنی خیلی مناسبه. فاصله‌های دنیای واقعی فاصله‌هایی هستن که برای ما آدما ملموس هستن و می‌تونیم اندازه‌گیریشون کنیم. منظور از فاصله اقلیدسی هم پیدا کردن کوتاهترین فاصله ممکن بین دو نقطه هستش.
 

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

نکته دیگه‌ای که توی پژوهش میررکنی وجود داره و از اهمیت بالایی برخوردار هست، سازوکار "جابجایی تصادفیه" که فرمول اصلیش از چند ابزار استفاده می‌کنه: ضرب داخلی که همون سایه انداختن بردار روی خط تصادفی هستش و دومیش اینه که اون خط رو به قطعاتی با طول r تقسیم می‌کنه.
شاید مهم‌ترین بخش این پژوهش، اینه که یه عدد تصادفی به موقعیت سایه‌ها اضافه می‌شه. یعنی چی؟ اگه توی همون مثالمون دو تا نقطه خیلی به هم نزدیکن، اما بدشانسی میارن و دقیقا توی مرز دو تا خونه از شبکه قرار می‌گیرن، (مثلا یکی توی خونه 3 و دیگری 4) با اینکه بهم نزدیکن، توی دوتا جعبه جدا قرار می‌گیرن. اضافه کردن اون عدد تصادفی مثل این میمونه که خطوط شبکه رو به طور تصادفی کمی به راست یا چپ هلش بدیم. این کار احتمال جدا شدن نقاط نزدیک به هم رو کم می‌کنه.
این باعث بالا رفتن دقت میشه.
برای تقویت بیشتر دقت کار دیگه‌ای هم انجام میشه:
برای حل مشکل احتمالی خطای سایه انداختن، یه ساختار 2 مرحله‌ای پیشنهاد می‌شه:
مرحله اول پارامتر k هستش. این یعنی به جای یه بار، n بار سایه میندازیم و نتیجه‌ها رو کنار هم می‌ذاریم. این کار باعث می‌شه که مطمئن بشیم فقط چیزایی که واقعا شبیه به هم هستن توی یه جعبه انداخته می‌شن. 
مرحله دوم پارامتر L هستش. این پارامتر میگه که سخت‌گیری بیش از حد ممکنه باعث شه بعضی از همسایه‌های واقعی یه چیز رو ازدست بدیم. برای حل این مشکل، کل این پروسه رو چندین بار (مثلا 20 بار) با شبکه‌های مختلف تکرارش می‌کنیم و 20 جدول مختلف می‌سازیم. اگه دو تا چیز توی جدول شماره 1 هم‌گروه نشدن، ممکنه توی جدول 12 هم‌گروه بشن.
این روش پیشنهادی برای داد‌های خلوت کارایی بالایی داره. به‌عنوان مثال، توی سایتای خبری، کلی مقاله وجود داره که هرکدومشون ممکنه یه بردار یا یه مجموعه صدهزار کاراکتری باشن، ولی چیزی که بین مقاله‌ها متمایزه کلا 500 کلمه باشه. مثلا توی مقاله‌ای که راجع به آتش‌سوزی نوشته شده، خود کلمه آتش‌سوزی متمایز از سایر مقاله‌های خبریه ولی توی متنش حروف و کاراکترهای اشتراکی زیادی با بقیه مقالات داره. مثلا "از، با، در و …". روش‌های قدیمی میومدن تمام اون صدهزار خونه رو می‌گشتن، حتی اگر ارزششون صفر بوده، (یعنی تموم حروف مشترک)؛ ولی روش میررکنی با ضرب داخلی میاد اون خونه‌هایی که ارزش صفر دارن رو حذف می‌کنه و باعث می‌شه فقط اون 500 کلمه متمایز پردازش بشن تا جست‌و‌جو سریع‌تر انجام بشه.

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