Optimization for Support Vector Machines (SVM)

18. Optimization for Support Vector Machines (SVM)

Support Vector Machines (SVM) are powerful supervised learning models used for classification and regression tasks. The key idea behind SVM is to find the hyperplane that best separates data points of different classes. In binary classification, the goal is to maximize the margin between the two classes, where the margin is defined as the distance between the hyperplane and the closest points from each class (the support vectors).

The optimization problem in SVM involves finding this optimal hyperplane by solving a convex optimization problem.

---

18.1 SVM Objective

Given a dataset $\{({\mathbf{x}}_i,y_i)\}$, where ${\mathbf{x}}_i\in {\mathbb{R}}^n$ are the feature vectors and $y_i\in \{-1,1\}$ are the class labels, the objective is to find a hyperplane:

$${\mathbf{w}}^T\mathbf{x}+b=0$$

That separates the two classes with the maximum margin. The margin is defined as the perpendicular distance from the hyperplane to the nearest points from either class (the support vectors).

The optimization problem for the SVM is formulated as:

$$\underset{\mathbf{w},b}{min}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$$

Subject to the constraints:

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

Where:
- $\mathbf{w}$ is the weight vector perpendicular to the hyperplane,
- $b$ is the bias term (offset of the hyperplane from the origin),
- $y_i$ is the class label of the $i$-th point, which must satisfy the constraint $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$ to ensure the points are correctly classified.

The objective function $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$ corresponds to maximizing the margin, since the margin is given by $\frac{1}{\Vert \mathbf{w}\Vert }$.

---

18.2 Primal Form of SVM Optimization

The optimization problem can be written in its primal form as:

$$\underset{\mathbf{w},b}{min}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$$

subject to:

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1\text{for all}i$$

This is a quadratic optimization problem with linear constraints.

---

18.3 Lagrange Multipliers and Dual Form

To solve the primal problem, we introduce Lagrange multipliers to incorporate the constraints into the objective function. The Lagrangian for this problem is:

$$\mathcal{L}(\mathbf{w},b,\alpha )=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^N{\alpha }_i(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)$$

Where ${\alpha }_i$ are the Lagrange multipliers corresponding to each constraint.

The next step is to maximize the Lagrangian with respect to ${\alpha }_i$, and minimize it with respect to $\mathbf{w}$ and $b$. After differentiating and setting the gradient to zero, we obtain the dual form of the SVM optimization problem.

---

18.4 Dual Form of SVM Optimization

By solving the Lagrangian, we get the dual form of the SVM optimization problem, which is:

$$\underset{\alpha }{max}\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$$

subject to:

$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

and

$${\alpha }_i\ge 0,\mathrm{\forall }i$$

Where:
- ${\alpha }_i$ are the Lagrange multipliers,
- $y_i$ are the class labels,
- ${\mathbf{x}}_i$ are the feature vectors.

This is a quadratic programming problem, and solving it will give us the values of ${\alpha }_i$, which are used to compute the weight vector $\mathbf{w}$ and the bias $b$.

---

18.5 Support Vectors and Decision Boundary

• The support vectors are the data points that lie on the margin boundaries, and they are the only points that affect the position of the decision boundary.
• The weight vector $\mathbf{w}$ can be computed as:

[
\mathbf{w} = \sum_{i=1}^{N} \alpha_i y_i \mathbf{x}_i
]

• The bias $b$ can be computed using any support vector ${\mathbf{x}}_i$ as:

[
b = y_i - \mathbf{w}^T \mathbf{x}_i
]

The decision boundary is given by:

$${\mathbf{w}}^T\mathbf{x}+b=0$$

---

18.6 Soft Margin SVM

In practice, the data may not be perfectly linearly separable. To account for this, we introduce a soft margin that allows some misclassifications. This is done by introducing slack variables ${\xi }_i$, which represent the amount of violation of the margin constraint for each data point.

The soft margin SVM optimization problem becomes:

$$\underset{\mathbf{w},b,\xi }{min}\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^N{\xi }_i$$

subject to:

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i,\mathrm{\forall }i$$

and

$${\xi }_i\ge 0,\mathrm{\forall }i$$

Where $C$ is a regularization parameter that controls the trade-off between maximizing the margin and minimizing the classification error.

---

18.7 Nonlinear SVM (Kernel Trick)

When the data is not linearly separable in its original feature space, we can map it into a higher-dimensional feature space using a kernel function. The most common kernel functions are:

1. Polynomial Kernel:

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=({\mathbf{x}}_i^T{\mathbf{x}}_j+1{)}^d$$

1. Radial Basis Function (RBF) Kernel:

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\frac{\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2}{2{\sigma }^2})$$

1. Sigmoid Kernel:

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh (\alpha {\mathbf{x}}_i^T{\mathbf{x}}_j+c)$$

The kernel trick allows us to compute the dot product in the higher-dimensional space without explicitly transforming the data, making it computationally efficient.

In the dual form, the kernel function replaces the dot product ${\mathbf{x}}_i^T{\mathbf{x}}_j$, and the optimization problem remains the same.

---

18.8 SVM Training and Classification

1. Training: Use the dual form of the SVM optimization problem and solve it using quadratic programming (QP) solvers. This will provide the values of the Lagrange multipliers ${\alpha }_i$.

2. Classification: Once the parameters $\mathbf{w}$ and $b$ are computed, classify new data points by evaluating the decision function:

$$f(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b$$

If $f(\mathbf{x})>0$, classify the data point as $+1$, and if $f(\mathbf{x})<0$, classify it as $-1$.

---

18.9 Practice Problems

1. Primal SVM: Formulate the primal optimization problem for an SVM with the following dataset:

[
\mathbf{X} = $$\left[\begin{array}{ccccc}2& 33& 44& 55& 6\end{array}\right]$$, \quad \mathbf{y} = $$\left[\begin{array}{c}11-1-1\end{array}\right]$$
]

Solve it using the quadratic programming approach.

1. Soft Margin SVM: Given the dataset:

[
\mathbf{X} = \begin{bmatrix}
1 & 1 \
2 & 2 \
3 &

3 \
4 & 4
\end{bmatrix}, \quad \mathbf{y} = $$\left[\begin{array}{c}1-11-1\end{array}\right]$$
]

Solve the soft margin SVM optimization problem for $C=1$.

---

This concludes the overview of Optimization for Support Vector Machines. Would you like to dive deeper into any specific part, or do you want to continue with another topic?