INF4300 - Digital Image Analysis
Exercise 8 - support vector machines.
Show that the criterion
Given a binary data set:
Plot the points. Sketch the support vectors and the decision boundary for a linear SVM classifier with maximum margin for this data set.
Given the binary classification problem:
Sketch the points in a scatterplot (preferably with different colors for the different classes).
What is the error rate of the Gaussian classifier on the training data set?
Sketch on the plot the decision boundary you would get using a SVM with linear kernel and a high cost of misclassifying training data. Indicate the support vectors and the decision boundary on the plot.
What is the error rate of the linear SVM on the training data set?
Download the two datasets mynormaldistdataset.mat and mybananadataset.mat .
You can use a library for SVM, e.g. scikit-learn in python.
Familiarize yourself with the data sets by studying scatterplots.
Rerun the experiments a couple of times, and visualize the data using something like the following:
How does the support vectors and the boundary change with the parameter?
Try to remove some of the non-support-vectors and rerun. Does the solution change?
In the lecture we defined the rbf kernel as
Make sure you know why we now get non-lenear decision boundaries.
You can for example use the parameter ranges suggested in the lecture slides:
An Introduction to Machine Learning
E solutions ch. 6 - support vector machines.
Solutions to exercises of chapter 6 .
E.1 Exercise 1
Load required libraries
Define a radial SVM using the e1071 library
Setup parallel processing
Extract predictors from segmentationData
Partition data
Set seeds for reproducibility (optional). We will be trying 9 values of the tuning parameter with 5 repeats of 10 fold cross-validation, so we need the following list of seeds.
We will pass the twoClassSummary function into model training through trainControl . Additionally we would like the model to predict class probabilities so that we can calculate the ROC curve, so we use the classProbs option.
Tune SVM over the cost parameter. The default grid of cost parameters start at 0.25 and double at each iteration. Choosing tuneLength = 9 will give us cost parameters of 0.25, 0.5, 1, 2, 4, 8, 16, 32 and 64. The train function will calculate an appropriate value of sigma (the kernel parameter) from the data.
SVM accuracy profile
SVM accuracy profile.
Test set results
Get predicted class probabilities
Build a ROC curve
Plot ROC curve.
SVM ROC curve for cell segmentation data set.
Calculate area under ROC curve
Solving SVM problems
Aurellem ☉.
- read the blog »
1 Question: How do you find \(\vec{w}\), \(b\), and the α's?
You should take a look at the class notes, for starters: http://ai6034.mit.edu/fall12/images/SVM_and_Boosting.pdf
You can also take a look at the next section to see an example of (part of) a worked problem.
When solving SVM problems, there are some useful equations to keep in mind:
- \(\vec{w}\cdot \vec{x} + b = 0\) defines the boundary, and in particular \(\vec{w}\cdot \vec{x} + b \geq 0\) defines the positive side of the boundary.
- \(\vec{w}\cdot \vec{x} + b = \pm 1\) defines the positive and negative gutters.
- The distance between the gutters (the width of the margin) is \(\text{margin-width} = \frac{2}{||\vec{w}||} = \frac{2}{\sqrt{\vec{w}\cdot \vec{w}}}\)
- \(\sum_{\text{training data}} y_i \alpha_i = 0\)
- \(\sum_{\text{training data}} y_i \alpha_i \vec{x}_i = \vec{w}\)
The last two equations involve the “supportiveness” parameters \(\alpha_i\). Look at equation (5) and notice what would happen if some \(\alpha_j\) were zero: the corresponding term in the sum would be zero, and hence that training point wouldn't contribute to \(\vec{w}\), and hence wouldn't affect where the boundary was drawn. In fact, notice that in this case you could delete \(\vec{x}_j\) altogether and the boundary would still be drawn in the same place.
Support vector guideline 1 : To see if a point \(\vec{x}_j\) is a support vector, imagine deleting it and see if you would draw a different SVM boundary. If you would draw a different SVM boundary, the point is a support vector (\(\alpha_j > 0\)). If you would draw the same boundary, even if the point were deleted, the point isn't a support vector (\(\alpha_j = 0\)).
Support vector guideline 2 : Only points on the gutter can be support vectors; if a point isn't on the gutter, it's not a support vector. If a point is on the gutter, it might or might not be a support vector—you can determine whether it is using Support vector guideline 1.
Support vector guideline 3 : You may find it useful to think of the \(\alpha_i\) as measuring “supportiveness”. This means, for example, that: \(\alpha_i\) is zero for non-support vectors, i.e. training points that do not determine the boundary, and which would not affect the placement of the boundary if deleted. When you compare two separate SVM problems, where the first has support vectors that are far from the boundary, and the second has support vectors very close to the boundary, the latter support vectors have comparatively higher \(\alpha_i\) values.
1.1 Can α be zero for support vectors?
No, α is zero for a point if and only if it's not a support vector. You can see this because in equation (5), just the points with nonzero alphas contribute to \(\vec{w}\).
1.2 Are all points on the gutter support vectors? How do you tell whether a point is a support vector?
Not all points on the gutter are support vectors. To tell if a training point is a support vector, imagine what would happen if you deleted it — would the decision boundary be different? If it would, the point is a support vector. If it wouldn't, the point isn't a support vector.
2 2011 Q4 Part A
The equation for the line you drew in part A is \(y = 0\), and points will be classified as positive if \(y\geq 0\).
Now in general, the equation for the decision boundary is \(\vec{w}\cdot \vec{x} + b = 0\), and points \(\vec{x}\) are classified as positive if \(\vec{w}\cdot \vec{x} + b \geq 0\). To solve for \(\vec{w}\) and \(b\), you just manipulate your inequation for the boundary into this form:
And so we have:
…which is almost right. The trouble is that we can multiply this inequation by any positive constant \(c>0\) and it will still be true — so, the right answer might not be the \(\vec{w}\) and \(b\) we found above, but instead a multiple of them. To fix this, we multiply the inequation by \(c>0\), and solve for \(c\):
One formula that you can use to solve for \(c\) is the margin-width formula; by examining the lines you drew, you see that the margin width is 4 . Now, in general, the equation for margin width is
So, for the second time, we use the technique of setting the quantity you can see (margin width = 4) equal to the general formula (margin width = 2/||w||) and solving for the parameters in the general formula:
(This uses the expression for \(\vec{w}\) we got after we multiplied by \(c\) above.)
Returning to our inequality, we have
And this is truly the right answer, now that we have solved for \(c\).
3 What's the use of gutters?
The gutters are the regions where you have no hard data supporting your classification, but the decision boundary is, as its name implies, the cutoff for making a decision between the two classifications. As such, you would likely have lower confidence in any decision within the gutters, but a classifier needs to make a decision one way or the other for all possible test data (there's no reason not to do so, as making no decision means you're automatically wrong in all cases, whereas even a lousy classifier will get some of them right).
Here are two more ways to look at it. First of all, and simplest, SVMs are supposed to find the boundary with the widest margin. The width of the margin is just the perpendicular distance between the gutters, so the gutters are important for that reason.
Second of all, if you attempt to define the SVM problem geometrically, i.e. put it into a form that can be solved by a computer, it looks something like the following.
Find a boundary — which is defined by a normal vector \(\vec{w}\) and an offset \(b\) — such that: The boundary “ \(\vec{w}\cdot \vec{x} + b = 0\) ” separates the positive and negative points The width of the margin is as large as possible. Remember, the margin width is twice the distance between the boundary and the training point that is closest to the boundary; in other words, $$\text{margin-width} = \min_{\text{training data}} 2 y_i (\vec{w}\cdot \vec{x}_i + b)$$
Unfortunately, the problem as stated has no unique solution, since if you find a satisfactory pair \(\langle \vec{w}, b \rangle\) , then the pair \(\langle 3\vec{w}, 3b\rangle\) (for example) defines the same boundary but has a larger margin. The problem is that any multiple of a satisfactory pair yields another satisfactory pair. In essence, we're just changing the units of measurement without materially affecting the boundary.
We can remove this additional degree of freedom by adding another constraint to the problem which establishes a sense of scale. For example, we could require \(\vec{w}\) to be a unit normal vector, i.e. we could require that \(||\vec{w}|| = 1\). This fixes the problem and gives SVMs a unique solution.
In 6.034, and elsewhere, we use an alternate constraint; we impose the gutter conditions :
\(\vec{w}\cdot \vec{x_+} + b = + 1\) for positive training points \(\vec{x_+}\).
\(\vec{w}\cdot \vec{x_-} + b = -1\) for negative training points \(\vec{x_-}\).
which we often combine into a single inequality: \(y_i (\vec{w}\cdot \vec{x}_i + b) \geqslant 1\) for all training points \(\langle \vec{x}_i, y_i\rangle\).
This constraint is enough to eliminate the extra degree of freedom and give SVMs a unique solution. Moreover, you get a nice formula for the margin width by requiring that it holds:
\(\text{margin-width} = \frac{2}{||\vec{w}||}\) because the gutter conditions are enforced.
That's why gutters are important.
Date: 2013-11-06T01:14-0500
Author: Dylan Holmes
Org version 7.9.3f with Emacs version 24
Navigation Menu
Search code, repositories, users, issues, pull requests..., provide feedback.
We read every piece of feedback, and take your input very seriously.
Saved searches
Use saved searches to filter your results more quickly.
To see all available qualifiers, see our documentation .
- Notifications You must be signed in to change notification settings
My assignment solutions for CS231n - Convolutional Neural Networks for Visual Recognition
jariasf/CS231n
Folders and files, repository files navigation, cs231n: convolutional neural networks for visual recognition - assignment solutions.
This repository contains my solutions to the assignments of the CS231n course offered by Stanford University (Spring 2018).
Find course notes and assignments here and be sure to check out the video lectures for Winter 2016 and Spring 2017 !
Assignments using Tensorflow are completed, those using Pytorch will be implemented in the future.
Assignment 1:
- Q1 : k-Nearest Neighbor classifier. ( Done )
- Q2 : Training a Support Vector Machine. ( Done )
- Q3 : Implement a Softmax classifier. ( Done )
- Q4 : Two-Layer Neural Network. ( Done )
- Q5 : Higher Level Representations: Image Features. ( Done )
Assignment 2:
- Q1 : Fully-connected Neural Network. ( Done )
- Q2 : Batch Normalization. ( Done )
- Q3 : Dropout. ( Done )
- Q4 : Convolutional Networks. ( Done )
- Q5 : PyTorch / TensorFlow on CIFAR-10. ( Done )
Assignment 3:
- Q1 : Image Captioning with Vanilla RNNs. ( Done )
- Q2 : Image Captioning with LSTMs. ( Done )
- Q3 : Network Visualization: Saliency maps, Class Visualization, and Fooling Images. ( Done )
- Q4 : Style Transfer. ( Done )
- Q5 : Generative Adversarial Networks. ( Done )
- Jupyter Notebook 98.5%
- Python 1.5%
IMAGES
VIDEO
COMMENTS
Homework 7: Support Vector Machines ECE 228, Mark Wagner. SVM for two Class Classification Goal: find +,- such that 3=+567+-Where +is a separating plane 6()is an arbitrary transformation-is a bias term 3 >0 => 7 is class 1 ... 7.1 Solution Note: +=W X
Second, write your solution independently: close the book and all of your notes, and send collaborators out of the room, so that the solution comes from you only. Late Submission Policy: Late submissions will not receive full credit. Half credit will be awarded to correct solutions submitted within 48 hours of the original deadline.
Problem 1: SVM decision boundaries [Zichao - 30pts] Support Vector Machines are powerful tools for classi cations. SVM can perform non-linear classi cation using the kernel trick. In this question, you are to examine the decision boundaries of SVM with fft kernels. 1. Recall that the soft-margin primal SVM problem is min 1 2 w w +C ∑n i=1 ...
CS229 Problem Set #2 Solutions 1 CS 229, Public Course Problem Set #2 Solutions: Kernels, SVMs, and Theory 1. Kernel ridge regression In contrast to ordinary least squares which has a cost function J(θ) = 1 2 Xm i=1 (θTx(i) −y(i))2, we can also add a term that penalizes large weights in θ. In ridge regression, our least
SVM on a small data set of blue squares and red circles. The dotted lines show the +1 and 1 level-sets ... CSE 151 Homework 3 Fall 2019 Solution 6.In this problem, you are going to manually di erentiate some simple neural networks. Let ˙denote the element-wise logistic function. Compute the gradient(s), with respect to each argument, for each
So that's the solution! Just to recap, to get the scoring function f for SVM, you'd compute from the dual problem (3), plug it into (4) to get , plug that into the equation above to get 0, and that's the solution to the primal problem, and the coe cients for f . 8. Support vectors. x. 2. x. 1. 1 1. Image by MIT OpenCourseWare.
Homework 4: SVM, Clustering, and Ethics Introduction This homework assignment will have you work with SVMs, clustering, and engage with the ethics lec- ... Con rm that the solution in Part 6 makes the constraints above binding for these support vectors. Problem 2 (K-Means and HAC, 20pts)
Support Vector Machine (SVM) V. Vapnik Robust to outliers! 1. Use optimization to find solution (i.e. a hyperplane) with few errors 2. Seek large margin separator to improve generalization 3. Use kernel trick to make large feature spaces computationally efficient Support vector machines: 3 key ideas ...
To handle the difference between empirical and expected losses . Choose large margin hypothesis (high confidence) . Choose a small hypothesis class. ෝ ∗. Corresponds to the hypothesis class. Thought experiment. Principle: use smallest hypothesis class still with a correct/good one. Also true beyond SVM.
This set of notes presents the Support Vector Machine (SVM) learning al-gorithm. SVMs are among the best (and many believe is indeed the best) \o -the-shelf" supervised learning algorithm. To tell the SVM story, we'll need to rst talk about margins and the idea of separating data with a large \gap."
SVM demonstration program, that means that none of the points are shown as red circles.) Also, not all (or not all but a few) of the data points are support vectors. Part 2: Thinking about the math 1. What equations are used for classification in a support vector machine? w. u + b > 0 for positive class (i.e. on one side of the boundary line)
Complementary hints and solutions to exercises for INF4300 - Digital Image Analysis at the University of Oslo. INF4300 - Digital Image Analysis. Exercise 8 - Support Vector Machines ... Stick with the linear SVM, but change the -parameter. Rerun the experiments a couple of times, and visualize the data using something like the following: ...
Dual SVM optimization problem I Any convex optimization problem has a dual problem. In SVM, it is both illuminating and practical to solve the dual problem. I The dual to problem (11) is max 2 1:n X i i 1 X i i jy iyjxiTx j s.t i 0for alli and X i iy i = 0: (16) I This is aquadraticproblem with n variables on a convex domain. I Dual problem in ...
not solutions) from books or online resources, again after you have thought about the problems on your own. There are two requirements: rst, cite your collaborators fully and completely (e.g., \Jane explained to me what is asked in Question 2.1"). Second, write your solution independently: close the book and all of your notes, and
Homework 3: Max-Margin and SVM Introduction This homework assignment will have you work with max-margin methods and SVM classi cation. The aim ... Using your answers so far, what particular solution to w will be optimal for this optimization problem? 6.Now solve for the corresponding value of w 0, using your general expression from part (4 ...
C Solutions ch. 4 - Clustering. C.1 Exercise 1; D Solutions ch. 7 - Nearest neighbours. D.1 Exercise 1; E Solutions ch. 6 - Support vector machines. E.1 Exercise 1; F Solutions ch. 9 - Decision trees and random forests. F.1 Exercise 1; G Solutions chapter 8 - use case 1. G.1 Preparation. G.1.1 Load required libraries; G.1.2 Define SVM model; G ...
When solving SVM problems, there are some useful equations to keep in mind: \vec {w}\cdot \vec {x} + b = 0 defines the boundary, and in particular \vec {w}\cdot \vec {x} + b \geq 0 defines the positive side of the boundary. \vec {w}\cdot \vec {x} + b = \pm 1 defines the positive and negative gutters. The last two equations involve the ...
This repository contains my solutions to the assignments of the CS231n course offered by Stanford University (Spring 2018).. Find course notes and assignments here and be sure to check out the video lectures for Winter 2016 and Spring 2017!. Assignments using Tensorflow are completed, those using Pytorch will be implemented in the future.
Assignment 2 Solutions for Spring 2017 homework svm cmu machine learning (spring 2017) out: feb 13 due: feb 27, 11:59 pm section multiple choice questions there. Skip to document. ... Main - Its Homework 4 assignment solution for the class in Spring 2017; Preview text. Homework 2 Na ̈ıve Bayes; SVM
Try to remove some of the non-support-vectors and rerun - does the solution change? Load mybananadataset.mat. Try various values values of the C-parameter with a linear SVM. Can the linear SVM classifier make a good separation of the feature space? Change kernel to a RBF (radial basis function), and rerun. Try changing the sigma-parameter
Homework 4: Kernel Methods Instructions: Your answers to the questions below, including plots and mathematical work, ... in which you can code a kernelized SVM and see how it works on a classification problem with a two-dimensional input space. The problem set ends with two
A support-vector machine constructs a hyperplane or set of hyperplanes in a high- or infinite-dimensional space, which can be used for classification, regression, or other tasks like outliers detection. ... When a problem can be converted to another problem whose solution is easier to compute and also provides the solution for the original ...
Using this matrix, give a closed form solution for the optimal weights w. 2. (20 points) Choosing the bandwidth is very important, as setting it too high or too low can lead to suboptimal results. Give the optimal weights w that result as ˙!1. 2