Method of Lagrange Multipliers: The Theory Behind Support Vector Machines (Part 2: The Non-Separable Case)

 This tutorial is an extension of Method Of Lagrange Multipliers: The Theory Behind Support Vector Machines (Part 1: The Separable Case)) and explains the non-separable case. In real life problems positive and negative training examples may not be completely separable by a linear decision boundary. This tutorial explains how a soft margin can be built that tolerates a certain amount of errors.

In this tutorial, we’ll cover the basics of a linear SVM. We won’t go into details of non-linear SVMs derived using the kernel trick. The content is enough to understand the basic mathematical model behind an SVM classifier.

After completing this tutorial, you will know:

• Concept of a soft margin
• How to maximize the margin while allowing mistakes in classification
• How to formulate the optimization problem and compute the Lagrange dual

Let’s get started.

Method Of Lagrange Multipliers: The Theory Behind Support Vector Machines (Part 2: The Non-Separable Case).
Photo by Shakeel Ahmad, some rights reserved.

Tutorial Overview

This tutorial is divided into 2 parts; they are:

1. The solution of the SVM problem for the case where positive and negative examples are not linearly separable
   1. The separating hyperplane and the corresponding relaxed constraints
   2. The quadratic optimization problem for finding the soft margin
2. A worked example

Pre-requisites

For this tutorial, it is assumed that you are already familiar with the following topics. You can click on the individual links to get more information.

• A Gentle Introduction to Optimization / Mathematical Programming
• A Gentle Introduction To Method Of Lagrange Multipliers
• Lagrange Multiplier Approach with Inequality Constraints
• Method Of Lagrange Multipliers: The Theory Behind Support Vector Machines (Part 1: The Separable Case))

Notations Used In This Tutorial

This is a continuation of Part 1, so the same notations will be used.

• $�$: Total training points
• $�$: Data point, which is an $�$-dimensional vector. Each dimension is indexed by j.
• ${�}^{+}$: Positive example
• ${�}^{-}$: Negative example
• $�$: Subscript used to index the training points. $0\le �<�$
• $�$: Subscript to index a dimension of the data point. $1\le �\le �$
• $�$: Label of data points. It is an m-dimensional vector
• $�$: Transpose operator
• $�$: Weight vector denoting the coefficients of the hyperplane. It is an $�$-dimensional vector
• $�$: Vector of Lagrange multipliers, an $�$-dimensional vector
• $�$: Vector of Lagrange multipliers, again an $�$-dimensional vector
• $�$: Error in classification. An $�$-dimensional vector

Want to Get Started With Calculus for Machine Learning?

Take my free 7-day email crash course now (with sample code).

Click to sign-up and also get a free PDF Ebook version of the course.

The Separating Hyperplane and Relaxing the Constraints

Let’s find a separating hyperplane between the positive and negative examples. Just to recall, the separating hyperplane is given by the following expression, with ${�}_{�}$ being the coefficients and ${�}_0$ being the arbitrary constant that determines the distance of the hyperplane from the origin:

$${�}^{�}{�}_{�}+{�}_0=0$$

As we allow positive and negative examples to lie on the wrong side of the hyperplane, we have a set of relaxed constraints. Defining ${�}_{�}\ge 0,\mathrm{\forall }�$, for positive examples we require:

$${�}^{�}{�}_{�}^{+}+{�}_0\ge 1–{�}_{�}$$

Also for negative examples we require:

$${�}^{�}{�}_{�}^{-}+{�}_0\le -1+{�}_{�}$$

Combining the above two constraints by using the class label ${�}_{�}\in \{-1,+1\}$ we have the following constraint for all points:

$${�}_{�}({�}^{�}{�}_{�}+{�}_0)\ge 1–{�}_{�}$$

The variable $�$ allows more flexibility in our model. It has the following interpretations:

1. ${�}_{�}=0$: This means that ${�}_{�}$ is correctly classified and this data point is on the correct side of the hyperplane and away from the margin.
2. $0<{�}_{�}<1$: When this condition is met, ${�}_{�}$ lies on the correct side of the hyperplane but inside the margin.
3. ${�}_{�}>0$: Satisfying this condition implies that ${�}_{�}$ is misclassified.

Hence, $�$ quantifies the errors in the classification of training points. We can define the soft error as:

$${�}_{����}=\sum _{�}{�}_{�}$$

The Quadratic Programming Problem

We are now in a position to formulate the objective function along with the constraints on it. We still want to maximize the margin, i.e., we want to minimize the norm of the weight vector. Along with this, we also want to keep the soft error as small as possible. Hence, now our new objective function is given by the following expression, with $�$ being a user defined constant and represents the penalty factor or the regularization constant.

$$\frac{1}{2}||�|{|}^2+�\sum _{�}{�}_{�}$$

The overall quadratic programming problem is, therefore, given by the following expression:

$$\underset{�}{min}\frac{1}{2}||�|{|}^2+�\sum _{�}{�}_{�}\text{ subject to }{�}_{�}({�}^{�}{�}_{�}+{�}_0)\ge +1–{�}_{�},\mathrm{\forall }�\text{ and }{�}_{�}\ge 0,\mathrm{\forall }�$$

The Role of C, the Regularization Constant

To understand the penalty factor $�$, consider the product term $�\sum _{�}{�}_{�}$, which has to be minimized. If C is kept large, then the soft margin $\sum _{�}{�}_{�}$ would automatically be small. If $�$ is close to zero, then we are allowing the soft margin to be large making the overall product small.

In short, a large value of $�$ means we have a high penalty on errors and hence our model is not allowed to make too many mistakes in classification. A small value of $�$ allows the errors to grow.

Solution Via The Method Of Lagrange Multipliers

Let’s use the method of Lagrange multipliers to solve the quadratic programming problem that we formulated earlier. The Lagrange function is given by:

$$�(�,{�}_0,�,�)=\frac{1}{2}||�|{|}^2+\sum _{�}{�}_{�}({�}_{�}({�}^{�}{�}_{�}+{�}_0)–1+{�}_{�})–\sum _{�}{�}_{�}{�}_{�}$$

To solve the above, we set the following:
$$\begin{gathered} \frac{��}{��}=0, \\ \frac{��}{��}=0, \\ \frac{��}{�{�}_0}=0, \\ \frac{��}{��}=0 \end{gathered}$$

Solving the above gives us:
$$�=\sum _{�}{�}_{�}{�}_{�}{�}_{�}$$
and
$$0=�–{�}_{�}–{�}_{�}$$

Substitute the above in the Lagrange function gives us the following optimization problem, also called the dual:

$${�}_{�}=-\frac{1}{2}\sum _{�}\sum _{�}{�}_{�}{�}_{�}{�}_{�}{�}_{�}({�}_{�}{)}^{�}({�}_{�})+\sum _{�}{�}_{�}$$

We have to maximize the above subject to the following constraints:

$$\begin{gathered} \sum _{�}{�}_{�}{�}_{�}=0 \\ \text{ and }0\le {�}_{�}\le �,\mathrm{\forall }� \end{gathered}$$

Similar to the separable case, we have an expression for $�$ in terms of Lagrange multipliers. The objective function involves no $�$ term. There is a Lagrange multiplier $�$ and $�$ associated with each data point.

Interpretation of the Mathematical Model and Computation of ${�}_0$

Following cases are true for each training data point ${�}_{�}$:

• ${�}_{�}=0$: The ith training point lies on the correct side of the hyperplane away from the margin. This point plays no role in the classification of a test point.
• $0<{�}_{�}<�$: The ith training point is a support vector and lies on the margin. For this point ${�}_{�}=0$ and ${�}_{�}({�}^{�}{�}_{�}+{�}_0)=1$ and hence it can be used to compute ${�}_0$. In practice ${�}_0$ is computed from all support vectors and an average is taken.
• ${�}_{�}=�$: The ith training point is either inside the margin on the correct side of the hyperplane or this point is on the wrong side of the hyperplane.

The picture below will help you understand the above concepts:

Deciding The Classification of a Test Point

The classification of any test point $�$ can be determined using this expression:

$$�(�)=\sum _{�}{�}_{�}{�}_{�}{�}^{�}{�}_{�}+{�}_0$$

A positive value of $�(�)$ implies $�\in +1$ and a negative value means $�\in -1$. Hence, the predicted class of a test point is the sign of $�(�)$.

Karush-Kuhn-Tucker Conditions

Karush-Kuhn-Tucker (KKT) conditions are satisfied by the above constrained optimization problem as given by:
$$\begin{array}{rcl}{�}_{�}& \ge & 0\\ {�}_{�}�({�}_{�})-1+{�}_{�}& \ge & 0\\ {�}_{�}({�}_{�}�({�}_{�})-1+{�}_{�})& =& 0\\ {�}_{�}\ge 0\\ {�}_{�}\ge 0\\ {�}_{�}{�}_{�}=0\end{array}$$

A Solved Example

Shown above is a solved example for 2D training points to illustrate all the concepts. A few things to note about this solution are:

• The training data points and their corresponding labels act as input
• The user defined constant $�$ is set to 10
• The solution satisfies all the constraints, however, it is not the optimal solution
• We have to make sure that all the $�$ lie between 0 and C
• The sum of alphas of all negative examples should equal the sum of alphas of all positive examples
• The points (1,2), (2,1) and (-2,-2) lie on the soft margin on the correct side of the hyperplane. Their values have been arbitrarily set to 3, 3 and 6 respectively to balance the problem and satisfy the constraints.
• The points with $�=�=10$ lie either inside the margin or on the wrong side of the hyperplane

Further Reading

This section provides more resources on the topic if you are looking to go deeper.

Books

• Pattern Recognition and Machine Learning by Christopher M. Bishop

Articles

• Support Vector Machines for Machine Learning
• A Tutorial on Support Vector Machines for Pattern Recognition by Christopher J.C. Burges

Summary

In this tutorial, you discovered the method of Lagrange multipliers for finding the soft margin in an SVM classifier.

Specifically, you learned:

• How to formulate the optimization problem for the non-separable case
• How to find the hyperplane and the soft margin using the method of Lagrange multipliers
• How to find the equation of the separating hyperplane for very simple problems

Do you have any questions about SVMs discussed in this post? Ask your questions in the comments below and I will do my best to answer.