Linear AlgebraOrthogonality and Projections6 of 9
Orthogonality and Projections · 6

Fitting Models to Data: Features, Polynomials, and Regularization

When we have noisy data points, we want to find a formula that fits the overall pattern so we can predict y\target{y} at new values of xx.

1

Fitting a Straight Line with Least Squares

Suppose we want to fit a straight line y=w0+w1x\target{y} = \firstcol{w_0} + \secondcol{w_1 x} to the three data points (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,5)\data{(3, 5)} so we can predict y\target{y} at new inputs like x=2.5x = 2.5 or x=4x = 4.

Plugging our three points into y=w0+w1x\target{y} = \firstcol{w_0} + \secondcol{w_1 x} gives three equations for only two weights, w0\firstcol{w_0} and w1\secondcol{w_1}. Here is how projecting onto the column space in 3D finds the closest line:

Fitting a Straight Line with Least Squares
11
22
33
44
11
22
33
44
55
66
xx
yy
2.52.5
(1,1)\htmlClass{lc-blue}{(1, 1)}
(2,2)\htmlClass{lc-blue}{(2, 2)}
(3,5)\htmlClass{lc-blue}{(3, 5)}
??
??
y=w0+w1x\htmlClass{lc-blue}{y} = \htmlClass{lc-green}{w_0} + \htmlClass{lc-pink}{w_1 x}
Text solution
1. Stack the data points into feature columnsPlugging (1,1)\data{(1, 1)}, (2,2)\data{(2, 2)}, and (3,5)\data{(3, 5)} into w0(1)+w1x≈y\firstcol{w_0(1)} + \secondcol{w_1 x} \approx \target{y} gives one vector equation in 3D space.
w0[111]⏟Column 1+w1[123]⏟Column 2≈[125]⏟y\displaystyle \firstcol{w_0} \underbrace{\firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}}_{\firstcol{\text{Column 1}}} + \secondcol{w_1} \underbrace{\secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}}}_{\secondcol{\text{Column 2}}} \approx \underbrace{\target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}}}_{\target{y}}
2. Dot each column with the system to build ATAw=ATyA^T A w = A^T \target{y}For the error vector to be perpendicular to the plane, its dot product with each column must be zero, so we dot Column 1 and Column 2 with every vector in the equation.
Col 1 dots:[111]⋅[111]=3,[111]⋅[123]=6,[111]⋅[125]=8Col 2 dots:[123]⋅[111]=6,[123]⋅[123]=14,[123]⋅[125]=20\displaystyle \begin{aligned} & \firstcol{\text{Col 1 dots:}} \\ &\qquad \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = 3, \\ &\qquad \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} = 6, \\ &\qquad \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} \cdot \target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}} = 8 \\[6pt] & \secondcol{\text{Col 2 dots:}} \\ &\qquad \secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} = 6, \\ &\qquad \secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} = 14, \\ &\qquad \secondcol{\begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}} \cdot \target{\begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}} = 20 \end{aligned}
[36614]⏟ATA[w0w1]=[820]⏟ATy\displaystyle \underbrace{\begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}}_{A^T A} \begin{bmatrix} \firstcol{w_0} \\ \secondcol{w_1} \end{bmatrix} = \underbrace{\begin{bmatrix} 8 \\ 20 \end{bmatrix}}_{A^T \target{y}}
3. Double the first row and subtract to solve for the weightsSubtracting twice the first equation from the second leaves only w1\secondcol{w_1}, which we plug back in to find w0\firstcol{w_0}.
6w0+14w1=20−(6w0+12w1=16)2w1=4  ⟹  w1=2,w0=−43\displaystyle \begin{aligned} 6\firstcol{w_0} + 14\secondcol{w_1} &= 20 \\ -(6\firstcol{w_0} + 12\secondcol{w_1} &= 16) \\ \hline 2\secondcol{w_1} &= 4 \\ \implies \secondcol{w_1} &= 2, \quad \firstcol{w_0} = -\frac{4}{3} \end{aligned}

So the best-fit line is y=−43+2xy = -\frac{4}{3} + 2x, which comes as close as possible to all three points even though no straight line passes through all three.

Try moving the third data point to see how the 2D line and the 3D column-space projection change together:

Three points sit on one line in 2D when the data vector lies flat in the 3D plane, and when a point moves off the line, the best-fit line comes from the vector's perpendicular shadow on the plane.
2

Fitting Polynomial Curves

When our data points bend in a U-shape, a straight line cannot follow the pattern. We want to fit a parabola y=w0+w1x+w2x2\target{y} = \firstcol{w_0} + \secondcol{w_1 x} + \thirdcol{w_2 x^2} to the five noisy data points (−2,2)\data{(-2, 2)}, (−1,3)\data{(-1, 3)}, (0,1)\data{(0, 1)}, (1,1)\data{(1, 1)}, and (2,8)\data{(2, 8)}.

−2−2
−1−1
11
22
22
44
66
88
xx
yy
y=1+x+x2y = 1 + x + x^2

Even though x2\thirdcol{x^2} makes the graph curve, we can use the exact same column projection because the weights w0,w1,w2\firstcol{w_0}, \secondcol{w_1}, \thirdcol{w_2} still just multiply columns of numbers that we calculate from x\secondcol{x} ahead of time.

Fitting Polynomial Curves
−2−2
−1−1
11
22
22
44
66
88
xx
yy
y=w0+w1x+w2x2\htmlClass{lc-blue}{y} = \htmlClass{lc-green}{w_0} + \htmlClass{lc-pink}{w_1 x} + \htmlClass{lc-violet}{w_2 x^2}
w0\htmlClass{lc-green}{w_0}
1\htmlClass{lc-green}{1}
++
w1\htmlClass{lc-pink}{w_1}
x\htmlClass{lc-pink}{x}
++
w2\htmlClass{lc-violet}{w_2}
x2\htmlClass{lc-violet}{x^2}
≈\approx
y\htmlClass{lc-blue}{y}
Text solution
1. Square the x\secondcol{x} values to build the third feature columnEvaluating 1\firstcol{1}, x\secondcol{x}, and x2\thirdcol{x^2} at the five inputs gives three feature columns in 5D space that we combine to get as close as possible to the target vector y\target{y}.
w0[11111]⏟1 (Col 1)+w1[−2−1012]⏟x (Col 2)+w2[41014]⏟x2 (Col 3)≈[23118]⏟y\displaystyle \firstcol{w_0} \underbrace{\firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}}}_{\firstcol{1\text{ (Col 1)}}} + \secondcol{w_1} \underbrace{\secondcol{\begin{bmatrix} -2 \\ -1 \\ 0 \\ 1 \\ 2 \end{bmatrix}}}_{\secondcol{x\text{ (Col 2)}}} + \thirdcol{w_2} \underbrace{\thirdcol{\begin{bmatrix} 4 \\ 1 \\ 0 \\ 1 \\ 4 \end{bmatrix}}}_{\thirdcol{x^2\text{ (Col 3)}}} \approx \underbrace{\target{\begin{bmatrix} 2 \\ 3 \\ 1 \\ 1 \\ 8 \end{bmatrix}}}_{\target{y}}
2. Assemble the 3×33 \times 3 dot-product grid ATAA^T A and target dots ATyA^T \target{y}Dotting each of the three feature columns with every column and with y\target{y} turns the five equations into a 3×33 \times 3 system.
Col 1 dots:Col 1⋅Col 1=5,Col 1⋅Col 2=0,Col 1⋅Col 3=10,Col 1⋅y=15Col 2 dots:Col 2⋅Col 1=0,Col 2⋅Col 2=10,Col 2⋅Col 3=0,Col 2⋅y=10Col 3 dots:Col 3⋅Col 1=10,Col 3⋅Col 2=0,Col 3⋅Col 3=34,Col 3⋅y=44\displaystyle \begin{aligned} & \firstcol{\text{Col 1 dots:}} \\ &\qquad \firstcol{\text{Col 1}} \cdot \firstcol{\text{Col 1}} = 5, \\ &\qquad \firstcol{\text{Col 1}} \cdot \secondcol{\text{Col 2}} = 0, \\ &\qquad \firstcol{\text{Col 1}} \cdot \thirdcol{\text{Col 3}} = 10, \\ &\qquad \firstcol{\text{Col 1}} \cdot \target{y} = 15 \\[6pt] & \secondcol{\text{Col 2 dots:}} \\ &\qquad \secondcol{\text{Col 2}} \cdot \firstcol{\text{Col 1}} = 0, \\ &\qquad \secondcol{\text{Col 2}} \cdot \secondcol{\text{Col 2}} = 10, \\ &\qquad \secondcol{\text{Col 2}} \cdot \thirdcol{\text{Col 3}} = 0, \\ &\qquad \secondcol{\text{Col 2}} \cdot \target{y} = 10 \\[6pt] & \thirdcol{\text{Col 3 dots:}} \\ &\qquad \thirdcol{\text{Col 3}} \cdot \firstcol{\text{Col 1}} = 10, \\ &\qquad \thirdcol{\text{Col 3}} \cdot \secondcol{\text{Col 2}} = 0, \\ &\qquad \thirdcol{\text{Col 3}} \cdot \thirdcol{\text{Col 3}} = 34, \\ &\qquad \thirdcol{\text{Col 3}} \cdot \target{y} = 44 \end{aligned}
[5010010010034][w0w1w2]=[151044]\displaystyle \begin{bmatrix} 5 & 0 & 10 \\ 0 & 10 & 0 \\ 10 & 0 & 34 \end{bmatrix} \begin{bmatrix} \firstcol{w_0} \\ \secondcol{w_1} \\ \thirdcol{w_2} \end{bmatrix} = \begin{bmatrix} 15 \\ 10 \\ 44 \end{bmatrix}
3. Solve the middle row directly and eliminate w0\firstcol{w_0} between the outer rowsThe second row gives w1\secondcol{w_1} right away, and subtracting twice the first row from the third row finds w2\thirdcol{w_2}.
10w1=10  ⟹  w1=1(10w0+34w2)−(10w0+20w2)=44−30  ⟹  14w2=14  ⟹  w2=15w0+10(1)=15  ⟹  w0=1\displaystyle \begin{aligned} 10\secondcol{w_1} &= 10 \\ \implies \secondcol{w_1} &= 1 \\ (10\firstcol{w_0} + 34\thirdcol{w_2}) & \\ - (10\firstcol{w_0} + 20\thirdcol{w_2}) &= 44 - 30 \\ \implies 14\thirdcol{w_2} &= 14 \\ \implies \thirdcol{w_2} &= 1 \\ 5\firstcol{w_0} + 10(1) &= 15 \\ \implies \firstcol{w_0} &= 1 \end{aligned}

So the best-fit parabola is y=1+x+x2y = 1 + x + x^2. Notice a handy shortcut: because the inputs x=−2,−1,0,1,2x = -2, -1, 0, 1, 2 are symmetric around 00, the odd column x\secondcol{x} is perpendicular to both even columns 1\firstcol{1} and x2\thirdcol{x^2}, putting zeros in the grid that let you solve for w1\secondcol{w_1} on its own.

3

Custom Features and Multiple Inputs

Because each column is just a list of numbers evaluated at our data points, we can build columns out of waves like sin⁡(x)\secondcol{\sin(x)} and cos⁡(x)\thirdcol{\cos(x)}, exponentials like 2x\secondcol{2^x}, or separate input variables altogether.

Suppose we want to predict the price y\target{y} (in $100k\$100\text{k} units) of four houses from two different inputs, house size x1\firstcol{x_1} (in thousands of square feet) and number of bedrooms x2\secondcol{x_2}, by fitting the model y=w1x1+w2x2\target{y} = \firstcol{w_1 x_1} + \secondcol{w_2 x_2} to the four houses (1,1,4)(\firstcol{1}, \secondcol{1}, \target{4}), (1,2,3)(\firstcol{1}, \secondcol{2}, \target{3}), (2,1,4)(\firstcol{2}, \secondcol{1}, \target{4}), and (2,2,7)(\firstcol{2}, \secondcol{2}, \target{7}).

Custom Features and Multiple Inputs
size\htmlClass{lc-green}{\text{size}}
x1\htmlClass{lc-green}{x_1}
bedrooms\htmlClass{lc-pink}{\text{bedrooms}}
x2\htmlClass{lc-pink}{x_2}
price\htmlClass{lc-blue}{\text{price}}
y\htmlClass{lc-blue}{y}
1\htmlClass{lc-green}{1}
1\htmlClass{lc-pink}{1}
4\htmlClass{lc-blue}{4}
1\htmlClass{lc-green}{1}
2\htmlClass{lc-pink}{2}
3\htmlClass{lc-blue}{3}
2\htmlClass{lc-green}{2}
1\htmlClass{lc-pink}{1}
4\htmlClass{lc-blue}{4}
2\htmlClass{lc-green}{2}
2\htmlClass{lc-pink}{2}
7\htmlClass{lc-blue}{7}
y=w1x1+w2x2w1, w2=  ?\begin{aligned} \htmlClass{lc-blue}{y} &= \htmlClass{lc-green}{w_1 x_1} + \htmlClass{lc-pink}{w_2 x_2} \\[3pt] \htmlClass{lc-green}{w_1},\ \htmlClass{lc-pink}{w_2} &= \;? \end{aligned}
Text solution
1. Place each input variable into its own columnThe four house sizes form Column 1, the bedroom counts form Column 2, and the prices form the target vector y\target{y} in 4D space.
w1[1122]⏟size x1+w2[1212]⏟bedrooms x2≈[4347]⏟price y\displaystyle \firstcol{w_1} \underbrace{\firstcol{\begin{bmatrix} 1 \\ 1 \\ 2 \\ 2 \end{bmatrix}}}_{\firstcol{\text{size } x_1}} + \secondcol{w_2} \underbrace{\secondcol{\begin{bmatrix} 1 \\ 2 \\ 1 \\ 2 \end{bmatrix}}}_{\secondcol{\text{bedrooms } x_2}} \approx \underbrace{\target{\begin{bmatrix} 4 \\ 3 \\ 4 \\ 7 \end{bmatrix}}}_{\target{\text{price } y}}
2. Dot the two input columns with each other and with y\target{y}Taking the dot products in 4D space turns the four house equations into a 2×22 \times 2 system of normal equations.
Col 1⋅Col 1=10,Col 1⋅Col 2=9,Col 1⋅y=29Col 2⋅Col 1=9,Col 2⋅Col 2=10,Col 2⋅y=28\displaystyle \begin{aligned} & \firstcol{\text{Col 1}} \cdot \firstcol{\text{Col 1}} = 10, \\ & \firstcol{\text{Col 1}} \cdot \secondcol{\text{Col 2}} = 9, \\ & \firstcol{\text{Col 1}} \cdot \target{y} = 29 \\[6pt] & \secondcol{\text{Col 2}} \cdot \firstcol{\text{Col 1}} = 9, \\ & \secondcol{\text{Col 2}} \cdot \secondcol{\text{Col 2}} = 10, \\ & \secondcol{\text{Col 2}} \cdot \target{y} = 28 \end{aligned}
[109910][w1w2]=[2928]\displaystyle \begin{bmatrix} 10 & 9 \\ 9 & 10 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} = \begin{bmatrix} 29 \\ 28 \end{bmatrix}
3. Subtract and add the two symmetric rowsSubtracting the second equation from the first gives the difference of the weights, and adding the two equations gives their sum.
Row 1−Row 2:w1−w2=1Row 1+Row 2:19(w1+w2)=57  ⟹  w1+w2=3w1=2,w2=1\displaystyle \begin{aligned} \text{Row 1} - \text{Row 2:} \quad & \\ \firstcol{w_1} - \secondcol{w_2} &= 1 \\[4pt] \text{Row 1} + \text{Row 2:} \quad & \\ 19(\firstcol{w_1} + \secondcol{w_2}) &= 57 \\ \implies \firstcol{w_1} + \secondcol{w_2} &= 3 \\ \hline \firstcol{w_1} &= 2, \quad \secondcol{w_2} = 1 \end{aligned}

So the fitted model is y=2x1+x2y = 2x_1 + x_2, which tells us that each thousand square feet adds $200k\$200\text{k} to the house price and each bedroom adds $100k\$100\text{k}.

4

Overfitting and Nearly Parallel Columns

If adding feature columns makes our model more flexible, what goes wrong if we put in a long list of features like 1,x,x2,x3,…,x10\firstcol{1}, \secondcol{x}, \thirdcol{x^2}, x^3, \dots, x^{10} all at once?

Overfitting is when a model has so many features that it passes right through the random noise in our data points while swinging wildly away from them, making its predictions at new points useless.

Overfitting and Nearly Parallel Columns
1\htmlClass{lc-green}{1}
x\htmlClass{lc-pink}{x}
x2\htmlClass{lc-violet}{x^2}
x3x^3
x4x^4
x5x^5
⋯\cdots
x10x^{10}
11
22
11
22
33
44
xx
yy

When we fit 5 independent polynomial columns (1,x,x2,x3,x4\firstcol{1}, \secondcol{x}, \thirdcol{x^2}, x^3, x^4) to 5 noisy data points, the columns span all of 5D space, so y\target{y} sits inside the column space with zero error. Because columns like x2,x3,x4\thirdcol{x^2}, x^3, x^4 grow in nearly the same way for positive inputs like x=0.5,0.6,0.7,0.8x = 0.5, 0.6, 0.7, 0.8, their column vectors point in almost the same direction. Reaching sideways to hit the noisy target y\target{y} forces the model to use huge weights with opposite signs along those nearly parallel columns:

y\displaystyle y =2−150x+1200x2−1800x3+752x4⏟cancel at the data points,explode away from them\displaystyle = 2 \underbrace{- 150x + 1200x^2 - 1800x^3 + 752x^4}_{\substack{\text{cancel at the data points,} \\ \text{explode away from them}}}
11
22
22
44
66
xx
yy
2.52.5
−19\htmlClass{lc-orange}{-19}

If we add a 6th feature column for only 5 data points, the columns become linearly dependent, so ATAA^T A is no longer invertible and the normal equations have infinitely many solutions.

Try nudging the target vector y\target{y} across the narrow gap between two nearly parallel columns to see why the weights blow up and flip signs:

When two feature columns point in nearly the same direction, a tiny sideways shift in the data vector forces huge opposite steps along the columns and makes the fitted curve swing wildly past the end points.
5

Regularization and the Complete Recipe

We want to keep flexible features like x2,x3,x4\thirdcol{x^2}, x^3, x^4 to capture curves, without letting nearly parallel columns end up with huge opposing weights like +1000+1000 and −999-999.

Regularization (specifically Ridge or L2 regularization) keeps the weights small by adding extra penalty rows swi≈0s w_i \approx 0 to the bottom of the system, pulling each weight toward zero with strength ss.

Regularization and the Complete Recipe
1\htmlClass{lc-green}{1}
x\htmlClass{lc-pink}{x}
x2\htmlClass{lc-violet}{x^2}
x3x^3
x4x^4
x5x^5
⋯\cdots
x10x^{10}
−1000−1000
00
10001000
ww
+1000\htmlClass{lc-green}{+1000}
−999\htmlClass{lc-pink}{-999}

Appending the penalty rows extends each column into its own new dimension while appending zeros to y\target{y}:

w1[123s0]+w2[1490s]≈[12500]\displaystyle \firstcol{w_1} \firstcol{\begin{bmatrix} 1 \\ 2 \\ 3 \\ \hdashline s \\ 0 \end{bmatrix}} + \secondcol{w_2} \secondcol{\begin{bmatrix} 1 \\ 4 \\ 9 \\ \hdashline 0 \\ s \end{bmatrix}} \approx \target{\begin{bmatrix} 1 \\ 2 \\ 5 \\ \hdashline 0 \\ 0 \end{bmatrix}}

When we take dot products, the penalty rows contribute s(0)+0(s)=0\firstcol{s}(\secondcol{0}) + \firstcol{0}(\secondcol{s}) = 0 between different columns and 00 with y\target{y}, and add λ=s2\lambda = s^2 only when a column is dotted with itself on the main diagonal:

(ATA+λ[1001]⏟I)w=ATy,λ=s2\displaystyle (A^T A + \lambda \underbrace{\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}}_{I}) w = A^T \target{y}, \qquad \lambda = s^2

Here are the steps for the extreme case where two data columns are completely identical: w1[11]+w2[11]≈[22]\firstcol{w_1} \firstcol{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} + \secondcol{w_2} \secondcol{\begin{bmatrix} 1 \\ 1 \end{bmatrix}} \approx \target{\begin{bmatrix} 2 \\ 2 \end{bmatrix}}.

Text solution
1. Check the unregularized system (λ=0\lambda = 0)Dotting each identical column with itself gives 22 and dotting with y\target{y} gives 44, producing a non-invertible grid where both equations say the exact same thing.
[2222][w1w2]=[44]  ⟹  w1+w2=2(infinitely many solutions,including 1000 and −998)\displaystyle \begin{gathered}\begin{aligned}\begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} &= \begin{bmatrix} 4 \\ 4 \end{bmatrix} \\ \implies \firstcol{w_1} + \secondcol{w_2} &= 2\end{aligned} \\ \text{(infinitely many solutions,} \\ \text{including } 1000 \text{ and } {-998}\text{)}\end{gathered}
2. Add λ=1\lambda = 1 down the main diagonal of ATAA^T ARegularizing with λ=1\lambda = 1 adds 11 to each diagonal entry while leaving the off-diagonal 22s and the right-hand side 44s unchanged.
[2+1222+1][w1w2]=[44]  ⟹  {3w1+2w2=42w1+3w2=4\displaystyle \begin{bmatrix} 2 + 1 & 2 \\ 2 & 2 + 1 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \end{bmatrix} \implies \begin{cases} 3\firstcol{w_1} + 2\secondcol{w_2} = 4 \\ 2\firstcol{w_1} + 3\secondcol{w_2} = 4 \end{cases}
3. Add and subtract the two rows to solveAdding the equations gives the sum of the weights, and subtracting them forces the two weights to be equal.
Add:5(w1+w2)=8  ⟹  w1+w2=1.6Subtract:w1−w2=0  ⟹  w1=w2=0.8\displaystyle \begin{aligned} \text{Add:} \quad && 5(\firstcol{w_1} + \secondcol{w_2}) &= 8 \\ && \implies \firstcol{w_1} + \secondcol{w_2} &= 1.6 \\ \text{Subtract:} \quad && \firstcol{w_1} - \secondcol{w_2} &= 0 \\ && \implies \firstcol{w_1} = \secondcol{w_2} &= 0.8 \end{aligned}

Instead of canceling each other out at +1000+1000 and −998-998, the two identical features share the weight equally at w1=0.8\firstcol{w_1} = 0.8 and w2=0.8\secondcol{w_2} = 0.8.

Try increasing the penalty ss to tilt the two columns apart into their own dimensions and calm down the fitted curve:

Tilting each column into its own perpendicular dimension spreads nearly parallel columns apart, shrinking huge opposing weights into a smooth fit.

Key concepts

Every data-fitting problem follows one geometric recipe: choose your features to build the columns of AA, take column dot products to project y\target{y} at 90∘90^\circ, and add λ\lambda to the diagonal if flexible features make the columns nearly parallel.

Choosing feature columns

Create one column of numbers per weight wiw_i by plugging your data inputs into each term of your model. Use [111]\firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} for a constant intercept w0\firstcol{w_0}, powers like x2\thirdcol{x^2} when the data bends (turning x=[−102]\secondcol{x} = \secondcol{\begin{bmatrix} -1 \\ 0 \\ 2 \end{bmatrix}} into x2=[104]\thirdcol{x^2} = \thirdcol{\begin{bmatrix} 1 \\ 0 \\ 4 \end{bmatrix}}), functions like 2x\secondcol{2^x} or sin⁡(x)\secondcol{\sin(x)} for exponential growth or waves, or separate columns for multiple inputs x1,x2\firstcol{x_1}, \secondcol{x_2}. If a straight line or simple parabola already captures the trend with well-separated columns, stop there; don't add higher powers like x4x^4 just to force the error at the noisy points to zero.

Least squares (ATAw=ATyA^T A w = A^T \target{y})

Build the square grid ATAA^T A by dotting every feature column with every feature column, and build the right-hand side ATyA^T \target{y} by dotting every feature column with the target vector y\target{y}.

Regularization ((ATA+λI)w=ATy(A^T A + \lambda I)w = A^T \target{y})

When you have many flexible features or nearly parallel columns (which show up as huge weights of opposite signs like +1200x2−1800x3+1200\thirdcol{x^2} - 1800x^3, or a non-invertible ATAA^T A when you have more features than points), add penalty rows swi≈0s w_i \approx 0. In the normal equations, this simply adds λ=s2\lambda = s^2 to the main diagonal of ATAA^T A:

[Col 1⋅Col 1+λCol 1⋅Col 2Col 2⋅Col 1Col 2⋅Col 2+λ][w1w2]=[Col 1⋅yCol 2⋅y]\displaystyle \begin{aligned} & \begin{bmatrix} \begin{gathered}\firstcol{\text{Col 1}}\cdot\firstcol{\text{Col 1}} \\ + \lambda\end{gathered} & \firstcol{\text{Col 1}}\cdot\secondcol{\text{Col 2}} \\[6pt] \secondcol{\text{Col 2}}\cdot\firstcol{\text{Col 1}} & \begin{gathered}\secondcol{\text{Col 2}}\cdot\secondcol{\text{Col 2}} \\ + \lambda\end{gathered} \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} \\ &\quad = \begin{bmatrix} \firstcol{\text{Col 1}}\cdot \target{y} \\ \secondcol{\text{Col 2}}\cdot \target{y} \end{bmatrix} \end{aligned}

6

Practice

1

Fit a straight line y=w0+w1x\target{y} = \firstcol{w_0} + \secondcol{w_1 x} to the three points (0,2)\data{(0, 2)}, (1,3)\data{(1, 3)}, and (2,10)\data{(2, 10)} by setting up the feature columns and solving ATAw=ATyA^T A w = A^T \target{y}, then use your line to predict y\target{y} at x=2.5x = 2.5.

What column vector multiplies the constant weight w0\firstcol{w_0} across all three data points before you take the dot products?

Stacking the three points into columns gives Column 1 =[111]= \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}}, Column 2 =[012]= \secondcol{\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}}, and target y=[2310]\target{y} = \target{\begin{bmatrix} 2 \\ 3 \\ 10 \end{bmatrix}}.
Taking the dot products (be careful to set Col 1⋅Col 1=1+1+1=3\firstcol{\text{Col 1}} \cdot \firstcol{\text{Col 1}} = 1 + 1 + 1 = 3 rather than 11, which is a common mistake that leads to w1=5.5,w0=−1.5\secondcol{w_1} = 5.5, \firstcol{w_0} = -1.5 and a wrong prediction of 12.2512.25):
[3335][w0w1]=[1523]\displaystyle \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix} \begin{bmatrix} \firstcol{w_0} \\ \secondcol{w_1} \end{bmatrix} = \begin{bmatrix} 15 \\ 23 \end{bmatrix}
Subtracting the first equation from the second gives 2w1=82\secondcol{w_1} = 8, so w1=4\secondcol{w_1} = 4 and w0=1\firstcol{w_0} = 1. The best-fit line is y=1+4xy = 1 + 4x, which predicts y=1+4(2.5)=11y = 1 + 4(2.5) = 11.
2

Fit a parabola y=w0+w1x+w2x2\target{y} = \firstcol{w_0} + \secondcol{w_1 x} + \thirdcol{w_2 x^2} to the five data points (−2,12)\data{(-2, 12)}, (−1,0)\data{(-1, 0)}, (0,7)\data{(0, 7)}, (1,−2)\data{(1, -2)}, and (2,8)\data{(2, 8)} by constructing the three feature columns and solving the 3×33 \times 3 normal equations.

Square each entry of the x\secondcol{x} column to form Column 3, and notice which column dot products cancel to 00 by symmetry.

The three feature columns are:
Column 1=[11111],Column 2=[−2−1012],Column 3=[41014],y=[1207−28]\displaystyle \firstcol{\text{Column 1}} = \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}}, \quad \secondcol{\text{Column 2}} = \secondcol{\begin{bmatrix} -2 \\ -1 \\ 0 \\ 1 \\ 2 \end{bmatrix}}, \quad \thirdcol{\text{Column 3}} = \thirdcol{\begin{bmatrix} 4 \\ 1 \\ 0 \\ 1 \\ 4 \end{bmatrix}}, \quad \target{y} = \target{\begin{bmatrix} 12 \\ 0 \\ 7 \\ -2 \\ 8 \end{bmatrix}}
Taking the dot products to build ATAw=ATyA^T A w = A^T \target{y} (watch out when computing Col 3⋅Col 3\thirdcol{\text{Col 3}} \cdot \thirdcol{\text{Col 3}}: you must dot Column 3 with itself to get 42+12+02+12+42=344^2 + 1^2 + 0^2 + 1^2 + 4^2 = 34, not just sum the entries of Column 3 to get 1010, which would give w2=−2.8\thirdcol{w_2} = -2.8 and w0=10.6\firstcol{w_0} = 10.6):
[5010010010034][w0w1w2]=[25−1078]\displaystyle \begin{bmatrix} 5 & 0 & 10 \\ 0 & 10 & 0 \\ 10 & 0 & 34 \end{bmatrix} \begin{bmatrix} \firstcol{w_0} \\ \secondcol{w_1} \\ \thirdcol{w_2} \end{bmatrix} = \begin{bmatrix} 25 \\ -10 \\ 78 \end{bmatrix}
The middle row gives 10w1=−1010\secondcol{w_1} = -10, so w1=−1\secondcol{w_1} = -1. Doubling the first row gives 10w0+20w2=5010\firstcol{w_0} + 20\thirdcol{w_2} = 50, and subtracting that from 10w0+34w2=7810\firstcol{w_0} + 34\thirdcol{w_2} = 78 gives 14w2=2814\thirdcol{w_2} = 28, so w2=2\thirdcol{w_2} = 2 and w0=1\firstcol{w_0} = 1. The best-fit parabola is y=1−x+2x2y = 1 - x + 2x^2.
3

Fit an exponential model y=w0+w12x\target{y} = \firstcol{w_0} + \secondcol{w_1 2^x} to the three points (0,5)\data{(0, 5)}, (1,2)\data{(1, 2)}, and (2,10)\data{(2, 10)} by building the feature columns for 1\firstcol{1} and 2x\secondcol{2^x} and solving ATAw=ATyA^T A w = A^T \target{y}.

Evaluate 2x\secondcol{2^x} at x=0,1,2x = 0, 1, 2 first so Column 2 is just a vector of three plain numbers.

At x=0,1,2x = 0, 1, 2, the feature columns are Column 1 =[111]= \firstcol{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}} and Column 2 =[124]= \secondcol{\begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix}} with target y=[5210]\target{y} = \target{\begin{bmatrix} 5 \\ 2 \\ 10 \end{bmatrix}} (be sure to evaluate 20=12^0 = 1 in the first row of Column 2; writing 20=02^0 = 0 makes Column 2 [024]\begin{bmatrix} 0 \\ 2 \\ 4 \end{bmatrix} and leads to w0=196,w1=54\firstcol{w_0} = \frac{19}{6}, \secondcol{w_1} = \frac{5}{4}).
Taking the dot products gives:
[37721][w0w1]=[1749]\displaystyle \begin{bmatrix} 3 & 7 \\ 7 & 21 \end{bmatrix} \begin{bmatrix} \firstcol{w_0} \\ \secondcol{w_1} \end{bmatrix} = \begin{bmatrix} 17 \\ 49 \end{bmatrix}
Tripling the first row gives 9w0+21w1=519\firstcol{w_0} + 21\secondcol{w_1} = 51; subtracting the second row gives 2w0=22\firstcol{w_0} = 2, so w0=1\firstcol{w_0} = 1 and w1=2\secondcol{w_1} = 2, giving y=1+2(2x)y = 1 + 2(2^x).
4

Four houses have size x1\firstcol{x_1} (in thousands of square feet), bedroom count x2\secondcol{x_2}, and price y\target{y} (in $100k\$100\text{k} units): (1,0,5)(\firstcol{1}, \secondcol{0}, \target{5}), (0,1,2)(\firstcol{0}, \secondcol{1}, \target{2}), (1,1,4)(\firstcol{1}, \secondcol{1}, \target{4}), and (2,1,9)(\firstcol{2}, \secondcol{1}, \target{9}). Fit the model y=w1x1+w2x2\target{y} = \firstcol{w_1 x_1} + \secondcol{w_2 x_2} and state what each weight means.

Build Column 1 directly from the four values of x1\firstcol{x_1} and Column 2 from the four values of x2\secondcol{x_2}.

Using Column 1 =[1012]= \firstcol{\begin{bmatrix} 1 \\ 0 \\ 1 \\ 2 \end{bmatrix}}, Column 2 =[0111]= \secondcol{\begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix}}, and y=[5249]\target{y} = \target{\begin{bmatrix} 5 \\ 2 \\ 4 \\ 9 \end{bmatrix}}, the normal equations are (watch the 0\secondcol{0} in the first entry of Column 2 when computing Col 2⋅y\secondcol{\text{Col 2}} \cdot \target{y} =0(5)+1(2)+1(4)+1(9){}= \secondcol{0}(\target{5}) + \secondcol{1}(\target{2}) + \secondcol{1}(\target{4}) + \secondcol{1}(\target{9}) =15{}= 15; including the 5\target{5} gives 2020 and leads to w1=73,w2=133\firstcol{w_1} = \frac{7}{3}, \secondcol{w_2} = \frac{13}{3}):
[6333][w1w2]=[2715]\displaystyle \begin{bmatrix} 6 & 3 \\ 3 & 3 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} = \begin{bmatrix} 27 \\ 15 \end{bmatrix}
Subtracting the second row from the first gives 3w1=123\firstcol{w_1} = 12, so w1=4\firstcol{w_1} = 4 and w2=1\secondcol{w_2} = 1. The model is y=4x1+x2y = 4x_1 + x_2: each thousand square feet adds $400k\$400\text{k} and each bedroom adds $100k\$100\text{k}.
5

Suppose you have 4 noisy data points. Explain what happens in the 4D column space and to the fitting error when you fit a polynomial with 4 independent columns (1,x,x2,x3\firstcol{1}, \secondcol{x}, \thirdcol{x^2}, x^3), why nearly parallel columns among them cause wild swings away from the points, and what happens to ATAA^T A if you add a 5th column x4x^4.

How many independent vectors does it take to span all of 4D space, and what kind of steps must you take along two nearly parallel vectors to reach a target slightly off to the side?

Four independent columns span all of 4D space, so the target vector y\target{y} sits inside the column space and the error at the 4 data points drops to zero (don't confuse zero error at the 4 noisy data points with a good fit overall; hitting the noise exactly is what causes overfitting). When feature columns point in nearly the same direction, reaching sideways to hit the noisy target y\target{y} requires huge weights of opposite signs that cancel at the data points but grow huge away from them. Adding a 5th column in 4D space makes the columns linearly dependent, so ATAA^T A is no longer invertible and the normal equations have infinitely many solutions.
6

Consider the system w1[12]+w2[12]≈[714]\firstcol{w_1} \firstcol{\begin{bmatrix} 1 \\ 2 \end{bmatrix}} + \secondcol{w_2} \secondcol{\begin{bmatrix} 1 \\ 2 \end{bmatrix}} \approx \target{\begin{bmatrix} 7 \\ 14 \end{bmatrix}} with two identical feature columns. Write the extended column system with regularization penalty rows for s=2s = 2, find λ\lambda, and compare the solutions of the unregularized system (λ=0\lambda = 0) and the regularized system (ATA+λI)w=ATy(A^T A + \lambda I)w = A^T \target{y}.

Append one penalty row for each weight, and check what dotting an extended column with itself adds to the main diagonal.

Appending the penalty rows for s=2s = 2 gives:
w1[1220]+w2[1202]≈[71400],λ=s2=4\displaystyle \firstcol{w_1} \firstcol{\begin{bmatrix} 1 \\ 2 \\ 2 \\ 0 \end{bmatrix}} + \secondcol{w_2} \secondcol{\begin{bmatrix} 1 \\ 2 \\ 0 \\ 2 \end{bmatrix}} \approx \target{\begin{bmatrix} 7 \\ 14 \\ 0 \\ 0 \end{bmatrix}}, \qquad \lambda = s^2 = 4
When λ=0\lambda = 0, the normal equations are:
[5555][w1w2]=[3535]\displaystyle \begin{bmatrix} 5 & 5 \\ 5 & 5 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} = \begin{bmatrix} 35 \\ 35 \end{bmatrix}
Here ATAA^T A is not invertible, and any (w1,w2)(\firstcol{w_1}, \secondcol{w_2}) with w1+w2=7\firstcol{w_1} + \secondcol{w_2} = 7 is a solution.
When λ=4\lambda = 4, we add λ=4\lambda = 4 to the main diagonal only (be careful not to add s=2s = 2 instead of λ=s2=4\lambda = s^2 = 4, which gives [7557]\begin{bmatrix} 7 & 5 \\ 5 & 7 \end{bmatrix} and w1=w2=3512\firstcol{w_1} = \secondcol{w_2} = \frac{35}{12}, and don't add 44 to the off-diagonal entries):
[9559][w1w2]=[3535]\displaystyle \begin{bmatrix} 9 & 5 \\ 5 & 9 \end{bmatrix} \begin{bmatrix} \firstcol{w_1} \\ \secondcol{w_2} \end{bmatrix} = \begin{bmatrix} 35 \\ 35 \end{bmatrix}
Adding and subtracting the equations gives 14(w1+w2)=7014(\firstcol{w_1} + \secondcol{w_2}) = 70 and w1=w2\firstcol{w_1} = \secondcol{w_2}, which has the single solution w1=2.5\firstcol{w_1} = 2.5 and w2=2.5\secondcol{w_2} = 2.5.