svm

Support Vector Machine

• Finding a separating hyperplane
  • Must correctly classify the data
  • The closest points have the greatest distance to it — Maximize the margin width
• Advantages
  • Insensitive to high dimensionality
  • Insensitive to class imbalance
• Disadvantages
  • Data may not have a clear boundary
  • Linear hyperplane doesn’t exist in non-linear data.
• sklearn.svm.LinearSVC: a parameter C to dictate tradeoff between margin and correct classification. The larger, the narrower the margin.
• Use kernel function to map data points to a higher dimensionality, so that they can be separated. A feature transformation $\mathbf{x}\to \varphi (\mathbf{x})$ is needed.
  • Polynomial
  • Radial basis function (RBF), or Gaussian kernel
  • Sigmoid kernel

Problem Definition

For a binary classification task

• Notations
  • ${\mathbf{x}}_i=(x_1,x_2,\dots ,x_n)$, where $\mathbf{x}\in {\mathbb{R}}^n$
  • $y_i\in \{-1,1\}$
  • Derive a function $f:\mathbf{x}\to y$.
  • The hyperplane is given as $\mathbf{wx}+b=0$
  • Where $\mathbf{w}=(w_1,w_2,\dots ,w_n)$ is a weighted vector and $b$ is the bias.
• To use the SVM, we have
  • Boundaries are given by $\mathbf{w}{\mathbf{x}}^{\pm }+b=\pm 1$
  • If $y_i=+1$, then ${\mathbf{wx}}_i+b\ge 1$
  • If $y_i=-1$, then ${\mathbf{wx}}_i+b\le 1$
  • i.e. $y_i({\mathbf{wx}}_i+b)\ge 1$
• Margin width is given by $2/\Vert \mathbf{w}\Vert$

$$\begin{array}{rl}\min & {\mathbf{w}}^{⊺}\mathbf{w}/2\\ \text{s.t.}& y_i({\mathbf{wx}}_i+b)\ge 1\forall ({\mathbf{x}}_i,y_i)\end{array}$$