به دلیل اینکه قانون اعداد بزرگ تضمین می کند که در احتمال[57]، ریسک تجربی به ریسک مورد انتظار همگرا می شود، میتوان به جای حداقل سازی ریسک مورد انتظار، ریسک تجربی را حداقل کرد.این موضوع را می توان تحت عنوان اصل حداقل سازی ریسک تجربی[58] اینگونه بیان کرد که اگر ریسک تجربی به ریسک واقعی همگرا شود، آنگاه حداقل ریسک تجربی ممکن است به حداقل ریسک واقعی همگرا شود.اگر این همگرایی برقرار نباشد نمی توان هیچ نتیجه ای بر اساس مجموعه داده ها گرفت و گفته می شود که ناسازگاری وجود دارد.
Vapnik و chervonenkis بیان کردند که شرط لازم و کافی برای داشتن سازگاری در اصل حداقل سازی ریسک تجربی، محدود بودن بعد VC فضای H میباشد.همانطور که قبلا بیان شد بعد VC فضای H (یا بعد VC طبقه بندی کننده ) یک عدد طبیعی است که بیانگر ماکزیمم تعداد نقاط داده میباشد که می تواند با توجه به تمام حالات ممکن توسط مجموعه توابع از هم جدا شوند.بعد VC همچنین بیانگر پیچیدگی مجموعه H است و اغلب متناسب با تعداد پارامترهای آزاد طبقه بندی کننده است]11[.
آنها یک حد بالا برای میزان انحراف ریسک تجربی نسبت به ریسک مورد انتظار بدست آوردند.این حد که دارای احتمال است، به صورت زیر بیان می شود:
(2-4)
که در آن h بعد VC تابع می باشد.
از این رابطه به طور واضح میتوان فهمید که برای داشتن یک ریسک مورد انتظار کوچک(جهت داشتن قدرت تعمیم خوب)، باید هم ریسک تجربی و هم نسبت بین بعد VC و تعداد نقاط داده کوچک باشد.از آنجا که ریسک تجربی معمولا یک تابع نزولی نسبت به h است می توان نتیجه گرفت که برای تعداد مشخص نقاط داده، یک مقدار بهینه h موجود میباشد.
انتخاب مناسب h (که در اکثر تکنیک ها توسط تعداد پارامترهای آزاد مدل مربوطه کنترل می شود) برای داشتن عملکرد خوب بسیار مهم است مخصوصا زمانی که تعداد نقاط داده کم میباشند.مثلا وقتی از پرسپترون چندلایه یا شبکه RBF استفاده می شود، تعیین بعد VC معادل با مساله پیدا کردن تعداد مناسبی از واحدهای مخفی است که مساله مشکلی است.رابطه بالا بیانگر این است که اصل حداقل سازی ریسک تجربی را میتوان با اصل بهتری جایگزین نمود که در بخش بعدی توضیح داده خواهد شد]11[.
2-8-5-5حداقل سازی ریسک ساختاری[59]
تکنیک حداقل سازی ریسک ساختاری که توسط vapnik بیان شد تلاش و کوششی جهت مقابله با مسئله انتخاب بهینه بعد VC بود. بطور واضح از معادله(2-4) مشخص است که داشتن مقدار حداقل برای ریسک تجربی لزوما به معنی داشتن یک مقدار حداقل برای ریسک مورد انتظار نیست که این منجر به بیان اصلی تحت عنوان اصل حداقل سازی ریسک ساختاری[60] شد.این اصل بر این اساس پایه گذاری شد که برای کوچک کردن ریسک مورد انتظار طبق معادله (2-4) باید هم بعد VC و هم ریسک تجربی همزمان حداقل شوند.
نیاز اصلی برای پیاده سازی این اصل، داشتن یک ساختار تو در تو در فضای فرضیه است:
با این خاصیت که و بعد VC مجموعه Hn میباشد.
با توجه به معادله(2-4) باید مسئله زیر حل شود(از قسمت های لگاریتمی صرف نظر شده است):
(2-5)
اگرچه اصل حداقل سازی ریسک ساختاری از نظر ریاضی بسیار واضح است ولی پیاده سازی آن به دلایل زیر دشوار است:
1) محاسبه بعد VC فضای H دشوار بوده و مدل های محدودی وجود دارند که دارای روش مشخصی برای محاسبه بعد VC هستند.
2) حتی با فرض اینکه بتوان بعد VC فضای H را محاسبه کرد، حداقل سازی رابطه (2-5) مشکل خواهد بود.
هدف از بکارگیری الگوریتم SVM، حداقل کردن یک حد برای بعد VC و همچنین حداقل کردن تعداد خطاهای آموزشی بطور همزمان است]11[.
2-8-6 ماشین بردار پشتیبان طبقه بندی کننده خطی با داده های جدا شدنی به طور خطی]9،10،11،12،14[
در این بخش ساده ترین حالت طبقه بندی کننده SVM که SVM خطی با داده های جدا شدنی به طور خطی است را مورد بررسی قرار میدهیم :
فرض کنید تعدادی از بردارهای ویژگی یا الگوهای آموزشی به صورت داریم که هر کدام یک بردار ویژگی m بعدی بوده و دارای برچسب است و .هدف حل یک مساله دسته بندی دو کلاسه به صورت بهینه است.فرض کنید این دو کلاس را بخواهیم با تابع تمایز f(x) و ابر صفحه H با معادله زیر از هم جدا کنیم :
(2-6)
اگر نمونه های دو کلاس را با نام های مثبت(+1) و منفی(-1) بیان کنیم، میتوان فوق صفحاتی را در نظر گرفت که نمونه های مثبت را از نمونه های منفی جدا کنند.نقاطی که روی این فوق صفحات جداکننده قرار میگیرند در معادله صدق می کنند که W بردار عمود بر فوق صفحه، فاصله عمودی از فوق صفحه تا مبدا ، اندازه اقلیدسی[61] بردار W و b مقدار بایاس[62] است .vapnik ثابت کرد که بعد VC برای طبقه بندی کننده هایی از نوع ابر صفحات کانونی دارای یک کران بالاست که این کران بالا با توان دوم نرم بردار وزن یعنی نسبت مستقیم دارد.در واقع اگر ما را محدود کرده و مینیمم کنیم، بعد VC طبقه بندی کننده را مینیمم کرده ایم و تخمین ما از مقدار ریسک واقعی به صورت احتمالی دقیق تر بوده و خاصیت تعمیم دسته بندی کننده بیشتر خواهد بود.
رابطه بین خاصیت تعمیم طبقه بندی کننده با را میتوان به طریق دیگر نیز توجیه کرد.فرض کنید داده های دو کلاس جداپذیر باشند و بردارهای ویژگی مرزی کلاس اول روی ابر صفحه و بردارهای ویژگی مرزی کلاس دوم روی ابر صفحه قرار گیرند.ابر صفحات و به این صورت تعریف میشوند :
(2-7)
الگوهایی که بر روی ابر صفحات و قرار میگیرند، بردارهای پـشتیبان نامیده میشوند.ناحیه بین دو ابرصفحه و را ناحیه مرزی[63] گویند.فاصله بین دو ابرصفحه و برابر با خواهد بود.طراحی ابرصفحه با بیشترین عرض ناحیه مرزی یا ناحیه مرزی بهینه[64] بر این استوار است که با شرط درست طبقه بندی شدن الگوها، عرض ناحیه مرزی حداکثر شود تا بتواند بهترین تفکیک پذیری را بین دو کلاس داشته باشد.یعنی ماکزیمم شود و مینیمم شود.هدف این است که اولا الگوها درست طبقه بندی گردند و ثانیا بر روی و یا خارج از ناحیه مرزی واقع شوند.فرض کنید تمام داده های آموزشی در محدوده زیر قرار گیرند :
(2-8)
ترکیب این دو معادله را میتوان به فرم زیر نوشت :
.
فاصله بین ابرصفحه جداکننده و نزدیک ترین داده اموزشی را حاشیه مینامیم. بی نهایت ابرصفحه جداکننده میتوانیم داشته باشیم.اما از میان این ابرصفحه های جداکننده باید مناسبترین را انتخاب کنیم.طبیعتا آن تفکیک کننده ایی که فاصله را بیشینه کند، ابرصفحه جداکننده بهینه خواهد بود.
برای پیدا کردن ابرصفحه جداکننده بهینه، لازم است صفحه ای که فاصله بین ابرصفحه و نزدیکترین داده ها(نمونه ها) به این ابر صفحه را بیشینه می کند، پیدا نمود.فاصله نزدیکترین نمونه برابر است با:
(2-9)
مقدار بیشینه و کمینه مناسب به ترتیب برابر است با 1و 1-.بدین ترتیب معادله بالا به صورت زیر در می آید:
بنابراین مسئله به کمینه کردن تبدیل می شود. پس در واقع طراحی یک طبقه بندی کننده ابرصفحه ای با ناحیه مرزی بهینه به صورت زیر خواهد بود :
(2-10)
واضح است که داریم : و .
[جمعه 1400-07-30] [ 07:16:00 ب.ظ ]
|