The Ancient Secrets of Prediction

A fitted model is just a list of coefficients --- a vector. Evaluating it at a point is a dot product. Build that toolkit first.

dot_product(a, b) multiplies element-by-element and sums: dot_product([1, 2], [3, 4]) is 1*3 + 2*4 = 11.

Tasks:

1. Write dot_product(a, b).
2. Verify with these assertions:

assert dot_product([1, 2], [3, 4]) == 11
assert dot_product([1, 0, 2], [5, 5, 5]) == 15
assert dot_product([2], [7]) == 14

The length of a vector is the distance formula in disguise: $\|v\| = \sqrt{v \cdot v}$ --- reuse your dot_product.

A unit vector keeps the direction but has length 1: divide every component by the length. convert_to_unit([3, 4]) -> [0.6, 0.8].

Tasks:

1. Write vector_length(v) using dot_product and math.sqrt.
2. Write convert_to_unit(v) that divides each component by the length.
3. Verify:

assert vector_length([3, 4]) == 5.0
assert convert_to_unit([3, 4]) == [0.6, 0.8]
assert abs(vector_length(convert_to_unit([2, 3, 6])) - 1.0) < 1e-9

How aligned are two vectors? Take the dot product of their unit versions. The result is the cosine of the angle between them:

• same direction -> 1.0
• perpendicular -> 0.0
• opposite -> -1.0

This one number is how modern systems compare documents, faces and embeddings --- you will meet it again the moment you touch LLMs.

Tasks:

1. Write cosine_similarity(a, b) using convert_to_unit and dot_product.
2. Verify:

assert abs(cosine_similarity([1, 2], [2, 4]) - 1.0) < 1e-9    # same direction
assert abs(cosine_similarity([1, 0], [0, 1])) < 1e-9           # perpendicular
assert abs(cosine_similarity([1, 2], [-1, -2]) + 1.0) < 1e-9   # opposite

A matrix is a list of rows. In the product C = A @ B, entry C[i][j] is the dot product of row i of A with column j of B. An (n x k) matrix times a (k x m) matrix gives an (n x m) matrix.

Write matrix_mul(A, B) using your dot_product.

Hint: column j of B is [row[j] for row in B].

Verify:

A = [[1, 2],
     [3, 4]]
B = [[5, 6],
     [7, 8]]
assert matrix_mul(A, B) == [[19, 22], [43, 50]]

M = [[1, 2, 3],
     [4, 5, 6]]
v = [[1], [0], [2]]                      # a column vector
assert matrix_mul(M, v) == [[7], [16]]   # (2x3) @ (3x1) -> (2x1)

Two vectors have a cosine similarity of 0. What does this tell you about their relationship?

A. They are identical

B. They point in exactly opposite directions

C. They are perpendicular (at 90 degrees) --- knowing one tells you nothing about the other

D. One of the vectors is all zeros

We store the equation $a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b$ as the list [a1, a2, ..., an, b], and a system as a list of such lists --- exactly the representation you used in Loops and Arrays, Part 5.

Paste your solve_equations (with its helpers solve_for_first_variable, eliminate_variable_pair, eliminate_variable) into the code cell. The test must pass before you go on.

(Skipped that chapter? Go invent it there first --- this whole chapter stands on it.)

Think: your solver eliminates one variable at a time, and each elimination touches every remaining equation, and each equation has that many coefficients --- three nested loops. Roughly how does the running time grow with n equations? If solving 4 equations takes 1 second, what would 8 take? Keep that number in mind --- it returns at the end of the chapter.

Redo the opening story with your tools:

1. Build the two equations in (beta1, beta0): trip 1 -> [3, 1, 6], trip 2 -> [5, 1, 8].
2. solve_equations gives you beta = [price, parking].
3. Predict the 10-apple trip with dot_product(beta, [10, 1]).

Traffic through a junction is measured three times:

The growth is not linear (check the gaps: +6, +8). Assume a quadratic: $traffic = a t^2 + b t + c$. Each measurement is one equation in $(a, b, c)$ --- for $t=1$: $a + b + c = 6$, and so on.

Tasks:

1. Build the three equations.
2. Solve for (a, b, c).
3. Predict the traffic at t = 4.

Automate it. Write solve_poly(x, y, xp):

• x and y are n observed points; assume a polynomial of degree n - 1.
• For each point build the row [x_i**(n-1), ..., x_i**2, x_i, 1, y_i] and solve for the coefficients.
• Return the polynomial's value at xp --- a dot_product of the coefficients with the matching powers of xp.

Think: why do n points pin down exactly a degree-(n-1) polynomial --- what goes wrong with fewer coefficients, and what freedom is left with more?

A factory reports:

Try a line through the first two points: slope 3, intercept 5 --- but then input 3 predicts 14, not 16. Through points 1 and 3: slope 4, intercept 4 --- but input 2 predicts 12, not 11. No line passes through all three points. Real measurements are noisy; perfect solving just broke.

New plan: accept an imperfect line, but pick the one that is least wrong. But how do you measure how wrong a line is? You'll figure that out in the next exercise.

For a candidate line $y = mx + c$, each data point $(x_i, y_i)$ has an error: the prediction $mx_i + c$ minus the actual $y_i$. But some errors are positive (prediction too high) and some are negative (prediction too low) --- if you just add them up, they cancel out.

Think: How do you prevent cancellation? What operation makes all errors positive? Then how do you combine them into a single "total wrongness" score?

Write total_error(m, c, data) where data is a list of (x, y) pairs.

At the minimum of $E$, nudging $m$ or $c$ changes nothing --- both partial derivatives are zero.

Your task:

1. Write the partial derivative $\frac{\partial E}{\partial m}$ --- differentiate each term of $E = \sum_i (mx_i + c - y_i)^2$ with respect to $m$.
2. Set it to zero and simplify. You should get a linear equation in $m$ and $c$.
3. Do the same for $\frac{\partial E}{\partial c}$.
4. Plug in the factory data values and use solve_equations from Part 2 to find $m$ and $c$.

Use solve_equations on the two equations you derived. The test also nudges your answer in every direction to confirm no neighbor does better --- the definition of a minimum.

Wrap it up. Write best_line(data):

1. From the (x, y) pairs compute $\sum x^2$, $\sum x$, $\sum xy$, $\sum y$ and $n$.
2. Build the two normal equations and solve_equations.
3. Return (m, c).

On data that is perfectly linear it must recover the exact line --- least squares contains exact fitting as a special case.

In the least squares method, you minimize the sum of squared errors. Why not just minimize the sum of raw errors (without squaring)?

A. Squaring makes the computation faster

B. Raw errors can be positive or negative --- a prediction 10 too high and one 10 too low would cancel out, giving a total error of 0 even though both predictions are wrong

C. Python can't handle negative numbers in sums

D. Squaring is needed because the data might contain negative values

So far matrices held data (trips, prices). But matrix_mul has a second life: a matrix can be a machine that moves points. Every video game, every 3D animation, every graphics chip is built on this.

Keep points as rows, [x, y]. Multiplying a stack of points by one 2x2 matrix moves all of them at once with your existing matrix_mul --- no new code needed.

The matrix that rotates every point counter-clockwise by angle $\theta$ (with points as rows) is:

$$R(\theta) = \begin{pmatrix} \cos\theta & \sin\theta \ -\sin\theta & \cos\theta \end{pmatrix}$$

Write rotation_matrix(angle_degrees) returning that 2x2 list-of-lists. Use math.radians to convert, then math.cos / math.sin.

Sanity checks worth predicting before you run: the point [1, 0] (due east) rotated 90 degrees should land at [0, 1] (due north). Rotated 180 degrees, at [-1, 0].

Here is a kite, five points as rows (the last repeats the first so it draws closed):

kite = [[0, 0], [1, 2], [0, 5], [-1, 2], [0, 0]]

Rotate the entire kite by 45 degrees with one call to matrix_mul, storing the result in turned. Then run the provided plotting cell to see both.

A deep property to verify while you're here: rotation moves points but never stretches them. The test checks every point stays the same distance from the origin.

Rotation matrices are special. What happens with an arbitrary 2x2 matrix?

Build one from random numbers, apply it to the kite with matrix_mul, and plot the result (reuse the plotting code above). Run it several times.

Observe, then answer: straight edges stay straight, and parallel edges stay parallel --- but lengths and angles change: the kite gets stretched, squashed, sheared, maybe flipped. Every 2x2 matrix is some such linear transformation, and rotations are exactly the ones that preserve all lengths. (When a neural network multiplies data by a learned weight matrix, this stretching and squashing of space is literally what it's doing.)

What you just derived is Ordinary Least Squares, the same closed-form answer sklearn.linear_model.LinearRegression computes.

So why does the next chapter exist? Two cracks in the ancient method: solving grows like $n^3$ (your Part 2 estimate), and the derive-set-to-zero trick needs a formula for the derivative --- which complicated models don't offer. Gradient Descent fixes both by walking toward the minimum instead of jumping to it.