Supervised Learning

Support Vector Machine

This feels like just finding a sort of Hyperplane that splits data into half.

Resources

• https://www.quarkml.com/2022/09/primal-formulation-of-svm-simplified.html
• StatQuest: https://www.youtube.com/watch?v=efR1C6CvhmE&ab_channel=StatQuestwithJoshStarmer

1. Primal Formulation (The Geometric Problem)

The primal formulation defines the optimization problem in terms of the primary variables: the weight vector $w$ and the bias $b$. Its objective is explicitly geometric: maximizing the margin.

Primal formulation of SVM (hard margin):

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{s.t.}{y}_i(w^{\top }{x}_i+b)\ge 1\forall i$$

My Intuition

$\hat{y}=w^{\top }x+b$ is the equation of the Hyperplane that we want to learn to linearly separate our points $(x_i,y_i)$. The sign of $\hat{y}$ tells us which side of the hyperplane the point $x$ lies on:

• If $\hat{y}>0$, then $x$ lies on the same side as the normal vector $w$
• If $\hat{y}<0$, then $x$ lies on the opposite side as the normal vector

So in the hard margin setup, we have correct label when $y\hat{y}>0$.

Equivalently, if we let ${\hat{y}}_i=⟨w,x_i⟩+b$

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2\text{s.t.}1-y_i{\hat{y}}_i\le 0\forall i$$

Soft-margin formulation:

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }_2^2+C\sum _i\max (0,1-y_i{\hat{y}}_i)$$

2. Dual Formulation

The Dual Formulation is defined entirely in terms of the Lagrange multipliers ${\alpha }_i$​ and the dot products of the data points $⟨x_i,x_j⟩$. We no longer use the primary variables.

Convert constrained optimization to unconstrained optimization via Method of Lagrange:

$$\underset{\alpha \in {\mathbb{R}}^n,\alpha \ge 0}{\max }\underset{w,b}{\min }\left[\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^n{\alpha }_i(y_i(w^{\top }{x}_i+b)-1)\right]$$

• Lagrange multipliers add a penalty to the objective for each violated constraint.

The dual formulation is given by: ${\min }_{\alpha \in {\mathbf{R}}^n,C\ge \alpha \ge 0}\frac{1}{2}{\sum }_i{\sum }_j{\alpha }_i{\alpha }_j{y}_i{y}_j⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩-{\sum }_i{\alpha }_i\text{s. t.}{\sum }_i{\alpha }_i{y}_i=0$

In the real-world

in practice, the Soft-Margin Support Vector Machine (SVM) formulation is almost always used because real-world data is rarely perfectly linearly separable.

CS231n

The Loss Function for a multiclass SVM loss for example $i$ is defined as a Hinge Loss): $L_i={\sum }_{j\ne y_i}\max (0,s_j-s_{y_i}+\Delta )$ where

• $s_j=f(x_i,W{)}_j$ is the score for the $j$-th class
• $\Delta$ can be interpreted as the minimum margin (use $\Delta =1$), i.e. the correct class should be a minimum of $\Delta$ away to make sure we incur 0 loss.

We omit $y_i$ as part of the calculation for loss because if not, the loss would be $\Delta$, instead of 0, even though we have perfect predictions.

The loss over the full dataset is $L=\frac{1}{N}\sum _i{L}_i+\lambda R(W)$

• The first part is the Data Loss
• The second part of the equation ($\lambda R(W)$) is the Regularization loss, given by $R(W)=\sum _k\sum _l{W}_{k,l}^2$ (this is L2 Regularization)

In code, these are implemented as:

def L_i(x, y, W):
  """
  unvectorized version. Compute the multiclass svm loss for a single example (x,y)
  - x is a column vector representing an image (e.g. 3073 x 1 in CIFAR-10)
    with an appended bias dimension in the 3073-rd position (i.e. bias trick)
  - y is an integer giving index of correct class (e.g. between 0 and 9 in CIFAR-10)
  - W is the weight matrix (e.g. 10 x 3073 in CIFAR-10)
  """
  delta = 1.0 # see notes about delta later in this section
  scores = W.dot(x) # scores becomes of size 10 x 1, the scores for each class
  correct_class_score = scores[y]
  D = W.shape[0] # number of classes, e.g. 10
  loss_i = 0.0
  for j in range(D): # iterate over all wrong classes
    if j == y:
      # skip for the true class to only loop over incorrect classes
      continue
    # accumulate loss for the i-th example
    loss_i += max(0, scores[j] - correct_class_score + delta)
  return loss_i
 
def L_i_vectorized(x, y, W):
  """
  A faster half-vectorized implementation. half-vectorized
  refers to the fact that for a single example the implementation contains
  no for loops, but there is still one loop over the examples (outside this function)
  """
  delta = 1.0
  scores = W.dot(x)
  # compute the margins for all classes in one vector operation
  margins = np.maximum(0, scores - scores[y] + delta)
  # on y-th position scores[y] - scores[y] canceled and gave delta. We want
  # to ignore the y-th position and only consider margin on max wrong class
  margins[y] = 0
  loss_i = np.sum(margins)
  return loss_i
 
def L(X, y, W):
  """
  fully-vectorized implementation :
  - X holds all the training examples as columns (e.g. 3073 x 50,000 in CIFAR-10)
  - y is array of integers specifying correct class (e.g. 50,000-D array)
  - W are weights (e.g. 10 x 3073)
  """
  # evaluate loss over all examples in X without using any for loops
  # left as exercise to reader in the assignment