{"id":251,"date":"2018-08-27T07:33:48","date_gmt":"2018-08-27T07:33:48","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=251"},"modified":"2018-08-27T08:18:36","modified_gmt":"2018-08-27T08:18:36","slug":"support-vector-machines-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/support-vector-machines-i\/","title":{"rendered":"Support Vector Machines i"},"content":{"raw":"<strong>Quadrant I \u2013 e-text<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will be discussing another popular machine learning technique \u2013 Support Vector Machinesin detail.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives:<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of this module are as follows:\r\n<ul>\r\n \t<li style=\"text-align: justify\">To understand the principles of Linear and Nonlinear SVM<\/li>\r\n \t<li style=\"text-align: justify\">To know the interpretation of Kernel Functions<\/li>\r\n \t<li style=\"text-align: justify\">To acquire knowledge about solving optimization problem<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>17.1 Introduction<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Support Vector Machines or SVMs as they are popularly called were proposed by Boser, Guyon and Vapnik in 1992 and gained increasing popularity in recent times. It is basically an algorithm for learning linear classifiers. Support Vector Machines is motivated by the idea of maximizing margins. Though basically SVMs are essentially linear, efficient extension to non-linear SVMs is possible through the use of kernels.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Support vector machines are based on three main ideas. We first need to define an optimal hyperplane in a computationally efficient way: that is we need to maximize margin. We then extend the above definition for non-linearly separable problems by having a penalty term for misclassifications. We also map data to high dimensional space where it is easier to classify with linear decision surfaces, in other words reformulate the problem so that data is mapped implicitly to this space.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.2 Linear Separators<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Binary classification can be viewed as the task of separating items into two classes in feature space (Figure 17.1). The line that separates the two classes<\/p>\r\n<img class=\"size-full wp-image-252 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-161.png\" alt=\"\" width=\"297\" height=\"194\" \/>\r\n<p style=\"text-align: justify\">is specified by the equation wTx+b where all items that fall in the space wTx+b&gt;0 are represented by red dots and all items that fall in the space wTx+b &lt;0 are represented by blue dots.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.2.1 Linear Classifier<\/strong>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-253 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162.png\" alt=\"\" width=\"568\" height=\"307\" \/>\r\n<p style=\"text-align: justify\">Figure 17.2 shows that more than one linear separator can be defined that separates two sets of examples. In this figure given input points x, they are processed by the function f(x,w,b), whose sign value decides the class of the item. Here the weight vector w can be defined as a weighted linear combination of the training examples. Different linear separators are defined based on different values of weight (w) or slope and different values of b or intercept (Figure 17.3).Lots of possible solutions for finding the separating plane exist but we need to find the optimal one according to some criterion of expected goodness.<\/p>\r\n<img class=\"size-full wp-image-254 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163.png\" alt=\"\" width=\"369\" height=\"285\" \/>\r\n\r\n<strong>17.3 Classification Margin<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us define the classification margin. The distance from example x<strong><em>i<\/em><\/strong> to the separator is given by<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-255 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-164.png\" alt=\"\" width=\"162\" height=\"79\" \/>\r\n<p style=\"text-align: justify\">The marginris shown in Figure 17.4 and is the distance between two of the closest data points or examples on either side of the separator.<\/p>\r\n<img class=\"size-full wp-image-256 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-165.png\" alt=\"\" width=\"282\" height=\"255\" \/>\r\n<p style=\"text-align: justify\">Examples closest to the hyperplane are <strong><em>support vectors<\/em><\/strong>. In other words, the margin\u03c1 of the separator is the distance between support vectors. Figure 17.5<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-257 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166.png\" alt=\"\" width=\"522\" height=\"329\" \/>\r\n<p style=\"text-align: justify\">shows the margin of the linear classifier which is defined as the width that the boundary or hyperplane between the two classes can be increased before hitting a data point.<\/p>\r\n<p style=\"text-align: justify\"><strong>17.3.1 Maximum Margin Classification<\/strong><\/p>\r\n<p style=\"text-align: justify\">Maximizing the margin is good according to intuition since this allows larger separation between the two sets of examples. Moreover maximizing the margin is also according to PAC( Probably Approximately Correct) theory. PAC theory states that any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be wrong. This maximization also implies that only support vectors matter; other training examples are ignorable.<\/p>\r\n<img class=\"size-full wp-image-258 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-167.png\" alt=\"\" width=\"222\" height=\"242\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">Support Vectors are those datapoints that the margin pushes up against. The maximum margin linear classifier is as the name suggests the linear classifier with the maximum margin.Support Vector Machine (SVM) finds an<span style=\"font-size: 1em\">optimalsolution that maximizes the distance between the hyperplane and the \u201cdifficult points\u201d close to decision boundary. The intuition is that if there are no points near the decision surface, then there are no very uncertain classification decisions.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">SVMs maximize the <\/span><strong style=\"font-size: 1em\"><em>margin<\/em><\/strong><span style=\"font-size: 1em\"> around the separating hyperplane.The decision function that is the function that separates the examples can now be fully specified by a subset of training samples, <\/span><strong style=\"font-size: 1em\"><em>the support vectors<\/em><\/strong><span style=\"font-size: 1em\">.This is the simplest kind of SVM (Called an LSVM) (Figure 17.7). Solving SVMs is a <\/span><strong style=\"font-size: 1em\"><em>quadratic programming <\/em><\/strong><span style=\"font-size: 1em\">problem. SVMs are considered as one of the most successful current text classification methods.Maximizing the margin is good according to intuition and PAC (Probably Approximately Correct<\/span><strong style=\"font-size: 1em\"><em>)<\/em><\/strong><span style=\"font-size: 1em\">theory. This implies that only support vectors are important; other training examples are ignorable and this implication works very well empirically.The maximum margin linear classifier is the linear classifier with the, um, maximum margin. This is the simplest kind of SVM (Called an LSVM).<\/span><\/p>\r\n\r\n<\/div>\r\n<img class=\"size-full wp-image-259 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168.png\" alt=\"\" width=\"549\" height=\"281\" \/>\r\n\r\n<strong>17.3.2 Theoretical Justification for Maximum Margins<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Vapnik has proved that t<strong><em>he class of optimal linear separators has VC<\/em><\/strong> (Vapnik\u2013 Chervonenkis) dimension <strong><em>h bounded by<\/em><\/strong><\/p>\r\n<img class=\"size-full wp-image-260 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-169.png\" alt=\"\" width=\"263\" height=\"83\" \/>\r\n<p style=\"text-align: justify\"><strong><em>where \u03c1 is the margin, D is the diameter of the smallest sphere that can enclose all of the training examples, and m<\/em><\/strong><strong><em>0<\/em><\/strong><strong><em>is the dimensionality.<\/em><\/strong>Intuitively, this implies that regardless of dimensionality <strong><em>m<\/em><\/strong><strong><em>0<\/em><\/strong>we can minimize the VC dimension by maximizing the margin <strong><em>\u03c1.<\/em><\/strong>Thus, complexity of the classifier is kept small regardless of dimensionality.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.3.3Linear SVMs Mathematically<\/strong>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-261 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170.png\" alt=\"\" width=\"402\" height=\"240\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us assume that the functional margin of each data item is at least 1, then the following two constraints is true for a training set {(<strong>x<\/strong><strong>i<\/strong>,<strong><em>y<\/em><\/strong><strong><em>i<\/em><\/strong>)}<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-262 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171.png\" alt=\"\" width=\"363\" height=\"121\" \/>\r\n<p style=\"text-align: justify\">For support vectors, the inequality becomes an equality Then, since each example\u2019s distance from the hyperplane is<\/p>\r\n<img class=\"size-full wp-image-263 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172.png\" alt=\"\" width=\"429\" height=\"180\" \/>\r\n<p style=\"text-align: justify\">Separated by a hyper-plane with margin \u03c1 we can rewrite the equation for each training example (xi, yi) as:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-264 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173.png\" alt=\"\" width=\"519\" height=\"67\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">For every support vector x<strong><em>s<\/em><\/strong> the above inequality is an equality. After rescaling w and <strong><em>b<\/em><\/strong> by <strong><em>\u03c1\/<\/em><\/strong>2, we obtain distance between each x<strong><em>s<\/em><\/strong> and the hyper plane as<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-265 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174.png\" alt=\"\" width=\"306\" height=\"86\" \/>\r\n<p style=\"text-align: justify\">The margin can be expressed through (rescaled) w as:<\/p>\r\n<img class=\"size-full wp-image-266 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175.png\" alt=\"\" width=\"540\" height=\"243\" \/>\r\n<p style=\"text-align: justify\">Using a better formulation (min <strong>w<\/strong>= max 1\/<strong>w<\/strong>), this can be reformulated as a minimization problem as follows:<\/p>\r\n<img class=\"size-full wp-image-267 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176.png\" alt=\"\" width=\"556\" height=\"246\" \/>\r\n<p style=\"text-align: justify\">This is now optimizing a <strong><em>quadratic<\/em><\/strong> function subject to <strong><em>linear<\/em><\/strong> constraints. Quadratic optimization problems are a well-known class of mathematical programming problem, and many algorithms exist for solving them. The solution involves constructing a <strong><em>dual problem<\/em><\/strong> where a <strong><em>Lagrange multiplier\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong> is associated with every constraint in the primary problem:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-268 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177.png\" alt=\"\" width=\"539\" height=\"137\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>17.4 Soft Margin Classification<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">What if the training set is not linearly separable or we have a dataset with noise (Figure 17.9)? So far we have assumed a hard margin that is we enforce the condition that all the data points be classified correctly and there is no training error. However in some cases the training set can be noisy. The answer is to use very powerful kernels which we will discuss later. However in the case of some noisy data or if the training data is not linearly separable, <strong><em>slack variables\u03be<\/em><\/strong><strong><em>i<\/em><\/strong> can be added to allow misclassification of difficult or noisy examples. In other words allow some errors and let some points be moved to where they belong, however at a cost (Figure 17.10). We will still try to minimize training set errors, and to place hyperplane \u201cfar\u201d from each class (large margin). We add slack variables\u03bei to allow misclassification of difficult or noisy examples, resulting in a soft margin. These types of SVMs are called C-SVMs.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-269 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178.png\" alt=\"\" width=\"259\" height=\"327\" \/>\r\n\r\n<img class=\"size-full wp-image-270 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179.png\" alt=\"\" width=\"429\" height=\"325\" \/>\r\n\r\n&nbsp;\r\n\r\nThe old formulation already discussed is:\r\n\r\n<img class=\"size-full wp-image-271 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180.png\" alt=\"\" width=\"612\" height=\"293\" \/>\r\n<p style=\"text-align: justify\">The new formulation incorporating slack variables:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-272 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181.png\" alt=\"\" width=\"552\" height=\"104\" \/>\r\n\r\n&nbsp;\r\n<div>\r\n<p style=\"text-align: justify\">Parameter <strong><em>C<\/em><\/strong> can be viewed as a way to control overfitting. In other words <strong><em>C<\/em><\/strong>is a tradeoff parameter between error and margin; and is usually chosen by the user. A large C means a higher penalty to errors.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">The Soft Margin Classification solution is similar to the dual problem of separable case except that we need additional Lagrange multipliers for slack variables:<\/span><\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-273 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182.png\" alt=\"\" width=\"573\" height=\"285\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>17.5 Linear SVMs: Summary<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The classifier is a <strong><em>separating hyperplane.<\/em><\/strong>Most \u201cimportant\u201d training points are support vectors which define the hyperplane.Quadratic optimization algorithms can identify training points x<strong><em>i<\/em><\/strong> with non-zero Lagrangian multipliers <strong><em>\u03b1<\/em><\/strong> <strong><em>i.<\/em><\/strong> Both in the dual formulation of the problem and in the solution training points appear only inside inner products:<\/p>\r\n<img class=\"size-full wp-image-274 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183.png\" alt=\"\" width=\"554\" height=\"123\" \/>\r\n\r\n<strong>17.6 Non-Linear SVMs<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Datasets that are linearly separable with some noise (Figure 17.11) was tackled using soft margins.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-275 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184.png\" alt=\"\" width=\"425\" height=\"104\" \/>\r\n<p style=\"text-align: justify\">But what are we going to do if the dataset is just too hard (Figure 17.12)?<\/p>\r\n<img class=\"size-full wp-image-276 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185.png\" alt=\"\" width=\"417\" height=\"102\" \/>\r\n<p style=\"text-align: justify\">To tackle these types of problems we map data to a higher-dimensional space.General idea: the original feature space can always be mapped to some higher-dimensional feature space where the training set is separable. We map our points with a mapping function f(x) to a space of sufficiently high dimension so that they are linearly separable by a hyper-plane. Given a dataset that is not linearly separable in \u211d N may be linearly separable in a higher-dimensional space \u211dM (where M &gt; N). Thus, if we have a transformation that transforms the dataset to a higher-dimensional space such that it becomes linearly separable in the higher dimensional space, then we can train a linear SVM to find a decision boundary that separates the classes in \u211dM. Projecting the decision boundary found back to the original space will yield a nonlinear decision boundary. Figure 17.13 shows the non-linear one dimensional dataset transformed to two dimensions. The figure shows that in two dimension the dataset is linearly separable.<\/p>\r\n<img class=\"size-full wp-image-277 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186.png\" alt=\"\" width=\"489\" height=\"374\" \/>\r\n\r\n<img class=\"size-full wp-image-278 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187.png\" alt=\"\" width=\"320\" height=\"208\" \/>\r\n<p style=\"text-align: justify\">Figure 17.14 shows the dataset in 2D that is not linearly separable being transformed into 3D space where it becomes linearly separable. The input space is the space where the points <strong>x<\/strong>i are located while the feature space is the space of f(<strong>x<\/strong>i) after transformation (Figure 17.15).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>17.7 The \u201cKernel Trick\u201d<\/strong><\/p>\r\n<p style=\"text-align: justify\">In general working in high dimensional feature space will be computationally expensive since while constructing the maximal margin hyperplane, we need to evaluate highdimensional inner products. Now the \u201cKernel Trick\u201d comes to the rescue.For many mappings from a low-dimensional space to a high-dimensional space, there is a simple operation on two vectors in the low-dimensional space that can be used to compute the scalar product of their two images in the high-dimensional space.<\/p>\r\n&nbsp;\r\n\r\n<em>K <\/em><strong>(<\/strong><em>x<\/em><em>a<\/em> <strong>,<\/strong><em> x<\/em><em>b<\/em> <strong>)<\/strong> = <em>f<\/em><strong>(<\/strong><em>x<\/em><em>a<\/em> <strong>).<\/strong><em>f<\/em><strong>(<\/strong><em>x<\/em><em>b<\/em> <strong>)<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">where we let the kernel do the work, while the f components calculate the scalar product as shown in Figure 17.16<\/p>\r\n<img class=\"size-full wp-image-279 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-188.png\" alt=\"\" width=\"252\" height=\"225\" \/>\r\n<p style=\"text-align: justify\">The linear classifier relies on inner product between vectors<\/p>\r\n<p style=\"text-align: justify\"><strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)=x<strong><em>i<\/em><\/strong>Tx<strong><em>j<\/em><\/strong><\/p>\r\n<p style=\"text-align: justify\">Every data point is mapped into high-dimensional space as<\/p>\r\n<p style=\"text-align: justify\">\u03a6: x\u2192 \u03c6(x),<\/p>\r\n<p style=\"text-align: justify\"><strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)= \u03c6(x<strong><em>i<\/em><\/strong>)T\u03c6(x<strong><em>j<\/em><\/strong>)<\/p>\r\n<p style=\"text-align: justify\">A <strong><em>kernel function<\/em><\/strong> is a function that is equivalent to an inner product in some feature space.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Therefore kernel function is defined as a function that corresponds to a dot product of two feature vectors in some expanded feature space:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-280 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189.png\" alt=\"\" width=\"494\" height=\"341\" \/>\r\n<p style=\"text-align: justify\">There is no need to know this mapping explicitly nor do we need to know the dimension of the new space, because we only use the dot product of feature vectors in both the training and test set<\/p>\r\n<img class=\"size-full wp-image-281 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190.png\" alt=\"\" width=\"462\" height=\"117\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Thus, a kernel function <strong><em>implicitly<\/em><\/strong> maps data to a high-dimensional space. In this example it maps the one dimensional data to a 2D dimensional space.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.7.1 Kernel Functions<\/strong>\r\n\r\n&nbsp;\r\n\r\nWhat Functions are Kernels?\r\n\r\n&nbsp;\r\n\r\nFor some functions <strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>) actually checking that that\r\n\r\n&nbsp;\r\n\r\n<strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)= \u03c6(x<strong><em>i<\/em><\/strong>)T\u03c6(x<strong><em>j<\/em><\/strong>) can be cumbersome.\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here the Mercer\u2019s theorem helps us. The Mercer\u2019s theorem states that <strong><em>every<\/em><\/strong> <strong><em>semi-positive definite symmetric function is a kernel.<\/em><\/strong>A function<strong><em> K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>) is a kernel (there exists a f(x) such that <strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x <strong><em>j<\/em><\/strong>)= f(x<strong><em>i<\/em><\/strong>)Tf(x<strong><em>j<\/em><\/strong>)<\/p>\r\n&nbsp;\r\n\r\n<strong>17.7.2 Examples of Kernel Functions<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Linear:<em>K<\/em><\/strong>(<strong>x<\/strong><strong><em>i<\/em><\/strong>,<strong>x<\/strong><strong><em>j<\/em><\/strong>)=<strong> x<\/strong><strong><em>i<\/em><\/strong><strong>T<\/strong><strong>x<\/strong><strong><em>j<\/em><\/strong>\r\n\r\n&nbsp;\r\n\r\nMapping \u03a6:\u00a0\u00a0\u00a0\u00a0 <strong>x\u2192 \u03c6<\/strong>(<strong>x<\/strong>), where<strong> \u03c6<\/strong>(<strong>x<\/strong>) is<strong> x <\/strong>itself\r\n\r\n&nbsp;\r\n\r\n<strong>Polynomial of power <em>p<\/em>:<em>K<\/em><\/strong>(<strong>x<\/strong><strong><em>i<\/em><\/strong>,<strong>x<\/strong><strong><em>j<\/em><\/strong>)= (1+<strong> x<\/strong><strong><em>i<\/em><\/strong><strong>T<\/strong><strong>x<\/strong><strong><em>j<\/em><\/strong>)<strong><em>p<\/em><\/strong>\r\n\r\n&nbsp;\r\n\r\nMapping \u03a6:\u00a0\u00a0\u00a0\u00a0 <strong>x\u2192 \u03c6<\/strong>(<strong>x<\/strong>), where<strong> \u03c6<\/strong>(<strong>x<\/strong>) has dimensions\r\n\r\n&nbsp;\r\n\r\n<strong>Gaussian (radial-basis function):<\/strong>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-282 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-191.png\" alt=\"\" width=\"188\" height=\"82\" \/>\r\n<p style=\"text-align: justify\">Mapping \u03a6: <strong>x\u2192 \u03c6<\/strong>( <strong>x<\/strong>), where <strong>\u03c6<\/strong>(<strong>x<\/strong>) is <strong><em>infinite-dimensional<\/em><\/strong>: every point is mapped to <strong><em>a function(a Gaussian)<\/em><\/strong><\/p>\r\n<p style=\"text-align: justify\">Higher-dimensional space still has <strong><em>intrinsic<\/em><\/strong> dimensionality <strong><em>d<\/em><\/strong> but linear separators in it correspond to <strong><em>non-linear<\/em><\/strong> separators in original space.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.7.3 Important Kernel Issues<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">One important question is which Kernel to use? This is still a open research question. It is one of the weaknesses of SVM. The next important question is how to verify that rising to higher dimension using a specific kernel will map the data to a space in which they are linearly separable. For most of the kernel functionswe do not know the corresponding mapping function f(x)and hence we do not know which dimension we transformed to. So even though rising to higher dimension increases the likelihood that they will be separable we can\u2019t guarantee that.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.8 Non-linear SVMs Mathematically<\/strong>\r\n\r\n&nbsp;\r\n\r\nSimilar to the non-linear case, the dual problem formulation is:\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-283 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192.png\" alt=\"\" width=\"402\" height=\"190\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nOptimization techniques for finding <strong><em>\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong><strong><em>\u2019<\/em><\/strong>s for non-linear SVMs remain the same.\r\n\r\n&nbsp;\r\n\r\n<strong>17.9 Properties of SVM<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li style=\"text-align: justify\">\u00a0Since only support vectors are used to specify the separating hyperplane there is sparseness of solution space when dealing with large data sets as only support vectors are used to specify the separating hyper-plane.<\/li>\r\n \t<li style=\"text-align: justify\">Due to the same reason it has the ability to handle large feature spaces-in other words the complexity does not depend on the dimensionality of the feature space.<\/li>\r\n \t<li style=\"text-align: justify\">Overfitting can be controlled by soft margin approach<\/li>\r\n \t<li style=\"text-align: justify\">There is a good math property: a simple convex optimization problem which is guaranteed to converge to a single global solution.<\/li>\r\n \t<li style=\"text-align: justify\">Feature Selection is automatic and is decided by support vectors.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In general, SVMs express learning as a mathematical program taking advantage of the rich theory in optimization. It is able to use the kernel trick to map indirectly to extremely high dimensional spaces. SVMs are extremely successful, robust, efficient, and versatile while there are good theoretical indications as to why they generalize well. Many tools are available that support SVMs.<\/p>\r\n&nbsp;\r\n\r\n<strong>17.10 SVM applications<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u2022 SVMs are currently among the best performers for a number of classification tasks ranging from text to genomic data.<\/p>\r\n<p style=\"text-align: justify\">\u2022 SVMs can be applied to complex data types beyond feature vectors (e.g. graphs, sequences, relational data) by designing kernel functions for such data.<\/p>\r\n<p style=\"text-align: justify\">\u2022 SVM techniques have been extended to a number of tasks such as regression, principal component analysis, etc.<\/p>\r\n<p style=\"text-align: justify\">\u2022 Most popular optimization algorithms for SVMs use <strong><em>decomposition<\/em><\/strong> to hill-climb over a subset of <strong><em>\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong><strong><em>\u2019<\/em><\/strong>s at a time, e.g. SMO<\/p>\r\n<p style=\"text-align: justify\">\u2022 Tuning SVMs remains a black art: selecting a specific kernel and parameters is usually done in a try-and-see manner. A method called<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Grid Search is a simple and systematic technique resembling exhaustive search that can be used for parameter estimation. We take exponentially increasing values in a particular range and find the set with minimum cross-validation error.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Explained the Maximum Margin Classification<\/li>\r\n \t<li>Described Linear and Non-linear SVMs<\/li>\r\n \t<li>Discussed about solving the optimization Problem<\/li>\r\n \t<li>Explained the Kernel Functions<\/li>\r\n \t<li>Listed SVM applications<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Weblinks<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">http:\/\/www.cs.columbia.edu\/~kathy\/cs4701\/documents\/jason_svm_tutorial.pdf<\/li>\r\n \t<li style=\"text-align: justify\">http:\/\/www.cis.temple.edu\/~latecki\/Courses\/AI-Fall10\/Lectures\/ch5SVM.ppt<\/li>\r\n \t<li style=\"text-align: justify\">http:\/\/www1.cs.columbia.edu\/~belhumeur\/courses\/biometrics\/2010\/svm.ppt<\/li>\r\n \t<li style=\"text-align: justify\">http:\/\/www.support-vector.net\/icml-tutorial.pdf<\/li>\r\n \t<li style=\"text-align: justify\">http:\/\/www.brainvoyager.com\/bvqx\/doc\/UsersGuide\/MVPA\/SupportVectorMachinesSVMs.html<\/li>\r\n \t<li style=\"text-align: justify\">cs.haifa.ac.il\/hagit\/courses\/seminars\/visionTopics\/...\/SVM_Lecture.<strong>ppt<\/strong><\/li>\r\n \t<li style=\"text-align: justify\">www.cs.toronto.edu\/~ruiyan\/csc411\/Tutorial11.<strong>ppt<\/strong><\/li>\r\n \t<li style=\"text-align: justify\">https:\/\/www.cs.toronto.edu\/~hinton\/csc2515\/<strong>not<\/strong>es\/lec10<strong>svm<\/strong>.<strong>ppt<\/strong><\/li>\r\n<\/ul>","rendered":"<p><strong>Quadrant I \u2013 e-text<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will be discussing another popular machine learning technique \u2013 Support Vector Machinesin detail.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of this module are as follows:<\/p>\n<ul>\n<li style=\"text-align: justify\">To understand the principles of Linear and Nonlinear SVM<\/li>\n<li style=\"text-align: justify\">To know the interpretation of Kernel Functions<\/li>\n<li style=\"text-align: justify\">To acquire knowledge about solving optimization problem<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>17.1 Introduction<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Support Vector Machines or SVMs as they are popularly called were proposed by Boser, Guyon and Vapnik in 1992 and gained increasing popularity in recent times. It is basically an algorithm for learning linear classifiers. Support Vector Machines is motivated by the idea of maximizing margins. Though basically SVMs are essentially linear, efficient extension to non-linear SVMs is possible through the use of kernels.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Support vector machines are based on three main ideas. We first need to define an optimal hyperplane in a computationally efficient way: that is we need to maximize margin. We then extend the above definition for non-linearly separable problems by having a penalty term for misclassifications. We also map data to high dimensional space where it is easier to classify with linear decision surfaces, in other words reformulate the problem so that data is mapped implicitly to this space.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.2 Linear Separators<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Binary classification can be viewed as the task of separating items into two classes in feature space (Figure 17.1). The line that separates the two classes<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-252 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-161.png\" alt=\"\" width=\"297\" height=\"194\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-161.png 297w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-161-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-161-225x147.png 225w\" sizes=\"auto, (max-width: 297px) 100vw, 297px\" \/><\/p>\n<p style=\"text-align: justify\">is specified by the equation wTx+b where all items that fall in the space wTx+b&gt;0 are represented by red dots and all items that fall in the space wTx+b &lt;0 are represented by blue dots.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.2.1 Linear Classifier<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-253 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162.png\" alt=\"\" width=\"568\" height=\"307\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162.png 568w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162-300x162.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162-65x35.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162-225x122.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-162-350x189.png 350w\" sizes=\"auto, (max-width: 568px) 100vw, 568px\" \/><\/p>\n<p style=\"text-align: justify\">Figure 17.2 shows that more than one linear separator can be defined that separates two sets of examples. In this figure given input points x, they are processed by the function f(x,w,b), whose sign value decides the class of the item. Here the weight vector w can be defined as a weighted linear combination of the training examples. Different linear separators are defined based on different values of weight (w) or slope and different values of b or intercept (Figure 17.3).Lots of possible solutions for finding the separating plane exist but we need to find the optimal one according to some criterion of expected goodness.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-254 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163.png\" alt=\"\" width=\"369\" height=\"285\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163.png 369w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163-300x232.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163-65x50.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163-225x174.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-163-350x270.png 350w\" sizes=\"auto, (max-width: 369px) 100vw, 369px\" \/><\/p>\n<p><strong>17.3 Classification Margin<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us define the classification margin. The distance from example x<strong><em>i<\/em><\/strong> to the separator is given by<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-255 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-164.png\" alt=\"\" width=\"162\" height=\"79\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-164.png 162w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-164-65x32.png 65w\" sizes=\"auto, (max-width: 162px) 100vw, 162px\" \/><\/p>\n<p style=\"text-align: justify\">The marginris shown in Figure 17.4 and is the distance between two of the closest data points or examples on either side of the separator.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-256 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-165.png\" alt=\"\" width=\"282\" height=\"255\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-165.png 282w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-165-65x59.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-165-225x203.png 225w\" sizes=\"auto, (max-width: 282px) 100vw, 282px\" \/><\/p>\n<p style=\"text-align: justify\">Examples closest to the hyperplane are <strong><em>support vectors<\/em><\/strong>. In other words, the margin\u03c1 of the separator is the distance between support vectors. Figure 17.5<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-257 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166.png\" alt=\"\" width=\"522\" height=\"329\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166.png 522w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166-300x189.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166-225x142.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-166-350x221.png 350w\" sizes=\"auto, (max-width: 522px) 100vw, 522px\" \/><\/p>\n<p style=\"text-align: justify\">shows the margin of the linear classifier which is defined as the width that the boundary or hyperplane between the two classes can be increased before hitting a data point.<\/p>\n<p style=\"text-align: justify\"><strong>17.3.1 Maximum Margin Classification<\/strong><\/p>\n<p style=\"text-align: justify\">Maximizing the margin is good according to intuition since this allows larger separation between the two sets of examples. Moreover maximizing the margin is also according to PAC( Probably Approximately Correct) theory. PAC theory states that any hypothesis that is consistent with a sufficiently large set of training examples is unlikely to be wrong. This maximization also implies that only support vectors matter; other training examples are ignorable.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-258 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-167.png\" alt=\"\" width=\"222\" height=\"242\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-167.png 222w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-167-65x71.png 65w\" sizes=\"auto, (max-width: 222px) 100vw, 222px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\">Support Vectors are those datapoints that the margin pushes up against. The maximum margin linear classifier is as the name suggests the linear classifier with the maximum margin.Support Vector Machine (SVM) finds an<span style=\"font-size: 1em\">optimalsolution that maximizes the distance between the hyperplane and the \u201cdifficult points\u201d close to decision boundary. The intuition is that if there are no points near the decision surface, then there are no very uncertain classification decisions.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">SVMs maximize the <\/span><strong style=\"font-size: 1em\"><em>margin<\/em><\/strong><span style=\"font-size: 1em\"> around the separating hyperplane.The decision function that is the function that separates the examples can now be fully specified by a subset of training samples, <\/span><strong style=\"font-size: 1em\"><em>the support vectors<\/em><\/strong><span style=\"font-size: 1em\">.This is the simplest kind of SVM (Called an LSVM) (Figure 17.7). Solving SVMs is a <\/span><strong style=\"font-size: 1em\"><em>quadratic programming <\/em><\/strong><span style=\"font-size: 1em\">problem. SVMs are considered as one of the most successful current text classification methods.Maximizing the margin is good according to intuition and PAC (Probably Approximately Correct<\/span><strong style=\"font-size: 1em\"><em>)<\/em><\/strong><span style=\"font-size: 1em\">theory. This implies that only support vectors are important; other training examples are ignorable and this implication works very well empirically.The maximum margin linear classifier is the linear classifier with the, um, maximum margin. This is the simplest kind of SVM (Called an LSVM).<\/span><\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-259 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168.png\" alt=\"\" width=\"549\" height=\"281\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168.png 549w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168-300x154.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168-225x115.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-168-350x179.png 350w\" sizes=\"auto, (max-width: 549px) 100vw, 549px\" \/><\/p>\n<p><strong>17.3.2 Theoretical Justification for Maximum Margins<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Vapnik has proved that t<strong><em>he class of optimal linear separators has VC<\/em><\/strong> (Vapnik\u2013 Chervonenkis) dimension <strong><em>h bounded by<\/em><\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-260 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-169.png\" alt=\"\" width=\"263\" height=\"83\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-169.png 263w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-169-65x21.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-169-225x71.png 225w\" sizes=\"auto, (max-width: 263px) 100vw, 263px\" \/><\/p>\n<p style=\"text-align: justify\"><strong><em>where \u03c1 is the margin, D is the diameter of the smallest sphere that can enclose all of the training examples, and m<\/em><\/strong><strong><em>0<\/em><\/strong><strong><em>is the dimensionality.<\/em><\/strong>Intuitively, this implies that regardless of dimensionality <strong><em>m<\/em><\/strong><strong><em>0<\/em><\/strong>we can minimize the VC dimension by maximizing the margin <strong><em>\u03c1.<\/em><\/strong>Thus, complexity of the classifier is kept small regardless of dimensionality.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.3.3Linear SVMs Mathematically<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-261 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170.png\" alt=\"\" width=\"402\" height=\"240\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170.png 402w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170-300x179.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170-65x39.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170-225x134.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-170-350x209.png 350w\" sizes=\"auto, (max-width: 402px) 100vw, 402px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us assume that the functional margin of each data item is at least 1, then the following two constraints is true for a training set {(<strong>x<\/strong><strong>i<\/strong>,<strong><em>y<\/em><\/strong><strong><em>i<\/em><\/strong>)}<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-262 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171.png\" alt=\"\" width=\"363\" height=\"121\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171.png 363w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171-300x100.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171-65x22.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171-225x75.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-171-350x117.png 350w\" sizes=\"auto, (max-width: 363px) 100vw, 363px\" \/><\/p>\n<p style=\"text-align: justify\">For support vectors, the inequality becomes an equality Then, since each example\u2019s distance from the hyperplane is<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-263 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172.png\" alt=\"\" width=\"429\" height=\"180\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172.png 429w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172-300x126.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172-65x27.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172-225x94.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-172-350x147.png 350w\" sizes=\"auto, (max-width: 429px) 100vw, 429px\" \/><\/p>\n<p style=\"text-align: justify\">Separated by a hyper-plane with margin \u03c1 we can rewrite the equation for each training example (xi, yi) as:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-264 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173.png\" alt=\"\" width=\"519\" height=\"67\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173.png 519w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173-300x39.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173-65x8.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173-225x29.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-173-350x45.png 350w\" sizes=\"auto, (max-width: 519px) 100vw, 519px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For every support vector x<strong><em>s<\/em><\/strong> the above inequality is an equality. After rescaling w and <strong><em>b<\/em><\/strong> by <strong><em>\u03c1\/<\/em><\/strong>2, we obtain distance between each x<strong><em>s<\/em><\/strong> and the hyper plane as<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-265 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174.png\" alt=\"\" width=\"306\" height=\"86\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174.png 306w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174-300x84.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174-65x18.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-174-225x63.png 225w\" sizes=\"auto, (max-width: 306px) 100vw, 306px\" \/><\/p>\n<p style=\"text-align: justify\">The margin can be expressed through (rescaled) w as:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-266 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175.png\" alt=\"\" width=\"540\" height=\"243\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175.png 540w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175-300x135.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175-225x101.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-175-350x158.png 350w\" sizes=\"auto, (max-width: 540px) 100vw, 540px\" \/><\/p>\n<p style=\"text-align: justify\">Using a better formulation (min <strong>w<\/strong>= max 1\/<strong>w<\/strong>), this can be reformulated as a minimization problem as follows:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-267 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176.png\" alt=\"\" width=\"556\" height=\"246\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176.png 556w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176-300x133.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176-225x100.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-176-350x155.png 350w\" sizes=\"auto, (max-width: 556px) 100vw, 556px\" \/><\/p>\n<p style=\"text-align: justify\">This is now optimizing a <strong><em>quadratic<\/em><\/strong> function subject to <strong><em>linear<\/em><\/strong> constraints. Quadratic optimization problems are a well-known class of mathematical programming problem, and many algorithms exist for solving them. The solution involves constructing a <strong><em>dual problem<\/em><\/strong> where a <strong><em>Lagrange multiplier\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong> is associated with every constraint in the primary problem:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-268 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177.png\" alt=\"\" width=\"539\" height=\"137\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177.png 539w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177-300x76.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177-65x17.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177-225x57.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-177-350x89.png 350w\" sizes=\"auto, (max-width: 539px) 100vw, 539px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.4 Soft Margin Classification<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">What if the training set is not linearly separable or we have a dataset with noise (Figure 17.9)? So far we have assumed a hard margin that is we enforce the condition that all the data points be classified correctly and there is no training error. However in some cases the training set can be noisy. The answer is to use very powerful kernels which we will discuss later. However in the case of some noisy data or if the training data is not linearly separable, <strong><em>slack variables\u03be<\/em><\/strong><strong><em>i<\/em><\/strong> can be added to allow misclassification of difficult or noisy examples. In other words allow some errors and let some points be moved to where they belong, however at a cost (Figure 17.10). We will still try to minimize training set errors, and to place hyperplane \u201cfar\u201d from each class (large margin). We add slack variables\u03bei to allow misclassification of difficult or noisy examples, resulting in a soft margin. These types of SVMs are called C-SVMs.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-269 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178.png\" alt=\"\" width=\"259\" height=\"327\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178.png 259w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178-238x300.png 238w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178-65x82.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-178-225x284.png 225w\" sizes=\"auto, (max-width: 259px) 100vw, 259px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-270 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179.png\" alt=\"\" width=\"429\" height=\"325\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179.png 429w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179-300x227.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179-65x49.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179-225x170.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-179-350x265.png 350w\" sizes=\"auto, (max-width: 429px) 100vw, 429px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>The old formulation already discussed is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-271 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180.png\" alt=\"\" width=\"612\" height=\"293\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180.png 612w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180-300x144.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180-225x108.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-180-350x168.png 350w\" sizes=\"auto, (max-width: 612px) 100vw, 612px\" \/><\/p>\n<p style=\"text-align: justify\">The new formulation incorporating slack variables:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-272 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181.png\" alt=\"\" width=\"552\" height=\"104\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181.png 552w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181-300x57.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181-65x12.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181-225x42.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-181-350x66.png 350w\" sizes=\"auto, (max-width: 552px) 100vw, 552px\" \/><\/p>\n<p>&nbsp;<\/p>\n<div>\n<p style=\"text-align: justify\">Parameter <strong><em>C<\/em><\/strong> can be viewed as a way to control overfitting. In other words <strong><em>C<\/em><\/strong>is a tradeoff parameter between error and margin; and is usually chosen by the user. A large C means a higher penalty to errors.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: initial;font-size: 1em\">The Soft Margin Classification solution is similar to the dual problem of separable case except that we need additional Lagrange multipliers for slack variables:<\/span><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-273 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182.png\" alt=\"\" width=\"573\" height=\"285\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182.png 573w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-182-350x174.png 350w\" sizes=\"auto, (max-width: 573px) 100vw, 573px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.5 Linear SVMs: Summary<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The classifier is a <strong><em>separating hyperplane.<\/em><\/strong>Most \u201cimportant\u201d training points are support vectors which define the hyperplane.Quadratic optimization algorithms can identify training points x<strong><em>i<\/em><\/strong> with non-zero Lagrangian multipliers <strong><em>\u03b1<\/em><\/strong> <strong><em>i.<\/em><\/strong> Both in the dual formulation of the problem and in the solution training points appear only inside inner products:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-274 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183.png\" alt=\"\" width=\"554\" height=\"123\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183.png 554w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183-300x67.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183-65x14.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183-225x50.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-183-350x78.png 350w\" sizes=\"auto, (max-width: 554px) 100vw, 554px\" \/><\/p>\n<p><strong>17.6 Non-Linear SVMs<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Datasets that are linearly separable with some noise (Figure 17.11) was tackled using soft margins.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-275 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184.png\" alt=\"\" width=\"425\" height=\"104\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184.png 425w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184-300x73.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184-65x16.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184-225x55.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-184-350x86.png 350w\" sizes=\"auto, (max-width: 425px) 100vw, 425px\" \/><\/p>\n<p style=\"text-align: justify\">But what are we going to do if the dataset is just too hard (Figure 17.12)?<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-276 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185.png\" alt=\"\" width=\"417\" height=\"102\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185.png 417w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185-300x73.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185-65x16.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185-225x55.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-185-350x86.png 350w\" sizes=\"auto, (max-width: 417px) 100vw, 417px\" \/><\/p>\n<p style=\"text-align: justify\">To tackle these types of problems we map data to a higher-dimensional space.General idea: the original feature space can always be mapped to some higher-dimensional feature space where the training set is separable. We map our points with a mapping function f(x) to a space of sufficiently high dimension so that they are linearly separable by a hyper-plane. Given a dataset that is not linearly separable in \u211d N may be linearly separable in a higher-dimensional space \u211dM (where M &gt; N). Thus, if we have a transformation that transforms the dataset to a higher-dimensional space such that it becomes linearly separable in the higher dimensional space, then we can train a linear SVM to find a decision boundary that separates the classes in \u211dM. Projecting the decision boundary found back to the original space will yield a nonlinear decision boundary. Figure 17.13 shows the non-linear one dimensional dataset transformed to two dimensions. The figure shows that in two dimension the dataset is linearly separable.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-277 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186.png\" alt=\"\" width=\"489\" height=\"374\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186.png 489w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186-300x229.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186-65x50.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186-225x172.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-186-350x268.png 350w\" sizes=\"auto, (max-width: 489px) 100vw, 489px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-278 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187.png\" alt=\"\" width=\"320\" height=\"208\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187.png 320w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187-300x195.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-187-225x146.png 225w\" sizes=\"auto, (max-width: 320px) 100vw, 320px\" \/><\/p>\n<p style=\"text-align: justify\">Figure 17.14 shows the dataset in 2D that is not linearly separable being transformed into 3D space where it becomes linearly separable. The input space is the space where the points <strong>x<\/strong>i are located while the feature space is the space of f(<strong>x<\/strong>i) after transformation (Figure 17.15).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>17.7 The \u201cKernel Trick\u201d<\/strong><\/p>\n<p style=\"text-align: justify\">In general working in high dimensional feature space will be computationally expensive since while constructing the maximal margin hyperplane, we need to evaluate highdimensional inner products. Now the \u201cKernel Trick\u201d comes to the rescue.For many mappings from a low-dimensional space to a high-dimensional space, there is a simple operation on two vectors in the low-dimensional space that can be used to compute the scalar product of their two images in the high-dimensional space.<\/p>\n<p>&nbsp;<\/p>\n<p><em>K <\/em><strong>(<\/strong><em>x<\/em><em>a<\/em> <strong>,<\/strong><em> x<\/em><em>b<\/em> <strong>)<\/strong> = <em>f<\/em><strong>(<\/strong><em>x<\/em><em>a<\/em> <strong>).<\/strong><em>f<\/em><strong>(<\/strong><em>x<\/em><em>b<\/em> <strong>)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">where we let the kernel do the work, while the f components calculate the scalar product as shown in Figure 17.16<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-279 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-188.png\" alt=\"\" width=\"252\" height=\"225\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-188.png 252w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-188-65x58.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-188-225x201.png 225w\" sizes=\"auto, (max-width: 252px) 100vw, 252px\" \/><\/p>\n<p style=\"text-align: justify\">The linear classifier relies on inner product between vectors<\/p>\n<p style=\"text-align: justify\"><strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)=x<strong><em>i<\/em><\/strong>Tx<strong><em>j<\/em><\/strong><\/p>\n<p style=\"text-align: justify\">Every data point is mapped into high-dimensional space as<\/p>\n<p style=\"text-align: justify\">\u03a6: x\u2192 \u03c6(x),<\/p>\n<p style=\"text-align: justify\"><strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)= \u03c6(x<strong><em>i<\/em><\/strong>)T\u03c6(x<strong><em>j<\/em><\/strong>)<\/p>\n<p style=\"text-align: justify\">A <strong><em>kernel function<\/em><\/strong> is a function that is equivalent to an inner product in some feature space.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Therefore kernel function is defined as a function that corresponds to a dot product of two feature vectors in some expanded feature space:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-280 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189.png\" alt=\"\" width=\"494\" height=\"341\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189.png 494w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189-300x207.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189-225x155.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-189-350x242.png 350w\" sizes=\"auto, (max-width: 494px) 100vw, 494px\" \/><\/p>\n<p style=\"text-align: justify\">There is no need to know this mapping explicitly nor do we need to know the dimension of the new space, because we only use the dot product of feature vectors in both the training and test set<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-281 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190.png\" alt=\"\" width=\"462\" height=\"117\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190.png 462w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190-300x76.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190-65x16.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190-225x57.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-190-350x89.png 350w\" sizes=\"auto, (max-width: 462px) 100vw, 462px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Thus, a kernel function <strong><em>implicitly<\/em><\/strong> maps data to a high-dimensional space. In this example it maps the one dimensional data to a 2D dimensional space.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.7.1 Kernel Functions<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>What Functions are Kernels?<\/p>\n<p>&nbsp;<\/p>\n<p>For some functions <strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>) actually checking that that<\/p>\n<p>&nbsp;<\/p>\n<p><strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>)= \u03c6(x<strong><em>i<\/em><\/strong>)T\u03c6(x<strong><em>j<\/em><\/strong>) can be cumbersome.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here the Mercer\u2019s theorem helps us. The Mercer\u2019s theorem states that <strong><em>every<\/em><\/strong> <strong><em>semi-positive definite symmetric function is a kernel.<\/em><\/strong>A function<strong><em> K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x<strong><em>j<\/em><\/strong>) is a kernel (there exists a f(x) such that <strong><em>K<\/em><\/strong>(x<strong><em>i<\/em><\/strong>,x <strong><em>j<\/em><\/strong>)= f(x<strong><em>i<\/em><\/strong>)Tf(x<strong><em>j<\/em><\/strong>)<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.7.2 Examples of Kernel Functions<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Linear:<em>K<\/em><\/strong>(<strong>x<\/strong><strong><em>i<\/em><\/strong>,<strong>x<\/strong><strong><em>j<\/em><\/strong>)=<strong> x<\/strong><strong><em>i<\/em><\/strong><strong>T<\/strong><strong>x<\/strong><strong><em>j<\/em><\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Mapping \u03a6:\u00a0\u00a0\u00a0\u00a0 <strong>x\u2192 \u03c6<\/strong>(<strong>x<\/strong>), where<strong> \u03c6<\/strong>(<strong>x<\/strong>) is<strong> x <\/strong>itself<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Polynomial of power <em>p<\/em>:<em>K<\/em><\/strong>(<strong>x<\/strong><strong><em>i<\/em><\/strong>,<strong>x<\/strong><strong><em>j<\/em><\/strong>)= (1+<strong> x<\/strong><strong><em>i<\/em><\/strong><strong>T<\/strong><strong>x<\/strong><strong><em>j<\/em><\/strong>)<strong><em>p<\/em><\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Mapping \u03a6:\u00a0\u00a0\u00a0\u00a0 <strong>x\u2192 \u03c6<\/strong>(<strong>x<\/strong>), where<strong> \u03c6<\/strong>(<strong>x<\/strong>) has dimensions<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Gaussian (radial-basis function):<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-282 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-191.png\" alt=\"\" width=\"188\" height=\"82\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-191.png 188w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-191-65x28.png 65w\" sizes=\"auto, (max-width: 188px) 100vw, 188px\" \/><\/p>\n<p style=\"text-align: justify\">Mapping \u03a6: <strong>x\u2192 \u03c6<\/strong>( <strong>x<\/strong>), where <strong>\u03c6<\/strong>(<strong>x<\/strong>) is <strong><em>infinite-dimensional<\/em><\/strong>: every point is mapped to <strong><em>a function(a Gaussian)<\/em><\/strong><\/p>\n<p style=\"text-align: justify\">Higher-dimensional space still has <strong><em>intrinsic<\/em><\/strong> dimensionality <strong><em>d<\/em><\/strong> but linear separators in it correspond to <strong><em>non-linear<\/em><\/strong> separators in original space.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.7.3 Important Kernel Issues<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">One important question is which Kernel to use? This is still a open research question. It is one of the weaknesses of SVM. The next important question is how to verify that rising to higher dimension using a specific kernel will map the data to a space in which they are linearly separable. For most of the kernel functionswe do not know the corresponding mapping function f(x)and hence we do not know which dimension we transformed to. So even though rising to higher dimension increases the likelihood that they will be separable we can\u2019t guarantee that.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.8 Non-linear SVMs Mathematically<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Similar to the non-linear case, the dual problem formulation is:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-283 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192.png\" alt=\"\" width=\"402\" height=\"190\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192.png 402w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192-300x142.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192-225x106.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-192-350x165.png 350w\" sizes=\"auto, (max-width: 402px) 100vw, 402px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p>Optimization techniques for finding <strong><em>\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong><strong><em>\u2019<\/em><\/strong>s for non-linear SVMs remain the same.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.9 Properties of SVM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: justify\">\u00a0Since only support vectors are used to specify the separating hyperplane there is sparseness of solution space when dealing with large data sets as only support vectors are used to specify the separating hyper-plane.<\/li>\n<li style=\"text-align: justify\">Due to the same reason it has the ability to handle large feature spaces-in other words the complexity does not depend on the dimensionality of the feature space.<\/li>\n<li style=\"text-align: justify\">Overfitting can be controlled by soft margin approach<\/li>\n<li style=\"text-align: justify\">There is a good math property: a simple convex optimization problem which is guaranteed to converge to a single global solution.<\/li>\n<li style=\"text-align: justify\">Feature Selection is automatic and is decided by support vectors.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In general, SVMs express learning as a mathematical program taking advantage of the rich theory in optimization. It is able to use the kernel trick to map indirectly to extremely high dimensional spaces. SVMs are extremely successful, robust, efficient, and versatile while there are good theoretical indications as to why they generalize well. Many tools are available that support SVMs.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>17.10 SVM applications<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u2022 SVMs are currently among the best performers for a number of classification tasks ranging from text to genomic data.<\/p>\n<p style=\"text-align: justify\">\u2022 SVMs can be applied to complex data types beyond feature vectors (e.g. graphs, sequences, relational data) by designing kernel functions for such data.<\/p>\n<p style=\"text-align: justify\">\u2022 SVM techniques have been extended to a number of tasks such as regression, principal component analysis, etc.<\/p>\n<p style=\"text-align: justify\">\u2022 Most popular optimization algorithms for SVMs use <strong><em>decomposition<\/em><\/strong> to hill-climb over a subset of <strong><em>\u03b1<\/em><\/strong><strong><em>i<\/em><\/strong><strong><em>\u2019<\/em><\/strong>s at a time, e.g. SMO<\/p>\n<p style=\"text-align: justify\">\u2022 Tuning SVMs remains a black art: selecting a specific kernel and parameters is usually done in a try-and-see manner. A method called<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Grid Search is a simple and systematic technique resembling exhaustive search that can be used for parameter estimation. We take exponentially increasing values in a particular range and find the set with minimum cross-validation error.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Explained the Maximum Margin Classification<\/li>\n<li>Described Linear and Non-linear SVMs<\/li>\n<li>Discussed about solving the optimization Problem<\/li>\n<li>Explained the Kernel Functions<\/li>\n<li>Listed SVM applications<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Weblinks<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">http:\/\/www.cs.columbia.edu\/~kathy\/cs4701\/documents\/jason_svm_tutorial.pdf<\/li>\n<li style=\"text-align: justify\">http:\/\/www.cis.temple.edu\/~latecki\/Courses\/AI-Fall10\/Lectures\/ch5SVM.ppt<\/li>\n<li style=\"text-align: justify\">http:\/\/www1.cs.columbia.edu\/~belhumeur\/courses\/biometrics\/2010\/svm.ppt<\/li>\n<li style=\"text-align: justify\">http:\/\/www.support-vector.net\/icml-tutorial.pdf<\/li>\n<li style=\"text-align: justify\">http:\/\/www.brainvoyager.com\/bvqx\/doc\/UsersGuide\/MVPA\/SupportVectorMachinesSVMs.html<\/li>\n<li style=\"text-align: justify\">cs.haifa.ac.il\/hagit\/courses\/seminars\/visionTopics\/&#8230;\/SVM_Lecture.<strong>ppt<\/strong><\/li>\n<li style=\"text-align: justify\">www.cs.toronto.edu\/~ruiyan\/csc411\/Tutorial11.<strong>ppt<\/strong><\/li>\n<li style=\"text-align: justify\">https:\/\/www.cs.toronto.edu\/~hinton\/csc2515\/<strong>not<\/strong>es\/lec10<strong>svm<\/strong>.<strong>ppt<\/strong><\/li>\n<\/ul>\n","protected":false},"author":3,"menu_order":16,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-251","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/251","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":7,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/251\/revisions"}],"predecessor-version":[{"id":290,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/251\/revisions\/290"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/251\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/media?parent=251"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapter-type?post=251"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/contributor?post=251"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/license?post=251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}