الگوریتم طبقه بندی ماشین بردار پشتیبان(SVM)

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

ماشین بردار پشتیبان دسته‌بندی کننده‌ای است که جزو روش‌های بر پایه هسته در یادگیری ماشین محسوب می‌شود. SVM در سال 1992 توسط وپ‌نیک معرفی شده و بر پایه نظریه آماری یادگیری بنا گردیده است. الگوریتم SVM یکی از الگوریتم‌های معروف در زمینه یادگیری با نظارت است که برای دسته‌بندی و رگرسیون استفاده می‌شود. این الگوریتم به طور هم‌زمان حاشیه‌های هندسی را بیشینه کرده و خطای تجربی دسته‌بندی را کمینه می‌کند لذا به عنوان دسته‌بندی حداکثر حاشیه نیز نامیده می‌شود.
برای یک مسأله دسته‌بندی با دو دسته نتیجه خطوط بی‌شماری ممکن است وجود داشته باشند که توسط آن‌ها دسته‌بندی انجام شود ولی فقط یکی از این خطوط ماکزیمم تفکیک و جداسازی را فراهم می‌آورد. از بین جداسازهای خطی، آن جداسازی که حاشیه داده‌های آموزشی را حداکثر می‌کند خطای تعمیم را حداقل خواهد کرد. نقاط داده‌ای ممکن است ضرورتاً نقاط داده‌ای در فضای R2 نباشند و ممکن است در فضای چند بعدی Rn مربوط باشند. دسته‌بندهای خطی بسیاری ممکن است این خصوصیت را ارضا کنند اما SVM به دنبال جداکننده‌ای است که حداکثر جداسازی را برای دسته‌ها انجام دهد.

همان‌طور که در شکل (8-2) مشاهده می‌شود فراصفحه‌هایی که از نزدیکی داده‌های آموزش می‌گذرند حساس به خطا می‌باشند و احتمال اینکه برای داده‌های خارج از مجموعه آموزش قدرت تعمیم دهی خوبی داشته باشند بسیار کم است. در عوض، به نظر می‌رسد فراصفحه ای که بیشترین فاصله را از تمام نمونه‌های آموزشی دارد قابلیت‌های تعمیم دهی مناسبی را فراهم آورد. نزدیک‌ترین داده‌های آموزشی به فراصفحه‌های تفکیک کننده را بردار پشتیبان (SV ) نامیده می‌شوند. اگر مجموعه داده به صورت {(Xn,Yn),…,(X2,Y2),(X1,Y1)} نشان داده شود. Yi می‌تواند مقدار 1 و 1- دریافت کند که توسط این ثابت‌ها دسته‌های نقاط Xi مشخص می‌گردد که هر Xi یک بردار n بعدی است. هنگامی که داده‌های آموزشی که در دسته‌های صحیح دسته‌بندی شده‌اند را در اختیار داریم، SVM توسط تقسیم‌بندی فراصفحه ای آن‌ها را از هم جدا کرده و در دسته‌های جداگانه قرار می‌دهد به طوری که W^TX+d=0 , بردار W نقاط عمودی فراصفحه‌ها را جدا می‌کند و b میزان حاشیه را مشخص می‌کند. فراصفحه‌های موازی را می‌توان به صورت W.X+d=1 و W.X+d=-1 تعریف کرد.
اگر داده‌های آموزشی به صورت خطی جدایی پذیر باشند، می‌توان فراصفحه‌ها را به طوری انتخاب نمود که هیچ نمونه‌ای میان آن‌ها نباشد و سپس تلاش کرد تا فاصله آن‌ها را به حداکثر رسانید. برای هر نمونه i از داده‌ها رابطه زیر را داریم:

می‌توان تصور کرد SVM بین دو دسته داده صفحه‌ای را ترسیم می‌کند و داده‌ها را در دو طرف این صفحه تفکیک می‌نماید. این فراصفحه به گونه‌ای قرار می‌گیرد که ابتدا دو بردار از یکدیگر دور می‌شوند و به گونه‌ای حرکت می‌کنند که هر یک به اولین داده نزدیک به خود برسد. سپس صفحه‌ای که در میان حد واسط این دو بردار رسم می‌شود از داده‌ها حداکثر فاصله را خواهد داشت و تقسیم کننده بهینه است.
تا اینجا، با این فرض که نمونه‌های آموزشی به صورت خطی جدایی پذیرند به استفاده از الگوریتم ماشین بردار پشتیبان پرداختیم. همان‌طور که می‌دانیم در عمل توزیع داده‌های دسته‌های مختلف ممکن است به راحتی جدایی پذیر نبوده و دارای تداخل باشد . در این صورت، تفکیک سازی دقیق نمونه‌ها ممکن است سبب تعمیم دهی ضعیف گردد.
یک راه حل این است که مقداری خطا در دسته‌بندی را بپذیریم. این کار با معرفی متغیر بی دقت (ξi) انجام می‌شود که نشانگر نمونه‌هایی است که توسط تابع W^TX+d=0 غلط ارزیابی می‌شوند. این روش که به SVM با حاشیه‌ی نرم معروف است که اجازه می‌دهد بعضی از نمونه‌ها در ناحیه اشتباه قرار گیرند سپس آن‌ها را جریمه می‌کند؛ لذا این روش برخلاف SVM حاشیه‌ی سخت برای مواردی که نمونه‌های آموزشی به صورت خطی جدایی پذیر نیستند قابل استفاده است.
با معرفی متغیر ξi محدودیت‌های قبلی ساده‌تر شده و رابطه (2-7) به صورت زیر تغییر می‌کند:

ماشین بردار پشتیبان با حاشیه نرم تلاش می‌کند ξi را صفر نگه دارد در حالی که حاشیه‌های دسته‌بند را حداکثر می‌کند. SVM تعداد نمونه‌هایی که به اشتباه دسته‌بندی شده‌اند را کمینه نمی‌کند بلکه سعی دارد مجموع فواصل از حاشیه‌ی فراصفحه‌ها را کمینه نماید . مقادیر بزرگ برای c سبب می‌شود که رابطه (2-6) مانند روش با حاشیه سخت عمل کند. ماشین بردار پشتیبان با حاشیه نرم همیشه یک راه حل پیدا می‌کند و در مقابل مجموعه داده‌هایی که دارای یک عضو جدا هستند مقاوم است و به خوبی عمل می‌کند.