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

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

${\displaystyle r\ c_{i}<r\ c_{j}}$

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

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

فرض کنید ${\displaystyle r_{1}}$ و ${\displaystyle r_{2}}$ دو روش رتبه‌بندی باشد که برای مجموعه داده‌های ${\displaystyle \mathbb {C} }$ اعمال می‌شود، تای کندال بین ${\displaystyle r_{1}}$ و ${\displaystyle r_{2}}$ را می‌توان به صورت زیر نشان داد: ${\displaystyle \tau (r_{1},r_{2})={P-Q \over P+Q}=1-{2Q \over P+Q}}$

که در آن ${\displaystyle P}$ تعداد جفت‌های همخوان است و ${\displaystyle Q}$ تعداد جفت‌های ناسازگار (وارونگی) است. یک جفت ${\displaystyle d_{i}}$ و ${\displaystyle d_{j}}$ همخوان است اگر در هر دو روش ${\displaystyle r_{a}}$ و ${\displaystyle r_{b}}$ رتبه‌بندی ${\displaystyle d_{i}}$ و ${\displaystyle d_{j}}$ یکسان باشد. در غیر این صورت ناسازگار خواهند بود.

کیفیت بازیابی اطلاعات معمولاً با سه معیار زیر ارزیابی می‌شود:

1. صحت، درستی (Precision)
2. فراخوانی، حساسیت (Recall)
3. دقت متوسط (Average Precision)

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

${\displaystyle {\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}}}$

که در آن ${\displaystyle Prec(Recall)}$ دقت فراخوانی است.

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

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

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

فرض کنید ${\displaystyle ({\vec {x}}_{i},y_{i})}$ عنصر یک مجموعه داده آموزشی که در آن ${\displaystyle {\vec {x}}_{i}}$ بردار ویژگی و ${\displaystyle y_{i}}$ برچسب (که دسته ${\displaystyle {\vec {x}}_{i}}$ را مشخص می‌کند) است. یک طبقه‌بندی کننده SVM معمولی برای چنین مجموعه داده‌ای می‌تواند به عنوان راه حل مسئله بهینه‌سازی زیر تعریف شود.

${\displaystyle {\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}}}$

حل مسئله بهینه‌سازی فوق را می‌توان به صورت ترکیبی خطی از بردارهای ویژگی ${\displaystyle x_{i}}$ نشان داد.

${\displaystyle {\vec {w}}^{*}=\sum _{i}{\alpha _{i}y_{i}x_{i}}}$

که در آن ${\displaystyle \alpha _{i}}$ ضرایبی هستند که باید تعیین شوند.

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

• تابع زیان مورد انتظار^[۹]

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

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

• تابع زیان تجربی

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

${\displaystyle L_{empirical}=-\tau _{S}(f)=-{1 \over n}\sum _{i=1}^{n}{\tau (r_{f(q_{i})},r_{i}^{*})}}$

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

یک نگاشت ${\displaystyle \Phi (q,d)}$^[۱۰][۱۱] مورد نیاز است که هر پرس و جو و عنصر پایگاه داده را به فضای ویژگی مورد نیاز متناظر کند. سپس هر نقطه در فضای ویژگی با روش رتبه‌بندی با رتبه خاصی برچسب گذاری می‌شود.

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

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

${\displaystyle {\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 نامیده می‌شود.

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

${\displaystyle {\vec {w}}^{*}=\sum {\alpha _{k,l}^{*}\Phi (q_{k},c_{i})}}$

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

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