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

This tutorial is designed for anyone looking for a deeper understanding of how Lagrange multipliers are used in building up the model for support vector machines (SVMs). SVMs were initially designed to solve binary classification problems and later extended and applied to regression and unsupervised learning. They have shown their success in solving many complex machine learning classification problems.

In this tutorial, we’ll look at the simplest SVM that assumes that the positive and negative examples can be completely separated via a linear hyperplane.

After completing this tutorial, you will know:

• How the hyperplane acts as the decision boundary
• Mathematical constraints on the positive and negative examples
• What is the margin and how to maximize the margin
• Role of Lagrange multipliers in maximizing the margin
• How to determine the separating hyperplane for the separable case

Let’s get started.

This tutorial is divided into three parts; they are:

1. Formulation of the mathematical model of SVM
2. Solution of finding the maximum margin hyperplane via the method of Lagrange multipliers
3. Solved example to demonstrate all concepts

Notations Used In This Tutorial

• $�$: Total training points.
• $�$: Total features or the dimensionality of all data points
• $�$: Data point, which is an n-dimensional vector.
• ${�}^{+}$: Data point labelled as +1.
• ${�}^{-}$: Data point labelled as -1.
• $�$: Subscript used to index the training points. $0\le �<�$
• $�$: Subscript used to index the individual dimension of a data point. $1\le �\le �$
• $�$: Label of a data point.
• T: Transpose operator.
• $�$: Weight vector denoting the coefficients of the hyperplane. It is also an n-dimensional vector.
• $�$: Lagrange multipliers, one per each training point. This is an m-dimensional vector.
• $�$: Perpendicular distance of a data point from the decision boundary.

The Hyperplane As The Decision Boundary

The support vector machine is designed to discriminate data points belonging to two different classes. One set of points is labelled as +1 also called the positive class. The other set of points is labeled as -1 also called the negative class. For now, we’ll make a simplifying assumption that points from both classes can be discriminated via linear hyperplane.

The SVM assumes a linear decision boundary between the two classes and the goal is to find a hyperplane that gives the maximum separation between the two classes. For this reason, the alternate term maximum margin classifier is also sometimes used to refer to an SVM. The perpendicular distance between the closest data point and the decision boundary is referred to as the margin. As the margin completely separates the positive and negative examples and does not tolerate any errors, it is also called the hard margin.

The mathematical expression for a hyperplane is given below with ${�}_{�}$ being the coefficients and ${�}_0$ being the arbitrary constant that determines the distance of the hyperplane from the origin:

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

For the ith 2-dimensional point $({�}_{�1},{�}_{�2})$ the above expression is reduced to:
$${�}_1{�}_{�1}+{�}_2{�}_{�2}+{�}_0=0$$

Mathematical Constraints On Positive and Negative Data Points

As we are looking to maximize the margin between positive and negative data points, we would like the positive data points to satisfy the following constraint:

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

Similarly, the negative data points should satisfy:

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

We can use a neat trick to write a uniform equation for both set of points by using ${�}_{�}\in \{-1,+1\}$ to denote the class label of data point ${�}_{�}$:

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

The Maximum Margin Hyperplane

The perpendicular distance ${�}_{�}$ of a data point ${�}_{�}$ from the margin is given by:

$${�}_{�}=\frac{|{�}^{�}{�}_{�}+{�}_0|}{||�||}$$

To maximize this distance, we can minimize the square of the denominator to give us a quadratic programming problem given by:

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

Solution Via The Method Of Lagrange Multipliers

To solve the above quadratic programming problem with inequality constraints, we can use the method of Lagrange multipliers. The Lagrange function is therefore:

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

To solve the above, we set the following:

$$\begin{gathered} \frac{��}{��}=0, \\ \frac{��}{��}=0, \\ \frac{��}{�{�}_0}=0 \end{gathered}$$

Plugging 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:

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

The nice thing about the above is that we have an expression for $�$ in terms of Lagrange multipliers. The objective function involves no $�$ term. There is a Lagrange multiplier associated with each data point. The computation of ${�}_0$ is also explained later.

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 

Karush-Kuhn-Tucker Conditions

Also, 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\end{array}$$

Interpretation Of KKT Conditions

The KKT conditions dictate that for each data point one of the following is true:

• The Lagrange multiplier is zero, i.e., ${�}_{�}=0$. This point, therefore, plays no role in classification

OR

• ${�}_{�}�({�}_{�})=1$ and ${�}_{�}>0$: In this case, the data point has a role in deciding the value of $�$. Such a point is called a support vector.

Computing w_0

For ${�}_0$, we can select any support vector ${�}_{�}$ and solve

$${�}_{�}�({�}_{�})=1$$

giving us:
$${�}_{�}(\sum _{�}{�}_{�}{�}_{�}{�}_{�}^{�}{�}_{�}+{�}_0)=1$$

A Solved Example

To help you understand the above concepts, here is a simple arbitrarily solved example. Of course, for a large number of points you would use an optimization software to solve this. Also, this is one possible solution that satisfies all the constraints. The objective function can be maximized further but the slope of the hyperplane will remain the same for an optimal solution. Also, for this example, ${�}_0$ was computed by taking the average of ${�}_0$ from all three support vectors.

This example will show you that the model is not as complex as it looks.

For the above set of points, we can see that (1,2), (2,1) and (0,0) are points closest to the separating hyperplane and hence, act as support vectors. Points far away from the boundary (e.g. (-3,1)) do not play any role in determining the classification of the points.

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
• Thomas’ Calculus, 14th edition, 2017  (based on the original works of George B. Thomas, revised by Joel Hass, Christopher Heil, Maurice Weir)

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 how to use the method of Lagrange multipliers to solve the problem of maximizing the margin via a quadratic programming problem with inequality constraints.

Specifically, you learned:

• The mathematical expression for a separating linear hyperplane
• The maximum margin as a solution of a quadratic programming problem with inequality constraint
• How to find a linear hyperplane between positive and negative examples using the method of Lagrange multipliers

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