ماشین های بردار پشتبان - مقاله تحقیقی

‫به نام خدا‬ ‫ماشین های بردار پشتبان‬ ‫جواد سلیمی سرتختی‬ ‫‪1‬‬  ‫مقدمه‪ -‬ماشین های بردار پشتیبان‬ ‫ماشین بردار پشتیبان یک دسته بند متعلق به روش های مبتنی بر کرنل می باشد‪.‬‬ ‫ ‬ ‫ماشین بردار پشتیبان در...

‫به نام خدا‬ ‫ماشین های بردار پشتبان‬ ‫جواد سلیمی سرتختی‬ ‫‪1‬‬  ‫مقدمه‪ -‬ماشین های بردار پشتیبان‬ ‫ماشین بردار پشتیبان یک دسته بند متعلق به روش های مبتنی بر کرنل می باشد‪.‬‬ ‫ ‬ ‫ماشین بردار پشتیبان در سال ‪ 1992‬توسط وپنیک ارائه شد‪.‬‬ ‫ ‬ ‫شهرت م‪.‬ب‪.‬پ بدلیل موفقیت آن در تشخیص حروف دست نویس است که با شبکه های عصبی‬ ‫ ‬ ‫که بدقت برای این کار تنظیم شده بودند برابری می کرد‪.‬همچنین م‪.‬ب‪.‬پ در کاربردهای زیر‬ ‫موفقیت های فراوانی را بدست آورده است‪:‬‬ ‫دسته بندی متن‬ ‫‪‬‬ ‫دسته بندی تصویر‬ ‫‪‬‬ ‫بیوانفورماتیک‬ ‫‪‬‬ ‫ایده اصلی در م‪.‬ب‪.‬پ بیشنه سازی حاشیه بین دو کالس می باشد‪.‬‬ ‫ ‬ ‫‪2‬‬ ‫ماشین های بردارپشتیبان‬ ‫‪w x + b>0‬‬ ‫)‪f(x,w,b) = sign(w x + b‬‬ ‫‪w x + b0‬‬ ‫کدام ابر صفحه مناسب تر‬ ‫است؟‬ ‫‪w x + b1‬‬ ‫‪w x + b< -1‬‬ ‫بردارهای پشتیبان‬ ‫‪6‬‬  ‫ماشین های بردارپشتیبان‬ ‫محاسبه حاشیه‪:‬‬ ‫ ‬ ‫‪ wxi + b ≤ - 1‬اگر ‪yi = -1‬‬ ‫‪yi(wxi + b) ≥ 1‬‬ ‫‪ wxi + b ≥ 1‬اگر ‪yi = +1‬‬ ‫از طرفی فاصله هر بردار پشتیبان تا ابرصفحه ‪ wxi + b =0‬برابر است با‪:‬‬ ‫ ‬ ‫)‪y vs (wx vs  b‬‬ ‫‪1‬‬ ‫‪r‬‬ ‫‪‬‬ ‫‪w‬‬ ‫‪w‬‬ ‫‪2‬‬ ‫بنابراین اندازه حاشیه برابر است با‪:‬‬ ‫ ‬ ‫‪M  2r ‬‬ ‫‪w‬‬ ‫‪7‬‬  ‫ماشین های بردارپشتیبان‬ ‫ الگوریتم بردار پشتیبان بدنبال بیشترین اندازه حاشیه می باشد یعنی‪:‬‬ ‫‪Minimize ||w||2‬‬ ‫‪Subject to: yi(wxi + b) ≥ 1‬‬ ‫که این یک مسئله برنامه ریزی غیرخطی با محدودیت هایی بصورت‬ ‫ ‬ ‫نامساوی است‪.‬‬ ‫راه حل‪ :‬روش ضرایب الگرانژ‪:‬‬ ‫ ‬ ‫‪8‬‬  ‫مضرب های الگرانژ‬ ‫فرض کنید می خواهیم تابع ‪ f‬را با توجه به محدودیت ‪ g‬کمینه کنیم‪:‬‬ ‫ ‬ ‫𝑦 ‪Minimize 𝑓 𝑥,‬‬ ‫‪Subject to 𝑔(𝑥, 𝑦) = 0‬‬ ‫می توان تابع ‪ L‬را بگونه ای تعریف کرد که گرادیان آن نقاط کمینه تابع ‪ f‬را با توجه به‬ ‫ ‬ ‫محدودیت ‪ g‬به ما بدهد‪:‬‬ ‫)𝑦 ‪𝐿 𝑥, 𝑦, 𝜆 = 𝑓 𝑥, 𝑦 − 𝜆𝑔(𝑥,‬‬ ‫که در این صورت خواهیم داشت‪:‬‬ ‫ ‬ ‫‪𝛻𝑥,𝑦,𝜆 𝐿 𝑥, 𝑦, 𝜆 = 0‬‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫و یا به عبارت دیگر‪:‬‬ ‫ ‬ ‫‪=0,‬‬ ‫‪= 0,‬‬ ‫‪=0‬‬ ‫𝑥𝜕‬ ‫𝑦𝜕‬ ‫𝜆𝜕‬ ‫‪9‬‬  ‫مضرب های الگرانژ‪ -‬ادامه‬ ‫فرض کنید می خواهیم تابع ‪ f‬را با توجه به محدودیت های ‪ gi‬کمینه کنیم‪:‬‬ ‫ ‬ ‫𝑦 ‪Minimize 𝑓 𝑥,‬‬ ‫‪Subject to 𝑔𝑖 (𝑥, 𝑦) = 0, i = 1, 2, … , n‬‬ ‫می توان تابع ‪ L‬را بگونه ای تعریف کرد که گرادیان آن‪ ،‬نقاط کمینه تابع ‪ f‬را با توجه به‬ ‫ ‬ ‫𝑛‬ ‫محدودیت های ‪ gi‬به ما بدهد‪:‬‬ ‫)𝑦 ‪𝐿 𝑥, 𝑦, 𝜆1 , 𝜆1 , … 𝜆𝑛 = 𝑓 𝑥, 𝑦 − ෍ 𝜆𝑖 𝑔𝑖 (𝑥,‬‬ ‫‪𝑖=1‬‬ ‫که در این صورت خواهیم داشت‪:‬‬ ‫ ‬ ‫‪𝛻𝑥,𝑦,𝜆1 ,𝜆1,…𝜆𝑛 𝐿 𝑥, 𝑦, 𝜆1 , 𝜆1 , … 𝜆𝑛 = 0‬‬ ‫و یا به عبارت دیگر‪:‬‬ ‫ ‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫‪=0,‬‬ ‫‪= 0,‬‬ ‫‪= 0,‬‬ ‫‪= 0,‬‬ ‫…‬ ‫𝑥𝜕‬ ‫𝑦𝜕‬ ‫‪𝜕𝜆1‬‬ ‫‪𝜕𝜆2‬‬ ‫‪15‬‬ 16  ‫مضرب های الگرانژ‪ -‬ادامه‬ ‫فرض کنید می خواهیم تابع ‪ f‬را با توجه به محدودیت های ‪ gi‬و نامساوی های ‪ hi‬را کمینه کنیم‪:‬‬ ‫ ‬ ‫𝑋 𝑓 ‪Minimize‬‬ ‫‪Subject to 𝑔𝑖 (𝑋) = 0, i = 1, 2, … , n‬‬ ‫‪And ℎ𝑖 (𝑋) ≥ 0, i = 1, 2, … , n‬‬ ‫می توان تابع ‪ L‬را بگونه ای تعریف کرد که گرادیان آن‪ ،‬نقاط کمینه تابع ‪ f‬را با توجه به تمام‬ ‫ ‬ ‫محدودیت های به ما بدهد‪:‬‬ ‫𝑛‬ ‫𝑛‬ ‫‪𝐿 𝑋, λ, 𝜇 = 𝑓 𝑋 − ෍ 𝜆𝑖 𝑔𝑖 𝑋 − ෍ 𝜇𝑖 ℎ𝑖 𝑋 ,‬‬ ‫‪𝜇𝑖 ≥ 0‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫که در این صورت خواهیم داشت‪:‬‬ ‫ ‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫𝐿𝜕‬ ‫‪=0,‬‬ ‫‪= 0,‬‬ ‫‪= 0,‬‬ ‫𝑛 ‪𝑖 = 1, 2, … ,‬‬ ‫𝑖𝑥𝜕‬ ‫𝑖𝜆𝜕‬ ‫𝑖𝜇𝜕‬ ‫‪17‬‬ ‫بیشینه کردن حاشیه با استفاده از مضارب الگرانژ‬ ‫‪𝑤 2‬‬ ‫)‪gi(x‬‬ ‫= 𝑥 𝑓 ‪Minimize‬‬ ‫‪2‬‬ ‫𝑚 ‪Subject to 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 − 1 ≥ 0, 𝑖 = 1, … ,‬‬ ‫𝑚‬ ‫𝑚‬ ‫𝑤‬ ‫‪2‬‬ ‫= )𝑥( 𝑖𝑔 𝑖𝜆 ‪𝐿 𝑤, 𝑏, Λ = 𝑓 𝑥 − ෍‬‬ ‫‪− ෍ 𝜆𝑖 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 − 1‬‬ ‫‪2‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫𝑚‬ ‫𝑚‬ ‫𝑤‬ ‫‪2‬‬ ‫=‬ ‫𝑏 ‪− ෍ 𝜆𝑖 𝑦𝑖 𝑤. 𝑥𝑖 +‬‬ ‫𝑖𝜆 ‪+ ෍‬‬ ‫‪2‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫𝑚‬ ‫𝑚‬ ‫𝑚‬ ‫𝑤‬ ‫‪2‬‬ ‫=‬ ‫𝑖𝜆 ‪− ෍ 𝜆𝑖 𝑦𝑖 𝑤. 𝑥𝑖 − ෍ 𝜆𝑖 𝑦𝑖 𝑏 + ෍‬‬ ‫‪2‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫‪18‬‬ ‫بیشینه کردن حاشیه با استفاده از مضارب الگرانژ‬ ‫بیشینه کردن حاشیه‪ -‬مسئله دوگان‬ ‫در حالت کلی‪:‬‬ ‫اما در برخی حاالت می توان گفت‪:‬‬ ‫بیشینه کردن حاشیه‪ -‬دوگان مسئله‬ ‫بیشینه کردن حاشیه‪ -‬حل دوگان مسئله‬ ‫بیشینه کردن حاشیه‪ -‬حل دوگان مسئله‬ ‫‪23‬‬ ‫بیشینه کردن حاشیه‪ -‬حل دوگان مسئله‬  ‫بیشینه کردن حاشیه با استفاده از مضارب الگرانژ‬ ‫شرط تعامد‬ ‫شرط مسئله‬ ‫𝑚‬ ‫شرط منفی نبودن‬ ‫𝑗𝑥 ‪𝑏 = 𝑦𝑗 − ෍ 𝜆𝑖 𝑦𝑖 𝑥𝑖.‬‬ ‫‪𝑖=1‬‬ ‫‪25‬‬ 26 27 ‫بیشینه کردن حاشیه با استفاده از مضارب الگرانژ‬ ‫راه حل های موجود برای بدست آوردن مقادیر 𝜆‪:‬‬ ‫ ‬ ‫حل دستگاه ‪ m‬معادله ‪ m‬مجهول زیر‪:‬‬ ‫ ‬ ‫تنها در صورتیکه همه داده های‬ ‫ورودی بردار پشتیبان باشند‬ ‫‪28‬‬ ‫مثال‬ ‫‪29‬‬ ‫مثال‬ ‫‪30‬‬ ‫ماشین بردارپشتیبان‪ -‬ضریب بی خیالی‬ ‫معادالت دو لبه حاشیه بصورت زیر می‬ ‫باشد‪:‬‬ ‫‪31‬‬  ‫ماشین بردارپشتیبان‪ -‬ضریب بی خیالی‬ ‫‪𝑔 𝑋 : 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 − 1 + 𝜉𝑖 ≥ 0‬‬ ‫‪3‬‬ ‫‪ℎ 𝑋 : 𝜉𝑖 ≥ 0‬‬ ‫‪4‬‬ ‫‪32‬‬ ‫ماشین بردارپشتیبان‪ -‬ضریب بی خیالی‬ ‫مشتق نسب به ‪w‬‬ ‫مشتق نسب به ‪b‬‬ ‫مشتق نسب به 𝜇‬ ‫شرط تعامد‬ ‫شرط مسئله‬ ‫شرط منفی نبودن‬ ‫‪33‬‬  ‫ماشین بردار پشتیبان مربعات حداقل‬ ‫هدف ‪ :‬تبدیل محدودیت های نابرابری به محدودیت های برابری‬ ‫ ‬ ‫مزیت‪ :‬افزایش سرعت الگوریتم و در برخی موارد افزایش دقت‬ ‫ ‬ ‫راهکار ارائه شده‪ :‬تبدیل معادله (‪ )3‬به معادله (‪)5‬‬ ‫ ‬ ‫𝑛‬ ‫𝜇‬ ‫𝜁‬ ‫‪5‬‬ ‫‪Minimize‬‬ ‫𝑤‬ ‫‪2‬‬ ‫‪+‬‬ ‫‪෍ 𝜉𝑖 2‬‬ ‫فاصله نمونه ها از مقدار واقعیشان‬ ‫‪2‬‬ ‫‪2‬‬ ‫𝑖‬ ‫‪𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 − 1 + 𝜉𝑖 = 0‬‬ ‫هنگامیکه میزان خطا درون فرمول کمینه سازی وجود دارد دیگر نیازی به‬ ‫محدودیت نابرابری نیست چون خطای آن محاسبه می شود‪.‬بنابراین محدودیت‬ ‫نابرابری به محدودیت برابری تبدیل می شود‪.‬‬ ‫‪34‬‬  ‫م‪.‬ب‪.‬پ مربعات حداقل‪ -‬ادامه‬ ‫𝑛‬ ‫𝑚‬ ‫𝑚‬ ‫𝑚‬ ‫𝑚‬ ‫𝜇‬ ‫𝜁‬ ‫‪6‬‬ ‫= ‪𝐿 𝑤, 𝑏, Λ‬‬ ‫𝑤‬ ‫‪2+‬‬ ‫𝑖𝜉 𝑖𝜆 ‪෍ 𝜉𝑖 2 − ෍ 𝜆𝑖 𝑤. 𝑥𝑖 − ෍ 𝜆𝑖 𝑏 + ෍ 𝜆𝑖 𝑦𝑖 − ෍‬‬ ‫‪2‬‬ ‫‪2‬‬ ‫𝑖‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫‪𝑖=1‬‬ ‫𝐿𝜕‬ ‫𝑚‪ 𝑤 = σ‬‬ ‫𝑖𝑥 𝑖𝜆 ‪𝑖=1‬‬ ‫𝑤𝜕‬ ‫𝑚‬ ‫𝐿𝜕‬ ‫‪෍ 𝜆𝑖 = 0‬‬ ‫مشتقات‬ ‫𝑏𝜕‬ ‫‪𝑖=1‬‬ ‫‪0‬‬ ‫𝑒‬ ‫𝑏‬ ‫‪0‬‬ ‫‪−1‬‬ ‫=‬ ‫معادله ‪5‬‬ ‫𝐿𝜕‬ ‫𝑖𝜉𝜁 = 𝑖𝜆 ‪‬‬ ‫‪𝑒 Ω + 𝜁 𝐼𝑁 Λ‬‬ ‫𝑌‬ ‫𝑏𝜕‬ ‫𝐿𝜕‬ ‫𝑖𝜉 ‪ 𝑦𝑖 = 𝑤. 𝑥𝑖 + 𝑏 +‬‬ ‫𝜆𝜕‬ ‫‪35‬‬  ‫م‪.‬ب‪.‬پ مربعات حداقل‪ -‬مقایسه با م‪.‬ب‪.‬پ‬ ‫داده های حلزونی‬ ‫نتیجه اعمال دسته بند‬ ‫نتیجه اعمال دسته بند‬ ‫م‪.‬ب‪.‬پ‬ ‫م‪.‬ب‪.‬پ‪.‬م‪.‬ح‬ ‫‪36‬‬ ‫م‪.‬ب‪.‬پ مقدار ویژه‬ ‫هدف ‪ :‬ایجاد دو ابرصفحه ناموازی به جای یکی‬ ‫ ‬ ‫مزیت‪ :‬افزایش دقت الگوریتم‬ ‫ ‬ ‫راهکار ارائه شده‪:‬‬ ‫ ‬ ‫‪ ‬فرض کنید ‪ m1‬نمونه متعلق به کالس ‪ +1‬و ‪m2‬‬ ‫نمونه متعلق به کالس ‪ -1‬باشد واین نمونه ها بترتیب با‬ ‫ماتریسهای ‪ A‬و ‪ B‬نمایش داده شوند‪.‬در م‪.‬ب‪.‬پ مقدار‬ ‫ویژه به دنبال دو ابر صفحه ناموازی همانند شکل روبرو‬ ‫هستیم‪:‬‬ ‫‪ ‬ویژگی این ابر صفحه ها این است که در عین اینکه‬ ‫کمترین فاصله را با نمونه های کالس خود داردند‪،‬‬ ‫بیشترین فاصله را با نمونه های کالس مقابل ایجاد می‬ ‫کنند‪.‬‬ ‫‪37‬‬  ‫م‪.‬ب‪.‬پ مقدار ویژه‪ -‬ادامه‬ ‫کاهش فاصله اقلیدسی در این مسئله منجر به رابطه کمینه سازی زیر می گردد‪:‬‬ ‫ ‬ ‫فاصله نمونه های کالس ‪ +1‬از ابر صفحه ‪1‬‬ ‫)‪𝐴𝑤 (1‬‬ ‫‪+‬‬ ‫)‪𝑒𝑏 (1‬‬ ‫𝑤 ‪/‬‬ ‫‪2‬‬ ‫‪7‬‬ ‫‪Min‬‬ ‫‪w,b≠0‬‬ ‫𝑤 ‪𝐵𝑤 (1) + 𝑒𝑏 (1) /‬‬ ‫‪2‬‬ ‫فاصله نمونه های کالس ‪ -1‬از ابر صفحه ‪1‬‬ ‫با اضافه کردن ضریب تیخونوف‪ ،‬معادله فوق تبدیل به یک معادله ‪ Rayleigh Quotient‬می‬ ‫ ‬ ‫گردد‪.‬‬ ‫‪8‬‬ ‫‪𝐴𝑤 (1) + 𝑒𝑏 (1) + 𝛿 𝑤 2‬‬ ‫‪Min‬‬ ‫‪w,b≠0‬‬ ‫)‪𝐵𝑤 (1) + 𝑒𝑏 (1‬‬ ‫با حل معادله فوق مقادیر ‪ w‬و ‪ b‬بدست می آید‪.‬‬ ‫ ‬ ‫‪38‬‬  ‫م‪.‬ب‪.‬پ توام‬ ‫این رویکرد در ذات شبیه رویکرد م‪.‬ب‪.‬پ مقدار ویژه می باشد‪.‬یعنی در اینجا هم بدنبال بدست‬ ‫ ‬ ‫آوردن دو ابر صفحه ناموازی هستیم‪.‬‬ ‫تفاوت آن با رویکرد م‪.‬ب‪.‬پ مقدار ویژه در این است که در اینجا به دنبال بیشینه کردن فاصله از‬ ‫ ‬ ‫کالس مقابل نیستیم بلکه نمونه های کالس مقابل تنها بصورت محدودیت در معادله ابر صفحه‬ ‫جاری ظاهر می شوند‪(.‬یعنی به دنبال بیشنه کردن فاصله از بردارهای پشتیبان کالس مقابل‬ ‫هستیم‪.‬‬ ‫به جای حل معادله برنامه نویسی غیر خطی با محدودیت های فراوان‪ ،‬م‪.‬ب‪.‬پ توام دو معادله با‬ ‫ ‬ ‫محدودیت های بسیار کمتر را حل می کند‪.‬‬ ‫‪39‬‬ ‫م‪.‬ب‪.‬پ توام‪ -‬ادامه‬ ‫م‪.‬ب‪.‬پ توام متعلق به ابر صفحه ‪:1‬‬ ‫م‪.‬ب‪.‬پ توام متعلق به ابر صفحه ‪:2‬‬ ‫‪40‬‬  ‫م‪.‬ب‪.‬پ توام‪ -‬مقایسه با م‪.‬ب‪.‬پ‬ ‫ب‪ :‬م‪.‬ب‪.‬پ توام‬ ‫الف‪ :‬م‪.‬ب‪.‬پ‬ ‫‪41‬‬ ‫م‪.‬ب‪.‬پ توام‪ -‬مقایسه با م‪.‬ب‪.‬پ مقدار ویژه‬ ‫الف‪ :‬م‪.‬ب‪.‬پ مقدار ویژه‬ ‫ب‪ :‬م‪.‬ب‪.‬پ توام‬ ‫‪42‬‬  ‫م‪.‬ب‪.‬پ توام مربعات حداقل‬ ‫ترکیب دو رویکرد م‪.‬ب‪.‬پ مربعات حداقل و م‪.‬ب‪.‬پ توام (استفاده از نقاط قوت هر دو رویکرد)‬ ‫ ‬ ‫نقطه قوت م‪.‬ب‪.‬پ مربعات حداقل‪ :‬تبدیل محدودیت های نابرابری به محدودیت های برابری‬ ‫‪‬‬ ‫نقطه قوت م‪.‬ب‪.‬پ توام‪ :‬استفاده از دو ابرصفحه‬ ‫‪‬‬ ‫به جای حل معادله برنامه نویسی غیر خطی با محدودیت های نابرابری فراوان‪ ،‬م‪.‬ب‪.‬پ توام‬ ‫ ‬ ‫مربعات حداقل دو معادله با محدودیت های برابری بسیار کمتر را حل می کند‪.‬‬ ‫‪ ‬معادله مربوط به م‪.‬ب‪.‬پ‪.‬ت‪.‬م‪.‬ح‪1‬‬ ‫فاصله نقاط کالس ‪ +1‬از ابرصفحه ‪1‬‬ ‫میزان خطای نمونه های کالس ‪+1‬‬ ‫ابر صفحه‪ 1‬باید نمونه های کالس ‪ -1‬را با در‬ ‫نظر گرفتن خطای ‪ y‬درست دسته بندی کند‬ ‫‪43‬‬  ‫م‪.‬ب‪.‬پ توام مربعات حداقل‪ -‬ادامه‬ ‫‪9‬‬ ‫‪10‬‬ ‫‪44‬‬  ‫م‪.‬ب‪.‬پ توام مربعات حداقل‪ -‬ادامه‬ ‫به طور کلی می توان م‪.‬ب‪.‬پ توام مربعات حداقل را در قالب الگوریتم زیر بیان نمود‪:‬‬ ‫ ‬ ‫تعریف ماتریس های ‪ F‬و ‪ E‬بر اساس ‪ A‬و ‪.B‬‬ ‫‪(1‬‬ ‫انتخاب پارامترهای ‪ C1‬و ‪ C2‬که معموال بر اساس خطا و آزمون تعیین می شود‪.‬‬ ‫‪(2‬‬ ‫تعیین پارامترهای دو ابر صفحه بر اساس فرمول های بدست آمده در اسالید قبل‪.‬‬ ‫‪(3‬‬ ‫محاسبه فاصله عمود نمونه جدید از دو ابرصفحه بدست آمده‪.‬‬ ‫‪(4‬‬ ‫انتساب نمونه جدید به یکی از کالس های ‪ +1‬و یا ‪ -1‬بر اساس فاصله بدست آمده از مرحله‬ ‫‪(5‬‬ ‫قبل‪.‬‬ ‫‪45‬‬  ‫م‪.‬ب‪.‬پ توام مربعات حداقل‪ -‬مزایا‬ ‫افزایش سرعت یادگیری نسبت به م‪.‬ب‪.‬پ‬ ‫ ‬ ‫از آنجاییکه در م‪.‬ب‪.‬پ توام برای کمینه سازی هر یک از معادالت نیمی از محدودیت ها به کار گرفته‬ ‫‪‬‬ ‫می شوند بنابراین می توان گفت که م‪.‬ب‪.‬پ توام سرعت یادگیری را چهار برابر افزایش می دهد‪:‬‬ ‫‪𝑚3‬‬ ‫‪𝑚 3 =4‬‬ ‫) (‪2‬‬ ‫‪2‬‬ ‫م‪.‬ب‪.‬پ مربعات حداقل‪ ،‬محدودیت های نابرابری را تبدیل به محدودیت های برابری می کند که این‬ ‫‪‬‬ ‫کار باعث افزایش شدید سرعت می شود‪.‬‬ ‫افزایش دقت نسبت به م‪.‬ب‪.‬پ‬ ‫ ‬ ‫‪46‬‬ ‫کارایی م‪.‬ب‪.‬پ توام مربعات حداقل‬ ‫‪SVM‬‬ ‫‪83.0‬‬ ‫‪79.0‬‬ ‫‪76.0‬‬ ‫‪82.0‬‬ ‫‪82.0‬‬ ‫‪59.0‬‬ ‫‪85.0‬‬ ‫‪94.0‬‬ ‫‪77.0‬‬ ‫‪74.0‬‬ ‫‪65.0‬‬ ‫‪77.8‬‬ ‫‪47‬‬ ‫کارایی م‪.‬ب‪.‬پ توام مربعات حداقل‬ ‫‪48‬‬ 49 50 ‫یادگیری در فضای ویژگی غیر خطی ‪ :‬مسئله جداسازی‬ ‫میتوان با نگاشت داده به یک فضای ویژگی آنها را بصورت خطی جداپذیر نمود‪:‬‬ ‫ ‬ ‫‪51‬‬  ‫تبدیل داده به فضای ویژگی‬ ‫) (‪f‬‬ ‫) (‪f‬‬ ‫) (‪f‬‬ ‫) (‪f( ) f( ) f‬‬ ‫)‪f(.‬‬ ‫) (‪f‬‬ ‫) (‪f‬‬ ‫) (‪f‬‬ ‫) (‪f( ) f‬‬ ‫) (‪f( ) f‬‬ ‫) (‪f‬‬ ‫) (‪f( ) f‬‬ ‫) (‪f‬‬ ‫) (‪f‬‬ ‫‪Input space‬‬ ‫‪Feature space‬‬ ‫‪Note: feature space is of higher dimension‬‬ ‫‪than the input space in practice‬‬ ‫انجام محاسبات در فضای ویژگی میتواند پرهزینه باشد برای اینکه ابعاد بیشتری دارد‪.‬‬ ‫ ‬ ‫در حالت کلی ابعاد این فضا بی نهایت است‪.‬‬ ‫ ‬ ‫برای غلبه بر این مشکل از ‪ kernel trick‬استفاده میشود‬ ‫ ‬ ‫‪52‬‬ ‫ترکیب غیرخطی ویژگیها‬ ‫‪53‬‬  ‫مشکالت فضای ویژگی‬ ‫کار کردن با فضای ویژگی با ابعاد باال مشکل است‬ ‫ ‬ ‫عالوه بر مسئله باال رفتن هزینه محاسباتی ممکن است مشکل تعمیم نیز بواسطه ‪curse‬‬ ‫ ‬ ‫‪ of dimensionality‬بوجود آید‪.‬‬ ‫‪54‬‬  ‫نگاشت غیر مستقیم به فضای ویژگی‬ We will introduce Kernels: Solve the computational problem of working with many dimensions Can make it possible to use infinite dimensions efficiently in time / space Other advantages, both practical and conceptual 55  ‫کرنل‬ Transform x  f(x) The linear algorithm depends only on xxi, hence transformed algorithm depends only on f(x)f(xi) Use kernel function K(xi,xj) such that K(xi,xj)= f(x)f(xi) 56  An Example for f(.) and K(.,.)  Suppose f(.) is given as follows  An inner product in the feature space is  So, if we define the kernel function as follows, there is no need to carry out f(.) explicitly  This use of kernel function to avoid carrying out f(.) explicitly is known as the kernel trick 57 ‫مثال‪ :‬کرنل چند جمله ای‬ ‫‪58‬‬ ‫چند تابع کرنل معروف‬ ‫‪59‬‬ 60 61 62  ‫ساخت کرنل ها‬ ‫ ‬ ‫مجموعه قوانین زیر در مورد کرنل ها صادق است‪:‬‬ ‫‪ If K, K’ are kernels, then:‬‬ ‫ ‬ ‫‪K+K’ is a kernel‬‬ ‫ ‬ ‫‪cK is a kernel, if c>0‬‬ ‫ ‬ ‫‪aK+bK’ is a kernel, for a,b >0‬‬ ‫ ‬ ‫……‪Etc etc etc‬‬ ‫ به این ترتیب میتوان کرنل های پیچیده را از روی کرنل‬ ‫های ساده تر ساخت‪.‬‬ ‫‪63‬‬ Multi-class Classification SVM is basically a two-class classifier One can change the QP formulation to allow multi-class classification More commonly, the data set is divided into two parts “intelligently” in different ways and a separate SVM is trained for each way of division Multi-class classification is done by combining the output of all the SVM classifiers Majority rule …. 64