دسته بندی کننده ماشین بردار پشتیبان

ماشين­هاي بردار پشتيبان يك تكنيك دسته­بندي و رگرسيون است كه توسط وپنیک[1] و گروهش در آزمايشگاه AT&T Bell پيشنهاد شده است و در حال حاضر در بسياري از زمينه­ها مثل تشخيص چهره، تشخیص صوت، بازشناسي ديجيتالي هويت با استفاده از دست­خط وغیره استفاده مي­شود. این دسته­بندی کننده یک دسته­بندی کننده خطی است که می­توان با اعمال برخی تغییرات از آن به عنوان دسته­بندی کننده غیر خطی نیز بهره­جست. توانایی این دسته­بندی کننده در یافتن فوق صفحه بهینه برای دسته­بندی می­باشد. در ادامه به بررسی این دسته­بندی کننده و توانایی آن در دسته بندی داده­های خطی در دو حالت جداپذیر کامل و جدا ناپذیر کامل می­پردازیم و سپس نحوه استفاده از این دسته­بندی کننده را برای داده­های غیرخطی شرح می­دهیم.

4-5-1- دسته­بندی کننده­ ماشین بردار پشتیبان خطی

4-5-1-1- دسته­بندی کلاس­های جداپذیر

در این بخش هدف طراحی یک دسته­بندی کننده خطی به منظور جداسازی کلاس­های جداپذیر از هم می­باشد. در ابتدا یک دسته­بندی کننده خطی به منظور جداسازی داده­های دو کلاس جداپذیر از هم معرفی می­گردد و سپس این دسته­بندی کننده را به منظور جدا سازی داده­های کلی و جداناپذیر گسترش می­دهیم.[28]

فرض کنید  بردارهای ویژگی برای داده­های آموزشی[2]  باشد. این داده­ها به دو کلاس  و ، که به صورت خطی از هم جداپذیرند، تعلق دارند. هدف بدست آوردن فوق صفحه  به نحوی است که تمامی داده­های آموزشی را صحیح دسته­بندی کند. به صورت کلی این فوق صفحه یکتا نبوده و می­توان مقادیر مختلفی را برای و  بدست آورد. شکل (4-6) دو نمونه از فوق صفحه­هایی را که می­توان به منظور دسته­بندی صحیح نقاط داده شده در نظرگرفت را نشان می­دهد.

شکل(4-6): یک نمونه از مسئله دو کلاسه خطی جداپذیر که نمونه­ها توسط دو دسته­بندی کننده خطی جدا شده.

هر دو فوق صفحه نشان داده شده در شکل (4-6) عمل جداسازی را به درستی انجام می­دهند، اما واضح است که خط متصل نسبت به خط منقطع دسته­بندی کننده مناسب­تری است. زیرا این فوق صفحه فضای بیشتری را در دو طرف خود ایجاد می­کند. این بدان معنی است که این دسته­بندی کننده در زمان دسته­بندی نمونه­های آزمایشی نتایج بهتری را از خود نشان می­دهد. این نتیجه امری بسیار مهم در طراحی دسته­بندی کننده­هاست و آنرا عمومیت عملکرد[3] دسته­بندی کننده می­نامند. این مسئله به توانایی دسته­بندی کننده در دسته­بندی رضایت­بخش داده­های خارجی برمی­گردد.

بنابراین در دسته­بندی کننده ماشین­های بردار پشتیبان قصد بر این است که علاوه بر دسته­بندی صحیح داده­های آموزشی، فوق صفحه­ای را بدست آوریم که حاشیه[4] بین دو کلاس را بیشینه کند. منظور از حاشیه بین دو کلاس فاصله­ای است که فوق­صفحه بین دو کلاس باقی می­گذارد.

هر فوق صفحه بوسیله جهت و مکان دقیقش در فضا مشخص می­گردد که جهت فوق­صفحه را  و مکان دقیق آنرا در فضا  مشخص می­کند. به دلیل اینکه هیچ برتری بین دو کلاس وجود ندارد، لازم است فاصله فوق صفحه از نزدیک­ترین نقاط هر دو کلاس  و  به یک اندازه باشد.  بنابراین لازم است فوق صفحه­ای را بیابیم که بیشترین حاشیه ممکن را ایجاد کند و به این منظور به دنبال جهت بهینه و مکان دقیق فوق­صفحه هستیم. [28] شکل (4-7) این امر را به وضوح روشن می­سازد.

شکل(4-7): حاشیه برای جهت 2 بیشتر از حاشیه در جهت 1 است.

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

 فاصله یک نقطه از یک فوق­صفحه برابر است با:

(4-7)

 و  را طوری مقیاس­دهی می­کنیم که اندازه  در نزدیک­ترین نقاط  برابر 1 و در نزدیک­ترین نقاط  برابر  شود. حاشیه بین دو کلاس برابر خواهد بود با:

(4-8)

به این ترتیب خواهیم داشت:

(4-9)

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

                                                      (4-10)

واضح است که کمینه کردن مقدار نرم[5] باعث می­گردد که حاشیه فوق­صفحه با کلاس­ها بیشینه گردد. این شرایط حل یک معادله غیرخطی براساس یک سری محدودیت­های خطی می­باشد.

شرایط Karush-Kuhn-Tucher (KKT) به منظور کمینه کردن معادله (4-8) برابر خواهد بود با:

                                                                                         (4-11)

                                                                                       (4-12)

                                                                                      (4-13)

                                                           (4-14)

در معادلات بالا  بردار ضرایب لاگرانژ  و  تابع لاگرانژ است که به صورت زیر تعریف می­گردد:

                                                  (4-15)

با ترکیب رابطه (4-15) با (4-11) و (4-12) خواهیم داشت:

                                                                                                (4-16)

                                                                                                   (4-17)

باید توجه داشت که ضرایب لاگرانژ، ها، می­توانند صفر و یا مثبت باشند. بنابراین براساس معادله(4-16) پاسخ بدست آمده برای بردار پارامتر­های  برابر است با  ترکیب خطی از  بردار ویژگی که ضریب لاگرانژ آنها مخالف صفر است.

                                                                                (4-18)

این بردارها که ضرایب لاگرانژ غیرصفر دارند و برای بدست آوردن فوق­صفحه بهینه استفاده می­گردند را بردارهای پشتیبان[6] می­نامند. بر اساس دسته محدودیت­های موجود در رابطه (4-14) برای ضرایب لاگرانژ غیرصفر، بردارهای پشتیبان در دو فوق­صفحه زیر قرار می­گیرند:

                                                                                               (4-19)

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

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

                                                                                    (4-20)

                                                                                  (4-21)

                                                                                                   (4-22)

محدودیت­های بدست آمده در رابطه (4-22) با صفر قرار دادن گرادیان لاگرانژ نسبت به و  بدست آمده­اند. با قرار دادن روابط (4-22) و (4-21) در رابطه (4-20) و انجام محاسبات ریاضی خواهیم داشت:

                                                                         (4-23)

                                                                                    (4-24)

4-5-1-2- دسته­بندی کلاس­های جدا ناپذیر

در این حالت کلاس­های موجود با استفاده از دسته­بندی کننده خطی به صورت کامل از همدیگر جدا نمی­شوند. همان­گونه که در شکل (4-8) مشخص می­باشد دو کلاس در این حالت جداپذیر نمی­باشند و نمی­توان با یک دسته­بندی کننده خطی آن­ها را کاملا از هم جدا کرد. هر گونه تلاشی به منظور جداسازی داده­ها با یک فوق­صفحه به نتیجه نمی­رسد مگر آنکه یک سری از داده­ها در داخل باند جداسازی قرار گیرد. در این شرایط حاشیه فاصله بین دو فوق­صفحه با معادله  تعریف می­گردد.

شکل(4-8): نمونه­ای از داده­هایی که به صورت خطی به طور کامل از همدیگر جدا نمی­شوند.

بردار ویژگی نمونه­های آموزشی به یکی از سه دسته زیر تعلق دارند.]28[

بردارهایی که خارج از باند قرار می­گیرند و صحیح دسته­بندی شده­اند. این بردارها شرایط در نظر گرفته شده در معادله (4-10) را برقرار می­سازند.

بردارهایی که در داخل باند قرار می­گیرند و صحیح دسته­بندی شده­اند. این بردارها در شکل (4-8) با مربع مشخص گردیده­اند و در شرایط زیر صدق می­کنند.

                                                                                                          (4-25)

بردارهایی که به اشتباه دسته­بندی شده­اند. این بردارها در شکل (4-8) با دایره مشخص گردیده­اند و از شریط زیر تبعیت می­کنند.

                                                                                           (4-26)

تمامی سه حالت فوق را می­توان با اضافه کردن یک محدودیت جدید و معرفی یک دسته  پارامتر جدید در نظر گرفت:

                                                                                      (4-27)

گروه اول داده­ها با در نظر گرفتن ، گروه­ دوم با در نظر گرفتن  و گروه سوم با در نظر گرفتن  بدست می­آیند. پارامتر  به نام پارامتر Slack شناخته می­شود. در شرایط کنونی هدف این است که تا حدممکن حاشیه را  با در نظر گرفتن تعداد نقاطی است که در آنها  است، افزایش دهیم. در فرم ریاضی این عمل برابر است با مینیمم کردن تابع هزینه زیر:

                                                                        (4-28)

که در آن  بردار پارامترهای  است و

                                                                                          (4-29)

پارامتر  یک عدد ثابت مثبت است که تاثیر نسبی دو قسمت رابطه (4-28) را کنترل می­کند. بهینه­سازی رابطه (4-28) مشکل است زیرا شامل تابع ناپیوسته  است. بنابراین شرایط به صورت زیر تغییر می­کند:

                                                            (4-30)

                                                 (4-31)

                                                                      (4-32)

محدودیت لاگرانژ برای حل معادلات فوق برابر است با:

                                                  (4-33)

شرایط Karush-Kuhn-Tucker متناظر برابر است با:

                                                                                (4-34)

                                                                                    (4-35)

                                                          (4-36)

                                                      (4-37)

                                                                                   (4-38)

                                                                           (4-39)

نمایش دوگانی Wolf معادلات فوق برابر خواهد بود با:

                                                            (4-40)

با اعمال محدودیت فوق به معادلات لاگرانژ خواهیم داشت:

                                                                      (4-41)

                                                                 (4-42)

                                                                                                   (4-43)

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

4-5-1-3- دسته­بندی داده­های چند کلاسه با ماشین­های بردار پشتیبان

در تمامی قسمت­های گذشته، به بررسی عمل دسته­بندی برای دو کلاس مختلف پرداختیم. اگر بخواهیم دسته­بندی کننده ماشین­های بردار پشتیبان را برای  کلاس گسترش دهیم کافی است روش ارائه شده در قسمت­های پیشین را برای  مسئله دو کلاس اعمال کنیم. به این ترتیب مسئله دسته بندی  کلاس به  دسته­بندی دو کلاسه تبدیل خواهد شد. برای هر یک از کلاس­ها، ما به دنبال بدست آوردن تابع تفکیک بهینه  هستیم. نمونه  متعلق به کلاس  است اگر

                                                                                   (4-44)

4-5-2- ماشین­های بردار پشتیبان غیر خطی

در بخش­های پیشین ماشین­های بردار پشتیبان را به صورت یک دسته­بندی کننده خطی بهینه معرفی کردیم. حال فرض کنید یک نگاشت به صورت

                                                                                           (4-45)

از فضای ویژگی­ ورودی به یک فضای k بعدی داریم که در این فضای جدید کلاس­ها با یک فوق­صفحه از یکدیگر قابل جداسازی هستند. حال در این فضای k بعدی جدید یک دسته­بندی کننده ماشین­های بردار پشتیبان طراحی می­کنیم.]28[ در زیر قضیه­ای را به نام Mercer معرفی می­کنیم.

قضیه Mercer :

فرض کنید  و نگاشت  به صورت زیر در نظر گرفته شده باشد:

                                                                                               (4-46)

 یک فضای اقلیدسی[7] است. در این صورت عملگر ضرب داخلی به صورت زیر قابل نمایش است:

                                                                                 (4-47)

 جزء r ام از نگاشت  بوده و  یک تابع متقارن است که از شرایط پیروی می­کند:

                                                                         (4-48)

به ازای هر  که داشته باشیم

                                                                                             (4-49)

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

 

• کرنل چند جمله­ای:
•                                                              (4-50)
• کرنل تابع پایه شعاعی[8] :
• (4-51)
• کرنل تانژانت هیپربولیک :
• (4-52)

از این کرنل­ها برای نگاشت به فضای بالاتر در دسته­بندی کننده­های ماشین­های بردار پشتیبان استفاده می­گردد. زمانی که یک کرنل مناسب به منظور نگاشت به فضایی با ابعاد بالاتر استفاده گردید با استفاده از بهینه ساز دوگان Wolfe خواهیم داشت:

                                                                (4-53)

                                                                 (4-54)

                                                                                                   (4-55)

و درنتیجه نمونه  متعلق به کلاس  خواهد بود اگر

                                                                       (4-56)

و بصورت مشابه نمونه  متعلق به کلاس  خواهد بو د اگر

                                                                        (4-57)

شکل (4-9) نحوه نگاشت به فضای بالاتر را در SVM غیرخطی نشان می­دهد. تعداد گره­های موجود در لایه میانی را تعداد بردارهای پشتیبان در دسته­بندی کننده SVM تعیین می­کند.]28[

1.Vapnik

2.Training Set

1 .Generalization Performance

2.Margin

1. Norm
2. 1. Support Vectors

1.Euclidean

1.Radial Basis Function(RBF)