اس‌وی‌ام رتبه‌بندی

در یادگیری ماشین، یک **SVM رتبه‌بندی** گونه‌ای از الگوریتم ماشین بردار پشتیبانی است که برای حل مسائل رتبه‌بندی خاص (از طریق یادگیری رتبه‌بندی) استفاده می‌شود. الگوریتم SVM رتبه‌بندی توسط Thorsten Joachims در سال ۲۰۰۲ منتشر شد. هدف اصلی این الگوریتم بهبود عملکرد یک موتور جستجوی اینترنتی بود. با این حال، مشخص شد که رتبه‌بندی SVM همچنین می‌تواند برای حل مسائل دیگری مانند Rank SIFT استفاده شود.

## توصیف
الگوریتم رتبه‌بندی SVM یک تابع بازیابی یادگیری است که از روش‌های رتبه‌بندی زوجی برای مرتب‌سازی تطبیقی نتایج بر اساس «مرتبط بودن» آنها برای یک پرس‌وجو خاص استفاده می‌کند. تابع رتبه‌بندی SVM از یک تابع نگاشت برای توصیف تطابق بین یک عبارت جستجو و ویژگی‌های هر یک از نتایج ممکن استفاده می‌کند. این تابع نگاشت هر جفت داده (مثلاً یک پرس و جوی جستجو و صفحه وب کلیک شده) را به یک فضای ویژگی تصویر می‌کند. این ویژگی‌ها با داده‌های کلیکی مربوطه ترکیب می‌شوند (که می‌تواند به عنوان یک واسط برای ارتباط یک صفحه برای یک جستجوی خاص عمل کند) و سپس می‌تواند به عنوان داده‌های آموزشی برای الگوریتم رتبه‌بندی SVM استفاده شود.

به‌طور کلی، رتبه‌بندی SVM شامل سه مرحله در دوره آموزش است:
# یک نگاشت از شباهت‌های بین پرس‌وجوها و صفحات کلیک‌شده به در یک فضای ویژگی خاص تعریف می‌کند.
# فاصله بین هر دو بردار به دست آمده در مرحله ۱ را محاسبه می‌کند.
# این یک مسئله بهینه‌سازی را تشکیل می‌دهد که شبیه به یک طبقه‌بندی استاندارد SVM است و این مشکل را با حل کننده SVM معمولی حل می‌کند.

## زمینه
### روش رتبه‌بندی
فرض کنید \mathbb{C}مجموعه داده‌ای است که شامل N عنصر c_i است.  r  یک روش رتبه‌بندی است که به \mathbb{C}اعمال می‌شود. سپس  r در \mathbb{C}را می‌توان به صورت یک ماتریس دودویی N \times N نشان داد. اگر رتبه c_i از رتبه c_j بالاتر باشد، یعنی:

r\ c_i 

آنگاه درایه متناظر با آن را در ماتریس مقدار ۱ و در غیر این صورت مقدار ۰ قرار می‌دهیم.

### تای کندال
تای کندال همچنین به ضریب همبستگی رتبه تای کندال اشاره دارد، که معمولاً برای مقایسه دو روش رتبه‌بندی برای یک مجموعه داده استفاده می‌شود.

فرض کنید r_1 و  r_2 دو روش رتبه‌بندی باشد که برای مجموعه داده‌های \mathbb{C} اعمال می‌شود، تای کندال بین r_1 و r_2 را می‌توان به صورت زیر نشان داد:


\tau (r_1,r_2) = {P-Q \over P+Q} = 1- {2Q \over P+Q}



که در آن P تعداد جفت‌های همخوان است و Q تعداد جفت‌های ناسازگار (وارونگی) است. یک جفت d_i و d_j همخوان است اگر در هر دو روش r_a و r_b رتبه‌بندی d_i و d_j یکسان باشد. در غیر این صورت ناسازگار خواهند بود.

### کیفیت بازیابی اطلاعات
کیفیت بازیابی اطلاعات معمولاً با سه معیار زیر ارزیابی می‌شود:
# صحت، درستی (Precision)
# فراخوانی، حساسیت (Recall)
# دقت متوسط (Average Precision)

برای یک پرس و جو خاص به یک پایگاه داده، فرض کنید P_{relevant} مجموعه ای از عناصر اطلاعاتی مرتبط در پایگاه داده و P_{retrieved} مجموعه ای از عناصر اطلاعاتی بازیابی شده باشد. سپس سه اندازه‌گیری فوق را می‌توان به صورت زیر نشان داد:

 \begin{array}{lcl}
Precision ={ \left \vert P_{relevant} \cap P_{retrieved} \right \vert \over \left \vert P_{retrieved} \right \vert}; \\
\\

Recall = {\left \vert P_{relevant} \cap P_{retrieved} \right \vert \over \left \vert P_{relevant} \right \vert} ;\\
\\
AveragePrecision = \int_0^1 {Prec(Recall)}dRecall,\\

\end{array}


که در آن Prec(Recall) دقت فراخوانی است.

فرض کنید r^* و r_{f(q)} به ترتیب روش‌های رتبه‌بندی مورد انتظار و پیشنهادی یک پایگاه داده باشند، کران پایین میانگین دقت روش r_{f(q)} را می‌توان به صورت زیر نشان داد.

 AvgPrec(r_{f(q)}) \geqq {1 \over R} \left[Q+ \binom{R+1}{2} \right]^{-1}(\sum_{i=1}^R\sqrt{i})^2

که در آن Q تعداد درایه‌های متفاوت در قسمت بالای قطر اصلی ماتریس هایr^* و r_{f(q)} و R تعداد عناصر مرتبط در مجموعه داده است.

### طبقه‌بندی SVM
فرض کنید (\vec x_i,y_i) عنصر یک مجموعه داده آموزشی که در آن \vec x_i بردار ویژگی و y_i برچسب (که دسته \vec x_i را مشخص می‌کند) است. یک طبقه‌بندی کننده SVM معمولی برای چنین مجموعه داده‌ای می‌تواند به عنوان راه حل مسئله بهینه‌سازی زیر تعریف شود.


\begin{array}{lcl}
\mathrm{minimize:\ } V(\vec w, \vec \xi) = {1 \over 2} \vec w \cdot \vec w + CF \sum{\xi_i^\sigma} \\
s.t. \\
\begin{array}{lcl}
 \sigma \geqq 0;\\

 \forall y_i(\vec w \vec x_i +b) \geqq 1-\xi_i^\sigma;
 \end{array}

\\

\mathrm{where,\ } \\

 \begin{array}{lcl}
 b \mathrm{\ is\ a\ scalar;}\\
 \forall y_i \in \left \{ -1,1 \right \};\\
 \forall \xi_i \geqq 0;\\
 \end{array}
\end{array}



حل مسئله بهینه‌سازی فوق را می‌توان به صورت ترکیبی خطی از بردارهای ویژگی x_i نشان داد.


 \vec w^* = \sum_i{\alpha_i y_i x_i}


که در آن \alpha_i ضرایبی هستند که باید تعیین شوند.

## الگوریتم رتبه‌بندی SVM
### تابع زیان
فرض کنید  \tau_{P(f)} تای کندال بین روش رتبه‌بندی مورد انتظار r^* و روش پیشنهادی r_{f(q)} باشد، می‌توان ثابت کرد که به ماکسیمم کردن  \tau_{P(f)} به مینیمم کردن کران پایینِ میانگینِ دقت r_{f(q)} کمک می‌کند.
* ***تابع زیان مورد انتظار***

منفی  \tau_{P(f)} را می‌توان به عنوان تابع زیان برای به حداقل رساندن کران پایین میانگین دقت r_{f(q)} انتخاب کرد. L_{expected}=-\tau_{P(f)}=-\int \tau(r_{f(q)},r^*)dPr(q,r^*)

که در آن Pr(q,r^*) توزیع آماری r^* به پرس و جو خاص q است.
* ***تابع زیان تجربی***

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

 L_{empirical} = - \tau_S(f)= -{1 \over n} \sum_{i=1}^n{\tau(r_{f(q_i)},r_i^*)}

### جمع‌آوری داده‌های آموزشی
n پرس و حوی iid روی یک پایگاه داده اعمال می‌شوند و هر پرس و جو با یک روش رتبه‌بندی مطابقت دارد. مجموعه داده‌های آموزشی n عنصر دارد. هر عنصر حاوی یک پرس و جو و روش رتبه‌بندی مربوطه است.

### فضای ویژگی
بندانگشتی| نقاط برچسب گذاری شده در فضای ویژگی
یک نگاشت \Phi(q,d) مورد نیاز است که هر پرس و جو و عنصر پایگاه داده را به فضای ویژگی مورد نیاز متناظر کند. سپس هر نقطه در فضای ویژگی با روش رتبه‌بندی با رتبه خاصی برچسب گذاری می‌شود.

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

فرض کنید c_i و c_j دو عنصر در پایگاه داده هستند و می‌نویسیم (c_i,c_j) \in r  اگر رتبه از c_i بالاتر از c_j در روش رتبه‌بندی معین r باشد. فرض کنید بردار \vec w کاندیدای طبقه‌بندی کننده خطی در فضای ویژگی باشد. آنگاه مسئله رتبه‌بندی را می‌توان به مسئله طبقه‌بندی SVM زیر ترجمه کرد. توجه داشته باشید که یک روش رتبه‌بندی با یک پرس و جو مطابقت دارد.



\begin{array}{lcl}
\mathrm{minimize:\ } V(\vec w, \vec \xi) = {1 \over 2} \vec w \cdot \vec w + C_{onstant} \sum{\xi_{i,j,k}} \\
s.t. \\ \begin{array}{lcl}
 \forall \xi_{i,j,k} \geqq 0\\
 \forall (c_i, c_j)\in r_k^*\\
 \vec w (\Phi(q_1,c_i)-\Phi(q_1, c_j)) \geqq 1- \xi_{i,j,1};\\
 ...\\
 \vec w (\Phi(q_n, c_i)-\Phi(q_n, c_j)) \geqq 1-\xi_{i,j,n};\\

\mathrm{where\ } \ k \in \left \{ 1,2,...n \right \},\ i,j \in \left \{ 1,2,... \right \}.\\

 \end{array}
\end{array}



مسئله بهینه‌سازی فوق با مسئله طبقه‌بندی SVM کلاسیک یکسان است، به همین دلیل است که این الگوریتم Ranking-SVM نامیده می‌شود.
بندانگشتی| نامزد W
بندانگشتی| یک نامزد w نیست

### تابع بازیابی
بردار بهینه \vec w^* که توسط نمونه آموزشی به دست آمده است، چنین است:

 \vec w^*=\sum{\alpha_{k,l}^*\Phi(q_k,c_i)}

بنابراین تابع بازیابی را می‌توان بر اساس چنین طبقه‌بندی بهینه ای تشکیل داد.

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

## کاربرد رتبه‌بندی SVM
رتبه‌بندی SVM می‌تواند برای رتبه‌بندی صفحات بر اساس پرس و جو اعمال شود. الگوریتم را می‌توان با استفاده از داده‌های کلیکی آموزش داد که از سه بخش زیر تشکیل شده است:
# پرس و جو.
# رتبه‌بندی فعلی نتایج جستجو
# نتایج جستجو توسط کاربر کلیک شده است

ترکیب ۲ و ۳ نمی‌تواند ترتیب داده‌های آموزشی کاملی را که برای اعمال الگوریتم کامل SVM لازم است را ارائه دهد. در عوض، بخشی از اطلاعات رتبه‌بندی داده‌های آموزشی را ارائه می‌دهد؛ بنابراین الگوریتم را می‌توان به صورت زیر کمی اصلاح کرد.


\begin{array}{lcl}
\mathrm{minimize:\ } V(\vec w, \vec \xi) = {1 \over 2} \vec w \cdot \vec w + C_{ontant} \sum{\xi_{i,j,k}} \\
s.t. \\ \begin{array}{lcl}
 \forall \xi_{i,j,k} \geqq 0\\
 \forall (c_i, c_j)\in r_k^'\\
 \vec w (\Phi(q_1,c_i)-\Phi(q_1,c_j)) \geqq 1- \xi_{i,j,1};\\
 ...\\
 \vec w (\Phi(q_n,c_i)-\Phi(q_n,c_j)) \geqq 1- \xi_{i,j,n};\\
\mathrm{where\ }\ k \in \left \{ 1,2,...n \right \},\ i,j \in \left \{ 1,2,... \right \}.\\
 \end{array}
\end{array}


روش r' اطلاعات رتبه‌بندی کل مجموعه داده را ارائه نمی‌دهد، بلکه زیر مجموعه ای از روش رتبه‌بندی کامل است؛ بنابراین شرط مسئله بهینه‌سازی در مقایسه با Ranking-SVM اصلی راحت تر می‌شود.

## منابع

رده:صفحات با ترجمه بازبینی‌نشده
رده:ماشین‌های بردار پشتیبانی