Spring 2026 Department of AI, IIT Kharagpur

AI61002: Deep Learning Foundations

and Applications
Module 1: Multi-layer Perceptrons

Dr. Somdyuti Paul

1
The Perceptron
• The perceptron is a linear, binary classi er that was used as building blocks of early neural networks.
x1

The Mark I perceptron machine from

1958 designed using hardware circuits
T
Input: x = [x1, x2, ⋯xn,1]
T
Weights: w = [w1, w2, ⋯wn, b]
T
Prediction: ŷ = sign(w x)
2
fi
The Perceptron Algorithm
Let a ground truth label be y, and the corresponding prediction y.̂ The Perceptron Algorithm

(i) (i)
Parameter update rule: Training data: (x , y ) ∀i ∈ {1,2,⋯M}
wt+1 = wt + αyx if yŷ < 0 Learning rate: α
= wt otherwise Result: w*
Initialize:
Intuition:
w0 ← 0;
t = 0;
Case 1: y= + 1, ŷ = − 1 repeat:
wt+1 = wt + αx for i = 1,2,⋯M, do
T T T T y(i)
̂ = sign(wtT x (i));
wt+1x = wt x + αx x > wt x
if y (i)y(i)
̂ < 0 then
(i) (i)
wt+1 ← wt + αy x ;
Case 2: y= − 1, ŷ = + 1 t ← t + 1;
wt+1 = wt − αx end
end
T T T T
wt+1x = wt x − αx x < wt x until convergence
3
 Convergence of the Perceptron Algorithm
• The perceptron algorithm converges in a nite number of steps when the training data is linearly
separable.

Proof:
n (i) T (i)
If the training data is linearly separable ∃w* ∈ ℝ that perfectly classi es the data. Also. Let γ = min y (w* x ) and
i
i
∥x ∥ ≤ R

After the k th weight update, we have,

wk+1 = wk + αy (i) x (i)

T
wt w* = (wt−1 + αy x ) w*
(i) (i) T

T (i) (i)T
= wt−1w* + αy x w*
T
≥ wt−1w* + αγ
T
As w0 = 0, by induction, we have wk w* ≥ kαγ. 4
fi
fi
 Convergence of the Perceptron Algorithm
Proof:

Using Cauchy-Schwarz inequality,

(wk w*) ≤
T 2
∥wk∥2∥w*∥2
(wk w*)
2 2 2 T 2
∴k α γ ≤ ≤ ∥wk∥2∥w*∥2

Also,
2 (i) (i) T (i) (i)
∥wk∥ = (wk−1 + αy x ) (wk−1 + αy x )
= ∥wk−1∥2 + 2αy (i)wk−1
T
x (i) + α 2∥x (i)∥2
2 2 2
≤ ∥wk−1∥ + α R

Since w0 = 0, by induction, we have ∥wk∥2 ≤ kα 2R 2

So, we have:
k 2α 2γ 2 ≤ kα 2R 2∥w*∥2
R 2
i.e. k ≤ ( ) ∥w*∥2.
γ
5
Limitations of Perceptrons
• Cannot classify non-linearly separable data - unable to implement simple boolean functions like XOR
• Outputs are binary valued due to the activation function being a step function.
• Limited to a single layer
• Sensitive to outliers

To overcome aforementioned limitations:

• Use multi-layer neural perceptrons (MLPs)

• Use other activation functions.

6
Implementing the XOR Function with Multi-layer Perceptron

-1 -1 1 -1 -1 -1 -1

-1 1 -1 1 -1 -1 1
1 -1 -1 -1 1 -1 1

1 1 -1 -1 -1 1 -1

Thus by adding a hidden layer, we were able to implement the XOR function!

7
Representation Power of Multi-layer Perceptrons
N
• Any arbitrary boolean function having N inputs can be represented by an MLP having 2
neurons in the hidden layer i.e. a MLP with a single hidden layer acts as an universal boolean
machine.

• Intuition
N
• N boolean inputs can have 2 logical combinations.
• Each unit in the hidden layer can be designed to respond to a single input combination,
followed by the output layer which combines these activations using weighted sum.

• The disadvantage is that the number of neurons in the hidden layer increases exponentially
with the number of inputs.
8
 Need for Deeper Neural Network Architectures
• Consider a XOR gate having N > 2 inputs
• An MLP with a single hidden layer would require 2N + 1 neurons, i.e. the number of neurons increases exponentially
with input size.
• What happens if we increase the number of layers?

N
• Total # of units for the network with a single hidden layer = 2 + 1 (increases exponentially with increase in N)
2
• Total # of units for the network with multiple hidden layers = (2 + 1) . (N − 1) (increases linearly with increase in N)
9
Need for Deeper Network Architectures
Advantages of deep networks

• Repeated compositions of non-linear functions allow the networks to exploit regularities in data and
learn multiple levels of hierarchical abstractions.

• Adding more layers acts as a form of regularization and thus improves generalization.
• The non-linear mappings enabled by activation functions serve to make the data linearly separable.

Disadvantage of Deep Networks

• Deeper networks are harder to train (due to vanishing and exploding gradients).
• It is harder to interpret the features learned by deeper layers.

10