Module 4

Linear Classifiers: Introduction, Linear Discriminant Functions and Decision Hyperplanes, The
Perceptron Algorithm, Mean Square Error Estimate, Stochastic Approximation of LMS
Algorithm, Sum of Error Estimate.

Introduction

Linear Classifiers

Classifies data regardless of the underlying distributions describing the training data.

The major advantage of linear classifiers is their simplicity and computational attractiveness.

Linear classifiers classify data into labels based on a linear combination of input features.
Therefore, these classifiers separate data using a line or plane or a hyperplane (a plane in more
than 2 dimensions). They can only be used to classify data that is linearly separable.

Linear Discriminant Functions and Decision Hyperplanes

Discriminant Function
A function of several variates used to assign items into one of two or more groups. The function
for a particular set of items is obtained from measurements of the variates of items which belong
to a known group.

Linear Discriminant Functions

A linear discriminant function divides the feature space by a hy­perplane decision [Link]
can be optimal if the underlying distributions are cooperative, such as Gaussians having equal
covariance.
Linear discriminant functions are relatively easy to compute, simple. Linear classifiers are
attractive candidates for initial, trial classifiers.
A discriminant function that is a linear combination of the components of x can be written as

where w is the weight vector and w0 the bias or threshold weight.

The Two-Category Case
For a discriminant function of the form of

a two-category classifier implements the following decision rule: Decide w1 if g(x)>0 and w2 if
g(x)<0. Thus, x is assigned to w1 if the inner product wTx exceeds the threshold – w0 and to w2
otherwise. If g(x)=0, x can ordinarily be assigned to either class, or can be left undefined. The
equation g(x)=0 defines the decision surface that separates points assigned to w1 from points
assigned to w2.
Decision Hyperplanes
A hyperplane is a subspace whose dimension is one less than that of its ambient space. For
example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if
the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. A decision boundary or
decision surface is a hypersurface that partitions the underlying vector space into two sets, one
for each class.
In a two category case When g(x) is linear, this decision surface is a hyperplane. If x1 and x2 are
both on the decision surface, then

or

and this shows that w is normal to any vector lying in the hyperplane. In general, the hyperplane
H divides the feature space into two half-spaces: decision region R1 for w1 and region R2 for w2.
Because g(x)>0 if x is in R1, it follows that the normal vector w points into R1. It is sometimes
said that any x in R1 is on the positive side of H, and any x in R2 is on the negative side.
The discriminant function g(x) gives an algebraic measure of the distance from x to the
hyperplane. The easiest way to see this is to express x as
where xp is the normal projection of x onto H, and r is the desired algebraic distance which is
positive if x is on the positive side and negative if x is on the negative side. Then, because
g(xp)=0,

Since then

or
Figure A: The linear decision boundary H separates the feature space into two half-spaces.

In particular, the distance from the origin to H is given by . If w0>0, the origin is on the
positive side of H, and if w0<0, it is on the negative side. If w0=0, then g(x) has the homogeneous
form , and the hyperplane passes through the origin (Figure A). A linear discriminant
function divides the feature space by a hy­perplane decision surface. The orientation of the
surface is determined by the normal vector w, and the location of the surface is determined by
the bias w0. The discrim­inant function g(x) is proportional to the signed distance from x to the
hyperplane, with g(x)>0 when x is on the positive side, and g(x)<0 when x is on the negative
side.

The Perceptron Algorithm

In Perceptron, we take a weighted linear combination of input features and pass it through a
thresholding function which outputs 1 or 0. The sign of wTx tells us which side of the plane
wTx=0, the point x lies on. Thus by taking threshold as 0, perceptron classifies data based on
which side of the plane the new point lies on.
The task during training is to arrive at the plane (defined by w) that accurately classifies the
training data. If the data is linearly separable, perceptron training always converges
we assume that the two classes 𝝎1 , 𝝎2 are linearly separable.

we assume that there exists a hyperplane, defined by w∗Tx = 0, such that

w∗T x > 0 ∀x ∈ 𝝎1

w∗T x < 0 ∀x ∈ 𝝎2

The formulation above also covers the case of a hyperplane not crossing the origin, that is

We will approach the problem as a typical optimization task we choose the perceptron cost
defined as

where Y is the subset of the training vectors, which are misclassified by the hyperplane defined
by the weight vector w. The variable 𝛅x is chosen so that 𝛅x = -1 if x ∈ 𝝎1 and 𝛅x = +1 if x ∈
𝝎2. J(w) = 0 when Y is empty set

The perceptron cost function is continuous and piecewise linear. If we change the weight vector
smoothly, the cost J (w) changes linearly until the point at which there is a change in the number
of misclassified vectors.

Weight updation formula is

The perceptron algorithm is quite simple in its structure. The algorithm is initialized from an
arbitrary weight vector w(0), and the correction vector is formed using the misclassified
features. The weight vector is then corrected according to the preceding rule. This is repeated
until the algorithm converges to a solution, that is, all features are correctly classified. A
pseudocode for the perceptron algorithm is given below.

Figure provides a geometric interpretation of the algorithm. It has been assumed that at step t
there is only one misclassified sample, x, and ρt = 1. The perceptron algorithm corrects the
weight vector in the direction of x. Its effect is to turn the corresponding hyperplane so that x is
classified in the correct class 𝝎1. Note that in order to achieve this, it may take more than one
iteration step, depending on the value(s) of t .

Example
Figure shows the dashed line

An example of the perceptron algorithm. After the update of the weight vector, the hyperplane is
turned from its initial location (dotted line) to the new one (full line), and all points are correctly
classified.

Variants of the Perceptron Algorithm

The N training vectors enter the algorithm cyclically, one after the other. If the algorithm has not
converged after the presentation of all the samples once, then the procedure keeps repeating until
convergence is achieved—that is, when all training samples have been classified correctly. Let
w(t) be the weight vector estimate and x(t) the corresponding feature vector, presented at the tth
iteration step. The algorithm is stated as follows:

In other words, if the current training sample is classified correctly, no action is taken.
Otherwise, if the sample is misclassified, the weight vector is corrected by adding (subtracting)
an amount proportional to x(t). The algorithm belongs to a more general algorithmic family
known as reward and punishment schemes. If the classification is correct, the reward is that no
action is taken. If the current vector is misclassified, the punishment is the cost of correction. It
can be shown that this form of the perceptron algorithm also converges in a finite number of
iteration steps.

Example

Figure shows four points in the two-dimensional space. Points (-1, 0), (0, 1) belong to class 𝝎1,
and points (0,-1), (1, 0) belong to class 𝝎2. The goal of this example is to design a linear
classifier using the perceptron algorithm in its reward and punishment form. The parameter ρ is
set equal to one, and the initial weight vector is chosen as w(0) [0, 0, 0]T in the extended
three-dimensional space.
Since for four consecutive steps no correction is needed, all points are correctly classified and the
algorithm terminates. The solution is w = [-1, 1, 0]T . That is, the resulting linear classifier is -x1
+ x2 = 0, and it is the line passing through the origin i.e x1 = x2

The Perceptron

Once the perceptron algorithm has converged to a weight vector w and a threshold w0, our next
goal is the classification of an unknown feature vector to either of the two classes. Classification
is achieved via the simple rule
A basic network unit that implements the operation is shown in Figure

(a) A linear combiner is followed by the activation function.

(b) The combiner and the activation function are merged together.

The elements of the feature vector x1, x2, . . . , xl are applied to the input nodes of the network.
Then each one is multiplied by the corresponding weights wi , i = 1, 2, . . . , l. These are known
as synaptic weights or simply synapses. The products are summed up together with the threshold
value w0. The result then goes through a nonlinear device, which implements the so-called
activation function. A common choice is a hard limiter; that is, f (·) is the step function [f (x) =-1
if x < 0 and f (x) = 1 if x > 0]. The corresponding feature vector is classified in one of the classes
depending on the sign of the output.

The Pocket Algorithm

Basically the pocket algorithm is a perceptron learning algorithm with a memory which keeps
the result of the iteration.

A basic requirement for the convergence of the perceptron algorithm is the linear separability of
the classes. If this is not true, as is usually the case in practice, the perceptron algorithm does not
converge. A variant of the perceptron algorithm was suggested that converges to an optimal
solution even if the linear separability condition is not fulfilled.

The pocket algorithm solves the stability problem of perceptron learning by keeping the best
solution seen so far "in its pocket". The pocket algorithm then returns the solution in the pocket,
rather than the last solution. It can be used also for non-separable data sets, where the aim is to
find a perceptron with a small number of misclassifications. However, these solutions appear
purely stochastically and hence the pocket algorithm neither approaches them gradually in the
course of learning, nor are they guaranteed to show up within a given number of learning steps.

The algorithm is known as the pocket algorithm and consists of the following two steps

■ Initialize the weight vector w(0) randomly. Define a stored (in the pocket!) vector ws. Set a
history counter hs of the ws to zero.

■ At the tth iteration step, compute the update w(t + 1), according to the perceptron rule. Use the
updated weight vector to test the number h of training vectors that are classified correctly. If h >
hs replace ws with w(t + 1) and hs with h. Continue the iterations.

It can be shown that this algorithm converges with probability one to the optimal solution, that is,
the one that produces the minimum number of misclassifications. Other related algorithms that
find reasonably good solutions when the classes are not linearly separable are the thermal
perceptron algorithm, the loss minimization algorithm, and the barycentric correction procedure.

Kesler’s Construction - The generalization to an M-class task