بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تحليل ماشين بردار پشتيبان و توابع کرنل در مسائل دسته بندي
چکيده
در مسائل دسته بندي استفاده از بردارهاي پشتيبان خطي (SVM) ، رويکردي است که مورد توجه بسياري قـرار گرفتـه اسـت . بـا انتخاب مرز تصميم گيري(Decision Bondry) مناسب ، باعث مي شود شرايط نويزي را بخوبي تحمل کند و پاسخ دهي خوبي داشته باشد. اين نحوه انتخاب مرز بر اساس نقاطي به نام بردارهاي پشتيبان انجام مي شود. اگر داده ها بطور خطي جـدا شـوند ، ابرصـفحه جداکننده اي مي تواند پيدا شود که داده ها را از هم جدا نمايد. صفحه اي که بيشترين (Margin)حاشيه با داده هـا داشـته باشـد، بهترين انتخاب است . در واقع SVM دسته بندي کننده اي است که بهترين (hyperplane) ابرصفحه را پيدا مي کند. اگـر داده هـا بطور خطي جداپذير نباشند ، کرنل ”trick“ مورد استفاده قرار مي گيرد.
کلمات کليدي
ماشين بردار پشتيبان ، دسته بندي کننده ، توابع کرنل .
١- مقدمه
در سال ١٩٦٠ Vapnik و Colleagues موسس SVM به وسيله تعريف بهينه سازي ابر صفحه به طور بهينه داده را جدا مي کند و بر پايه تئوري يادگيري آماري (statistical learning theory) بنا گرديده است و دسته بندي کننده اي است که جزو شاخه روش هاي کرنل (Kernel Methods) در يادگيري ماشين محسوب مي شود. شهرت SVM بخاطر موفقيت آن در تشخيص حروف دست نويس است که با شبکه هاي عصبي بدقت تنظيم شده است . هدف اين دسته الگوريتم ها تشخيص و متمايز کردن الگوهاي پيچيده در داده هاست .
SVM ها در رشد تعداد مسائل به کار مي روند که شامل شناسايي يا همان تعيين هويت ، شناسايي اشيا، دسته بندي کردن متون (يعني فيلترکردن spam ها )، شناسايي کاراکترهاي دست نوشته ، دسته بندي کردن عکس ها، شناسايي صدا و صورت افراد مي باشد. همچنين SVM ها در زمينه bioinformatic مسائل شناسايي را به عنوان الگو بکار مي برند. شناسايي همساني از راه دور پروتئين ها ، شناسايي عبارت ژن ميکرو آرايه ها، پيش بيني عکس العمل هاي پروتئين ها و شناختن peptide (مواد تشکيل دهنده پروتئين ) از داده هاي انبوه است [٤][٣][٢] .
فرض مي کنيم يکسري نمونه داريم که با d تعداد از ويژگي ها نسبت داده شده است . هر مثال ساده را بعنوان بردار d بعدي در يک فضاي d بعدي مورد بحث قرار مي دهيم . اگر دسته بندي هاي دودويي از مثال ها را بخواهيم بيان کنيم ، آنگاه هر برچسب نقطه داده d بعدي بعنوان مثبت يا منفي دارد. روش ساده و شهودي براساس ابر صفحه جداکننده طرح ريزي شده است که مثلا نقاط داده مثبت و منفي را جدا مي کند. درابتدا فرض مي کنيم داده به تعداد ديگر از فضاي H با استفاده از نگاشت (در ابعاد بالا) نگاشت شده است . سپس ابرصفحه جداکننده اي در ابرفضاي H معين مي کنيم . حل کردن معادلات براي بهينه سازي ابر صفحه جداکننده در ابر فضا را مشاهده مي کنيم که تمام فرمول ها از طريق حاصلضرب نقطه اي در H فقط به داده بستگي دارد يعني بر روي توابعي از و تابع کرنل k را به اين صورت معرفي مي کنيم :
بعنوان شباهت اندازه گيري براي xi و xj ، بعد H بطور صريح بدون شناختن آن را استفاده مي کند. داده ها بصورت خطي يا غير خطي مي باشند که در آن صورت اگر داده ها خطي باشند تفکيک داده ها توسط خط يا يک صفحه امکان پذير است . در مسايلي که داده ها بصورت خطي جداپذير نباشند داده ها به فضاي با ابعاد بيشتر نگاشت پيدا مي کنند تا بتوان آنها را در اين فضاي جديد بصورت خطي جدا نمود.
٢-ماشين هاي بردار خطي
نقاط داده در R2 به دو کلاس که با خط مستقيم تفکيک مي شود در R3 با صفحه تفکيک مي شود. در فضاي با ابعاد بالاتر درباره ابرصفحه ها صحبت مي کنيم . تفکيک ابرصفحه توسط بردار نرمال w و آفست b مشخص مي شود.(فاصله اي که صفحه جا به جا شده از منبع محور y نمودار است . )
با به عنوان حاصلضرب نرده اي يا همان اسکالر مشخص شده است . اگر ابرصفحه اي جداکننده طرح ريزي کنيم بنابراين نقاط w براي نقاط مثبت و تابع تصميم آن به صورت زير است :
١+ براي نقاط کاذب در سمت مثبت از ابرصفحه و ١- براي نقاط منفي در سمت منفي را برگشت خواهد داد.
روشهاي امکان پذير براي جايگزيني ابرصفحه اي که به دو کلاس تفکيک خواهد شد. از اين رو براي بهينه سازي ابرصفحه جداکننده OSH - Optimal Hyperplane Seperating فرض اصلي يادگيري از مثال هايي که نقاط داده جديد در ميان داده آموزشي (training data) جديد شناخته مي شود. بنابراين OSH بايداجازه دهد که انحراف کوچکي در داده و ميان ساختارهايي از ابرهاي داده مثبت يا منفي باشد.
شکل (١) ابرصفحه جداکننده بهينه اي را نشان مي دهد [٨]
ماشين بردار پشتيبان (SVM) تابعي است که به هر مقدار ورودي کلاس مثبت يا کلاس منفي نسبت داده مي شود و برچسب مثبت يا منفي نسبت داده مي شود.
مثال نوعي از دسته بندي کننده هاي متني يعني تصميم گيري اينکه آيا يک ايميل spam است يا نيست . در اينجا هر ايميلي که در يک (ابعاد بالاي دودويي) بردار رمزگذاري شده که هر وجود قطعه با ١+ يا نبودن وجود قطعه با ١- در ايميل نمايش داده مي شود. براي بدست آوردن SVM هاي خوب سازگار شده نقاط داده آموزش ديده شده متعلق به برچسبهايي که اصطلاحا training data شناخته مي شود.
ايميل هايي که توسط شخص مطلع ، spam و غير spam دسته بندي شده است همچنين کارشناس يا سر پرست در مفهوم يادگيري ماشين مي باشد. training data به عنوان مجموعه زير نمايش داده مي شود:
درجاييکه xi نقاط داده وبرچسب yi که هم ١- و هم ١+ مي باشد.
تابع تصميم
بردارهاي ورودي xi به کلاس مثبت يا منفي نگاشت شده است . [٨]
Kernel Trick-3
تابع نگاشت و فضاي ويژگي را به ترتيب و H در نظر مي گيريم .
در دسته بندي کننده هاي خطي، حاصلضرب نقاط بين بردارها است .
اگر هر نقطه داده با فضايي به ابعاد بالا نگاشت شود، از طريق نگاشت حاصل ضرب داخلي به تبديل مي شود.
SVM ها نسبت به شبکه هاي عصبي مصنوعي بديهي تر هستند و در نتيجه به راه حلي که چگونگي محاسبه معادلات بهترين جداکننده ابر صفحه OSH - Optimal Seperating Hyperplane نياز داريم .
مفاهيم تئوري بهينه سازي براي پيدا کردن OSH مورد نياز است .
دو نقطه و نگاشت را بر روي p و q بکار مي بريم .
فرضيه حاصلضرب نقطه اي بصورت زير محاسبه مي شود:
درنهايت بجاي محاسبه همين نگاشت خاص ، بوسيله حاصلضرب نقطه اي معادل حاصلضرب نقطه اي نقاط اصلي و مربع آن را مي توانيم محاسبه کنيم . بنابراين حاصلضرب نقطه اي بدون بکاربردن تابع محاسبه مي کنيم . توابعي که براي اين نگاشت توسط حاصلضرب نقطه اي در H مناسب هستند، توابع کرنل ناميده مي شوند و توسط k علامت گذاري مي شوند. سوالي که در اينجا پيش مي آيد اين است که چرا تابع کرنل trick را مورد استفاده قرار مي دهيم ؟ هر الگوريتمي براي داده برداري فقط در واژه حاصلضرب نقطه اي بين بردارها بيان مي شود. اين بدان معني است که به شناسايي فضاي ويژگي H و به تابع کرنلي احتياج داريم که شباهت يکساني را بر مي گرداند و تمام محاسبات را بطور مستقيم در H انجام نمي دهيم . [٨]
٤-ماشين هاي بردار غير خطي
بسياري از داده هاي جهان واقعي به صورت خطي جدا نمي شوند. در بيشتر نمونه ها پردازش با استفاده از داده هايي که به سادگي توليد مي شوند و توسط توابع خطي نميتوانند تقريب زده شوند. مشخصه نگاشتي که نقاط داده آن Xi و فضاي داده به فضاي ويژگي H در جاييکه جداپذير خطي امکان پذير است . فضاي ويژگي H بايد فضاي هيلبرت باشد. به ويژه هر فضاي خطي با حاصلضرب داخلي تعريف شده است . در سال ١٩٧٠ تعدادي از نويسندگان از جمله کالماگراف و فامين به فضاهاي هيلبرت که ابعاد نامحدودي دارد، نياز دارند و رياضيدانان فضاي اقليدسي با ابعاد نامحدود، تعريف مي کنند.
بعنوان مثال مجموعه آموزشي X در نظر مي گيريم :
نقاطي در R2 با برچسب هاي ١+ و ١- مي باشد.
در شکل (٢) نشان داده شده است .
توسط يک صفحه ٣ نقطه نمي توانند جدا شوند. (يعني يک خط مستقيم در R2) نگاشت زير را بکار مي بريم :
بر روي مربع نگاشت کاملي از داده در تعريف شده است . نگاشت ٣ نقطه و که با نقاط قرمز رنگ براي نقاط مثبت و مربعات آبي براي نقاط منفي مشخص شده است .
ضريب تکاثر لاگرانژ بعنوان است . چيزي که استنتاج مي شود:
و بردار واحد مي باشد.
بزرگترين حاشيه ابر صفحه در فضاي ويژگي بنابراين يک صفحه موازي x3×x2 در فاصله ٠.٥ در جهت مثبت x1 صفحه در شکل (٢) نشان داده نشده اما محل آن خط تيره اشتراکي اشاره مي کند.
شکل (٢)
گرافيکي از نقاط در مربع حاشيه دار سبز [١,١-]× [١,١-] در R2 نشان داده شده است .
نگاشت بعنوان سطح رنگ شده در R3 مي باشد.
٣ نقطه نشان داده شده دو نقطه قرمز (١,١) و (١,١-) و يک مربع آبي (٠,١) در فضايR2 غير قابل تفکيک مي باشد. وقتي فضاي ويژگي H درR3 نگاشت شده است ، ٣ نقطه توسط يک صفحه جداپذير مي شود که محل آن توسط خطوط تيره اشتراکي نشان داده شده است . در R2 کران تصميم گيري خطوط نقطه گذاري شده که از صفحه جداکننده بهينه اي در R3 گرفته شده است .
