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

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

توصیف

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

به طور کلی، رتبه بندی SVM شامل سه مرحله در دوره آموزش است:

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

زمینه

روش رتبه بندی

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

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

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

تای کندال

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

فرض کنید $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}$ یکسان باشد. در غیر این صورت ناسازگار خواهند بود.

کیفیت بازیابی اطلاعات

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

1. صحت، درستی (Precision)
2. فراخوانی، حساسیت (Recall)
3. دقت متوسط (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 می تواند برای رتبه بندی صفحات بر اساس پرس و جو اعمال شود. الگوریتم را می توان با استفاده از داده های کلیکی آموزش داد که از سه بخش زیر تشکیل شده است:

1. پرس و جو.
2. رتبه بندی فعلی نتایج جستجو
3. نتایج جستجو توسط کاربر کلیک شده است

ترکیب 2 و 3 نمی تواند ترتیب داده های آموزشی کاملی را که برای اعمال الگوریتم کامل 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 اصلی راحت تر می شود.