Deep Learning · TEE · section

F23 Q5b

Final examination December 2023 fully solved

Question

Question (10 marks). Explain why a single perceptron cannot classify nonlinearly separable data. Implement XOR and XNOR using suitable perceptrons.

Answer — step by step

Given

Required logic functions = XOR and XNOR on two binary inputs.

Weights and biases are design choices, not given constants.

To find

Explain the failure of a single linear separator, choose suitable hidden/output perceptrons and show all four truth-table rows.

Formula — which one and why

Threshold logic. Compute the weighted sum for every binary input combination and apply the threshold rule exactly. Hidden neurons can provide separate threshold decisions before the output combines them.

step(z) returns 1 at or above zero unless the question specifies a strict inequality; otherwise it returns 0.

$z=\sum_iw_ix_i+b$ LaTeX: z=\sum_iw_ix_i+b

$\operatorname{step}(z)=\begin{cases}1&z\ge0\\0&z<0\end{cases}$ LaTeX: \operatorname{step}(z)=\begin{cases}1&z\ge0\\0&z<0\end{cases}

Yaad rakhne ka cue: Har input row ka sum nikalo, phir threshold lagao.

Solution — step by step

A single perceptron forms a weighted sum and applies a threshold. Its decision boundary is linear: w·x+b = 0. It can learn linearly separable patterns such as AND and OR under suitable learning conditions, but cannot represent XOR with one linear separator.

Opposite corners for XOR cannot be split by one straight line Tap the diagram to enlarge.

For binary AND, w₁ = w₂ = 1 and b = −1.5 give preactivations −1.5, −0.5, −0.5 and 0.5 for 00, 10, 01 and 11. A step that returns 1 at nonnegative inputs produces 0,0,0,1.

For XOR, use h₁ = step(x₁+x₂−0.5) for OR and h₂ = step(x₁+x₂−1.5) for AND. Then XOR = step(h₁−2h₂−0.5). For inputs 00,01,10,11, the hidden pairs are (0,0), (1,0), (1,0), (1,1), producing 0,1,1,0. XNOR = step(−h₁+2h₂+0.5), producing 1,0,0,1. This is a multilayer construction, not a claim that a single perceptron solves XOR.

A multilayer feedforward network adds hidden nonlinear features before the final boundary. Without hidden nonlinearities, adding linear layers still produces one affine map.

Verify input (0,0)

Step 1: calculate hidden OR preactivation.

$z_1=0+0-0.5=-0.5$ LaTeX: z_1=0+0-0.5=-0.5

Step 2: apply its threshold.

$h_1=0$ LaTeX: h_1=0

Step 3: calculate hidden AND preactivation.

$z_2=0+0-1.5=-1.5$ LaTeX: z_2=0+0-1.5=-1.5

Step 4: apply its threshold.

$h_2=0$ LaTeX: h_2=0

Step 5: calculate XOR output preactivation.

Step 6: apply the XOR threshold.

$y_{XOR}=0$ LaTeX: y_{XOR}=0

Step 7: calculate XNOR output preactivation.

Step 8: apply the XNOR threshold.

$y_{XNOR}=1$ LaTeX: y_{XNOR}=1

Verify input (0,1)

Step 1: calculate hidden OR preactivation.

$z_1=0+1-0.5=0.5$ LaTeX: z_1=0+1-0.5=0.5

Step 2: apply its threshold.

$h_1=1$ LaTeX: h_1=1

Step 3: calculate hidden AND preactivation.

$z_2=0+1-1.5=-0.5$ LaTeX: z_2=0+1-1.5=-0.5

Step 4: apply its threshold.

$h_2=0$ LaTeX: h_2=0

Step 5: calculate XOR output preactivation.

Step 6: apply the XOR threshold.

$y_{XOR}=1$ LaTeX: y_{XOR}=1

Step 7: calculate XNOR output preactivation.

Step 8: apply the XNOR threshold.

$y_{XNOR}=0$ LaTeX: y_{XNOR}=0

Verify input (1,0)

Step 1: calculate hidden OR preactivation.

$z_1=1+0-0.5=0.5$ LaTeX: z_1=1+0-0.5=0.5

Step 2: apply its threshold.

$h_1=1$ LaTeX: h_1=1

Step 3: calculate hidden AND preactivation.

$z_2=1+0-1.5=-0.5$ LaTeX: z_2=1+0-1.5=-0.5

Step 4: apply its threshold.

$h_2=0$ LaTeX: h_2=0

Step 5: calculate XOR output preactivation.

Step 6: apply the XOR threshold.

$y_{XOR}=1$ LaTeX: y_{XOR}=1

Step 7: calculate XNOR output preactivation.

Step 8: apply the XNOR threshold.

$y_{XNOR}=0$ LaTeX: y_{XNOR}=0

Verify input (1,1)

Step 1: calculate hidden OR preactivation.

$z_1=1+1-0.5=1.5$ LaTeX: z_1=1+1-0.5=1.5

Step 2: apply its threshold.

$h_1=1$ LaTeX: h_1=1

Step 3: calculate hidden AND preactivation.

$z_2=1+1-1.5=0.5$ LaTeX: z_2=1+1-1.5=0.5

Step 4: apply its threshold.

$h_2=1$ LaTeX: h_2=1

Step 5: calculate XOR output preactivation.

Step 6: apply the XOR threshold.

$y_{XOR}=0$ LaTeX: y_{XOR}=0

Step 7: calculate XNOR output preactivation.

Step 8: apply the XNOR threshold.

$y_{XNOR}=1$ LaTeX: y_{XNOR}=1

Final answer: XOR = [0,1,1,0]; XNOR = [1,0,0,1] for 00,01,10,11. The hidden nonlinear units make this possible.