The Classification Problem

• Two classes \(C_1, C_2\) with labels \(1, -1\) repsectively
• Sample set \( \mathcal{X} = \{\mathbf{x}^t, r^t\}_{t=1}^N\) with known points and labels
• Goal: Find \( \mathbf{w}\) (discriminant vector) and \(w_0 \) (number) to separate the two classes of points, i.e.: \[ U^t \equiv r^t(\mathbf{w}^T \mathbf{x}^t + w_0) \geq 1 \mbox{ for all } t \]
• Margin: distance from separation hyperplane to closest points
• Best discriminant (optimal separation hyperplane) maximizes the margin so as to distinguish the classes in the clearest way
• Maximizing the margin \( \Leftrightarrow \) minimizing \( \norm{\mathbf{w}} \Rightarrow \) minimizing \( \frac{1}{2} \norm{\mathbf{w}}^2 = \frac{1}{2} \mathbf{w}^T \mathbf{w} \)
• We have an optimization problem! Something to minimize under certain constraints.

Lagrangian for the Classification Problem

• Let's look at this from the perspective of Lagrangian mechanics:
• "Kinetic Energy": \( T = \frac{1}{2} \vert\vert\mathbf{w}\vert\vert^2 = \frac{1}{2} \mathbf{w}^T \mathbf{w} \)
• "Potential Energy": \( U = \sum_{t=1}^N \alpha^t U^t \) (assume \(\alpha^t \geq 0\) for all \(t\))
• Lagrangian \( L_p = T-U = \frac{1}{2} \mathbf{w}^T \mathbf{w} - \sum_{t=1}^N \alpha^t[r^t(\mathbf{w}^T \mathbf{x}^t + w_0)-1]\)
• Optimize with respect to \(\mathbf{w}\) and \(w_0\):
  • \( \frac{\partial L_p}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum_{t=1}^N \alpha^t r^t \mathbf{x}^t\)
  • \( \frac{\partial L_p}{\partial w_0} = 0 \Rightarrow \sum_{t=1}^N \alpha^t r^t =0 \)

New Lagrangian, New Problem

• Plug expressions for \(\norm{\mathbf{w}}\) and \(w_0\) back into original expression to get "dual Lagrangian": \[ L_d = -\frac{1}{2} \sum_{t=1}^N \sum_{s=1}^N \alpha^t \alpha^s r^t r^s (\mathbf{x}^t)^T \mathbf{x}^s + \sum_{t=1}^N \alpha^t \]
• Maximize with respect to \(\alpha^t\) under previous constraints \(\Rightarrow \) most are zero!
• The \(\mathbf{x}^t\) associated with the nonzero \(\alpha^t\) are called support vectors, and they satisfy the exact equality: \[ U^t = 0 \Rightarrow r^t(\mathbf{w}^T \mathbf{x}^t +w_0) = 1 \Rightarrow w_0 = r^t -\mathbf{w}^T \mathbf{x}^t \]
• For stability, take an average: \( w_0 = \frac{1}{N}\sum_{t=1}^N \left(r^t -\mathbf{w}^T \mathbf{x}^t \right) \)
• Discriminant (now called support vector machine) is weighted sum of support vectors: \(\mathbf{w} = \sum_{t=1}^N \alpha^t \mathbf{x}^t\)
• For the \(\alpha^t =0\), \(U^t>0 \Rightarrow\) points lie away from discriminant and do not affect classification result!

Problem?

We assumed that there was a perfect solution to linearly separate the classes.

What if there isn't?

• Data point is on wrong side of hyperplane
• Data point is on correct side, but within the margin

Solution: Soft Margin Hyperplane

• Introduce slack variables \(\xi^t \geq 0\). Proceed in the same fashion, but with small changes:
• Constraint becomes \(U^t + \xi^t \geq 0\)
• Soft error \(C\sum_{t=1}^n \xi^t\) added to kinetic energy (\(C=\) penalty term)
• Linear combination \(\sum_{t=1}^n \mu^t \xi^t\) added to potential energy
• Additional optimization constraint: \( \frac{\partial L_p}{\partial \xi^t} = 0 \Rightarrow C-\alpha^t-\mu^t = 0\ \)
• Result:
  • Support vectors have \(\alpha^t >0\) again, SVM defined in same way
  • \(\alpha^t \lt C \Rightarrow \) support vectors are on margin; use to calculate \(w_0\) like before
  • \(\alpha^t = C\): problem data points mentioned before

Kernel Methods

• Nonlinear transformation to a smaller \(k\)-dimensional space: \(\mathbf{z} = \mathbf{\phi}(\mathbf{x}) = \left( \phi_j(\mathbf{x}) \right)_{j=1}^k \)
• Proceed as with soft margin hyperplane, except with \(\mathbf{x} \rightarrow \mathbf{\phi}(\mathbf{x})\): \[ L_d = -\frac{1}{2} \sum_{t=1}^N \sum_{s=1}^N \alpha^t \alpha^s r^t r^s \mathbf{\phi}(\mathbf{x}^t)^T \mathbf{\phi}(\mathbf{x}^s) + \sum_{t=1}^N \alpha^t \]
• Define kernel function \( K(\mathbf{x}^t,\mathbf{x}^s) = \mathbf{\phi}(\mathbf{x}^t)^T \mathbf{\phi}(\mathbf{x}^s) \)
• Discriminant becomes: \( g(\mathbf{x}) = \mathbf{w}^T \mathbf{\phi}(\mathbf{x}) = \sum_{t=1}^N \alpha^t r^t K(\mathbf{x}^t,\mathbf{x}) \)
• If we have kernel function, we don't need to use the nonlinear transformation at all!
• Gram Matrix: kernel values \( \mathbf{K}_{ts} = K(\mathbf{x}^t,\mathbf{x}^s) \) should be symmetric, positive semidefinite
• Great for use in bioinformatics, where number of dimensions is high; \(K\) produces a real number \(\Rightarrow\) cheaper to store

Popular Kernel Functions

• Polynomials: \(K(\mathbf{x}^t,\mathbf{x}) = (\mathbf{x}^T \mathbf{x}^t + 1)^q \)
• Radial-basis: \(K(\mathbf{x}^t,\mathbf{x}) = \exp{\left[ -\frac{\norm{\mathbf{x}^t-\mathbf{x}}^2}{2s^2} \right]}\)
• General distance: \(K(\mathbf{x}^t,\mathbf{x}) = \exp{\left[ -\frac{\mathcal{D}(\mathbf{x}^t,\mathbf{x})}{2s^2} \right]}\), where \(\mathcal{D}\) is a distince function
• Sigmoidal: \(K(\mathbf{x}^t,\mathbf{x}) = \tanh{(2 \mathbf{x}^T \mathbf{x}^t + 1)}\)
• Given two existing kernels \(K_1(\mathbf{x},\mathbf{y}), K_2(\mathbf{x},\mathbf{y}) \), we can generate new ones:
  • \(K(\mathbf{x},\mathbf{y}) = cK_1(\mathbf{x},\mathbf{y})\)
  • \(K(\mathbf{x},\mathbf{y}) = K_1(\mathbf{x},\mathbf{y})+K_2(\mathbf{x},\mathbf{y})\)
  • \(K(\mathbf{x},\mathbf{y}) = K_1(\mathbf{x},\mathbf{y}) \cdot K_2(\mathbf{x},\mathbf{y})\)

Kernel PCA

• Regular Principal Components Analysis: examine eigenvectors with largest eigenvalues
• Analyze eigenvalues, eigenvectors of kernel matrix as a dimensionality reduction
• You get to choose the number of dimensions you want to analyze! Allows you to adjust resolution of problem
• Can be applied similarly to linear dimensionality reduction (LDA)

Conclusion and Goals

• Classification problem
• Solution: support vectors and SVM
• Data's not perfect! Soft margin
• Kernel methods and dimensionality reduction

Ultimately, we want to analyze big data and characterize it with small number of dimensions. This is the motivation behind using SVMs and kernel methods.

Thanks for listening!

Here are some more resources:

• Introduction to Machine Learning, by Ethem Alpaydin
• Pattern Recognition and Machine Learning, by Christopher M. Bishop
• Concise Linear Algebra (a review of basic linear techniques)