پایان نامه با کلید واژگان تابع کرنل، مقدار خطا

دارا بودن يک شالوده رياضي منسجم در تئوري يادگيري آماري، عملکرد بسيار خوب و موفقيت آميزي را در کاربردهاي عملي و واقعي از خود به نمايش گذاشته اند. تعدادي از اين کاربردها عبارتند از: تشخيص هاي پزشکي، بيوانفورماتيک، پردازش تصوير و متن کاوي34. ماشين هاي بردار پشتيباني، مشابه با شبکه هاي عصبي قادر هستند تا براي هر تابع چند متغيره، تقريب هايي را با درجه دلخواه به دست دهند. بنابراين و به منظور مدل کردن سيستم ها و فرآيندهاي غيرخطي و بسيار پيچيده مي توان از SVM ها استفاده کرد. اين الگوريتم در حال حاظر در بسياري از زمينه هاي مختلف علمي (برق، پردازش تصوير، پزشکي و …) مورد استفاده پژوهشگران قرار گرفته است[9],[34],[24],[20],[18].
1-5-2) دسته بندي کننده بردار پشتيباني:
در رابطه با دسته بندي دودويي که در آن، صرفا با دو کلاس ممکن مواجه هستيم و همچنين مي توان کلاس ها را بطور خطي از يکديگر جداساخت، هدف SVC عبارت است از يافتن ابر صفحه35 جداکننده نقاط داده اي متعلق به دو کلاس، با حاشيه36 ماکسيمال و بهترين توانايي تعميم. حاشيه از ديدگاه هندسي عبارت است از فاصله موجود بين ابرصفحه و نزديک ترين نمونه آموزشي. از يک زاويه ديگر حاشيه اين گونه تعريف مي شود: مقدار فضا يا جدايي موجود ميان دو کلاس که توسط ابرصفحه تعريف مي شود. منظور از توانايي تعميم آن است که دسته بندي کننده علاوه بر داشتن عملکرد خوب در دسته بندي داده هاي آموزشي (دقت)، داراي يک دقت پيش بيني بالا در قبال داده هاي مشاهده نشده (که توزيع آن ها با توزيع داده هاي آموزشي يکسان است) نيز باشد.
شکل2-2: صفحه تفکيک کننده داده ها در SVC براي فضاي سه بعدي[33]
همانطور که در شکل زير ديده مي شود براي جداکردن اين دو کلاس ابرصفحه هاي بيشماري وجود دارد (چون در اين مثال فضا دو بعدي است با خط نمايش داديم)که بعضي از آنها به کلاس ها نزديکترند. SVM تلاش مي کند تا ابرصفحه اي را بيابد که بيشترين فاصله را از دو کلاس داشته باشد(يعني همان H2). همانطور که گفته شد انتخاب اين ابرصفحه باعث مي شود که طبقه بندي قابليت تعميم بيشتري داشته باشد.
شکل 2-3 : همانطور که از شکل پيداست H3 دو کلاس را بخوبي تفکيک نکرده است. H1 تفکيک را بدرستي انجام داده ولي با کمترين حاشيه اما H2 با بيشترين حاشيه توانسته عمل تفکيک را بدرستي انجام دهد[16].
براي اين منظور دو ابرصفحه موازي که نقاط سرحدي را در دو کلاس تعيين مي کنند در نظر گرفته مي شوند و سپس ابرصفحه اي که در فاصله مساوي از اين دو ابرصفحه قرار مي گيرد به عنوان ابرصفحه طبقه بندي کننده تعيين مي شود. مطابق شکل بعد:
شکل 2-4 : دو کلاس خطي جدايي پذير و طبقه بندي کننده SVM [3]
ابرصفحه طبقه بندي کننده را بصورت زير در نظر مي گيريم
(معادله 2-1)[3]
در ابرصفحه بهينه فوق، w و b به ترتيب عبارتند از بردار وزن و يک اسکالر.
فاصله هندسي مطلوب ميان نمونه x و ابرصفحه بهينه عبارت است از :
(معادله 2-2) [3]
در(2)، عبارت است از تابع تشخيص37 که توسط ابر صفحه مورد نظر تعريف مي شود.
بنابراين و در ارتباط با ابرصفحه بهينه، پارامترهاي w و b را مي بايست به نحوي تعيين کرد که حاشيه جداسازي (P) بيشينه گردد. اين حاشيه، با توجه به کوتاهترين فواصل هندسي r* از دو کلاس تعيين مي شود. با توجه به مطالب بيان شده، SVC را دسته بندي کننده با حاشيه ماکسيمال38 مي نامند. بدون از دست دادن کليت، حاشيه تابعي را با 1 در نظر مي گيريم. با توجه به مجموعه آموزشي { , } که i ها از 1 تا n ودر فضاي m بعدي مي باشند(توجه شود که y ها فقط دو مقدار 1 و 1- دارند) خواهيم داشت :
(معادله 2-3) [3]
نقاط ويژه اي که نامساوي هاي موجود در (3) را به تساوي تبديل مي کنند، بردارهاي پشتيباني ناميده مي شوند. اين نقاط (, ، نزديک ترين نقاط داده اي به ابرصفحه بهينه مي باشند. فاصله هندسي متناظر ميان بردارهاي پشتيباني x* و ابرصفحه بهينه عبارت است از :
(معادله 2-4) [3]
با توجه به شکل قبل خواهيم داشت:
(معادله 2-5) [3]
SVC به منظور يافتن يک ابرصفحه با حاشيه بيشينه، p را با توجه به w و b بيشينه مي سازد:
(معادله 2-6) [3]
Subject to :
بيشينه سازي (6) معادل است با :
(معادله 2-7) [3]
Subject to:
در اين جا و بمنظور ساده سازي مراحل بهينه سازي، از بجاي ||w|| استفاده مي کنيم. معمولا و به منظور حل مساله اي که در (7) مطرح شده است، مساله اوليه39 از روش ضريب لاگرانژ استفاده مي کنيم. تابع لاگرانژ زير را تشکيل مي دهيم:
(معادله 2-8) [3]
در (8) عبارت است از ضريب لاگرانژ با توجه به i امين نامساوي.
از نسبت به w و b مشتق گرفته و نتايج حاصل را برابر با صفر قرار مي دهيم. در نهايت، دو شرط زير را براي بهينگي به دست مي آوريم:
(معادله 2-9) [3]
در ادامه خواهيم داشت
(معادله 2-10) [3]
با توجه به (8) و (10)، مساله دوگان40 متناظر را به دست مي آوريم:
(معادله 2-11) [3]
Subject to :
همزمان شرط مکمل کروش _ کان _ تاکر41 برابر است با :
(معادله 2-12) [3]
بنابراين، تنها آن بردارهاي پشتيباني ( , ) که کم ترين فاصله را از ابرصفحه بهينه داشته و حاشيه ماکسيمال را تعيين مي کنند، متناظر با هاي غيرصفر مي باشند. بقيه ها برابر با صفر هستند.
مساله دوگاني که در (11) آمده است، بهينه سازي يک مساله برنامه ريزي درجه محدب مي باشد. در بسياري از موارد و با بکارگيري يک تکنيک بهينه سازي مناسب، مي توان جواب بهينه سراسري را بطور کارا بدست آورد.
پس از تعيين ضرايب لاگرانژ بهينه ، مي توانيم بردار وزن بهينه، ، را به کمک (10) محاسبه نماييم:
(معادله 2-13) [3]
سپس به کمک بردار پشتيباني مثبت ، مقدار بهينه اسکالر b را به صورت زير تعيين مي کنيم:
(معادله 2-14) [3]
for
2-5-2) SVC با حاشيه انعطاف پذير42 و بهينه سازي :
SVC با حاشيه ماکسيمال، نقطه آغازين الگوريتم هاي SVM قلمداد مي شود. با اين وجود و در بيشتر مسايل واقعي، منطقي نيست که فرض کنيم تمامي نقاط به صورت خطي تفکيک پذيرند. دسته بندي غيرخطي پيچيده يکي از اين مسائل واقعي مي باشد. زماني که تفکيک خطي نمونه ها بطور کامل شدني نيست، اين امکان وجود دارد که حاشيه ها منفي باشند.
معمولا براي حل اين مسائل تفکيک ناپذير دو رويکرد را مد نظر قرار مي دهيم. اولين رويکرد آن است که از شدت و دقت نامساوي هاي موجود در (7) بکاهيم. اين رويکرد ما را به سمت بهينه سازي با حاشيه هاي انعطاف پذير (نرم) رهنمون مي سازد. براي درک بهتر مفهوم نرم بايد گفت قدر مطلق را در فيزيک و رياضي بيش از همه مي‌توان به مفهوم بزرگي، فاصله و نُرم نزديک دانست.
روش ديگر بکارگيري Kernel Trick به منظور خطي سازي مسايل غير خطي مورد نظر مي باشد.(شکل(2-5))
شکل 2-5 : نمايش تاثير تابع کرنل براي نگاشت داده ها به فضاي خطي[17]
در اين قسمت بهينه ساز با حاشيه انعطاف پذير را شرح خواهيم داد. مواردي را در نظر بگيريد که در آن ها تعدادي از نقاط متعلق به کلاس هاي مختلف با يکديگر مخلوط شده اند. اين نقاط، بيانگر خطاي آموزش مي باشند. اين خطا، حتي براي ابرصفحه با حاشيه بيشينه نيز وجود دارد. هدف از بکارگيري “حاشيه انعطاف پذير” ، توسعه دادن الگوريتم SVC است به نحوي که در تعيين ابرصفحه، امکان وجود داده هاي حاوي اختلال نيز فراهم شود. به منظور دستيابي به اين هدف، يک متغير کمکي43 معرفي مي شود تا از اين طريق بتوان مقدار خطاي دسته بندي را در نظر گرفت:
(معادله 2-15) [3]
Subject to:
نقش C در رابطه فوق، ايجاد تعادل ميان پيچيدگي ماشين و تعداد نقاط تفکيک ناپذير. در حالت معمول اين پارامتر توسط کاربر و بر اساس تجربه يا تحليل تعيين مي شود.
متغيير کمکي ، بيانگر فاصله موجود ميان ابرصفحه و داده اي است که دسته بندي آن نادرست مي باشد. در واقع، اين فاصله ميزان انحراف يک نمونه را از وضعيت ايده آل تفکيک پذيري مي سنجد. با استفاده از روش ضريب لاگرانژ، مي توان مساله دوگان متناظر با حاشيه انعطاف پذير را به صورت زير فرموله کرد:
(معادله 2-16) [3]
Subject to:
به اين نکته توجه داشته باشيد که متغيير کمکي در مساله دوگان ظاهر نمي شود ((11)و(16) را با يکديگر مقايسه کنيد). مهم ترين تفاوت موجود ميان حالت تفکيک پذيري خطي و حالتي که تفکيک پذيري خطي امکان پذير نمي باشد آن است که بجاي محدوديت از محدوديت دقيق تر استفاده مي شود. دو حالت مذکور، در بقيه موارد (محاسبه مقادير بهينه بردار وزن w و اسکالر b، و تعريف بردارهاي پشتيباني) يکسان هستند. در حالت تفکيک ناپذير، شرط مکمل کروش-کان-تاکر به صورت زير است:
(معادله 2-17) [3]
و
(معادله 2-18) [3]
در (18)، ضريب لاگرانژ متناظر با مي باشد. در نقطه زيني که مشتق تابع لاگرانژ براي مساله اوليه صفر مي شود (نسبت به )، خواهيم داشت:
(معادله 2-19) [3]
با توجه به روابط (18) و (19) خواهيم داشت:
(معادله 2-20) [3]
در نتيجه، وزن بهينه برابر خواهد بود با:
(معادله 2-21) [3]
مقدار بهينه براي اسکالر b، با توجه (17) و هر نقطه داده اي دلخواه () در مجموعه آموزشي که براي آن داشته باشيم ، به دست مي آيد.
3-5-2) کرنل:
Kernel Trick ، يکي ديگر از تکنيک هاي متداول براي حل مسائلي است که به صورت خطي تفکيک پذير نيستند. در اينجا و بر اساس ضرب داخلي داده هاي مفروض، يک تابع کرنل مناسب تعريف مي شود. در واقع با يک تبديل غيرخطي از فضاي ورودي به فضاي خصيصه با ابعاد بيش تر (حتي نا متناهي) مواجه هستيم تا از اين طريق بتوان مسائل را به صورت خطي تفکيک پذير ساخت. اين رويکرد را مي توان با توجه به قضيه پوشش44 در مورد تفکيک پذيري الگوها توجيه کرد: احتمال آنکه يک مساله پيچيده دسته بندي الگو در فضايي با ابعاد بيش تر، به صورت خطي تفکيک پذير باشد بيش تر از احتمال تفکيک پذيري خطي اين مساله در فضايي با ابعاد کمتر است.
فرض کنيد که تبديلي غيرخطي از فضاي ورودي به فضاي خصيصه H باشد که در آن، مساله به صورت خطي تفکيک پذير است. مي توان ابرصفحه بهينه متناظر را به صورت زير تعريف کرد:
(معادله 2-22) [3]
بدون از دست دادن کليت، اسکالر b را برابر صفر در نظر گرفته و در نتيجه خواهيم داشت:
(معادله 2-23) [3]
مشابه با آنچه در ارتباط با تفکيک پذيري خطي شاهد بوديم، بردار وزن بهينه را در فضاي خصيصه و به کمک ضرايب لاگرانژ به دست مي آوريم:
(معادله 2-24) [3]
بنابراين، ابرصفحه بهينه اي که در فضاي خصيصه محاسبه مي شود به صورت زير خواهد بود:
(معادله 2-25) [3]
در (معادله 2-25)، بيانگر ضرب داخلي دو بردار و است.
نکته : تعريف کرنل ضرب داخلي : کرنل، براي تمامي که زير مجموعه مي باشند، يک تابع بوده و به صورت زير تعريف مي شود:
(معادله 2-26) [3]
در (معادله 2-26)، تبديلي است از فضاي ورودي X به فضاي خصيصه H .
اهميت کرنل از آنجا ناشي مي شود که مي توانيم آن را به منظور ايجاد ابرصفحه بهينه در فضاي خصيصه مورد استفاده قرار دهيم، بدون آنکه مجبور باشيم تا فرم اصلي و مشخص تبديل را مد نظر قرار دهيم. معمولا، لازم نيست تا را در فضاي خصيصه اي با ابعاد بيش تر (حتي نامتناهي) بطور صريح فرموله کنيم. بنابراين، با استفاده از کرنل مي توان حساسيت الگوريتم را در قبال بعد از بين برد و همچنين يک دسته بندي کننده خطي را در فضايي با ابعاد بيش تر به نحوي طراحي کرد تا مسائلي که به صورت خطي تفکيک پذير

Author: y7oozita

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *