الگوریتم پرسپترون میانگین‏‏دار ()

1. 1. به ازای انجام بده

1. 1. به ازای انجام بده

1. 1. اگر آنگاه

1. 1. پایان حلقه دوم

1. 1. پایان حلقه اول

1. 1. بازگرداندن مقدار به عنوان مقدار خروجی

شکل ۳-۲: الگوریتم پرسپترون میانگین‏دار
۳-۱-۱-۲. ماشین بردار پشتیبان
ماشین بردار پشتیبان شیوه دیگری برای حل یک مسئله یادگیری است که در آن مسئله در قالب یک مسئله بهینه ‏سازی حل می‏شود. ماشین بردار پشتیبان^[۱۹۸] بر اساس جداسازهای با بیشترین حاشیه هستند. ایده اصلی در جداسازهای با بیشترین حاشیه، یافتن ابر صفحه است که رده‏ها را با بیشترین حاشیه از یکدیگر افراز نمایند. حاشیه به فاصله‏ای گفته می‏شود که دو خط موازی جداساز به صورت مساوی از دو طرف طی می‏کنند تا یکی از آنها به یکی از داده‏ها برخورد نماید. از لحاظ تئوری می‏توان ثابت کرد که جداسازی که بیشترین حاشیه را داشته باشد قابلیت تعمیم بیشتری نیز خواهد داشت [۱۱۵،۱۱۶] و با تغییرات کوچک در داده‏ها صحت رده‏بندی حفظ می‏شود. علاوه برآن می‏توان نشان داد که تنها پارامترهایی به جداسازی بیشترین حاشیه منجر می شوند که اگر آنها را مستقل از b در نظر بگیریم، در آن‏ها کوچک باشد.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

حالتی را درنظر بگیرید که داده‏ها قابل تفکیک هستند و اندازه حاشیه برابر با ۱ است. بدین معنا که مجموعه‏ای از پارامتر‏ها وجود دارد که داده‏های آموزشی را با حاشیه برگی رده‏بندی می‏نماید. در این صورت مسئله SVM به صورت رابطه‏ی۳-۲ در می‏آید.

رابطه(۳-۲)

مسئله بهینه ‏سازی SVM به دنبال یافتن بردار وزن w و گرایش b است به گونه‏ای که نرم کمینه شود. در بسیاری از موارد این مسئله بهینه ‏سازی غیر عملی است زیرا ممکن است چنین پارامترهایی وجود نداشته باشد که از محدودیت مسئله بهینه ‏سازی تبعیت نمایند. بعلاوه در مواقعی هم که داده‏ها تفکیک‏پذیر هستند عموما ترجیح نمی‏دهیم که الگوریتم به بهترین کارایی رده‏بندی بر روی داده‏های آموزشی برسد؛ به عبارتی دیگر مقداری خطا قابل تحمل است، در نتیجه SVM‏های «نرم‏حاشیه»^[۱۹۹] مطرح شدند. مفهوم SVM نرم‏حاشیه این است که لزومی ندارد که تمام نمونه‏ها با حاشیه ۱ رده‏بندی شوند. علاوه بر آن، به ازای هر نمونه‏ای که از محدودیت رده‏بند SVM تبعیت نمی‏کند، محاسبه می‏شود که آن نمونه چقدر با موقعیتی فاصله دارد که در آن محدودیت SVM «سخت‏حاشیه»^[۲۰۰] ارضا می‏شود؛ این اندازه به عنوان انعطاف آن نمونه شناخته می‏شود. مسئله SVMهای نرم‏حاشیه به فرم رابطه‏ی ۳-۳ می‏باشد.

رابطه (۳-۳)

در معادله SVMهای نرم‏حاشیه تابع هدف از دو مولفه تشکیل شده است؛ اولین مولفه را ملزم به یافتن پاسخی می‏کند که قابلیت تعمیم خوبی داشته باشد. مولفه دوم (مجموع مقادیر متغیر‏های انعطاف) SVM را ملزم می‏نماید که بیشتر داده‏های آموزشی را به درستی رده‏بندی نماید. پارامتر C ≥ ۰موازنه‏ای میان تطبیق رده‏بند با داده‏های آموزشی و یافتن یک بردار وزنی کوچک می‏باشد. در صورتی کهC به بی‏نهایت میل نماید شیوه SVM نرم‏حاشیه به SVM سخت‏حاشیه نزدیک می‏شود که در آن تمام داده‏های آموزشی باید به درستی رده‏بندی شوند. در صورتی که C به صفر میل کند SVM کمتر به درست رده‏بندی کردن داده‏های آموزشی اهمیت می‏دهد و به سادگی یک بردار وزن کوچک را جستجو می‏کند.
همان‏طور که گفته شد،در محدودیت مربوط به SVM نرم‏حاشیه، دیگر نیازی نیست که نمونه با حاشیه ۱ رده‏بندی شود و به جای آن هر نمونه با حاشیه رده‏بندی می‏شود. اگر پارامتر‏ها به گونه‏ای یافت شوند که در آن تمام نمونه‏های آموزشی با حاشیه ۱ رده‏بندی شوند آنگاه تمام ها می‏توانند برابر با صفر قرار داده شوند. اما به عنوان نمونه در مورد داده‏های تفکیک‏ناپذیر این متغیر‏های انعطاف‏ می‏توانند نماینگر خطا باشند. هرچند که تعداد محدودیت‏ها به تعداد داده‏هاست ولی می‏توان توسط شرایط Karush-Kuhn-Tucker [21] نشان داد که در یک بردار وزن بهینه تنها تعداد بسیار کمی از آن‏ها مقدار غیر صفر دارند بدین معنا که هنگامی که wوb مقدار بهینه داشته باشند مطلقا بزرگتر از یک بوده و به ازای بسیاری ازn ها برابر با صفر است. نمونه‏هایی که وزن متناظر با آن‏ها غیر صفر است بردار پشتیبان خوانده می‏شوند زیرا تنها این نمونه‏ها هستند که در تصمیم‏ گیری رده‏بند تاثیر خواهند داشت.
الگوریتم‏های بسیاری برای حل کردن SVM وجود دارند ساده‏ترین آن‏ها تبدیل آن به یک مسئله برنامه ریزی غیرخطی[۲۱] و اعمال یک بسته بهینه ‏سازی عمومی بر روی آن است. پس از تبدیل مسئله SVM به یک مسئله برنامه ریزی غیرخطی مسئله به فرم زیر در می آید:

رابطه(۳-۴)