موتورهای جستجو - بررسی نحوه عملکرد و پیاده سازی (قسمت دوم)

اگر قسمت اول را نخوانده اید، از اینجا می توانید به آن دسترسی داشته باشید.

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

ابتدا، به چند مورد از پیش پردازش هایی که حتما قبلا به چشمتان آمده و برایتان آشنا هستند، اشاره ای می کنیم.

• همسان سازی کوئری وارد شده - normalization
• کامل کردن ادامه جمله (کوئری) بصورت خودکار - auto-complete
• پیشنهاد کلمه صحیح، هنگام تایپ - auto-correct
• تشخیص دسته مرتبط با کوئری وارد شده (در جستجوگر هایی که اسنادشان قابل دسته بندی باشد)

• درست کردن غلط های تایپی موجود در کوئری - spellchecking
• آنالیز کردن کوئری و همینطور فیلد های مهم در اسناد (قبل یا حین ایندکس کردن)
• ...

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

• غلط های املایی
• غلط های تایپی
• کلماتی که در هیچ یک از اسناد ما حضور نداشته اند
• اشتباهاتی که به دلیل تفاوت تلفظ محاوره ای یک کلمه با تلفظ رسمی آن بوجود می آیند (این مورد شامل لهجه های مختلف برای تلفظ یک کلمه هم می شود)
• ...

به همین دلیل، این موضوع بسیار مهم می باشد که سعی کنیم هرچه بیشتر، به چیزی که در ذهن کاربر بوده، در هنگام تایپ کردن کوئری، نزدیک شویم و نتایج مرتبط تر را به کاربر نمایش دهیم.

در این نوشته، سعی میکنم هریک از این سه موردی که اشاره کردم را، شرح مختصری بدهم؛ اما تمرکز بیشتری به روی موضوع spellchecking خواهم داشت.

همسان سازی کوئری - normalization

این پروسه، شاید در برخی موتور های جستجو، اصلا لازم نباشد. همینطور ممکن است بنا به نوع و زبان اصلی اسناد مورد جستجو توسط موتور جستجو، متفاوت باشد. از مثال هایی از بلا هایی که در این مرحله، به سر کوئری وارد شده می آیند، می توان به موارد زیر اشاره کرد:

• تبدیل تمامی حروف به حالت lower-case
• حذف یا جایگزینی symbol ها (!,@,#,$,...)
• جدا کردن کلمات از اعداد. برای مثال: iphone6 به iphone 6
• حذف کاراکتر های اضافی مثل علائم نگارشی، نشانه های ثانویه فارسی ( َ ِ ُ ً ٍ ٌ آ أ ء ...) برای مثال، حروفی مثل «آ» و «أ» را به «ا» تبدیل می کنیم.

پیشنهاد ادامه جمله - autocomplete

*مفهوم autocomplete را با autocorrect اشتباه نگیرید. موضوع autocorrect بسیار شبیه به spellchecking می باشد، که این موضوع را در ادامه بررسی میکنیم.*

حتما با پیشنهاد های سرچ گوگل در هنگام سرچ کردن مواجه شده اید. به محض اینکه اولین کاراکتر یا اولین کلمه را در جعبه جستجو گوگل وارد میکنید، پیشنهاد های متعددی به شما نمایش داده می شوند که در اکثر اوقات هم، بسیار نزدیک به چیزی که در ذهنتان بوده، هستند. اگر دقت کرده باشید، هرچه تعداد کلماتی که می نویسید، بیشتر باشد، پیشنهاد های دقیق تری هم به شما نمایش داده می شوند. تمام کوئری هایی که خودتان، یا کاربران دیگر، در طول عمر یک موتور جستجو، در این موتور جستجو وارد کرده اید، در انجام این پروسه، به کار گرفته می شوند. همینطور تیتر اسناد ایندکس شده، در عملکرد بهتر سرویس autocomplete تاثیر میگذارند. ایده کلی درباره کارکرد قابلیت autocomplete، استفاده از تعداد زیادی string می باشد که احتمال اینکه کاربر چیزی نزدیک به یکی از آنها را بنویسد، زیاد باشد.

روشی که بصورت معمول استفاده می شود، استفاده از درخت پسوندی - suffix tree می باشد. suffix های یک string، در واقع همان زیر رشته (substring) های یک string می باشند. اگر یک درخت تشکیل دهیم که فرزندان هر گره، substring های آن رشته باشند، زمانی که کاربر بخشی از کوئری مورد نظرش (به این تکه از کوئری sq می گوییم) را وارد کرده، میتوانیم با اجرای یک الگوریتم سرچ روی این درخت، رشته هایی که بخشی از آنها، شبیه به sq هستند را پیدا کنیم و به عنوان پیشنهاد، به کاربر نمایش دهیم.

روش دیگری که برای حدس زدن کلمه بعدی یک جمله به کار می رود، استفاده از مدل Markov می باشد. به دنباله ای از رویداد ها که از مدل Markov پیروی می کنند، یک زنجیره مارکوف - Markov Chain می گویند. در این روش به همون شکل قبل، یک مجموعه از جملات محتمل را پردازش، و با توجه به توزیع احتمالاتی دنباله کلمات وارد شده (qs)، سعی میکنیم کلمه بعدی را حدس بزنیم. به دلیل اینکه توضیح این روش، این متن رو بسیار طولانی (تر) می کند، به ارائه یک مثال بسنده می کنم و اگر علاقه ای به خواندن بیشتر در این مورد دارید، پیشنهاد میکنم این مقاله را مطالعه کنید.

جملات زیر را در نظر بگیرید:

• I like Photography
• I like Science
• I love Mathematics

تشخیص دسته بندی

این قسمت، در موتور جستجو هایی که اسنادشان قابل دسته بندی هستند و یا به هر نوعی، مفهوم دسته بندی روی این اسناد قابل تعریف باشد، نیاز می شود و تجربه کاربری را بسیار بهبود می دهد. اگر به تصویری که از جعبه جستجو وبسایت ترب که بالاتر قرار گرفته، دقت کنید، سه پیشنهاد اول، شامل پیشنهاد دسته بندی نیز می باشند. روشی که برای پیاده سازی این قابلیت استفاده شده، naive bayes classification می باشد. دیتایی که برای آموزش این مدل استفاده شده، اسم تمام محصولات موجود در یک دسته بندی مشخص می باشد. مدل naive bayes، برای دیتا هایی که اصطلاحا لیبل دار هستند، مدل بسیار مناسبی است. همانطور که می توانید ببینید، دیتای ما، کاملا لیبل دار است و با استفاده از naive bayes، میتوانیم به این قابلیت برسیم که یک یا چند کلمه را به عنوان ورودی به مدل بدهیم و دسته بندی هایی که این دنباله از کلمات، احتمالا به آن دسته مربوطند را، به عنوان خروجی، از مدل بگیریم.

رفع غلط های تایپی - spellchecking

حتما تابحال با صحنه ای مشابه تصویر بالا روبرو شده اید. شاید حتی خیلی اوقات، برای پیدا کردن املای صحیح یک کلمه، اولین املایی که به ذهنتون میرسه رو تو گوگل وارد میکنید و در نهایت به املای درست اون کلمه میرسید. غلط های تایپی/املایی، رایج ترین نوع خطاهای انسانی در سطح دنیا محسوب می شوند. هرروز، هنگام چت کردن، نوشتن یک ایمیل، نوشتن توییت، سرچ کردن و ... با غلط های تایپی/املایی روبرو می شوید. این مشکل، نه مختص شماست، نه مشکل کیبرد شماست!! هنگام استفاده از تلفن همراه، به دلایل مختلف، ممکن است که کلید اشتباهی را بفشارید (انگشتان بزرگی دارید :joy:) یا کلید ها را به ترتیب اشتباهی بفشارید. به هرحال، این نوع اشتباهات، کاملا رایج هستند و هیچ راهی برای جلوگیری از اتفاق افتادنشان وجود ندارد. اگر شما کلمه اشتباهی را جستجو کنید، به صورت منطقی، نباید هم به نتایج دلخواهتان برسید. اما، از آنجایی که شاید خیلی اوقات، حتی متوجه این موضوع نشوید که کلمه اشتباهی را جستجو کرده اید، در اکثر اوقات، نرسیدن به نتایج مطلوب را، به «بد» بودن آن موتور جستجو نسبت می دهید :)) اما خب امروزه، با استفاده از تکنیک های مختلف، میشه تا حدی، این غلط های املایی و تایپی رو، متوجهشون شد و در نهایت به کلمه درست (کلمه ای که از ابتدا تو ذهن کاربر بوده) رسید.

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

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

فرض کنیم که یک corpus از کلمات و جملات مورد نظرمان را جمع آوری کرده ایم. نحوه تشخیص کلمات درست، بسیار ساده است. اگر یک کلمه خاص، در corpus ما، بیشتر از یک threshold خاصی، تکرار شده باشد، می توانیم بگوییم که این کلمه، کلمه درستی است. برای مثال، اگر فرکانس یک کلمه، بزرگتر از ۱۵ باشد، با احتمال بیش از ۹۰ درصد، این کلمه، کلمه درستی است. یکی از مشکلاتی که در این مرحله با آن مواجه می شویم، مشکل کثیف بودن corpus می باشد. فرض کنیم که corpus ما، تعدادی article جمع آوری شده از سطح اینترنت باشد. مشکلی که پیش می آید، این است که اگر یک کلمه اشتباه (دارای غلط املایی)، در چند جای مختلف از این article ها، تکرار شده باشد، الگوریتم ما، این کلمه اشتباه را هم بعنوان یک کلمه درست در نظر میگیرد. به همین دلیل، تمیز بودن corpus و بالانس کردن threshold برای تشخیص کلمات درست، در این مرحله، اهمیت بالایی دارد.

بعد از اینکه کلمات درست موجود در یک جمله (کوئری کاربر) را تشخیص دادیم، می توانیم بگوییم که کلمات باقی مانده، کلمات اشتباهی هستند (که غلط املایی یا تایپی دارند).

بازیابی کلمات

در ابتدا، اجازه دهید که کمی درباره مفهوم فاصله کلمات با یکدیگر صحبت کنیم. فاصله ای که از آن حرف میزنیم، یک معیار قابل اندازه گیری، برای میزان اختلاف دو string مختلف می باشد. برای مثال، رشته های زیر را در نظر بگیرید.

• neat, beat, bear, seat
• black, red, apple, kiwi

می توانید ببینید که کلمات دسته اول، بسیار شبیه به هم و نزدیک به هم هستند. در صورتی که کلمات دسته دوم، تقریبا هیچ شباهتی به یکدیگر ندارند. اگر شباهت از نظر نحوه گفته شدن و تلفظ کلمات را در نظر نگیریم، می توانیم ببینیم که اختلاف کلمات دسته اول، هر کدام با دیگری، تنها در یک کاراکتر می باشد (bear و beat را با هم در نظر بگیرید :joy:) به اینصورت که، یکی از کاراکتر ها باید به کاراکتر دیگری تبدیل شود. حال، به تغییرات دیگری که می توان روی یک کلمه ایجاد کرد تا به کلمه دیگری رسید فکر کنید. این تغییرات، یکی از این حالت ها هستند: جابجا کردن حروف، اضافه کردن یا حذف کردن یکی از حروف، تغییر دادن یکی از حروف (که می توان به چشم یک حذف و یک اضافه به این عمل نگاه کرد). پس می توان با اندازه گیری تعداد تغییرات مورد نیاز، برای رسیدن از یک کلمه، به یک کلمه دیگر، فاصله این دو رشته را از هم حساب کرد. روش های مختلفی برای محاسبه این نوع از فاصله بین string ها (که به آنها editing distance گفته می شود) ابداع شده اند. روش های Levenshtein Distance و Damerau-Levenshtein Distance و Jaro Score، از جمله معروف ترین این روش ها هستند.

نکته بعدی که در ادامه از آن استفاده خواهیم کرد، این نکته هست که، هنگام محاسبه فاصله دو کلمه از یکدیگر، می توانیم برای هر یک از اعمالی (تغییرات) که روی کلمه اول باید اتفاق بیوفتد تا به کلمه دوم برسد، یک امتیاز تعریف کنیم. برای مثال، اگر عمل ما، جابجا کردن دو تا از حروف می باشد، می توان این عمل را با توجه به فاصله آن دو حرف از یکدیگر، امتیاز دهی کرد. یا اگر یکی از حروف، با حرف دیگری قرار است جایگزین شود، فاصله کاراکتر ها، می تواند متفاوت باشد. به تصویر زیر توجه کنید:

حروفی که روی یک کیبرد استاندارد qwerty، نزدیک تر به یک حرف هستند، امتیاز بالاتری برای جایگزینی دارند (یعنی فاصله شان کمتر است).

ایده پردازش متقارن

ایده اصلی که در پروسه spellchecking استفاده شده، پردازش کلمات corpus و کوئری کاربر، بصورت متقارن می باشد. فرض کنید که ما میخواهیم سرویسی ارائه کنیم، که قابلیت بازیابی کلمات تا حداکثر فاصله ۴ را داشته باشد. کاری که در ابتدا انجام می دهیم، تشکیل یک دیکشنری از تمام token های موجود در corpusمان می باشد. نحوه تشکیل این دیکشنری، به این شکل هست که، به ازای هر token، تمام token های ممکن، در فاصله حداکثر ۲ را، در کنار یک object بعنوان راهنمای بازیابی کلمه، می سازیم. برای فهم بهتر، به مثال زیر توجه کنید:

کلمه مورد بررسی ما، کلمه iphone می باشد. وقتی از token های با فاصله حداکثر ۲ صحبت می کنیم، منظورمان token هایی است که با عمل «کم کردن» از iphone ساخته می شوند. در نتیجه، token های تولید شده برای کلمه iphone، به شرح زیر می باشند:

['phone', 'ihone', 'ipone', 'iphne', 'iphoe', 'iphon', 'hone', 'pone', 'phne', 'phoe', 'phon', 'ione', 'ihne', 'ihoe', 'ihon', 'ipne', 'ipoe', 'ipon', 'iphe', 'iphn', 'ipho']

حال برای هر یک از این token ها، یک object راهنما، برای بازیابی این کلمه به کلمه اصلی نیز ذخیره می کنیم. این object در واقع، به ما می گوید که برای رسیدن به هر یک از این token ها، چه حروفی، از کجای کلمه اصلی حذف شده اند. برای مثال، برای رسیدن از کلمه iphone، به ihone، باید حرف p را از جایگاه دوم این کلمه، حذف کنیم. این object، توانایی نگهداری ۲ فاصله را دارد (به شکل یک آرایه ۲ تایی). در حال حاضر، ما تمام token های با فاصله حداکثر ۲، از تمام کلمات corpus خودمان را داریم. یکی از نکات جالب توجه در این مرحله، تقلیل کلمات مختلف به یکدیگر می باشد. در مثال بالا، دیدیم که کلمه iphone، با حذف حرف اولش، به کلمه phone تبدیل می شود. مثال های متعددی از این نوع اتفاق، می توان پیدا کرد (هدفون -> هدف، مردانه -> مردان، ...).

ساختمان داده ای که در مرحله قبل ساختیم، که شامل یک دیکشنری از تک تک کلمات corpus و فرکانسشان (freq) و یک mapping از هر کلمه، به token های در فاصله ۲ از آن کلمه (deleted) می باشد، برای سرعت دسترسی بالا، در مرحله initial سرویس اسپل چکر، محاسبه و بروی رم قرار داده می شود.

زمانی که کلمه ای برای تصحیح اسپلینگ، به ما داده می شود (کوئری کاربر)، مراحل حذف و تولید token های با فاصله ۲ را، روی آن اجرا می کنیم و تک تک token های تولید شده را، با لیست token های موجود در deleted، چک میکنیم و به دنبال match ها میگردیم.

1. تولید token های در فاصله ۲ از کوئری کاربر
2. برای هریک از این token ها، به دنبال match در deleted می گردیم.
3. هر یک از این match ها را، با توابع مختلف، امتیاز دهی می کنیم. (درباره نحوه امتیازدهی، در ادامه صحبت شده)
4. بالاترین امتیاز را بعنوان پاسخ بر میگردانیم.

به مثال زیر توجه کنید:

کوئری کاربر: مانتیور - پاسخ تصحیح شده: مانیتور

هر یک از token های بالا، ممکن است با نسخه تقلیل یافته یک کلمه ای که در corpus قرار داشته، match شود.

با این روش (Symmetric Delete spelling correction algorithm) می توانیم تا فاصله حداکثر ۴، هر کلمه را اسپل چک کنیم. در این روش، با انجام یک trade-off روی میزان رم مصرفی و تایم پردازش سر هر درخواست، به سرعت بسیار بالایی با دقت ۴ فاصله می رسیم. می توانید این مقاله رو هم برای توضیحات بیشتر درباره این روش، بخوانید.

امتیازدهی

پارامتر های زیادی برای محاسبه امتیاز هریک از این «تبدیل» (transform) ها وجود دارد. می توان گفت که این مرحله، مهم ترین مرحله پروسه اسپل چکینگ می باشد. شاید برای هر کلمه ای که miss-spell شده، بتوانید بالای ۱۰ تا match پیدا کنید. اینکه کدام یک از این match ها را بعنوان پاسخ صحیح معرفی کنید. بسیار موضوع مهمی است.

هزینه تبدیل

در هر عمل تبدیل، اتفاقات مختلفی ممکن است رخ دهد. در ساده ترین حالت، این اعمال یا بصورت حذف کردن چند حرف خواهند بود، یا به صورت اضافه کردن چند حرف. اما این حذف و اضافه ها، می توانند از انواع خاصی باشند. برای مثال، یک حذف و یک اضافه، می تواند به صورت جایگزین شدن یک حرف باشد. مثل: ipjone و iphone. فاصله ای که برای این دو کلمه در نظر گرفته می شود، فاصله ۲ است. درصورتی که ارزش (هزینه) این تبدیل، کمتر از ۲ باید محاسبه شود. مخصوصا اگر حرف جایگزین شده، از کلید های دور و اطراف کلید حرف اولیه باشد (تصویر مربوط به همسایگی کلیدها در کیبرد). همینطور، این حذف و اضافه ها می توانند به شکل جابجایی دو حرف باشند. حالت جابجایی، با فاصله ۴ قابل شبیه سازی است. اما هزینه این تبدیل، مشخصا کمتر از ۴ است. به این شکل، امتیازی که برای هر تبدیل حساب می کنیم، می تواند به عنوان امتیاز فاصله (فاصله واقعی) در نظر گرفته شود.

امتیاز اندازه تغییر و فرکانس

در اینجا، منظور از «اندازه تغییر»، کسر زیر می باشد.

d: فاصله
s: اندازه کلمه
(d/s)

این پارامتر، از این رو اهمیت دارد که، اگر یک کلمه شامل ۴ حرف باشد، اضافه یا حذف کردن ۳ حرف به این کلمه، واقعا زیاد است!! یعنی کاربر باید ۳ حرف را اشتباها اضافه کرده باشد یا ننوشته باشد. درصورتی که اگر این کلمه شامل ۱۰ حرف باشد، اختلاف ۳ حرف، انقدر غیر منطقی نیست. پارامتر بعدی، فرکانس کلمات است. اگر ما با پردازش match های کوئری کاربر، بین دو کلمه، با امتیاز یکسان مانده باشیم، قاعدتا باید گزینه ای که فرکانس بالاتری دارد را به عنوان جواب برگردانیم. فرمولی که ما در سرویس اسپل چکر ترب استفاده کرده ایم، چیزی شبیه به فرمول زیر است:

1000 * exp(-15 * (distance / origin_size + 0.3) + 10) * ln(1 + freq)

بردار کلمات (word2vec)

در قسمت اول این نوشته، درباره نحوه تبدیل کردن دنباله ای از کلمات، به یک بردار و نحوه برخوردمان با این بردار ها توضیح دادیم. به دلیل بیش از اندازه طولانی نشدن این نوشته، از توضیح درباره خود الگوریتم word2vec میگذریم. برای اینکه بیشتر با این الگوریتم آشنا شوید، می توانید از صفحه ویکیپدیا این الگوریتم شروع کنید.

جایی که ما از این الگوریتم استفاده می کنیم، در همین قسمت امتیازدهی می باشد. همونطور که در ادامه بحث گفتیم، زمانی که یک دنباله از کلمات (درواقع کل کوئری کاربر) به سرویس ما ارسال می شود، ما کلماتی که فرکانسشان بیشتر از threshold مورد نظرمان باشد را بعنوان کلمه صحیح میشناسیم و پردازشی روی آنها انجام نمی دهیم. استفاده جالبی که می توان از این کلمات کرد، تولید بردار حاصل از کنار هم قرار دادن این کلمات صحیح، با استفاده از مدل train شده word2vec می باشد. می توانیم مدلمان را با همان corpusی که تا الان با آن کار میکردیم، train کنیم و با توجه به همان مدل، برای کلمات و جملات مختلف، بردار مربوطه شان را بسازیم. استفاده ای که از این بردار می کنیم، به این شکل هست که، اگر کلمه بازیابی شده، در این بردار وجود داشته باشد، امتیازش یک ضریب خیلی خوب میگیرد. یعنی هنگام امتیاز دهی هر یکی از match هایی که در مراحل قبل پیدا کردیم، هربار چک می کنیم که آیا این match، مشابهش در بردار تولید شده توسط بقیه کلمات وارد شده توسط کاربر، موجود هستند یا خیر. به مثال زیر توجه کنید:

کوئری کاربر: گوشی اپل آیفن - کوئری صحیح: گوشی اپل آیفون

زمانی که ما میخواهیم این کوئری را پردازش کنیم، کلمات «گوشی» و «اپل» به دلیل داشتن فرکانس بالاتر از threshold، بعنوان کلمه صحیح شناخته می شوند. این دو کلمه را بعنوان ورودی، به مدل word2vec مان می دهیم و برداری مشابه بردار زیر به ما برگردانده می شود:

['موبایل', 'تلفن', 'آیفون', 'سامسونگ', 'آیفون۶', '۶۴گیگ', 'همراه', 'گیگابایت']

اینکه سایز بردار چه اندازه باشد، دست خودمان است و می توانیم به هر اندازه بزرگ در نظر بگیریمش. ترتیب این کلمات، بر اساس میزان ارتباطشان می باشد.

بعد از اینکه این بردار را تولید کردیم، در زمان امتیاز دهی، هربار چک میکنیم که کلمه ای که تولید شده، در این بردار حضور دارد یا نه. اگر حضور داشته باشد، ضریب نسبتا بزرگی را در امتیاز آن match ضرب می کنیم.

با استفاده از این الگوریتم، ما توانستیم دقت تشخیص و تصحیح سرویس اسپل چکر را به چیزی نزدیک به ۷۰ درصد افزایش دهیم. قبل از اینکه روش word2vec به این سرویس اضافه شود، دقتش حدود ۵۰ درصد بود؛ که امروز با افزایش ۲۰ درصدی، روی موتور جستجو اصلی ترب در حال استفاده می باشد.

در تلاش هستیم که سورس کد این سرویس را سریعتر، بصورت متن باز منتشر کنیم. منطق اصلی این سرویس با زبان c++ نوشته شده و اینترفیس نرم افزاری آن را با استفاده از cython و twisted پیاده سازی کرده ایم.

یادگیری رتبه بندی اسناد

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

یکی از جالب ترین مسائل در بحث بهینه سازی نتایج، فیدبک های کاربران می باشد. اینکه شما چقدر الگوریتم پیچیده ای برای رتبه بندی اسنادتان استفاده می کنید، تا زمانی که کاربر از نتایج شما رضایت نداشته باشد، «تقریبا» هیچ اهمیتی ندارد :)) یکی از ساده ترین پارامتر ها برای اینکه متوجه شوید کاربر چقدر از نتایج شما رضایت داشته و از این مهم تر، از کدامیک از نتایجی که نمایش داده اید، رضایت بیشتری داشته است، توجه به کلیک های کاربر می باشد. اگر در لیست نتایج مربوط به یک کوئری، اولین سندی که روی آن کلیک شده، سند پنجم باشد، الگوریتم شما «بهتر بود» آن سند را در رتبه اول نمایش میداد!! در ادامه به شرح کلیتی از روشی که در این مقاله توضیح داده شده می پردازیم.

این مقاله، به معرفی روشی با استفاده از مدل SVM برای رتبه بندی اسناد با توجه به «کلیک های کاربران» برروی اسناد می پردازد. رتبه بندی ای که موتوری مانند ElasticSearch به شما می دهد، با توجه به پارامتر های (محتوا) داخل سند انجام می شود. کار ساده ای که میتوان انجام داد، ایجاد یک فیلد جدید در ساختار سند است، که شمارنده تعداد کلیک های کاربران بروی اون سند می باشد. می توان یک تابع امتیاز دهی بر اساس این فیلد، داخل کوئری الستیک نوشت. مشکل این روش، و درواقع تفاوتی که باعث می شود ما نتوانیم از این روش به درستی استفاده کنیم، این است که، یک سند، ممکن است در نتیجه جستجوی هزاران کوئری متفاوت ظاهر شود و کلیک بخورد. اما مسأله ما، بهینه کردن نتایج کوئری های مختلف بصورت مستقل می باشد. یک سند (a) ممکن است در ۱۰۰ کوئری مختلف، کلیک خورده باشد. اما کاربری، یک کوئری متفاوت از این ۱۰۰ کوئری را وارد کند و سند دیگری (b)، از سند (a) مرتبط تر با این کوئری وجو داشته باشد. اگر سند (b) تا به امروز، تعداد کلیک های پایینی داشته باشد، با توجه به نرخ بالای کلیک ها در سند (a)، سند (b) در نتایج، پایین تر از سند (a) نمایش داده می شود. در نتیجه ما به مدل پیچیده تری برای در نظر گرفتن این نوع از فیدبک ها و تاثیر دادنشان در نتایج، نیاز داریم. اگر کاربران، هر باری که با صفحه نتایج یک کوئری روبرو می شدند، درباره نتایج به ما فیدبک می دادند، ما می توانستیم از این داده ها برای آموزش مدلمان استفاده کنیم. اما کاربران به ندرت حاضر می شوند که نظرشان را اعلام کنند. درصورتی که دیتای مورد نیاز ما، واقعا در لاگ فعالیت کاربران در صفحه نتایج بصورت نیمه-پنهان وجود دارد. دیتای مورد نظر ما، دیتای clickthrough نامیده می شود. ساختار این نوع دیتا، به شکل زیر می باشد:

(q, r, c)
q: کوئری کاربر
r: رتبه بندی (رنکینگ) ای که به کاربر ارائه شده
c: مجموعه اسنادی که کاربر روی آنها کلیک کرده

سه تایی مربوط به تصویر بالا، به شکل زیر است:

q: "support vector machine"
r: ["http://svm.first.gmd.de/", "http://jbolivar.freeservers.com/", ..., "http://www.cs.wisc.edu/dmi/lsvm"]
c: ["http://svm.first.gmd.de/", "http://ais.gmd.de/~thorsten/svm_light/", "http://svm.research.bell-labs.com/SVT/SVMsvt.html"]

این داده ها، به ازای هر کوئری که هر کاربر وارد می کند، قابل ثبت هستند. همچنین می توانیم مجموعه c را برای هر کوئری (بصورت unique شده) با در نظر گرفتن فرکانس هر سند، بزرگتر کنیم - به این دلیل که کاربران مختلفی ممکن است کوئری یکسانی را وارد کنند (درباره اشتراک کوئری های کاربران در ادامه حرف می زنیم).

اطلاعاتی که از تحلیل این داده ها بدست می آیند، می توانند به رتبه بندی «نسبی» اسناد در رنکینگ مربوط به یک کوئری، به کار بیایند. این اطلاعات، به شکل زیر قابل استفاده اند:

سه تایی ای که بالاتر برای کوئری "support vector machine" معرفی شد را در نظر بگیرید. با استفاده از الگوریتم زیر، می توانیم اطلاعات مورد نیازمان را استخراج کنیم.

معرفی نمادگذاری: در اینجا منظور از *r، رنکینگ مطلوب (ایده آل) می باشد. و نماد *r> به معنای ترتیب قرار گیری اسناد در رنکینگ ایده آل (*r) می باشد.

پس برای تصویر بالا، نتایج به این شکل خواهند بود.

در نهایت، این pair ها و همچنین feature های استخراج شده مربوطه دیگر (که قبلا درباره آنها حرف زدیم) را به عنوان ورودی به الگوریتم SVM می دهیم و مدلمان را آموزش می دهیم. توجه داشته باشید که مراحل پیچیده تری برای طراحی توابعی که باید بهینه شوند و تعریف پارامتر های بهینه سازی طی می شود که از بیان آنها در این مطلب پرهیز می کنیم.

از این مدل، می توان به عنوان تابع re-ranking استفاده کرد و پس از بازیابی نتایج از موتور ایندکس کننده، با توجه به این تابع، رتبه بندی بهتری را به کاربر ارائه کرد.

کوئری های تکراری

طبق این پست که در بلاگ گوگل منتشر شده، گوگل ادعا می کند که تنها ۱۵ درصد از کوئری هایی که در هرروز دریافت می کنند کوئری هایی هستند که جدیدند!

We see billions of queries every day, and 15 percent of queries are ones we’ve never seen before. Given this scale, the only way to provide Search effectively is through an algorithmic approach. This helps us not just solve all the queries we’ve seen yesterday, but also all the ones we can’t anticipate for tomorrow.

با یک پردازش ساده بروی کوئری های وارد شده در موتور جستجو ترب، در طول یک ماه، به این نتیجه رسیدیم که چیزی نزدیک به ۶۰ درصد کوئری هایی که در طول روز توسط کاربران وارد می شوند، در بازه زمانی یک ماه قبل از هر روز، حداقل ۱ بار تکرار شده اند. این نکته، بسیار جالب توجه است! متاسفانه، این موضوع، هم بُعد خوب دارد و هم بُعد بد. قابلیت پردازش و رتبه بندی آفلاین نتایج مربوط به کوئری های پر طرفدار، می تواند منجر به مهندسی نتایج و نمایش نتایج دلخواه سازمان ها (!!) در نتایج شود. مسأله پرفورمنس و کم کردن بار روی موتور ایندکس کننده، با cache کردن کوئری ها و نتایجشان، آنچنان موضوع مهمی نیست. به این دلیل که این موتور ها، قابلیت مقیاس پذیری بالایی دارند و به راحتی می توانند چندین هزار درخواست در ثانیه را پاسخ دهند. اما این پردازش آفلاین واقعا می تواند به بهبود نتایج کمک کند.

--

ممنون از اینکه توجه کردید و تا انتهای این مطلب را خواندید. امیدوارم توانسته باشم چالش های مربوط به طراحی یک موتور جستجو را تا حد ممکن توضیح داده باشم و این مطلب بتواند نقطه آغاز مناسبی برای افراد و سازمان هایی که با یک موتور جستجو سر و کار دارند و به دنبال بهبود نتایجشان هستند، باشد.

سعی کردم تمامی منابع را بصورت hyperlink در دل مطالب بگنجونم تا برای مطالعه بیشتر و عمیق تر بتوانید از همین نوشته استفاده کنید.