Perceptron Algorithm | Pegasos Algorithm | Support Vector Machine | Linear Classifier Among Dataset | Deep Learning | Machine Learning

PERCEPTRON ALGORITHM

Perceptron Algorithm is one of the most used algorithm in classifying data.It frequently seems little tough while learning first time.

In today's post , We'll try to understand it well in brief with full explanation. 

Perceptron Algorithm is used whenever given dataset can be classified into two parts or it has only two labels.(One can consider it as +1, -1)

There are three version of Perceptron Algorithm:

1. Simple Perceptron 
2. Average Percepron
3. Pegasos Algorithm or Support Vector  Machine

Relax! Terms are sounding dangerous but they are really very easy.Let me explain you.

1.Simple Perceptron:

The single target of perceptron algorithm is to find a Linear classifier( say Linear equation) on one side of which are all positively labelled point and on another side all negatively labelled points are there.

As we know any linear equation can be written as,

Y=θ.X + θ₀

Using Perceptron Our Aim is to find those value of θ vector and θ₀ , with which formed line divide our dataset into two part , one part of which will be positively labelled and another part will be negatively labelled.See below pic:

• It is also an iterative method.We'll start with θ = 0 vector and θ₀₌₀

• _{In each iteration ,for every data point ,}

•  if ((yⁱ)*(θ.xⁱ+θ₀)<=0) :
• Update (θ=θ_old + (yⁱ.xⁱ))
                 (θ₀=θ₀ + yⁱ)

Reason For above updates can be derived using stochastic gradient descent algorithm.We'll derive above updation.If you are not familiar with Stochastic Gradient Descent ,Click Below Link.

Link to Stochastic Gradient Descent

2. Averaged Perceptron :

               In Averaged Perceptron , Our Averaged Perceptron Function returns the average value of θ and θ_{0 ,updated in every iteration.While in "Only Perceptron Algorithm" , We return the last updated value of θ and θ0 .}

_{See the Below Code of a sample implementation}

 

3. Pegasos Algorithm/Support Vector Machine:

In above two algorithm, we have taken care of getting best linear classifier, Which can well classify our dataset, but what if there are many classifier existing that can classify the dataset in two part.See Below pic

In above picture, It can be seen quite clearly that all the classifier line is well classifying our training set.

If you think little wisely, you can say the classifier with a high margin boundary will be said to best fit.

In such a case we should choose, which have large margin(d) on both side (positively labelled and negatively labelled) . 

Now, there are two things :

1. Loss : Loss on misclassifying a data
2. Regularization : Responsible for maintaining large boundary

Remember we are concerned only about its correct classification.If our classifier classifies any point wrongly , we will give some penalty to our classifier.

Also Notice if any point will be classified correctly and not on decision boundary, then :

label*Y_predicted >0

Since we want no point inside margin boundary too, We'll give penalty, when it will inside margin boundary too.So there will be no loss if :

(yⁱ(θ.Xⁱ+θ₀))>=1

Otherwise we'll give some penalty to our model, this is known as Hinge Loss, and it is defined as:

H(z)=max{0,1-z}, z=(yⁱ(θ.Xⁱ+θ₀))

means , Loss will be zero if z>1 else 1-z

So, Our Objective function will be 

J = Loss + Regularization

J(θ,θ₀) = (1/n)[Σ_iⁿ₌₁H(yⁱ(θ.Xⁱ+θ₀)) + (λ/2)||θ||² ]

Our target is to find those value of θ,θ₀ For which value of objective function is least or we have to minimize Objective function.We'll do it using Stochastic gradient descent Algorithm

So, in each iteration we will consider only one point and will calculate cost only for that and update.

J(θ,θ₀) = H(yⁱ(θ.Xⁱ+θ₀ⁱ)) + (λ/2)||θ||² 

^Since, ∂H(z)/∂θ = {0 if z>1 ,-∂z/∂θ otherwise}

So,the iteration formula from stochastic Gradient Descent:

if z<=1:

θ_new=θ_old - η[-yⁱ.xⁱ +λ.θ_old]

θ_new=θ_old +ηyⁱ.xⁱ  -η.λ.θ_old

θo_new=θo_old  + η.yⁱ

else:

θ_new=θ_old  - λ.θ_old

θo_new=θo_old 

We will make η getting decreased as iteration will increase.

Try to implement and Uderstand Below code

If we remove the regularization term , and take η=1 , it becomes Simple Perceptron Algorithm.