ماشین بردار پشتیبان

صفحه 1:
ماشین بردار پشتیبان ۱ Ghiry 6666 

صفحه 2:
© امقدمه * 0 دسته ب ندیک نندم لعلستک ه جزو شاخه ام د21 اه(1) دريادكيرىماشينمحسوبميشود. * )در سال00) توسط بلمرن() معرفی‌شده و بر پایه رس مسا سونو بنا گردیدم لستِ * شهرت (96(6) بخاطر موفقیت آن در تشخیص حروف دست نویس است که با شبکه های عصبی بدقت تنظیم شده برابری ميكند: 900.0 خطا 

صفحه 3:
۶ امعدمه * هدف اين دسته الگوریتم ها تشخیص و متمایز کردن الگوهای پیچیده ‎FS‏ داده هاست ( از طریق کلاسترینگ» دسته بندی» ‎(Sa)‏ پاکسازی و غیره) ‎٩‏ مسایل مطرح: ‏* الگوهای پیچیده را چگونه نمایش دهیم * چگونه از مسئله ,برس پرهیز کنیم 

صفحه 4:
© با فرض اينکه دسته ها بصورت خطی جداپذیر باشند ابررصفحه هاتى با حذاكئر حلقية (بچسعی سس را بدست می آورد که دسته ها را جدا کنند. * در مسایلی که داده ها بصورت خطی جداپذیر نباشند داده ها به فضای با ابعاد بیشتر نگاشت پیدا میکنند تا بتوان آنها را در اين فضای جدید اسر یس | نمود. 

صفحه 5:
9 Guppent Orvior Quobkices ure u spstew Por foduced Peuture spuves, while nespevitoy the iosiqhts ‏سوه موجه مه تس طسو خام‎ ‏سا‎ ‎© Cristacict & Ghawe-Dupor (COO) 

صفحه 6:
مسئله جداسازی خطی: :2 دا(!) عوصوارا © اگر دو دسته وجود داشته باشند که بصورت خطی از هم جداپذیر باشند» بهترین جدا کننده اين دو دسته چیست؟ # الگوریتم های مختلفی از جمله پرسپترون میتوانند این جداسازی را انجام دهند. ۶ آیا همه اين الگوریتمها بخوبی از عهده اینکار بر میایند؟ 

صفحه 7:


صفحه 8:


صفحه 9:


صفحه 10:


صفحه 11:
۱ 6 

صفحه 12:
6ه 66 

صفحه 13:


صفحه 14:


صفحه 15:


صفحه 16:
:: اضرب داخلی 2 ‏ضرب داخلی را میتوان معیاری از تشابه دانست‎ ٩ A - مب و[ ‎a-b=alh.co#‏ ۶ در حالت » بعدی میتوان آترا بصورت زیر نمایش داد. ۳ ‎ab‏ د ‎abe R’ (ab)‏ i ‏م‎ 

صفحه 17:
32 اخط یا ابر صفحه جدا کننده xd * هدف: پیدا کردن بهترین خط ( ابر صفحه) که دو دسته را از هم جدا کند. در حالت دو بعدی معادله این خط بصورت زير است: 0< + ۲۷۷۵26 + ۲2 © در حالت > بعدی خواهیم داشت: >, wixi+ b=0 w .x+b=0 

صفحه 18:
ايده 680000 براى جدا سازى دسته ها © دو صفحه مرزى بسازيد : © دو صفحه مرزى موازى با صفحه دسته بندى رسم كرده و آندو را آنقدر از هم دور ميكنيم كه به داده ها برخورد كنند. ‎٩‏ صفحه دسته بندی که بیشترین فاصله را از صفحات مرزی داشته باشد؛ بهترین جدا کننده خواهد بود. ‎wx+ b= a)‏ Oh م ۲۸۷+ 3 

صفحه 19:
# بر طبق قضیه ای در تئوری یادگیری اگر متالهای آموزشی بدرستی دسته بندی شده باشند» از بین جداسازهای خطی آن حداسار ی که حاشیه داده های آمورستي را حداکتر میکند خطای تعمیم را حداقل خواهد کرد. 1106+ «- Oh ۲۸۷+ 3 

صفحه 20:
© به نظر میرسد که مطمئن ترين راه باشد. ۶ تئوری هائی برمبنای »متسر 0) وجود دارد که مفيد بودن آنرا اثبات میکند. © بطور تجربی این روش خیلی خوب جواب داده است. 

صفحه 21:
بان نزدیکترین داده های آموزشی به ابر صفحه های جدا کننده بردار پشتیبان نامیده میشوند xd 

صفحه 22:
22 تسیم و ‎GOD‏ 9 در صورت استفاده مناسب از (6000© اين الكوريتم قدرت تعمیم خوبی خواهد داشت: ‎٩‏ علیرغم داشتن ابعاد زیاد (رناممسصسسد ط) از بمنبممه پرهیز میکند. این خاصیت ناشی از «طاهداهاسه اين الگوریتم است ‎٩‏ فشرده سازی اطلاعات: * بجای داده های آموزشی از بردارهای پشتیبان استفاده میکند. 

صفحه 23:
احل مسئله برای حالت دو بعدی تمونه های آموزشی ۳ 6 « ‎ve (4,‏ ۶ تابع تصمیم گیری (ط + سوه ع م۲ ‎we Re‏ bER * میخواهیم مقادیر ط ,()رابگونه ای پیدا کنیم که: * نمونه های آموزشی را بدقت دسته بندی کند * با این فرض که داده ها بصورت خطی جدا پذیر باشند ‎٩‏ اشیه را حدلکتر نماید 2 

صفحه 24:
Liew GOO Oukewuiodly © Let trating set {(xi, p)}AC.. 0, ERY, 17 € {-, O} be ee a eres a as eae ‏لوس‎ ‎(xi, 11): 3 ۲ ۱ bie 6/2 ‏رده عر رك‎ - pl2 ۷۳ + ‏ترز 1۴ ۵/2 < ط‎ © Gor every support vevior xs the ubove icequaliy is oc equally. ORter resvatec us ond bby O/C ta the equality, we obtaic trot ‏هروا من‎ euck x= ued the kyperplooe is ‏دسر‎ 1 0 ‏ی دس سم و سس رس(‎ keel) eee > 2 p=2r= ۷ 

صفحه 25:
:: احل مسئله برای حالت دو بعدی ۲۵۵ ۵۵ Px)>O * فاصله خط جداکننده از مبدا برا براست با ۳ :# فاصله نمونه ای مثل « از خط جدا کننده برابر است با 

صفحه 26:
تعیین حاشیه بین خطوط جدا کننده Phis-pour = {xiw.xtb=td} Oicus-pe = {x iw. xtb=-d} OkossiPy us... -0 PF ‏را ید بر‎ > 0 +1 Pw.xtb>= Classifier Boundary سس سس و 0 ‎COR‏ ‎ig 8‏ ‎Pus Pane‏ الال ‎ ‎ 

صفحه 27:
* |محاسبه پهنای حاشیه ‎٩‏ صفحه مثبت و منفی را بصورت زیر در نظر میگیریم: ‎={xiw.xtb=+d}‏ لمیر و ‎Drnws-phrw = {iw tb = 0}‏ © ‏* بردار ری بر صفحه مثبت ومنفی عمود خواهد بود. ‏© فرض كنيد 2 نقطه ای در صفحه منفی بوده و (+ نزدیکترین نقطه در ‏صفحه مثبت به - باشد. ‎\M =Margin Width ‎ ‎ ‎ ‎ ‎ee ‎ ‎ 

صفحه 28:
‎٩‏ خطی که - رابه »9+ وصل میکند بر هر دو صفحه عمود خواهد بود. لذا فاصله بین دو صفحه مضربی از () خواهد بود. در اینصورت خواهیم داشت: ‎xt= ot Aw Por sowe udu oP A.‏ ‏لايد ‏م ‎we‏ نم ‎ ‎ ‎\M =Margin Width \ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 29:
© ميدانيم كه: ©» ‏را + ني . رن‎ - +0 © ‏غ + مر . رن‎ - -0 MH xt hw 9 | x*- x] =O ‎le‏ میتوان 0) را برحسب ()و « محاسبه کرد. ‎۱۸2۵۱۸ 

صفحه 30:
w(xt Aw) +b = +0 | wxthww tb = +d | -(+ A wan = +0 | A=C/ waw 

صفحه 31:
؟ امحاسبه پهنای حاشیه 5 ٩ ۲ - ۳ fidth = 2 [CN = Margin Width - == عر Be gers OSI ape [xt oc | =| aw |= ۲ 2 + < ور + هر , با w.xtb=-1 2h waw 2 ial Gaus ww Vw.w [xt - ‏>د‎ | = 7 2 ww < 215۷| 2 What we know: 

صفحه 32:
7 امحدودیت * اگر برای مثال دو بعدی فوق مقدار دسته ها را با 6 و )- مشخص کنیم داریم: ‎Por pad‏ 0 2 9 + جرک و ‎e <wyx> tbs -d Por p= -d‏ 9 که میتوان آنرابصورت زیر نوشت ‎(<w,x> +b) 20 Por hi‏ بر »© 

صفحه 33:
:: اجمع بندی حل مسئله ۶ در (0(0) بدنبال حل همزمان معادلات زیر هستیم: ۶ با داشتن مثالهای آموزشی ( ‎WE{+,-C} 4S (ad,‏ :(0,0,...۲<ز "سا ین ۰ ذلك ۳ 0 2 ‎(<w,x> +b)‏ بر : وا سل © سکب س۳| ما عون * © این یک مسئله موسر موی با محدودیت هائی بصورت نامعادلات خطی است. روشهای شناخته شده ای برای چنین مسئله هائی بوجود آمده اند. 

صفحه 34:
Quadratic 6 8 ۳ 5 3 u Ru sy Find argmax ¢+d?u+——— -———— Quadratic critet Subject to Aly + yyy H+ Ay My SD, Axl, + AyyUy +. Fy Uy = Dy n additional linear inequali constraints wath Gill ‏كا‎ Ay Wy + Ay atl And subject to 4 ‏صجى2 - مالورريبى 6 +... + والوريبى 6 + وزرب‎ Aner lly + Angra +--+ 0 ‏رمبى2 - وماتورريبى‎ squiensuo2 Auenbs همم = ‎Ansell +--+ Unseymllm‏ + رالروبی4 

صفحه 35:
Qevup vF Ovestrated 60۵ © Suppose we want io! winivize Ac) subject i x(x) =O 9 ‏تمعاسي بام هدعا ببطليوه ييه ف‎ we +ag(x))) =0 مسر ‎g(x) =0‏ ام ترا ‎et he‏ © ۶ ) ‏ی‎ cvastruiis y(x) = O, Fd, ..., 7, we ceed o Lagrange ‏ری‎ ot, Por mack oF the costes 0= زموه يط + وماج | ‎fori=1,..., m‏ مح تيو 

صفحه 36:
Qevup vF Ovestrated 60۵ © Phe ose Por equally cocstrctat g(r) < Oe scien, except thot he Lara srultipter o,, shoud be postive ‏موه له بط نا موه و و رخ و‎ problew min f(x) subject to g(x) <0 fori=1,...,m © Dhere west exist oF > 6۱ Pee i= ‏فا و مب‎ cri, ‏إ(ممنويم + وماج‎ 0 re g(x) <0 fori=1,...,m 200 + ‏نويه ر5‎ ‏مت با و‎ i ue to set tts rercicat to OD dey heowa os he Laren tan we 

صفحه 37:
‎sly‏ حل معلاله ‏میا عطا موی 8 عون 0 ‎wrtconstraint >0,i=1...N‏ ‏ققشت عسة عسي ا لح عب ا سن ل ل 7 ‎5 5 ‏زره ز لاد مظعل‎ -0 >parameters are expressed as a 0 28 ‎altw.ha) 2 linear combination of training ‏سس‎ ab — points ‎KKTcondaly(wx +B)- 11=0‏ ‎a,‏ ۱09-2670 76هظ یی وی پر 0 را را ۱ ‎ ‎9 

صفحه 38:
Class 1 

صفحه 39:
The Oud Problew * Rue nb we Saxe boron jue her 12 ۳۹۳ n n ۳ = 22 x ‏زءزلازيه ب یه‎ x a ( ‏رازه بعت‎ + ») j=l non 3 7 ۳ له رز - رازه رز اه رز — ‎a‏ + رد ارت تاره زر 5= = ‎j=l i=1‏ i=1j=1 1 ‏بت‎ ‎= ‏بو تج‎ DY aieguinyxt byt Yai i=1j=1 » ‏رز دا ده‎ ۷ 20 © Dk iso Puonticn oP ‏تا‎ 

صفحه 40:
The Oud Problew © Dhe cew vbjeviive Puariiog is io terse oP 1, vol © his keouse us the dud problew! P uve how ww, we haow oll 0; Pe hom ol 0, we hoo we ام ام ‎problew te koowe us the‏ نی با و ‎the dudl problew oerds to be woxtized!‏ اه موی( شزا ۲ و ‎Dke dod problec is therePore:‏ و ‎ ‎ ‎n ‎1 7 max. W(a) = ‏زک بدرلانازوزه - وه‎ i=1 n subject to a; > 0, Say = ‎Properties of a, when we The result when we differentiate introduce the Lagrange the original Lagrangian w.r.t.b ‎multipliers 

صفحه 41:
The Oud Problew L <— 7 = </2 ‏زا اكتزلازلارعيه‎ =1j=1 7 subject to a; >0, ‏زاره‎ = 0 i=1 n max. W(a) = > aj — ‏اح‎ © This is 0 quadratic programeviegy (QP) problew © ‏میت اون و‎ oF ‏یره‎ chvaye be Pouerd ‎be revered by n‏ موم رن و ‎w= > ‏كمرك‎ ‎i=1 

صفحه 42:
‎sly‏ حل معلاله ‎by, ‏د‎ 4 ‏,مه‎ W= J, YR =D, ot YR Pha this back to he Lagraccfar ty bts the dal orem Whe resulta dh fro is soled Por of by wskny a QP sober: maximisdM(a) =- ‏لاه‎ ati YY RK, + 2 ‏ی‎ ‎subject a AY, =0,a, 20,i=1,.. ‎Whe b does ont oppor ta he dd sv ‎te deerme suru ‎Bree hes eel coh ee Data enters only in the form of dot ‎products! ‎we 

صفحه 43:
2 دسته بندی داده های جدید ۶ پس از آنکه مقادیر (ط ,*0) با حل معادلات سم بر اساس داده های ورودی بدست آمد» میتوان 86(60) را برای دسته بندی نمونه های جدید بکار برد. ۶ اگر »« یک نمونه جدید باشد. دسته بندی آن بصورت زیر مشخص میشود: ۶ ‏که امد‎ b’)], where foo’, B) =wx+B =Y" of yxx+B =Y aye Data enters only in the form of dot products! 9 

صفحه 44:
:؟ اویژگی های راه حل ‎oP the GOO, ie. oP the quadratic‏ مشاه با و ‎has‏ وی موه ما خاش ‎probes‏ بجر ‎the Pore oP dot‏ جز ‎the vice property thot the dota euters valy‏ ‎procucts!‏ ‎Oot pod (waive & wewory rePreshioy): give‏ و ‎Ged PE(VaVer---V,)s thee the dot product oP x‏ لد )یر ‎ward pb Y= (mas KOVOr +s RM a)>‏ ‎° Dis is cig becouse tl dlows us 7 woke GOOs ‏اوه‎ ‎witout coxpphicatiag the uyoriiha ‎ee 

صفحه 45:
Pre Quadratic Proqracneicry @rvblew © Oy wprowhes hove bers proposed © bee ee ce © Dost we “iaterio~poidt” wetkods © Gtot wits oc tottd schuiog hot coc vicki ‏موه‎ ‎© Aeoprove this ‏جملا باص كحم عو للم مت ماه با موه روا ماو‎ ‏متواص اموویی ۴و موم‎ ‏و‎ Por GOO, sequecidl wisicval ppivizaiva (SOO) seews to be the wost popular © © GC wk te vortubles is rivid to sche ۶ ‏مها و‎ oF GOO picks a pair oF (0,01) ood solve the QP wits these ‏وس سس بسن سلاو بوسر‎ ۱ GP svlver us a “black-box” wikout ‏ولا‎ how it works es 

صفحه 46:
:: اداده هائی که بصورت خطی جدا پذیر نیستند یک فرض بسیار قوی در (96(6) اين بود که داده ها بصورت خطی جداپذیر باشند. در حالیکه در عمل در بسیاری مواقع اين 6م 

صفحه 47:
افزودن متغیر های !سلاو * یک راه حل این است که ‎oli gS Sail‏ آمده و مقداری خطا در دسته بندی را بپذیریم! * اين كار با معرفى متغير 5 انجام میشود که نشانگر تعداد نمونه هائی است که توسط ‎wath ati‏ غلط ارزیابی ميشوند. | 3 ‏م ه‎ 2 Pa w we 

صفحه 48:
shack la ‏|افزودن متغير‎ *: 9 با معرفی متغیر() ,... ,9 ,0 ,5أ,ر محدوديت هاى قبلى ساده تر شده و رابطه ‎(<w,x> + b) 20‏ بر ؟ بصورت زیر تغییر میکند: ‎v, (Swix? +b) 20-§, 520‏ * در حالت ايده آل همه اين متغير ها بايد صفر باشند. eo 

صفحه 49:
© در اینصورت مسئله بهینه سازی تبدیل میشود به یافتن ررر به نحوی که معادله زیر مینیمم شود: ‎Mio es?‏ subject To Ylw'x,+D21-§, §20, vi 9 که ‎O> DM yl‏ میباشد. جمله اضافه شدن سعی دارد تا حد امکان همه متغیرهای ربلد را کوچک نماید. 

صفحه 50:
© رابطه دوگان در حالت جدید بصورت زیر خواهد بود. ‎Sai) SS ava 2)‏ هد لسن ‎ ‏* مقدار مناسب م بر اساین داده:های ‎Alias‏ انتخاب میشود. ‎eo 

صفحه 51:
GoFt QOuarqd ۱ © ‏مس رخ‎ W, ‏كمد ع رجا‎ be ‏بو تنج‎ wixjtb>1-& yal wx; +bS-14+& y=-1 & 20 Vi © § we “stack vortubles” ta optcotzatica * ‏ما سوه‎ 20 BP there te ww error Por x, © oa upper bond oP the eg oP ern 21۳۳۱۳ + 0 ‏ور‎ 6 ‎Op watt ty wivicvize‏ و ‎Ot tradevPP poraveter betwee enor ond wart‏ © اه ‎Minimize 4}||w||? + CD, &‏ ‎subject to y;(w?x;+6)>1-G, 6 < ۳‏ 

صفحه 52:
The 0 ۱ ‏ای‎ ‎1 2 max. W(a) = 2 ‏-به‎ 3, DY ‏رنه‎ ‎subject ‏برونه 2۳ ,0 < به < 0 مه‎ 0 ‏ی‎ ‎2-5 ‏ل ۹ ع بن‎ 3 ‏رازه دسر(‎ ‏با و‎ ts very sitar to the opieizatod problew to the bara seporuble ‏وی‎ ‎except tho there is oc upper bound O vo Ow ۶ Over agai, ¢ QP solver coo be used ty Pied 0, 8 wis reopened os ee 

صفحه 53:
§ امسئله جداسازی غیر خطی : یادگیری در فضای ویژگی * میتوان با نگاشت داده به یک فضای ویژگی آنها را بصورت خطی جداپذیر نمود: ‎(x)‏ جعر 

صفحه 54:
Input space Feature space Note: feature space is of higher dimension than the input space in practic ۷ ‏انجام محاسبات در فضای ویژگی میتوآند پرهزینه باشد برای اينکه ابعاد بیشتری دارد.‎ ۶ ‏در حالت کلی ابعاد اين فضا بى نهايت است.‎ * ‏برای غلبه بر اين مشکل از جامده اسب استفاده میشود.‎ © 

صفحه 55:
‎ee‏ مشکلات فضای ویژگی ‎٩‏ کار کردن با فضای ویژگی با ابعاد بالا مشکل است ‏© علاوه بر مسئله بالا رفتن هزینه محاسباتی ممکن است مشکل تعمیم نیز بواسطه ,ادوص دروك *ام دوج بوجود آيد. ‏هه 

صفحه 56:
نگاشت غیر مستقیم به فضای ویژگی ‎De will troduce Kercels:‏ و ‎Gove the coxoputatiocal problew oP workers wit wo‏ © سس ‎Coo woke it possible to use inPicite dieusives‏ © ‎PP Riedy in toe | space‏ »© ‎Other advantages, botk pracica cod pooreptad‏ © 

صفحه 57:
كرئل ی © ‏مرا ما با‎ depeods vay vox, Keue troasPorwed ukprikes depeuds vey vot (x) (5) © ‏ی اس بو(‎ K(x.) suk thot K(x,%)= (>«)(2) Input space 

صفحه 58:
ua Cxcnvope Por $(.) ard K(.,.) Guppose 0(.) i quedo Polos 0([25]) = (1, 201, V200, 09,903, V20109) (Bo tecer produ to the ‏مهو(‎ spare te (6([23]),0(())) = + ery + 2292)? (Sp, PF we dePioe the kerael Puontiog as Polows, there te a ceed ty cary cn (.) empha K(x y) = (1+ 21y1 + r2y2)? جه مستحححا صا ببلاصتادوك (.)() ‎oul‏ روصت له وا یاهع ‎his‏ vere trict 

صفحه 59:
m-thDegrepolynomiak(x x) =(1+ (x x))” Radiabasis K(x x) =expé ||x- x|f/0 Neuraletworkk(x x’) =tanhki< x x'> +2) K(x,z) = (x,z)" K(x,z)=e hte x V2xx, x 3 "رت (بعد ‎K(x,‏ - واو هه 

صفحه 60:
‎3s‏ مثال: کرنل چند جمله ای ‎ ‎- x, Bis) (2 2 Eas =(9(2),0@)) —saarsinpnveceeret 

صفحه 61:
QOodPicaiod Our to Kercet uation © Chooge of ‏موز‎ products to kercet Poot ‏بل ه‎ 5 ۲ Original n 1 9 max. W(a) = 7 ‏زر وه‎ aiojyiyyx? x; subject to C > a; >0, > ayy; = 0 i=1 3 ۳ ‏رسد‎ ‎With max. W(a) = Sais YO ajayyyyjK (xi, x;) kernel A ‏كم‎ ‎function 7 0 رازه زر ,0 < یه < 0 ۲0 ‎subject‏ i=1 

صفحه 62:
QOodPicaiod Our to Kercet Puccio © (Por testing, the cew dot z is clossiPied us class (1 iP PO, ocd os kes O PP <O 8 Original w=)>) ‏رنه‎ ‎i ‎f=w Tabb On; ‏حل را‎ 0 : = ‏بر‎ oe yt, P(Xt;) With kernel function f= ۳ ‘6(@) b= = a yt, K (Xt;, 2) +b ee 

صفحه 63:
هه Ovduariy با ‎oP‏ ری میاه مها لحاس رو و ال ممی رما سم ‎yecerd‏ © مد اس تاه مططامم ۵ © ‎wi cay Kercel‏ لا مه مه 6) رو و ‎Cert thewseves vod be coostrunted tao woddtar way‏ © ‎Grea Por svPwore euyiaperiog (wad Por ura)‏ © 

صفحه 64:
#3 ساخت کرئل ها © مجموعه قوانین زیر در مورد کرتل ها صادق است: ی ‎Kt is a hereel‏ © ‎DK is ukerce|, P o>O‏ © ‎M+ is a hereel, Por u,b >O‏ © ‎Cte etc etr......‏ © © به اين ترتیب میتوان کرنل های پیچیده را از روی کرنل هاى ساده تر ساخت. 

صفحه 65:
Cxxcnople ١ 9: ‏سحي‎ ۱ eee: ‏ا ا ی ات را نا‎ ‏وب رترب ,کون راکوب راحرنر < 9 عصعاه‎ aR De ‏ميد حل لها لمعيه عا بس‎ © © ‏سوم < (سع‎ ۰ ) ‏بو ع‎ «00 © We Prot Ped 0, (Ad, ...,S) by ‏كاي‎ 2 max. ‏يه زح‎ 5 YS DS aagyiy; (ex; + 1) i=1 141 5 subject to 100 >a; >0, > ayy; =0 i=1 

صفحه 66:
۷ © Op usin ‏ه‎ QP sober, we vet © aFO, a,=2C.S, a,=O, o=?.999, a,=F.899 ® Oote thot the oocstraicts ore tedeed suttoPied © Dhe support vectors ore {xo=O, xp=S, xo=O} ۷15 ۰ 1 ‏مت منود‎ a5 K(z, a5) f(z) / = 2.5(1)(22 + 1)? + 7.333(-1)(Sz + 1)? + 4.833(1)(6z + 1)? +6 = 0.666727 — 5.333z +b ,0 ت(ت)" ‎bis recovered by soins (C)=0 or by P(G)=4 or by‏ * 1ع مط ين 0ن 0 صما صا صم جلا نود عدم ويد حت ‎o(w)o(x) +6 = -1‏ ها و ‎f(z) = 0.666727 — 5.333249‏ >= مر مرن ‎Oliver‏ © هه 

صفحه 67:
۷ alue of discriminant function 

صفحه 68:
تشخیص حروف دست نویس © در اداره يست آمریکا با استفاده از اين روش توانسته اند به خطائى در حدود “900 برسند. مثالى از كاربرد output Dv, £6a)+5 weights ‎prt (B14) M))= KE)‏ او ‎mapped vectors P05) 68)‏ ‎support vectors ky‏ ‎SHE ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 69:
مراحل استفاده از 90)0) برای دسته بندی ‎repo the dota wutrix‏ ل ‎© Gelent the herael Puartivg to use ‎© Creo the trotcicy chore usiey 1 QP sper to vbtaic the CO, values ‎۰ )( ‏ول یو‎ coo be chssiPied ‏دص ام يه هذا عدص‎ ed the support veviors ‎0 

صفحه 70:
انتخاب تابع كرنل © جدى ترين مسئله در روش (0000 انتخاب تابع كرنل است. * روشها و اصول متعددی برای اين کار معرفی شده است: ‎diPPusive kereel, Pisker kercel, string kercel, ...‏ و تحقیقاتی نیز برای بدست آوردن ماتریس کرنل از روی داده های موجود * ‎ry ‎dose related to ROP ‏.در حال انجام است ‏در عل ۰ او ‎ )٩/6‏ او ارام مر زرا شم و © ‎a reusvouble widts is a youd initial‏ کرد ‎Ovte ha GOOD wi ROC kercel ix‏ ‎ ‎ ‎wits the mecters oP the redial basis Pucctions‏ ,وه اسهم ‎chosed Por SOM‏ نموه 

صفحه 71:
امه 000 « ون له ‎proposed by Boser, Buyoa‏ زاو و ۵0 و 02ص و تلور مهو لصو له ‎coceber oF‏ وه ۲ وا ما اجه راوس مه ‎GOOs‏ و موی صا فا ما زو لو موسوم ‏ی ‎dota per beyood Peoture‏ موه وا تاهج موم ۵0۶ و ‎ote; srqueues, rebiccd data) by desiqoiog heroel Puccticas Por suck‏ ‏كت حاصك حخاصم خام عصحاصعب ه صا لجلمجاءك وا ل 5 ‎et‏ امس ت0] اه سوه منم [ 19 ‎eet‏ ووو ‎of." 58‏ ‎bik‏ وا سل عص ۵)0((2) ۲ اما مشاه ملس تس و ‎dhe per uber of Oe ot ute, eg. GOO [Plat OO] aed‏ ‎Nouchies '99]‏ ‎© ‏يحص"‎ GOOs ‏اه موی‎ ot! ‏بای‎ a specific ‏ای اس‎ ] ts usudly door too iq-ord-ser wodder. 

صفحه 72:
نقاط قوت و ضعف 6000 و ‎easy‏ راعشا ع بو ‎(ood yecrratzatve ta theory urd practice ‎Oork well wits Pevy tratctay testes ‎Cred yicbally best wodel, Do loc optical, vote ft curd uetiworks 4isodes relatively well to hich dicoecsivod dota ‎ood be ootoled‏ و له رای واه وبا لو( ‎eeceee eg ‎© Oocrrodiicca dota tite stages ced trees coo be used ‏عاجوا جه‎ GOO, testend oP Peature vevtors ‎© Opukusses © Deed to choose a “ood” keroel ‏اس‎ 

صفحه 73:
نتیجه گیری © 06 Pied opicvd leur ‏هو‎ ‎© Dkey pick the kyperplooe thot woxiwises the wary © Dke opted kyperphror tures cut to be a beer coxbicratica oF Upper veviors ‏و‎ Dke kere tick wokes GOOs ‏وا ساوسو‎ ‏مه‎ ۱ dereasicod spare Usicry heroel Pucrticas) thea there is wore choave thot to the trorasPorned spore he cusses wil be ‏اجره راما‎ «۵ 

صفحه 74:
: اسایر جنبه های 9660) ° Wow ‏هه‎ ‎© Ove ‏وت موی‎ the QP Pornutsticg 7 becowe wuli-chss © Dore oPteu, wuliple brary clossPiers ure cowhbiced © Ove ceo trot wuliple coe-versus-ll chssiPiers, or moswbice outiple ‏اسان وان منم‎ © AWow to itterpret ‏رک‎ Pucntiog value os ‏هار‎ + © ‏من مور تا بو( ره‎ the GOO ‏اه او و اه نوی‎ hota (voidatiza set) that is aot used Por trator, ‏و‎ Gowe GOO svPtwere (like ibsve) hue these Peutures ‏انا‎ 

صفحه 75:
ها دج اصن (0) ° COO is busicdly ‏وان مب و‎ تایه تاه صا ‎Ove coo choage the QP Porwutatice‏ و روهام © Ope vowwodly, the dota set is divided into tuo ports ۱ wed a separate GOO is ‏موی و لصو‎ way oP divisiva © Oudti-cliss clossiPivation is dour ‏عد اتاروم برط‎ the ‏اه خن نزن‎ the GOO chassiPiers © Daipriy nde © Cro ‏له رس‎ © ‏اي سوه لس‎ 

صفحه 76:
* لیستی از نرم افزار های مختلف را میتوانید در آدرس زیر بيابيد: © برخى نرم افزارها نظير (109)9600,| میتوانند بصورت چند دسته اى كار كنند. © نرم افزار «إزرا(!)500) در مراجع مختلفى بكار رفته است. ‎٩‏ چندین »ریاس در و/ك(1) براى 050000 معرفى شده اند. 

صفحه 77:
مراجع [1] b.E. Boser et a/. A training algorithm for optimal margin classifiers. Proceedings of the fifth annual workshop on computational learning theory 5 144-152, Pittsburgh, 1992. [2] |. Bottou et a/, Comparison of classifier methods: a case study in handwritten digit recognition. Proceedings of the 12th IAPR international conference on pattern recognition, vol. 2, pp. 77-82. [3] v. Vapnik. The nature of statistical learning theory. 2™¢ edition, Springer, 1999. 

ماشین بردار پشتیبان Instructor : Saeed Shiry 1 مقدمه SVM دسته ب ندیک ننده ایاستک ه جزو ش اخه Kernel Methodsدریادگ یریماشینمحسوبمیشود. ‏SVM در س ا ل 1992ت وسط Vapnikمع رفیش ده و ب ر است پ ایه statistical learning theoryب نا گ ردیده . شهرت SVMبخاطر موفقیت آن در تشخیص حروف دست نویس است که با شبکه های عصبی بدقت تنظیم شده برابری میکند %1.1 :خطا 2 مقدمه هدف این دسته الگوریتم ها تشخیص و متمایز کردن الگوهای پیچیده در داده هاست ( از طریق کالسترینگ ،دسته بندی، رنکینگ ،پاکسازی و غیره) مسایل مطرح: ‏ ‏ 3 الگوهای پیچیده را چگونه نمایش دهیم چگونه از مسئله overfittingپرهیز کنیم ایده اصلی با فرض اینکه دسته ها بصورت خطی جداپذیر باشند، ابرصفحه هائی با حداکثر حاشیه ( )maximum marginرا بدست می آورد که دسته ها را جدا کنند. در مسایلی که داده ها بصورت خطی جداپذیر نباشند داده ها به فضای با ابعاد بیشتر نگاشت پیدا میکنند تا بتوان آنها را در این فضای جدید بصورت خطی جدا نمود. 4 تعریف  Support Vector Machines are a system for efficiently training linear learning machines in kernelinduced feature spaces, while respecting the insights of generalisation theory and exploiting optimisation theory.  Cristianini & Shawe-Taylor (2000) 5 مسئله جداسازی خطی: ‏Linear Discrimination اگر دو دسته وجود داشته باشند که بصورت خطی از هم جداپذیر باشند ،بهترین جدا کننده این دو دسته چیست؟ الگوریتم های مختلفی از جمله پرسپترون میتوانند این جداسازی را انجام دهند. آیا همه این الگوریتمها بخوبی از عهده اینکار بر میآیند؟ ‏x0w = í + 1 ‏A+ ‏A6 ‏w ‏x0w = í à 1 ‏x0w = í ‏Separating Surface: Intuitions X X X X X X O X O X O O O O O O 7 Intuitions X X X X X X O X O X O O O O O O 8 Intuitions X X X X X X O X O X O O O O O O 9 Intuitions X X X X X X O X O X O O O O O O 10 A “Good” Separator X X X X X X O X O X O O O O O O 11 Noise in the Observations X X X X X X O X O X O O O O O O 12 Ruling Out Some Separators X X X X X X O X O X O O O O O O 13 Lots of Noise X X X X X X O X O X O O O O O O 14 Maximizing the Margin X X X X X X O X O X O O O O O O 15 ضرب داخلی ضرب داخلی را میتوان معیاری از تشابه دانست ‏a ‏ ‏b ‏ab  a b cos در حالت nبعدی میتوان آنرا بصورت زیر نمایش داد. ‏n ‏ ab ‏a,b  ‏i i 16 ‏i 1 ‏a,b Rn خط یا ابر صفحه جدا کننده ‏X2 ‏X1 ‏Class 1 ‏Class -1 هدف :پیدا کردن بهترین خط ( ابر صفحه) که دو دسته را از هم جدا کند .در حالت دو بعدی معادله این خط بصورت زیر است: ‏w1X1  w2 X2  b 0 در حالت nبعدی خواهیم داشت: 17 ‏T  ‏w .x  b 0 ‏n ‏wi.xi  b 0 ‏ ‏i ‏0 ایده SVMبرای جدا سازی دسته ها ‏ ‏ ‏ دو صفحه مرزی بسازید : دو صفحه مرزی موازی با صفحه دسته بندی رسم کرده و آندو را آنقدر از هم دور میکنیم که به داده ها برخورد کنند. صفحه دسته بندی که بیشترین فاصله را از صفحات مرزی داشته باشد، بهترین جدا کننده خواهد بود. ‏ ‏w.x  b 0 ‏Class -1 ‏Class 1 18 ‏ ‏w.x  b C ‏ ‏w.x  b   C حداکثر حاشیه بر طبق قضیه ای در تئوری یادگیری اگر مثالهای آموزشی بدرستی دسته بندی شده باشند ،از بین جداسازهای خطی ،آن جداسازی که حاشیه داده های آموزشی را حداکثر میکند خطای تعمیم را حداقل خواهد کرد. ‏ ‏w.x  b 0 ‏Class -1 ‏Class 1 19 ‏ ‏w.x  b C ‏ ‏w.x  b   C چرا حداکثر حاشیه؟ به نظر میرسد که مطمئن ترین راه باشد. تئوری هائی برمبنای VC dimensionوجود دارد که مفید بودن آنرا اثبات میکند. بطور تجربی این روش خیلی خوب جواب داده است. 20 بردار پشتیبان نزدیکترین داده های آموزشی به ابر صفحه های جدا کننده بردار پشتیبان نامیده میشوند ‏X2 ‏SV ‏SV ‏SV ‏X1 21 ‏Class 1 ‏Class -1 تعمیم و SVM در صورت استفاده مناسب از SVMاین الگوریتم قدرت تعمیم خوبی خواهد داشت: ‏ ‏ علیرغم داشتن ابعاد زیاد ( )high dimensionalityاز overfitting پرهیز میکند .این خاصیت ناشی از optimizationاین الگوریتم است فشرده سازی اطالعات: ‏ 22 بجای داده های آموزشی از بردارهای پشتیبان استفاده میکند. حل مسئله برای حالت دو بعدی ‏ نمونه های آموزشی ‏ تابع تصمیم گیری )f(x) = sign(<w,x> + b ‏w  n ‏b ابر صفحه <w, x> + b = 0 ‏w 1 x1 + w 2 x 2 … + w n xn + b = 0 میخواهیم مقادیر W, bرابگونه ای پیدا کنیم که: نمونه های آموزشی را بدقت دسته بندی کند ‏x  n }y  {-1, 1 ‏ ‏ ‏ ‏ 23 با این فرض که داده ها بصورت خطی جدا پذیر باشند حاشیه را حداکثر نماید Linear SVM Mathematically   Let training set {(xi, yi)}i=1..n, xiRd, yi  {-1, 1} be separated by a hyperplane with margin ρ. Then for each training example (xi, yi): wTxi + b ≤ - ρ/2 if yi  yi(wTxi + b) ≥ ρ/2 = -1 wTxi + b ≥ ρ/2 if yi = For 1 every support vector xs the above inequality is an equality. After rescaling w and b by ρ/2 in the equality, we obtain that distance between each xs and the hyperplane is  ys (wT xs  b) 1 r  w w Then the margin can be expressed through (rescaled) w and b as:  2r  2 w 24 حل مسئله برای حالت دو بعدی ‏f(x)>0 ‏f(x)<0 ‏f(x)=0 ‏X2 بردار wبر هر دو صفحه مثبت ومنفی عمود خواهد بود. ‏b ‏w ‏x ‏w ‏f (x) wx b ‏ ‏w ‏w ‏X1 ‏ ‏ 25 ‏b ‏w فاصله خط جداکننده از مبدا برا براست با فاصله نمونه ای مثل xاز خط جدا کننده برابر است با ‏f (x) wx b ‏ ‏w ‏w تعیین حاشیه بین خطوط جدا کننده Plus-plane = { x : w . x + b = +1 } Minus-plane = { x : w . x + b = -1 } Classify as.. -1 if w . x + b <= -1 +1 if w . x + b >= 1 26 محاسبه پهنای حاشیه ‏ ‏ ‏ 27 صفحه مثبت و منفی را بصورت زیر در نظر میگیریم: ‏ Plus-plane } = { x : w . x + b = +1 }  Minus-plane = { x : w . x + b = -1 بردار wبر صفحه مثبت ومنفی عمود خواهد بود. فرض کنید -Xنقطه ای در صفحه منفی بوده و +Xنزدیکترین نقطه در صفحه مثبت به -Xباشد. محاسبه پهنای حاشیه خطی که -Xرابه +Xوصل میکند بر هر دو صفحه عمود خواهد بود .لذا فاصله بین دو صفحه مضربی از Wخواهد بود. در اینصورت خواهیم داشت: ‏x+= x-+ λ w ‏for some value of λ. 28 محاسبه پهنای حاشیه میدانیم که: ‏w . x+ + b = +1 ‏ w . x- + b = -1 ‏ X+ = x- + λ w ‏ | x+ - x- | = M لذا میتوان Mرا برحسب Wو bمحاسبه کرد. 29 محاسبه پهنای حاشیه w . x+ + b = +1  w . x- + b = -1  X+ = x- + λ w  | x+ - x- | = M w.( x-+ λ w) + b = +1 w.x-+ λ w.w + b = +1 -1+ λ w.w = +1 λ=2/ w.w 30 محاسبه پهنای حاشیه 31 محدودیت اگر برای مثال دو بعدی فوق مقدار دسته ها را با 1و -1 مشخص کنیم داریم: ‏ <w,x > + b ≥ 1 for y=1 ‏i + b  -1 for y= -1 >  <w,x ‏i که میتوان آنرابصورت زیر نوشت ‏yi (<w,xi> + b) ≥ 1 for all i 32 ‏ جمع بندی حل مسئله ‏ ‏ در SVMبدنبال حل همزمان معادالت زیر هستیم: با داشتن مثالهای آموزشی ( )xi, yiکه }i=1,2,…N; yi{+1,-1 ‏Minimise ||w||2 ‏Subject to : yi (<w,xi> + b) ≥ 1 for all i ‏Note that ||w||2 = wTw ‏ 33 ‏ ‏ ‏ این یک مسئله quadratic programmingبا محدودیت هائی بصورت نامعادالت خطی است .روشهای شناخته شده ای برای چنین مسئله هائی بوجود آمده اند. Quadratic Programming 34 Recap of Constrained Optimization     Suppose we want to: minimize f(x) subject to g(x) = 0 A necessary condition for x0 to be a solution: : the Lagrange multiplier For multiple constraints gi(x) = 0, i=1, …, m, we need a Lagrange multiplier i for each of the constraints 35 Recap of Constrained Optimization   The case for inequality constraint gi(x)  0 is similar, except that the Lagrange multiplier i should be positive If x0 is a solution to the constrained optimization problem  There must exist i ≥0 for i=1, …, m such that x0 satisfy  The function want to set its gradient to 0 is also known as the Lagrangrian; we 36 راه حل معادله  Construct & minimise the Lagrangian N 1 2 L(w,b, )  ||w ||    i [ yi (wxi  b)  1] 2 i 1 wrt.constraint  i 0, i 1,...N  Take derivatives wrt. w and b, equate them to 0 L(w,b, ) w  w N  i yi xi 0  i 1 L(w,b, ) N   i yi 0 b i 1 KKT cond: i [ yi (wxi  b)  1] 0 parameters are expressed as a linear combination of training points  SVs will have non-zero i The Lagrange multipliers i are calledonly ‘dual variables’ Each training point has an associated dual variable. 37 راه حل معادله Class 2 8=0. 6 10=0 5=0 4=0 9=0 Class 1 7=0 2=0 1=0.8 6=1.4 3=0 38 The Dual Problem  If we substitute  Note that  This is a function of i only to Lagrangian , we have 39 The Dual Problem      The new objective function is in terms of i only It is known as the dual problem: if we know w, we know all i; if we know all i, we know w The original problem is known as the primal problem The objective function of the dual problem needs to be maximized! The dual problem is therefore: Properties of i when we introduce the Lagrange multipliers The result when we differentiate the original Lagrangian w.r.t. 40b The Dual Problem  This  w is a quadratic programming (QP) problem A global maximum of i can always be found can be recovered by 41 راه حل معادله    N So, w i1 i yi xi  iSV i yi xi Plug this back into the Lagrangian to obtain the dual formulation The resulting dual that is solved for  by using a QP solver:   maximise :W( )  1 N N   y y x x   i j i j i j i1 i 2 i, j 1 N subject to : i1 i yi 0,  i 0, i 1,...N  The b does not appear in the dual so it is determined separately from the initial constraints Data enters only in the form of dot products! 42 دسته بندی داده های جدید ‏ ‏ پس از آنکه مقادیر ( )**, bبا حل معادالت quadraticبر اساس داده های ورودی بدست آمد ،میتوان SVMرا برای دسته بندی نمونه های جدید بکار برد. اگر xیک نمونه جدید باشد ،دسته بندی آن بصورت زیر مشخص میشود: ‏sign[f(x, *, b*)], where ‏N *f (x, ,b ) w x  b i1 i* yi xi x  b* iSV i* yi xi x  b 43 ‏Data enters ‏only in the ‏form of dot !products * * * * ‏ ویژگی های راه حل    The solution of the SVM, i.e. of the quadratic programming problem with linear inequality constraints has the nice property that the data enters only in the form of dot products! Dot product (notation & memory refreshing): given x=(x1,x2,…xn) and y=(y1,y2,…yn), then the dot product of x and y is xy=(x1y1, x2y2,…, xnyn). This is nice because it allows us to make SVMs non-linear without complicating the algorithm 44 The Quadratic Programming Problem     Many approaches have been proposed  Loqo, cplex, etc. Most are “interior-point” methods  Start with an initial solution that can violate the constraints  Improve this solution by optimizing the objective function and/or reducing the amount of constraint violation For SVM, sequential minimal optimization (SMO) seems to be the most popular  A QP with two variables is trivial to solve  Each iteration of SMO picks a pair of ( , ) and solve the QP with these i j two variables; repeat until convergence In practice, we can just regard the QP solver as a “black-box” without bothering how it works 45 داده هائی که بصورت خطی جدا پذیر نیستند یک فرض بسیار قوی در SVMاین بود که داده ها بصورت خطی جداپذیر باشند .در حالیکه در عمل در بسیاری مواقع این فرض صحیح نیست. ‏ ‏ 46 + ‏ ‏ ‏ + ‏ + ++ + + افزودن متغیر های slack ‏ ‏ یک راه حل این است که اندکی کوتاه آمده و مقداری خطا در دسته بندی را بپذیریم! این کار با معرفی متغیر iانجام میشود که نشانگر تعداد نمونه هائی است که توسط تابع wTx+bغلط ارزیابی میشوند. ‏Class 2 ‏Class 1 47 افزودن متغیر های slack با معرفی متغیر ,i, i=1, 2, …, Nمحدودیت های قبلی ساده تر شده و رابطه ‏yi (<w,xi> + b) ≥1 بصورت زیر تغییر میکند: ‏yi (<w,xi> + b) ≥1- i , i ≥ 0 در حالت ایده آل همه این متغیر ها باید صفر باشند. 48  در اینصورت مسئله بهینه سازی تبدیل میشود به یافتن wبه نحوی که معادله زیر مینیمم شود: 1 w 2  C  i 2 2 ‏i ‏subject To ‏yi (wT xi  b) 1  i ,  i 0, i که در آن C > 0میباشد .جمله اضافه شدن سعی دارد تا حد امکان همه متغیرهای slackرا کوچک نماید. 49  رابطه دوگان در حالت جدید بصورت زیر خواهد بود. 1    i j yi yj xiT x j 2 i j ‏i  i  ‏find i that maximizes ‏N ‏i 1 i yi 0, 0  i C, i ‏subject to مقدار مناسب Cبر اساس داده های مسئله انتخاب میشود. 50 Soft Margin Hyperplane  If we minimize wi i, i can be computed by  i are “slack variables” in optimization    We want to minimize   Note that i=0 if there is no error for xi i is an upper bound of the number of errors C : tradeoff parameter between error and margin The optimization problem becomes 51 The Optimization Problem  The dual of this new constrained optimization problem is  w is recovered as  This is very similar to the optimization problem in the linear separable case, except that there is an upper bound C on i now Once again, a QP solver can be used to find i  52 مسئله جداسازی غیر خطی : یادگیری در فضای ویژگی میتوان با نگاشت داده به یک فضای ویژگی آنها را بصورت خطی جداپذیر نمود: 53 تبدل داده به فضای ویژگی ) ( ) ( ) (( ) ( )  ) (( )  ) ( ) (( ) ) (( )  ) (( ) ( )  ) ( ) ( ) ( ‏Feature space ‏ ‏ ‏ 54 ‏Note: feature space is of higher ‏dimension than the input space ‏in practice )(. ‏Input space انجام محاسبات در فضای ویژگی میتواند پرهزینه باشد برای اینکه ابعاد بیشتری دارد. در حالت کلی ابعاد این فضا بی نهایت است. برای غلبه بر این مشکل از kernel trickاستفاده میشود. مشکالت فضای ویژگی کار کردن با فضای ویژگی با ابعاد باال مشکل است عالوه بر مسئله باال رفتن هزینه محاسباتی ممکن است مشکل تعمیم نیز بواسطه curse of dimensionalityبوجود آید. 55 نگاشت غیر مستقیم به فضای ویژگی  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 56 کرنل  Transform x  (x)  The linear algorithm depends only on xx , hence i transformed algorithm depends only on (x)(xi)  Use kernel function K(xi,xj) such that K(xi,xj)= (x)(xi) 57 An Example for (.) and K(.,.)  Suppose (.) 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 (.) explicitly  This use of kernel function to avoid carrying out (.) explicitly is known as the kernel trick 58 :کرنل های نمونه m- thDegree polynomial : K (x, x') (1 (x, x'))m Radialbasis: K (x, x') exp( ||x  x'||2 / c) Neural network : K (x, x') tanh( k1 x, x' k2)  x12     (x)  2x1x2   2   x2    K (xi , x j ) (xi x j )2 59 مثال :کرنل چند جمله ای 60 Modification Due to Kernel Function  Change all inner products to kernel functions  For training, Original With kernel function 61 Modification Due to Kernel Function  For testing, the new data z is classified as class 1 if f0, and as class 2 if f <0 Original With kernel function 62 Modularity  Any kernel-based learning algorithm composed of two modules:      A general purpose learning machine A problem specific kernel function Any K-B algorithm can be fitted with any kernel Kernels themselves can be constructed in a modular way Great for software engineering (and for analysis) 63 ساخت کرنل ها مجموعه قوانین زیر در مورد کرنل ها صادق است: ‏ 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 به این ترتیب میتوان کرنل های پیچیده را از روی کرنل های ساده تر ساخت. 64 ‏ ‏ ‏ ‏ Example  Suppose we have 5 1D data points   We use the polynomial kernel of degree 2    x1=1, x2=2, x3=4, x4=5, x5=6, with 1, 2, 6 as class 1 and 4, 5 as class 2  y1=1, y2=1, y3=-1, y4=-1, y5=1 K(x,y) = (xy+1)2 C is set to 100 We first find i (i=1, …, 5) by 65 Example  By using a QP solver, we get  1=0, 2=2.5, 3=0, 4=7.333, 5=4.833  Note that the constraints are indeed satisfied The support vectors are {x2=2, x4=5, x5=6}   The discriminant function is  b is recovered by solving f(2)=1 or by f(5)=-1 or by f(6)=1, as x2 and x5 lie on the line and x 4 lies on the line All three give b=9  66 Example Value of discriminant function class 1 1 class 1 class 2 2 4 5 6 67 مثالی از کاربرد تشخیص حروف دست نویس ‏ 68 در اداره پست آمریکا با استفاده از این روش توانسته اند به خطائی در حدود %4برسند.  برای دسته بندیSVM مراحل استفاده از  Prepare the data matrix  Select the kernel function to use  Execute the training algorithm using a QP solver to obtain the i values  Unseen data can be classified using the i values and the support vectors 69 انتخاب تابع کرنل      . انتخاب تابع کرنل استSVM جدی ترین مسئله در روش : روشها و اصول متعددی برای این کار معرفی شده اسـت diffusion kernel, Fisher kernel, string kernel, … و تحقیقاتی نیز برای بدست آوردن ماتریس کرنل از روی داده های موجود در حال انجام است. در عمل In practice, a low degree polynomial kernel or RBF kernel with a reasonable width is a good initial try Note that SVM with RBF kernel is closely related to RBF neural networks, with the centers of the radial basis functions automatically chosen for SVM 70 SVM applications       SVMs were originally proposed by Boser, Guyon and Vapnik in 1992 and gained increasing popularity in late 1990s. SVMs are currently among the best performers for a number of classification tasks ranging from text to genomic data. SVMs can be applied to complex data types beyond feature vectors (e.g. graphs, sequences, relational data) by designing kernel functions for such data. SVM techniques have been extended to a number of tasks such as regression [Vapnik et al. ’97], principal component analysis [Schölkopf et al. ’99], etc. Most popular optimization algorithms for SVMs use decomposition to hillclimb over a subset of αi’s at a time, e.g. SMO [Platt ’99] and [Joachims ’99] Tuning SVMs remains a black art: selecting a specific kernel and parameters is usually done in a try-and-see manner. 71 SVM نقاط قوت و ضعف  Strengths         Training is relatively easy Good generalization in theory and practice Work well with few training instances Find globally best model, No local optimal, unlike in neural networks It scales relatively well to high dimensional data Tradeoff between classifier complexity and error can be controlled explicitly Non-traditional data like strings and trees can be used as input to SVM, instead of feature vectors Weaknesses  Need to choose a “good” kernel function. 72 نتیجه گیری  SVMs find optimal linear separator    They pick the hyperplane that maximises the margin The optimal hyperplane turns out to be a linear combination of support vectors The kernel trick makes SVMs non-linear learning algorithms  Transform nonlinear problems to higher dimensional space using kernel functions; then there is more chance that in the transformed space the classes will be linearly separable. 73 SVM سایر جنبه های  How to use SVM for multi-class classification?     How to interpret the SVM discriminant function value as probability?   One can change the QP formulation to become multi-class More often, multiple binary classifiers are combined One can train multiple one-versus-all classifiers, or combine multiple pairwise classifiers “intelligently” By performing logistic regression on the SVM output of a set of data (validation set) that is not used for training Some SVM software (like libsvm) have these features built-in 74 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 Error correcting code Directed acyclic graph 75 نرم افزار لیستی از نرم افزار های مختلف را میتوانید در آدرس زیر بیابید: ‏ http://www.kernel-machines.org/software.html برخی نرم افزارها نظیر LIBSVMمیتوانند بصورت چند دسته ای کار کنند. نرم افزار SVMLightدر مراجع مختلفی بکار رفته است. چندین toolboxدر Matlabبرای SVMمعرفی شده اند. 76 مراجع [1] b.E. Boser et al. A training algorithm for optimal margin classifiers. Proceedings of the fifth annual workshop on computational learning theory 5 144-152, Pittsburgh, 1992. [2] l. Bottou et al. Comparison of classifier methods: a case study in handwritten digit recognition. Proceedings of the 12th IAPR international conference on pattern recognition, vol. 2, pp. 77-82. [3] v. Vapnik. The nature of statistical learning theory. 2nd edition, Springer, 1999. 77