Gradient Descent & the Delta Rule

Source: Unit 2 §6

Why the delta rule exists

≡FactsThe gap the delta rule fills

• When the data is not linearly separable, the perceptron training rule may never converge.
• The delta rule converges instead toward a best-fit approximation of the target concept, separable or not.
• It gets there with gradient descent, searching the hypothesis space of weight vectors for the weights that best fit the data.

Gradient descent, the idea

We are minimising a cost function $J(\theta_0, \theta_1)$:

$$\min_{\theta_0, \theta_1} J(\theta_0, \theta_1)$$

→StepsThe whole algorithm in three lines

1. Start with some $\theta_0, \theta_1$, chosen at random.
2. Keep changing $\theta_0, \theta_1$ in whatever direction reduces $J$.
3. Repeat until you reach a minimum.

The trekking analogy. You are standing somewhere on a hilly surface. You look around, take a small step in the steepest downhill direction, and repeat. Eventually you stop moving, because every direction is uphill: you are at the bottom of a valley.

Gradient descent only ever walks downhill from where it happens to start, so two random initialisations can settle in two different valleys.

⚠GotchaDifferent starting points, different answers

Gradient descent finds a minimum, not the minimum. Two random initialisations can descend into two different local minima, and nothing in the algorithm can tell you that the valley you landed in is not the deepest one. This is a defining property of gradient descent, and its main weakness.

The update rule

Until convergence, update every parameter:

$$\theta_j \leftarrow \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta_0, \theta_1)$$

The derivative term is the slope of the tangent at the current point, so the step size is proportional to how steep the surface is right here.

⚠GotchaUpdate simultaneously, not one at a time

Compute all the updates from the old parameter values, then assign them together. Using a freshly updated $\theta_0$ while computing the update for $\theta_1$ is a different algorithm, and not the one that is guaranteed to descend.

What the derivative's sign does

For a single-variable $J(x)$:

Situation	Derivative	Update	Effect
Positive slope at point a	> 0	x ← x − α(+)	x moves left, toward the minimum
Negative slope at point b	< 0	x ← x − α(−)	x moves right, toward the minimum
At the minimum	= 0	x ← x − 0	x is unchanged - and stuck, if this minimum is only local

The sign takes care of itself: subtracting the gradient always points you downhill, whichever side of the valley you are on.

The learning rate α

$\alpha$ (also written $\eta$) controls how big a step you take downhill.

Same bowl, same start, two learning rates: α too small crawls, α too large overshoots and can bounce out entirely.

⇄CompareGetting α wrong in each direction

α too smallTiny steps. The descent is correct but **slow** - it can take an impractical number of iterations to reach the minimum.

α too largeThe step jumps past the bottom. It may **overshoot** the minimum, bounce around it, or **never converge** at all.

Gradient descent for perceptron learning

Define an error (cost) function over the weights. For output $o$ and target $t$, summing over the training rows $d$:

$$E(\vec{w}) = \frac{1}{2} \sum_d (t_d - o_d)^2$$

Symbol	Meaning
E(w⃗)	the error, treated as a function of the weights w⃗
t_d	target (expected) output for training row d
o_d	actual perceptron output for the current weights

≡FactsWhy the error is squared

• Squaring is mainly for ease of differentiation - the $\frac{1}{2}$ out front cancels the 2 that the power rule brings down.
• It also penalises big errors disproportionately, so one badly wrong prediction moves the weights more than several slightly wrong ones.

→StepsDescending on a two-input perceptron

1. The perceptron computes $W = w_0 + w_1 x_1 + w_2 x_2$.
2. Feed the training rows through it and evaluate $E(\vec{w}) = \frac{1}{2}\sum_d (t_d - o_d)^2$.
3. Apply the update rule to each of $w_0$, $w_1$ and $w_2$, all from the same old values.
4. Repeat. The weights descend to the minimum of $E$, which is the set of optimal weights.