وبلاگ

شکل (2-12)- ابر صفحه جدا کننده بهینه در دو بعد
مساله بالا را می­توان توسط تکنیک های بهینه سازی QP^[65] حل کرد.برای حل این مساله تابع لاگرانژی زیر را تشکیل داده و ضرایب لاگرانژ  را بدست می­آوریم .

(2-11)

مسئله بالا نسبت به  باید مینیمم شود و نسبت به متغییر  ها باید ماکزیمم شود. باید این مسئله را با حذف متغییر های  حل نمائیم.پس مسئله موجود یک مسئله ماکزیمم سازی براساس  خواهد بود که این مسئله را حل می­کنیم .برای اینکه  جواب مساله باشد، این جواب باید در شرایط ^[66]KKT صدق کند و در نقطه جواب، مشتق L نسبت به  صفر باشد.با مساوی قرار دادن مشتق برابر صفر به معادلات زیر می­رسیم :

(2-13)
(2-12)

با قرار دادن مقدار w از رابطه فوق در  به مساله دوگان برای بهینه سازی مقید خواهیم رسید:

(2-14)
این فرمول از ماشین های بردار پشتیبان را ماشین بردار پشتیبان حاشیه سخت می­نامیم.چون طبقه بندی را به طور کامل انجام می­دهد و هیچگونه تخطی ندارد.
پس از حل مسئله دوگان بهینه سازی، ضرایب لاگرانژ بدست می­آیند.در واقع هر کدام از ضرایب  متناظر با یکی از الگوهای  می­باشند.الگوهای  را که متناظر با ضرایب  (مثبت)هستند، بردارهای پشتیبان  می­نامیم.مقدار بردار وزن و b از روابط زیر بدست می­آیند:

(2-15)
تابع تمایز برای طبقه بندی یک الگوی ورودی x به صورت زیر خواهد بود :

(2-16)

2-8-7ماشین بردار پشتیبان طبقه بندی کننده خطی با داده های جدا نشدنی به طور خطی (حالت جدایی ناپذیر)

در قسمت قبل، داده های آموزشی را جداپذیر خطی فرض کردیم .وقتی که داده های آموزشی جدا پذیر خطی نباشند یعنی، داده هایی باشند که وارد کلاسی غیر از کلاس خودشان شده باشند.در واقع تخطی انجام گرفته باشد. هیچ جواب شدنی وجود ندارد.در اینجا ماشین بردار پشتیبان را تعمیم می دهیم تا برای حالت های جدایی ناپذیر هم کاربرد داشته باشد.اکنون حالتی را درنظر می گیریم که هنوز به دنبال یک ابرصفحه جداکننده خطی هستیم با این تفاوت که ابرصفحه جداکننده ای که به طور کامل در نامعادله (2-10)صدق کند وجود ندارد.برای بررسی این حالت یک متغیر جدید به نام متغیرهای کمبود^[67]  تعریف می­کنیم که بیانگر میزان انحراف از نامعادله (2-10) است.بنابراین هدف الگوریتم، ماکزیمم کردن حاشیه مربوطه در مقابل پرداختن یک هزینه متناسب با انحراف از نامعادله (2-10) تعریف می­ شود. واضح است كه هر چقدر مجموع مقادير متغيرهاي  بیشتر شود، از حالت بهينه دورتر خواهيم شد و خطا بيشتر مي­گردد.بیان ریاضی مساله به فرم زیر می­باشد:

(2-17)

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

(2-18)
که  و  است.برای محاسبه جواب بهینه، شرایطKKT باید بررسی شود.به این ترتیب که در اینجا معادله لاگرانژ بالا باید نسبت به  و نسبت به  ماکزیمم شود.
(2-19)

(2-20)

(2-21)
(2-22)
(2-23)

(2-24)
از رابطه (2-18) به ترتیب نسبت به  و  و  مشتق جزئی می­گیریم.

(2-25)

(2-27)