پروژه پیاده سازی الگوریتم PageRank و بهبود آن برای صفحات دانشگاهی

همانطور که در مطالب قبلی ذکر شدف الگوریتم PageRank الگوریتمی ساختاری است که به صورت آفلاین اجرا شده ورتبه صفحات را محاسبه می کند در این پروژه، هدف ما پیاده سازی اگوریتم برروی صفحات دانشگاهی است که به صورت موردی روی صفحات دانشگاه فردوسی مشهد اعمال شده است.
این پیاده سازی به زبان جاوا و با نرم افزار NetBeans صورت گرفته است.
مرحله اول انجام پروژه، به دست آورد اطلاعات لینک های بین صفحات می باشد. برای این کار، از داده های حاصل از اجرای کرالر استفاده شده است. فایل لینک های حاصل از کرالر که برای قابل نمایش بودن قبلا پارس شده است، فایلی متنی است که به صورت زیر می باشد:
PageUrl inlinks:
fromurl: InlinkUrl
 fromurl: InlinkUrl 
 ما این داده ها را تفکیک کرده وPageUrl ها را داخل لیست قرار دادیم که دارای زیرلیستی از InlinkUrlهایش می باشد.
با توجه به این که برای محاسبه رتبه هر صفحه، درجه خروجی لینک های ورودی اش موردنیاز است، این لینک های خروجی محاسبه شده و داخل لیستی قرار داده شده است.
مرحله دوم پیاده سازی الگوریتم اولیه است که روی داده های حاصل از مرحله قبل اعمال می شود. در این پیاده سازی مقدار d=0.85 در نظر گرفته شده است
مرحله سوم ، با هدف پوشش ضعف الگوریتم PageRank که توجه به صفحات قدیمی تر است صورت گرفته است. برای این کار با الهام از الگوریتم improved PageRank از فاکتور زمان استفاده شده است که معکوس تعداد دفعات مراجعه کرالر به هر صفحه می باشد. ولی با توجه به این که این داده ها در زمان مناسب از داده های کرالر حاصل نشد، برای محاسبه مقداری تصادفی استفاده شد که دقت اعداد را کاهش داد.
در ادامه کار می توان این اعداد را در پیاده سازی به کاربرده و میزان دقت الگوریتم جدید را با الگوریتم قبلی مقایسه کرد. 


معرفی الگوریتم PageRank

   الگوریتم  Page rank:

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


 



الگوریتم HITS (Hypertext Induced Topic Search)

الگوریتم HITS الگوریتمی ساختاری است و رتبه صفحات را براساس لینک های ورودی و خروجی تعیین می کند.HITS ساختار گراف را دریافت کرده و صفحات را در دو دسته Hub و Authority قرار می دهد. Authority صفحاتی هستند که حاوی الاعات مرتبط با پرس و جو می باشند  Hub صفحاتی هستند که به Authority ها لینک دارند. در این الگوریتم، ابتدا صفحات مرتبط با پرسجوی کاربر جمع اوری می شوند و سپس به صورت تکراری صفحات Hub  و Authority مرتبط با ان ها مشخص شده و برای هر صفحه مقدار Ap و Hp تعیین می شود براساس این دو مقدار، رتبه هر صفحه تعیین می شود.
نقطه ضعف این الگوریتم، زمان اجرای کند ان است که برای هر صفحه باید دو مقدار را محاسبه کند.


ترجمه مقاله با عنوان: Learning to Rank: From Pairwise Approach to Listwise Approach

چکیده                                                                

 این مقاله در رابطه با یادگیری رتبه بندی سایت هاست که به طراحی یک مدل یا تابع برای رتبه بندی اشیا می پردازد. رتبه بندی برای بازیابی اسناد، فیلترینگ مشترک و بسیاری کاربردهای دیگر مورد استفاده قرار می گیرد. تاکنون چندین تکنیک برای رتبه بندی پیشنهاد شده است که جفت اشیا را به عنوان "نمونه"(instances) درنظر می گیرد. این تکنیک در این مقاله با عنوان رویکرد pairwise بیان می شود. علارغم مزایای که pairwise دارد این حقیقت را که رتبه بندی وظیفه اش پیشنهاد از لیستی از اشیا است را کتمان می کند. ادعای این مقاله این است که یادگیری رتبه بندی باید رویکرد  listwise را  در لیست اشیای مورد استفاده که "نمونه ها "هستند بپذیرد. مقاله، روشی احتمالی برپایه رویکرد listwise ارائه داده است. به طور خاص، دو مدل احتمالی معرفی شده است با عناوین "احتمال جایگشت"(permutation) و احتمال(Top One)  برای تعیین  listwise loss function for learning . در روش یادگیری از مدل ها و الگوریتم های شبکه های عصبی و گرادیان نزولی استفاده شده است. نتایج نهایی باریابی اطلاعات نمایش می دهد که رویکردlistwise بهتر از رویکرد pairwise عمل می کند.

1.      مقدمه

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

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

اخیرا، یادگیری رتبه بندی با توجه به اهمیتش توجه گسترده ای به اجتماع یادگیری ماشین (learning machine comunity) دارد. روش های موفقیت امیزی براساس رویکردpairwise توسعه یافته و در بازیابی اسناد استفاده شده اند. در این رویکرد جفت هایی از اسناد به عنوان نمونه های یادگیری درنظر گرفته می شوند و مسئله یادگیری رتبه بندی به صورت نوعی از ان دسته بندی مشخص می شود این رویکرد به طور خاص ، جفت اسناد را از لیست های رتبه بندی شده جمع اوری می کند و برای هر جفت سند، نشانه ای که نمایانگر میزان ارتباط دو سند است اختصاص می دهد سپس مسئله یادگیری رتبه بندی را به صورت دسته بندی فرموله می کند. مدل دسته بندی ای برروی داده های نشانه گذاری شده ازمایش می کند. استفاده از مدل های دسته بندی Support Vector Machines (SVM), Boosting, and Neural Network روش های رتبه بندی زیر را ارائه می دهد:

SVM(Herbrich et al., 1999), RankBoost (Freund et al., 1998), and RankNet (Burges et al., 2005).

رویکرد pairwise دارای مزایایی می باشد. اول این که متدولوژی های دسته بندی موجود مستقیما قابل استفاده هستند.دوم، نمونه های ازمایشی جفت اسناد در سناریوهای مشخص را به راحتی می توان به دست اورد. (Joachims, 2002).

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

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

در این مقاله رویکرد listwise  ارائه شده که به جای جفت اسناد از لیست اسناد به عنوان نمونه های یادگیری استفاده می شود.سوال اصلی که مطرح می شود این است که چگونهlistwise loss function  را تعریف کنیم که بیانگر تفاوت لیست خروجی رتبه بندی شده از مدل رتبه بندی و لیست حقیقی باشد.

ما یک مدل احتمالی ارائه داده ایم که listwise loss function را محاسبه می کند. به طور مشخص، امتیاز اسنادی که توسط تابع رتبه بندی تعیین شده و اسنادی که توسط قضاوت صریح یا ضمنی افراد به صورت توزیع احتمال در امده اند را تغییر(ترانسفرم) می دهیم. سپس می توانیم هر metric(سنجه ای) بین توزیع های احتمال را به عنوان تابع فقدان درنظر بگیریم. استفاده از هر دو مدل را برای تغییر(ترانسفرم) درنظر می گیریم یکی با نام احتمال جایگشت و دیگری با نام احتمال top one .

سپس، روش  یادگیری رتبه بندی را به کمک تابع listwise loss function ، مدل شبکه های عصبی و الگوریتم گرادیان نزولی ارائه می کنیم و آن را ListNet می گوییم.

ListNet را در بازیابی اسناد به کار می بریم و نتایج ان را با نتایج حاصل از روش های pairwise مانند رتبه بندیSVM، RankBoost, وRankNet. مقایسه می کنیم. نتایج حاصل از سه مجموعه داده نشان می دهد که روش ما بهتر از روش های موجود می باشد و پیشنهاد می دهد که برای یادگیری رتبه بندی از روش های listwise به جای روش های pairwise استفاده شود.

سهم عمده این مقاله شامل1- پیشنهاد رویکرد Listwise 2- فرموله سازی تابع فقدان Listwise برپایه مدل های احتمالی3- توسعه روش ListNet 4- تایید تجربی اثرات روش.

ادامه مقاله به بخش های زیر پرداخته است: بخش 2 معرفی کارهای مشابه. بخش3- تشریح رویکرد Listwise در یادگیری رتبه بندی. 4- مدل های احتمالی برای تعریف تابع فقدان Listwise در بخش چهارم معرفی شده اند. 5- روش یادگیری ListNet در بخش پنجم توضیح داده شده است.6- در بخش ششم نتایج تجربی گزارش شده اند و 7- در بخش هفتم به نتیجه گیری پرداخته شده است.

2.      کارهای مرتبط

2-1- یادگیری رتبه بندی

یادگیری رتبه بندی عنوانی جدید و محبوب در یادگیری ماشین است. رویکردی گسترده در رابطه با یادگیری رتبه بندی وجود دارد که در این مقاله با عنوان رویکرد pairwise بیان شده است. در مورد رویکردهای دیگر به

 & Singer, 2001; Lebanon & La_erty, 2002) (Shashua & Levin, 2002; Crammer  مراجعه شود.

در رویکرد pairwise ، وظیفه یادگیری به صورت دسته بندی جفت اشیا در دو گروه(رتبه بندی صحیح و رتبه بندی اشتباه) انجام می شود. Herbrich et al. (1999)با این رویکرد و استفاده از تکنیک SVM  مدلی برای دسته بندی پیشنهاد کرد که روش رتبه بندیsvm نام دارد.

Freund et al. (1998) کاری به همان شکل انجام داد اما به تقویت آن پرداخت. Burges et al. (2005)

با پذیرفتن رویکرد، روشی به نام RankNet. را ارائه داد. ان ها برای تابع فقدان از گشتاور پیوندی(CROSS ENTROPY) و برای الگوریتم از گرادیان نزولی به منظور ازمایش مدل شبکه های عصبی استفاده کردند.

یادگیری رتبه بندی و به طور خاص رویکرد pairwise متوالیا برای بازیابی اطلاعات به کار برده شده اند. به عنوان نمونه، Joachims (2002) رتبه بندی SVM را برای بازیابی اسناد به کار برد. او روشی برای اسنتباط جفت اسناد برای ازمایش توسعه داد با استفاده از داده های کلیک شده کاربر. Burges et al. (2005) روش RankNet را برای جستجوی وب در مقیاس بزرگ ارائه داد. Cao et al. (2006) از رتبه بندی SVM و تغییر تابع فقدان برای بازیابی اسناد استفاده کرد. همچنین به (Matveeva et al., 2006; Yu, 2005).مراجعه شود.

2-2- مدل های احتمال برای رتبه بندی

در امارشناسی، توزیع های احتمال برای نمایش رتبه بندی لیستی از اشیا و روش هایی برای تخمین توزیع ها پیشنهاد شده است. به طور مثال کار Luce (1959), Plackett (1975) توزیع های احتمال برروی لیستی از اشیا رتبه بندی شده را تعیین می کند او به علاوه پارامترهایی را برای متمایز کردن توزیع های احتمال معرفی می کند و روشی برای تخمین پارامترها توسعه می دهد. Plackett مدل و روشی برای پیش بینی نتایج انتخابات بیان می کند. در این مقاله، ما از توزیع های احتمال مشابهی استفاده می کنیم. اگرچه ساختار زیربنایی(مانند پارامترها) و استفاده اساسی(مانند انتقال امتیاز به توزیع های احتمال ) مدل ما از مدل Plackett متفاوت است.

3.      رویکرد Listwise

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

در ازمایش، مجموعه پرسجوی  Q={q1,q2,…,q(m)} داده شده است. هر پرسجوی q(i) مرتبط با لیست اسناد  d(i)=d1(i),d2(i),…,dn(i)(i)  مرتبط است که dj(i)  معرف j  امین سند و n(i)  نمایشگر اندازه سند است d(i)  است. همچنین هر لیست سند d(i)  با مجموعه امتیازهای y(i)=y1(i),y2(i),…,yn(i)(i)  در ارتباط است که هر yj(i)  امتیاز پرسجوی q(i)   در سند dj(i)  می باشد. امتیاز  yj(i)  درجه مرتبط بودن سند dj(i)  با پرسجوی q(i)  را نشان می دهد و می تواند امتازی صریح یا ضمنی باشد که توسط انسان داده شده است. به طور مثال، yj(i)  می تواند تعداد کلیک ها برروی سند بازیابی شده dj(i)  حاصل از پرسجوی q(i)  در یک موتور جستجو باشد(Joachims, 2002). فرض بر این است که هر چقدر تعداد کلیک ها بیشتر باشد، میزان ارتباط پرسجوی q(i)  با سند dj(i)  بیشتر است.

 برای هر جفت پرسجو-سند qi,dji,i=1,2,…,m;j=1,2,…,n(i)  یک بردار ویژگیxj(i)=ψ(qi,dji)  ایجاد می شود. برای هر نمونه  لیست ویژگی x(i)=x1(i),x2(i),…,xn(i)(i)  و لیست امتیاز y(i)=y1(i),y2(i),…,yn(i)(i)  متناظر با آن ایجاد می شود. مجموعه آزمایشی به صورت زیر نمایش داده می شود: T={xi,y(i)}mi=1

سپس، تابع رتبه بندی f  با عملکرد زیر ایجاد می شود: برای هر بردار ویژگی xj(i)  (متناظر با سند dj(i) ) امتیاز f(xj(i))  را در خروجی تولید می کند. پس برای هر لیست بردار ویژگی x(i) ، لیست امتیاز z(i)=f(x1i),…,f(xnii)  حاصل می شود. هدف یادگیری با مینیمم سازی تلفات(losses) داده های ازمایشی به دست می آید. i=1mL(yi,z(i))  (1)  که L  تابع فقدان رویکرد Listwise است.

در رتبه بندی زمانی که پرسجوی  qi´  و سند di´  مرتبط با آن داده می شود، بردار ویژگی xi´  را برای آن ها  می سازیم واز تابع رتبه بندی آزمایش شده  برای امتیازدهی به سند di´  استفاده می کنیم. سپس سند را براساس ترتیب نزولی امتیازها رتبه بندی می کنیم. ما مسئله یادگیری که در بالا بیان شد را با عنوان رویکرد Listwise یادگیری رتبه بندی وصف می کنیم.

در مقابل، در رویکرد pairwise یک مجموعه داده آزمایشی T´  از مجموعه T  ایجاد می شود که  هر جفت بردار ویژگی xji  و xki  یک نمونه جدید می سازند به طوری که jk  و اگر yji  بزرگ تر از xki  باشد مقدار +1 به جفت اختصاص می یابد در غیر اینطورت مقدار -1 به جفت اختصاص می یابد. مشخص است که مجموعه آزمایشی T´  مجموعه داده ای از دسته بندی باینری است. یک مدل دسته بندی مانند SVM می تواند ایجاد گردد. همانطور که در بخش 1 توضیح داده شد، رویکرد pairwise علارغم مزایایی که دارد ،شامل نقاط ضعفی نیز می باشد. البته رویکرد Listwise این مشکلات را رفع کرده است که در بخش 6 به صورت کامل بیان می شود.

4.      مدل های احتمال

ما از مدل های احتمالی برای محاسبه تابع فقدان رویکرد listwise در فرمول (1) استفاده می کنیم. به طور خاص، ما لیست امتیازها را با استفاده از مدل های احتمالی که در این بخش بیان می شود به توزیع احتمال نگاشت می کنیم سپس بین دو توزیع احتمال به عنوان تابع فقدان هر اندازه ای را به دست می آوریم. دو مدل با نام های احتمال جایگشت و احتمال top one بیان می شوند.

4.1.            احتمال جایگشت

فرض کنید که مجموعه ای از اشیا با شماره های 1,2,…,n  برای رتبه بندی داریم. جایگشت π برروی اشیا به صورت یک به یک از مجموعه {1,2,…,n}  به خودش تعریف می شود. ما جایگشت را به صورت π1,π2,…,π(n)  می نویسیم. π(j) به شی واقع در مکان j جایگشت اشاره می کند. مجموعه همه جایگشت های ممکن از n شی با Ωn  نمایش داده می شود.

فرض کنید تابع رتبه بندی وجود دارد که n شی را امتازدهی می کند. لیست امتیازها را با s=(s1,s2,…,sn)  نمایش می دهیم که sj  امتیاز j امین شی می باشد. از این پس، گاهی تابع رتبه بندی و لیست امتیازهای حاصل از آن را به جای هم به کار می بریم.

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

تعریف1: فرض می کنیم که π  جایگشت n  شی است و ϕ(.)  یک تابع صعودی و مثبت است. سپس احتمال جایگشت π ، لیست امتیازهای s را به صورت زیر تعریف می کند:

Psπ=j=1nϕ(sπ(j))k=jnϕ(sπk)

 که sπ(j)  امتیاز شی در موقعیت j از جایگشت π  است.

مثالی را در نظر بگیرید که لیست اشیا{1,2,3} با امتیازهای s=(s1,s2,s3)  را داریم. احتمال جایگشت های π= 1,2,3  و π´= 3,2,1  به صورت زیر محاسبه می گردد:

Psπ=ϕ(s1)ϕs1+ϕs2+ϕs3·ϕ(s2)ϕs2+ϕs3·ϕ(s3)ϕs3·

Psπ´=ϕ(s3)ϕs1+ϕs2+ϕs3·ϕ(s2)ϕs2+ϕs1·ϕ(s1)ϕs1·

 

لم2 احتمال جایگشت Psπ  کهπ Ωn از توزیع احتمال برروی مجموعه جایگشت ها را داریم، برای هر π Ωn  داریم Psπ>0  و π ΩnPsπ=1  

 

قضیه3 برای هر دو جایگشت π,π´ Ωn     اگر

(1) πp=π´q, πq=π´p,p<q

(2) πr=π´r,rp,q

(3) sπ(p)> sπ(q)

 

آنگاه  Psπ>Psπ´

قضیه4 برای n شی، اگرs1>s2>…>sn  آنگاه Ps1,2,…,n   بیشترین احتمال جایگشت و Psn,n-1,…,1  کمترین احتمال جایگشت در میان احتمال های جایگشت n شی است.

اثبات درستی قضیه 4 آسان است. اثبات لم 2 و قضیه3 در پی نوشت آورده شده است.

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

با داشتن دو لیست امتیاز، می توانیم در ابتدا، دو توزیع احتمال جایگشت را محاسبه کرده و سپس مسافت بین آن ها را به عنوان تابع فقدان رویکرد Listwise به دست آوریم.از آنجایی که تعداد جایگشت ها n!  است باید محاسبات ، مقاوم باشد.[1] برای مقابله با این مشکل، احتمال top one را بررسی می کنیم.

4.2.            احتمال top one

احتمال top one برای هر شی، احتمال گرفتن بالاترین رتبه با گرفتن امتیاز دیگر اشیا است.

تعریف5 احتمال top one  برای هر شی j به صورت ذیل تعریف می شود:

Psj=π1=j,π ΩnPsπ

 

که Psπ  احتمال جایگشت π  در s  است.

باید گفت که احتمال top one برای شی j برابر با مجموع احتمالات جایگشت جایگشت هایی است که j بالاترین رتبه را دارد.

ممکن است اینطور به نظر برسد که برای محاسبه n احتمال top one نیاز به محاسبه n!  احتمال جایگشت است. قضیه6 نشان می دهد که می توانیم احتمال top one را به روشی دیگر که کارامد است محاسبه کنیم.

قضیه6 برای احتمال top one یعنی Psj  داریم:

 

Psj=ϕ(sj)k=1nϕ(sk)

که sj  امتیاز شی j است و j=1,2,…,n  

لم7 احتمال top one Psj  که j=1,2,…,n  توزیع احتمال مجموعه ای از n شی را تشکیل می دهد.

قضیه 8 برای دو شی j و k اگر sj>sk , jk , j,k=1,2,…,n  آنگاه Psj>Psk

اثبات قضیه6 در پی نوشت آمده است. اثبات درستی لم 7 و قضیه 8 بسیار ساده می باشد.

با داشتن دو لیست امتیاز و استفاده از احتمال top one، هر اندازه ای را برای نمایش مسافت بین دو لیست می توانیم نمایش دهیم. به طور مثال، زمانی که از اندازه Cross Entropy استفاده می کنیم تابع فقدان listwise به صورت زیر می باشد:

Ly(i),z(i)=-j=1npyijlog⁡(pzij)

5.      روش یادگیری: ListNet

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

دوباره، مثال بازیابی سند را در نظر بگیرید. تابع رتبه بندی مبتنی بر مدل شبکه های عصبی ω  را fω  می نامیم. با داشتن بردار ویژگی xj(i) ، امتیاز fω(xj(i))  به آن تعلق می گیرد. برای سادگی، ϕ  در تعریف 1 را تابعی نمایی تعریف می کنیم. سپس احتمال  top one در قضیه 6 را به صورت ذیل بیان می کنیم:

Psj=ϕ(sj)k=1nϕ(sk)=exp(sj)k=1nexp(sk)

در پرس وجوی qi ، تابع رتبه بندی fω  امتیاز zifω=(fω x1(i),fω x2(i),,fω (xn(i)(i)))  را تولید می کند. سپس احتمال top one برای سند dj(i)  به صورت ذیل محاسبه می گردد:

                                                      Pzi(fω)xji=exp(fω xji)k=1niexp(fω xki)

الگوریتم 1 الگوریتم یادگیری ListNet

 

با معیار(اندازه) cross entropy، تلفات(فقدان) برای پرس و جوی q(i)  به شکل زیر است:

Lyi,zi(fω)=-j=1n(i)Pyixj(i)log⁡(Pzifω(xj(i)))          (2)

با مشتق گیری(لطفا به پی نوشت مراجعه شود)، می توانیم گرادیان Lyi,zi(fω)  را با توجه به پارامتر ω  به صورت ذیل به دست آوریم:

ωΔ=Lyi,zi(fω)∂ω=-j=1n(i)Pyixj(i)fω(xj(i))∂ω+1j=1n(i)exp⁡(fω(xj(i)))j=1n(i)exp⁡⁡(fω(xj(i)))fω(xj(i))∂ω             (3)

معادله 3 بعد در گرادیان نزولی مورد استفاده قرار می گیرد.الگوریتم 1 الگوریتم یادگیری ListNet را نمایش می دهد.

توجه کنید که ListNet شبیه RankNet می باشد. تنها تفاوت آن ها در این است که قبلی از لیست اسناد برای نمونه استفاده می کرد اما بعدی از جفت سند برای نمونه استفاده می کند. قبلی از تابع فقدان listwise و بعدی از تابع فقدان pairwise بهره می برد. جالب است بدانید که زمانی که برای هر پرس و جو فقط دو سند موجود است تابع فقدان ListNetدرlistwise برابر با تابع فقدان pairwise در RankNet است.

پیچیدگی زمانی RankNet از مرتبه O(m.nmax2)  است (Burges et al., 2005) که m تعداد پرس وجوهای آموزشی و nmax  ماکسیمم تعداد سندهای هر پرس و جو است. در مقابل  پیچیدگی زمانی ListNet از مرتبه O(m.nmax)  است. بنابراین ListNet کارامدتر از RankNet می باشد.

6.       آزمایش ها(تجربیات)

صحت رتبه بندی ListNet را با سه روش پایه RankNet (Burges et al., 2005)، رتبه بندی SVM  (Herbrich et al., 1999) و RankBoost (Freund et al.,1998) برروی سه مجموعه داده مقایسه می کنیم.توجه داشته باشید که ListNet مبتنی بر مدل احتمال top one می باشد.

برای سادگی، در آزمایش هایمان از مدل شبکه های عصبی خطی و حذف مقدار ثابت b در آن، استفاده کرده ایم:

fωxji=ω,xji  

که 0,0  حاصلضرب داخلی می باشد.[2]

6.1.            مجموعه های داده

ما در آزمایش ها از سه مجموعه داده استفاده می کنیم: TREC مجموعه داده حاصل از جستجوی وب TREC 2003 (Craswell et a.,2003)، یک مجموعه داده معیار برای بازیابی اسناد (Hersh et al.,1994) و CSearch مجموعه داده یک موتور جستجوی تجاری.

TREC شامل صفحات وب crawl شده از دامنه .gov و در اوایل سال 2002 است.

در مجموعه داده، تعداد 1053110 صفحه و تعداد 11164829 hyperlink وجود دارد. همچنین، شامل 50 پرس و جو از topic distillation task  در جستجوی وب TREC 2003  است. داوری ارتباط (مرتبط یا نامرتبط بودن) صفحات وب با پرس و جو داده شده است.حدود 20 مشخصه استخراج شده از هرجفت پرس وجو- سند شامل مشخصات محتوایی و مشخصات hyperlink وجود دارد.

OHSUMED (Hersh et al.,1994) مجموعه ای از اسناد و پرس و جوهای پزشکی است.در مجموع، 16140 جفت سند-پرس وجو که داوری ارتباط روی آن ها انجام شده وجود دارد. داوری ارتباط می تواند کاملا مرتبط، احتمالا مرتبط و یا نامرتبط باشد. مشخصه های استاندارد در بازیابی اسناد(Nallapati,2004) از جفت پرس و جو-سند استخراج شده است. در مجموع 30 مشخصه وجود دارد.

CSearch یک مجموعه داده از موتور جستجوی تجاری است. شامل 25000 پرس وجو است و هر پرس و جو 1000 سند مرتبط دارد. در مجموع حدود 600 مشخصه برای هر جفت پرس و جو-سند وجود دارد شامل مشخصات وابسته و مشخصات مستقل. این مجموعه داده 5 سطح داوری ارتباط، فراهم می کند که در بازه 0( عدم تطابق) تا 4(تطابق کمل) است.

برای دریافت لیست رتبه بندی صحیح(ground truth rank list!!!!) برای هر پرس و جو،به سادگی، از*ranks*رتبه نمونه ها برای تهیه لیست استفاده می کنیم. (مانند امتیاز داوری مجزا)[3]

دز ارزیابی کارایی رتبه بندی، دو معیار ارزیابی بازیابی اطلاعات را اتخاذ می کنیم: افزایش تجمعی نزولی نرمال(NDCG) (Jarvelin & Kehanainen,2000) و دقت میانگین ناچیز (MAP) )(Baeza-Yates & RibeiroNet,1999). NDCG برای اندازه گیری دقت رتبه بندی در زمانی که بیشتر از دو سطح داوری امتیاز وجود دارد طراحی شده است. در MAP دو سطح فرض می شود: مرتبط و نامرتبط. در محاسبات MAP برای OHSUMED ما ارتباط قطعی را به عنوان مرتبط و دو سطح دیگر را نامرتبط فرض می کنیم. برای CSearch فقط از NDCG استفاده می کنیم.

6.2.            دقت (صحت) رتبه بندی

برای TREC و OHSUMED هر مجموعه داده را به 5 زیرمجموعه تقسیم می کنیم و اعتبارسنجی متقاطع 5 لایه را اعمال می کنیم. در هر آموزش، سه لایه برای آزمایش یکی برای اعتبارسنجی و یکی برای تست مورد استفاده قرار می گیرد. در RankNet و ListNet مجموعه اعتبارسنجی در هر لایه برای تعیین تعداد تکرارها استفاده می شود. در رتبه بندی SVM، برای همانگ کردن ضریب C و در RankBoost برای انتخاب تعداد یادگیرندگان ضعیفweak learners استفاده می شود. دقتی که در این بخش گزارش می دهیم در 5 آزمون میانگین گیری شده اند.

شکل 1و جدول 1 نتایج TREC را نشان می دهد. می بینیم که ListNet از همه جهت بهتر از سه روش پایه RankNet، رتبه بندی  SVM و RankBoost عمل می کند. مخصوصا، ListNet برای NDCG@1  و NDCG@2 بیش از 4 امتیاز مثبت4 point gain دارد که حدود 10 درصد، بهبود نسبی است.

شکل 2 و جدول 1 نتایج OHSUMED را نشان می دهد. دوباره  ListNet از همه جهت از RankNet و RankBoost بهتر عمل می کند. همچنین، ListNet از جهت NDCG@1 ، NDCG@2،  NDCG@4 و MAP بهتر از رتبه بندی SVM عمل می کند.

CSearch مجموعه داده بزرگی است بنابراین از اعتبارسنجی متقاطع استفاده نمی کنیم. در مقابل، به صورت تصادفی، یک سوم داده ها را برای آموزش، یک سوم برای اعتبارسنجی و یک سوم برای تست انتخاب می کنیم.شکل 3 نتایج ListNet، RankNet و RankBoost را نشان می دهد. دوباره، ListNet از همه نظر بهتر از RankNet و RankBoostعمل می کند. از آنجایی که اندازه داده های آموزشی بزرگ است، قادر به استفاده از رتبه بندی SVM با ابزار  SVMlight (Joachism,1999) نبودیم.

6.3.            مباحثه(بررسی)discussion

علت بهتر بودن روش ListNet در رویکرد listwise از ورش های رویکرد pairwise مانند RankNet، رتبه بندی  SVM و RankBoost را بررسی کردیم.

همانطور که در بخش 1 توضیح داده شد، برای رویکرد pairwise تعداد جفت سندها در پرس و جوهای مختلف متغیر است.در نتیجه، مدل آموزشی، ممکن است به پرس و جوهای با جفت سند بیشتر گرایش داشته باشد. ما گرایشات همه مجموعه داده ها را مشاهده کردیم.به طور مثال، جدول 2 توزیع تعداد جفت سندها را برای هر پرس و جو در OHSUMED نشان می دهد. می بینیم که توزیع به صورت مورب است: بیشتر پرس و جو ها تعداد کمی جفت سند دازند( به عنوان مثال، کمتر از 5000) در حالیکه تعداد کمی از پرس و جوها تعداد جفت سند زیادی دارند( به طور مثال، بیشتر از 15000). در رویکرد listwise ، تابع فقدان برای هر پرس و جو تعریف می شود و مشکل وجود ندارد. این، یک دلیل کارایی بهتر ListNet را نشان می دهد.

در واقع، رویکرد pairwise از تابع فقدان pairwise استفاده می کند که از نظر مجاورت با معیارهای کارایی NDCG و NMAPبسیار ضعیف است. در مقابل، تابع فقدان listwise در رویکرد listwise معیارهای کارایی بهتری استفاده می کند. این، دلیل دیگری بر بهتر بودن ListNet از RankNet و ... است. برای اثبات درستی ادعا، فرایند بهینه سازی دو روش را بررسی می کنیم.

ارتباط بین تابع فقدان استفاده شده در ListNet و RankNet و معیار NDCG در فاز یادگیری را با هم مقایسه می کنیم. توجه داشته باشید که تفاوت عمده بین دو روش تابع فقدان آن هاست. نتایج حاصل از استفاده مجموعه داده TREC در شکل های 4 و 5 نشان داده شده است. ازشکل ها، متوجه می شویم که فقدان pairwise حاصل از RankNet با NDCG ارتباط معکوس ندارد. از تکرار 20 تا تکرار 50، NDCG@5 افزایش می یابد درحالیکه فقدان pairwise حاصل از RankNet کاهش می یابد. اگرچه، بعد از تکرار 60،  NDCG@5 افت می کند و فقدان pairwise نیز همچنان کاهش می یابد. در مقابل، فقدان listwise کاملا با  NDCG ارتباط معکوس دارد. به طور خاص، از تکرار 20 تا تکرار 50 تابع فقدان listwise کاهش می یابد و متعاقبا NDCG@5 افزایش می یابد. بعد از تکرار 50، فقدان listwise به حداقل می رسد در حالیکه NDCG@5 همگرا می شود. به علاوه، فقدان pairwise کندتر از فقدان listwise همگرا می شود که بیانگر این است که RankNet در آموزش تکرارهای بیشتری نسبت به ListNet اجرا می کند. در نتایج ارزیابی شده در MAP نیز، روند مشابهی دیده می شود.

نتیجه می گیریم که رویکرد listwise در یادگیری رتبه بندی مؤثرتر است.

7.      نتایج

در این مقاله، رویکرد جدیدی برای یادگیری رتبه بندی ارائه کردیم. نشان دادیم که استفاده از این رویکرد بهتز از رویکرد قبلی pairwise می باشد. در رویکرد listwise برای نمونه به جای استفاده از جفت اشیا از لیست اشیا استفاده می کنیم.

مسئله اصلی در رویکرد listwise استفاده از تابع فقدان listwise می باشد. در این مقاله، از روش احتمالی برای اتخاذ آن استفاده کردیم. به طور خاص، از احتمال جایگشت و احتمال top one برای انتقال امتیازهای رتبه بندی به توزیع های احتمال استفاه کردیم. سپس، می توانیم هر اندازه بین توزیع های احتمال( مانند cross entropy) را به هنوان تابع فقدان listwise درنظر بگیریم.

سپس، روش یادگیری مبتنی بر این رویکرد را با استفاده از مدل شبکه های عصبی و گرادیان نزولی توسعه دادیم. نتایج تجربی حاصل از سه مجموعه داده که روش ما بهتر از روش های موجود pairwise مانند RankNet، رتبه بندی SVM و RankBoost عمل می کند. بنابراین، استفاده از رویکرد listwise برای یادگیری رتبه بندی پیشنهاد می شود.

کارهای آینده شامل کشف کارایی تابع هدف دیگر در کنار cross entropy و کارایی مدل رتبه بندی دیگر به جای مدل شبکه های عصبی خطی است. همچنین رابطه بین تابع فقدان listwise و معیارهای کارایی مانند NDCG و MAP استفاده شده در بازیابی اطلاعات را بررسی خواهیم کرد.



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

[2] توجه داشته باشید که معادله  (3) و الگوریتم 1 در هر تابع پیوسته رتبه بندی قابل استفاده است.

[3]  این فقط یک رویکرد برای امتیاز داوری مجزا می باشد. اگر داده pairwise در دسترس باشد( مانند clics-through که توسط Joachims(2002) ارائه شده است) نیاز به استفاده از رویکرد دیگری داریم مانند ایجاد داده listwise از داده pairwise ( به طور مثال استفاده از الگوریتم ارائه شده توسط  Cohen et al.(1998)). این می تواند کار بعدی ما باشد.


ترجمه مقاله با عنوان: AdaRank: الگوریتمی افزایشی برای بازیابی اطلاعات

چکیده

در این مقاله مسئله یادگیری رتبه بندی برای بازیابی سند مورد مطالعه قرار می گیرد. در این کار، یک مدل، با مقداری داده آموزشی به صورت خودکار ایجاد می شود و سپس برای رتبه بندی اسناد مورد استفاده قرار می گیرد. کارایی این مدل با معیارهای کارایی مانند MAP(Mean Average Precision)( دقت میانگین ناچیز) و NDCG(Normalized Discounted Cumulative Gain)  (سود تجمعی افزایشی نرمالسازی شده) بررسی می شود. در وضع مطلوب، یک الگوریتم یادگیری باید یک مدل رتبه بندی را که می تواند معیارهای کارایی را متناسب با داده های آزمایشی بهینه سازی کند ارائه دهد. روش های موجود فقط قادر به آموزش مدل های یادگیری با مینیمم کردن توابع فقدان مرتبط با معیارهای کارایی هستند. به طور مثال، رتبه بندی SVM و RankBoost(رتبه بندی افزایشی) مدل های رتبه بندی را با مینمم سازی خطاهای دسته بندی در جفت نمونه ها، آموزش می دهند. برای کنار آمدن با این مسئله،  یک الگوریتم یادگیری جدید در فریم ورک boosting ارائه می دهیم که می تواند تابع فقدان تعریف شده برروی معیارهای کارایی  را مینیمم کند. الگوریتم ما با نام AdaRank شناخته می شود که به صورت متوالی، رتبه بندهای ضعیف”weak rankers” براساس داده های آموزشی دوباره وزن گرفته می سازد و در پایان، آن ها را به صورت خطی برای تولید پیش بینی رتبه بندی ترکیب می کند. ثابت  می کنیم که فرایند آموزشی AdaRank دقیقا همانی است که معیارهای کارایی افزایش دهنده استفاده می کنند. نتایج تجربی برروی 4 مجموعه داده نمونه نشان می دهد که AdaRank به طور قابل ملاحظه ای از روش های پایه مانند BM25، رتبه بندی  SVM و RankBoost بهتر عمل می کند.

1.      مقدمه

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

چندین روش یادگیری رتبه بندی برای بازیابی سند ارائه شده و مورد استفاده قرار گرفته اند. به طور مثال: Herbrich et al. [13] یک الگوریتم یادگیری برای رتبه بندی برپایه ماشین های برداری پشتیبان با نام رتبه بندی SVM ارائه داده است. Freund et al. [8] رویکردی مشابه استفاده کرده و یادگیری  را با  کمک boosting اجرایی کرده است که رياRankBoost نام دارد. همه روش های موجود استفاده شده برای بازیابی سند[2,3,8,13,16,20]  برای بهینه سازی تابع فقدان کمی مرتبط با معیارهای بازیابی اطلاعات طراحی شده اند نه برای توابع فقدان کاملا مبتنی بر معیارها. به طور مثال، رتبه بندی SVM و RankBoost  مدل های رتبه بندی را با مینیمم سازی خطاهای دسته بندی جفت نمونه ها آموزش می دهند.

در این مقاله، هدف، ارائه الگوریتم یادگیری جدیدی است که معیارهای کارایی استفاده شده در بازیابی سند را بهینه کند.(به حد کمال برساند). با الهام گرفتن از کار AdaBoost برای دسته بندی[9] الگوریتمی افزایشی برای بازیابی اطلاعات به نام AdaRank ارائه داده ایم. AdaRank مانند مدلش از ترکیب خطی رتبه بندهای ضعیف استفاده می کند. در یادگیری با تکرار فرایند وزن دهی دوباره نمونه ها ی آزمایشی، یک رتبه بند ضعیف تولید می کند و وزن آن را محاسبه می کند.

نشان می دهیم که الگوریتم AdaRank می تواند تابع فقدان نمایی مبتنی بر معیارهای کاریابی IR را مکررا بهینه نماید. حد پایین کارایی داده های آزمایشی داده شده است که نشان می دهد صحت رتبه بندی مبتنی بر معیارهای کارایی می تواند در طول فرایند آموزش توسعه یابد.

AdaRank چندین مزیت دارد: سهولت اجرا، صحت نظری، بهره وری در آموزش و دقت بالای رتبه بندی. نتایج تجربی بیانگر این است که AdaRank از روش های پایه مانند BM25، رتبه بندی SVM وRankBost برروی 4 مجموعه داده مانند OHSUMED، WSJ، AP و Gov بهتر عمل می کند.

تنظیم مدل های رتبه بندی با استفاده از داده های آموزشی معین و یک معیار کارایی کاری مشترک در بازیابی اطلاعات است[1]. هرچقدر تعداد ویژگی های مدل رتبه بندی و تعداد مجموعه های داده  بیشتر می شود تنظیم مشکل تر می شود. از دیدگاه IR، AdaRank یک روش یادگیری ماشین برای تنظیم مدل رتبه بندی است.

اخیرا، بهینه سازی مستقیم معیارهای کارایی در یادگیری، عنوان تحقیقاتی بسیار خوبی است. چندین روش دسته بندی[17] و رتبه بندی [5,19] ارائه شده است. AdaRank می تواند یک روش یادگیری ماشین مبتنی بر رویکردی متفاوت برای بهینه سازی مستقیم معیارهای کارایی باشد.

ادامه مقاله به شرح ذیل می باشد: بعد از خلاصه کارهای مرتبط در بخش 2، جرئیات الگوریتم ارائه شده  AdaRank در بخش 3 شرح داده شده است. نتایج تجربی و بررسی ها در بخش 4 بیان می شوند. بخش5 نتیجه گیری و کارهای آینده را بیان می کند.

2.      کارهای مرتبط

2.1.            بازیابی اطلاعات

مسئله کلیدی در بازیابی اطلاعات، رتبه بندی است. به خصوص، این که چگونه مدل رتبه بندی ایجاد کنیم که اسناد را براساس ارتباطشان با پرس و جو مرتب کند. یک روش معمول در IR برای تنظیم پارامترهای مدل رتبه بندی براساس داده های نشانه گذاری شده و یک معیار کارایی وجود دارد[1]. به طور مثال: روش های جدید BM25 [24] و LMIR(مدل های زبانی برای بازیابی اطلاعات)[18,22] پارامترهایی برای تنظیم دارند. هرچقد مدل های رتبه بندی پیچیده تر می شوند( با استفاده از ویژگی های بیشتر) و داده های نشانه گذاری بیشتری در دسترس قرار می گیرند، چگونگی تنظیم یا آموزش مدل های رتبه بندی چالش برانگیزتر می شود.

روش های جدید یادگیری ماشین در ساخت مدل رتبه بندی استفاده شده و نتایج امیدبخشی حاصل شده است. به طور مثال: Joachims [16] از رتبه بندی SVM برای بازیابی سند استفاده کرد. او داده کلیک شده را برای استنتاج داده آموزشی و ایجاد مدل، بهینه کرد.  Cao et al.[4] با تغییر تابع Hinge Loss، رتبه بندی  SVM را با بازیابی اطلاعات برای داشتن شرایط بهتر IR وفق داد. به طور مشخص، تابع Hinge Loss را معرفی کردند که خطاهای ابتدای لیست رتبه بندی و خطاهای پرس وجوهای شامل اسناد بازیابی شده کمتر را به شدت کاهش می دهد. Burges et al[3] از آنتروپی نسبی(Relative  به عنوان تابع فقدان Entropy) و از گرادیان نزولی به عنوان الگوریتم ، برای آموزش مدل شبکه های عصبی در رتبه بندی بازیابی اسناد استفاده کرده است. عنوان روش RankNet می باشد.

2.2.            یادگیری ماشین

سه عنوان مرتبط با کار ما در یادگیری ماشین وجود دارد: یادگیری رتبه بندی، boosting و بهینه سازی مستقیم معیارهای کارایی.

یادگیری رتبه بندی تولید خودکار تابع رتبه بندی برای امتیازدهی به نمونه ها و سپس رتبه دهی نمونه ها براساس امتیازها است. چند رویکرد برای حل این مسئله ارائه شده است. یک  رویکرد عظیم در یادگیری ماشین، انتقال آن به دسته های باینری جفت نمونه ها است. این رویکرد pairwise با بازیابی اطلاعات همخوانی خوبی دارد و بنابراین در IR زیاد استفاده می گردد. نمونه روش های های رویکرد، شامل رتبه بندی SVM [13]، RankBoost [8] و RankNet [3] است.برای رویکردهای دیگر رتبه بندی به [2,11,31] رجوع شود.

در رویکرد رتبه بندی pairwise، وظیفه یادگیری به صورت مسئله دسته بندی جفت نمونه ها در دو دسته فرموله می شود(رتبه بندی شده صحیح و رتبه بندی شده غلط). در عمل مشخص است کاهش خطاهای دسته بندیدر جفت نمونه ها برابر با ماکسیمم سازی حد پایین MAP [16] است. در این معنا، روش های موجود مانند رتبه بندی SVM، RankBoost و RankNet فقط توابع فقدان با ارتباط ناچیز با معیارهای کارایی IR را مینیمم می کنند.

Boosting یک تکنیک عمومی برای بهبود دقت الگوریتم های یادگیری ماشین است. ایده پایه boosting  ساخت مکرر یادگیرنده های ضعیف توسط وزن دهی دوباره داده های آموزشی و سپس ترکیب یادگیرنده های ضعیف است به طوریکه مجموع کارایی  حداکثر باشد. Freund و Schapire اولین الگوریتم boosting شناخته شده را با نام AdaBoost ارائه دادند.(Adaptive Boosting) [9] که برای دسته بندی باینری طراحی شده است( پیش بینی 0-1). بعدها Schapire و Singer، نسخه عمومی AdaBoost را معرفی کردند که یادگیرنده های ضعیف در پیش بینی می توانند امتیازهای مطمئنی نسبت به انتخاب 0-1 داشته باشند[26].  ضمیمه هایی برای حل مسئله دسته بندی چند کلاسه[10,26]، بازگشت[7] و رتبه بندی [8] ارائه شده اند. در حقیقت AdaBoost الگوریتمی است که ابتکارانه یک مدل خطی مبتنی بر داده آموزشی با مینیمم سازی تابع فقدان نمایی می سازد [26]. این مقاله یک روش boosting برای رتبه بندی به طور خاص برای IR ارائه می دهد.

اخیرا، تعدادی از نویسندگان، مدیریت بهینه سازی مستقیم معیارهای کارایی چند متغیره در یادگیری را ارائه کرده اند. به عنوان نمونه، Joachims [17]، روش SVM اراده داده است برای بهینه سازی مستقیم معیارهای کارایی چند متغیره غیرخطی مانند معیار F1  در دسته بندی. Cossock  و Zhang [5] روشی برای بهینه سازی تقریبی معیارDCG [15] کارایی رتبه بندی یافته اند. Metzler et al. [19] روشی برای ماکسیمم سازی مستقیم اندازه های مبتنی بر رتبه براساس اصل یادگیری چندجانبه ارائه کرده است. همچنین، تلاش AdaRank بر بهینه سازی مستقیم معیارهای کارایی چند متغیره است اما مبتنی بر رویکرد دیگری می باشد. AdaRank به دلیل به کارگیری تابع فقدان نمایی مبتنی بر  معیارهای کارایی IR و تکنیک های boosting منحصربه فرد است.

3.AdaRank

3.1. چارچوب کلی

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

 

فرض کنید Y={r1,r2,…,rl}  مجموعه رتبه هاست که l  تعداد رتبه ها را نشان می دهد.ترتیب بین رتبه ها به صورت rl>rl-1>…>r1  است.

در آموزش، مجموعه پرس و جوی Q={q1,q2,…,qm}  داده شده است. هر پرس و جوی qi  مرتبط با لیست اسناد بازیابی شده di={di1,di2,…,di,n(qi)}  است و yi={yi1,yi2,…,yi,n(qi)}  لیست نشانه ها است که n(qi)  اندازه لیست di  و yi  است و dij  نمایانگر j امین سند از di  است و yij∈Y  رتبه سند dij  است. بردار مشخصه xij=ψ(qi,dij)∈X  برای هر جفت پرسجو- سند ایجاد می شود. بنابراین مجموعه داده به صورت S=qi,di,yi,i=1,…,m  می باشد.

هدف یادگیری تولید تابع رتبه بندی f:X→R   است که برای هر پرسجو المان های لیست اسناد مرتبط با آن امتیاز مربوطه را دریافت می کنند و سپس براساس امتیاز، رتبه بندی می شوند. به طور خاص، جایگشت صحیح π(qi,di,f)  برای هر پرسجوی qi  و اسناد مرتبط با آن و تابع رتبه بندی  f  تولید می شود. اگر di={di1,di2,…,di,n(qi)}  توسط لیست صحیح {1,2,…,nqi}  شناسایی شود و سپس جایگشت π(qi,di,f)  به صورت پوشا از  {1,2,…,nqi}  به خودش، تعریف می شود. از πj  برای نمایش مکان  آیتم j استفاده می شود. فرایند یادگیری، تابع فقدان را مینیمم می کند که نشانه اختلاف بین جایگشت π(qi,di,f)  و لیست امتیازها برای همه پرس وجوها است.

در مقاله، مدل رتبه بندی به صورت ترکیب خطی رتبه بندهای ضعیف تعریف می شود: fx=t=1Tathtx  که htx  رتبه بند ضعیف و at  وزن آن  و T تعداد رتبه بندهای ضعیف است.

در بازیابی اطلاعات، معیارهای کارایی مبتنی بر پرسجو برای بررسی صحت تابع رتبه بندی استفاده می شود. با معیارهای مبتنی بر پرسجو، معیار تعریف شده برروی لیست رتبه بندی شده اسناد مرتبط با پرسجو را به دست می آوریم. این معیارها شامل MAP، NDCG، MRR(Mean Reciprocal Rank)،Take All) WTA(Winners  و دقت @n[1, 15] می باشد. ما تابع عمومی Eπqi,di,f,yi∈[-1, +1]  را برای نمایش معیارهای کارایی استفاده می کنیم. اولین آرگومان E، جایگشت π  تولید شده با استفاده از تابع f  و di  است. دومین آرگومان، لیست رتبه های yi  تعیین شده توسط انسان است. E توافق بین π  و yi  را اندازه گیری می کند. جدول 1 خلاصه آنچه شرح دادیم را می دهد.

سپس، به عنوان مثال معیار کارایی، تعریف MAP و NDCG را ارائه می کنیم. در پرسجوی qi  و با لیست رتبه های yi  و جایگشت πi  برروی سند di  دقت میانگین به صورت زیر به دست می آید:

که  yij  مقدار 0 و 1 می گیرد و مرتبط بودن یا نبودن را نشان می دهد و Pi(j)  صحت در مکان dij  را نشان می دهد.

 

  πi(j)  مکان dij  را نشان می دهد.

در پرسجوی qi  و با لیست رتبه های yi  و جایگشت πi  برروی سند di ، NDCG در مکان m به صورت ذیل تعریف می شود:

ni  ثابت نرمالسازی است و بهترین رتبه بندی در موقعیت m امتیاز 1 دارد.

3.2. الگوریتم

براساس الگوریتم دسته بندی AdaBoost، الگوریتمی جدید که تابع فقدان مبتنی بر معیارهای کارایی IR را بهینه می کند ارائه کرده ایم. این الگوریتم با نام AdaRank شناخته می شود و در شکل 1 نمایش داده شده است.

AdaRank  مجموعه آموزشی   S=qi,di,yi,m=1,…,m  را در ورودی می گیرد و تابع معیار کارایی E و تعداد تکرار آن را به عنوان پارامتر می گیرد. AdaRank، T مرتبه اجرا می شود و هر مرتبه یک رتبه بند ضعیف ht(t=1,…,T)  تولید می شود. در پایان، مدل رتبه بندی f با ترکیب خطی رتبه بندهای ضعیف را در خروجی می دهد.

در هر مرتبه، AdaRank توزیع وزن پرسجوها در داده های آموزشی را نگهداری می کند. توزیع وزن ها در مرتبه t   با Pt  نشان داده می شود و وزن i امین پرسجوی آموزشی qi  با Pt(i)  نمایش داده می شود. AdaRank  در ابتدا، وزن یکسانی به پرسجوها اختصاص می دهد. در هر مرتبه وزن پرسجوهایی که با ft  خوب رتبه بندی نشده اند افزایش می یابد، تا اینجا مدل ایجاد می شود. در نتیجه، یادگیری در مرتبه بعد برروی تولید رتبه بندهای ضعیف که می توانند روی رتبه بندی آن پرسجوهای سخت کار کنند تمرکز می کند.

در هر مرتبه، یک رتبه بند ضعیف ht  مبتنی بر داده های آموزشی و توزیع وزن Pt ساخته می شود. صحت یک رتبه بند ضعیف با معیار کارایی E  وزن دهی شده با Pt  بررسی می شود.

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

هرمرتبه که رتبه بند ضعیف ht  ساخته می شود، AdaRank وزن αt>0  به آن اختصاص می دهد. به طور مستقیم، αt  اهمیت ht  را اندازه گیری می کند.

یک مدل رتبه بندی  ft  در هر مرتبه توسط ترکیب خطی رتبه بندهای ضعیف ساخته شده h1,…,ht  با وزن های α1,…,αt    تولید می شود. سپس ft برای به روزرسانی توزیع Pt+1  استفاده می شود.

3.3. تجزیه و تحلیل نظری

تلاش الگوریتم های یادگیری رتبه بندی موجود برای مینیمم سازی تابع فقدان مبتنی بر جفت نمونه(جفت سند) است. در مقابل، تلاش AdaRank بر بهینه سازی تابع فقدان مبتنی بر پرسجو است. علاوه براین، در AdaRank  تابع فقدان براساس معیارهای عمومی کارایی IR تعریف شده است. معیارها می توانند MAP، WTA، NDCG،  MRR  و یا هر معیاری که در بازه [-1, +1]  باشد. بعد، دلیل این مورد را توضیح می دهیم.

به طور ایده آل، می خواهیم دقت رتبه بندی مبتنی بر معیار کارایی در داده های آموزشی، ماکسیمم شود:

 

که  F  مجموعه توابع ممکن برای رتبه بندی است. این برابر با مینیمم سازی تلفات(فقدان) در داده های آموزشی است.

بهینه سازی مستقیم فقدان،به این دلیل که E تابعی ناپیوسته است دشوار است؛ بنابراین، رسیدگی به آن دشوار است.

برای هر x∈R ، e-x≥1-x  برقرار است. ما از ترکیب خطی رتبه بندهای ضعیف برای مدل رتبه بندی استفاده می کنیم:

مینیمم سازی در (6) به صورت زیر است:

H  مجموعه ممکن برای رتبه بندهای ضعیف است. αt  وزن مثبت است و

چندین روش برای محاسبه ضرب αt  و ht  در نظر گرفته می شود. طبق ایده AdaBoost، در AdaRank از رویکرد مدل افزایشی forward stage-wise  [12] و الگوریتم شکل1 استفاده می کنیم. ثابت می شود که حدپایین تری در دقت AdaRank برروی داده های آموزشی وجود دارد.

قضیه 1 دردقت رتبه بندی AdaRank  روی داده های آموزشی ، حدود زیر برقرار است:

اثبتات قضیه در پیوست آمده است. قضیه نشان می دهد که دقت رتبه بندی به عنوان معیار کارایی پیوسته می تواند بهبود یابد. تا زمانیکه شرط زیر برقرار است.

3.4. مزایا

AdaRank  روش قدرتمند ساده ای است. همچنین روشی است که می تواند از دیدگاه نظری تعدیل( تصدیق) شود. همچنین در مقایسه با روش های یادگیری موجود مانند Ranking SVM، RankBoost و RankNet مزایای بیشتری دارد.

اول این که AdaRank   می تواند هر معیار کارایی را به کار گیرد به شرطی که معیار، مبتنی بر پرسجو و در بازه [-1, +1] باشد. توجه کنید که اکثر معیارهای IR این شرایط را دارند. در مقابل، روش های موجود، فقط تابع فقدان دارای ارتباط ناچیز با معیارهای IR را مینیمم می کنند  [16].

دوم، فرایند یادگیری AdaRank  کارامدتر از الگوریتم های یادگیری موجود است. پیچیدگی زمانی AdaRank  از مرتبه O(k+T.m.nlogn)  است. K تعداد مشخصه ها( ویژگی ها)، T تعداد مرتبه تکرارها، m تعداد پرسجو ها در داده آموزشی و n تعداد اسناد پرسجو است. پیچیدگی زمانی  RankBoost از مرتبه O(T.m.n2)  [8] است.

سوم، AdaRank  چارچوب موجه تری نسبت به روش های دیگر برای انجام رتبه بندی دارد. به طور خاص، نمونه ها مطابق با پرسجوها هستند در حالیکه در دیگر روش ها، نمونه ها مطابق با جفت اسناد هستند. در نتیجه نقایص ذیل که در روش های دیگراست را ندارد. الف) روش های موجود فرض می کنند که جفت اسناد از پرسجوهای یکسان مستقل از هم توزیع شده اند. در واقعیت، این حالت وجود ندارد و AdaRank   این مشکل را ندارد. ب) رتبه بندی اسناد مرتبط تر در بالای لیست برای بازیابی اطلاعات، حیاتی است. روش های موجود، نمی توانند بر بالای لیست تمرکز کنند [4]. چندین روش برای اصلاح این مسئله ارائه شده است  [4] اگرچه به نظر نمی رسد که کاملا این مسئله را حل کنند. در مقابل، AdaRank    به راحتی می تواند بر بالای لیست تمرکز کند زیرا معیارهای کارایی از رتبه بندی های دلخواه برای هر سند مربوطه در بالای لیست استفاده می کنند. ج) در روش های موجود، تعداد جفت اسناد در پرسجوهای مختلف متفاوت است که باعث تولید مدل های برپایه پرسجو و با جفت اسناد بیشتر می شود [4]. AdaRank  این ضعف را ندارد چون از پرسجوها به جای اسناد برای واحدهای پایه استفاده می کند.

3.5. تفاوت ها با AdaBoost

AdaRank  الگوریتمی افزایشی(boosting) است. بنابراین مشابه AdaBoost می باشد اما چندین تفاوت آشکار با آن دارد.

ابتدا، نوع نمونه ها متفاوت است. AdaRank   از پرسجوها و لیست اسناد مطابق با آن ها به عنوان نمونه استفاده می کند. نشانه های داده آموزشی لیست رتبه هاست( سطح ارتباط). AdaBoost از بردار مشخصه به عنوان نمونه استفاده می کند. نشانه در داده های آموزشی -1 و +1 هستند.

دوم، معیارهای کارایی متفاوت هستند. در AdaRank   معیار کارایی معیاری کلی( عمومی) است که برروی لیست اسناد و لیست رتبه هر پرسجو تعریف شده است. در AdaBoost معیار کارایی، معیاری خاص برای دسته بندی باینری است که margin [25] معرفی می شود.

سوم، شیوه به روزرسانی وزن ها متفاوت است. در AdaBoost ، توزیع وزن ها در نمونه های آموزشی طبق توزیع متداول و کارایی یادگیرنده های ضعیف کنونی محاسبه می شود. در AdaRank  محاسبه ، طبق کارایی مدل رتبه بندی تولید شده در اینجا که در شکل 1 است صورت می گیرد. توجه کنید که  AdaBoost می تواند با روش به روزرسانی وزن ارائه شده در AdaRank  مطابقت یابد. برای AdaBoost هردو برابرند (cf., [12] page 305). اگرچه این برای AdaRank   صدق نمی کند.

3.6. ساحت رتبه بند ضعیف

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

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

4.      نتایج تجربی

نتایج را برای تست کارایی AdaRank در چهار مجموعه داده OHSUMED، WSJ، AP و .Gov بررسی می کنیم.

4.1. تنظیم نتایج

رتبه بندی SVM [13, 16] و RankBoost [8] به عنوان خطوط پایه در نتایج انتخاب شده اند زیرا روش های جدید یادگیری رتبه بندی هستند. به علاوه،BM25 [24] به عنوان پایه استفاده می شد به عنوان روش جدید  IR.

در AdaRank پارامتر T در طول آزمایش به صورت خودکار تعیین می شود؛ مخصوصا زمانی که در دقت رتبه بندی به عنوان معیار کارایی بهبودی صورت نمی گیرد و تکرار متوقف می شود.همانطور که معیارهای E، MAP و NDCG@5 استفاده شدند. نتایج AdaRank با استفاده از معیارهای MAP و NDCG@5 مطرح شده در آموزش به ترتیب با عنوان AdaRank.MAP و AdaRank.NDCG معرفی شده اند.

4.2.           نتایج حاصل از مجموعه داده OHSUMED

در این نتایج، از مجموعه داده OHSUMED [14] برای تست کارایی AdaRank استفاده کردیم. این مجموعه شامل 348566 سند و 106 پرسجو است. در مجموع، 16140 جفت پرسجو- سند برای هر داوری ارتباط وجود دارد. داوری ارتباط یا d (definitely relevant) یا p (possibly relevant) یا n (not relevant) هستند. داده ها در نتایج زیادی در IR [4, 29] استفاده شده اند.

برای مشخصه ها، آن هایی که در بازیابی سند[4]  مورد استفاده اند انتخاب شده اند. شکل 2 مشخصه ها را نمایش می دهد.برای مثال: tf (term frequency)، idf ( inverse document frequency)،  dl (document length) و ترکیب آن ها به عنوان مشخصه تعیین شده اند. امتیاز BM25 هم یک مشخصه است. کلمات توقف حذف شده و کلمات اصلی بررسی شده اند.

پرسجوها را به صورت تصادفی در 4 زیرمجموعه قرار می دهیم و نتایج اعتبارسنجی متقاطع 4 لایه را بررسی می کنیم. پارامترها را برای BM25 در هر مرحله تنطیم می کنیم و برای مرحله بعد به کار می گیریم. نتایج شکل 2 در 4 مرحله تعدیل شده اند. در محاسبات MAP از رتبه d  برای مرتبط بودن و دو رتبه دیگر برای نامرتبط بودن استفاده می کنیم.در شکل 2 می بینیم که AdaRank.MAP وAdaRank.NDCg از BM25، رتبه بندی SVM و RankBoost از نظرهمه معیارها  بهتر عمل می کنند. تست کارامدی را با نام t-test برای بهبود AdaRank.MAP از BM25، رتبه بندی SVM و RankBoost با استفاده از MAP بررسی می کنیم. نتایج نشان می دهد که همه بهبودها از نظر آماری کارامد هستند (p-value < 0.05). همچنین، از t-test برای بهبود AdaRank.NDCg از BM25، رتبه بندی SVM و RankBoost با استفاده از NDCG@5 اعمال می کنیم که آن هم از نظر آماری کارامد است.

4.3.           نتایج حاصل از مجموعه داده های WSJ و AP

در این نتایج از مجموعه داده های AP  و WSJ از توالی بازیابی TREC ad-hoc برای تست کارایی AdaRank استفاده کردیم.   WSJ شامل 74520 مقاله از ژورنال Wall Street از سال 1990تا 1992 است  و AP شامل 158240 مقاله  Associaterd Press از سال های 1988 و 1990  است.200 پرسجو از عناوین TREC انتخاب شده اند.( شماره 101 تا شماره 300) هر پرسجو تعدادی سند مرتبط به همراه نشانه هایشان(مرتبط و نامرتبط) دارد.طبق [28] پرسجوهای دارای کمتز از 10 سند مرتبط، نادیده گرفته می شوند.جدول 3 نتایج آمارس دو مجموعه داده را نشان می دهد.

به روش مشابه در بخش 4.2، از ویژگی های لیست شده در جدول 2 برای رتبه بندی استفاده می کنیم. همچنین از نتایج اعتبارسنجی 4 لایه استفاده می کنیم. نتایج شکل های 3 و 4 در 4 مرحله برروی مجموعه های AP و WSJ تعدیل(میانگین گیری) شده اند. از شکل 3 و 4 نتیجه می گیریم که AdaRank.MAP و AdaRank.NDCG برروی مجموعه داده های AP و WSJ از نظر همه مشخصه ها( ویژگی ها)  بهتر از BM25، رتبه بندی SVM و RankBoost عمل می کنند. همچنین ازمون t را روی AdaRank.MAP و AdaRank.NDCG اعمال می کنیم. نتایج نشان می دهد که از نظر MAP همه بهبودها کارامد هستند(p-value < 0.05) . اما از نظر NDCG@5 برخی بهبودها کارامد هستند ولی روی هم رفته امتیازات NDCG خیلی بالا هستند.

4.4.           نتایج حاصل از مجموعه داده .Gov

در این نتایج، از مجموعه TREC .Gov برای تست کارایی AdaRaknk در بازیابی وب استفاده شده است. مجموعه از crawl در دامنه .gov در اوایل سال 2002 به دست امده است. آن ها 1053110 صفحه وب  با 11164829 هایپرلینک هستند. 50 پرسجو در جستجوی عناوین TREC 2003 [6] استفاده شده است. حقایق پایه برای پرسجوها توسط کمیته TREC با داوری باینری ارائه شده که یا مرتبط و یا غیرمرتبط هستند.تعداد صفحات مرتبط برای پرسجوهای متختلف متفاوت است. ( از 1 تا 86)

ما 14 مشخصه از جفت پرسجو-سند استخراج کرده ایم.جدول 4 لیست مشخصه ها را نمایش می دهد که خروجی های الگوریتم های  معروفی هستند. این مشخصه ها با مشخصه های جدول 2 متفاوت هستند زیرا وظیفه آن ها متفاوت است.

دوباره ازنتایج اعتبارسنجی متقاطع 4 لایه استفاده کردیم.نتایج حاصل از 4 مرحله در شکل 5 آورده شده است. از نتایج می فهمیم که AdaRank.MAP و AdaRank.NDCG از نظر همه مشخصه ها بهتر از روش های پایه عمل می کنند. تست بهبود AdaRank.MAP و AdaRank.NDCG  از BM25، رتبه بندی SVM و RankBoost را بررسی می کنیم. برخی بهبودها خیلی کارامد نیستند زیرا فقط 50 پرسجو در آزمایشات استفاده شده و تعدا پرسجوها خیلی کم است.

4.5.           بحث

دلایل بهتر بودن AdaRank از روش های پایه برروی مجموعه داده OHSUMED را بررسی کردیم.

اول، بررسی کردیم که AdaRank کارایی بیشتری از رتبه بندی SVM و RankBoost دارد. نرخ خطای بین جفت رتبه بندی های متفاوت تولید شده توسط رتبه بندی SVM، RankBoost، AdaRank.MAP و AdaRank.NDCG را باهم مقایسه کردیم. نتایج تعدیل شده در 4 مرحله اعتبارسنجی متقاطع 4 لایه در شکل 6 نمایش داده شده است. از ‘d-n’ برای نمایش جفت های بین کاملا مرتبط و نامرتبط، از ‘d-p’ برای جفت های بین احتمالا مرتبط و کاملا مرتبط، از ‘p-n’ برای جفت های بین احتمالا مرتبط و نامرتبط استفاده می کنیم. از شکل 6 متوجه می شویم که AdaRank.MAP و AdaRank.NDCG خطای کمتری درمورد ‘d-n’ و ‘d-p’ دارند که مرتبط با بالای لیست رتبه بندی هستند و با اهمیت می باشند. دلیل آن، تمرکز این دو روش بر بالای داده های آموزشی با بهینه سازی MAP و NDCG@5 می باشد.

همچنین، آماری از جفت اسناد هر پرسجو تهیه کردیم( برای مرحله 1). پرسجو ها  براساس جفت اسناد مرتبطشان در گروه های مختلف دسته بندی می شوند. شکل 7 توزیع گروه های پرسجو را نشان می دهد. برای مثال، ‘0-1k’ گروه پرسجوهای دارای تعداد جفت اسناد بین 0 تا 999 می باشد. می بینیم که تعداد جفت اسناد برای پرسجوهای مختلف متفاوت است. سپس دقت AdaRank.MAP و RankBoost در رابطه با MAP برای هر گروه پرسجو بررسی می کنیم. نتایج در شکل 8 آورده شده است. می بینیم که میانگین MAP در AdaRank.MAP نسبت به RankBoost دو رتبه بالاتر است. علاوه براین، AdaRank.MAP در پرسجوهای دارای تعداد جفت سند کمتر از RankBoost بهتر عمل می کند.مثلا(‘0-1k’ , ‘1k-2k’ , ‘2k-3k’). نتایج نشان می دهد که AdaRank.MAP از تولید مدل با پرسجوهای دارای تعداد جفت سند بیشتر دوری می کند. برایAdaRank.NDCG نیز نتایج مشابهی مشاهده می شود.

 

 

آزمایشی بررسی می کنیم برای اینکه ببینیم AdaRank توانایی بهبود دقت رتبه بندی براساس معیارها با استفاده از معیارها را دارد. از  مدل رتبه بندی AdaRank.MAP و AdaRank.NDCG و دقت آن ها برروی مجموعه داده براساس هردو MAP و  NDCG@5 استفاده می کنیم. نتایج هر مرحله بررسی شده است. شکل 9 و 10 نتایج را نشان می دهند.می بینیم که AdaRank.MA براساس MAP و AdaRank.NDCG براساس NDCG@5 بهتر عمل می کنند. همچنین نتایج نشان می دهد که AdaRank می تواند کارایی رتبه بندی براساس معیارها با استفاده از معیارها را افزایش دهد.

سرانجام، سعی می کنیم که قضیه 1 را اثبات کنیم که دقت رتبه بندی  براساس معیار رتبه بندی نیز به همراه آن اثبات می شود و تا زمانی که e-δmint1-φt2<1  برقرار است.به عنوان مثال، شکل 11 منحنی یادگیری AdaRank.MAP را براساس MAP در طول فاز آموزش در یک مرحله از اعتبارسنجی متقاطع نشان می دهد.  از شکل می بینیم که دقت رتبه بندی AdaRank.MAP به طور پیوسته بهبود می یابد تا زمانیکه به اوج می رسد. نتیاج مطابق با قضیه 1 می باشد.

5.      نتیجه گیری و کارهای آینده

در این مقاله، الگوریتمی جدید با نام AdaRank برای مدل یادگیری رتبه بندی در بازیابی سند ارائه دادیم. در مقابل روش های موجود، AdaRank تابع فقدانی که براساس معیارکارایی تعریف شده را بهینه می کند. این روش، از تکنیک boosting در مدل آموزشی استفاده می کند و سه مزیت را پیشنهاد می دهد: پیاده سازی آسان، صحت نظری، کارایی آموزش و دقت بالا در رتبه بندی. نتایج حاصل برروی چهار مجموعه داده، کارایی بهتر AdaRank نسبت به BM25، Ranking SVM و RankBoost را نشان می دهد. کارهای آینده شامل آنالیز نظری برروی خطاهای عمومی و دیگر ویژگی های الگوریتم AdaRank می باشد و ارزیابی تجربی الگوریتم ازجمله مقایسه با دیگر الگوریتم هایی است که معیارکارایی را بهینه می کنند. 


معرفی چند الگوریتم رتبه بندی گوگل

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

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

 

الگوریتم مرغ مگس خوار(Hummingbird)

علت نامگذاری این الگوریتم، دقت و سرعت بالای آن است.

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


معرفی رتبه بندی صفحات وب

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