Gradient descent

TopicGradient descent

Title

Two steps of gradient descent

ExampleW03.1

Step1 / 5

Mode

Given

Fit the line $h(x) = \theta_0 + \theta_1 x$ to the three points by gradient descent on $J(\theta) = \frac{1}{2m} \sum_i \left( h(x_i) - y_i \right)^2$ . Start from $\theta^{(0)} = (0, 0)$ with learning rate $\alpha = 0.1$ and take two steps, updating $\theta_0$ and $\theta_1$ together.

Points $(0, 1)$ , $(1, 3)$ , $(2, 4)$ , so $m = 3$
$\theta^{(0)} = (0, 0)$
$\alpha = 0.1$

Each step:

\theta := \theta - \alpha \nabla J(\theta)

$k$	$\theta_0$	$\theta_1$	$J(\theta)$
0
1
2

y

x

Fig.The three points, and the line after two steps

Read the problem

Each row of the table is one value of

\theta

and its cost. A step moves both parameters against the gradient,

\frac{\partial J}{\partial \theta_0} = \frac{1}{m} \sum_i (h - y)

and

\frac{\partial J}{\partial \theta_1} = \frac{1}{m} \sum_i (h - y) x

Sim

Gradient descent on the three points

Drag the start $\theta^{(0)}$ on the contours of $J$ , change $\alpha$ or the number of steps. The table fills step by step; past the largest $\alpha$ that converges, the steps overshoot and $J$ grows.

Assumed: supplied here, not in the Materials: $\theta_0$ and $\theta_1$ tuned from $-1$ to $3$ in steps of $0.1$ · $\alpha$ tuned from $0.01$ to $1$ in steps of $0.01$ · up to $30$ steps

\theta_1

\theta_0

Fig.Contours of

J(\theta)

. Drag

\theta^{(0)}

to start somewhere else.

y

x

Fig.The data, and the line after 2 steps

\alpha

0.10

\theta_0

at the start0.0

\theta_1

at the start0.0

Steps2

$k$	$\theta_0$	$\theta_1$	$J(\theta)$
0	0.0000	0.0000	4.3333
1	0.2667	0.3667	2.5231
2	0.4700	0.6456	1.4741

After 2 steps: $\theta_0$ = 0.4700, $\theta_1$ = 0.6456, $J(\theta)$ = 1.4741

Python

The same line by the normal equation

Real Python with numpy: the line gradient descent steps towards, solved in one step by $\theta = (X^{\mathsf{T}} X)^{-1} X^{\mathsf{T}} y$ . Edit the code and run it live.

y

x

h_\theta(x)

Fig.The three points and the least-squares line

h_\theta(x) = \theta_0 + \theta_1 x

The plot and output the code gave at build. Run live downloads Python (16.5 MB) and runs the code as you edit it.

Output

theta0 = 1.1667
theta1 = 1.5000
J(theta) = 0.0278

Code

# The line through the three points by the normal equation, solved in one step with numpy:
# theta = (X^T X)^-1 X^T y. Change the points or the model and run it again.
import numpy as np

x = np.array([0.0, 1.0, 2.0])
y = np.array([1.0, 3.0, 4.0])

X = np.column_stack([np.ones_like(x), x])  # a column of ones for theta0
theta = np.linalg.solve(X.T @ X, X.T @ y)
cost = np.sum((X @ theta - y) ** 2) / (2 * len(x))

print(f"theta0 = {theta[0]:.4f}")
print(f"theta1 = {theta[1]:.4f}")
print(f"J(theta) = {cost:.4f}")

ends = np.array([0.0, 3.0])
plot = [{"id": f"point-{i + 1}", "kind": "point", "at": [xi, yi]} for i, (xi, yi) in enumerate(zip(x, y))]
plot.append({"id": "fit", "kind": "line", "through": [[e, theta[0] + theta[1] * e] for e in ends]})

Worked examples

Two steps of gradient descent

Read the problem

Gradient descent on the three points

The same line by the normal equation