Deep Learning

Perceptron & linear separability

This lecture builds the perceptron from the biological neuron (MP neuron, Rosenblatt perceptron, step activation). It shows the decision boundary and linear separability with OR, AND and XOR. After this page you can run PLA updates on OR and solve thresholds for AND and OR.

Biological neuron to artificial neuronSearch on YouTube

A biological neuron receives signals through dendrites. It processes them in the cell body. It fires through the axon when the net input passes a threshold. The hand-pulled-from-heat reflex shows this chain. Receptors sense heat, interneurons decide, motor neurons carry the response.

The artificial neuron copies this chain with numbers:

Artificial componentBiological partFunction
Inputs x1,x2,…,xnx_1, x_2, \dots, x_nDendritesReceive signals
Weights w1,w2,…,wnw_1, w_2, \dots, w_nSynaptic strengthSet signal importance
Sum zzCell body (soma)Combine inputs
Activation function f(z)f(z)Firing mechanismDecide output
Output aaAxonPass output onward

D-S-C-F-A

Dendrites take inputs · Synapses set weights · Cell body sums · Firing is activation · Axon sends output.

Computational unitsSearch on YouTube

A computational unit is the basic building block of a neural network. It receives scalar inputs. It multiplies each input by a weight. It sums the products. It passes the sum through an activation function such as thresholding. It emits one output value.

Think of a voting panel. Each member casts a weighted vote. The chair adds the votes. The motion passes when the total crosses a fixed mark.

McCulloch-Pitts neuronSearch on YouTube

McCulloch and Pitts published the MP neuron in 1943. It was one of the first formal neuron models. It performs binary logic with Boolean inputs. It has no learning. Its output follows a fixed threshold.

f(x)=∑i=12wixif(x) = \sum_{i=1}^{2} w_i x_i

wiw_i are fixed weights. xix_i are Boolean inputs (00 or 11). The neuron fires when the sum reaches the threshold.

Threshold logicSearch on YouTube

Threshold logic computes a function from a weighted sum. The neuron fires when the sum reaches a manually chosen threshold. No training adjusts the threshold. The designer picks it from the target logic.

Worked example: AND with an MP neuron. Set both weights to 11. Set the threshold to 22. The neuron fires only when both inputs are 11.

x1x_1x2x_2Sum x1+x2x_1 + x_2Output aa
0000
0110
1010
1121

Check each row.

(0,0):0<2  ⇒  0(0,1):1<2  ⇒  0(1,0):1<2  ⇒  0(1,1):2≥2  ⇒  1\begin{aligned} (0,0):\quad 0 &\lt 2 \;\Rightarrow\; \mathbf{0}\\ (0,1):\quad 1 &\lt 2 \;\Rightarrow\; \mathbf{0}\\ (1,0):\quad 1 &\lt 2 \;\Rightarrow\; \mathbf{0}\\ (1,1):\quad 2 &\ge 2 \;\Rightarrow\; \mathbf{1} \end{aligned}

The table matches AND. The threshold 22 forces both inputs to be active.

a={1if ∑i=12wixi≥20if ∑i=12wixi<2a = \begin{cases} 1 & \text{if } \sum_{i=1}^{2} w_i x_i \ge 2\\ 0 & \text{if } \sum_{i=1}^{2} w_i x_i \lt 2 \end{cases}

aa is the output. The value 22 is the fixed threshold for AND with unit weights.

MP neuron featuresSearch on YouTube

FeatureDescription
InputsBoolean (00 or 11)
WeightsFixed, typically positive integers
SumAdds the weighted inputs
ThresholdFixed integer value
Activation functionStep: 11 when sum ≥\ge threshold, else 00
OutputBoolean (00 or 11)
LearningNone (no weight updates)

Say "fixed threshold" for MP neurons in the exam. Say "learned weights and bias" for perceptrons. The contrast earns marks.

Supervised learningSearch on YouTube

Supervised learning learns a mapping from inputs to outputs. The input vector is X=[x1,x2,…,xn]X = [x_1, x_2, \dots, x_n]. The learning algorithm searches for a function ff. The model must fit the training data. It must also predict new records correctly.

y^=f(X)\hat{y} = f(X)

XX is the attribute vector. ff is the learned function. y^\hat{y} is the predicted output.

The slides show an X→YX \to Y table (for example 5→275 \to 27, 1→31 \to 3). Each row pairs one input with its label. Learning means finding the ff behind such pairs.

Classification and regressionSearch on YouTube

Prediction learns a target function from each attribute set xx to an output yy. Classification predicts a categorical yy (spam or safe). Regression predicts a continuous yy (a number). The perceptron below does binary classification.

loss=Y−Y^\text{loss} = Y - \hat{Y}

YY is the true label. Y^\hat{Y} is the predicted output. The loss measures how wrong one prediction is.

Linear perceptronSearch on YouTube

Rosenblatt proposed the perceptron in 1958. It is a single-neuron network. It was the first neuron model that could learn weights from data. It takes several inputs (real or Boolean). It applies weights and a bias. It passes the result through an activation function (typically a step). It handles only linear boundaries (a straight line or hyperplane).

The neuron output aa reports the activation level of that neuron. The slides call the activation function an "activity function" once. The canonical term is activation function.

Step and sigmoid activationSearch on YouTube

The activation function decides the activity level of a neuron.

Step functionSearch on YouTube

The step uses a threshold tt (the bias form appears below). The neuron stays dormant below tt. It becomes active at and above tt.

SigmoidSearch on YouTube

The sigmoid gives graded activity between 00 and 11. The same input sum can thus give many activity levels. The slides use four sample points.

a=σ(z)=11+e−za = \sigma(z) = \frac{1}{1 + e^{-z}}

zz is the weighted sum plus bias. σ\sigma is the sigmoid. Large zz pushes aa toward 11. Small zz pushes aa toward 00.

Worked example: sigmoid activity levels. Apply σ\sigma to the four slide inputs.

σ(−2.7)=1/(1+e2.7)=1/15.88=0.063σ(−0.9)=1/(1+e0.9)=1/3.46=0.289σ(0.7)=1/(1+e−0.7)=1/1.497=0.668σ(1.0)=1/(1+e−1.0)=1/1.368=0.731\begin{aligned} \sigma(-2.7) &= 1/(1 + e^{2.7}) = 1/15.88 = \mathbf{0.063}\\ \sigma(-0.9) &= 1/(1 + e^{0.9}) = 1/3.46 = \mathbf{0.289}\\ \sigma(0.7) &= 1/(1 + e^{-0.7}) = 1/1.497 = \mathbf{0.668}\\ \sigma(1.0) &= 1/(1 + e^{-1.0}) = 1/1.368 = \mathbf{0.731} \end{aligned}

Read the trend. Activity rises with zz. The neuron is nearly dormant at −2.7-2.7. It is strongly active at 1.01.0.

Patterns in solution spaceSearch on YouTube

Three step neurons give only dormant or active states. The total codebook is 2×2×2=82 \times 2 \times 2 = 8 patterns. Sigmoid neurons give graded levels from 00 to 11. With 1010 distinct levels each, three neurons give 103=100010^3 = 1000 patterns. More states mean a larger solution space.

From threshold to biasSearch on YouTube

The perceptron fires when the weighted sum reaches the threshold. Subtract the threshold from both sides. The test becomes "shifted sum ≥0\ge 0". Write the negative threshold as w0w_0 (the bias). Then w0w_0 equals minus the threshold. Say "threshold" once as the alias. Use bias after that.

a={1if ∑i=1nwixi≥t0if ∑i=1nwixi<ta = \begin{cases} 1 & \text{if } \sum_{i=1}^{n} w_i x_i \ge t\\ 0 & \text{if } \sum_{i=1}^{n} w_i x_i \lt t \end{cases}

tt is the threshold. This is the threshold form of the step rule.

a={1if ∑i=1nwixi−t≥00if ∑i=1nwixi−t<0z=∑i=1nwixi+w0a = \begin{cases} 1 & \text{if } \sum_{i=1}^{n} w_i x_i - t \ge 0\\ 0 & \text{if } \sum_{i=1}^{n} w_i x_i - t \lt 0 \end{cases} \qquad z = \sum_{i=1}^{n} w_i x_i + w_0

w0=−tw_0 = -t is the bias. zz is the net input. The perceptron fires when z≥0z \ge 0.

Do not mix the two signs. Threshold form tests ∑wixi≥t\sum w_i x_i \ge t. Bias form tests ∑wixi+w0≥0\sum w_i x_i + w_0 \ge 0 with w0=−tw_0 = -t. A flipped sign moves the boundary to the wrong side.

Training: loss and weight updatesSearch on YouTube

Three items control the output: weights, bias and activation. Training adjusts the weights and bias from feedback. The loss Y−Y^Y - \hat{Y} reports each mistake. Backpropagation pushes that feedback into weight and bias updates. Biology does the same: synapses strengthen or weaken with experience.

Linear separabilitySearch on YouTube

Linear separability splits the input space with one boundary. Points with positive response lie on one side. Points with negative response lie on the other. The boundary is also called the decision line.

The net input defines the sides:

z=∑i=1nwixi+w0z = \sum_{i=1}^{n} w_i x_i + w_0

z>0z \gt 0 means a positive response. z<0z \lt 0 means a negative response. The boundary is z=0z = 0.

∑i=1nwixi+w0=0⟺∑i=1nwixi−t=0⟺∑i=1nwixi=t\sum_{i=1}^{n} w_i x_i + w_0 = 0 \qquad\Longleftrightarrow\qquad \sum_{i=1}^{n} w_i x_i - t = 0 \qquad\Longleftrightarrow\qquad \sum_{i=1}^{n} w_i x_i = t

All three forms state the same boundary. The first uses the bias. The others use the threshold t=−w0t = -w_0.

Line, plane or hyperplaneSearch on YouTube

The input count sets the shape. Two inputs give a line. Three inputs give a plane. More inputs give a hyperplane.

w1x1+w2x2+w0=0⟺y=mx+c    means    mx−y+c=0w_1 x_1 + w_2 x_2 + w_0 = 0 \qquad\Longleftrightarrow\qquad y = mx + c \;\; \text{means} \;\; mx - y + c = 0

The left form is the two-input boundary. The right form recalls the school line y=mx+cy = mx + c.

OR with a perceptronSearch on YouTube

OR outputs 00 only for (0,0)(0,0). It outputs 11 for (1,0)(1,0), (0,1)(0,1) and (1,1)(1,1). Write x0=1x_0 = 1 for the bias term. Then each row gives one inequality:

w0+w1⋅0+w2⋅0<0w0+w1⋅1+w2⋅0≥0w0+w1⋅0+w2⋅1≥0w0+w1⋅1+w2⋅1≥0⟺w0<0w0+w1≥0w0+w2≥0w0+w1+w2≥0\begin{aligned} w_0 + w_1\cdot 0 + w_2\cdot 0 &\lt 0\\ w_0 + w_1\cdot 1 + w_2\cdot 0 &\ge 0\\ w_0 + w_1\cdot 0 + w_2\cdot 1 &\ge 0\\ w_0 + w_1\cdot 1 + w_2\cdot 1 &\ge 0 \end{aligned} \qquad\Longleftrightarrow\qquad \begin{aligned} w_0 &\lt 0\\ w_0 + w_1 &\ge 0\\ w_0 + w_2 &\ge 0\\ w_0 + w_1 + w_2 &\ge 0 \end{aligned}

w0w_0 is the bias. w1,w2w_1, w_2 are the input weights. Any triple that satisfies all four rows implements OR.

(0,0) (1,0) (0,1) (1,1) x1+x2=1
OR is separable. The line through (1,0) and (0,1) leaves (0,0) alone.

Worked example: solve the OR inequalities. Pick w0=−1w_0 = -1, w1=1w_1 = 1, w2=1w_2 = 1.

(0,0):−1<0  ⇒  0(1,0):−1+1=0≥0  ⇒  1(0,1):−1+1=0≥0  ⇒  1(1,1):−1+1+1=1≥0  ⇒  1\begin{aligned} (0,0):\quad -1 &\lt 0 \;\Rightarrow\; \mathbf{0}\\ (1,0):\quad -1 + 1 = 0 &\ge 0 \;\Rightarrow\; \mathbf{1}\\ (0,1):\quad -1 + 1 = 0 &\ge 0 \;\Rightarrow\; \mathbf{1}\\ (1,1):\quad -1 + 1 + 1 = 1 &\ge 0 \;\Rightarrow\; \mathbf{1} \end{aligned}

Read the boundary. The line is x1+x2−1=0x_1 + x_2 - 1 = 0. It cuts the axes at (1,0)(1,0) and (0,1)(0,1). The triple [−1,2,2][-1, 2, 2] from the slides passes the same four tests.

Random weights and the error surfaceSearch on YouTube

Fix the bias and vary w1,w2w_1, w_2. Each trial draws one decision line. The slides try several lines. One line makes 33 errors. A better line makes 11 error. The error surface bottoms out when both w1w_1 and w2w_2 exceed 11. Random search wastes trials there. A principled rule finds the weights directly.

Push a fence until each animal stands on the right side. Each mistake tells you which way to push. PLA turns each mistake into one push.

Perceptron learning algorithmSearch on YouTube

The Perceptron Learning Algorithm (PLA) trains one perceptron for binary classification. PP is the positive class. NN is the negative class. ww is the weight vector (bias w0w_0 included). xx is the input vector (with x0=1x_0 = 1). PLA seeks the decision line that separates PP from NN. It stops when every input is classified correctly.

Predict 11 when z≥0z \ge 0. Predict 00 when z<0z \lt 0. Update only on mistakes:

w←w+x(true 1, predicted 0)w←w−x(true 0, predicted 1)w \leftarrow w + x \quad \text{(true $1$, predicted $0$)} \qquad\qquad w \leftarrow w - x \quad \text{(true $0$, predicted $1$)}

Add the input when the perceptron misses a positive point. Subtract the input on a false alarm. Leave ww unchanged on correct predictions.

Memorise the directions: miss means add, false alarm means subtract. The bias w0w_0 updates too because x0=1x_0 = 1 rides along.

PLA for OR, step by stepSearch on YouTube

Start from w=[−1,0,0]w = [-1, 0, 0]. Cycle the OR rows in order (1,0)(1,0), (0,1)(0,1), (1,1)(1,1), (0,0)(0,0). The slides show the first four computations. The trace below continues to convergence at w=[−1,1,1]w = [-1, 1, 1].

Steps 1 to 4: first pass. Current weights are w=[−1,0,0]w = [-1, 0, 0].

(1,0):z=−1⋅1+0⋅1+0⋅0=−1<0  ⇒  predict 0, true 1, updatew=[−1+1, 0+1, 0+0]=[0,1,0](0,1):z=0⋅1+1⋅0+0⋅1=0≥0  ⇒  predict 1, true 1, no update(1,1):z=0⋅1+1⋅1+0⋅1=1≥0  ⇒  predict 1, true 1, no update(0,0):z=0⋅1+1⋅0+0⋅0=0≥0  ⇒  predict 1, true 0, updatew=[0−1, 1−0, 0−0]=[−1,1,0]\begin{aligned} (1,0):\quad z &= -1\cdot 1 + 0\cdot 1 + 0\cdot 0 = -1 \lt 0 \;\Rightarrow\; \text{predict } \mathbf{0},\ \text{true } 1,\ \text{update}\\ w &= [-1+1,\ 0+1,\ 0+0] = \mathbf{[0, 1, 0]}\\ (0,1):\quad z &= 0\cdot 1 + 1\cdot 0 + 0\cdot 1 = 0 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 1,\ \text{no update}\\ (1,1):\quad z &= 0\cdot 1 + 1\cdot 1 + 0\cdot 1 = 1 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 1,\ \text{no update}\\ (0,0):\quad z &= 0\cdot 1 + 1\cdot 0 + 0\cdot 0 = 0 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 0,\ \text{update}\\ w &= [0-1,\ 1-0,\ 0-0] = \mathbf{[-1, 1, 0]} \end{aligned}

Steps 5 to 8: second pass. Current weights are w=[−1,1,0]w = [-1, 1, 0].

(1,0):z=−1+1+0=0≥0  ⇒  predict 1, true 1, no update(0,1):z=−1+0+0=−1<0  ⇒  predict 0, true 1, updatew=[−1+1, 1+0, 0+1]=[0,1,1](1,1):z=0+1+1=2≥0  ⇒  predict 1, true 1, no update(0,0):z=0≥0  ⇒  predict 1, true 0, updatew=[0−1, 1−0, 1−0]=[−1,1,1]\begin{aligned} (1,0):\quad z &= -1 + 1 + 0 = 0 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 1,\ \text{no update}\\ (0,1):\quad z &= -1 + 0 + 0 = -1 \lt 0 \;\Rightarrow\; \text{predict } \mathbf{0},\ \text{true } 1,\ \text{update}\\ w &= [-1+1,\ 1+0,\ 0+1] = \mathbf{[0, 1, 1]}\\ (1,1):\quad z &= 0 + 1 + 1 = 2 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 1,\ \text{no update}\\ (0,0):\quad z &= 0 \ge 0 \;\Rightarrow\; \text{predict } \mathbf{1},\ \text{true } 0,\ \text{update}\\ w &= [0-1,\ 1-0,\ 1-0] = \mathbf{[-1, 1, 1]} \end{aligned}

Step 9: verify convergence. Test all rows with w=[−1,1,1]w = [-1, 1, 1].

(1,0):−1+1=0≥0  ⇒  1(0,1):−1+1=0≥0  ⇒  1(1,1):−1+1+1=1≥0  ⇒  1(0,0):−1<0  ⇒  0\begin{aligned} (1,0):\quad -1 + 1 &= 0 \ge 0 \;\Rightarrow\; \mathbf{1}\\ (0,1):\quad -1 + 1 &= 0 \ge 0 \;\Rightarrow\; \mathbf{1}\\ (1,1):\quad -1 + 1 + 1 &= 1 \ge 0 \;\Rightarrow\; \mathbf{1}\\ (0,0):\quad -1 &\lt 0 \;\Rightarrow\; \mathbf{0} \end{aligned}

All four rows match OR. PLA stops. The slide target [−1,2,2][-1, 2, 2] is another valid separator.

Convergence theoremSearch on YouTube

The theorem answers one question: does PLA stop after finite steps? It stops when the two classes are linearly separable. It needs finite point sets. It tests the vectors cyclically, one after another.

Two sets PP and NN in nn-dimensional space are absolutely linearly separable when weights w0,w1,…,wnw_0, w_1, \dots, w_n exist with:

∑i=1nwixi>−w0for every point in P∑i=1nwixi<−w0for every point in N\sum_{i=1}^{n} w_i x_i \gt -w_0 \quad \text{for every point in } P \qquad\qquad \sum_{i=1}^{n} w_i x_i \lt -w_0 \quad \text{for every point in } N

PP sits fully on the positive side. NN sits fully on the negative side. The same w0w_0 serves both lines.

Proposition: when PP and NN are finite and linearly separable, PLA updates the weight vector finitely many times. After finite steps tt, the vector wtw_t separates the two sets.

Run PLA only on separable data. On overlapping classes it never settles. It cycles through mistakes without end.

Spam filter and XOR limitSearch on YouTube

Real tasks often reduce to linear choices. The spam scenario uses two binary features. Feature x1=1x_1 = 1 when "free" appears. Feature x2=1x_2 = 1 when "win" appears. The slides label (0,0)(0,0) as safe. They label (0,1)(0,1), (1,0)(1,0) and (1,1)(1,1) as spam. That table is OR. One perceptron implements it.

XOR breaks the perceptron. XOR outputs 11 for (0,1)(0,1) and (1,0)(1,0). It outputs 00 for (0,0)(0,0) and (1,1)(1,1). Opposite corners share labels. No single straight line isolates the two 11s.

(0,0) (1,0) (0,1) (1,1) fails on (1,1)
XOR is not separable. The OR line leaves (1,1) on the wrong side.

Worked example: prove XOR needs more than one line. Assume a separator exists with w0<0w_0 \lt 0 for (0,0)(0,0).

(0,0):w0<0(1,0):w0+w1≥0(0,1):w0+w2≥0(1,1):w0+w1+w2<0\begin{aligned} (0,0):\quad w_0 &\lt 0\\ (1,0):\quad w_0 + w_1 &\ge 0\\ (0,1):\quad w_0 + w_2 &\ge 0\\ (1,1):\quad w_0 + w_1 + w_2 &\lt 0 \end{aligned}

Derive the clash. Add the two middle rows.

2w0+w1+w2≥0w0=(2w0+w1+w2)−(w0+w1+w2)>0−0=0\begin{aligned} 2w_0 + w_1 + w_2 &\ge 0\\ w_0 &= (2w_0 + w_1 + w_2) - (w_0 + w_1 + w_2) \gt 0 - 0 = 0 \end{aligned}

So w0>0w_0 \gt 0. This clashes with w0<0w_0 \lt 0. No triple satisfies all rows. XOR is nonlinear for one perceptron. Higher networks (with hidden layers) handle it.

Try PLA on OR and XOR below. Move the weights or press Play PLA and watch the line react.

0011x1x21(1,0)1(0,1)1(1,1)0(0,0)

Line is w1x1+w2x2+w0=0. Blue dots output 1. Hollow dots output 0.

z = 1x1 + 1x2 + -1. Predict 1 when z ≥ 0.

Weights solve OR. Press Reset, then Play PLA. 4 of 4 rows pass. Mistakes: 0.

ANN layersSearch on YouTube

The network stacks neurons in layers. The arrangement plus the connection pattern is the network architecture.

  • Neuron: a cell that sums weighted inputs, adds a bias and holds activity aa.
  • Input layer: the first layer. It receives the raw input vector. With mm dimensions, it holds mm neurons. Each neuron is a placeholder for one dimension (no computation).
  • First dense layer in Keras: each neuron takes the full input vector. Its size need not equal the input size. The slides contrast this practical layout with the placeholder view.
  • Hidden layer: any layer between input and output. It extracts patterns from its inputs. Each layer may hold a different neuron count.
  • Output layer: the last layer. It emits one or more values from the previous layer.

A first input vector I1={x11,x12,x13}I_1 = \{x_{11}, x_{12}, x_{13}\} feeds three input neurons in the slide sketch. Each dense neuron would instead see the whole triple.

Three aspects of a modelSearch on YouTube

Slide lists three model aspects: synaptic interconnections, training rules for weight updates and activation functions. Later lectures vary each aspect.

Feedforward and feedback networksSearch on YouTube

Interconnections fall in two groups: feedforward and feedback.

FeedforwardFeedback
Data flow one way (input to hidden to output)Outputs return as inputs (same or earlier layer)
No cycles or loopsLoops carry past information forward
Sequential Dense modelsRecurrent and dynamic networks
Fixed-size classification and regressionSequences: time series, language, speech

Feedforward types: single-node network (linear perceptron), single-layer network and multilayer network. Feedback types: single node with self-feedback, single-layer recurrent network and multilayer recurrent network. Lateral feedback returns output within the same layer. It models competition or cooperation (stronger neurons suppress weaker ones through lateral inhibition). Self-feedback returns one output to its own neuron. Cross-neuron feedback sends outputs to other neurons in the same or earlier layers. Recurrent neural networks (RNNs) process sequences with such loops. Variants named in the slides: LSTM, GRU and bidirectional RNNs. A single-layer perceptron has no hidden layer (input to output). Its output layer may hold several perceptrons. A multilayer perceptron (MLP) adds hidden layers. It handles linear and nonlinear functions.

F-F-F, F-R-M: loops or no loops

Feedforward: single-node, single-layer, multilayer (no loops) · Feedback: self, recurrent single-layer, multilayer (loops back).

Quick self-testSearch on YouTube

1. Map each artificial part (input, weight, sum, activation, output) to its biological part.

Inputs map to dendrites. Weights map to synaptic strength. Sum maps to the cell body. Activation maps to firing. Output maps to the axon.

2. Differentiate the MP neuron from the Rosenblatt perceptron in three points.

MP uses Boolean inputs and fixed weights with no learning. The perceptron accepts real inputs and learns weights and bias. MP sets the threshold by hand, while the perceptron shifts it through w0w_0.

3. Weights are 1,11, 1 with threshold 22. Compute the outputs for (0,1)(0,1) and (1,1)(1,1). Which gate is it?

(0,1)(0,1) sums to 1<21 \lt 2, so output is 00. (1,1)(1,1) sums to 2≥22 \ge 2, so output is 11. The full table is AND.

4. Solve for OR: which inequality does (0,0)(0,0) give, and does w=[−1,1,1]w = [-1, 1, 1] satisfy all rows?

(0,0)(0,0) gives w0<0w_0 \lt 0. The triple gives −1-1, 00, 00, 11 across the four rows. All four tests pass, so it implements OR.

5. Starting from w=[−1,0,0]w = [-1, 0, 0], what is zz for OR input (1,0)(1,0) and what is the update?

z=−1<0z = -1 \lt 0 predicts 00 against true 11. Add the input: ww becomes [0,1,0][0, 1, 0].

6. With w=[0,1,0]w = [0, 1, 0], what does PLA do on OR input (0,0)(0,0), and why?

z=0≥0z = 0 \ge 0 predicts 11 against true 00. Subtract the input [1,0,0][1, 0, 0]: ww becomes [−1,1,0][-1, 1, 0]. Subtraction fixes false alarms.

7. Compute σ(−0.9)\sigma(-0.9) and σ(0.7)\sigma(0.7) to three decimals. What trend do they show?

σ(−0.9)=0.289\sigma(-0.9) = 0.289 and σ(0.7)=0.668\sigma(0.7) = 0.668. Activity rises with zz. The sigmoid grades the response instead of switching hard.

8. Three step neurons give how many patterns, and three 10-level sigmoid neurons give how many?

Step gives 23=82^3 = 8 patterns. Graded gives 103=100010^3 = 1000 patterns. More levels expand the solution space.

9. Why does PLA converge on OR but never settle on overlapping classes?

OR is linearly separable, so a separator exists and PLA makes finite updates. Overlapping classes admit no separator, so mistakes never end and updates cycle forever.

10. Prove with four inequalities that no single perceptron implements XOR.

XOR needs w0<0w_0 \lt 0, w0+w1≥0w_0 + w_1 \ge 0, w0+w2≥0w_0 + w_2 \ge 0, w0+w1+w2<0w_0 + w_1 + w_2 \lt 0. The middle rows force w0>0w_0 \gt 0. The clash proves the need for hidden layers.

  • The artificial neuron copies biology: inputs (dendrites), weights (synapses), sum (cell body), activation (firing), output (axon).
  • The MP neuron (McCulloch and Pitts, 1943) uses Boolean inputs and a fixed threshold. It learns nothing.
  • AND with weights 1,11, 1 needs threshold 22. Only (1,1)(1,1) reaches it.
  • The perceptron (Rosenblatt, 1958) learns weights and bias. It handles only linear boundaries.
  • Step gives hard 00 or 11. Sigmoid σ(z)=1/(1+e−z)\sigma(z) = 1/(1+e^{-z}) grades activity (for example σ(0.7)=0.668\sigma(0.7) = 0.668).
  • Bias form: z=∑wixi+w0z = \sum w_i x_i + w_0 with w0=−tw_0 = -t. Fire when z≥0z \ge 0.
  • The boundary is ∑wixi+w0=0\sum w_i x_i + w_0 = 0. Two inputs give a line, three give a plane, more give a hyperplane.
  • OR needs w0<0w_0 \lt 0, w0+w1≥0w_0+w_1 \ge 0, w0+w2≥0w_0+w_2 \ge 0, w0+w1+w2≥0w_0+w_1+w_2 \ge 0. Both [−1,1,1][-1,1,1] and [−1,2,2][-1,2,2] pass.
  • PLA adds the input on a miss and subtracts it on a false alarm. It stops when all rows pass.
  • PLA converges in finite steps only for finite linearly separable sets. XOR is the canonical failure (w0<0\mathbf{w_0 \lt 0} clashes with w0>0\mathbf{w_0 \gt 0}).