از بکارگيري الگوريتم SVM، حداقل کردن يک حد براي بعد VC و همچنين حداقل کردن تعداد خطاهاي آموزشي بطور همزمان است]11[.

2-8-6 ماشين بردار پشتيبان طبقه بندي کننده خطي با داده هاي جدا شدني به طور خطي]9،10،11،12،14[
در اين بخش ساده ترين حالت طبقه بندي کننده SVM که SVM خطي با داده هاي جدا شدني به طور خطي است را مورد بررسي قرار ميدهيم :
فرض کنيد تعدادي از بردارهاي ويژگي يا الگوهاي آموزشي به صورت داريم که هر کدام يک بردار ويژگي m بعدي بوده و داراي برچسب است و .هدف حل يک مساله دسته بندي دو کلاسه به صورت بهينه است.فرض کنيد اين دو کلاس را بخواهيم با تابع تمايز f(x) و ابر صفحه H با معادله زير از هم جدا کنيم :

اگر نمونه هاي دو کلاس را با نام هاي مثبت(+1) و منفي(-1) بيان کنيم، ميتوان فوق صفحاتي را در نظر گرفت که نمونه هاي مثبت را از نمونه هاي منفي جدا کنند.نقاطي که روي اين فوق صفحات جداکننده قرار ميگيرند در معادله صدق ميکنند که W بردار عمود بر فوق صفحه، فاصله عمودي از فوق صفحه تا مبدا ، اندازه اقليدسي64 بردار W و b مقدار باياس65 است .vapnik ثابت کرد که بعد VC براي طبقه بندي کننده هايي از نوع ابر صفحات کانوني داراي يک کران بالاست که اين کران بالا با توان دوم نرم بردار وزن يعني نسبت مستقيم دارد.در واقع اگر ما را محدود کرده و مينيمم کنيم، بعد VC طبقه بندي کننده را مينيمم کرده ايم و تخمين ما از مقدار ريسک واقعي به صورت احتمالي دقيق تر بوده و خاصيت تعميم دسته بندي کننده بيشتر خواهد بود.

رابطه بين خاصيت تعميم طبقه بندي کننده با را ميتوان به طريق ديگر نيز توجيه کرد.فرض کنيد داده هاي دو کلاس جداپذير باشند و بردارهاي ويژگي مرزي کلاس اول روي ابر صفحه و بردارهاي ويژگي مرزي کلاس دوم روي ابر صفحه قرار گيرند.ابر صفحات و به اين صورت تعريف ميشوند :

الگوهايي که بر روي ابر صفحات و قرار ميگيرند، بردارهاي پـشتيبان ناميده ميشوند.ناحيه بين دو ابرصفحه و را ناحيه مرزي66 گويند.فاصله بين دو ابرصفحه و برابر با خواهد بود.طراحي ابرصفحه با بيشترين عرض ناحيه مرزي يا ناحيه مرزي بهينه67 بر اين استوار است که با شرط درست طبقه بندي شدن الگوها، عرض ناحيه مرزي حداکثر شود تا بتواند بهترين تفکيک پذيري را بين دو کلاس داشته باشد.يعني ماکزيمم شود و مينيمم شود.هدف اين است که اولا الگوها درست طبقه بندي گردند و ثانيا بر روي و يا خارج از ناحيه مرزي واقع شوند.فرض کنيد تمام داده هاي آموزشي در محدوده زير قرار گيرند :

ترکيب اين دو معادله را ميتوان به فرم زير نوشت :
Error! Bookmark not defined.
فاصله بين ابرصفحه جداکننده و نزديک ترين داده اموزشي را حاشيه ميناميم. بي نهايت ابرصفحه جداکننده ميتوانيم داشته باشيم.اما از ميان اين ابرصفحه هاي جداکننده بايد مناسبترين را انتخاب کنيم.طبيعتا آن تفکيک کننده ايي که فاصله را بيشينه کند، ابرصفحه جداکننده بهينه خواهد بود.
براي پيدا کردن ابرصفحه جداکننده بهينه، لازم است صفحه اي که فاصله بين ابرصفحه و نزديکترين داده ها(نمونه ها) به اين ابر صفحه را بيشينه ميکند، پيدا نمود.فاصله نزديکترين نمونه برابر است با:

مقدار بيشينه و کمينه مناسب به ترتيب برابر است با 1و 1-.بدين ترتيب معادله بالا به صورت زير در مي آيد:

بنابراين مسئله به کمينه کردن تبديل ميشود. پس در واقع طراحي يک طبقه بندي کننده ابرصفحه اي با ناحيه مرزي بهينه به صورت زير خواهد بود :

واضح است که داريم :و .

مساله بالا را ميتوان توسط تکنيک هاي بهينه سازي QP68 حل کرد.براي حل اين مساله تابع لاگرانژي زير را تشکيل داده و ضرايب لاگرانژ را بدست ميآوريم .

مسئله بالا نسبت به بايد مينيمم شود و نسبت به متغيير ها بايد ماکزيمم شود. بايد اين مسئله را با حذف متغيير هاي حل نمائيم.پس مسئله موجود يک مسئله ماکزيمم سازي براساس خواهد بود که اين مسئله را حل ميکنيم .براي اينکه جواب مساله باشد، اين جواب بايد در شرايط 69KKT صدق کند و در نقطه جواب، مشتق L نسبت به صفر باشد.با مساوي قرار دادن مشتق برابر صفر به معادلات زير ميرسيم :

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

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

تابع تمايز براي طبقه بندي يک الگوي ورودي x به صورت زير خواهد بود :

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

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

که و است.براي محاسبه جواب بهينه، شرايطKKT بايد بررسي شود.به اين ترتيب که در اينجا معادله لاگرانژ بالا بايد نسبت به و نسبت به ماکزيمم شود.

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

و روابط (2-25) و (2-26) را در مسئله (2-18)جايگذاري کرده و دوگان مسئله را به صورت زير مينويسيم:

همانطور كه ملاحظه ميشود حل مسأله جدايي ناپذير مشابه حل آن در حالت جدايي پذير است با اين تفاوت كه محدوده تغييرات ضرايب لاگژانرفرق ميكند.پس از بدست آوردن ضرايب لاگرانژ الگوهايي كه ضرايب لاگرانژ آنها در رابطه زير صدق ميکنند، بردار پشتيبان هستند.

مقدار w و شکل تابع تمايز هم مشابه حالت جدايي پذير خواهد بود.ابرصفحه بدست آمده در حالت جدايي نا پذير را ابرصفحه با ناحيه مرزي نرم71 مينامند.در واقع تنها اختلاف بين ماشين بردار پشتيبان حاشيه نرم L1 و ماشين بردار پشتيبان حاشيه سخت مقدارايي است که از مقدار نميتواند تجاوز کند.()
اين شرايط نتايجي را در بر دارد که در زير به آنها اشاره مي کنيم:
اگر آن گاه . در اين صورت قابل طبقه بندي هستند.
اگر آن گاه و که در اين صورت و بردار پشتيبان است.که بردارهاي پشتيبانهايي با را يک بردار پشتيبان بيکران ميناميم.
اگر آن گاه و . بنابراين يک بردار پشتيبان است، که بردارهاي پشتيبان با را بردار پشتيبان کراندار ميناميم که اگر ، قابل طبقه بندي است و اگر قابل طبقه بندي نخواهد بود.
2-8-8 ماشين بردار پشتيبان غير خطي
ماشين هاي بردار پشتيبان ذکر شده در قسمت هاي قبل ، براي دسته بندي الگوهاي يک مسئله دو کلاسه، از مرزهاي جداکننده خطي و از يک ابرصفحه استفاده ميکنند.در واقع حاصلضرب داخلي بردار ورودي با هر کدام از بردارهاي پشتيبان در فضاي- بعدي ورودي محاسبه ميگردد.Vapnik با استفاده از مفهوم حاصلضرب داخلي در فضاي هيلبرت و قضيه هيلبرت- اشميت نشان داد که ابتدا مي توان بردار ورودي را با يک تبديل غير خطي به يک فضاي با بعد زياد انتقال داد و در آن فضا حاصلضرب داخلي را انجام داد و ثابت کرد که اگر يک کرنل متقارن، شرايطMercer را داشته باشد، اعمال اين هسته در فضاي ورودي با بعد کم ميتواند به حاصلضرب داخلي در يک فضاي هيلبرت با بعد زياد تلقي شود و محاسبات را به شدت کاهش دهد.
در واقع تعميم اين مساله به حالت غيرخطي به طور مفهومي ساده است.اين کار با نگاشت متغير ورودي X به يک فضاي ويژگي با ابعاد بزرگ تر و در نتيجه با استفاده از يک طبقه بندي کننده خطي در آن فضا صورت ميگيرد.(شکل2-14)
براي حل اين مشكل ميتوان ابتدا داده ها را از فضاي اوليهRn با استفاده از يک تبديل غيرخطي به فضايRm، با ابعاد بيشتر منتقل كرد كه در فضاي جديد كلاسها تداخل كمتري با يكديگر داشته باشند.سپس در فضاي جديد با استفاده از معادلات قبلي و با جايگزيني xi با و در نظر گرفتن مقداري خطا مرز تصميم گيري بهينه محاسبه ميشود.با توجه به اين امر در اين حالت يافتن مرز تصميم گيري بهينه به حل مساله بهينه سازي زير تبديل ميشود:

در اين مساله بهينه سازي C يک عدد ثابت است.اگر ، مساله بهينه سازي به سمت يافتن يک مرز بهينه براي کلاس هايي با تداخل بسيار زياد پيش ميرود.از طرفي اگر مساله بهينه سازي به سمت يافتن يک مرز بهينه جداکننده دو کلاس که تداخل بسيار کمي دارند پيش خواهد رفت.در رابطه بالا معمولا به جاي استفاده از ، از يک تابع هسته که به صورت زير تعريف ميشود استفاده ميگردد:

پس از تعيين يک مناسب، در معادله بالا ، تابع قرار داده شده و مساله بهينه سازي حل ميشود. در واقع يک تابع در فضاي اوليه است که برابر با ضرب داخلي دو بردار در فضاي ويژگي است.براي معادل بودن با ضرب داخلي دو بردار در فضاي ويژگي، بايد يک تابع معين متقارن مثبت بوده و در شرط Mercer صدق کند.برخي از مهم ترين توابع کرنل در ادامه بيان ميشود]11[.
شرط mercer :
يک نگاشت و همچنين تابع کرنلوجود دارد اگر و تنها اگر g(X) اي وجود داشته باشد که محدود باشد و

امتياز استفاده از کرنل در اين است که لازم نيست که صريحاً از فضاي ويژگي ها با بعد بالا سروکار داشته باشيم.اين تکنيک را لم کرنل ميناميم.

دسته بندی : No category

دیدگاهتان را بنویسید