Manuscript ID : 202005071458 Visit : 16334 Page: 67 - 86

Article Type: Original Research

A new algorithm based on ensemble learning for learning to rank in information retrieval

Subject Areas : Information and Knowledge Technology

1 -
2 - University of Tehran

Received: 2014-04-13 Published : 2019-11-08

Keywords:

Abstract :

Learning to rank refers to machine learning techniques for training a model in a ranking task. Learning to rank has been shown to be useful in many applications of information retrieval, natural language processing, and data mining. Learning to rank can be described by two systems: a learning system and a ranking system. The learning system takes training data as input and constructs a ranking model. The ranking system then makes use of the learned ranking model for ranking prediction. In this paper, a new learning algorithm based on ensemble learning for learning ranking models in information retrieval is proposed. This algorithm iteratively constructs weak learners using a fraction of the training data whose weight distribution is determined based on previous weak learners. The proposed algorithm combines the weak rankers to achieve the final ranking model. This algorithm constructs a ranking model on a fraction of the training data to increase the accuracy and reduce the learning time. Experimental results based on Letor.3 benchmark dataset shows that the proposed algorithm significantly outperforms other ensemble learning algorithms.

References:

Full-Text:

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال هفتم، شماره‌هاي 25 و 26، پاییز و زمستان 1394

صص: 67- 86

$E:\E Drive\logo\iicta Logo0.JPG$

ارائۀ الگوریتمی مبتنی بر یادگیری جمعی به منظور یادگیری رتبهبندی در بازیابی اطلاعات

*الهام قنبری **آزاده شاکری

*دانشجو دکتری، دانشکده مهندسی برق و کامپیوتر، پردیس دانشکده‌های فنی دانشگاه تهران، تهران

**استادیار، دانشکده مهندسی برق و کامپیوتر، پردیس دانشکده‌های فنی دانشگاه تهران، تهران

تاریخ دریافت:24/01/93 تاریخ پذیرش:25/03/94

چکيده

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

واژههای کلیدی: یادگیری در ایجاد رتبهبندی، یادگیری رتبهبندی در بازیابی اطلاعات، یادگیری ماشین، یادگیری جمعی

1- مقدمه

مسائل رتبه‌بندی امروزه در پژوهش‌ها از جایگاه ویژه‌ای برخوردارند و کاربردهای متنوعی به خصوص در بازیابی اطلاعات و موتورهای جستجو دارند. مسائل رتبه‌بندی را می‌توان به دو دسته کلی تقسیم کرد[1]

1. ایجاد رتبهبندی¹: برای یک درخواست وارد شده، یک لیست مرتبشده از پیشنهادات مبتنی بر خصوصیات آن درخواست ارائه میشود.

2. تجمیع رتبهبندی²: برای یک درخواست وارد شده، از چندین لیست مرتب شده از پیشنهادات استفاده کرده و یک لیست مرتب شده جدید از پیشنهادات ارائه میشود.

بازیابی اطلاعات جزو مسائل دسته اول، یعنی ایجاد رتبه‌بندی محسوب میشود. در بازیابی اطلاعات، با ورود هر پرس‌وجوی q از طرف کاربر،سیستم بازیابی اسنادی که

نویسندۀ عهدهدار مکاتبات: آزاده شاکری shakery@ut.ac.ir

[1] . Ranking creation

[2] . Ranking aggregation

شکل1: مراحل بازیابی اطلاعات [1]

مرتبط با پرس‌وجو هستند را از مجموعه D استخراج می‌کند. منظور از اسناد مرتبط، سندهایی هستند که شامل کلمات موجود در پرس‌وجو می‌باشند. بعد از استخراج این اسناد، سیستم بازیابی آن‌ها را رتبه‌بندی می‌کند و درصدی از اسناد با رتبه بالا را به عنوان خروجی به کاربر نشان می‌دهد. مراحل عنوان شده در شکل 1 دیده میشود.

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

در یادگیری رتبهبندی، بخش ایجاد رتبهبندی از اهمیت بیشتری برخوردار است، به گونهای که اکثر مطالعات انجام شده در این بخش صورت گرفته است و اکثر الگوریتمهای پیشنهادی مبتنی بر یادگیری با نظارت¹ هستند.

الگوریتمهایی که تا کنون برای یادگیری رتبهبندی ارائه شده‌اند، به سه بخش روشهای مبتنی بر نقطه²، مبتنی بر جفت³ و مبتنی بر لیست⁴ تقسیم میشوند [1]روشهای مبتنی بر نقطه و جفت، مسائل رتبهبندی را با تغییر در نحوه داده‌ها به مسائل دستهبندی تبدیل میکنند، در حالی که روشهای مبتنی بر لیست، بدون تغییری در داده‌های ورودی، با استفاده از بهینه کردن یک تابع هدف سعی در رتبه‌بندی پرسوجوی جدید مینمایند.

در این مقاله الگوریتمی جدید در بخش ایجاد رتبه‌بندی ارائه شده است. این الگوریتم در دسته روشهای مبتنی بر لیست قرار میگیرد و سعی میکند با کمینه کردن حد بالایی از خطای ایجاد شده به وسیله تعریف تابع هدف، به دقت بالا در رتبهبندی دست پیدا کند. الگوریتم جدید مشابه الگوریتم AdaRank‎0 [2] به صورت تکراری یادگیرهایی ضعیف بر روی دادههای آموزشی که توزیع آنها بر اساس یادگیر قبلی تغییر یافته است، می‌سازد تا بتواند در مجموع تابع خطا را کمینه کند. ایده جدید روش ارائه شده در این مقاله این است که در ساخت یادگیرهای ضعیف، از تمام مجموعه پرسوجو و مستندات مرتبط به آنها استفاده نمی‌شود، بلکه درصدی از آنها که وزن بالاتری دارند مورد استفاده قرار می‌گیرند. استفاده از درصدی از داده‌ها علاوه بر این که باعث افزایش دقت می‌شود، سبب می‌شود زمان اجرای الگوریتم به طور قابل ملاحظه‌ای کاهش پیدا کند و نیاز نباشد در هر تکرار، یادگیری بر روی تمام پرسوجوها انجام شود. با بررسی انجام شده بر روی هفت مجموعه داده در LETOR3 [3]دیده میشود که الگوریتم پیشنهادی هم از لحاظ دقت و هم از لحاظ سرعت نسبت به الگوریتمهای قبلی بهتر عمل می‌کند.

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

2- مروری بر کارهای گذشته

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

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

در سیستم رتبه‌بندی، بر اساس مدل ساخته شده، مجموعه مستندات مرتبط در پاسخ به برای پرس‌وجوی جدید رتبه‌بندی می‌شوند.

در بخش یادگیری، اکثر الگوریتمهای یادگیری ماشین که در دستهبندی دادهها مورد استفاده قرار میگیرند میتوانند در یادگیری رتبهبندی مورد استفاده واقع شوند. یکی از مهم‌ترین الگوریتمهای یادگیری در رتبهبندی که در هر سه دسته الگوریتم‌های مبتنی بر نقطه، جفت و لیست کاربرد دارد، استفاده از الگوریتم‌های یادگیری جمعی است؛ یعنی برای دستهبندی دادهها از چندین دستهبند و ترکیب آنها استفاده میکنند. این الگوریتمها به علت بهرهگیری از چندین دستهبند، در اکثر مواقع نتایج دقیقتر و مقاومتری تولید میکنند، لذا استفاده از این الگوریتمها در یادگیری رتبهبندی مورد توجه واقع شده است.

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

2-1- روش‌های مبتنی بر نقطه

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

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

در [6]مسائل رتبهبندی به صورت دستهبندی چندکلاسه در نظر گرفته شده است و الگوریتم McRank بر این مبنا ارائه شده است. در این الگوریتم اسناد به صورت منفرد در کلاس‌های مختلف که در ساده‌ترین حالت دو کلاس "مرتبط" و "نامرتبط" می‌باشد، قرار می‌گیرند. در این الگوریتم از معیار DCG برای ارزیابی استفاده میشود، به این صورت که دستهبند مناسب، دارای امتیاز بالایDCG خواهد بود. در این روش از ایده امید ریاضی برای تبدیل احتمال کلاسها به امتیاز رتبهبندی استفاده می‌شود. احتمالات برای هر کلاس توسط الگوریتم درخت بوستینگ در امتداد گرادیان محاسبه میگردد.

در [7]مطالعه بر روی دستهبندی به منظور تخصیص امتیازدهی مناسب به هر شی ورودی انجام گرفته است. از این امتیازدهی میتوان برای رتبهبندی نیز استفاده نمود. این الگوریتم با نام Prank، الگوریتمی برخط است که رتبه‌بند خود را براساس مدل‌های موازی پرسپترون⁵می‌سازد. هر مدل توانایی جدا نمودن امتیازات دو همسایگی را از یکدیگر دارا میباشد. تعداد همسایگی‌ها در این روش همان تعداد درجه ارتباط اسناد است، که در ساده‌ترین حالت اسناد در دو همسایگی مرتبط یا نامرتبط قرار می‌گیرند.

الگوریتم MART الگوریتم دیگری در این حوزه از خانواده الگوریتم‌های یادگیری جمعی است، که خروجی آن یک ترکیب خطی وزن‌دار از مجموعه درخت‌های رگرسیون می‌باشد. هر درخت رگرسیون با هدف کمینه کردن تابع خطا در امتداد کاهش گرادیان ساخته می‌شود[11].

الگوریتم OC SVM⁶ یک روش مبتنی بر ماشین بردار پشتیبان با حاشیه⁷ بزرگ برای دستهبندی ترتیبی است[4]در این الگوریتم سعی میشود ابرصفحاتی⁸ به صورت موازی برای جداسازی امتیازدهی همسایهها یاد گرفته شود. هر همسایگی به صورت یک درجه ارتباط بین اسناد در نظر گرفته می‌شود. برای تعریف حاشیه مناسب بین همسایگی‌ها، دو روش در نظر گرفته شده است: یکی در نظر گرفتن حاشیه مساوی برای امتیازدهی به همسایهها و بیشینه کردن این حاشیه و دیگری در نظر گرفتن حاشیه‌های متفاوت برای هر همسایه و بیشینه کردن مجموع این حاشیه‌ها.

2-2- روش‌های مبتنی بر جفت

در روش‌های مبتنی بر جفت، هدف یافتن ترتیب بین هر دو سند برای یک پرس‌وجو است. این روش‌ها بین هر جفت سد با دادن امتیاز بیشتر به سندی که مرتبط‌تر است، اسناد را رتبه‌بندی می‌کنند. برای مثال فرض کنید برای یک پرس‌وجو، سه سند ، و موجود باشد. در این روش‌ها ترتیب دو به دو اسناد مشخص می‌شود. اگر این ترتیب به صورت ، و تشخیص داده شود، رتبه‌بندی نهایی به صورت بدست می‌آید.

در الگوریتم‌های مبتنی بر جفت، رایج‌ترین تابع خطا به صورت ترتیب نادرست دو به دو اسناد در نظر گرفته می‌شود.

یکی از اولین الگوریتمهای موجود در این زمینه برای یادگیری رتبهبندی، RankingSVM است.[8] در این الگوریتم برای دو به دو اسناد یک دسته‌بند بر اساس ماشین بردار پشتبان ساخته می‌شود. سپس از این دسته‌بندها برای رتبه‌بندی اسناد به صورت جفت بهره برده می‌شود.

الگوریتم RankNet با بهرهگیری از یک تابع احتمالی ساده به نام آنتروپی متقابل⁹برای محاسبه تابع خطا و استفاده از گرادیان در امتداد نزولی¹⁰ سعی میکند تا یک مدل بهینه مبتنی بر شبکه عصبی طراحی میکند[9]این الگوریتم به عنوان اولین الگوریتم مبتنی بر یادگیری رتبه‌بندی مورد استفاده موتورهای جستجو واقع شده است.

الگوریتم LambdaRank مشابه با الگوریتم RankNet تعریف می‌شود که از شبکه عصبی برای ساخت مدل رتبه‌بند خود استفاده می‌کند. این الگوریتم گرادیان تابع خطا را با عنوان تابع Lambda تعریف می‌کند. این تابع بر اساس تغییر رتبه اسناد در یک لیست مرتب به منظور بهینه کردن کارایی رتبه‌بند تعریف می‌شود. به عبارتی این روش برای بهینه کردن تابع lambda از شبکه عصبی بهره میبرد[10]

الگوریتم LambdaMART در راستای الگوریتم LambdaRank ارائه شد. این الگوریتم به جای ساخت مدل رتبه‌بند از طریق شبکه عصبی، از روش درختان بوستیگ و یا به عبارتی از الگوریتم MART بهره میبرد[12].کارایی و دقت این روش در مقایسه با روش LambdaRank بالاتر است.

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

الگوریتم دیگر، الگوریتم RankBoost است [14]که مبتنی بر روش بوستینگ عمل میکند. این الگوریتم در هر مرحله سعی می‌کند رتبه‌بند ضعیفی بسازد که کمترین خطا را از نظر تشخیص نادرست ترتیب بین جفت اسناد داشته باشد. بدین منظور در هر مرحله وزن اسناد را به صورت دوبه دو تغییر می‌دهد. سپس با ترکیب این رتبه‌بند‌ها، مدل کلی ساخته می‌شود. رتبه‌بند ضعیف در هر مرحله می‌تواند بر اساس انتخاب مقدار بهترین ویژگی و یا انتخاب حدی بر روی ویژگی‌ها منظور شود.

الگوریتم Ranking Forest الگوریتمی است که برای رتبه‌بندی ارائه شده است و نوعی از الگوریتم یادگیری جمعی است که نتایج مجموعه‌ای از درختان تصادفی را با هم ترکیب می‌کند. این الگوریتم عمل نمونه‌گیری برای ساخت رتبه‌بند را به صورت بگینگ انجام می‌دهد تا ارتباط بین دو درخت رتبه‌بند را کاهش دهد[15]

چهارالگوریتم انتهایی، الگوریتمهایی هستند که در دسته الگوریتمهای مبتنی بر یادگیری جمعی قرار میگیرند.

2-3- روشهای مبتنی بر لیست

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

یکی از مهمترین الگوریتم‌های این دسته، الگوریتمSVM MAP [16] است که از بهینهسازی مستقیم معیار MAP برای ساخت مدل یادگیری استفاده میکند، به این صورت که با استفاده از تابع HINGE حد بالایی از خطا را که بر اساس معیار MAPمحاسبه شده است بهنیه می‌کند. برای بهینه سازی این تابع خطای جدید از الگوریتم یادگیری ماشین بردار پشتیبان بهره برده میشود. این ایده میتواند گسترش پیدا کند، به گونهای که برای هر حد بالایی از خطایی که با استفاده از معیارهای بازیابی اطلاعات ایجاد شود می‌توان از الگوریتم ماشین بردار پشتیبان استفاده نمود.

الگوریتم SoftRank الگوریتم دیگری است که یک راه تخمینی (نرم) برای محاسبه توزیع رتبهبندی ارائه میدهد. به این صورت که امتیاز اسناد را به صورت یک متغیر تصادفی از نوع گوسی در نظر می‌گیرد. توزیع این امتیازات برای هر سند به عنوان مبنایی برای تعریف معیارهای بازیابی اطلاعات به صورت احتمالی می‌شود ، به گونهای که با استفاده از این توزیع میتوان به طور تخمینی معیارهایی مانند NDCG را محاسبه کرد[17]. خوبی این روش در این است که در اکثر معیارهای ارزیابی که توانایی بهینه سازی مستقیم را ندارند، میتوان از این روش استفاده نمود.

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

الگوریتم بعدی AdaRank است[2] این الگوریتم مبتنی بر بوستیگ است، به این صورت که به صورت تکراری یادگیرهای ضعیفی بر روی دادههای آموزشی که توزیع آنها بر اساس یادگیر قبلی تغییر یافته است، میسازد و جمعی از یادگیرهای ضعیف را برای رتبه‌بندی تولید میکند. یادگیر ضعیف در هر مرحله با انتخاب یک ویژگی که با هدف کمینه کردن تابع خطا ( مبتنی بر یکی از معیارهای MAP یا NDCG) صورت می‌گیرد ساخته می‌شود. تفاوت این روش با روشهای جمعی دستهبندی، استفاده از معیارهای ارزیابی به عنوان تابع خطا و روش انتخاب تابع یادگیر ضعیف است.

3- الگوریتم پیشنهادی

در بین الگوریتم‌های مبتنی بر نقطه، جفت و لیست الگوریتمهای موجود در دسته مبتنی بر لیست کارایی بهتری دارند. در این مقاله با الهام از الگوریتمهای موجود در این دسته و با بهرهگیری از یادگیری جمعی، الگوریتمی ارائه خواهد شد که سعی در یادگیری رتبهبندی مستندات دارد.

این الگوریتم الهام گرفته از الگوریتم AdaBoost [19]مبتنی بر بوستیگ و الگوریتم R-AdaBoost[20]می‌باشد. در الگوریتم پیشنهادی مشابه الگوریتم AdaBoost به صورت تکراری یادگیرهای ضعیفی بر روی دادههای آموزشی که توزیع آنها بر اساس یادگیر قبلی تغییر یافته است، ساخته می‌شود، با این تفاوت که در الگوریتم AdaBoost سعی در ساخت دسته بند است، ولی در الگوریتم پیشنهادی هدف ساخت یک تابع رتبهبندی است که بتواند مستندات را در پاسخ به یک پرس‌وجوی خاص مرتب کند. در نهایت با ترکیب این یادگیرهای ضعیف یک تابع رتبهبندی ساخته میشود.

در مرحله ساخت رتبهبندهای ضعیف، مشابه الگوریتم R-AdaBoost که در ساخت دستهبندهایش از درصدی از دادهها

استفاده میشود، به جای استفاده از کل دادههای آموزشی، از درصدی از آنها، مثلا از 20% دادههای آموزشی که وزن بالاتری دارند، استفاده میشود. این پارامتر با R نشان داده میشود و درصد انتخاب تصادفی دادهها را بیان میکند. این ویژگی سبب میشود رتبهبندهای جدید تمرکز خود را بیشتر بر روی داده‌های با وزن بالاتر قرار دهند (دادههایی که به درستی رتبهبندی نشدهاند) و لذا دقت را بالاتر خواهد برد. در الگوریتم AdaRank در ساخت هر رتبه‌بند ضعیف از همه داده‌های ورودی استفاده میشود و این علاوه بر زمانبر بودن الگوریتم، سبب میشود قابلیت یادگیری محلی از بین برود.

روش پیشنهادی مشابه الگوریتم AdaRank مبتنی بر لیست است، لذا دادههای ورودی آن به صورت برداری از ویژگیها و لیست مرتب شده متناظر با آنها به صورت خواهد بود. هدف ساخت یک تابع رتبهبند است که بتواند یک لیست مرتب شده بر حسب ویژگیهای x (ویژگی‌های استخراج شده ازپرسوجوی q و مستند d مرتب شده برای آن) به وجود آورد. برای بررسی ارزیابی این لیست ایجاد شده یک تابع تعریف میشود. تابع رتبهبند باید دقت را بر روی تابع ارزیابی بیشینه کند که این مستلزم کمینه کردن تابع خطا است که در معادله1 تعریف میشود.

معادله (1) ( لیست تمام معادلادت در پیوست شماره 1 ذکر شده است)

تابع نشان دهنده ارزیابی لیست مرتب شده تولید شده توسط تابع یادگیری و لیست اصلی y برای هر عضو از داده آموزشی است. پس به عنوان تابع خطا روی مجموعه داده ورودی محسوب میشود.

حل این تابع خطا با روشهای بهینهسازی مستقیم امکان‌پذیر نخواهد بود، زیرا تابع E در این روش که می‌تواند معیار MAP و یا NDCG باشد ناپیوسته و مشتق ناپذیر است، لذا سعی میشود تاحد بالای آن کمینه شود. بدین منظور مشابه [2] از معادله 2 برای پیدا کردن این حد استفاده میشود. پس مسئله بهینهسازی، تبدیل به معادله 3 میشود، یعنی به جای بهینه کردن تابع خطا از حد بالای آن استفاده میشود.

معادله(2) و (3)

الگوریتم پیشنهادی به صورت تکراری سعی در حل این مسئله جدید بهینه‌سازی می‌کند.

با ورود نمونههای آموزشی و تعداد تکرارها (T)، الگوریتم مشابه الگوریتم AdaRank در هر تکرار یک رتبهبند ضعیف میسازد و با ترکیب خطی این رتبهبندها مدل مرتبسازی را به وجود می‌آورد. تفاوت الگوریتم پیشنهادی با الگوریتم AdaRank در این است که به جای اینکه در هر تکرار از تمام نمونههای آموزشی در ساخت رتبهبند ضعیف بهره گرفته شود، تنها از R% از نمونهها که وزن بالاتری دارند استفاده خواهد شد. این انتخاب سبب میشود تا تمرکز بر روی نمونههایی قرار بگیرد که تا کنون درست رتبهبندی نشدهاند و ضمن کاهش زمان یادگیری، دقت را نیز بالا میبرد.

[1] . Supervised learning

[2] . Pointwise

[3] . Pairwise

[4] . Listwise

[5] . Perceptron

[6] . Ordinal Classification SVM

[7] . Margin

[8] . Hyperplanes

[9] . CrossEntropy

[10] . Gradient Descent

Input: and parameters E and T

Set the Randomness Level R

Initialize

For t = 1,…, T

· Create weak ranker with weighted distribution from the top R percent of the training data S

· Choose

· Create

· Update

End For

Output ranking model:

شکل2: الگوریتم پیشنهادی

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

معادله (4)

4- پیاده سازی و ارزیابی

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

4-1- مجموعه داده‌ها

برای ارزیابی الگوریتم پیشنهادی مجموعه داده LETOR نسخه 3 مورد استفاده قرار میگیرد. مجموعه دادهLETOR ‎0[3]از دادههای TREC توسط محققان ماکروسافت بدست آمده است. بیشتر روشهای یادگیری رتبهبندی از این مجموعه داده برای ارزیابی کارایی روشهایشان استفاده میکنند. برای ساخت نسخه سوم این مجموعه داده از دو مجموعه داده [21]OHSUMED و.GOV استفاده شده است. در مجموعه داده OHSUMED، 106 پرسوجو موجود است که در حدود 152 مستند به هر کدام از آنها تخصیص داده شده است. از این مجموعه داده در کل 45 ویژگی استخراج شده است.

مجموعه داده .GOV از ترکیب نتایج جستجو در سه حوزه وب شامل Topic Distillation(TD)، HomePage Finding(HP) و Named Page Finding(NP) تشکیل شده است که در طی سال‌های 2003 و 2004 از مجموعه TRECجمع‌آوری شده است. تعداد پرسوجوها در هر زیرمجموعه متفاوت است، ولی به طور کلی این مجموعه شامل 350 پرسوجو است.تعداد ویژگیهای استخراج شده از این مجموعه داده برابر با 64 ویژگی است.

4-2- معیارهای ارزیابی

معیارهایی که کارایی مدل رتبهبند را مورد ارزیابی قرار میدهند، به صورت مقایسه بین لیست مرتب خروجی از مدل با لیست مرتب شده واقعی موجود عمل میکنند. در زمینه بازیابی اطلاعات، معیارهای ارزیابی متفاوتی از جمله NDCG¹، DCG²،MAP³ مورد استفاده قرار می‌گیرند. در این مقاله از سه معیار NDCG وP@n و MAP استفاده میشود. علت انتخاب این معیارها، گستردگی استفاده از آنها در بین پژوهشگران این زمینه است.وقتی یک پرسوجوی و مجموعه سندهای تخصیص داده شده به آن به همراه لیست رتبهبندی و برچسب وارد میشود، میتوان معیار DCG برای این پرسوجو در موقعیت k ام آن را به صورت معادله 5 تعریف کرد [21].

معادله (5)

معادله (6)

که در آن به عنوان عامل هنجارسازی معرفی میشود و بیشینه DCG در حالتی است که مستندات در بهترین ترتیب مناسب مرتب شده باشند.

متوسط دقت به صورت معادله 7 تعریف می‌شود[23]

که در آن(0)G یک تابع بهره و (0)D تابع تخفیف بر اساس موقعیت است و نیز (j)نشان دهنده موقعیت مستند در رتبهبندی است . نرمال شده این معیار به نام NDCGشناخته میشود.

معادله (7)

که در آن نشان دهنده سطح ارتباط سند است که دو مقدار 0 یا 1 را به خود اختصاص میدهد. که به آن دقت تا موقعیت سند برای پرسوجوی میگویند به صورت معادله 8 تعریف میشود.

معادله (8)

که در آن نشان دهنده موقعیت سند در رتبهبندی است. برای محاسبه MAP میانگین AP روی مجموعه تمام پرسوجوها محاسبه می‌شود[23]‎0.

معیار P@n که نشان دهنده دقت در n سند بالا است، توسط معادله 8 تعریف میشود که به جای j پارامتر n جایگزین میشود.

4-3- نتایج

برای ارزیابی الگوریتمها از اعتبارسنجی متقاطع پنج دستهای⁴ استفاده شده است، به این ترتیب که دادهها در هر مجموعه داده به 5 قسمت تقسیم شد و سه دسته برای آموزش، یکی برای اعتبار سنجی و دیگری برای تست استفاده شد. برای ارزیابی نتایج، از تمام ویژگیهای موجود در مجموعه داده‌ها استفاده شد. این ویژگیها به صورت هنجار شده می‌باشد.

در ابتدا به طور کامل نتایج پیاده‌سازی برای مجموعه داده OHSUMED نشان داده میشود و سپس نتایج برای مجموعه داده .GOV مورد بررسی قرار می‌گیرد. این نتایج هم به صورت کلی برای این مجموعه داده و هم به صورت مجزا برای 6 زیرمجموعه آن ارائه خواهد شد.

در انتها هم مقایسه‌ای از نظر انتخاب درصد نمونه‌های مورد نظر برای آموزش یادگیر‌های ضعیف (R) بر روی مجموعه دادهها و نیز بررسی تاثیر زمانی اجرای این الگوریتم انجام میشود. این مقایسه به خوبی نشان میدهد که برای رسیدن به MAP بالا نیازی به استفاده صد درصد داده‌ها نیست و با داشتن درصدی از آنها میتوان در کنار کاهش چشم گیر زمان به جواب خوبی رسید.

با اعمال الگوریتم پیشنهادی بر روی مجموعه داده OHSUMED در 5 تکرار، نتایج P@n و MAP برای هر تکه محاسبه شد. این نتایج در جدول 1 دیده میشود.

در جدول 2، نتایج الگوریتم پیشنهادی و الگوریتم پایه آن یعتی AdaRank آمده است. در این جدول دیده میشود که MAP الگوریتم پیشنهادی بر روی این مجموعه داده برابر با 0.4528 است که در مقایسه با الگوریتم پایه آن که برابر با 0.4366 بوده است، رشدی برابر با 3.5 درصد داشته است. روند رشد الگوریتم پیشنهادی در مورد دقت نیز مشاهده می‌شود.

همین روند در مورد معیار NDCG هم صورت گرفت، به این صورت که با اعمال الگوریتم پیشنهادی بر روی مجموعه داده OHSUMED در 5 تکرار نتایج NDCG@K برای هر دسته ذخیره شد. این نتایج در جدول 3 دیده میشود نتایج این جدول نشان می‌دهد که در این معیار نیز الگوریتم پیشنهادی به خوبی عمل کرده و توانسته است برتری مطلقی بر الگوریتم AdaRank پیدا کند. نتایج موجود در جدول 4 به خوبی گواه این مطلب است. همانطور که در مورد مجموعه داده OHSUMED عنوان شد، نتایج بدست آمده از الگوریتم پیشنهادی به خوبی توانسته است در معیارهایMAP، P@K و NDCG@K برتری نسبت به نتایج الگوریتم AdaRank داشته باشد. در نتیجه میتوان گفت این ایده که در هر یادگیری به جای انتخاب همه دادهها، بر روی درصدی از آنها که وزن بالاتری دارند، آموزش صورت بگیرد، میتواند ما را به نتایج بهتری برساند.

علاوه بر مقایسه الگوریتم پیشنهادی با الگوریتم پایه AdaRank، الگوریتم پیشنهادی با الگوریتم‌های دیگر یادگیری رتبه‌بندی که مبتنی بر یادگیری جمعی هستند نیز مورد مقایسه قرار گرفت. به طور خاص الگوریتم پیشنهادی با الگوریتم‌های مطرح دیگری به نام‌هایRankBoost [14]و RankingForest ‎0 [15]و MART [11]از نظر معیار MAP بر روی مجموعه داده OHSUMED مورد

مقایسه قرار گرفت. نتایج این مقایسه درشکل 3 نشان داده شده است.

[1] . Normalized Discounted Cumulative Gain

[2] . Discounted Cumulative Gain

[3] . Mean Average Precision

[4] . 5-fold cross validation

جدول1: نتایج MAP و Precision الگوریتم پیشنهادی در مجموعه داده OHSUMED

MAP	P@10	P@5	P@3	P@1
0.3576	0.3818	0.4727	0.5303	0.6364	Fold1
0.4529	0.5048	0.5333	0.5714	0.7143	Fold2
0.4725	0.5571	0.6752	0.6670	0.7619	Fold3
0.5189	0.5762	0.6095	0.6349	0.7143	Fold4
0.4623	0.5714	0.6381	0.6825	0.7143	Fold5
0.4528	0.5183	0.5858	0.6172	0.7082	Avg.

جدول2 : مقایسه نتایج MAP و Precision الگوریتم پیشنهادی با الگوریتم AdaRankدر مجموعه داده OHSUMED

	P@1	P@3	P@5	P@10	MAP
AdaRank	0.5684	0.5461	0.5053	0.4862	0.4366
Proposed algorithm	0.7082	0.6172	0.5858	0.5183	0.4528

جدول3: نتایج NDCG الگوریتم پیشنهادی در مجموعه داده OHSUMED

@10	@5	@3	@1
0.3797	0.3980	0.4273	0.4848	Fold1
0.4689	0.4864	0.4888	0.5873	Fold2
0.4605	0.5146	0.5181	0.6190	Fold3
0.4885	0.4980	0.5134	0.6190	Fold4
0.5054	0.5477	0.5912	0.6190	Fold5
0.4606	0.4889	0.5078	0.5858	Avg.

جدول4: مقایسه نتایج NDCG الگوریتم پیشنهادی با الگوریتم AdaRankدر مجموعه داده OHSUMED

	@1	@3	@5	@10
AdaRank	0.4731	0.4460	0.4211	0.4263
Proposed algorithm	0.5858	0.5078	0.4889	0.4606

شکل3 : مقایسه نتایج MAP الگوریتم پیشنهادی با سایر الگوریتم‌ها در OHSUMED

همان‌طور که در شکل 3 دیده می‌شود، الگوریتم پیشنهادی در مجموعه داده OHSUMED به MAP بالاتری نسب به سایر الگوریتم‌ها دست یافته است.در گام بعدی آزمایشات، این روند در مورد مجموعه داده .GOV نیز صورت پذیرفت. با اعمال الگوریتم پیشنهادی بر روی این مجموعه داده نتایج P@n و MAP با الگوریتم پایه AdaRank مورد مقایسه قرار گرفت. نتایج بدست آمده در جدول 5 نشان می‌دهد که روند رشد الگوریتم پیشنهادی در مورد این مجموعه داده نیز وجود دارد. همین روند در مورد معیار NDCG هم صورت گرفت و نتایج ارائه شده در جدول 6 نشان دهنده برتری الگوریتم پیشنهادی نسبت به الگوریتم AdaRank است.

نتایج بدست آمده در این مجموعه داده نیز نشان می‌دهد الگوریتم پیشنهادی به خوبی توانسته است در معیارهایMAP، P@K و NDCG@K برتری نسبت به نتایج الگوریتم پایهAdaRank داشته باشد.

در نهایت برای بررسی کارایی الگوریتم پیشنهادی، مقایسه‌ای بین این الگوریتم با الگوریتم‌های دیگر یادگیری رتبه‌بندی که مبتنی بر یادگیری جمعی هستند از نظر معیار MAP صورت گرفت. نتایج برای مجموعه داده استاندارد LETOR3 که از دو مجموعه داده OHSUMED و .GOV است، درجدول 7 نشان داده شده است. همان‌طور که در جدول 7 دیده می‌شود، الگوریتم پیشنهادی در مجموعه داده OHSUMED و .GOV نسبت به دیگر

الگوریتم‌ها به MAP بالاتری دست یافته است.

مجموعه داده .GOV از 6 زیر مجموعه تشکیل شده است. برای بررسی دقیق‌تر، نتایج برای این زیر مجموعه داده‌ها نیز به تفکیک بیان خواهد شد. بدین منظور در گام بعدی آزمایشات، برای هر شش زیر مجموعه داده معرفی شده، کارایی الگوریتم پیشنهادی در مقایسه با الگوریتم‌های پایه یادگیری جمعی در یادگیری رتبهبندی(RankingForest و MART و RankBoost و AdaRank) مورد ارزیابی قرار گرفت و نتایج آن نظر معیار MAP در جدول 8 نشان داده شده است.

نتایج نشان میدهد که در همه این زیر مجموعه دادهها، الگوریتم پیشنهادی از الگوریتم پایه خود، یعنی AdaRank بهتر عمل کرده و به MAP بالاتری رسیده است. این روند در مقایسه با الگوریتم MART نیز مشاهده می‌شود. در مقایسه با الگوریتم‌هایRankBoost و RankingForest، به جز دو مجموعه داده TD2004 و NP2003، الگوریتم پیشنهادی همچنان MAP بالاتری بدست آورده است. لذا برای ادامه کار کارایی این الگوریتم‌ها بر روی دو مجموعه مورد بحث بالا از نظر معیار NDCG هم مورد بررسی قرار می‌گیرد.

در جدول 9 معیار NDCG@K برای مجموعه داده TD2004 از منظر الگوریتم RankBoost و AdaRank و الگوریتم پیشنهادی مشاهده می‌شود.

جدول5 : مقایسه نتایج MAP و Precision الگوریتم پیشنهادی با الگوریتم AdaRankدر مجموعه داده .GOV

	P@1	P@3	P@5	P@10	MAP
AdaRank	0.4950	0.2751	0.1993	0.1305	0.5185
Proposed algorithm	0.5167	0.2811	0.2033	0.1482	0.5369

جدول6: مقایسه نتایج NDCG الگوریتم پیشنهادی با الگوریتم AdaRankدر مجموعه داده .GOV

	@1	@3	@5	@10
AdaRank	0.5033	0.5548	0.5658	0.5800
Proposed Algorithm	0.5167	0.5668	0.5796	0.5894

جدول7: مقایسه نتایج MAP الگوریتم پیشنهادی با سایر الگوریتم‌ها به صورت تجمیع در مجموعه داده LETOR 3

	OHSUMED	.GOV
Ranking Forest	0.4316	0.5209
MART	0.4269	0.4578
RankBoost	0.4411	0.4988
AdaRank	0.4366	0.5185
Proposed Algorithm	0.4528	0.5369

جدول8: مقایسه نتایج MAP الگوریتم پیشنهادی با سایر الگوریتم‌ها در زیر مجموعه داده‌های .GOV

	Ranking Forest	MART	RankBoost	AdaRank	Proposed Algorithm
TD2003	0.2205	0.1877	0.2235	02452	0.2512
TD2004	0.2572	0.1876	0.2178	0.1914	0.2004
NP2003	0.6955	0.6223	0.6495	0.6182	0.6383
NP2004	0.5880	0.5188	0.5559	0.6008	0.6531
HP2003	0.7369	0.7309	0.7204	0.7323	0.7434
HP2004	0.6274	0.4995	0.6259	0.7229	0.7352

جدول9:مقایسه نتایج NDCG الگوریتم پیشنهادی با سایر الگوریتم‌ها در مجموعه داده TD2004

	@1	@3	@5	@10
RankBoost	0.4400	0.3575	0.3228	0.3063
AdaRank	0.3600	0.3390	0.3070	0.2823
Proposed Algorithm	0.4000	0.3622	0.3314	0.3122

جدول10:مقایسه نتایج NDCG الگوریتم پیشنهادی با سایر الگوریتم‌ها در مجموعه داده NP2003

	@1	@3	@5	@10
RankBoost	0.5400	0.6344	0.6784	0.6964
AdaRank	0.5067	0.6065	0.6445	0.6702
Proposed Algorithm	0.5267	0.6181	0.6700	0.6888

در این مجموعه داده دیده می‌شود که همان طور که MAP الگوریتم پیشنهادی از الگوریتم AdaRank بیشتر است، در معیار NDCG@k هم باز الگوریتم پیشنهادی توانسته به خوبی با این الگوریتم رقابت کند. در مورد الگوریتم RankBoost مشاهده می‌شود که در معیار NDCG، الگوریتم پیشنهادی توانسته است به کارایی بهتری دست پیدا کند و به جز در NDCG@1 در بقیه برتری با الگوریتم پیشنهادی بوده است. پس در این مجموعه داده، اگر چه الگوریتم پیشنهادی در MAP نسبت به RankBoost بالاتر قرار نگرفت، ولی در معیار NDCG توانست به خوبی با الگوریتم RankBoost رقابت کند.

همین آزمایش در مورد مجموعه داده NP2003 هم انجام شده است که نتایج در جدول 10 مشاهده می‌شود.

در این مجموعه داده مشاهده می‌شود که همان طور که MAP الگوریتم پیشنهادی از الگوریتم AdaRank بیشتر است، در معیار NDCG@k هم باز الگوریتم پیشنهادی توانسته به خوبی با این الگوریتم رقابت کند. در مورد الگوریتم RankBoost مشاهده می‌شود که در معیار NDCG، باز هم نتوانسته با الگوریتم RankBoost رقابت کند. البته مشاهده می‌شود که این اختلاف بسیار کم است.

شایان ذکر است که این روند زیاد دور از انتظار نیست. زیرا همان‌طور که در[24] نیز عنوان شده است، ماهیت این زیرمجموعه‌ها به علت تعداد کم بودن پرس‌وجوها با سایر زیرمجموعه‌ها متفاوت است.

علاوه بر این در تحلیلی که بر روی مجموعه داده استاندارد LETOR3 انجام گرفت، عنوان شد که دو مجموعه داده TD2004 وNP2003 دارای رفتار یکسانی برای تمام الگوریتم‌‌ها نمی‌باشند. به عبارتی مابقی مجموعه داده‌ها رفتار مشابهی از نظر روند رشد در مورد الگوریتم‌ها نشان می‌دهند و در بازه نزدیک قرار می‌گیرند، ولی این دو مجموعه داده دارای اختلاف MAP بالایی هستند[25].

پس همان‌طور که در جدول 7 و 8 دیده می‌شود، الگوریتم پیشنهادی اگر چه بر روی دو زیر مجموعه موفق نبوده است، اما بر روی مجموعه داده LETOR 3 به صورت تجمیع، به بالاترین MAP نسبت به سایر الگوریتم‌ها دست یافته است.

فاز بعدی، بررسی انتخاب معیار R در مجموعه دادهها است. بدین منظور در مجموعه دادهها، ابتدا آزمایش‌ها بر روی کل مجموعه دادهها با R‌هایی با فاصله 0.1 انجام شد و سپس برای هر مجموعه داده و با استفاده از مجموعه داده Validation بهترین R انتخاب شد. نتایج در شکل‌های 4 تا 10 دیده میشود.

شکل4: نتایج R‌های متفاوت در مجموعه داده OHSUMED

شکل5: نتایج R‌های متفاوت در مجموعه داده TD2003

شکل6: نتایج R‌های متفاوت در مجموعه داده TD2004

شکل7: نتایج R‌های متفاوت در مجموعه داده NP2003

شکل8: نتایج R‌های متفاوت در مجموعه داده NP2004

شکل9: نتایج R‌های متفاوت در مجموعه داده HP2003

شکل10: نتایج R‌های متفاوت در مجموعه داده HP2004

شکل11: مقایسه نسبت هزینه زمانی الگوریتم پیشنهادی و الگوریتم AdaRank

همانطور که در مجموعه داده OHSUMED دیده می شود، برای بدست آوردن MAP بالا استفاده از R=1 یعنی ساخت تابع یادگیر بر روی کل مجموعه دادهها نیاز نیست و تنها بهره‌گیری از درصد کمتری از داده‌ها MAP را افزایش خواهد داد.

از این نمودارها دو نتیجه بسیار مهم گرفته میشود، یکی این که برای بدست آوردن MAP بالا نیاز نیست کل دادهها مورد استفاده قرار بگیرد و میتوان در هر مرحله مطابق الگوریتم پیشنهادی بهترین دادهها نگه داشته شوند و الگوریتم بر روی آنها کار را به جلو ببرد.

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

برای نمونه در شکل 11 نسبت زمان مصرفی الگوریتم پیشنهادی در مقایسه با الگوریتم AdaRank دیده می‌شود. برای نمونه اگر مجموعه داده NP2004 توسط الگوریتم AdaRank زمانی برابر با 1 واحد مصرف کند، این زمان توسط الگوریتم پیشنهادی حدود 0.4 خواهد بود. برای نمایش بهتر، نسبت زمان الگوریتم پیشنهادی به الگوریتم AdaRank مد نظر قرار گرفته است

.همان‌طور که مشاهده میشود در اکثر این مجموعه دادهها، به عنوان نمونه در مجموعه داده OHSUMED، اگر از همه مجموعه داده استفاده شود، نه تنها جواب خوبی حاصل نمیشود، بلکه MAP پایین‌تری به دست می‌آید، در حالی که انتخاب مثلا 20% دادهها جواب مناسبی را بدست خواهد آورد.علت می‌تواند این باشد که اگر از تمام دادهها در ساخت یادگیر ضیعف استفاده شود، با وجود وزندار بودن باز هم تمرکز بر روی تمام دادهها قرار می‌گیرد، ولی اگر از درصدی از دادهها استفاده شود، این تمرکز بر روی همان درصد در ساخت یادگیر خواهد بود.

نتیجه مهم دیگری که از این آزمایش‌ها بدست آمد این بود که بهتر است به جای اینکه از R% مشخص از مجموعه داده‌ها استفاده شود، در هر مرحله از آزمایش بر حسب مجموعه اعتبار سنجی این R انتخاب و بر طبق آن الگوریتم ادامه یابد. مشاهده می‌شود که در اکثر این مجموعه دادهها، نتایج (Result1) به MAP بالاتری دست پیدا کرده است. این نتایج حاصل از انتخاب R مناسب برای هر قسمت از مجموعه داده است.

5- نتيجه‌گيري و کارهای آینده

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

این الگوریتمها به علت بهرهگیری از چندین دستهبند، در اکثر مواقع نتایج دقیقتر و مقاومتری تولید میکنند. لذا استفاده از این الگوریتمها در یادگیری رتبهبندی مورد توجه واقع شده است.

مبتنی بر الگوریتمهای موجود در دسته لیست، الگوریتم پیشنهادی ارائه شد که این الگوریتم به صورت تکراری یادگیرهای ضعیفی بر روی دادههای آموزشی که توزیع آنها بر اساس یادگیر قبلی تغییر یافته است، ساخته می‌شود و جمعی از یادگیرهای ضعیف را برای دستهبندی تولید میکند. در مرحله ساخت رتبهبندهای ضعیف به جای استفاده از کل دادههای آموزشی، از درصدی از آنها استفاده می‌شود. با بررسی این الگوریتم بر روی مجموعه داده LETOR3 مشاهده میشود که این الگوریتم با ساختن رتبهبند بر روی درصدی از دادهها، سبب افزایش دقت و کاهش زمان می‌شود. هدف اصلی ارائه این الگوریتم نیز رسیدن به زمان کمتر در حین نگه داشتن دقت بالا بود. نتایج نشان می‌دهد که الگوریتم پیشنهادی نسبت به الگوریتم پایهAdaRank بر روی مجموعه داده LETOR3 به MAP و NDCG بالاتری دست یافته است.

مقایسه الگوریتم پیشنهادی با الگوریتم‌های RankBoost، Ranking Forest و MART که جزو الگوریتم‌های رتبه‌بندی مبتنی بر یادگیری جمعی هستند، نشان می‌دهد که الگوریتم پیشنهادی اگر چه در برخی از زیرمجموعه‌های .GOV مانند TD2003 و NP2003 به MAP بالاتری دست نیافته است، ولی توانسته است میانگین MAP بدست آمده برای مجموعه .GOV را نسبت به الگوریتم‌های دیگر افزایش دهد. همین روند رو به رشد در مجموعه داده OHSUMED دیده می‌شود.

پس به طور کلی می‌تواند عنوان کرد که الگوریتم پیشنهادی ضمن کاهش زمان توانسته به MAP بالاتری در مجموعه داده LETOR3 دست پیدا کند.از جمله کارهایی که در آینده میتوان انجام داد این است که بتوان روشی برای انتخاب هوشمندانه پارامتر R ایجاد کرد. علاوه بر آن میتوان این روش را در مورد الگوریتمهای دیگر در زمینه یادگیری رتبهبندی هم اعمال کرد و نتایج را بررسی نمود.

پیوست شماره 1 : معادلات ذکر شده در متن مقاله

جدول.jpg

منابع

1.Hang Li, Learning to Rank for Information Retrieval and Natural Language Processing, Synthesis Lectures on Human Language Technologies, Morgan & Claypool Publishers, 2011.

2.Jun Xu and Hang Li, Adarank: a boosting algorithm for information retrieval. In Proceedings of the 30th annual international ACM SIGIR conference on Research and

development in information retrieval, pages 391–398, 2007.

3.Tao Qin, Tie-Yan Liu, Jun Xu, and Hang Li, LETOR: A benchmark collection for research on learning to rank for information

retrieval, Information Retrieval, vol. 13(4), pages 346–374, 2010.

4.AmnonShashua and Anat Levin, Ranking with large margin principle: Two approaches,In Advances in Neural Information ProcessingSystems 15(NIPS 2002), pages 937-944, 2002.

5.Koby Crammer and Yoram Singer, Pranking with ranking, In Advances in Neural Information ProcessingSystems 14(NIPS 2001), pages 641–647, 2001.

6.Ping Li, Christopher Burges, and Qiang Wu, Mcrank: Learning to rank using multiple classification and gradient boosting, In Advances in Neural Information Processing Systems 20(NIPS 2008), pages 897–904, 2008.

7.Koby Crammer and Yoram Singer, Pranking with ranking, In Advances in Neural Information ProcessingSystems 14(NIPS 2001), pages 641–647, 2001.

8.Ralf Herbrich, ThoreGraepel, and KlausObermayer, Large Margin rank boundaries for ordinal regression,Advances in Large Margin Classifiers, pages 115-132, 2000.

9.Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender, Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, pages 89–96, 2005.

10.Christopher J.C. Burges, R. Ragno, and Q.V. Le. Learning to rank with nonsmooth cost functions. In Advances in Neural Information Processing Systems 18(NIPS 2006), pages 395–402, 2006.

11.Jerome .H. Friedman, Greedy function approximation: A gradient boosting machine, The Annals of Statistics, vol. 29, pages 1189-1232, 2001.

12.Qiang Wu, Christopher J. C. Burges, Krysta Marie Svore, and JianfengGao, Adapting boosting for information retrieval measures. Information Retrieval, vol. 13(3), pages 254–270, 2010.

13.ZhaohuiZheng, HongyuanZha, Tong Zhang, Olivier Chapelle, Keke Chen and Gordon Sun, A general boosting method and its application to learning ranking functions for web search. In Advances in Neural Information Processing Systems 20(NIPS 2008), pages 1697–1704, 2008.

14.Yoav Freund, Raj D. Iyer, Robert E. Schapire, and Yoram Singer, An efficient boosting algorithm for combining preferences. The Journal of Machine Learning Research, vol. 4, pages 933–969, 2003.

15.St´ephanCl´emencon, Marine Depecker, Nicolas Vayatis ,Ranking Forests,The Journal of Machine Learning Research, vol. 14,pages 39-73, 2013.

16.YisongYue,Thomas Finley, FilipRadlinski and Thorsten Joachims, A support vector method for optimizing average precision, In Proceedings of the 30th annual international ACMSIGIR conference, pages 271–278, 2007

17.Michael Taylor, John Guiver, Stephen Robertson, and Tom Minka, Softrank: optimizing non-smooth rank metrics. In Proceedings of the international conference on Web search and web data mining, pages 77–86, 2008.

18.Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai and Hang Li, Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129–136, 2007.

19.Y. Freund and R. E. Schapire, A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Journal of Computer and System Sciences, vol. 55(1), pages 119-139, 1997.

20.Binxuan SUN, Jiarong LUO, Shuangbao SHU and Nan YU, Approaches to Combine Techniques Used by EnsembleLearning Methods, Journal of Computational Information Systems, vol. 8(1), pages 305–312, 2012.

21.William R. Hersh, Chris Buckley, T. J. Leone and David H. Hickam, OHSUMED: an interactive retrieval evaluation and new large test collection for research, In Proceedings of the 17rd annual international ACMSIGIR conference on Research and development in information retrieval, pages 192–201, 1994.

22.KalervoJärvelin and JaanaKekäläinen, In evaluation methods for retrieving highly relevant documents, In Proceedings of the 23rd annual international ACMSIGIR conference on Research and development in information retrieval, pages 41–48, 2000.

23.Ellen M. Voorhees and Donna Harman, TREC: Experiment and Evaluation in Information Retrieval, MIT, 2005.

24.Jun Xu, Tie-Yan Liu, Min Lu, Hang Li, Wei-Ying Ma: Directly optimizing

evaluationmeasures in learning to rank, In Proceedings of the 31rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 107-114, 2008.

25.Guilherme de Castro Mendes Gomes, Vitor Campos de Oliveira, Jussara M. Almeida,Marcos André Gonçalves: Is Learning to Rank Worth it? A Statistical Analysis of Learningto Rank Methods in the LETOR Benchmarks. JIDM 4(1), pages 57-66, 2013.

Rimag

Rimag is an integrated platform to accomplish all scientific journal requirements such as submission, evaluation, reviewing, editing, DOI assignment and publishing in the web.

Share To

Article Url

A new algorithm based on ensemble learning for learning to rank in information retrieval

Rimag

Links

Related Centers

Technical Support

Official pages