• الصفحة الرئيسية
  • ارائه الگوریتمی مبتنی بر یادگیری جمعی به منظور یادگیری رتبه‌بندی در بازیابی اطلاعات

شارک

عنوان URL للمقالة


رقم المقالة : 202005071458 زيارة : 16139 الصفحة: 67 - 86

نوع المخطوط: المحکّمة

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

الموضوعات :

آزاده شاکری 1 , الهام قنبری 2

1 - هیات علمی دانشگاه
2 - دانشگاه تهران

تاريخ الإرسال : 13 الأحد , جمادى الثانية, 1435 تاريخ الإصدار : 11 الجمعة , ربيع الأول, 1441

الکلمات المفتاحية: یادگیری رتبه‌بندی, یادگیری رتبه‌بندی در بازیابی اطلاعات, یادگیری ماشین, یادگیری جمعی,

ملخص المقالة :

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

المصادر:


نص كامل:


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

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

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

صص: 67- 86

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

 

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

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

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

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

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

 

چکيده 

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

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

 

1-       مقدمه

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

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

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

[1] . Ranking creation

[2] . Ranking aggregation

 

 

 

 

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الگوریتم RankNet با بهره­گیری از یک تابع احتمالی ساده به نام آنتروپی متقابل9برای محاسبه تابع خطا و استفاده از گرادیان در امتداد نزولی10 سعی می­کند تا یک مدل بهینه مبتنی بر شبکه عصبی طراحی می­کند[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-                      معیارهای ارزیابی

معیارهایی که کارایی مدل رتبه­بند را مورد ارزیابی قرار می­دهند، به صورت مقایسه بین لیست مرتب خروجی از مدل با لیست مرتب شده واقعی موجود عمل می­کنند. در زمینه بازیابی اطلاعات، معیارهای ارزیابی متفاوتی از جمله NDCG1، DCG2،MAP3 مورد استفاده قرار می‌گیرند. در این مقاله از سه معیار 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-                      نتایج

برای ارزیابی الگوریتم­ها از اعتبارسنجی متقاطع پنج دسته­ای4 استفاده شده است، به این ترتیب که داده­ها در هر مجموعه داده به 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.

 

37


رایمگ

يقوم نظام رایمگ بتنفيذ جميع عمليات الاستلام والتقييم والحكم والتحرير وتخطيط الصفحة والنشر الإلكتروني للمجلات العلمية.

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية

حقوق هذا الموقع الإلكتروني مملوكة لنظام Rimag Press Management. © 1438-1446

الصفحة الرئيسية| دخول| عنا| اتصل بنا|
[English] [فارسی] [en] [fa]