BSNotes.in — Notes for IIT Madras BS StudentsSearch your notes⌘ K
REVISION AND PRACTICE

Week 1 Quick Revision

4 min read
On this page 5 headings

Swipe long formulas, tables or code sideways to see the rest.

Start here All of Week 1 on one page. Read this the night before the quiz.

The story in 6 lines

  1. Biological neuron: dendrite (receives) → soma (processes) → axon (sends) → synapse (connects). The brain has ~101110^{11} neurons, works in parallel, and is organised in layers (simple → complex).
  2. MP neuron (1943): inputs 0/1, add them, output 1 if sum ≥θ\ge \theta . Any inhibitory input =1→= 1 \to output 0.
  3. Perceptron (Rosenblatt 1958, refined by Minsky–Papert 1969): weights + real inputs + learnable bias. y=1y = 1 if ∑i=0nwixi≥0\sum _{i=0}^{n} w_{i}x_{i} \ge 0, with x0=1,w0=−θx_{0} = 1, w_{0} = -\theta .
  4. PLA: wrong on a positive point →w=w+x\to w = w + x; wrong on a negative point →w=w−x\to w = w - x. Converges if the data is linearly separable.
  5. XOR is not linearly separable → one perceptron can’t do it.
  6. MLP: 1 hidden layer of 2n2^{n} perceptrons + 1 output perceptron can represent any Boolean function of n inputs.

Key formulas

Idea Formula
MP neuron g(x)=∑xi;y=1g(x) = \sum x_{i}; y = 1 if g(x)≥θg(x) \ge \theta , else 0
Perceptron y=1y = 1 if wTx≥0w^{T}x \ge 0, else 0(x0=1,w0=−θ)0 (x_{0} = 1, w_{0} = -\theta )
Angle cos⁡α=wTx/(∥w∥∥x∥)\cos \alpha = w^{T}x / (\Vert w\Vert \Vert x\Vert )
PLA updates x∈P,wTx<0→w+x;x∈N,wTx≥0→w−xx \in P, w^{T}x < 0 \to w + x; x \in N, w^{T}x \ge 0 \to w - x
Convergence bound cos⁡β≥(w∗⋅w0+kδ)/∥w0∥2+k→k\cos \beta \ge (w*\cdot w_{0} + k\delta ) / \sqrt{\Vert w_{0}\Vert ^{2} + k} \to k is bounded
Boolean functions of n inputs 22n2^{2^{n}} (n = 2 → 16, of which 14 separable)
Hidden units in the theorem 2n2^{n} (sufficient, not necessary)

Gates to remember

Gate MP neuron Perceptron (w0,w1,w2)(w_{0}, w_{1}, w_{2})
AND θ=n\theta = n (−1.5, 1, 1) or (−2, 1, 1)
OR θ=1\theta = 1 (−1, 1.1, 1.1) or (−0.5, 1, 1)
NOR all inputs inhibitory, θ=0\theta = 0 (0.5, −1, −1)
NOT input inhibitory, θ=0\theta = 0 (0.5, −1)
NAND — (1.5, −1, −1)
XOR / XNOR impossible impossible with one unit — needs a hidden layer

Common traps

  • wTx=0w^{T}x = 0 counts as output 1 (the rule is ≥0\ge 0).
  • A perceptron is not more powerful than an MP neuron in what kinds of Boolean functions it can represent: both can do only linearly separable functions. The gain is weights, real inputs and learning.
  • PLA convergence needs linearly separable data. On XOR it never stops.
  • The2nThe 2^{n} hidden-unit network uses ±1 inputs and hidden bias −n (−2 for 2 inputs, −3 for 3 inputs).
  • Slide errata: the error table shows 1 error for (w1,w2)=(−1,−1)(w_{1}, w_{2}) = (-1, -1) with w0=−1w_{0} = -1 — the correct count for OR is 3. In the convergence proof, the denominator should be ∥w0∥2+k\sqrt{\Vert w_{0}\Vert ^{2} + k}.

Exam words: dendrite, soma, axon, synapse, thresholding logic, excitatory, inhibitory, perceptron, bias, prior, linearly separable, error surface, Perceptron Learning Algorithm, convergence, XOR, hidden layer, MLP, representation power.

Quick check

  1. Who proposed the perceptron and when?
Frank Rosenblatt, 1958 (later refined by Minsky and Papert, 1969).
  1. MP neuron with 3 inputs and θ=0\theta = 0, no inhibitory inputs. What does it compute?
Always 1 (tautology), since the sum is always ≥0\ge 0.
  1. Perceptron w=[−3,2,2]w = [-3, 2, 2]. Output for (1, 1) and (1, 0)?
(1,1):−3+2+2=1≥0→1(1,1): -3 + 2 + 2 = 1 \ge 0 \to 1. (1,0):−3+2=−1→0(1,0): -3 + 2 = -1 \to 0. (This is AND.)
  1. PLA:w=[0,1,−1]PLA: w = [0, 1, -1], negative point (2, 1). New w?
x=[1,2,1];wTx=0+2−1=1≥0→x = [1, 2, 1]; w^{T}x = 0 + 2 - 1 = 1 \ge 0 \to wrong. w−x=[−1,−1,−2]w - x = [-1, -1, -2].
  1. Why can’t one perceptron learn XOR?
Rows (0,1) and (1,0) force w1+w2≥−2w0>−w0w_{1} + w_{2} \ge -2w_{0} > -w_{0}, but row (1,1) needs w1+w2<−w0w_{1} + w_{2} < -w_{0}. Contradiction — XOR is not linearly separable.
  1. How many hidden perceptrons does the theorem use for 4 inputs?
24=16. 2^{4} = 16.
YOUR STUDY PROGRESS

Finished this section? Save your progress.

Back to top ↑