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

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

اسلاید 1: 1ماشین بردار پشتیبانInstructor : Saeed Shiry

اسلاید 2: 2مقدمهSVM دسته بندی کننده ای است که جزو شاخه Kernel Methods دریادگیری ماشین محسوب میشود. SVMدر سال 1992 توسط Vapnik معرفی شده و بر پایه statistical learning theory بنا گردیده است.شهرت SVM بخاطر موفقیت آن در تشخیص حروف دست نویس است که با شبکه های عصبی بدقت تنظیم شده برابری میکند: 1.1% خطا

اسلاید 3: 3مقدمههدف این دسته الگوریتم ها تشخیص و متمایز کردن الگوهای پیچیده در داده هاست ( از طریق کلاسترینگ، دسته بندی، رنکینگ، پاکسازی و غیره)مسایل مطرح: الگوهای پیچیده را چگونه نمایش دهیمچگونه از مسئله overfitting پرهیز کنیم

اسلاید 4: 4ایده اصلیبا فرض اینکه دسته ها بصورت خطی جداپذیر باشند، ابرصفحه هائی با حداکثر حاشیه (maximum margin) را بدست می آورد که دسته ها را جدا کنند.در مسایلی که داده ها بصورت خطی جداپذیر نباشند داده ها به فضای با ابعاد بیشتر نگاشت پیدا میکنند تا بتوان آنها را در این فضای جدید بصورت خطی جدا نمود.

اسلاید 5: 5تعریفSupport Vector Machines are a system for efficiently training linear learning machines in kernel-induced feature spaces, while respecting the insights of generalisation theory and exploiting optimisation theory.Cristianini & Shawe-Taylor (2000)

اسلاید 6: 6مسئله جداسازی خطی: Linear Discriminationاگر دو دسته وجود داشته باشند که بصورت خطی از هم جداپذیر باشند، بهترین جدا کننده این دو دسته چیست؟الگوریتم های مختلفی از جمله پرسپترون میتوانند این جداسازی را انجام دهند.آیا همه این الگوریتمها بخوبی از عهده اینکار بر میآیند؟Separating Surface:A+A-

اسلاید 7: 7IntuitionsXXOOOOOOXXXXXXOO

اسلاید 8: 8IntuitionsXXOOOOOOXXXXXXOO

اسلاید 9: 9IntuitionsXXOOOOOOXXXXXXOO

اسلاید 10: 10IntuitionsXXOOOOOOXXXXXXOO

اسلاید 11: 11A “Good” SeparatorXXOOOOOOXXXXXXOO

اسلاید 12: 12Noise in the ObservationsXXOOOOOOXXXXXXOO

اسلاید 13: 13Ruling Out Some SeparatorsXXOOOOOOXXXXXXOO

اسلاید 14: 14Lots of NoiseXXOOOOOOXXXXXXOO

اسلاید 15: 15Maximizing the MarginXXOOOOOOXXXXXXOO

اسلاید 16: 16ضرب داخلیضرب داخلی را میتوان معیاری از تشابه دانستدر حالت n بعدی میتوان آنرا بصورت زیر نمایش داد.qab

اسلاید 17: 17خط یا ابر صفحه جدا کنندههدف: پیدا کردن بهترین خط ( ابر صفحه) که دو دسته را از هم جدا کند. در حالت دو بعدی معادله این خط بصورت زیر است:در حالت n بعدی خواهیم داشت:Class 1Class -1X2X1

اسلاید 18: 18ایده SVM برای جدا سازی دسته هادو صفحه مرزی بسازید :دو صفحه مرزی موازی با صفحه دسته بندی رسم کرده و آندو را آنقدر از هم دور میکنیم که به داده ها برخورد کنند.صفحه دسته بندی که بیشترین فاصله را از صفحات مرزی داشته باشد، بهترین جدا کننده خواهد بود.Class 1Class -1

اسلاید 19: 19حداکثر حاشیهبر طبق قضیه ای در تئوری یادگیری اگر مثالهای آموزشی بدرستی دسته بندی شده باشند، از بین جداسازهای خطی، آن جداسازی که حاشیه داده های آموزشی را حداکثر میکند خطای تعمیم را حداقل خواهد کرد. Class 1Class -1

اسلاید 20: 20چرا حداکثر حاشیه؟به نظر میرسد که مطمئن ترین راه باشد.تئوری هائی برمبنای VC dimension وجود دارد که مفید بودن آنرا اثبات میکند.بطور تجربی این روش خیلی خوب جواب داده است.

اسلاید 21: 21بردار پشتیباننزدیکترین داده های آموزشی به ابر صفحه های جدا کننده بردار پشتیبان نامیده میشوندClass 1Class -1X2X1SVSVSV

اسلاید 22: 22تعمیم و SVMدر صورت استفاده مناسب از SVM این الگوریتم قدرت تعمیم خوبی خواهد داشت:علیرغم داشتن ابعاد زیاد (high dimensionality) از overfitting پرهیز میکند. این خاصیت ناشی از optimization این الگوریتم استفشرده سازی اطلاعات:بجای داده های آموزشی از بردارهای پشتیبان استفاده میکند.

اسلاید 23: 23حل مسئله برای حالت دو بعدینمونه های آموزشیx  ny  {-1, 1}تابع تصمیم گیریf(x) = sign(<w,x> + b)w  n b  ابر صفحه<w, x> + b = 0w1x1 + w2x2 … + wnxn + b = 0میخواهیم مقادیر W, bرابگونه ای پیدا کنیم که: نمونه های آموزشی را بدقت دسته بندی کندبا این فرض که داده ها بصورت خطی جدا پذیر باشندحاشیه را حداکثر نماید

اسلاید 24: 24Linear SVM MathematicallyLet 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):For 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 Then the margin can be expressed through (rescaled) w and b as:wTxi + b ≤ - ρ/2 if yi = -1wTxi + b ≥ ρ/2 if yi = 1yi(wTxi + b) ≥ ρ/2

اسلاید 25: 25حل مسئله برای حالت دو بعدیفاصله خط جداکننده از مبدا برا براست بافاصله نمونه ای مثل x از خط جدا کننده برابر است باX2X1f(x)=0f(x)>0f(x)<0wxبردار w بر هر دو صفحه مثبت ومنفی عمود خواهد بود.

اسلاید 26: 26تعیین حاشیه بین خطوط جدا کننده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

اسلاید 27: 27محاسبه پهنای حاشیهصفحه مثبت و منفی را بصورت زیر در نظر میگیریم:Plus-plane = { x : w . x + b = +1 }Minus-plane = { x : w . x + b = -1 }بردار w بر صفحه مثبت ومنفی عمود خواهد بود. فرض کنید X- نقطه ای در صفحه منفی بوده و X+ نزدیکترین نقطه در صفحه مثبت به X- باشد.

اسلاید 28: 28محاسبه پهنای حاشیهخطی که X- رابه X+ وصل میکند بر هر دو صفحه عمود خواهد بود. لذا فاصله بین دو صفحه مضربی ازW خواهد بود.در اینصورت خواهیم داشت:x+= x-+ λ w for some value of λ.

اسلاید 29: 29محاسبه پهنای حاشیهمیدانیم که: w . x+ + b = +1w . x- + b = -1X+= x-+ λ w| x+- x-| = Mلذا میتوان M را برحسب Wو b محاسبه کرد.

اسلاید 30: 30محاسبه پهنای حاشیهw . x+ + b = +1w . x- + b = -1X+= x-+ λ w| x+- x-| = Mw.( x-+ λ w) + b = +1w.x-+ λ w.w + b = +1-1+ λ w.w = +1 λ=2/ w.w

اسلاید 31: 31محاسبه پهنای حاشیه

اسلاید 32: 32محدودیتاگر برای مثال دو بعدی فوق مقدار دسته ها را با 1 و 1- مشخص کنیم داریم:<w,xi> + b ≥ 1 for y=1<w,xi> + b £ -1 for y= -1که میتوان آنرابصورت زیر نوشتyi (<w,xi> + b) ≥ 1 for all i

اسلاید 33: 33جمع بندی حل مسئلهدر SVM بدنبال حل همزمان معادلات زیر هستیم:با داشتن مثالهای آموزشی (xi, yi) که i=1,2,…N; yi{+1,-1}Minimise ||w||2Subject to : yi (<w,xi> + b) ≥ 1 for all iNote that ||w||2 = wTw این یک مسئله quadratic programming با محدودیت هائی بصورت نامعادلات خطی است. روشهای شناخته شده ای برای چنین مسئله هائی بوجود آمده اند.

اسلاید 34: 34Quadratic Programming

اسلاید 35: 35Recap of Constrained OptimizationSuppose we want to: minimize f(x) subject to g(x) = 0A necessary condition for x0 to be a solution: a: the Lagrange multiplierFor multiple constraints gi(x) = 0, i=1, …, m, we need a Lagrange multiplier ai for each of the constraints

اسلاید 36: 36Recap of Constrained OptimizationThe case for inequality constraint gi(x) £ 0 is similar, except that the Lagrange multiplier ai should be positiveIf x0 is a solution to the constrained optimization problemThere must exist ai ≥ 0 for i=1, …, m such that x0 satisfyThe function is also known as the Lagrangrian; we want to set its gradient to 0

اسلاید 37: 37راه حل معادلهConstruct & minimise the LagrangianTake derivatives wrt. w and b, equate them to 0The Lagrange multipliers ai are called ‘dual variables’Each training point has an associated dual variable. parameters are expressed as a linear combination of training pointsonly SVs will have non-zero ai

اسلاید 38: 38راه حل معادلهa6=1.4Class 1Class 2a1=0.8a2=0a3=0a4=0a5=0a7=0a8=0.6a9=0a10=0

اسلاید 39: 39The Dual ProblemIf we substitute to Lagrangian , we have Note that This is a function of ai only

اسلاید 40: 40The Dual ProblemProperties of ai when we introduce the Lagrange multipliersThe result when we differentiate the original Lagrangian w.r.t. bThe new objective function is in terms of ai onlyIt is known as the dual problem: if we know w, we know all ai; if we know all ai, we know wThe original problem is known as the primal problemThe objective function of the dual problem needs to be maximized!The dual problem is therefore:

اسلاید 41: 41The Dual ProblemThis is a quadratic programming (QP) problemA global maximum of ai can always be foundw can be recovered by

اسلاید 42: 42راه حل معادلهSo, Plug this back into the Lagrangian to obtain the dual formulationThe resulting dual that is solved for  by using a QP solver: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!

اسلاید 43: 43دسته بندی داده های جدیدپس از آنکه مقادیر (*, b*) با حل معادلات quadratic بر اساس داده های ورودی بدست آمد، میتوان SVM را برای دسته بندی نمونه های جدید بکار برد.اگر x یک نمونه جدید باشد، دسته بندی آن بصورت زیر مشخص میشود:sign[f(x, *, b*)], where Data enters only in the form of dot products!

اسلاید 44: 44ویژگی های راه حل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

اسلاید 45: 45The Quadratic Programming ProblemMany approaches have been proposedLoqo, cplex, etc. Most are “interior-point” methodsStart with an initial solution that can violate the constraintsImprove this solution by optimizing the objective function and/or reducing the amount of constraint violationFor SVM, sequential minimal optimization (SMO) seems to be the most popularA QP with two variables is trivial to solveEach iteration of SMO picks a pair of (ai,aj) and solve the QP with these two variables; repeat until convergenceIn practice, we can just regard the QP solver as a “black-box” without bothering how it works

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

اسلاید 47: 47افزودن متغیر های slack یک راه حل این است که اندکی کوتاه آمده و مقداری خطا در دسته بندی را بپذیریم!این کار با معرفی متغیر xi انجام میشود که نشانگر تعداد نمونه هائی است که توسط تابع wTx+b غلط ارزیابی میشوند.Class 1Class 2

اسلاید 48: 48افزودن متغیر های slackبا معرفی متغیرxi, i=1, 2, …, N, محدودیت های قبلی ساده تر شده و رابطه yi (<w,xi> + b) ≥1بصورت زیر تغییر میکند:yi (<w,xi> + b) ≥1- xi , xi ≥ 0در حالت ایده آل همه این متغیر ها باید صفر باشند.

اسلاید 49: 49در اینصورت مسئله بهینه سازی تبدیل میشود به یافتن w به نحوی که معادله زیر مینیمم شود:که در آن C > 0 میباشد. جمله اضافه شدن سعی دارد تا حد امکان همه متغیرهای slack را کوچک نماید.

اسلاید 50: 50رابطه دوگان در حالت جدید بصورت زیر خواهد بود.مقدار مناسب C بر اساس داده های مسئله انتخاب میشود.find ai that maximizes subject to

اسلاید 51: 51Soft Margin HyperplaneIf we minimize wi xi, xi can be computed byxi are “slack variables” in optimizationNote that xi=0 if there is no error for xixi is an upper bound of the number of errorsWe want to minimize C : tradeoff parameter between error and marginThe optimization problem becomes

اسلاید 52: 52The Optimization ProblemThe dual of this new constrained optimization problem isw is recovered asThis is very similar to the optimization problem in the linear separable case, except that there is an upper bound C on ai nowOnce again, a QP solver can be used to find ai

اسلاید 53: 53مسئله جداسازی غیر خطی : یادگیری در فضای ویژگیمیتوان با نگاشت داده به یک فضای ویژگی آنها را بصورت خطی جداپذیر نمود:

اسلاید 54: 54تبدل داده به فضای ویژگی انجام محاسبات در فضای ویژگی میتواند پرهزینه باشد برای اینکه ابعاد بیشتری دارد.در حالت کلی ابعاد این فضا بی نهایت است.برای غلبه بر این مشکل از kernel trick استفاده میشود.f( )f( )f( )f( )f( )f( )f( )f( )f(.)f( )f( )f( )f( )f( )f( )f( )f( )f( )f( )Feature spaceInput spaceNote: feature space is of higher dimension than the input space in practice

اسلاید 55: 55مشکلات فضای ویژگیکار کردن با فضای ویژگی با ابعاد بالا مشکل استعلاوه بر مسئله بالا رفتن هزینه محاسباتی ممکن است مشکل تعمیم نیز بواسطه curse of dimensionality بوجود آید.

اسلاید 56: 56نگاشت غیر مستقیم به فضای ویژگیWe will introduce Kernels:Solve the computational problem of working with many dimensionsCan make it possible to use infinite dimensionsefficiently in time / spaceOther advantages, both practical and conceptual

اسلاید 57: 57کرنلTransform x  (x)The linear algorithm depends only on xxi, hence transformed algorithm depends only on (x)(xi)Use kernel function K(xi,xj) such that K(xi,xj)= (x)(xi)

اسلاید 58: 58Suppose f(.) is given as followsAn inner product in the feature space isSo, if we define the kernel function as follows, there is no need to carry out f(.) explicitlyThis use of kernel function to avoid carrying out f(.) explicitly is known as the kernel trickAn Example for f(.) and K(.,.)

اسلاید 59: 59کرنل های نمونه:

اسلاید 60: 60مثال: کرنل چند جمله ای

اسلاید 61: 61Modification Due to Kernel FunctionChange all inner products to kernel functionsFor training,OriginalWith kernel function

اسلاید 62: 62Modification Due to Kernel FunctionFor testing, the new data z is classified as class 1 if f³0, and as class 2 if f <0OriginalWith kernel function

اسلاید 63: 63ModularityAny kernel-based learning algorithm composed of two modules:A general purpose learning machineA problem specific kernel functionAny K-B algorithm can be fitted with any kernelKernels themselves can be constructed in a modular wayGreat for software engineering (and for analysis)

اسلاید 64: 64ساخت کرنل هامجموعه قوانین زیر در مورد کرنل ها صادق است:If K, K’ are kernels, then:K+K’ is a kernelcK is a kernel, if c>0aK+bK’ is a kernel, for a,b >0Etc etc etc……به این ترتیب میتوان کرنل های پیچیده را از روی کرنل های ساده تر ساخت.

اسلاید 65: 65ExampleSuppose we have 5 1D data pointsx1=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=1We use the polynomial kernel of degree 2K(x,y) = (xy+1)2C is set to 100We first find ai (i=1, …, 5) by

اسلاید 66: 66Example By using a QP solver, we geta1=0, a2=2.5, a3=0, a4=7.333, a5=4.833Note that the constraints are indeed satisfiedThe support vectors are {x2=2, x4=5, x5=6}The discriminant function isb 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 x4 lies on the line All three give b=9

اسلاید 67: 67ExampleValue of discriminant function12456class 2class 1class 1

اسلاید 68: 68مثالی از کاربردتشخیص حروف دست نویسدر اداره پست آمریکا با استفاده از این روش توانسته اند به خطائی در حدود 4% برسند.

اسلاید 69: 69مراحل استفاده از SVM برای دسته بندیPrepare the data matrixSelect the kernel function to useExecute the training algorithm using a QP solver to obtain the i valuesUnseen data can be classified using the i values and the support vectors

اسلاید 70: 70 انتخاب تابع کرنلجدی ترین مسئله در روش 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 tryNote that SVM with RBF kernel is closely related to RBF neural networks, with the centers of the radial basis functions automatically chosen for SVM

اسلاید 71: 71SVM applicationsSVMs 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 hill-climb 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.

اسلاید 72: 72نقاط قوت و ضعف SVMStrengthsTraining is relatively easy Good generalization in theory and practiceWork well with few training instancesFind globally best model, No local optimal, unlike in neural networksIt scales relatively well to high dimensional dataTradeoff between classifier complexity and error can be controlled explicitlyNon-traditional data like strings and trees can be used as input to SVM, instead of feature vectorsWeaknessesNeed to choose a “good” kernel function.

اسلاید 73: 73نتیجه گیریSVMs find optimal linear separatorThey pick the hyperplane that maximises the marginThe optimal hyperplane turns out to be a linear combination of support vectorsThe kernel trick makes SVMs non-linear learning algorithmsTransform 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.

اسلاید 74: 74سایر جنبه های SVMHow to use SVM for multi-class classification?One can change the QP formulation to become multi-classMore often, multiple binary classifiers are combinedOne can train multiple one-versus-all classifiers, or combine multiple pairwise classifiers “intelligently”How to interpret the SVM discriminant function value as probability?By performing logistic regression on the SVM output of a set of data (validation set) that is not used for trainingSome SVM software (like libsvm) have these features built-in

اسلاید 75: 75Multi-class ClassificationSVM is basically a two-class classifierOne can change the QP formulation to allow multi-class classificationMore commonly, the data set is divided into two parts “intelligently” in different ways and a separate SVM is trained for each way of divisionMulti-class classification is done by combining the output of all the SVM classifiersMajority ruleError correcting codeDirected acyclic graph

اسلاید 76: 76نرم افزارلیستی از نرم افزار های مختلف را میتوانید در آدرس زیر بیابید:http://www.kernel-machines.org/software.htmlبرخی نرم افزارها نظیر LIBSVM میتوانند بصورت چند دسته ای کار کنند.نرم افزار SVMLight در مراجع مختلفی بکار رفته است.چندین toolbox در Matlab برای SVM معرفی شده اند.

اسلاید 77: 77مراجع[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.