الگوریتم یادگیری ماشین بردار پشتیبان

الگوریتم یادگیری ماشین بردار پشتیبان – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

یک الگوریتم جدید برای یادگیری افزایشی ماشین بردار پشتیبان (SVM)

چکیده

بر مبنای تحلیل ارتباط بین شرایط کروش ـ کان ـ تاکر (KKT) ماشین بردار پشتیبان و توزیع نمونه های آموزشی، تغییرات احتمالی مجموعه بردار پشتیبان، پس از اضافه سازی نمونه های جدید به مجموعه آموزشی، مورد تحلیل قرار گرفته و شرایط تعمیم یافته کروش ـ کان ـ تاکر تعریف گردید. بر مبنای رده بندی معادل بین مجموعه آموزشی قبلی و مجموعه آموزشی اضافه شده جدید، یک الگوریتم نوین برای فرآیند یادگیری افزایشی CVM پیشنهاد شده است. با  توجه به الگوریتم ارائه شده، نمونه غیرمفید به کنار گذاشته شده و اطلاعات مفید در نمونه های آموزشی انباشته می شوند. نتایج تجربی با توجه به مجموعه های اطلاعاتی استاندارد نشان دهنده کارایی الگوریتم پیشنهادی می باشند.

الگوریتم یادگیری ماشین بردار پشتیبان

۱- مقدمه

ماشین بردار پشتیبان (SVM) یک تکنیک دسته بندی جدید و نویددهنده به شمار می آید که به وسیله Vapnik و همکاران [۱] توسعه یافته است، و فراهم آورنده یک ابزار قدرتمند برای مدل های فراگیری می باشد که قابلیت تعمیم یافتگی مناسب حتی تحت شرایط مجموعه های پراکنده با ویژگی های ابعادی بالا را خواهد داشت. برای حاصل آوردن ویژگی های بهتر عملکرد با توجه به مؤلفه های کلی و ظرفیت بهتر فراگیری، توجه زیادی به SVM در ارتباط با شناسایی الگو و فراگیری ماشینی در خلال سالیان اخیر جلب شده است [۲].

البته هنوز شاهد وجود نقصهایی در خصوص SVM می باشیم، به طور مثال، این مورد از یادگیری افزایشی پشتیبانی نمی نماید، اما یادگیری افزایشی دسته ای در برنامه های کاربردی  گسترده  آنلاین،  و سناریوهای افزایشی و فعال  از جذابیت  زیادی  برخوردار  می باشد و بر این مبنا الگوریتم یادگیری افزایشی هم اکنون به عنوان یکی از تکنیک های کلیدی برای فراگیری تعداد زیادی از داده ها با ویژگی ابعادی بالا به شمار می آید. بنابراین، یافتن الگوریتم یادگیری افزایشی SVM محتمل و کارآمد مهم تلقی می گردد.

تکنیک های مختلف یادگیری افزایشی SVM [3، ۴، ۵، ۶] جهت تسهیل یادگیری افزایشی دسته ای SVM توسعه یافته اند. الگوریتم یادگیری افزایشی کارآمد در این مقاله مورد بررسی قرار می گیرد. یک الگوریتم جدید برای یادگیری افزایشی SVM بر مبنای رده بندی همتراز بین مجموعه فراگیری قبلی و مجموعه آموزشی اضافه شده جدید در طی فرآیند آموزشی پیشنهاد می شود.

این مقاله به شرح ذیل سازماندهی شده است. بخش ۲ فرآیند یادگیری افزایشی SVM را مورد تجزیه و تحلیل قرار می دهد. بخش ۳ الگوریتم جدیدی را برای یادگیری افزایشی SVM ارائه می دهد. بخش ۴ عرضه کننده آزمایشات شبیه سازی و نتایج آن می باشد. در نهایت بخش ۵ به نتیجه گیری این مقاله می پردازد.

الگوریتم یادگیری ماشین بردار پشتیبان

۲- تحلیل یادگیری افزایشی SVM

در یادگیری افزایشی، تعادل دسته بندی بین مجموعه SV و مجموعه فراگیری قبلی، با توجه به روی کارآمدن نمونه های آموزشی اضافه شده جدید دیگر وجود ندارد، و بنابراین لازم است تا قابلیت یافتن مجموعه SV جدید را داشته باشیم.

وظیفه اصلی یادگیری افزایشی یافتن  راهکارهایی  در این  زمینه  می باشد که  چگونه  می بایست اقدام به تعامل با نمونه های آموزشی جدیداً اضافه شده نموده و چگونه باید نتیجه فراگیری قبلی را به صورت کارآمد جهت حاصل آوردن نتیجه بهتر دسته بندی و اجتناب از فراگیری مجموعه نمونه آموزشی مشابه به صورت تکراری بکار گرفت.

به هنگام ملاحظه تأثیر نمونه های آموزشی جدید در ارتباط با مجموعه SV قبلی، لازم است تا موارد ذیل را در نظر داشته باشیم : ۱) کدام یک از نمونه های آموزشی جدید قابلیت تأثیرگذاری بر روی مجموعه SV قبلی را داشته و همچنین می توانند بر روی عملکرد کلی SVM قبلی مؤثر باشند؟ ۲) در خصوص تغییر مجموعه SV قبلی پس از یادگیری افزایشی چه فکر می کنید؟ ۳) کدام  نوع از نمونه آموزش را می توان به عنوان SV جدید در نظر گرفت و کدام نمونه آموزشی قابلیت تبدیل شدن به SV جدید را ندارد؟

جهت حاصل آوردن پاسخ های کارآمد در ارتباط با مسایل فوق، ما در ابتدا اقدام به تحلیل ارتباط بین شرایط KKT در زمینه SVM و توزیع نمونه های آموزشی نمودیم.

۲ـ۱٫ شرایط کروش ـ کان ـ تاکر

برای کلاسیفایر SVM، به حداکثررسانی حاشیه جداسازی، خود برابر با مسئله تحمیل برنامه کوآدراتیک قطعی نیمه مثبت ذیل می باشد :

۲ـ۲٫ تأثیر نمونه اضافه شده جدید به مجموعه SV

کدام نوع از نمونه های آموزشی اضافه شده جدید قابلیت تغییر مجموعه SV قبلی را خواهند داشت؟ در خصوص تغییر مجموعه SV و مجموعه غیر SV نمونه آموزشی قبلی پس از یادگیری افزایشی چه فکر می کنید؟

قضیه ۱ : برای ماتریس هشین Q برنامه کوآدراتیک محدود خطی، در صورتی که Q به صورت قطعی نیمه مثبت تلقی شود، بنابراین این مورد را می توان به عنوان یک برنامه کوآدراتیک مشخص شده فوق در نظر گرفت. برای یک راه حل در زمینه این برنامه کوآدراتیک a، در صورتی که صرفاً هر x قابلیت ارضای شرایط KKT را داشته باشند (مشخص شده به وسیله ضریب لاگرانژی a)، بنابراین a به عنوان راه حل بهینه برنامه کوآدراتیک فوق محسوب می شود [۲].

۲ـ۳٫ نمونه آموزشی جدید با قابلیت ارضای شرایط KKT و احتمال تبدیل به یک SV جدید

قضیه ۴ : در صورتی که یک نمونه آموزشی جدید قابلیت نقص شرایط KKT را داشته باشد، بنابراین نمونه آموزشی جدید با قابلیت ارضای شرایط KKT احتمالاً تبدیل به یک SV جدید خواهد شد.

قضیه ۳ و ۴ معرف آن می باشند که نمونه آموزشی جدید و نمونه آموزشی قبلی با قابلیت ارضای شرایط KKT  همچنین از قابلیت تبدیل به بردارهای پشتیبان جدید نیز برخوردار می باشند.

۲ـ۴٫ شرایط تعمیم یافته کروش ـ کان ـ تاکر

در صورتی که نمونه آموزشی جدید یکی از SV های قدیمی به شمار آید، این مورد قابلیت ارضای شرایط KKT را داشته و از هیچ تأثیری بر روی مجموعه SV قبلی نیز برخوردار نخواهد بود، اما در عین حال این مورد را می توان به عنوان یک SV جدید در نظر گرفت، بنابراین ما قابلیت تعمیم تعریف نقص شرایط KKT به صورت :y_ig(x_i) £۱  را خواهیم داشت، بر این مبنا ما این مورد را تحت عنوان نقص شرایط KKT تعمیم یافته می خوانیم.

مجموعه نمونه های آموزشی جدید با قابلیت نقص شرایط KKT تعمیم یافته به عنوان مجموعه ای یکنواخت از نمونه های آموزشی جدید تلقی می شوند که قابلیت نقص شرایط KKT و مجموعه SV قبلی را خواهند داشت.

الگوریتم یادگیری ماشین بردار پشتیبان

۳- یک الگوریتم جدید برای یادگیری افزایشی SVM

هدف یادگیری افزایشی حاصل آوردن راه حل بهینه برای مجموعه نمونه آموزشی قبلی و مجموعه نمونه آموزشی جدیداً اضافه شده می باشد.

با وجود آنکه مجموعه نمونه آموزشی قبلی غالباً بزرگتر از مجموعه نمونه آموزشی جدیداً اضافه شده می باشد، اما آنها از اهمیت یکسانی در خصوص نتیجه یادگیری افزایشی برخوردار می باشند و برای نتیجه چنین مؤلفه ای نیز از نوعی همسانی برخوردار هستند.

در نظر بگیرید که X₀ به عنوان مجموعه نمونه آموزشی قبلی، و X_I مجموعه نمونه های فراگیری جدیداً اضافه شده می باشند. با فراگیری آموزش X₀ در ابتدا، ما قابلیت حاصل آوردن SVM₀ را خواهیم داشت، پس از یادگیری افزایشی با X_I، می توان نتیجه یادگیری افزایشی SVM را نیز حاصل آورد. از طریق آموزش X_I در ابتدا، قابلیت حاصل آوردن SVM_I را داشته، آن هم پس از یادگیری افزایشی با X₀، که به عنوان مجموعه نمونه های آموزشی جدیداً اضافه شده در اینجا به شمار می آید، بنابراین ما می توانیم نتیجه یادگیری افزایشی SVM را نیز حاصل آوریم.

بر مبنای تحلیل فوق، و با استفاده از اصل منطقی حاصل آمده از قضیه های فوق، که قابلیت رد نمودن نمونه غیرمفید به صورت کارآمد و استفاده از نمونه های مفید به صورت مؤثر را دارند، یک الگوریتم جدید برای یادگیری افزایشی SVM در این مقاله پیشنهاد می شود.

الگوریتم یادگیری ماشین بردار پشتیبان

۴- آزمایشات و نتایج

به منظور مشخص سازی تأثیر الگوریتم یادگیری افزایشی SVM پیشنهادی، دو گروه داده ها از بانک اطلاعاتی UCI در این آزمایشات بکار گرفته شده و مقایسه بین الگوریتم متقابل [۶] و الگوریتم ارائه شده انجام شد.

اولین مجموعه اطلاعاتی در این آزمایشات به عنوان بالانس در نظر گرفته می شود. مجموعه داده های بالانس ۶۲۷ نمونه مربوط به ۳ کلاس (۴۹ مورد بالانس شده، ۲۹۰ مورد سمت چپ، و ۲۸۸ راست) هر کدام دارای ۴ ویژگی هستند. کلاس دوم مجموعه داده های بالانس به عنوان کلاس مثبت بکار گرفته شد، دو کلاس دیگر به عنوان کلاس منفی استفاده شدند. اولین ۳۰۰ نمونه در پروسه آموزشی شرکت داده شد، ۳۲۷ نمونه چپ نیز در فرآیند آزمایشی مورد استفاده قرار گرفتند.

مجموعه داده دوم که در این آزمایش بکار گرفته شد تحت عنوان شناسایی ـ حروف  تلقی می شود. مجموعه  داده های این مورد متشکل از  ۲۰  هزار نمونه مرتبط  با  ۲۶ کلاس می باشند که هر کدام دارای ۱۶ ویژگی هستند. اولین کلاس مجموعه مربوط به این داده ها به عنوان کلاس مثبت بکار گرفته شد، کلاس های دیگر به عنوان کلاس منفی مورد استفاده قرار گرفتند. ۶۰۰ نمونه به صورت تصادفی از مجموعه اطلاعاتی انتخاب شده و به عنوان نمونه های آموزشی بکار گرفته شدند، ۱۰۰۰ نمونه نیز به صورت تصادفی از مجموعه انتخابی برگزیده شده و به عنوان نمونه های آزمایشی قرار گرفتند.

الگوریتم یادگیری ماشین بردار پشتیبان

۵- نتیجه گیری

رویکرد کارآمد الگوریتم یادگیری افزایشی SVM در این مقاله مورد بررسی قرار گرفته است. بر مبنای تحلیل ارتباط بین شرایط KKT مرتبط با SVM و توزیع نمونه های آموزشی، تغییرات محتمل مجموعه SV پس از نمونه های جدید به مجموعه آموزشی اضافه شده و مورد تحلیل قرار گرفته و شرایط کروش ـ کان ـ تاکر تعمیم یافته مشخص شد. یک الگوریتم جدید برای یادگیری افزایشی SVM بر مبنای تعادل دسته بندی بین مجموعه فراگیری قبلی و مجموعه آموزشی اضافه شده جدید در طی فرآیند آموزشی پیشنهاد شد. با توجه به الگوریتم ارائه شده، نمونه بدون فایده طرد گردیده و اطلاعات مفید در نمونه های آموزشی انباشته شدند. نتایج تجربی با توجه به مجموعه داده های استاندارد معرف امکان پذیری و کارایی الگوریتم پیشنهادی می باشند.