(‏۴‑۴)
به جز در مواردی محدود، معمولاً P(x,y) را نداریم و مجبوریم از خطای تجربی (۴-۵) به عنوان برآوردی از ریسک مورد انتظار استفاده کنیم.
(‏۴‑۵)
قضیه VC؛ اگر h بعد VC تابع f باشد، آنگاه با احتمال برای ریسک مورد انتظار داریم:

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

(‏۴‑۶)
اگرچه معمولاً محکم نیست و در کاربرد به طور مستقیم استفاده نمی­ شود، ولی از لحاظ مفهومی بسیار مفید است. این حد منجر به پیدایش اصل کمینه سازی ریسک ساختاری شد.
کمینه­سازی خطای ساختاری به جست و جوی تابعی می ­پردازد که کران بالای (۴-۶) را کمینه کند. حد (۴-۶) دو مؤلفه دارد که بایستی کمینه شوند. به این ترتیب برای کمینه کردن مؤلفه VC Confidence، در میان خانواده توابع بایستی خانواده­هایی با کمترین بعد VC و برای کمینه کردن ریسک تجربی، از میان این خانواده تابعی که ریسک تجربی خانواده مربوطه را کمینه می­ کند بایستی انتخاب کرد. یک رهیافت ساده برای کمینه کردن ریسک ساختاری این است که همیشه از خانواده توابع خطی که دارای کمترین VC Confidence در بین تمام توابع می­باشند، استفاده کرد. بنابراین طبقه ­بندی، که ریسک ساختاری را کمینه می­ کند، تابعی خطی است که ریسک تجربی را کمینه کند. SVM از این رهیافت استفاده می­ کند و همواره در خانواده توابع خطی در جست­و­جوی تابعی با کمترین ریسک تجربی است.
ماشین­های بردار پشتیبان (SVM)
SVM یک نوع سیستم یادگیری است که هم برای دسته­بندی داده ­های ورودی و هم برای تخمین و برآورد تابع برازش داده ­ها به کار می­رود، به طوری که کمترین خطا در دسته­بندی داده ­ها و تابع برازش رخ دهد. داده ­ها کلاً به سه دسته آموزشی، صحت­سنجی و آزمون تقسیم می­کنیم به طوری که داده ­های آموزشی باعث آموزش ماشین بردار پشتیبان می­شوند، داده ­های صحت­سنجی به واسنجی پارامترهای ماشین می ­پردازد و در نهایت از این ماشین برای طبقه ­بندی یا برآورد داده ­های آزمون استفاده می­ شود. این روش بر مبنای تئوری بهینه­سازی مقید است که از اصل کمینه­سازی خطای ساختاری استفاده کرده و منجر به یک جواب بهینه کلی می­گردد (Vapnik, 1998). که این اصل در بالا به طور خلاصه توضیح داده شده است و برای توضیحات بیشتر به منابع رجوع شود.

طبقه ­بندی ماشین بردار پشتیبان
در آغاز دسته­بندی داده ­ها را برای حالتی که به صورت خطی جدا­پذیر باشند بررسی می­کنیم. اگر نمونه­ها به صورت خطی جدا­پذیر باشند، باید دنبال بهترین خط یا ابرصفحه­ای بود که بتواند دو دسته را از هم تفکیک کند.
قضیه ابرصفحه جداساز؛ اگر C و D دو مجموعه محدب باشند که با هم هیچ اشتراکی ندارند آنگاه وجود دارد که و . ابرصفحه را ابرصفحه جداساز برای مجموعه­های C و D می­نامند.
در عبارت w.x+b=0، بردار w را بردار وزن می­نامند که بر ابرصفحه جداکننده، عمود بوده و b مقدار پیش­قدر^[۲۹] می­باشد. صفحات مرزی به صورت زیر تعریف می­شوند:
(‏۴‑۷)
الگو­هایی که بر روی این صفحات قرار دارند، نزدیک­ترین فاصله را با ابرصفحه بهینه دارند که به این الگوها بردار پشتیبان می­گویند. ناحیه­ی بین دو ابرصفحه H⁺ و H^– را حاشیه^[۳۰] یا ناحیه مرزی می­گویند.
تابع طبقه ­بندی در روش SVM به شکل زیر است:
(‏۴‑۸)
که برای یافتن ابرصفحه بهینه می­بایستی مسأله بهینه­سازی محدب زیر را حل کرد:
(‏۴‑۹)
هدف ابرصفحه بهینه این است که از بین تمام ابرصفحه­هایی که قشر محدب دو کلاس را از هم جدا می­ کنند، بهترین آنها ابرصفحه­ای است که با بیشترین حاشیه، قشرهای محدب دو کلاس را جدا کند. برای جلوگیری از مقیاس شدن w و b، به طور قراردادی اندازه تابع تصمیم را به ازای نزدیک­ترین نمونه با آن برابر ۱ در نظر می­گیریم:
(‏۴‑۱۰)
از طرفی فاصله هر نمونه تا ابرصفحه برابر است با:
(‏۴‑۱۱)
به این ترتیب می­توان مشاهده کرد که فاصله نزدیک­ترین نمونه­ها از هر کلاس برابر و عرض حاشیه برابر با است. پس می­توان با بیشینه کردن حاشیه، مقدار را کمینه کرد و با قرار دادن ||w||² به جای ||w||، مسأله معادلی حاصل می­ شود که تابع هدفش هم مشتق­پذیر و هم هموار است. قید نیز به نمونه­ها اجازه ورود به حاشیه را نمی­دهد. بنابراین به راحتی می­توان برای تمام مسائل بهینه­سازی مقید، تابع لاگرانژ را تعریف کرد. شکل ذیل حاشیه و طبقه ­بندی دو دسته را با هم نشان می­دهد.

Class 1
Class 2
شکل ‏۴‑۳: نمایشی از طبقه ­بندی داده ­ها به دو دسته و حاشیه­ اطمینانی که داده ­های دو دسته با هم دارند
برای حل این مسأله­ بهینه­سازی، تابع لاگرانژی زیر را تشکیل می­دهیم و ضرایب لاگرانژ را خواهیم یافت:
(‏۴‑۱۲)
برای اینکه جواب را پیدا کنیم، باید این جواب در شرایط ^[۳۱]KKT صدق کند که در ذیل مشاهده می­ شود. شرایط KKT روش لاگرانژ را برای حالت هایی که قیود به صورت نامساوی باشند، تعمیم می­دهد.
(‏۴‑۱۳)
با قرار دادن مقدار w از رابطه قبل در تابع لاگرانژ، به مساله­ی دوگان^[۳۲] برای بهینه­سازی مقید خواهیم رسید:
(‏۴‑۱۴)
که:
(‏۴‑۱۵)
حل این مسأله بهینه­سازی­ دوگان، با بهینه­سازی درجه دوم^[۳۳] میسر است و ضرایب لاگرانژ با بهره گرفتن از این روش بدست می­آیند.
هر الگویی ضریب لاگرانژ مربوط به خود را دارد. الگوهایی که ضریب لاگرانژ آنها بزرگتر از صفر است، همان بردار پشتیبان می­باشند.
(‏۴‑۱۶)
که x_sv(+1) و x_sv(-1) به ترتیب، بردارهای پشتیبان قرار گرفته در دسته با برچسب ۱+ و ۱- هستند. پس از تعیین بردارهای پشتیبان و مقدار پیشقدر، تابعِ ممیّز که دو کلاس را از هم جدا می­ کند می ­تواند به صورت زیر نوشته شود:
(‏۴‑۱۷)
پس با بهره گرفتن از بردارهای پشتیبان می­توان تابع ممیّز را ساخت و با بهره گرفتن از بردارهای پشتیبان و تابع ممیّز می­توان فهمید که داده ­های آزمایشی در کدام دسته­بندی قرار می­گیرند. پس دیگر آن دسته از داده ­های آموزشی که بردار پشتیبان نیستند، به دردی نمی­خورند و می­توان آنها را حذف کرد.