ماشین بردار پشتیبان

ماشین بردار پشتیبان یکی از جدیدترین روش ها جهت طبقه بندی داده ها می باشد که نسبت به روش های قدیمی تر مانند شبکه عصبی کارایی بهتری دارد. این تکنیک یک روش یادگیری supervised است و جزو شاخه Kernel Methods دریادگیری ماشین محسوب می شود. از SVM هم جهت شناسایی الگو و هم جهت دسته بندی آنها استفاده می شود.
SVM با فرض اینکه دسته ها به صورت خطی جداپذیر باشند، ابرصفحه هائی با حداکثر حاشیه (maximum margin) را بدست می آورد تا دسته ها را جدا کند. سپس با درنظر گرفتن این ابرصفحه ها، داده ها را به دو کلاس مجزا تقسیم می کند که جواب کلاس اول در معادله صفحه مثبت و دیگری در معادله صفحه منفی است. البته این روش تا زمانی پاسخگو است که داده ها به صورت خطی تفکیک پذیر باشند اما در مسایلی که داده ها بصورت خطی جداپذیر نباشند داده ها را باید به فضایی با ابعاد بیشتر نگاشت دهیم یا در همین فضا آنها را توسط تابعی (کرنل) جایگزین نمائیم؛ تا بتوان آنها را بصورت خطی جدا نمود[54].
SVM دارای معایب و مزایایی می باشد از جمله در آموزش خود مشکل بهينه هاي محلي را ندارد و برخلاف شبکه های عصبی در ماکزیمم های محلی گیر نمی افتد. و Classifier را با حداکثر تعميم بنا مي کند . ساختار و توپولوژي خود را به صورت بهينه تعيين مي کند .توابع تمايز غير خطي را به راحتي و با محاسبات کم، با استفاده از مفهوم حاصلضرب داخلي تشکيل مي دهد. آموزش آن نسبتاً ساده است. برای داده های با ابعاد بالا تقریباً خوب جواب می دهد. به یک تابع کرنل خوب و انتخاب پارامتر C نیاز دارد.
5-5-1- ابر صفحه جداساز
ابرصفه یک مفهوم در هندسه و تعمیمی از یک صفحه در تعداد متفاوتی از ابعاد است. در SVM اگر داده ها دارای n بُعد باشند، صفحه جداساز دارای n-1 بُعد است. اما جهت جداسازی داده ها چندین صفحه جداساز وجود دارد زیرا مفهوم آموزشی که اشیاء بتوانند به عنوان نقاط در یک فضای با ابعاد بالا دسته بندی شوند و پیدا کردن خطی که آنها را جدا کند منحصر به فرد نیست. (شکل 5-7) حال سوال این است که کدام صفحه مناسب تر است؟ منظور ما از “مناسب تر بودن” داشتن حداکثر فاصله با داده های دو کلاس و حداقل خطا می باشد. آنچه که SVM را از سایر classifier ها متمایز کرده است، بکارگیری همین شیوه در انتخاب صفحه جداساز است. به همین دلیل SVM به راحتی می تواند برای طبقه بندی داده ها در دو کلاس یا بیشتر استفاده شود.
همانطور که در بالا ذکر شد، درSVM ماکزیمم کردن حاشیه بین دو کلاس مدنظر است. بنابراین ابرصفحه ای را انتخاب می کند که فاصله آن از نزدیک ترین داده ها در هر دو طرف جداکننده خطی، ماکزیمم باشد. اگر چنین ابرصفحه ای وجود داشته باشد، به عنوان ابرصفحه ماکزیمم حاشیه شناخته می شود.
حال با توجه به توضیحات بیان شده، مفهوم support vector به راحتی قابل درک می باشد. support vector به بردارهایی اطلاق می شود که دارای حداکثر فاصله با صفحه جداساز هستند و این حداکثر فاصله را با m (margin) نمایش می دهند که در شکل (5-7) نشان داده شده است.
هدف SVM ایجاد یک معیار مناسب جهت دسته بندی است به طوری که برای نمونه های ندیده به خوبی قابل

شکل 5- 7 – صفحه های جداساز و بردارهای پشتیبان
استفاده باشد و در عین حال از قابلیت تعمیم خوبی برخوردار باشد.
در صورت استفاده مناسب از SVM این الگوریتم قدرت تعمیم خوبی خواهد داشت. علی رغم ابعاد زیاد از سرریز شدن پرهیز می-کند. همچنین به جای استفاده از کل داده ها، فقط از بردارهای پشتیبان استفاده می کند. یک جداکننده اغلب به صورت یک تابع نشان داده می شود. وقتی که دو کلاس داریم، اگر باشد، داده به کلاس مثبت نسبت داده می شود و درغیر این صورت به کلاس منفی تعلق دارد. در شکل (5-8) این نواحی با اعداد 1+ و 1- نشان داده شده است.
تابع خطی، تابعی است که از ترکیب خطی ورودی x به صورت زیر تعریف می شود:
(12-5)
این تابع (تابع تصمیم گیری برای جداکردن داده ها) با یک زیرمجموعه ای از مثال های آموزشی که بردار های پشتیبان نزدیک ترین داده های آموزشی به ابرصفحه جداکننده، نامیده می شوند، تعیین می شود. در واقع ابرصفحه بهینه در SVM جداکننده ای بین بردار-های پشتبیبان است.
جهت جداسازی مجموعه ای از نقاط که (y نشانه و label مربوط به کلاس داده ها

شکل 5- 8 – صفحه جداساز و نواحی مربوط به هر کلاس

می باشد.)، توسط یک جداکننده خطی، باید بتوان خطی را پیدا کرد به نحوی که برای تمام i ها رابطه برقرار باشد. فرض کنید تعدادی داده آموزشی داریم، یک مجموعه از نقاط به فرم:
(13-5)
می تواند 1 یا 1- باشد، که مشخص می کند داده متعلق به چه کلاسی است. هر یک بردار p بعدی است. می خواهیم جداکننده ماکزیمم حاشیه ای پیدا کنیم که نقاطی که آنها برابر 1 است از نقاطی که آنها 1- است جدا کند. هر ابرصفحه می-تواند به صورت یک مجموعه از نقاط x که رابطه را ارضاء می کنند نوشته شود. بردار w یک بردار نرمال است. این بردار بر ابرصفحه عمود است. پارامتر آفست ابرصفحه از مبدا در امتداد بردار نرمال w می باشد.
حال می خواهیم w و b را طوری انتخاب کنیم که حاشیه یا فاصله بین ابرصفحه های موازی ماکزیمم شود به نحوی که ابرصفحه-های موازی تا آنجا که می توانند از هم دور باشند و همچنان داده ها را بتوان جدا کرد. این ابرصفحه های موازی می توانند با معادله-های زیر توصیف شوند[55]:
(14-5)
توجه کنید اگر داده های آموزشی را بتوان به صورت خطی جدا کرد، می توانیم دو صفحه جداکننده را طوری انتخاب کنیم که هیچ داده ای بین آنها نباشد و سپس سعی کنیم فاصله آنها را ماکزیمم کنیم. با استفاده از هندسه، فاصله بین این دو ابرصفحه (پهنای حاشیه) را پیدا می کنیم که برابر است. بنابراین می خواهیم را مینیمم کنیم.