Home / MLT / Week 9

Week 9 · Perceptron and logistic regression

Official syllabus line: Discriminative Models - Perceptron; Logistic Regression

About 80 minEnd Term material (see exam radar)BSCS2007 · Arun Rajkumar

Before you start: MLF week 7 (gradient descent), MLF week 9 (sigmoid and log-loss), MLT week 8 (generative vs discriminative).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine you have red and green marbles scattered on a table. Your goal is to find a straight stick that you can place so all the red marbles are on one side and all the green marbles are on the other. This stick helps us separate things. This is exactly what a linear classifier does!
The Perceptron is like a simple teacher. It nudges the stick only when a marble is on the wrong side. Logistic Regression is gentler; it nudges the stick a little for every marble, based on how wrong its probability guess was. Both try to find the best straight stick to separate our data.
Let's try it! Start with the stick anywhere. Pick a red marble on the green side. Nudge the stick just enough to bring that red marble to its side. Repeat this for all marbles that are on the wrong side. Keep going until no marbles are misplaced. The stick has learned to separate them!
For your exam, remember the Perceptron updates only on mistakes, and only works if data is clearly separable. Logistic Regression always finds a solution, outputting probabilities. Both give a straight line boundary! Keep practicing, and you'll soon be an expert at separating data with your clever stick!

The one-minute story

Think of it like this

Spread red and green marbles on a table and try to lay a straight stick between them so all the reds are on one side and all the greens on the other. That stick is a linear classifier, and the whole job is to find it.

The perceptron is a very simple teacher. Start with any stick. Pick up one marble at a time; if it is on the wrong side, nudge the stick a little towards the right side for that marble. Keep going round until nobody is on the wrong side. If a straight stick can separate the marbles, this is guaranteed to work.

Logistic regression is a gentler teacher. Instead of a hard "this side / that side", it gives a probability: far on the red side means "99% red", right on the stick means "50/50". Instead of nudging only on mistakes, it nudges a little for every marble, in proportion to how wrong the probability was.

Both are discriminative: they learn the boundary directly and never model what the marbles look like.

By the end of this week you can:

describe a linear classifier and its decision boundary;
run the perceptron algorithm by hand and state its convergence theorem;
write the logistic regression model, loss and gradient;
compare the perceptron and logistic regression.

Words you need

Linear classifier - predicts by the sign of $\mathbf w^T\mathbf x+b$ .
Decision boundary - the set of points where $\mathbf w^T\mathbf x+b=0$ : a line in 2-D, a plane in 3-D.
Linearly separable - some line separates the two classes perfectly.
Label convention - the perceptron uses $y\in\{-1,+1\}$ ; logistic regression uses $y\in\{0,1\}$ .
Sigmoid $\sigma(z)=\dfrac1{1+e^{-z}}$ - squashes any number into $(0,1)$ .
Log-odds (logit) - $\ln\frac p{1-p}$ ; for logistic regression it equals $\mathbf w^T\mathbf x$ .

Idea 1: Linear classifiers

Predict $\hat y=\operatorname{sign}(\mathbf w^T\mathbf x+b)$ . The weight vector $\mathbf w$ is perpendicular to the boundary and points towards the positive side. The value $\mathbf w^T\mathbf x+b$ says which side and, divided by $\|\mathbf w\|$ , how far from the boundary.

A trick to avoid carrying $b$ around: add a constant feature 1 to every $\mathbf x$ and absorb $b$ into $\mathbf w$ . Then the prediction is just $\operatorname{sign}(\mathbf w^T\mathbf x)$ .

A point $(\mathbf x,y)$ with $y\in\{\pm1\}$ is classified correctly exactly when $y\,\mathbf w^T\mathbf x>0$ .

Idea 2: The perceptron algorithm

The idea

Perceptron (labels $y\in\{-1,+1\}$ , bias absorbed):

Start with $\mathbf w=\mathbf 0$ .
Go through the training examples. For each $(\mathbf x,y)$ : if $y\,\mathbf w^T\mathbf x\le0$ (a mistake), update

\mathbf w\leftarrow\mathbf w+y\,\mathbf x

Repeat passes over the data until a full pass makes no mistakes.

Why does the update help? After the update the new score for that same example is $y(\mathbf w+y\mathbf x)^T\mathbf x=y\mathbf w^T\mathbf x+\|\mathbf x\|^2$ , which is larger by $\|\mathbf x\|^2>0$ . So the mistake gets less wrong (it may still need more nudges).

Convergence theorem. If the data is linearly separable with margin $\gamma$ (every point is at least $\gamma$ from some separating boundary, with $\|\mathbf w^*\|=1$ ) and every $\|\mathbf x\|\le R$ , then the perceptron makes at most $(R/\gamma)^2$ mistakes and stops. If the data is not linearly separable (the classic example: XOR), it never converges, cycling forever. Also, the solution it finds is not unique: it depends on the order of the data.

Solved example: 1. A perceptron run

Question. Data: $(1,2)$ with $y=+1$ ; $(-1,-1)$ with $y=-1$ ; $(2,-1)$ with $y=+1$ (bias already absorbed). Run the perceptron from $\mathbf w=(0,0)$ , going through the points in this order.

Solution.

Pass 1.

$(1,2),+1$ : $y\,\mathbf w^T\mathbf x=0\le0$ mistake. $\mathbf w\leftarrow(0,0)+(1,2)=(1,2)$ .
$(-1,-1),-1$ : $\mathbf w^T\mathbf x=-3$ , $y\cdot(-3)=3>0$ correct.
$(2,-1),+1$ : $\mathbf w^T\mathbf x=2-2=0$ , $y\cdot0\le0$ mistake. $\mathbf w\leftarrow(1,2)+(2,-1)=(3,1)$ .

Pass 2.

$(1,2)$ : $3+2=5>0$ ✓. $(-1,-1)$ : $-3-1=-4$ , times $-1$ is $4>0$ ✓. $(2,-1)$ : $6-1=5>0$ ✓.

No mistakes: stop with $\mathbf w=(3,1)$ after two updates. The boundary is $3x_1+x_2=0$ .

Idea 3: Logistic regression

Instead of a hard sign, model the probability of class 1:

P(y=1\mid\mathbf x)=\sigma(\mathbf w^T\mathbf x)=\frac1{1+e^{-\mathbf w^T\mathbf x}}

Equivalently, the log-odds are linear: $\ln\dfrac{P(y=1\mid\mathbf x)}{P(y=0\mid\mathbf x)}=\mathbf w^T\mathbf x$ . The class is predicted as 1 when $P>0.5$ , i.e. $\mathbf w^T\mathbf x>0$ , so the decision boundary is still the straight line $\mathbf w^T\mathbf x=0$ .

Training by maximum likelihood. With labels $y_i\in\{0,1\}$ the likelihood of the data is $\prod p_i^{y_i}(1-p_i)^{1-y_i}$ with $p_i=\sigma(\mathbf w^T\mathbf x_i)$ . Taking the negative log gives the cross-entropy (log) loss:

\mathcal L(\mathbf w)=-\sum_{i=1}^n\Big[y_i\ln p_i+(1-y_i)\ln(1-p_i)\Big]

It is convex with a lovely gradient:

\nabla\mathcal L(\mathbf w)=\sum_{i=1}^n(p_i-y_i)\,\mathbf x_i

("prediction minus truth, times the input"). There is no closed-form solution, so use gradient descent: $\mathbf w\leftarrow\mathbf w-\eta\sum_i(p_i-y_i)\mathbf x_i$ .

Extras. If the classes are perfectly separable the likelihood keeps improving as $\|\mathbf w\|\to\infty$ , so add a regulariser $\lambda\|\mathbf w\|^2$ (as in ridge) to keep $\mathbf w$ finite. For more than two classes, replace the sigmoid with softmax (week 12).

Solved example: 2. One gradient step of logistic regression

Question. Two examples (no bias): $\mathbf x_1=(1,2)$ with $y_1=1$ and $\mathbf x_2=(-1,-1)$ with $y_2=0$ . Start with $\mathbf w=(0,0)$ and use $\eta=0.1$ . Do one step.

Solution. With $\mathbf w=0$ , every $z=0$ , so $p_1=p_2=\sigma(0)=0.5$ .

\nabla\mathcal L=(0.5-1)(1,2)+(0.5-0)(-1,-1)=(-0.5,-1)+(-0.5,-0.5)=(-1,\,-1.5)

\mathbf w\leftarrow(0,0)-0.1(-1,-1.5)=(\mathbf{0.1},\,\mathbf{0.15})

The weights moved so that $\mathbf x_1$ gets a higher score and $\mathbf x_2$ a lower one. ✓

Solved example: 3. From score to probability

Question. $\mathbf w=(0.5,\,1)$ , bias $b=-2$ . What is $P(y=1\mid\mathbf x)$ at $\mathbf x=(2,3)$ ?

Solution. $z=0.5\cdot2+1\cdot3-2=2$ . $p=\sigma(2)=\frac1{1+e^{-2}}=\frac1{1+0.135}=\mathbf{0.881}$ . Predict class 1.

Idea 4: Perceptron versus logistic regression

	Perceptron	Logistic regression
Output	hard label $\pm1$	probability in $(0,1)$
Updates	only on mistakes	on every example, scaled by the error
Loss	mistake-driven (0-1 flavoured)	log-loss (smooth, convex)
Convergence	only if linearly separable	always fine (with regularisation)
Boundary	a line	a line

Your turn

Your turn: 1. Perceptron updates

Start from $\mathbf w=(0,0)$ . Examples in order: $(2,1)$ with $y=-1$ , then $(1,3)$ with $y=+1$ . Apply one pass of the perceptron.

Need a hint?

Update only when $y\,\mathbf w^T\mathbf x\le0$ .

Show the full solution

First: $\mathbf w^T\mathbf x=0$ , mistake: $\mathbf w=(0,0)+(-1)(2,1)=(-2,-1)$ . Second: $\mathbf w^T\mathbf x=-2-3=-5$ , $y\cdot(-5)=-5\le0$ , mistake: $\mathbf w=(-2,-1)+(1,3)=(\mathbf{-1},\,\mathbf2)$ .

Your turn: 2. Probabilities

A model has $\mathbf w=(2,-1)$ and $b=-3$ . Compute the class-1 probability at $\mathbf x=(3,1)$ and say which side of the boundary it is on.

Need a hint?

$z=\mathbf w^T\mathbf x+b$ .

Show the full solution

$z=6-1-3=2>0$ , so the positive side. $p=\sigma(2)=0.881$ .

Your turn: 3. The boundary

For $\mathbf w=(1,1)$ and $b=-4$ , write the decision boundary and give two points on it.

Need a hint?

Set $\mathbf w^T\mathbf x+b=0$ .

Show the full solution

$x_1+x_2=4$ . E.g. $(4,0)$ and $(2,2)$ . $\mathbf w$ is perpendicular to this line.

Your turn: 4. True or false

(a) The perceptron converges on any data set. (b) Logistic regression has a closed-form solution. (c) The logistic regression boundary is linear. (d) The log-loss is convex in $\mathbf w$ .

Need a hint?

Think about XOR and the gradient formula.

Show the full solution

(a) False, only if separable. (b) False, use gradient descent. (c) True. (d) True.

Your turn: 5. Margin and mistakes

The data have $\|\mathbf x\|\le5$ and are separable with margin $\gamma=0.5$ . Give the perceptron's mistake bound.

Need a hint?

$(R/\gamma)^2$ .

Show the full solution

$(5/0.5)^2=10^2=\mathbf{100}$ mistakes at most. A bigger margin means fewer.

Exam radar

In the End Term, summaries mention logistic regression in 23 papers, perceptron in 13 and perceptron algorithm in 15, weight update in 13, decision boundary in 19, sigmoid in 10.

Typical: "perform one update of the perceptron", "when does the perceptron converge?", the gradient of the log-loss ( $p-y$ times $\mathbf x$ ), "what is the decision boundary of logistic regression?" (linear), the probability computed from given weights, and a comparison table like the one above.

Watch out - real exam trap

Perceptron labels are $\pm1$ ; logistic labels are $0/1$ . The gradient formula $(p_i-y_i)\mathbf x_i$ assumes $0/1$ .
Update $\mathbf w+y\mathbf x$ only on a mistake (including the "score $=0$ " case).
Don't forget the bias: add a feature of 1.
The perceptron solution is not unique; logistic regression's is (when regularised).
Linearly separable is required for perceptron convergence, not for logistic regression to run.

Quick quiz

The perceptron update on a mistake is...

w minus y x
w plus y x
w times y
w plus x

The weights are moved towards the correct side: w <- w + y x.

The decision boundary of logistic regression is...

a circle
a straight line (hyperplane)
a parabola
not defined

Probability 0.5 occurs where w transpose x = 0, a hyperplane.

The gradient of the logistic log-loss for labels in {0,1} is...

sum of (y - p) squared
sum of (p - y) x
sum of p x
sum of y x

It is the prediction error times the input.

Select all TRUE statements. (select all that apply)

The perceptron stops only if the data is linearly separable.
Logistic regression outputs a probability.
Logistic regression has a closed-form solution.
The perceptron minimises the log-loss.

Logistic regression needs gradient descent, and the perceptron is a mistake-driven rule, not a log-loss minimiser.

Recap

Remember this

Linear classifier: $\operatorname{sign}(\mathbf w^T\mathbf x+b)$ ; $\mathbf w\perp$ boundary; correct iff $y\mathbf w^T\mathbf x>0$ .
Perceptron: on a mistake $\mathbf w\leftarrow\mathbf w+y\mathbf x$ ; converges iff separable; mistake bound $(R/\gamma)^2$ ; solution not unique.
Logistic regression: $P(y=1\mid\mathbf x)=\sigma(\mathbf w^T\mathbf x)$ ; log-odds linear; boundary linear; cross-entropy loss, gradient $\sum(p_i-y_i)\mathbf x_i$ ; gradient descent; regularise if separable.

Formulas to keep

Perceptron: mistake if $y\mathbf w^T\mathbf x\le0$ ; update $\mathbf w\leftarrow\mathbf w+y\mathbf x$ ; mistakes $\le(R/\gamma)^2$
Logistic: $p=\sigma(\mathbf w^T\mathbf x)=\frac1{1+e^{-\mathbf w^T\mathbf x}}$ ; $\ln\frac p{1-p}=\mathbf w^T\mathbf x$
Loss $-\sum[y\ln p+(1-y)\ln(1-p)]$ ; gradient $\sum(p_i-y_i)\mathbf x_i$ ; step $\mathbf w\leftarrow\mathbf w-\eta\nabla\mathcal L$

Connected weeks (learn them together)

MLF week 7 - Finding the lowest point: gradient descent: Training the perceptron and logistic regression is gradient descent.
MLF week 9 - Optimising with rules: Lagrange and KKT: Logistic regression written as an optimisation problem.
MLF week 11 - The exponential family: Logistic regression is a member of the exponential family of models.
MLP week 5 - Logistic regression in sklearn: Logistic regression: the theory, then the code.
MLP week 6 - Binary classifiers and how to judge them: Binary classifiers and their metrics.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 39 real questions on this week All End Term papers