{"id":291,"date":"2018-08-27T08:56:13","date_gmt":"2018-08-27T08:56:13","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=291"},"modified":"2019-01-02T06:50:54","modified_gmt":"2019-01-02T06:50:54","slug":"support-vector-machines-ii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/support-vector-machines-ii\/","title":{"rendered":"Support Vector Machines-II"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/mH71Xra3J44\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n&nbsp;\r\n\r\n&nbsp;\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 more details about support vector machine, the basics of which we have already discussed in the last module.<\/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 concept margins of SVM<\/li>\r\n \t<li style=\"text-align: justify\">To learn more about soft margin<\/li>\r\n \t<li style=\"text-align: justify\">To classify multiple classes using SVM<\/li>\r\n \t<li style=\"text-align: justify\">To understand some applications of SVM<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>18.1 Introduction<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">SVM has roots in statistical learning and is considered one of the most important discoveries in machine learning since it also works well for high dimensional data. Most importantly it represents the decision boundary using a subset of training examples called support vectors. It is based on the concept of maximal margin hyper planes. Margin of a classifier is defined as the minimum distance to any example and in SVM the decision boundary which maximizes the margin is chosen<\/p>\r\n<img class=\"size-full wp-image-292 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193.png\" alt=\"\" width=\"362\" height=\"238\" \/>\r\n<p style=\"text-align: justify\">In this module we will discuss more in detail about soft margin, the use of SVM to solve multi-class problems and finally some applications of SVM.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.2 Soft Margin<\/strong>\r\n\r\n&nbsp;\r\n\r\nConsider a two class classification problem that uses a linear model\r\n\r\n&nbsp;\r\n\r\ny(x) = wT(x) + b\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">followed by a threshold function. Assume that training data are linearly separable. As we have already discussed there are multiple hyper planes that separate the data points. There are many possibilities for such hyperplanes. The task is to choose the optimal separating hyperplane. There are distance of (d++d-) where d+ is the shortest distance of a positive example from the hyper plane and d- is the shortest distance of a negative example from the hyper plane.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-293 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194.png\" alt=\"\" width=\"373\" height=\"279\" \/>\r\n<p style=\"text-align: justify\">Now if the problem is not linearly separable then we need to introduce slack variables and we need to minimize:<\/p>\r\n<img class=\"size-full wp-image-294 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195.png\" alt=\"\" width=\"527\" height=\"247\" \/>\r\n\r\n<strong>18.2.1 What is Soft Margin?<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The SVM must not result in too many misclassifications. Therefore we introduce soft margin where a user specified parameter can control roughly, how many examples are allowed to violate the separating hyper plane and how far across the plane the examples can be considered. Setting this parameter is a tradeoff where we still want to try to achieve a large margin with respect to the correctly classified examples. Hence, the soft margin parameter specifies a trade-off between hyperplane violations and the size of the margin.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Maximum margin allows SVM to select among multiple candidate hyper planes. Soft margin accepts some misclassifications of the training examples. A soft margin can be obtained by adding a constant factor to the kernel function output, defining a priori, an upper bound on the size of the training set weights.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.2.2 Linear, Soft-Margin SVMs<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Soft \u2013Margin SVM tries to maintain slack variables x<em>i<\/em> to zero while maximizing margin. It does not minimize the <em>number<\/em> of misclassifications but the sum of distances from the margin hyper planes. In the case of soft margin, we allow \u201cerror\u201d \u03bei in classification. We use \u201cslack\u201d variables \u03be1 , \u03be2 \u2026\u2026.. \u03ben (one for each sample) (Figure 18.3).<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-295 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196.png\" alt=\"\" width=\"388\" height=\"318\" \/>\r\n<p style=\"text-align: justify\">\u03bei Is the deviation error from ideal place for sample i: If 0&lt; \u03bei &lt; 1 then sample i is on the right side of the hyperplane but within the region of the margin. If \u03bei &gt; 1 then sample i is on the wrong side of the hyper plane.<\/p>\r\n&nbsp;\r\n\r\nThe primal optimization problem now can be explained. We change the constraints to\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-296 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197.png\" alt=\"\" width=\"316\" height=\"51\" \/>\r\n\r\nInstead of\r\n\r\n<img class=\"size-full wp-image-297 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198.png\" alt=\"\" width=\"533\" height=\"219\" \/>\r\n<p style=\"text-align: justify\">C&gt;0 is a constant. It is a kind of penalty on the term \u00a0. It is a trade off between the margin and the training error. It is a way to control overfitting along with the maximum margin approach.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.2.3 The \u201cC\u201d Problem<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u201cC\u201d plays a major role in controlling over fitting (Figure 18.4). A larger value of C means that less number of training samples are not in ideal position. But smaller margin affects performance and a large enough value of C may lead to over fitting that is a complex classifier that fits only the training set. This means less training error that affects the classification performance positively. A smaller value of C means that more training samples are not in ideal position. A small C may lead to under fitting. This means more training error that affects<\/p>\r\n<img class=\"size-full wp-image-298 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199.png\" alt=\"\" width=\"490\" height=\"309\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">the Classification Performance negatively. From the figure you can see that the more complex the model is (shown by blue line) the less is the minimum training error (shown by the green line) that is we have good classification performance but only for the given training samples. Now the dotted line shows the bound on the test error, so we need to choose a value of C that gives minimum testing error.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.2.4 Soft vs Hard Margin SVMs<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The robustness of soft and hard margin SVMs is shown in Figure 18.5.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-299 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200.png\" alt=\"\" width=\"444\" height=\"227\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>SVMs 18.2.4.1 Hard Margin SVM<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Considering the objective function discussed in section 18.2.2 we have an extra term in our objective function that is equal to the sum of the slack variables \u03bei\u2019s. Our aim is to minimize the objective function and hence we need to keep the \u03bei values small resulting in a hard margin and overfitting. Remember that the \u03be term is multiplied by C which indicates that as C increases we care less about the size of the margin, and more about keeping the \u03bei\u2019s small. Thus, the value of C trades between how large of a margin we would prefer, as opposed to how many of the training set examples violate this margin (and by how much).<\/p>\r\n<img class=\"size-full wp-image-300 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201.png\" alt=\"\" width=\"527\" height=\"331\" \/>\r\n\r\n<strong>Soft Margin SVM<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Soft margins allow errors in classification. Objective function is still valid, but constraints need to be relaxed to tackle the non-linear separable case, so the linear separator is modified so that it does not satisfy all the constraints. In other words it allows softening of the constraints and results in under fitting (Figure 18.6).<\/p>\r\n&nbsp;\r\n\r\n<strong>18.2<\/strong>\u00a0<strong>Classification with SVMs<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The classifier is modelled as a separating hyper plane. The most \u201cimportant\u201d training points are support vectors and they define the hyper plane. When we need to classify a given data point x using SVMs, we can score its projection normal to the hyper plane:<\/p>\r\n&nbsp;\r\n\r\n<strong>w<\/strong><strong>T<\/strong><strong>x <\/strong>+ b = \u03a3\u03b1iyi<strong>x<\/strong><strong>i<\/strong><strong>T<\/strong><strong>x + <\/strong>b\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We can decide the class based on where the example lies with respect to the hyper plane. Depending on whether the score is &lt; or &gt; we can decide the class. We can also set a confidence threshold t in order to control the overfitting issue. When the score &gt; t: we say the example belongs to the class and when score &lt; -t we say the example does not belong to the class.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.3.1 Recipe and Model selection procedure:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In most of the real-world applications of SVM we combine what we learned about the kernel trick and the soft margin and use them together:<\/p>\r\n<img class=\"size-full wp-image-301 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202.png\" alt=\"\" width=\"525\" height=\"122\" \/>\r\n\r\n&nbsp;\r\n\r\nWe solve for\u00a0 \u03b1\u00a0 using a Quadratic Programming software.\r\n\r\n<img class=\"size-full wp-image-302 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203.png\" alt=\"\" width=\"581\" height=\"49\" \/>\r\n\r\nTo find \u201cb\u201d we take any 0&lt; \u03b1i&lt;C and solve\r\n\r\n<img class=\"size-full wp-image-303 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204.png\" alt=\"\" width=\"536\" height=\"142\" \/>\r\n\r\nThe Classification function will be:\r\n\r\n<img class=\"size-full wp-image-304 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205.png\" alt=\"\" width=\"386\" height=\"98\" \/>\r\n\r\n<strong>18.3.2 Model selection procedure<\/strong>\r\n\r\n&nbsp;\r\n\r\nWe have to decide which Kernel function and \u201cC\u201d value to use.\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us assume that the Gaussian radial basis or a low degree polynomial kernel is used. We start checking which set of parameters C or \u03c3 (the standard deviation) if we choose Gaussian radial basis are the most appropriate by using K-Fold Cross-Validation. The steps of this cross-validation are to first randomly divide all the available training examples into <em>K<\/em> equal-sized subsets. Then we use all but one subset to train the SVM with the chosen parameters. We then use the held out subset to measure classification error. We repeat Steps 2 and 3 for each subset. We then average the results to get an estimate of the generalization error of the SVM classifier.The SVM is tested using this procedure for various parameter settings. In the end, the model with the smallest generalization error is adopted. Then we train our SVM classifier using these parameters over the whole training set.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.4 Multi Class SVM for <\/strong><strong>more than two classes<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">There are two basic approaches to solve <em>q<\/em>-class problems (q&gt;2 ) with SVMs.The first approach we will discuss is the One versus Others approach.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.4.1 One vs. Others<\/strong>:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This approach works by constructing a \u201cregular\u201d SVM\u00a0\u00a0\u00a0\u00a0\u00a0 <em>\u03c9<\/em><em>i<\/em>\u00a0\u00a0\u00a0\u00a0 for each class <em>i<\/em> that separates that class from all the other classes (class \u201c i\u201d positive and \u201cnot i\u201d negative). Then we check the output of each of the q SVM classifiers for our input and choose the class i where the corresponding SVM has the maximum output.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.4.2 Pairwise (one vs one):<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Here we construct a binary SVM for each pair of classes (so we construct q(q-1)\/2 SVMs) as shown in Figure 18.7. Then we use \u201cmax-wins\u201d voting strategy: we test each SVM on the input and each time an SVM chooses a certain class we add vote to that class. Then we choose the class with highest number of votes.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-305 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206.png\" alt=\"\" width=\"333\" height=\"231\" \/>\r\n<p style=\"text-align: justify\">Both the methods mentioned above give in average comparable accuracy results. However the second method is relatively slower than the first method. Sometimes for certain application one method is preferable over the other. More advanced methods to improve pairwise comparison includes using decision graphs to determine the class selected in a similar manner to knockout tournaments. There are several other strategies that can be used for selecting the final classification based on the output of the binary SVMs.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.4.3 Basis of Multi-Label Classification<\/strong>\r\n\r\n<img class=\"size-full wp-image-306 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207.png\" alt=\"\" width=\"599\" height=\"298\" \/>\r\n<p style=\"text-align: justify\">The basis of multi-label classification could be whole-part where an element may belong to both the whole and the component. This perspective is common for parent-child relationship where we add \u201cOther\u201d category, and do binary classification to distinguish the child from the other category. Since the classification boundary is non-linear, kernel methods may be more effective. The basis of multi-label classification can also be shared concepts (Figure 18.8).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">When the basis of the multi-label classification is shared concepts, training can be conducted in the following ways:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Mode-S \u2013 We label the multi-label data with the class to which the data most likely belonged, using some perhaps subjective criterion.<\/p>\r\n<p style=\"text-align: justify\">Mode-N \u2013In this case we consider the multi-label data as a new class separate from all the other classes<\/p>\r\n<p style=\"text-align: justify\">Mode-X \u2013 Here we use the multi-label data more than once, using each example as a positive example of each of the classes to which it belongs. This means that a training sample can belong to more than one class<\/p>\r\n<p style=\"text-align: justify\">The testing for the share concepts can be carried out as follows:<\/p>\r\n<p style=\"text-align: justify\">P-cut - Label input testing data by all of the classes corresponding to positive SVM scores. If no scores are positive, label that data to the class with top score.<\/p>\r\n<p style=\"text-align: justify\">S-cut -Train a threshold for each class by cross validation, and label input testing data by all of the classes for which scores of the input data were higher than the threshold..<\/p>\r\n<p style=\"text-align: justify\">R-cut -For any given test instance, always assign it <em>r<\/em> labels according to the descending confidence scores. Here <em>r<\/em> can be learned from training data.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>18.4.4 Evaluation Criteria<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we have already discussed previously F1 score combines precision and recall into one measure.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-307 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208.png\" alt=\"\" width=\"511\" height=\"280\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">Here as we know p is precision and r is the recall, and TP is true positive, FP is false positive and FN is false negative. The above measures are used for one class at a time.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">Now we are going to discuss how to evaluate multi-label classification. There are many parameters that are used to evaluate multi-label classification performance. When we have more than one class we need to combine multiple performance measures into one quantity. There are basically two methods of combining namely micro-averaging and macro-averaging. In micro-averaging where we collect decisions for all classes, compute a contingency table and then evaluate. Macro-averaging is where we compute performance for each class, then average the value. With the above basis we outline the evaluation measure of combining performance measures.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">Here we use n to define the number of classes. The first method is Micro-F1 which measures the overall classification performance.<\/span><\/p>\r\n\r\n<\/div>\r\n<img class=\"size-full wp-image-308 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209.png\" alt=\"\" width=\"315\" height=\"106\" \/>\r\n<p style=\"text-align: justify\">The second method is Macro-F1 which measures the classification accuracy on the category level. This reflects the classifier\u2019s capability of dealing with rare categories<\/p>\r\n<img class=\"size-full wp-image-309 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210.png\" alt=\"\" width=\"353\" height=\"83\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>18.5 SVM Applications<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">SVM has been successfully used to solve many real-world problems. Some of the applications include text categorization, image classification, bioinformatics (protein classification, cancer classification), hand-written character recognition, etc..<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>18.5.1 Application 1: Cancer Classification<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The SRCBT dataset can be used to illustrate the application. This is a high dimensional data set where the number of samples (patients) is &gt; 1000 and the number of features n &gt; 100. In such examples sometimes the samples are imbalanced with less number of positive samples. Many irrelevant features may be present where we need to perform feature selection. In the linear case, wi2 gives the ranking of dim i. However, SVM is sensitive to noisy (mis-labeled ) data.<\/p>\r\n&nbsp;\r\n\r\n<strong>18.5.2 Application 2: Text Categorization<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us take up the classification of natural text (or hypertext) documents into a fixed number of predefined categories based on their content. There are many uses for this task such as email filtering, web searching, sorting documents by topic, etc. A document can be assigned to more than one category, viewed as a series of binary classification problems, one for each category. In this application, the representation of text is an important aspect. Normally vector space model (aka bag-of-words representation) used by information retrieval is used. Typical features are term frequency, and inverse document frequency where inverse term frequency is used to give less weightage to terms that occur in all classes and hence does not contribute to the classification<\/p>\r\n<img class=\"size-full wp-image-310 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211.png\" alt=\"\" width=\"326\" height=\"77\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In this case a document is represented by a vector indexed by a pre-fixed set or dictionary of terms. The values of an entry can be binary or weights<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u03c6i(<em>x<\/em>)=tfi log(idfi) \/ k<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">For documents, removal of stops words and stemming is carried out as a pre-processing step. In order to account for varying length documents, normalization is carried out. Therefore can be represented Doc x =&gt; \u03c6(<em>x<\/em>). The distance between two documents is \u03c6(<em>x<\/em>)\u00b7\u03c6(<em>z)<\/em> where <em>K<\/em>(<em>x,z<\/em>) = \u03c6(<em>x<\/em>)\u00b7\u03c6(<em>z<\/em>) is a valid kernel. SVM can be used with <em>K<\/em>(<em>x,z<\/em>) for discrimination.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Why should we use SVM for text categorization? It is a typical multi-class multi-label classification problem. Documents are represented in such a way that it results in high dimensional input space, has few irrelevant features (dense concept) and the document vectors are sparse. In general text categorization problems are linearly separable. SVM, with some additional heuristic, has been regarded as one of the best classification scheme for text data, based on many benchmark evaluations.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>18.5.3 Application 3: Facial Expression Recognition<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">For this application we refer to the work discussed in the paper \u201cFacial Expression Recognition Using Support Vector Machines by Philipp Michel and Rana El Kaliouby\u201d. Three basic problems a facial expression analysis approach needs to deal with are face detection in a still image or image sequence where we assume a full frontal view of the face. The data from facial expression is extracted using an automatic tracker that extracts the position of facial features from the video stream or an image as the case may be. For each expression, a vector of feature displacements is calculated by taking the Euclidean distance between feature locations in a neutral state of the face and a \u201cpeak\u201d frame representative of the expression. We use the SVM method to construct the classifier and the vectors of feature displacements for the previous stage as our input. A set of 10 examples for each basic emotion (in still images) was used for training, followed by classification of 15 unseen examples per emotion. Libsvm was used as the underlying SVM classifier. At first they used the standard SVM classification using linear kernel and they got 78% accuracy. Then with subsequent improvements including selection of a kernel function (they chose RBF) and the right \u201cC\u201d customized to the training data, the recognition accuracy boosted up to 87.9%.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-311 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212.png\" alt=\"\" width=\"578\" height=\"300\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>18.6 Advantages of SVM<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The Kernel maps to a very-high dimensional space. In general, the search space has a unique minimum. The training that needs to be carried out is extremely efficient and similarly classification is extremely efficient. The two choices that are to be made are about the Kernel function and the cost. In typical domains, very good accuracy can be achieved. It is generally an extremely robust method.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>18.7 Weakness of SVM<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">However in spite of many advantages SVM has some disadvantages. It is sensitive to noise where a relatively small number of mislabeled examples can dramatically decrease the performance. In general it is a binary classification mechanism where only two classes are considered. It is expensive in terms of both memory and computational time, especially for multiclass problems. The selection of the kernel function and the right value for the \u201cTrade-off\u201d parameter \u201cC\u201d is not a straightforward issue.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>18.8 Software: Popular implementations<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">SVM is a technique that has many implementations available for use. One such implementation is SVM<\/span><em style=\"font-size: 1em\">light<\/em><span style=\"font-size: 1em\">: <\/span><a style=\"font-size: 1em\" href=\"http:\/\/svmlight.joachims.org\/\">http:\/\/svmlight.joachims.org\/ <\/a><span style=\"font-size: 1em\">. This implementation is by Joachims . It is the most widely used SVM classification and regression package. It is distributed as a C++ source and binaries for Linux, Windows, Cygwin, and Solaris. The kernels provided are polynomial, radial basis function, and sigmoid (tanh).<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The next software is LibSVM <\/span><a style=\"font-size: 1em\" href=\"http:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvm\/\">: http:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvm\/ .<\/a><span style=\"font-size: 1em\"> LIBSVM (Library for Support Vector Machines), is developed by Chang and Lin and is also a widely used software developed in C++ and Java. It supports multi-class classification, weighted SVM for unbalanced data, cross-validation and automatic model selection. It has interfaces for Python, R, Splus, MATLAB, Perl, Ruby, and LabVIEW. Kernels provided include linear, polynomial, radial basis function, and neural (tanh).<\/span><\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Summary<\/strong><\/p>\r\n\r\n<ul>\r\n \t<li>Explained max margin<\/li>\r\n \t<li style=\"text-align: justify\">Discussed optimal separating hyper planes<\/li>\r\n \t<li>Explained soft margin SVMs and multi class SVMs<\/li>\r\n \t<li>Listed various applications<\/li>\r\n \t<li>Discussed cancer classification and text categorization<\/li>\r\n \t<li>Listed advantages and Weaknesses of SVM<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Support Vector Machines-II<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/mH71Xra3J44\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n\r\n<strong>Web Links<\/strong>\r\n<ul>\r\n \t<li>http:\/\/www.shivani-agarwal.net\/Teaching\/E0370\/Aug-2011\/Lectures\/2.pdf<\/li>\r\n \t<li>http:\/\/vda.univie.ac.at\/Teaching\/ML\/15s\/LectureNotes\/06_SVM.pdf<\/li>\r\n \t<li>https:\/\/people.cs.pitt.edu\/~milos\/courses\/cs2750-Spring04\/lectures\/class11.pdf<\/li>\r\n \t<li>http:\/\/www.cs.nyu.edu\/~mohri\/mls\/lecture_4.pdf<\/li>\r\n \t<li><em>http:\/\/www.cs.cmu.edu\/~epxing\/Class\/10701\/Lecture\/lecture9-svmII.pdf<\/em><\/li>\r\n \t<li>www.iro.umontreal.ca\/~pift6080\/H09\/documents\/...\/<strong>svm<\/strong>_tutorial.<strong>ppt<\/strong><\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Supporting &amp; Reference Materials<\/strong>\r\n<ul>\r\n \t<li><em>Support Vector Machines by John Shawe-Taylor &amp; Nello Cristianini ,2000<\/em><\/li>\r\n \t<li><em>Support Vector Machines by Steinwart, Ingo, Christmann, Andreas,2008<\/em><\/li>\r\n \t<li><em>Support Vector Machines Applications by\u00a0 <strong>Ma<\/strong>, Yunqian, <strong>Guo<\/strong>, Guodong, 2014<\/em><\/li>\r\n<\/ul>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/mH71Xra3J44\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/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 more details about support vector machine, the basics of which we have already discussed in the last module.<\/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 concept margins of SVM<\/li>\n<li style=\"text-align: justify\">To learn more about soft margin<\/li>\n<li style=\"text-align: justify\">To classify multiple classes using SVM<\/li>\n<li style=\"text-align: justify\">To understand some applications of SVM<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>18.1 Introduction<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">SVM has roots in statistical learning and is considered one of the most important discoveries in machine learning since it also works well for high dimensional data. Most importantly it represents the decision boundary using a subset of training examples called support vectors. It is based on the concept of maximal margin hyper planes. Margin of a classifier is defined as the minimum distance to any example and in SVM the decision boundary which maximizes the margin is chosen<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-292 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193.png\" alt=\"\" width=\"362\" height=\"238\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193.png 362w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193-300x197.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193-225x148.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-193-350x230.png 350w\" sizes=\"auto, (max-width: 362px) 100vw, 362px\" \/><\/p>\n<p style=\"text-align: justify\">In this module we will discuss more in detail about soft margin, the use of SVM to solve multi-class problems and finally some applications of SVM.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.2 Soft Margin<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Consider a two class classification problem that uses a linear model<\/p>\n<p>&nbsp;<\/p>\n<p>y(x) = wT(x) + b<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">followed by a threshold function. Assume that training data are linearly separable. As we have already discussed there are multiple hyper planes that separate the data points. There are many possibilities for such hyperplanes. The task is to choose the optimal separating hyperplane. There are distance of (d++d-) where d+ is the shortest distance of a positive example from the hyper plane and d- is the shortest distance of a negative example from the hyper plane.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-293 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194.png\" alt=\"\" width=\"373\" height=\"279\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194.png 373w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194-300x224.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194-65x49.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194-225x168.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-194-350x262.png 350w\" sizes=\"auto, (max-width: 373px) 100vw, 373px\" \/><\/p>\n<p style=\"text-align: justify\">Now if the problem is not linearly separable then we need to introduce slack variables and we need to minimize:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-294 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195.png\" alt=\"\" width=\"527\" height=\"247\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195.png 527w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195-300x141.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195-225x105.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-195-350x164.png 350w\" sizes=\"auto, (max-width: 527px) 100vw, 527px\" \/><\/p>\n<p><strong>18.2.1 What is Soft Margin?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The SVM must not result in too many misclassifications. Therefore we introduce soft margin where a user specified parameter can control roughly, how many examples are allowed to violate the separating hyper plane and how far across the plane the examples can be considered. Setting this parameter is a tradeoff where we still want to try to achieve a large margin with respect to the correctly classified examples. Hence, the soft margin parameter specifies a trade-off between hyperplane violations and the size of the margin.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Maximum margin allows SVM to select among multiple candidate hyper planes. Soft margin accepts some misclassifications of the training examples. A soft margin can be obtained by adding a constant factor to the kernel function output, defining a priori, an upper bound on the size of the training set weights.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.2.2 Linear, Soft-Margin SVMs<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Soft \u2013Margin SVM tries to maintain slack variables x<em>i<\/em> to zero while maximizing margin. It does not minimize the <em>number<\/em> of misclassifications but the sum of distances from the margin hyper planes. In the case of soft margin, we allow \u201cerror\u201d \u03bei in classification. We use \u201cslack\u201d variables \u03be1 , \u03be2 \u2026\u2026.. \u03ben (one for each sample) (Figure 18.3).<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-295 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196.png\" alt=\"\" width=\"388\" height=\"318\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196.png 388w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196-300x246.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196-65x53.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196-225x184.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-196-350x287.png 350w\" sizes=\"auto, (max-width: 388px) 100vw, 388px\" \/><\/p>\n<p style=\"text-align: justify\">\u03bei Is the deviation error from ideal place for sample i: If 0&lt; \u03bei &lt; 1 then sample i is on the right side of the hyperplane but within the region of the margin. If \u03bei &gt; 1 then sample i is on the wrong side of the hyper plane.<\/p>\n<p>&nbsp;<\/p>\n<p>The primal optimization problem now can be explained. We change the constraints to<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-296 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197.png\" alt=\"\" width=\"316\" height=\"51\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197.png 316w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197-300x48.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197-65x10.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-197-225x36.png 225w\" sizes=\"auto, (max-width: 316px) 100vw, 316px\" \/><\/p>\n<p>Instead of<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-297 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198.png\" alt=\"\" width=\"533\" height=\"219\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198.png 533w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198-300x123.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198-65x27.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198-225x92.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-198-350x144.png 350w\" sizes=\"auto, (max-width: 533px) 100vw, 533px\" \/><\/p>\n<p style=\"text-align: justify\">C&gt;0 is a constant. It is a kind of penalty on the term \u00a0. It is a trade off between the margin and the training error. It is a way to control overfitting along with the maximum margin approach.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.2.3 The \u201cC\u201d Problem<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u201cC\u201d plays a major role in controlling over fitting (Figure 18.4). A larger value of C means that less number of training samples are not in ideal position. But smaller margin affects performance and a large enough value of C may lead to over fitting that is a complex classifier that fits only the training set. This means less training error that affects the classification performance positively. A smaller value of C means that more training samples are not in ideal position. A small C may lead to under fitting. This means more training error that affects<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-298 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199.png\" alt=\"\" width=\"490\" height=\"309\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199.png 490w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199-300x189.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199-225x142.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-199-350x221.png 350w\" sizes=\"auto, (max-width: 490px) 100vw, 490px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">the Classification Performance negatively. From the figure you can see that the more complex the model is (shown by blue line) the less is the minimum training error (shown by the green line) that is we have good classification performance but only for the given training samples. Now the dotted line shows the bound on the test error, so we need to choose a value of C that gives minimum testing error.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.2.4 Soft vs Hard Margin SVMs<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The robustness of soft and hard margin SVMs is shown in Figure 18.5.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-299 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200.png\" alt=\"\" width=\"444\" height=\"227\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200.png 444w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200-300x153.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200-225x115.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-200-350x179.png 350w\" sizes=\"auto, (max-width: 444px) 100vw, 444px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>SVMs 18.2.4.1 Hard Margin SVM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Considering the objective function discussed in section 18.2.2 we have an extra term in our objective function that is equal to the sum of the slack variables \u03bei\u2019s. Our aim is to minimize the objective function and hence we need to keep the \u03bei values small resulting in a hard margin and overfitting. Remember that the \u03be term is multiplied by C which indicates that as C increases we care less about the size of the margin, and more about keeping the \u03bei\u2019s small. Thus, the value of C trades between how large of a margin we would prefer, as opposed to how many of the training set examples violate this margin (and by how much).<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-300 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201.png\" alt=\"\" width=\"527\" height=\"331\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201.png 527w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201-300x188.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201-225x141.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-201-350x220.png 350w\" sizes=\"auto, (max-width: 527px) 100vw, 527px\" \/><\/p>\n<p><strong>Soft Margin SVM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Soft margins allow errors in classification. Objective function is still valid, but constraints need to be relaxed to tackle the non-linear separable case, so the linear separator is modified so that it does not satisfy all the constraints. In other words it allows softening of the constraints and results in under fitting (Figure 18.6).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.2<\/strong>\u00a0<strong>Classification with SVMs<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The classifier is modelled as a separating hyper plane. The most \u201cimportant\u201d training points are support vectors and they define the hyper plane. When we need to classify a given data point x using SVMs, we can score its projection normal to the hyper plane:<\/p>\n<p>&nbsp;<\/p>\n<p><strong>w<\/strong><strong>T<\/strong><strong>x <\/strong>+ b = \u03a3\u03b1iyi<strong>x<\/strong><strong>i<\/strong><strong>T<\/strong><strong>x + <\/strong>b<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We can decide the class based on where the example lies with respect to the hyper plane. Depending on whether the score is &lt; or &gt; we can decide the class. We can also set a confidence threshold t in order to control the overfitting issue. When the score &gt; t: we say the example belongs to the class and when score &lt; -t we say the example does not belong to the class.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.3.1 Recipe and Model selection procedure:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In most of the real-world applications of SVM we combine what we learned about the kernel trick and the soft margin and use them together:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-301 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202.png\" alt=\"\" width=\"525\" height=\"122\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202.png 525w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202-300x70.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202-225x52.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-202-350x81.png 350w\" sizes=\"auto, (max-width: 525px) 100vw, 525px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>We solve for\u00a0 \u03b1\u00a0 using a Quadratic Programming software.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-302 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203.png\" alt=\"\" width=\"581\" height=\"49\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203.png 581w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203-300x25.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203-65x5.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203-225x19.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-203-350x30.png 350w\" sizes=\"auto, (max-width: 581px) 100vw, 581px\" \/><\/p>\n<p>To find \u201cb\u201d we take any 0&lt; \u03b1i&lt;C and solve<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-303 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204.png\" alt=\"\" width=\"536\" height=\"142\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204.png 536w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204-300x79.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204-65x17.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204-225x60.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-204-350x93.png 350w\" sizes=\"auto, (max-width: 536px) 100vw, 536px\" \/><\/p>\n<p>The Classification function will be:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-304 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205.png\" alt=\"\" width=\"386\" height=\"98\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205.png 386w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205-300x76.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205-65x17.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205-225x57.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-205-350x89.png 350w\" sizes=\"auto, (max-width: 386px) 100vw, 386px\" \/><\/p>\n<p><strong>18.3.2 Model selection procedure<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>We have to decide which Kernel function and \u201cC\u201d value to use.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us assume that the Gaussian radial basis or a low degree polynomial kernel is used. We start checking which set of parameters C or \u03c3 (the standard deviation) if we choose Gaussian radial basis are the most appropriate by using K-Fold Cross-Validation. The steps of this cross-validation are to first randomly divide all the available training examples into <em>K<\/em> equal-sized subsets. Then we use all but one subset to train the SVM with the chosen parameters. We then use the held out subset to measure classification error. We repeat Steps 2 and 3 for each subset. We then average the results to get an estimate of the generalization error of the SVM classifier.The SVM is tested using this procedure for various parameter settings. In the end, the model with the smallest generalization error is adopted. Then we train our SVM classifier using these parameters over the whole training set.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.4 Multi Class SVM for <\/strong><strong>more than two classes<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">There are two basic approaches to solve <em>q<\/em>-class problems (q&gt;2 ) with SVMs.The first approach we will discuss is the One versus Others approach.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.4.1 One vs. Others<\/strong>:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This approach works by constructing a \u201cregular\u201d SVM\u00a0\u00a0\u00a0\u00a0\u00a0 <em>\u03c9<\/em><em>i<\/em>\u00a0\u00a0\u00a0\u00a0 for each class <em>i<\/em> that separates that class from all the other classes (class \u201c i\u201d positive and \u201cnot i\u201d negative). Then we check the output of each of the q SVM classifiers for our input and choose the class i where the corresponding SVM has the maximum output.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.4.2 Pairwise (one vs one):<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Here we construct a binary SVM for each pair of classes (so we construct q(q-1)\/2 SVMs) as shown in Figure 18.7. Then we use \u201cmax-wins\u201d voting strategy: we test each SVM on the input and each time an SVM chooses a certain class we add vote to that class. Then we choose the class with highest number of votes.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-305 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206.png\" alt=\"\" width=\"333\" height=\"231\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206.png 333w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206-300x208.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-206-225x156.png 225w\" sizes=\"auto, (max-width: 333px) 100vw, 333px\" \/><\/p>\n<p style=\"text-align: justify\">Both the methods mentioned above give in average comparable accuracy results. However the second method is relatively slower than the first method. Sometimes for certain application one method is preferable over the other. More advanced methods to improve pairwise comparison includes using decision graphs to determine the class selected in a similar manner to knockout tournaments. There are several other strategies that can be used for selecting the final classification based on the output of the binary SVMs.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.4.3 Basis of Multi-Label Classification<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-306 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207.png\" alt=\"\" width=\"599\" height=\"298\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207.png 599w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-207-350x174.png 350w\" sizes=\"auto, (max-width: 599px) 100vw, 599px\" \/><\/p>\n<p style=\"text-align: justify\">The basis of multi-label classification could be whole-part where an element may belong to both the whole and the component. This perspective is common for parent-child relationship where we add \u201cOther\u201d category, and do binary classification to distinguish the child from the other category. Since the classification boundary is non-linear, kernel methods may be more effective. The basis of multi-label classification can also be shared concepts (Figure 18.8).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">When the basis of the multi-label classification is shared concepts, training can be conducted in the following ways:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Mode-S \u2013 We label the multi-label data with the class to which the data most likely belonged, using some perhaps subjective criterion.<\/p>\n<p style=\"text-align: justify\">Mode-N \u2013In this case we consider the multi-label data as a new class separate from all the other classes<\/p>\n<p style=\"text-align: justify\">Mode-X \u2013 Here we use the multi-label data more than once, using each example as a positive example of each of the classes to which it belongs. This means that a training sample can belong to more than one class<\/p>\n<p style=\"text-align: justify\">The testing for the share concepts can be carried out as follows:<\/p>\n<p style=\"text-align: justify\">P-cut &#8211; Label input testing data by all of the classes corresponding to positive SVM scores. If no scores are positive, label that data to the class with top score.<\/p>\n<p style=\"text-align: justify\">S-cut -Train a threshold for each class by cross validation, and label input testing data by all of the classes for which scores of the input data were higher than the threshold..<\/p>\n<p style=\"text-align: justify\">R-cut -For any given test instance, always assign it <em>r<\/em> labels according to the descending confidence scores. Here <em>r<\/em> can be learned from training data.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>18.4.4 Evaluation Criteria<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we have already discussed previously F1 score combines precision and recall into one measure.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-307 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208.png\" alt=\"\" width=\"511\" height=\"280\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208.png 511w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208-300x164.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208-65x36.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208-225x123.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-208-350x192.png 350w\" sizes=\"auto, (max-width: 511px) 100vw, 511px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\">Here as we know p is precision and r is the recall, and TP is true positive, FP is false positive and FN is false negative. The above measures are used for one class at a time.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">Now we are going to discuss how to evaluate multi-label classification. There are many parameters that are used to evaluate multi-label classification performance. When we have more than one class we need to combine multiple performance measures into one quantity. There are basically two methods of combining namely micro-averaging and macro-averaging. In micro-averaging where we collect decisions for all classes, compute a contingency table and then evaluate. Macro-averaging is where we compute performance for each class, then average the value. With the above basis we outline the evaluation measure of combining performance measures.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">Here we use n to define the number of classes. The first method is Micro-F1 which measures the overall classification performance.<\/span><\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-308 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209.png\" alt=\"\" width=\"315\" height=\"106\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209.png 315w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209-300x101.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209-65x22.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-209-225x76.png 225w\" sizes=\"auto, (max-width: 315px) 100vw, 315px\" \/><\/p>\n<p style=\"text-align: justify\">The second method is Macro-F1 which measures the classification accuracy on the category level. This reflects the classifier\u2019s capability of dealing with rare categories<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-309 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210.png\" alt=\"\" width=\"353\" height=\"83\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210.png 353w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210-300x71.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210-225x53.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-210-350x82.png 350w\" sizes=\"auto, (max-width: 353px) 100vw, 353px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.5 SVM Applications<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">SVM has been successfully used to solve many real-world problems. Some of the applications include text categorization, image classification, bioinformatics (protein classification, cancer classification), hand-written character recognition, etc..<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>18.5.1 Application 1: Cancer Classification<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The SRCBT dataset can be used to illustrate the application. This is a high dimensional data set where the number of samples (patients) is &gt; 1000 and the number of features n &gt; 100. In such examples sometimes the samples are imbalanced with less number of positive samples. Many irrelevant features may be present where we need to perform feature selection. In the linear case, wi2 gives the ranking of dim i. However, SVM is sensitive to noisy (mis-labeled ) data.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.5.2 Application 2: Text Categorization<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us take up the classification of natural text (or hypertext) documents into a fixed number of predefined categories based on their content. There are many uses for this task such as email filtering, web searching, sorting documents by topic, etc. A document can be assigned to more than one category, viewed as a series of binary classification problems, one for each category. In this application, the representation of text is an important aspect. Normally vector space model (aka bag-of-words representation) used by information retrieval is used. Typical features are term frequency, and inverse document frequency where inverse term frequency is used to give less weightage to terms that occur in all classes and hence does not contribute to the classification<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-310 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211.png\" alt=\"\" width=\"326\" height=\"77\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211.png 326w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211-300x71.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-211-225x53.png 225w\" sizes=\"auto, (max-width: 326px) 100vw, 326px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In this case a document is represented by a vector indexed by a pre-fixed set or dictionary of terms. The values of an entry can be binary or weights<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u03c6i(<em>x<\/em>)=tfi log(idfi) \/ k<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For documents, removal of stops words and stemming is carried out as a pre-processing step. In order to account for varying length documents, normalization is carried out. Therefore can be represented Doc x =&gt; \u03c6(<em>x<\/em>). The distance between two documents is \u03c6(<em>x<\/em>)\u00b7\u03c6(<em>z)<\/em> where <em>K<\/em>(<em>x,z<\/em>) = \u03c6(<em>x<\/em>)\u00b7\u03c6(<em>z<\/em>) is a valid kernel. SVM can be used with <em>K<\/em>(<em>x,z<\/em>) for discrimination.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Why should we use SVM for text categorization? It is a typical multi-class multi-label classification problem. Documents are represented in such a way that it results in high dimensional input space, has few irrelevant features (dense concept) and the document vectors are sparse. In general text categorization problems are linearly separable. SVM, with some additional heuristic, has been regarded as one of the best classification scheme for text data, based on many benchmark evaluations.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>18.5.3 Application 3: Facial Expression Recognition<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For this application we refer to the work discussed in the paper \u201cFacial Expression Recognition Using Support Vector Machines by Philipp Michel and Rana El Kaliouby\u201d. Three basic problems a facial expression analysis approach needs to deal with are face detection in a still image or image sequence where we assume a full frontal view of the face. The data from facial expression is extracted using an automatic tracker that extracts the position of facial features from the video stream or an image as the case may be. For each expression, a vector of feature displacements is calculated by taking the Euclidean distance between feature locations in a neutral state of the face and a \u201cpeak\u201d frame representative of the expression. We use the SVM method to construct the classifier and the vectors of feature displacements for the previous stage as our input. A set of 10 examples for each basic emotion (in still images) was used for training, followed by classification of 15 unseen examples per emotion. Libsvm was used as the underlying SVM classifier. At first they used the standard SVM classification using linear kernel and they got 78% accuracy. Then with subsequent improvements including selection of a kernel function (they chose RBF) and the right \u201cC\u201d customized to the training data, the recognition accuracy boosted up to 87.9%.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-311 aligncenter\" src=\"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212.png\" alt=\"\" width=\"578\" height=\"300\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212.png 578w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212-300x156.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212-65x34.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212-225x117.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-content\/uploads\/sites\/65\/2018\/08\/Untitled-212-350x182.png 350w\" sizes=\"auto, (max-width: 578px) 100vw, 578px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>18.6 Advantages of SVM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The Kernel maps to a very-high dimensional space. In general, the search space has a unique minimum. The training that needs to be carried out is extremely efficient and similarly classification is extremely efficient. The two choices that are to be made are about the Kernel function and the cost. In typical domains, very good accuracy can be achieved. It is generally an extremely robust method.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>18.7 Weakness of SVM<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">However in spite of many advantages SVM has some disadvantages. It is sensitive to noise where a relatively small number of mislabeled examples can dramatically decrease the performance. In general it is a binary classification mechanism where only two classes are considered. It is expensive in terms of both memory and computational time, especially for multiclass problems. The selection of the kernel function and the right value for the \u201cTrade-off\u201d parameter \u201cC\u201d is not a straightforward issue.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>18.8 Software: Popular implementations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">SVM is a technique that has many implementations available for use. One such implementation is SVM<\/span><em style=\"font-size: 1em\">light<\/em><span style=\"font-size: 1em\">: <\/span><a style=\"font-size: 1em\" href=\"http:\/\/svmlight.joachims.org\/\">http:\/\/svmlight.joachims.org\/ <\/a><span style=\"font-size: 1em\">. This implementation is by Joachims . It is the most widely used SVM classification and regression package. It is distributed as a C++ source and binaries for Linux, Windows, Cygwin, and Solaris. The kernels provided are polynomial, radial basis function, and sigmoid (tanh).<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The next software is LibSVM <\/span><a style=\"font-size: 1em\" href=\"http:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvm\/\">: http:\/\/www.csie.ntu.edu.tw\/~cjlin\/libsvm\/ .<\/a><span style=\"font-size: 1em\"> LIBSVM (Library for Support Vector Machines), is developed by Chang and Lin and is also a widely used software developed in C++ and Java. It supports multi-class classification, weighted SVM for unbalanced data, cross-validation and automatic model selection. It has interfaces for Python, R, Splus, MATLAB, Perl, Ruby, and LabVIEW. Kernels provided include linear, polynomial, radial basis function, and neural (tanh).<\/span><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Summary<\/strong><\/p>\n<ul>\n<li>Explained max margin<\/li>\n<li style=\"text-align: justify\">Discussed optimal separating hyper planes<\/li>\n<li>Explained soft margin SVMs and multi class SVMs<\/li>\n<li>Listed various applications<\/li>\n<li>Discussed cancer classification and text categorization<\/li>\n<li>Listed advantages and Weaknesses of SVM<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Support Vector Machines-II<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/mH71Xra3J44\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong>Web Links<\/strong><\/p>\n<ul>\n<li>http:\/\/www.shivani-agarwal.net\/Teaching\/E0370\/Aug-2011\/Lectures\/2.pdf<\/li>\n<li>http:\/\/vda.univie.ac.at\/Teaching\/ML\/15s\/LectureNotes\/06_SVM.pdf<\/li>\n<li>https:\/\/people.cs.pitt.edu\/~milos\/courses\/cs2750-Spring04\/lectures\/class11.pdf<\/li>\n<li>http:\/\/www.cs.nyu.edu\/~mohri\/mls\/lecture_4.pdf<\/li>\n<li><em>http:\/\/www.cs.cmu.edu\/~epxing\/Class\/10701\/Lecture\/lecture9-svmII.pdf<\/em><\/li>\n<li>www.iro.umontreal.ca\/~pift6080\/H09\/documents\/&#8230;\/<strong>svm<\/strong>_tutorial.<strong>ppt<\/strong><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Supporting &amp; Reference Materials<\/strong><\/p>\n<ul>\n<li><em>Support Vector Machines by John Shawe-Taylor &amp; Nello Cristianini ,2000<\/em><\/li>\n<li><em>Support Vector Machines by Steinwart, Ingo, Christmann, Andreas,2008<\/em><\/li>\n<li><em>Support Vector Machines Applications by\u00a0 <strong>Ma<\/strong>, Yunqian, <strong>Guo<\/strong>, Guodong, 2014<\/em><\/li>\n<\/ul>\n","protected":false},"author":3,"menu_order":17,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-291","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/291","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":14,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/291\/revisions"}],"predecessor-version":[{"id":485,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapters\/291\/revisions\/485"}],"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\/291\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/media?parent=291"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/pressbooks\/v2\/chapter-type?post=291"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/contributor?post=291"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/wp-json\/wp\/v2\/license?post=291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}