بایگانی‌های ماشين بردار پشتيبان خطي

تاريخچه

الگوريتم SVM اوليه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شد و در سال ۱۹۹۵ توسطVapnik و Corinna Cortes براي حالت غيرخطي تعميم داده شد.

ماشين بردار پشتيباني (Support vector machines) يکي از روش‌هاي يادگيري بانظارت(Supervised learning) است که از آن براي طبقه‌بندي و رگرسيون استفاده مي‌کنند.

اين روش از جمله روش‌هاي نسبتاً جديدي است که در سال‌هاي اخير کارايي خوبي نسبت به روش‌هاي قديمي‌تر براي طبقه‌بندي از جمله شبکه‌هاي عصبي پرسپترون نشان داده است. مبناي کاري دسته‌بنديکنندة SVM دسته‌بندي خطي داده‌ها است و در تقسيم خطي داده‌ها سعي مي‌کنيم خطي را انتخاب کنيم که حاشيه اطمينان بيشتري داشته باشد. حل معادلة پيدا کردن خط بهينه براي داده‌ها به وسيله روش‌هايQP (Quadratic Programming) که روش‌هاي شناخته شده‌اي در حل مسائل محدوديت‌دار هستند صورت مي‌گيرد.

SVM از يک تکنيک که kernel trick ناميده مي شود، براي تبديل داده هاي شما استفاده مي کند و سپس بر اساس اين تبديل، مرز بهينه بين خروجي هاي ممکن را پيدا مي کند. به عبارت ساده تبديلات بسيار پيچيده را انجام مي دهد، سپس مشخص مي کند چگونه داده هايتان را بر اساس برچسب ها يا خروجي هايي که تعريف کرده ايد، جدا کنيد.

يکي از روش هايي که در حال حاضر به صورت گسترده براي مسئله دسته بندي (Classification) مورد استفاده قرار مي گيرد، روش ماشين بردار پشتيبان (SVM) است. شايد به گونه اي بتوان محبوبيت کنوني روش ماشين بردار پشتيبان را با محبوبيت شبکه هاي عصبي در دهه گذشته مقايسه کرد. علت اين قضيه نيز قابليت استفاده اين روش در حل مسائل گوناگون مي باشد، در حاليکه روش هايي مانند درخت تصميم گيري را نمي توان به راحتي در مسائل مختلف به کار برد.

کاربردهاي SVM

الگوريتم SVM، جز الگوريتم هاي تشخيص الگو دسته بندي مي شود. از الگوريتم SVM، در هر جايي که نياز به تشخيص الگو يا دسته بندي اشيا در کلاس هاي خاص باشد مي توان استفاده کرد. در ادامه به کاربرد هاي اين الگوريتم به صورت موردي اشاره مي شود:

سيستم آناليز ريسک، کنترل هواپيما بدون خلبان، رديابي انحراف هواپيما، شبيه سازي مسير، سيستم راهنمايي اتوماتيک اتومبيل، سيستمهاي بازرسي کيفيت، آناليز کيفيت جوشکاري، پيش بيني کيفيت، آناليز کيفيت کامپيوتر، آناليز عملياتهاي آسياب، آناليز طراحي محصول شيميايي، آناليز نگهداري ماشين، پيشنهاد پروژه، مديريت و برنامه ريزي، کنترل سيستم فرايند شيميايي و ديناميکي، طراحي اعضاي مصنوعي، بهينه سازي زمان پيوند اعضا، کاهش هزينه بيمارستان، بهبود کيفيت بيمارستان، آزمايش اتاق اورژانس، اکتشاف روغن و گاز، کنترل مسير در دستگاههاي خودکار، ربات، جراثقال، سيستمهاي بصري، تشخيص صدا، اختصار سخن، کلاسه بندي صوتي، آناليز بازار، سيستمهاي مشاوره اي محاسبه هزينه موجودي، اختصار اطلاعات و تصاوير، خدمات اطلاعاتي اتوماتيک، مترجم لحظه اي زبان، سيستمهاي پردازش وجه مشتري، سيستمهاي تشخيص ترمز کاميون، زمانبندي وسيله نقليه، سيستمهاي مسيريابي، کلاسه بندي نمودارهاي مشتري/بازار، تشخيص دارو، بازبيني امضا، تخمين ريسک وام، شناسايي طيفي، ارزيابي سرمايه، کلاسه بندي انواع سلولها، ميکروبها و نمونه ها، پيش بيني فروشهاي آينده، پيش بيني نيازهاي محصول، پيش بيني وضعيت بازار، پيش بيني شاخصهاي اقتصادي، پيش بيني ملزومات انرژي، پيش بيني واکنشهاي دارويي، پيش بيني بازتاب محصولات شيميايي، پيش بيني هوا، پيش بيني محصول، پيش بيني ريسک محيطي، پيش بيني جداول داوري، مدل کردن کنترل فرآيند، آناليز فعاليت گارانتي، بازرسي اسناد، تشخيص هدف، تشخيص چهره، انواع جديد سنسورها، دستگاه کاشف زير دريايي بوسيله امواج صوتي، رادار، پردازش سيگنالهاي تصويري شامل مقايسه اطلاعات، پيگيري هدف، هدايت جنگ افزارها، تعيين قيمت وضعيت فعلي، جلوگيري از پارازيت، شناسايي تصوير /سيگنال، چيدمان يک مدار کامل، بينايي ماشين، مدل کردن غير خطي، ترکيب صدا، کنترل فرآيند ساخت، آناليز مالي، پيش بيني فرآيندهاي توليد، ارزيابي بکارگيري يک سياست، بهينه سازي محصول، تشخيص ماشين و فرآيند، مدل کردن کنترل سيستمها، مدل کردن ساختارهاي شيميايي، مدل کردن سيستمهاي ديناميکي، مدل کردن سيگنال تراکم، مدل کردن قالبسازي پلاستيکي، مديريت قراردادهاي سهام، مديريت وجوه بيمه، ديريت سهام، تصويب چک بانکي، اکتشاف تقلب در کارت اعتباري، ثبت نسيه، بازبيني امضا از چکها، پيش بيني ارزش نسيه، مديريت ريسک رهن، تشخيص حروف و اعدا، تشخيص بيماري و…..

ايده اصلي SVM

l با فرض اينکه دسته ها بصورت خطي جداپذير باشند، ابرصفحه هائي با حداکثر حاشيه(maximum margin) را بدست مي آورد که دسته ها را جدا کنند.

l در مسايلي که داده ها بصورت خطي جداپذير نباشند، داده ها به فضاي با ابعاد بيشتر نگاشت پيدا مي کنند تا بتوان آنها را در اين فضاي جديد بصورت خطي جدا نمود.

l در يک فرايند يادگيري که شامل دو کلاس ميباشد، هدف SVM پيدا کردن بهترين تابع براي طبقهبندي ميباشد به نحوي که بتوان اعضاي دو کلاس را در مجموعه دادهها از هم تشخيص داد. معيار بهترين طبقهبندي بهصورت هندسي مشخص ميشود، براي مجموعه دادههايي که بهصورت خطي قابل تجزيه هستند. بهطور حسي آن مرزي که بهصورت بخشي از فضا تعريف ميشود يا همان تفکيک بين دو کلاس بوسيله hyperplane تعريف ميشود. همين تعريف هندسي به ما اجازه ميدهد تا کشف کنيم که چگونه مرزها را بيشينه کنيم ولو اينکه تعداد بيشماري hyperplane داشته باشيم و فقط تعداد کمي، شايستگي راه حل براي SVM دارند.

مسئله جداسازي خطي: Linear Discrimination

اگر دو دسته وجود داشته باشند که بصورت خطي از هم جداپذير باشند، بهترين جدا کننده اين دو دسته چيست؟

الگوريتم هاي مختلفي از جمله پرسپترون ميتوانند اين جداسازي را انجام دهند.

آيا همه اين الگوريتمها بخوبي از عهده اين کار بر مي آيند؟

آشنايي با مفاهيم ابتدايي

خط يا ابر صفحه جدا کننده:

هدف: پيدا کردن بهترين خط ( ابر صفحه) که دو دسته را از هم جدا کند. در حالت دو بعدي معادله اين خط بصورت زير است:

در حالت n بعدي خواهيم داشت:

حداکثر حاشيه (maximum margin)

بر طبق قضيه اي در تئوري يادگيري اگر مثالهاي آموزشي بدرستي دسته بندي شده باشند، از بين جداسازهاي خطي، آن جداسازي که حاشيه داده هاي آموزشي را حداکثر مي کند، خطاي تعميم را حداقل خواهد کرد.

چرا حداکثر حاشيه؟

¢ به نظر مي رسد که مطمئن ترين راه باشد.

¢ تئوري هائي برمبناي VC dimension وجود دارد که مفيد بودن آنرا اثبات مي کند.

¢ بطور تجربي اين روش خيلي خوب جواب داده است.

¢ دليل اينکه SVM روي بزرگترين مرز براي hyperplane پافشاري ميکند اينست که قضيه قابليت عموميت بخشيدن به الگوريتم را بهتر تامين ميکند. اين نه تنها به کارايي طبقهبندي و دقت آن روي دادههاي آزمايشي کمک ميکند، فضا را نيز براي طبقهبندي بهتر دادههاي آتي مهيا ميکند.

بردار پشتيبان

نزديکترين داده هاي آموزشي به ابر صفحه هاي جدا کننده بردار پشتيبان ناميده مي شوند.

ماشين بردار پشتيبان خطي

ماشين بردار پشتيبان يک روش يادگيري نسبتا جديد است که اغلب براي کلاسبندي باينري مورد استفاده واقع مي شود. فرض کنيد L مشاهده داريم که هر مشاهده مشتمل بر زوج هاي است که در آن . بردار ورودي و يک مقدار دو وضعيتي (1- يا 1+) است. ايده ي ماشين بردار پشتيبان مي کوشد، ابرصفحاتي در فضا رسم کند که عمل تمايز نمونه هاي کلاس هاي مختلف داده ها را بطور بهينه انجام دهد. مي توان يک ابرصفحه را از طريق رابطه زير نشان داد:

براي يک بردار خطي b با وزن w ، حاشيه جداسازي عبارتست از فاصله ي بين ابرصفحه تعريف شده توسط رابطه ي فوق و نزديکترين ويژگي به آن. هدف ماشين بردار پشتيبان يافتن ابرصفحه اي ست که بيشترين حاشيه ي جداسازي را داشته باشد. مهمترين وظيفه SVM ، يافتن پارامترهاي w0 و b0 بر اساس بردارهاي آموزشي داده شده، براي اين ابرصفحه بهينه است. براي يک بردار ويژگي X، فاصله تا ابرصفحه بهينه به صورت زير است:

از رابطه بالا نتيجه مي شود که ماکزيموم کردن حاشيه جداسازي بين الگوها و ابرصفحه، معادلست با مينيموم کردن فرم اقليدسي بردار وزن w. بنابراين مساله بهينه سازي مقيد را مي توان به صورت زير تعريف کرد:

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

لاگرانژين L بايد نسبت به متغيرهاي اوليه bو w مينيموم و نسبت به متغيرهاي دوگان ماکزيموم شود. با مساوي صفر قراردادن مشتق L نسبت به b،w:

به معادلات زير خواهيم رسيد:

مجموعه جواب، بسطي از نمونه هاي آموزشي است که مقدار متناظر با آن ها، يک مقدار غير صفر است. اين نمونه هاي آموزشي خاص به بردارهاي پشتيبان مشهورند. بردارهاي پشتيبان روي مرز حاشيه قرار دارند. مابقي نمونه هاي آموزشي در اين قسمت نقشي ندارند.

تمايز نمونه هاي دو کلاس با ابرصفحه ي بهينه

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

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

ماشين بردار پشتيبان براي بردارهاي ورودي جدايي ناپذير:

اغلب در عمل، يافتن يک ابرصفحه متمايز کننده به راحتي امکان پذير نيست. زيرا مثلا يک نويز قوي مي تواند باعث ايجاد رويهم افتادگي کلاس ها شود. در اين حالت از متغير هايي به نام متغيرهاي کمبود(Slack Variables) استفاده مي کنيم. به گونه اي که شرايط زير برقرار باشند:

حال يک تعميم خوب براي ابرصفحه ي متمايز کننده، با کنترل ظرفيت کلاسبند (از طريق ) و همچنين تعداد خطاهاي مرحله آموزش بدست مي آيد. مساله بهينه سازي به صورت زير تعريف خواهد شد:

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

ماشين بردار پشتيبان غيرخطي:

ابرصفحه جداکننده بهينه اولين بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که يک دسته کننده خطي بود. در سال ۱۹۹۲ ،Bernhard Boser ، Isabelle GuyonوVapnik راهي را براي ايجاد دسته بند غيرخطي، با استفاده قرار دادن هسته براي پيدا کردن ابرصفحه با بيشتر حاشيه، پيشنهاد دادند. الگوريتم نتيجه شده ظاهرا مشابه است، به جز آنکه تمام ضرب هاي نقطه اي با يک تابع هسته غيرخطي جايگزين شده اند. اين اجازه مي دهد، الگوريتم، براي ابرصفحه با بيشترين حاشيه در يک فضاي ويژگيِ تغييرشکل داده، مناسب باشد. ممکن است، تغييرشکل غيرخطي باشد و فضاي تغيير يافته، داراي ابعاد بالاتري باشد. به هر حال دسته کننده، يک ابرصفحه در فضاي ويژگي با ابعاد بالا است، که ممکن است در فضاي ورودي نيز غيرخطي باشد.

در حالت غيرخطي، مي توان با اعمال پيش پردازش داده ها، مساله را به فضايي برد که در آن جا با يک ابرصفحه ساده قابل حل باشد. براي اين منظور يک نگاشت تعريف مي کنيم که بردار ورودي d بعدي x را به بردار d’ بعدي z تبديل مي کند.

بايد به گونه اي انتخاب شود که بردارهاي فضاي ويژگي جديد جدايي پذير باشند. در حالت کلي مي توان گفت که اگر بردارهاي ورودي را به فضايي ببرد که تعداد ابعاد آن به اندازه کافي بزرگ باشد (