2. Perceptron

Activity: Understanding Perceptrons and Their Limitations

This activity is designed to test your skills in Perceptrons and their limitations.

The thread running through the activity is separability: you will train the same perceptron on two datasets — one the algorithm can solve, one it cannot — and the interesting part is not that the second one fails, but how it fails.

Exercise 1

Separable Data: the case the perceptron was designed for

A — Generate the data

Generate two classes of 2D points, 1000 samples per class, from multivariate normal distributions:

• Class 0: Mean \(= [1.5, 1.5]\), Covariance \(= [[0.5, 0], [0, 0.5]]\)
• Class 1: Mean \(= [5, 5]\), Covariance \(= [[0.5, 0], [0, 0.5]]\)

The means are far apart relative to the spread, so the two clouds are linearly separable with at most a handful of exceptions.

Produce Figure 1: a scatter plot of the 2000 points, one color per class.

B — Implement the perceptron

Write a single-layer perceptron from scratch. This same implementation is reused in Exercise 2 — write it once, as a function or a class.

• Prediction. \(\hat{y} = \text{step}(\mathbf{w} \cdot \mathbf{x} + b)\), where \(\text{step}(z) = 1\) if \(z \geq 0\) and \(0\) otherwise.

• Update rule. For each sample \((\mathbf{x}, y)\), compute \(\hat{y}\) and apply

  \[ \mathbf{w} \leftarrow \mathbf{w} + \eta \, (y - \hat{y}) \, \mathbf{x}, \qquad b \leftarrow b + \eta \, (y - \hat{y}) \]

  with \(y, \hat{y} \in \{0, 1\}\). The error \((y - \hat{y})\) is \(0\) on a correct prediction — so correctly classified samples produce no update — and \(+1\) or \(-1\) on the two kinds of mistake.

  Why not \(\mathbf{w} \leftarrow \mathbf{w} + \eta \, y \, \mathbf{x}\)?

  You will find that form in many textbooks. It belongs to the convention where labels are \(-1\) and \(+1\). With the \(0/1\) labels used here it would never update on Class 0, and the perceptron could never correct a false positive. Match the rule to your labels.

• Initialization. Draw \(\mathbf{w}\) from rng.normal(0, 0.01, size=2) and set \(b = 0\). Do not start from \(\mathbf{w} = \mathbf{0}\) — item D asks you to reason about the learning rate, and from an all-zero start the learning rate provably changes nothing (it only rescales \(\mathbf{w}\), leaving the decision boundary and the epoch count identical).

• Learning rate. \(\eta = 0.01\).

• Stopping. Train until a full pass over the dataset produces no update, or for a maximum of 100 epochs, whichever comes first. Record the accuracy on the full dataset after every epoch.

C — Train and measure

1. Train the model and report the final \(\mathbf{w}\), the final \(b\), the number of epochs, and the final accuracy.
2. Produce Figure 2: the decision boundary \(\mathbf{w} \cdot \mathbf{x} + b = 0\) drawn over the data points, with any misclassified points marked differently.
3. Produce Figure 3: accuracy \(\times\) epoch.

D — Analysis

1. Why does separable data converge quickly? Connect your answer to the update rule: what happens to the number of updates per epoch as training progresses?
2. Re-run the training with \(\eta = 1.0\), changing nothing else. Report the epoch count and the final accuracy, and compare the direction of \(\mathbf{w}\) (that is, \(\mathbf{w} / \lVert \mathbf{w} \rVert\)) against the \(\eta = 0.01\) run. Both runs should reach 100%, but by different boundaries — explain what \(\eta\) controls, given that every update adds \(\eta \, \mathbf{x}\) to weights that started at a magnitude of about \(0.01\).
3. Now argue what would have happened from \(\mathbf{w} = \mathbf{0}\), \(b = 0\). Show algebraically that running the whole training twice, with \(\eta_1\) and \(\eta_2\), produces weights that differ only by the constant factor \(\eta_2 / \eta_1\) — so the decision boundary and the epoch count are identical and \(\eta\) has no effect at all. This is why item B forbids the zero start.

Exercise 2

Overlapping Data: the case the perceptron cannot solve

A — Generate the data

Generate two classes of 2D points, 1000 samples per class:

• Class 0: Mean \(= [3, 3]\), Covariance \(= [[1.5, 0], [0, 1.5]]\)
• Class 1: Mean \(= [4, 4]\), Covariance \(= [[1.5, 0], [0, 1.5]]\)

The means are now close together and the spread is three times larger, so the clouds overlap heavily and no straight line separates them.

Produce Figure 4: a scatter plot of the 2000 points, one color per class.

B — Train, keeping the best weights

Reuse the implementation from Exercise 1, unchanged, with the same \(\eta = 0.01\) and the same 100-epoch cap. Because the data is not separable the training loop will never stop updating, so you will track two sets of weights:

• the final weights — whatever the loop happens to hold after the last epoch;
• the pocket weights — the best-so-far: every time an update produces a higher accuracy on the full dataset than any previously seen, copy \((\mathbf{w}, b)\) into your "pocket" and keep it. This is the pocket algorithm, and the copy is the only thing you add to the loop.

Report, for both sets of weights: \(\mathbf{w}\), \(b\), and the accuracy.

C — Figures

1. Produce Figure 5: both decision boundaries — final and pocket — drawn over the data points, with misclassified points marked.
2. Produce Figure 6: two curves against epoch — the accuracy of the current weights, and the best-so-far (pocket) accuracy.

D — Analysis

1. The best straight line for this data scores about 73%. Your pocket weights should land close to that; your final weights should not. Explain the gap. Where does the final boundary sit relative to the data cloud, and why does the training loop leave it there? Hint: compare how far \(b\) moves per mistake against how far \(\mathbf{w}\) moves, given that \(\lVert \mathbf{x} \rVert \approx 5\) for this data.
2. Compare Figure 3 with Figure 6. In Exercise 1 the accuracy curve settles; here it does not. What does the perceptron convergence theorem guarantee, and which of its assumptions does this dataset violate?
3. Does adding more epochs fix it? Does a smaller \(\eta\)? Justify your answer from the update rule rather than by trial and error.

Results summary

Close the report with this table, filled in:

Evaluation Criteria

The deliverable for this activity is a report that includes:

1. A brief description of your implementation approach and any challenges faced.
2. The code for the perceptron and for the data generation, commented.
3. Figures 1 to 6, numbered as requested.
4. Your answers to the analysis questions in items D.
5. The Results summary table.

Important Notes:

• The deliverable is a GitHub Pages site backed by a public repository — see Submission Format for the required layout, front matter and checklist;

• There is a strict no-plagiarism policy. Any form of plagiarism will result in a zero grade for the activity and may lead to further disciplinary action under the university's academic integrity policies;

• The deadline for each activity is not extended — NO EXCEPTIONS will be made for late submissions.

• AI collaboration is allowed, but each student MUST UNDERSTAND and be able to explain every part of the submitted code and analysis. Any use of AI tools must be properly cited. ORAL EXAMS may be conducted.

• All deliverables for individual activities should be submitted through the course platform insper.blackboard.com.

Grading Criteria:

Each row is worth the points indicated, awarded in full, partially (half), or not at all: in full when the item is complete and correct; partially when it is implemented but missing the requested analysis, or when the analysis lacks the numerical result that supports it; zero when absent or incorrect.

The accuracy value itself is not graded — Exercise 2 is supposed to score badly. What is graded is the method, the figures, and reporting honestly what you got.

Exercise 1 — Separable data (4 points):

Exercise 2 — Overlapping data (4 points):

Report (2 points):