اس‌وی‌ام رتبه‌بندی
در یادگیری ماشین، یک SVM رتبه‌بندی گونه‌ای از الگوریتم ماشین بردار پشتیبانی است که برای حل مسائل رتبه‌بندی خاص (از طریق یادگیری رتبه‌بندی) استفاده می‌شود. الگوریتم SVM رتبه بندی توسط Thorsten Joachims در سال 2002 منتشر شد. هدف اصلی این الگوریتم بهبود عملکرد یک موتور جستجوی اینترنتی بود. با این حال، مشخص شد که رتبه بندی SVM همچنین می تواند برای حل مسائل دیگری مانند Rank SIFT استفاده شود.
الگوریتم رتبه‌بندی SVM یک تابع بازیابی یادگیری است که از روش‌های رتبه‌بندی زوجی برای مرتب‌سازی تطبیقی نتایج بر اساس «مرتبط بودن» آنها برای یک پرس‌وجو خاص استفاده می‌کند. تابع رتبه بندی SVM از یک تابع نگاشت برای توصیف تطابق بین یک عبارت جستجو و ویژگی های هر یک از نتایج ممکن استفاده می کند. این تابع نگاشت هر جفت داده (مثلاً یک پرس و جوی جستجو و صفحه وب کلیک شده) را به یک فضای ویژگی تصویر می‌کند. این ویژگی‌ها با داده‌های کلیکی مربوطه ترکیب می‌شوند (که می‌تواند به عنوان یک واسط برای ارتباط یک صفحه برای یک جستجوی خاص عمل کند) و سپس می‌تواند به عنوان داده‌های آموزشی برای الگوریتم رتبه‌بندی SVM استفاده شود.
به طور کلی، رتبه بندی SVM شامل سه مرحله در دوره آموزش است:فرض کنید formula_1مجموعه داده ای است که شامل formula_2 عنصر formula_3 است. formula_4 یک روش رتبه بندی است که به formula_1اعمال می شود. سپس formula_6 در formula_1را می توان به صورت یک ماتریس دودویی formula_8 نشان داد. اگر رتبه formula_3 از رتبه formula_10 بالاتر باشد، یعنی:
formula_11
آنگاه درایه متناظر با آن را در ماتریس مقدار 1 و در غیر این صورت مقدار 0 قرار می‌دهیم. تای کندال همچنین به ضریب همبستگی رتبه تای کندال اشاره دارد، که معمولاً برای مقایسه دو روش رتبه‌بندی برای یک مجموعه داده استفاده می‌شود.
فرض کنید formula_12 و formula_13 دو روش رتبه بندی باشد که برای مجموعه داده های formula_1 اعمال می شود، تای کندال بین formula_12 و formula_16 را می توان به صورت زیر نشان داد: formula_17
که در آن formula_18 تعداد جفت های همخوان است و formula_19 تعداد جفت های ناسازگار (وارونگی) است. یک جفت formula_20 و formula_21 همخوان است اگر در هر دو روش formula_22 و formula_23 رتبه بندی formula_20 و formula_21 یکسان باشد. در غیر این صورت ناسازگار خواهند بود.
کیفیت بازیابی اطلاعات معمولاً با سه معیار زیر ارزیابی می شود:برای یک پرس و جو خاص به یک پایگاه داده، فرض کنید formula_26 مجموعه ای از عناصر اطلاعاتی مرتبط در پایگاه داده و formula_27 مجموعه ای از عناصر اطلاعاتی بازیابی شده باشد. سپس سه اندازه گیری فوق را می توان به صورت زیر نشان داد:
formula_28
که در آن formula_29 دقت فراخوانی است.
فرض کنید formula_30 و formula_31 به ترتیب روش های رتبه بندی مورد انتظار و پیشنهادی یک پایگاه داده باشند، کران پایین میانگین دقت روش formula_31 را می‌توان به صورت زیر نشان داد.
formula_33
که در آن formula_19 تعداد درایه های متفاوت در قسمت بالای قطر اصلی ماتریس هایformula_30 و formula_31 و formula_37 تعداد عناصر مرتبط در مجموعه داده است.
فرض کنید formula_38 عنصر یک مجموعه داده آموزشی که در آن formula_39 بردار ویژگی و formula_40 برچسب (که دسته formula_39 راامشخص می‌کند) است. یک طبقه بندی کننده SVM معمولی برای چنین مجموعه داده ای می تواند به عنوان راه حل مسئله بهینه سازی زیر تعریف شود.
formula_42
حل مسئله بهینه سازی فوق را می توان به صورت ترکیبی خطی از بردارهای ویژگی formula_43 نشان داد.
formula_44
که در آن formula_45 ضرایبی هستند که باید تعیین شوند.
فرض کنید formula_46 تای کندال بین روش رتبه بندی مورد انتظار formula_30 و روش پیشنهادی formula_31 باشد، می توان ثابت کرد که به ماکسیمم کردن formula_46 به مینیمم کردن کران پایینِ میانگینِ دقت formula_31 کمک می‌کند.منفی formula_46 را می توان به عنوان تابع زیان برای به حداقل رساندن کران پایین میانگین دقت formula_31 انتخاب کرد.formula_53
که در آن formula_54 توزیع آماری formula_30 به پرس و جو خاص formula_56 است.از آنجایی که تابع زیان مورد انتظار قابل پیاده سازی نیست، تابع زیان تجربی زیر در عمل برای داده های آموزشی انتخاب می شود.
formula_57
formula_58 پرس و حوی iid روی یک پایگاه داده اعمال می شوند و هر پرس و جو با یک روش رتبه بندی مطابقت دارد. مجموعه داده های آموزشی formula_58 عنصر دارد. هر عنصر حاوی یک پرس و جو و روش رتبه بندی مربوطه است.
یک نگاشت formula_60 مورد نیاز است که هر پرس و جو و عنصر پایگاه داده را به فضای ویژگی مورد نیاز متناظر کند. سپس هر نقطه در فضای ویژگی با روش رتبه بندی با رتبه خاصی برچسب گذاری می شود.
نقاط تولید شده توسط داده های آموزشی در فضای ویژگی قرار دارند که حاوی اطلاعات رتبه (برچسب ها) نیز می باشد. از این نقاط برچسب زده شده می توان برای یافتن مرز (طبقه بندی) که ترتیب آنها را مشخص می کند استفاده کرد. در حالت خطی، چنین مرزی (طبقه‌بندی کننده) یک بردار است.
فرض کنید formula_3 و formula_10 دو عنصر در پایگاه داده هستند و می‌نویسیم formula_63 اگر رتبه از formula_3 بالاتر از formula_10 در روش رتبه بندی معین formula_66 باشد. فرض کنید بردار formula_67 کاندیدای طبقه بندی کننده خطی در فضای ویژگی باشد. آنگاه مسئله رتبه بندی را می توان به مسئله طبقه بندی SVM زیر ترجمه کرد. توجه داشته باشید که یک روش رتبه بندی با یک پرس و جو مطابقت دارد.
formula_68
مسئله بهینه سازی فوق با مسئله طبقه بندی SVM کلاسیک یکسان است، به همین دلیل است که این الگوریتم Ranking-SVM نامیده می شود.
بردار بهینه formula_69 که توسط نمونه آموزشی به دست آمده است، چنین است:
formula_70
بنابراین تابع بازیابی را می توان بر اساس چنین طبقه بندی بهینه ای تشکیل داد.
برای پرس و جوی جدید formula_56، تابع بازیابی ابتدا تمام عناصر پایگاه داده را به فضای ویژگی تصویر می‌کند. سپس این نقاط ویژگی را بر اساس مقادیر ضرب داخلی آنها با بردار بهینه مرتب می کند. و رتبه هر نقطه ویژگی، رتبه عنصر مربوطه پایگاه داده برای پرس و جوی formula_56 است.
رتبه بندی SVM می تواند برای رتبه بندی صفحات بر اساس پرس و جو اعمال شود. الگوریتم را می توان با استفاده از داده های کلیکی آموزش داد که از سه بخش زیر تشکیل شده است:ترکیب 2 و 3 نمی تواند ترتیب داده های آموزشی کاملی را که برای اعمال الگوریتم کامل SVM لازم است را ارائه دهد. در عوض، بخشی از اطلاعات رتبه بندی داده های آموزشی را ارائه می دهد. بنابراین الگوریتم را می توان به صورت زیر کمی اصلاح کرد.
formula_73
روش formula_74 اطلاعات رتبه بندی کل مجموعه داده را ارائه نمی دهد، بلکه زیر مجموعه ای از روش رتبه بندی کامل است. بنابراین شرط مسئله بهینه سازی در مقایسه با Ranking-SVM اصلی راحت تر می شود.