Simple Linear SVM with Hard Margin

Introduction

A Linear Support Vector Machine (Linear SVM) is used to classify data into two classes using a straight decision boundary.

For example, suppose we have two classes:

• Class $+1$ : ○
• Class $-1$ : ×

              ○   ○
           ○

        -----------------  ← Decision boundary

      ×
   ×     ×

Many straight lines may separate these two classes correctly.

The main idea of SVM is:

Among all possible separating lines, choose the one with the maximum margin.

---

 What is Hard-Margin SVM?

A Hard-Margin SVM assumes that:

1. The two classes are perfectly separable.
2. There is no overlap between the classes.
3. Every training point must be correctly classified.

For example:

Class -1                         Class +1

   ×       ×                         ○       ○
       ×                                 ○


              |        |        |
              |        |        |
         Margin     Decision    Margin
                     Boundary

The SVM finds the decision boundary that maximizes the distance from the nearest points of both classes.

---

 What Is a Hyperplane?

A hyperplane is the mathematical decision boundary used by SVM.

For two features:

$$x_1,\quad x_2$$

the equation is:

$$\boxed{w_1x_1+w_2x_2+b=0}$$

This represents a line.

Using vector notation:

$$\boxed{w^Tx+b=0}$$

where:

$$w= \begin{bmatrix} w_1\\ w_2 \end{bmatrix}$$

and

$$x= \begin{bmatrix} x_1\\ x_2 \end{bmatrix}$$

---

Meaning of the Terms

Symbol	Meaning
$x$	Input feature vector
$w$	Weight vector
$b$	Bias
$w^Tx+b$	Decision function

The equation

$$\boxed{w^Tx+b=0}$$

represents the decision boundary.

---

Classification Using the Hyperplane

Define the decision function:

$$\boxed{f(x)=w^Tx+b}$$

Now there are three possibilities.

Case 1

If:

$$f(x)>0$$

then predict:

$$\boxed{+1}$$

---

Case 2

If:

$$f(x)<0$$

then predict:

$$\boxed{-1}$$

---

Case 3

If:

$$f(x)=0$$

the point lies exactly on the decision boundary.

Therefore:

y^​=sign(wTx+b)​

Linear Decision Boundary

Suppose each data point has two features:

$$x=(x_1,x_2)$$

A linear decision boundary is written as:

$$\boxed{w_1x_1+w_2x_2+b=0}$$

Using vector notation:

$$\boxed{w^Tx+b=0}$$

where:

• $x$ = input vector
• $w$ = weight vector
• $b$ = bias

For two dimensions:

$$w= \begin{bmatrix} w_1\\ w_2 \end{bmatrix}$$

and

$$x= \begin{bmatrix} x_1\\ x_2 \end{bmatrix}$$

Therefore:

$$w^Tx=w_1x_1+w_2x_2$$

---

 Classification Rule

The SVM calculates:

$$\boxed{f(x)=w^Tx+b}$$

Then:

If

$$f(x)>0$$

the point belongs to:

$$\boxed{+1}$$

If

$$f(x)<0$$

the point belongs to:

$$\boxed{-1}$$

Therefore:

$$\boxed{\hat y=\operatorname{sign}(w^Tx+b)}$$

---

Example of Classification

Suppose:

$$w= \begin{bmatrix} 1\\ 0 \end{bmatrix}$$

and

$$b=-3$$

Then:

$$f(x)=w^Tx+b$$

becomes:

$$\boxed{f(x)=x_1-3}$$

The decision boundary is:

$$x_1-3=0$$

Therefore:

$$\boxed{x_1=3}$$

Now consider a point:

$$x=(5,2)$$

Then:

$$f(x)=5-3=2$$

Since:

$$2>0$$

the predicted class is:

$$\boxed{+1}$$

Now consider:

$$x=(1,4)$$

Then:

$$f(x)=1-3=-2$$

Therefore:

$$\boxed{-1}$$

---

What are Support Vectors?

Consider the following points:

             ○       ○
       ○

---------------------------

            ×       ×
       ×

Not all points are equally important.

The points closest to the separating boundary are the most important.

             ○       ○
        [○]

===========================

        [×]
             ×       ×

The points inside brackets are:

$$\boxed{\text{Support Vectors}}$$

---

Simple Definition

Support vectors are the training points closest to the decision boundary.

They play a crucial role in determining the optimal separating hyperplane.

---

The Margin Boundaries

The decision boundary is:

$$\boxed{w^Tx+b=0}$$

For Hard-Margin SVM, we define two additional parallel boundaries:

Positive margin boundary

$$\boxed{w^Tx+b=1}$$

Negative margin boundary

$$\boxed{w^Tx+b=-1}$$

Thus, we have:

             Class +1

        wᵀx+b = 1
        -------------------

        wᵀx+b = 0
        ===================

        wᵀx+b = -1
        -------------------

             Class -1

The support vectors lie on the two margin boundaries.

Class +1

       ○      ○
          ○

wᵀx+b=+1  --------------------

                ↑
                │ Margin
                ↓

wᵀx+b=0   ====================
             Decision Boundary

                ↑
                │ Margin
                ↓

wᵀx+b=-1  --------------------

          ×
       ×      ×

Class -1

The points lying on:

$$w^Tx+b=+1$$

and

$$w^Tx+b=-1$$

are the support vectors.

---

Hard-Margin Classification Constraints

Suppose the class labels are:

$$\boxed{y_i\in\{-1,+1\}}$$

For a point belonging to Class $+1$:

$$y_i=+1$$

we require:

$$\boxed{w^Tx_i+b\geq1}$$

For a point belonging to Class $-1$:

$$y_i=-1$$

we require:

$$\boxed{w^Tx_i+b\leq-1}$$

---

 Combining Both Constraints

We can combine the two constraints into one equation:

$$\boxed{ y_i(w^Tx_i+b)\geq1 }$$

Let us verify this.

---

For Class $+1$

If:

$$y_i=+1$$

then:

$$(+1)(w^Tx_i+b)\geq1$$

Therefore:

$$\boxed{w^Tx_i+b\geq1}$$

---

For Class $-1$

If:

$$y_i=-1$$

then:

$$(-1)(w^Tx_i+b)\geq1$$

Therefore:

$$\boxed{w^Tx_i+b\leq-1}$$

Thus:

$$\boxed{ y_i(w^Tx_i+b)\geq1 }$$

ensures that all points are correctly classified.

---

Mathematical Formulation of Hard-Margin SVM

The goal of SVM is to find:

• the weight vector $w$
• the bias $b$

such that the margin is maximum.

Distance from a Point to a Hyperplane

Consider the hyperplane:

$$\boxed{w^Tx+b=0}$$

The perpendicular distance of a point $x$ from this hyperplane is:

$$\boxed{ \frac{|w^Tx+b|}{||w||} }$$

where:

$$||w||=\sqrt{w_1^2+w_2^2+\cdots+w_n^2}$$

is the magnitude (Euclidean norm) of $w$.

---

Deriving the Margin Width

The two margin boundaries are:

$$w^Tx+b=+1$$

and

$$w^Tx+b=-1$$

The distance between them is:

$$\boxed{ \frac{2}{||w||} }$$

Therefore:

$$\boxed{\text{Margin Width}=\frac{2}{||w||}}$$

The standard hard-margin SVM formulation follows directly from maximizing this margin while satisfying the classification constraints.

---

The Main Mathematical Idea of SVM

SVM wants to maximize:

$$\boxed{ \frac{2}{||w||} }$$

Since $2$ is constant:

$$\text{Maximize }\frac{2}{||w||}$$

is equivalent to:

$$\text{Minimize }||w||$$

For mathematical convenience, we minimize:

$$\boxed{ \frac{1}{2}||w||^2 }$$

---

Hard-Margin Linear SVM Optimization Problem

Now we can write the complete mathematical model.

Objective Function

$$\boxed{ \min_{w,b}\frac{1}{2}||w||^2 }$$

Subject to

$$\boxed{ y_i(w^Tx_i+b)\geq1 }$$

for every training example.

---

⭐ Complete Hard-Margin SVM Formula

$$\boxed{ \begin{aligned} \text{Minimize:}\quad& \frac{1}{2}||w||^2\\ \text{Subject to:}\quad& y_i(w^Tx_i+b)\geq1 \end{aligned} }$$

This is called the primal formulation of Hard-Margin SVM

---

Why Do We Minimize $\frac12\|w\|^2$?

The width of the margin is:

$$\boxed{ \text{Margin Width}=\frac{2}{\|w\|} }$$

Therefore, to maximize:

$$\frac{2}{\|w\|}$$

we need to minimize:

$$\|w\|$$

For mathematical convenience, we minimize:

$$\boxed{ \frac12\|w\|^2 }$$

Thus:

Maximizing the margin is equivalent to minimizing $\frac12\|w\|^2$.

---

Worked Example: Finding the Decision Boundary

Consider the following training data.

Class $-1$

$$x_1=(1,1)$$ $$x_2=(2,1)$$

Class $+1$

$$x_3=(4,1)$$ $$x_4=(5,1)$$

The data can be visualized as:

x₂
↑

1       ×       ×               ○       ○

        1       2               4       5

+------------------------------------------------→ x₁

---

Step 1: Identify the Closest Points

The closest points from the two classes are:

$$(2,1)$$

and

$$(4,1)$$

These are the:

$$\boxed{\text{Support Vectors}}$$

---

Step 2: Find the Decision Boundary

The boundary should lie halfway between:

$$x_1=2$$

and

$$x_1=4$$

Therefore:

$$\frac{2+4}{2}=3$$

So the decision boundary is:

$$\boxed{x_1=3}$$

---

Scaling the Equation for SVM

The simple decision boundary is:

$$x_1-3=0$$

However, for the standard SVM formulation, we want the support vectors to satisfy:

$$w^Tx+b=+1$$

and

$$w^Tx+b=-1$$

The two support vectors are at:

• $x_1=2$, Class $-1$
• $x_1=4$, Class $+1$

Let:

$$f(x)=wx_1+b$$

We require:

For $x_1=4$

$$4w+b=1$$

For $x_1=2$

$$2w+b=-1$$

Subtracting:

$$(4w+b)-(2w+b)=1-(-1)$$ $$2w=2$$

Therefore:

$$\boxed{w=1}$$

Substituting into:

$$4w+b=1$$

we get:

$$4+b=1$$

Therefore:

$$\boxed{b=-3}$$

Thus, the SVM decision function is:

$$\boxed{f(x)=x_1-3}$$

---

Checking the Support Vectors

Support Vector $(4,1)$

$$f(x)=4-3=1$$

Therefore:

$$\boxed{w^Tx+b=+1}$$

Correct.

---

Support Vector $(2,1)$

$$f(x)=2-3=-1$$

Therefore:

$$\boxed{w^Tx+b=-1}$$

Correct.

---

Checking the Hard-Margin Constraints

The constraint is:

$$\boxed{ y_i(w^Tx_i+b)\geq1 }$$

Let's check every point.

Point	Class $y_i$	$f(x)$	$y_if(x)$	Constraint
$(1,1)$	-1	-2	2	✓
$(2,1)$	-1	-1	1	✓
$(4,1)$	+1	1	1	✓
$(5,1)$	+1	2	2	✓

All points satisfy:

$$\boxed{y_if(x)\geq1}$$

Therefore, the data is correctly separated with a hard margin.

---

Margin Boundaries in the Example

The decision boundary is:

$$x_1-3=0$$

Therefore:

$$\boxed{x_1=3}$$

The positive margin boundary is:

$$x_1-3=1$$

Therefore:

$$\boxed{x_1=4}$$

The negative margin boundary is:

$$x_1-3=-1$$

Therefore:

$$\boxed{x_1=2}$$

Thus:

Class -1              Decision             Class +1

 ×        ×              |              ○        ○
          ↑              ↑              ↑
       x₁ = 2         x₁ = 3         x₁ = 4

       Support        Decision        Support
        Vector        Boundary         Vector

---

Calculating the Margin

We have:

$$w= \begin{bmatrix} 1\\ 0 \end{bmatrix}$$

Therefore:

$$\|w\|=\sqrt{1^2+0^2}=1$$

The total margin width is:

$$\boxed{ \frac{2}{\|w\|} }$$

Therefore:

$$\boxed{ \frac{2}{1}=2 }$$

So the distance between the two margin boundaries is:

$$\boxed{2}$$

The decision boundary is exactly in the middle.

Therefore, the distance from the decision boundary to each support vector is:

$$\boxed{1}$$

---

Classifying New Points

The decision function is:

$$\boxed{ f(x)=x_1-3 }$$

The classification rule is:

$$\boxed{ \hat y=\operatorname{sign}(x_1-3) }$$

---

Example 1

Consider:

$$x=(6,2)$$

Then:

$$f(x)=6-3=3$$

Since:

$$3>0$$

we predict:

$$\boxed{+1}$$

---

Example 2

Consider:

$$x=(1.5,4)$$

Then:

$$f(x)=1.5-3=-1.5$$

Since:

$$-1.5<0$$

we predict:

$$\boxed{-1}$$

---

Limitation of Hard-Margin SVM

Real-world data is often noisy.

Consider:

          ○ ○ ○

             ×   ← Outlier

---------------------

       × × ×

One unusual point can make perfect separation difficult or impossible.

Hard-Margin SVM can therefore be unsuitable for noisy or overlapping data and can be sensitive to outliers.

So we need a more practical approach.( Soft Margin SVM)

Final Summary

Hard-Margin Linear SVM finds a straight decision boundary that perfectly separates two classes and chooses the boundary with the maximum possible margin. The closest points that determine this boundary are called support vectors.

The complete idea of Hard-Margin Linear SVM can be summarized as follows:

Training Data

$$(x_i,y_i)$$

where:

$$\boxed{y_i\in\{-1,+1\}}$$

Decision Function

$$\boxed{ f(x)=w^Tx+b }$$

Decision Boundary

$$\boxed{ w^Tx+b=0 }$$

Margin Boundaries

$$\boxed{ w^Tx+b=+1 }$$ $$\boxed{ w^Tx+b=-1 }$$

Classification Constraint

$$\boxed{ y_i(w^Tx_i+b)\geq1 }$$

Margin Width

$$\boxed{ \frac{2}{\|w\|} }$$

Optimization Problem

$$\boxed{ \begin{aligned} \text{Minimize:}\quad& \frac12\|w\|^2\\ \text{Subject to:}\quad& y_i(w^Tx_i+b)\geq1 \end{aligned} }$$

---

Example Problem:

Finding an SVM Classifier for the Given Data

Given data:

$X_1$	$X_2$	Class
2	2	0
4	5	1
7	4	1

We have two classes:

• Class $0$: $(2,2)$
• Class $1$: $(4,5)$, $(7,4)$

To use the standard hard-margin SVM formulation, let us convert the class labels:

$$0\rightarrow -1,\qquad 1\rightarrow +1$$

Thus:

$$\begin{aligned} (2,2)&\rightarrow -1\\ (4,5)&\rightarrow +1\\ (7,4)&\rightarrow +1 \end{aligned}$$

---

1. Identify the Support Vectors

Geometrically, the negative point is:

$$A=(2,2)$$

The two positive points are:

$$B=(4,5),\qquad C=(7,4)$$

The closest positive point to $A$ is $B=(4,5)$.

Distance between $A$ and $B$:

$$d=\sqrt{(4-2)^2+(5-2)^2}$$ $$=\sqrt{4+9}$$ $$=\sqrt{13}$$

Distance between $A$ and $C$:

$$d=\sqrt{(7-2)^2+(4-2)^2}$$ $$=\sqrt{25+4}$$ $$=\sqrt{29}$$

Since:

$$\sqrt{13}<\sqrt{29}$$

the closest points are:

$$\boxed{(2,2)\text{ and }(4,5)}$$

These will be the support vectors.

---

2. Find the Maximum-Margin Decision Boundary

The maximum-margin boundary is:

1. Perpendicular to the line joining the two support vectors.
2. Passes through the midpoint of the support vectors.

---

Step 1: Find the midpoint

The support vectors are:

$$(2,2)\quad\text{and}\quad(4,5)$$

The midpoint is:

$$\left( \frac{2+4}{2}, \frac{2+5}{2} \right)$$

Therefore:

$$\boxed{M=(3,3.5)}$$

---

Step 2: Find a vector perpendicular to the decision boundary

The vector joining the support vectors is:

$$(4-2,\;5-2)$$ $$\boxed{(2,3)}$$

This vector is perpendicular (normal) to the decision boundary.

Therefore:

$$w= \begin{bmatrix} 2\\ 3 \end{bmatrix}$$

So the decision boundary has the form:

$$\boxed{2x_1+3x_2+b=0}$$

---

3. Find $b$

The boundary passes through:

$$(3,3.5)$$

Substitute into:

$$2x_1+3x_2+b=0$$ $$2(3)+3(3.5)+b=0$$ $$6+10.5+b=0$$

Therefore:

$$\boxed{b=-16.5}$$

So one form of the separating boundary is:

$$\boxed{2x_1+3x_2-16.5=0}$$

Multiplying by 2:

$$\boxed{4x_1+6x_2-33=0}$$

---

4. Convert to Standard SVM Form

For standard hard-margin SVM, the support vectors should satisfy:

$$w^Tx+b=+1$$

and

$$w^Tx+b=-1$$

Our current function is:

$$4x_1+6x_2-33$$

For $(2,2)$:

$$4(2)+6(2)-33$$ $$8+12-33=-13$$

For $(4,5)$:

$$4(4)+6(5)-33$$ $$16+30-33=13$$

Therefore, divide everything by $13$.

The standard SVM decision function is:

$$\boxed{ f(x)=\frac{4}{13}x_1+\frac{6}{13}x_2-\frac{33}{13} }$$

Thus:

$$\boxed{ w= \begin{bmatrix} \frac{4}{13}\\ \frac{6}{13} \end{bmatrix} }$$

and:

$$\boxed{ b=-\frac{33}{13} }$$

---

5. Final SVM Classifier

The classifier is:

$$\boxed{ f(x)=\frac{4}{13}x_1+\frac{6}{13}x_2-\frac{33}{13} }$$

The decision rule is:

$$\boxed{ \hat y= \begin{cases} 1 & \text{if }f(x)>0\\ 0 & \text{if }f(x)<0 \end{cases} }$$

Or equivalently, without fractions:

$$\boxed{ 4x_1+6x_2-33=0 }$$

Therefore:

$$\boxed{ \hat y= \begin{cases} 1 & \text{if }4x_1+6x_2-33>0\\ 0 & \text{if }4x_1+6x_2-33<0 \end{cases} }$$

---

6. Verify All Training Points

Point $(2,2)$

$$4(2)+6(2)-33=-13$$

Negative, so:

$$\boxed{\text{Class }0}$$

✓ Correct.

---

Point $(4,5)$

$$4(4)+6(5)-33=13$$

Positive, so:

$$\boxed{\text{Class }1}$$

✓ Correct.

---

Point $(7,4)$

$$4(7)+6(4)-33$$ $$28+24-33=19$$

Positive, so:

$$\boxed{\text{Class }1}$$

✓ Correct.

---

Final Answer

Support Vectors

$$\boxed{(2,2)\text{ and }(4,5)}$$

Maximum-Margin Decision Boundary

$$\boxed{4X_1+6X_2-33=0}$$

Standard Hard-Margin SVM Classifier

$$\boxed{ f(X)=\frac{4}{13}X_1+\frac{6}{13}X_2-\frac{33}{13} }$$

Classification Rule

$$\boxed{ \text{Class }1 \text{ if }4X_1+6X_2-33>0 }$$                                                            Class 0 if 4X1​+6X2​−33<0​