Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Linear Regression, the Perceptron, and Online Learning

Linear Regression, the Perceptron, and Online Learning

Computer Science Dept, Ferdowsi University of Mashhad

Just as naive Bayes (a topic of another course) is a good starting point for classification tasks, linear regression models are a good starting point for regression tasks. Such models are popular because they can be fit quickly and are straightforward to interpret. You are already familiar with the simplest form of linear regression model (i.e., fitting a straight line to two-dimensional data), but such models can be extended to model more complicated data behavior.

Notebook Cell
Notebook Cell

Linear Model

Suppose that the true model is denoted by y=b+mx+ϵy = b + m x + \epsilon and the estimated model denoted by y^\hat{y} (Eq. 23.2 of Zaki book Zaki & Meira (2020)):

y^=β0+β1x=β0x0+β1x1 (ESL Notation)=θ0x0+θ1x1  (Ng Notation)=w0x0+w1x1(Zaki Notation)where:x0=1\begin{aligned} \\ \hat{y} &= \beta_0 + \beta_1 x \\ &= \beta_0 x_0+ \beta_1 x_1 \quad \ \textrm{(ESL Notation)}\\ &= \theta_0 x_0+ \theta_1 x_1 \quad \ \ \textrm{(Ng Notation)}\\ &= w_0 x_0+ w_1 x_1 \quad\textrm{(Zaki Notation)}\\ \\ &\textrm{where:}\\ &x_0 = 1 \end{aligned}

If we have:

x=[x0x1],w=[w0w1]\mathbf{x} = \begin{bmatrix} x_0\\x_1 \end{bmatrix}, \mathbf{w} = \begin{bmatrix} w_0\\w_1 \end{bmatrix}

then y^\hat{y} can be considered as dot product of two vectors:

y^=w0x0+w1x1=wTx\begin{aligned} \hat{y} = w_0 x_0+ w_1 x_1 = \mathbf{w}^T\mathbf{x} \end{aligned}

If ithi^{th} instance is shown by xi\mathbf{x}_i

xi=[xi,0xi,1],\mathbf{x}_i = \begin{bmatrix} x_{i,0}\\x_{i,1} \end{bmatrix},

then:

y^i=w0xi,0+w1xi,1\begin{aligned} \hat{y}_i = w_0 x_{i,0}+ w_1 x_{i,1} \end{aligned}

Sum of Squared Error (SSE):

SSE=∑i=1nerrori2=∑i=1n(yi^−yi)2=∑i=1n(w0xi,0+w1xi,1−yi)2=∑i=1n(wTxi−yi)2=∑i=1n(xiTw−yi)2=∣∣Xw−y∣∣22=(Xw−y)T(Xw−y)\begin{aligned} \textrm{SSE} &= \sum_{i=1}^n{error_i}^2 \\ &= \sum_{i=1}^n{(\hat{y_i} - y_i)}^2 \\ &= \sum_{i=1}^n{(w_0 x_{i,0} + w_1 x_{i,1} - y_i)}^2\\ &= \sum_{i=1}^n{(\mathbf{w}^T\mathbf{x}_{i} - y_i)}^2 = \sum_{i=1}^n{(\mathbf{x}_{i}^T\mathbf{w} - y_i)}^2\\ &= ||X\mathbf{w} - \mathbf{y}||_2^2 = (X\mathbf{w} - \mathbf{y})^T(X\mathbf{w} - \mathbf{y}) \end{aligned}

where:

X=[x1Tx2T⋮xnT],y=[y1y2⋮yn]X = \begin{bmatrix} \mathbf{x_1}^T \\ \mathbf{x_2}^T \\ \vdots \\ \mathbf{x_n}^T \end{bmatrix}, \mathbf{y} = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}

Data Generation

Synthetic Data Generation

(100, 1) (100, 2)
[[0.37454012]
 [0.95071431]
 [0.73199394]]
[[1.75778494]
 [2.87152788]
 [2.47316396]]
<Figure size 500x500 with 1 Axes>

Normal Equations

The Normal Equations provide a closed-form solution for finding the optimal parameters (coefficients) that minimize the cost function (usually the mean squared error) in linear regression.

  • The Normal Equations are derived by setting the partial derivatives of the cost function with respect to each coefficient to zero.

  • The Closed Form Solution refers to finding the optimal parameters directly using a mathematical formula, rather than an iterative optimization process.

We have to minimize: ∣∣Xw−y∣∣22||X\mathbf{w} - \mathbf{y}||_2^2 wrt w\mathbf{w}, which is equal to the famous form minx∣∣Ax−b∣∣22min_{x}||Ax - b||_2^2. Temporary we use β\beta, instead of w\mathbf{w} and ignore the bold faces of letters; hence we have to minimize ∣∣Xβ−y∣∣22||X\beta-y||_2^2

SSE=∣∣Xβ−y∣∣22=(Xβ−y)T(Xβ−y)=((Xβ)T−yT)(Xβ−y)=(βTXT−yT)(Xβ−y)=βTXTXβ−βTXTy−yTXβ+yTy=βTMβ−(Xβ)Ty−yTXβ+yTy(M=XTX)=βTMβ−2yTXβ+yTy(ATB=BTA)=βTMβ−2zTβ+yTy(zT=yTX,z=XTy)\begin{aligned} SSE&=||X\beta-y||_2^2 = (X\beta-y)^T(X\beta-y)\\ &=((X\beta)^T-y^T)(X\beta-y) =(\beta^TX^T-y^T)(X\beta-y) \\ &=\beta^TX^T X\beta - \beta^T X^Ty -y^TX\beta + y^Ty\\ &=\beta^T M\beta - (X\beta)^Ty -y^TX\beta + y^Ty \qquad {(M=X^T X)}\\ &=\beta^T M\beta - 2y^TX\beta + y^Ty \qquad\qquad{(A^TB=B^TA)}\\ &=\beta^T M\beta - 2z^T\beta + y^Ty \qquad\qquad{(z^T=y^TX, z=X^Ty)} \end{aligned}

We Know that (See Matrix Calculus in Wikipedia):

∂yTx∂x=∂xTy∂x=y\frac{\partial y^Tx}{\partial x}=\frac{\partial x^Ty}{\partial x}=y
∂Mx∂x=M\frac{\partial Mx}{\partial x}=M

and if MM be a symmetric matrix:

∂xTMx∂x=2Mx\frac{\partial x^TMx}{\partial x}=2Mx

Hence:

∂SSE∂β=∂(βTMβ−2zTβ+yTy)∂β=2Mβ−2z=2XTXβ−2XTy\begin{aligned} \frac{\partial SSE}{\partial \beta} &= \frac{\partial (\beta^T M\beta - 2z^T\beta + y^Ty)}{\partial \beta} \\ &= 2M\beta-2z = 2X^TX\beta-2X^T y \end{aligned}

Set the derivative equal to zero:

∂SSE∂β=0⇒2XTXβ−2XTy=0⇒XTXβ=XTy⇒β=(XTX)−1XTy\begin{aligned} &\frac{\partial SSE}{\partial \beta}=0 \\ \Rightarrow & 2 X^TX\beta - 2X^T y = 0\\ \Rightarrow & X^TX\beta = X^Ty \\ \Rightarrow & \beta = (X^TX)^{-1}X^Ty \\ \end{aligned}

and with our previous notation: w=(XTX)−1XTy\mathbf{w} = (X^TX)^{-1}X^T\mathbf{y}

array([[1.02150962], [1.95402268]])

Using Scikit-learn

[1.02150962] [[1.95402268]]

If we have augmented data matrix X∈Rn×(d+1)X \in \mathbb{R}^{n\times (d+1)}, we have to set fit_intercept=False. In eq. (23.20) of Zaki this is denoted by D~\tilde{D}.

[[1.02150962 1.95402268]]

Bivariate Regression

In bivariate regression, we have two variables: one is the predictor variable (also known as the feature), and the other is the response variable (also known as the target).

  1. Predictor Variable (Feature):

    • The predictor variable (often denoted as x) is the input variable that we use to predict or explain the variation in the response variable.

    • In machine learning, this is equivalent to a feature. Features represent the characteristics or attributes of the data points.

    • For example, in a housing price prediction model, features could include square footage, number of bedrooms, location, etc.

  2. Response Variable (Target):

    • The response variable (often denoted as y) is the output variable that we are trying to predict or understand based on the predictor variable.

    • In machine learning, this is equivalent to the target. The target represents the value we want to predict.

    • For the housing price prediction model, the target would be the actual sale price of a house.

So, in summary, bivariate regression involves analyzing the relationship between two variables: one (the feature) is used to predict or explain the behavior of the other (the target). These terms are commonly used in both statistics and machine learning.

For further information about Multivariate Multiple Regression, see this blog post of Faradars.

Gradient Descent


In this section we are going to introduce the basic concepts underlying gradient descent. Some materials are borrowed from D2L.

One-Dimensional Gradient Descent

Gradient descent in one dimension is an excellent example to explain why the gradient descent algorithm may reduce the value of the objective function. Consider some continuously differentiable real-valued function f:R→Rf: \mathbb{R} \rightarrow \mathbb{R}. Using a Taylor expansion we obtain

f(x+h)=f(x)+hf′(x)+O(h2).f(x + h) = f(x) + h f'(x) + \mathcal{O}(h^2).

That is, in first-order approximation f(x+h)f(x+h) is given by the function value f(x)f(x) and the first derivative f′(x)f'(x) at xx. It is not unreasonable to assume that for small hh moving in the direction of the negative gradient will decrease ff. To keep things simple we pick a fixed step size η>0\eta > 0 and choose h=−ηf′(x)h = -\eta f'(x). Plugging this into the Taylor expansion above we get

f(x−ηf′(x))=f(x)−ηf′2(x)+O(η2f′2(x)).f(x - \eta f'(x)) = f(x) - \eta f'^2(x) + \mathcal{O}(\eta^2 f'^2(x)).

If the derivative f′(x)≠0f'(x) \neq 0 does not vanish we make progress since ηf′2(x)>0\eta f'^2(x)>0. Moreover, we can always choose η\eta small enough for the higher-order terms to become irrelevant. Hence we arrive at

f(x−ηf′(x))⪅f(x).f(x - \eta f'(x)) \lessapprox f(x).

This means that, if we use

x←x−ηf′(x)x \leftarrow x - \eta f'(x)

to iterate xx, the value of function f(x)f(x) might decline. Therefore, in gradient descent we first choose an initial value xx and a constant η>0\eta > 0 and then use them to continuously iterate xx until the stop condition is reached, for example, when the magnitude of the gradient ∣f′(x)∣|f'(x)| is small enough or the number of iterations has reached a certain value.

Gradient Descent on f(x)=x2f(x)=x^2

For simplicity we choose the objective function f(x)=x2f(x)=x^2 to illustrate how to implement gradient descent. Although we know that x=0x=0 is the solution to minimize f(x)f(x), we still use this simple function to observe how xx changes.

x = 9.00, f'(x) = 18.00, -lr*f'(x)=-1.80
x = 7.20, f'(x) = 14.40, -lr*f'(x)=-1.44
x = 5.76, f'(x) = 11.52, -lr*f'(x)=-1.15
x = 4.61, f'(x) =  9.22, -lr*f'(x)=-0.92
x = 3.69, f'(x) =  7.37, -lr*f'(x)=-0.74
x = 2.95, f'(x) =  5.90, -lr*f'(x)=-0.59
x = 2.36, f'(x) =  4.72, -lr*f'(x)=-0.47
x = 1.89, f'(x) =  3.77, -lr*f'(x)=-0.38
x = 1.51, f'(x) =  3.02, -lr*f'(x)=-0.30
x = 1.21, f'(x) =  2.42, -lr*f'(x)=-0.24
x = 0.97, f'(x) =  1.93, -lr*f'(x)=-0.19
x = 0.77, f'(x) =  1.55, -lr*f'(x)=-0.15
x = 0.62, f'(x) =  1.24, -lr*f'(x)=-0.12
x = 0.49, f'(x) =  0.99, -lr*f'(x)=-0.10
x = 0.40, f'(x) =  0.79, -lr*f'(x)=-0.08
<Figure size 800x500 with 1 Axes>

And another function see f(x)=3sin⁡(x)+(0.1x−3)2f(x)=3\sin(x)+(0.1x-3)^2 where is solved in ADS course using PSO.

<Figure size 800x600 with 1 Axes>

Using Gradient Descent for Regression in Machine Learning

Here we use training data for estimation of the model parameters and report the error on test data

Train-Test Split

((80, 2), (80, 1))
(<Figure size 1200x600 with 2 Axes>, array([<Axes: title={'center': 'Generated Data - Train'}, xlabel='x', ylabel='y'>, <Axes: title={'center': 'Generated Data - Test'}, xlabel='x', ylabel='y'>], dtype=object))
<Figure size 1200x600 with 2 Axes>

Step 0: Random Initialization

[[ 0.49671415]
 [-0.1382643 ]]

Step 1: Compute Model’s Predictions

array([0.39881299, 0.41404593, 0.36925186])
array([[0.39881299], [0.41404593], [0.36925186]])
(<Figure size 600x600 with 1 Axes>, <Axes: xlabel='x', ylabel='y'>)
<Figure size 600x600 with 1 Axes>

Step 2: Compute the Loss

$$

\begin{aligned} error_i &= \hat{y_i} - y_i\ where:\ y &= true_w_0 + true_w_1 x_1 + \epsilon\ &\hat{y}= w_0 x_0+ w_1 x_1 \end{aligned} $$

[2.36596945] [0.39881299]
(<Figure size 600x600 with 1 Axes>, <Axes: xlabel='x', ylabel='y'>)
<Figure size 600x600 with 1 Axes>

$$

\begin{aligned} MSE &= \frac{1}{n} \sum_{i=1}^n{error_i}^2 \ &= \frac{1}{n} \sum_{i=1}^n{(\hat{y_i} - y_i)}^2 \ &= \frac{1}{n} \sum_{i=1}^n{(w_0 x_{i,0} + w_1 x_{i,1} - y_i)}^2 \end{aligned} $$

(80, 1)
2.6401126993616817

Loss Surface

(<Figure size 1200x600 with 2 Axes>, (<Axes3D: title={'center': 'Loss Surface'}, xlabel='b', ylabel='w'>, <Axes: title={'center': 'Loss Surface'}, xlabel='b', ylabel='w'>))
<Figure size 1200x600 with 2 Axes>

Step 3: Compute the Gradients

∂MSE∂wj=∂∂wj1n(∑i=1nerrori2)=1n∑i=1n∂errori2∂wj=1n∑i=1n∂(yi^−yi)2∂wj=1n∑i=1n2∂(yi^−yi)∂wj(yi^−yi)=1n∑i=1n2∂(yi^−yi)∂yi^⋅∂yi^∂wj(yi^−yi)=21n∑i=1nxi,j(yi^−yi)=21n∑i=1nxi,jerrori\begin{aligned} \frac{\partial{MSE}}{\partial{w_j}} &= \frac{\partial{}}{\partial{w_j}}\frac{1}{n} \big(\sum_{i=1}^n{error_i}^2\big) =\frac{1}{n} \sum_{i=1}^n{\frac{\partial{error_i^2}}{\partial{w_j}}} \\ &= \frac{1}{n} \sum_{i=1}^n{\frac{\partial{{(\hat{y_i} - y_i)}^2}}{\partial{w_j}}} \\ &= \frac{1}{n} \sum_{i=1}^n{2\frac{\partial{(\hat{y_i} - y_i)}}{\partial{w_j}} (\hat{y_i} - y_i)}\\ &= \frac{1}{n} \sum_{i=1}^n{2\frac{\partial{(\hat{y_i} - y_i)}}{\partial{\hat{y_i}}} \cdot \frac{\partial{\hat{y_i}}}{\partial{w_j}} (\hat{y_i} - y_i)} \\ &= 2 \frac{1}{n} \sum_{i=1}^n{x_{i,j} (\hat{y_i} - y_i)}= 2 \frac{1}{n} \sum_{i=1}^n{x_{i,j} error_i} \end{aligned}
-3.0224384959608583 -1.7706733515907813
(80, 2)

Vectorized form

(2,) [-3.0224385  -1.77067335]
(2, 1) [[-3.0224385 ]
 [-1.77067335]]

Backpropagation

Step 4: Update the Parameters

$$

\begin{aligned} & b = b - \eta \frac{\partial{MSE}}{\partial{b}} \ & w = w - \eta \frac{\partial{MSE}}{\partial{w}} \end{aligned} $$

(2, 1) (2, 1)
[0.49671415] [-0.1382643]
[[0.798958  ]
 [0.03880303]]
[0.798958]
(<Figure size 600x600 with 1 Axes>, <Axes: xlabel='x', ylabel='y'>)
<Figure size 600x600 with 1 Axes>

Step 5: Repeat the above updating!

array([[1.11648206], [1.75056848]])
(<Figure size 600x600 with 1 Axes>, <Axes: xlabel='x', ylabel='y'>)
<Figure size 600x600 with 1 Axes>
<Figure size 640x480 with 1 Axes>

Using PyTorch auto grad

  • PyTorch is a Python-based tool for scientific computing that provides several main features:

    • torch.Tensor, an n-dimensional array similar to that of numpy, but which can run on GPUs

    • Computational graphs for building neural networks

    • Automatic differentiation for training neural networks (more on this next lecture)

  • You can install PyTorch from: https://pytorch.org/

Backward

Differntiationg using backward function

https://pytorch.org/tutorials/beginner/pytorch_with_examples.html

tensor([[1.1165], [1.7506]], dtype=torch.float64, requires_grad=True)

https://pytorch.org/tutorials/beginner/pytorch_with_examples.html

  • PyTorch: Defining new autograd functions

  • PyTorch: nn module

  • PyTorch: optim

  • PyTorch: Custom nn Modules

Using PyTorch library

Linear(in_features=2, out_features=1, bias=False)
None
Parameter containing:
tensor([[1.0940, 1.7949]], requires_grad=True)
tensor([1.0940, 1.7949], grad_fn=<SelectBackward0>)
tensor(1.0940, grad_fn=<SelectBackward0>)
1.093968391418457
1.0939684
(<Figure size 600x600 with 1 Axes>, <Axes: xlabel='x', ylabel='y'>)
<Figure size 600x600 with 1 Axes>

From Regression to Classification

So far the target yy was a number and the loss was the squared error. In classification the target is a label, and the same linear model becomes a linear score function

f(x)=w⊤x+b,y^=sign⁡(f(x)),f(x) = w^\top x + b, \qquad \hat y = \operatorname{sign}\big(f(x)\big),

whose zero set {x:w⊤x+b=0}\{x : w^\top x + b = 0\} is the decision boundary: a hyperplane with normal vector ww. Two remarks before the algorithm.

  • The pair (w,b)(w, b) is defined only up to a positive scale: (w,b)(w,b) and (2w,2b)(2w, 2b) produce the same boundary. Everything below is about the direction of ww, not about its length.

  • The squared error is the wrong loss here. With labels yi∈{−1,+1}y_i \in \{-1, +1\}, a confidently wrong point has a huge mean-squared loss although it is only one mistake, and a point that is correct but close to the boundary is penalised although it costs nothing. The loss that matches the decision rule is the 0-1 loss 1{y f(x)<0}\mathbb{1}\{y\,f(x) < 0\}, which is flat, discontinuous and has zero gradient almost everywhere. We therefore optimise a convex surrogate and keep the 0-1 loss as the quantity we actually report.

The Perceptron

The oldest online classifier (Rosenblatt, 1958). Take labels yi∈{−1,+1}y_i \in \{-1, +1\}, start from w=0w = 0 (the bias is absorbed by appending a column of ones to XX) and sweep the data:

if yi w⊤xi≤0:w←w+η yixi.\text{if } y_i\, w^\top x_i \le 0: \qquad w \leftarrow w + \eta\, y_i x_i .

Only mistakes change the parameters, and each update moves ww towards the point it got wrong: after the update yi w⊤xiy_i\, w^\top x_i has increased by η∥xi∥2\eta \|x_i\|^2, so that same point is now classified correctly. Nothing is stored — no loss history, no schedule, no matrix to invert — which is why the perceptron was implementable in 1958 hardware.

Convergence (Novikoff). Assume the data are linearly separable: there is a unit vector w∗w_* and a number γ>0\gamma > 0 with yi w∗⊤xi≥γy_i\, w_*^\top x_i \ge \gamma for every ii, and every point satisfies ∥xi∥≤R\|x_i\| \le R. Take η=1\eta = 1 and start from w(0)=0w^{(0)} = 0. After kk mistakes two inequalities hold:

  1. The projection grows. Each update adds yi w∗⊤xi≥γy_i\, w_*^\top x_i \ge \gamma, so w∗⊤w(k)≥kγw_*^\top w^{(k)} \ge k\gamma, and by Cauchy–Schwarz ∥w(k)∥≥kγ\|w^{(k)}\| \ge k\gamma.

  2. The norm grows slowly. Because the update happens only on a mistake, yi w(k−1)⊤xi≤0y_i\, w^{(k-1)\top} x_i \le 0, hence ∥w(k)∥2=∥w(k−1)∥2+2yiw(k−1)⊤xi+∥xi∥2≤∥w(k−1)∥2+R2\|w^{(k)}\|^2 = \|w^{(k-1)}\|^2 + 2 y_i w^{(k-1)\top}x_i + \|x_i\|^2 \le \|w^{(k-1)}\|^2 + R^2 and therefore ∥w(k)∥2≤kR2\|w^{(k)}\|^2 \le kR^2.

Combining the two, k2γ2≤∥w(k)∥2≤kR2k^2\gamma^2 \le \|w^{(k)}\|^2 \le kR^2, that is

k  ≤  (Rγ)2.k \;\le\; \left(\frac{R}{\gamma}\right)^{2}.

The bound is independent of nn and of dd — a rare luxury — but read it carefully: it counts mistakes, it is void when γ=0\gamma = 0 (non-separable data), and it says nothing about test error. A large margin is what makes the bound small, and that observation is the door to margin-based methods.

The perceptron is SGD on the hinge loss

The hinge loss of one example is

ℓ(w)=max⁡(0, 1−y w⊤x)\ell(w) = \max\big(0,\, 1 - y\, w^\top x\big)

whose (sub)gradient with respect to ww is −yx-y x when y w⊤x<1y\,w^\top x < 1 and 0 otherwise. One stochastic gradient step with rate η\eta reads

w←w+η yxif y w⊤x<1,w←wotherwise.w \leftarrow w + \eta\, y x \quad\text{if } y\,w^\top x < 1, \qquad w \leftarrow w \quad\text{otherwise.}

Ignoring the threshold 1, this is precisely the perceptron rule. So the perceptron is not a separate species: it is the crudest member of the family used in the previous sections, with the squared loss replaced by the hinge loss and the average gradient replaced by a single-sample one.

Lab 1: the perceptron on separable data, and the bound

Two Gaussian blobs, a known separating direction, and a count of the mistakes per epoch. We also compute the two numbers of the theorem, RR and γ\gamma, and check that the total number of mistakes stays below (R/γ)2(R/\gamma)^2.

R = 3.280,  gamma = 1.409,  (R/gamma)^2 = 5.4
mistakes per epoch: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
total mistakes: 1
training accuracy: 1.0
<Figure size 500x500 with 1 Axes>

Why a single unit is not enough

The four points of the XOR problem are not linearly separable, so the perceptron has no ww that classifies them: the mistakes per epoch stop decreasing, and the accuracy stays at chance. This is not a defect of the learning rate — it is a statement about hyperplanes.

mistakes per epoch: [4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
perceptron accuracy: 0.0
best accuracy of any straight line: 0.75

Online Learning

Batch learning sees all nn points before it updates anything; online learning sees one point at a time and has to predict before the label arrives. The perceptron is an online algorithm, and its mistake bound is an online guarantee: on any ordering of separable data the total number of mistakes is at most (R/γ)2(R/\gamma)^2, whatever the order.

Three practical consequences, which is why the idea outlived the algorithm:

  • No stored dataset. The update uses one example, which is what makes streaming and very large nn possible; the batch gradient of the previous section is the same step averaged over the sample.

  • The order matters. Sweeping the data in the given order can lock the model into a bad route; shuffling each epoch — and averaging the iterates, the averaged perceptron — is the standard fix.

  • Learning rate. With ηt=η0/t\eta_t = \eta_0/\sqrt{t} the accumulated noise stays finite; with a constant η\eta the iterate keeps jittering around the solution, which is visible in the loss curve of the next lab.

Modern first-order training (SGD, momentum, Adam) is this same loop with a smooth loss and a better step rule — so the two remaining notebooks of this block are, in a sense, the perceptron with more layers.

Lab 2: the same rule as torch.optim.SGD on the hinge loss

The previous section trained a linear model with torch and the squared error; here the loss is the hinge loss of the box above and the optimiser is the plain SGD of this lecture. Both models separate the data, but the weight vectors differ: the perceptron stops at the first separating vector it meets, while SGD on the hinge loss keeps pushing until every point has margin 1, so its solution is the one with the smallest hinge loss, not the one that merely separates. Which of the two is “better” depends on the goal — and on the test data, not on the training data.

mean hinge loss over the last epoch: 0.0
training accuracy: 1.0
weights (torch): [ 0.81206715 -0.2167826 ]
weights (perceptron, scaled): [ 0.78386254 -0.62093439]
<Figure size 640x480 with 1 Axes>

Exercises

  1. Show that the perceptron update leaves every correctly classified point correct only if the margin is small enough; find the largest η\eta for which one specific point stays correct after an update, in terms of yiw⊤xiy_i w^\top x_i and ∥xi∥2\|x_i\|^2.

  2. Prove that the perceptron on separable data reaches zero training error in finitely many updates, and give an example where a bad ordering makes it take at least nn updates.

  3. Derive the perceptron rule as SGD on the hinge loss (done above), then derive it as SGD on the squared loss with labels ±1\pm 1 — and explain why the resulting rule is not the same.

  4. Run Lab 1 with η=0.1\eta = 0.1 and with η=5\eta = 5, and plot the total number of mistakes against η\eta. Explain what the theorem says about η\eta (hint: the bound does not depend on η\eta; rescaled data does).

  5. Show that a single linear score cannot compute XOR, and write down the smallest two-layer network with ReLU units that computes it. This is the starting point of the next notebook.

  6. In an online setting, the cumulative mistake count is compared with the best fixed ww in hindsight. State why a linear model on non-separable data cannot have a o(T)o(T) bound, and what the perceptron guarantees instead (a bound in terms of ∑imax⁡(0,1−yiw∗⊤xi)\sum_i \max(0, 1-y_i w_*^\top x_i)).

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367