Chapter 6 Linear classifier

2
How you can concentrate in the lecture
Linear classifier

❖Sometimes probabilistic
information (Bayesian
rule) unavailable or
mathematically difficult

❖Many alternatives to
Bayesian classification,
but optimality guarantee
may be compromised!

❖Linear classifiers use a decision hyperplane to

perform classification with Simple separation
❖ Linear classifiers reach to Optimality of linear
separability for classes 3
 APPLICATION OF SOUND CLASSIFICATION

X1
x2
OBSERVED .
PATTERN analog xn
digital
Class
FILTERING assignment
& FEATURE CLASSIFICATION
Wi SAMPLING EXTRACTION ALGORITHM ^
Wi
Preprocessing
ACOUSTIC / enhancement
SIGNALS
FROM
ACOUSTIC
TARGET
LEARNING
ACOUSTIC SENSORS ALGORITHM

3
APPLICATION OF SOUND CLASSIFICATION

❖Feature extraction :
● The feature may be extracted by using
information about the observed pattern
●The aim of this function is to create a discriminative
feature good (all classes are linearly separated)

GOOD
BAD

4
BASIC CONCEPT ABOUT LINEAR CLASSIFICATION

x1
wi x2 =X  Ri
.
Decision
xn Feature
vector region
class

● The feature vector X is a point in feature space R

● THE CLASSIFIER PARTATIONS THE FEATURE VECTORS INTO DECISION
REGION
X2 R1

w1 R2 IF X  R1

FEATURE w2 X is assigned to w1
VECTORS X
X1 6
Conventional and Artificial Neural Networks Classifiers
Bayesian classifier
w

w w
w

w w

❖In Bayesian classifier, all relevant probabilities are

defined as :
where gi(x) is a discriminant function calculated by the
classifier, P (wi|x) is a posterior probability, p (x|wi) is
the conditional probability density function depending
on the state of nature, P (wi) is a priori probability of the
state of nature wi, and x is a feature vector.

6
Conventional and Artificial Neural Networks Classifiers
Bayesian classifier
w

w w
w

w w

❖The decision rule

^
wi = argmax p (wi|x)=argmax p (x|wi)p (wi)
wi wi

7
 Linear discriminant function

gk(x) = p (wk|x)

●In linear discriminant function

gk(x) = wkT x +w0 ,wk weight vector,w0 threshold weight
●To classify vector x
If gk(x) > gi(x) for all k<>i
x Rk x is assigned to wk 9
Multilayer Perceptron (MLP)

● The multilayer perceptron (MLP) is the most widely used

paradigm among neural networks in various applications.

● it is a powerful signal processing algorithm for solving many

practical problems.

● it is a powerful classifier in pattern classification problem.

● The MLP is certainly a good candidate for a classifier in a

pattern classification system.

9
Linear Models for Classification
❖ Linear models for classification separate input vectors
into classes using linear (hyperplane) decision
boundaries.
w1

Example:
2D Input vector x
Two discrete classes w1 and w2
w2

10
 Linear discriminant functions

● g (x) or y(x) = wT x +w0

● Let w=[w1,…….., wp]t be a weight vector
and w0 be a threshold
● Decision surface is a hyperplain by set y (x)=0

● wT x +w0 = 0
p

● Predict w2 if ∑ w i x i  w0
i =1

otherwise predict w1

11
 Two Class Discriminant Function

y (x) = wt x + w
y (x) >= 0 x assigned to w1
y (x) < 0 x assigned to w2

Thus y(x) = 0 defines the decision boundary

12
Two Class Discriminant Function
For simplicity
making an extension to the weight vector w and feature vector x

So we can express

y(x) = wt x

13
Generalized Linear Models

It is useful to elaborate the linear model by introducing

a nonlinear activation function f, which typically will
constrain y to lie between -1 and 1 or between 0 and 1.

(x ) = f (w x )

14
Artificial Neuron

Figure .. Artificial neuron

Output y of the neuron is defined as

y = f (v )
and
n
v = ∑ w ixi
i=0

Where xi=the ith input (x0=1)

Wi = the weight connecting to the ith input. It is a bias if i is equal to 0
16
f ( ) is the non-linear activation function
Many type of non linear activation function

17
Supervised learning

❖ System is presented with a set of training pairs

consisting of an input vector x and desired output
vector .
❖ Weights w are adjusted to minimize the
difference (error) between the actual output 18
and desired output
Training
❖ So deterministic function classifying vectors
Weight are
changed in
direction that
minimizes
classification
error

desired

18
Training

If class linearly
separable then
by cycling
through vectors,
guaranteed to
converge in finite
number of steps

19
Training

20
Training

21
 Example 1

X 1{1, -.5, 3, -2 } w1 ^
sum F(sum) =1 if sum  
y
+
X2=1 =-1 if sum  
w2
_
Error =
+
 =zero ^
 = y− y
LR =  =0.5
{1,-1, 1 -1 }
W1=-2.5
desired = y
W2=1.75

22
Example 1
❖ According to the previous figure show how perceptron can learn logic
function where threshold  =zero, learning rate (LR)=0.5
weights w1=-2.5 , w2=1.75
Answer
 =zero
function: x1 x2 y
LR =  =0.5
1 1 1
-0.5 1 -1 W1=-2.5
3 1 1
-2 1 -1
W2=1.75
First iteration/1
Wi(t+1)=wi(t)+ w i = w i + x
Input x1=1, x2=1
W1(t+1)=-2.5+(0.5*2*1)=-1.5
Weight w1=-2.5,w2=1.75
W2(t+1)=1.75+(0.5*2*1)=2.75
∑ =(x1w1)+(x2w2)= (1*- 2.5) +
(1*1.75)=-0.75 
^
Then y =-1
^
y is not as expected
Error  =1-(-1) =2 then weights 24
change
Example 1
❖ Show how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=-1.5
-2 1 -1
W2=2.75
2 n d iteration/1
Input x1=-0.5, x2=1 Wi(t+1)=wi(t)+ w i = w i + x
Weight w1=-1.5,w2=2.75 W1(t+1)=-1.5+(0.5*-2*-0.5)=-1

∑ =(x1w1)+(x2w2)= (-0.5*-1.5)+ W2(t+1)=2.75+(0.5*-2*1)=1.75

(1*2.75)=4.5 
^
Then y =1
^
y is not as expected
Error  =-1-(1) =-2 then 25
weights change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=-1
-2 1 -1 W2=1.75
3 rd iteration/1
Input x1=3, x2=1 Wi(t+1)=wi(t)+ w i = w i + x

Weight w1=-1,w2=1.75 W1(t+1)=-1+(0.5*2*3)=2

=(x1w1)+(x2w2)= (3*-1)+ W2(t+1)=1.75+(0.5*2*1)=2.75

∑
(1*1.75)=-1.25 
^
Then y =-1
^
y is not as expected
Error  =1-(-1) =2 then weights 26
not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2
-2 1 -1 W2=2.75
4 th iteration/1
Input x1=-2, x2=1
Weight w1=2,w2=2.75
∑ =(x1w1)+(x2w2)= (-2*2)+
(1*2.75)=-1.25 
^
Then y =-1
^
y is as expected
Error  =-1-(-1) =0 then 27
weights not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2
-2 1 -1 W2=2.75
First iteration/2
Input x1=1, x2=1
Weight w1=2,w2=2.75
∑ =(x1w1)+(x2w2)= (1*2)+
(1*2.75)=4.75 
^
Then y =1
^
y is as expected
Error  =1-(1) =0 then weights 28
not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2
-2 1 -1 W2=2.75
2nd iteration/2
Input x1=-0.5, x2=1 Wi(t+1)=wi(t)+ w i = w i + x
Weight w1=2,w2=2.75 W1(t+1)=2+(0.5*-2*-0.5)=2.5

∑ =(x1w1)+(x2w2)= (-0.5*2)+ W2(t+1)=2.75+(0.5*-2*1)=1.25

(1*2.75)=1.75 
^
Then y =1
^
y is not as expected
Error  =-1-(1) =-2 then 29
weights change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y
 =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.50
-2 1 -1 W2=1.25
3 rd iteration/2
Input x1=3, x2=1
Weight w1=2.50,w2=1.25
∑ =(x1w1)+(x2w2)= (3*2.50)+
(1*1.25)=8.25 
^
Then y =1
^
y is as expected
Error  =1-(1) =0 then weights 30
not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
❖ Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.5
-2 1 -1 W2=1.25
4 th iteration/2
Input x1=-2, x2=1
Weight w1=2.5,w2=1.25

∑ =(x1w1)+(x2w2)= (-2*2.5)+
(1*1.25)=-3.75 
^
Then y =-1
^
y is as expected
Error  =-1-(-1) =0 then 31
weights not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.5
-2 1 -1 W2=1.25
1 th iteration/3
Input x1=1, x2=1
Weight w1=2.5,w2=1.25
∑ =(x1w1)+(x2w2)= (1*2.5)+
(1*1.25)=3.75 
^
Then y =1
^
y is as expected
Error  =1-(1) =0 then weights 32
not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.5
-2 1 -1 W2=1.25
2 n d iteration/3
Input x1=-0.5, x2=1
Weight w1=2.5,w2=1.25
∑ =(x1w1)+(x2w2)= (-0.5*2.5)+
(1*1.25)=0 
^
Then y =-1
^
y is as expected
Error  =-1-(-1) =0 then 33
weights not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.5
-2 1 -1 W2=1.25
3 rd iteration/3
Input x1=3, x2=1
Weight w1=2.5,w2=1.25

∑ =(x1w1)+(x2w2)= (3*2.5)+
(1*1.25)=8.75 
^
Then y =1
^
y is as expected
Error  =1-(1) =0 then weights 34
not change
Example 1
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.5 weights w1=-2.5 , w2=1.75
Answer
function: x1 x2 y  =zero
1 1 1
LR =  =0.5
-0.5 1 -1
3 1 1 W1=2.5
-2 1 -1 W2=1.25
4 th /iteration/3
Input x1=-2, x2=1
Weight w1=1.5,w2=0.25
∑ =(x1w1)+(x2w2)= (-2*2.5)+
(1*1.25)=-3.75 
^
Then y =-1
^
y is as expected
Error  =-1-(-1) =0 then 35
weights not change
Example 1

cycle x1 x2 Desired w1 w2 sum Actual error w1 w2

output output
1 1 1 1 -2.5 1.75 -0.75 -1 2 -1.5 2.75
-0.5 1 -1 -1.5 2.75 4.5 1 -2 -1 1.75
3 1 1 -1 1.75 -1.25 -1 2 2 2.75
-2 1 -1 2 2.75 -1.25 -1 0 2 2.75
2 1 1 1 2 2.75 4.75 1 0 2 2.75

-0.5 1 -1 2 2.75 1.75 1 -2 2.5 1.25

3 1 1 2.5 1.25 8.25 1 0 2.5 1.25

-2 1 -1 2.5 1.25 3.75 -1 0 2.5 1.25

35
Example 1

cycle x1 x2 Desired w1 w2 sum Actual error w1 w2

output output
3 1 1 1 2.5 1.25 3.75 1 0 2.5 1.25
-0.5 1 -1 2.5 1.25 0 -1 0 2.5 1.25
3 1 1 2.5 1.25 8.75 1 0 2.5 1.25
-2 1 -1 2.5 1.25 -3.75 -1 0 2.5 1.25

36
 Example 2

w1
X1{ 0011}
^
sum F(sum) =1 if sum  
y
+
X 2{0101} =0 if sum  
w2
_
Error =
+
 =zero ^
 = y− y
LR =  =0.2
W1=0 {0111}
W2=0.4 desired = y

37
Example 2
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.2 weights w1=0 , w2=0.4
Answer
function: x1 x2 y  =zero
0 0 0
LR =  =0.2
0 1 1
1 0 1 W1=0
1 1 1 W2=0.4
First iteration 2nd iteration
Input x1=0, x2=0 Input x1=0, x2=1
Weight w1=0,w2=0.4 Weight w1=0,w2=0.4
∑ =(x1w1)+(x2w2)= (0*0)+ ∑ =(x1w1)+(x2w2)= (0*0)+
(0*0.4)=0  (1*0.4)=0.4 
^
Then y =0
^
Then y =1
^ ^
y is as expected y is as expected
Error  =0 then weights don’t Error  =0 then weights 39
change don’t change
Example 2
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.2 weights w1=0 , w2=0.4
Answer
function: x1 x2 y  =zero
0 0 0
LR =  =0.2
0 1 1
1 0 1 W1=0
1 1 1 W2=0.4

3 rd iteration
Wi(t+1)=wi+ w i = w i + x
Input x1=1, x2=0
W1(t+1)=0+(0.2*1*1)=0.2
Weight w1=0,w2=0.4
W2(t+1)=0.4+(0.2*1*0)=0.4
∑ =(x1w1)+(x2w 2)=
(1*0)+(0*0.4)=0  
^
Then y =0
^
y is not as expected
40
Error  =1 then weights change
Example 2
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.2 weights w1=0 , w2=0.4
Answer
function: x1 x2 y  =zero
0 0 0
LR =  =0.2
0 1 1
1 0 1 W1=0.2
1 1 1 W2=0.4
4 th iteration
Input x1=1, x2=1
Weight w1=0.2,w2=0.4
∑ =(x1w1)+(x2w2)= (1*0.2)+
(1*0.4)=0.6 
^
Then y =1
^
y is as expected
Error  =0 then weights not 41
change
Example 2
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.2 weights w1=0 , w2=0.4
Answer
function: x1 x2 y  =zero
0 0 0
LR =  =0.2
0 1 1
1 0 1 W1=0.2
1 1 1 W2=0.4
First iteration 2nd iteration
Input x1=0, x2=0 Input x1=0, x2=1
Weight w1=0.2,w2=0.4 Weight w1=0.2,w2=0.4
∑ =(x1w1)+(x2w2)= (0*0.2)+ ∑ =(x1w1)+(x2w2)= (0*0.2)+
(0*0.4)=0  (1*0.4)=0.4 
^
^
Then y =0 Then y =1
^ ^
y is as expected y is as expected
Error  =0 then weights don’t Error  =0 then weights 41
change don’t change
Example 2
❖ Shaw how perceptron can learn logic function where threshold
 =zero, learning rate =0.2 weights w1=0 , w2=0.4
Answ er
function: x1 x2 y
 =zero
0 0 0 LR =  =0.2
0 1 1
W1=0.2
1 0 1
1 1 1 W2=0.4
3 rd iteration 4 th iteration
Input x1=1, x2=0 Input x1=1, x2=1
Weight w1=0.2,w2=0.4 Weight w1=0.2,w2=0.4
∑ =(x1w1)+(x2w2)= (1*0.2)+ ∑ =(x1w1)+(x2w2)= (1*0.2)+
(0*0.4)=0.2  (1*0.4)=0.6 
^
^
Then y =1 Then y =1
^
is as expected
^
y
y is as expected
Error  =0 then weights don’t Error  =0 then weights 42
change don’t change
Example 2

cycle x1 x2 Desired w1 w2 sum Actual error w1 w2

output output
1 0 0 0 0 .4 0 0 0 0 .4
0 1 1 0 .4 .4 1 0 0 .4
1 0 1 0 .4 0 0 1 .2 .4
1 1 1 .2 .4 .6 1 0 .2 .4
2 0 0 0 .2 .4 0 0 0 .2 .4

0 1 1 .2 .4 .4 1 0 .2 .4
1 0 1 .2 .4 .2 1 0 .2 .4

1 1 1 .2 .4 .6 1 0 .2 .4

44