Lab 19 Support Vectors

Hyperplanes

  • 1 dimension. graph: line. hyperplane: point \(\beta_0+\beta_1X_1=0\)
  • 2 dimensions. graph: plane. hyperplane: line \(\beta_0+\beta_1X_1+\beta_2X_2=0\)
  • 3 dimensions: plane \(\beta_0+\beta_1X_1+\beta_2X_2+\beta_3X_3=0\)
  • 4 dimensions: hyperplane \(\beta_0+\beta_1X_1+...\beta_pX_p=0\)

Question 1 rewrite the one and two dimensional cases into a form using x (1 dimensional) as a point value. and x, y (2 dimensional) in slope intercept form.

Separating Hyperplanes

Figure9.2.png Question 2 In general, if the points are linearly separable, how many separating hyperplanes exist?

Maximal Margin Classifier

Find the separating hyperplane with the furthest minimum distance an observation

  • Maximal
    • Maximize the distance
  • Margin
    • Distance to closest observation
  • Classifier
    • Classifies into 0/1

As the book says: midpoint of the largest “slab” you could insert between the classes

Figure9.3.png
Figure9.3.png

Support vectors

Observations that are minimally distant from the Classifier

  • Support:
    • These are the only points that effect the maximal margin hyperplane
    • They “support” the MMH
  • Vectors:
    • The vector from the MMH to the point

Question 3 What is the minimum number of support vectors? maximum?

Fitting the MMC

See text

Non-separable case

This is the most common in the real world. Instead of requiring an exact separation (margin), we can create a hyperplane that almost separates the classes (soft margin). This leads to Support Vector Classifiers

Support Vector Classifiers

Also called a soft margin classifier

Maximal Margin Classifiers tend to overfit and are extremely sensitive to training data (even a single point)

Figure9.5.png
Figure9.5.png

\[\text{maximize } M \text{ subject to: }\] \[\text{subject to } \sum_{j=1}^p\beta_j^2=1\] \[y_i(\beta_0+\beta_1x_{i1}...+\beta_px_{ip})\geq M(1-\epsilon_i)\] \[\epsilon_i\geq0\text{, }\sum_{i=1}^n\epsilon_i\leq C\]

  • M is the width of the margin (what we want to maximize)
  • \(\epsilon\) are slack variables
    • 0: correct side of the margin
    • \(>0\): wrong side of the margin
    • \(>1\) wrong side of the hyperplane
    • (effectively scaled distance from “correct”)
  • C is the tuning parameter or the budget for margin violations
    • choose via cross validation
    • low: low bias, high variance (more accurate to training data)
    • high: high bias, low variance
  • Only observations that are on or violate the margin (>0) affect the hyperplane
    • support vectors
    • variance is due to close values
    • very robust to distant, well classified values

Question 4 How well will this do on data that is not linearly separable at all, even if it is separable with a simple shape (e.g. a circle). (see board)

Question 5 9.7.2 in the text





































Lab 20: SVM

Support Vector Machines

Similar to going from linear regression to quadratic/polynomial regression, we can go from a support vector classifier to a support vector machine. However, instead of using polynomial scaling, we use “kernels” (you can look them up yourself later)

Linear problem:

  • The solution to the linear problem depends only on the inner products of the observations
    • this will have \(\frac{n(n-1)}{2}\) values \[f(x)=\beta_0+\sum_{i=1}^n\alpha_i\langle x_i,x_i\prime\rangle\]
    • However, we only need the support vectors, which allows us to write this as \[f(x)=\beta_0+\sum_{i\in S}\alpha_i\langle x_i,x_{i^\prime}\rangle\]
    • Note that \(\langle x_i,x_{i^\prime}\) is the inner product (which you should be familiar with from calculus)
  • Question 6 what is the inner product of x=[1,2,3,4] and y=[2,4,5,3]?

Generalized problem:

  • Instead of using the inner product, we can use a “kernel” \(K(x_i,x_{i^\prime})\)
  • Question 7 using the same vectors as Question 6, and a kernel \(K(x,y)=\sum x_jy_j^2\), what would K(x,y) be?
  • general polynomial kernel of degree d: (d in $) \[K(x_i,x_{i^\prime})=(1+\sum x_{ij}x_{i^\prime j})^d\]
  • Then we have that \[f(x)=\beta_0+\sum_{i\in S}\alpha_i K(x_i,x_{i^\prime})\]
  • Other popular kernels include the radial kernel (See 9.24 in the book)
  • Question 8 why do you think it is called the “radial” kernel?
  • Question 9 How large is the feature space in the radial kernel compared to the linear kernel?

More than 2 classes

We won’t cover this in detail.

  • One versus one: create an SVM between every pair of classes (e.g. if there are 3 options A, B, C you’d make 3, AvsB, Bvsc, AvsC)
    • K choose 2 classifiers
  • One versus all: compare class K to not K (1/-1). Observation goes to the largest value from the classifiers
    • K classifiers

Question 10 Work through 9.6.2 to make sure you understand SVMs enough to do the homework. (not graded)