MIT 6.036x - Week 5 Problems

Gradient Calculations

1A

Write an expression for $g(x^{(i)},y^{(i)})$ using the symbols: x_i, y_i, theta and theta_0, where $g(x^{(i)},y^{(i)})$ is the derivative of the $L_s$​ function described above with respect to $\theta$. Remember that you can use @ for matrix product, and you can use transpose(v) to traanspose a vector. Note that this $g(\cdot )$ function is just the derivative with respect to a single data point.

$L_s$ refers to squared loss, such that:

$$L_s(x^{(i)},y^{(i)},\theta ,{\theta }_0)=({\hat{y}}^{(i)}-y^{(i)}{)}^2=({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2$$

So we want to take the derivative of this with respect to $\theta$:

$$\begin{array}{rl}\frac{\partial }{\partial \theta }(L_s)& =\frac{\partial }{\partial \theta }(({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2)\\ & =2({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})\cdot \frac{\partial }{\partial \theta }({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})\\ & =\boxed{2({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})\cdot x^{(i)}}\end{array}$$

The terms in the second expression simplify to $x^{(i)}$ because ${\theta }^T{x}^{(i)}$ is treated as a linear function of $\theta$, while ${\theta }_0$ and $y^{(i)}$ are treated as constants, since they do not change depending on the value of $thet$.

1B

What is the gradient of the squared loss/empirical risk now with ${\theta }_0$?

$$\begin{array}{rl}\frac{\partial }{\partial {\theta }_0}(L_s)& =\frac{\partial }{\partial {\theta }_0}(({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2)\\ & =2({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})\cdot \cancel{\frac{\partial }{\partial {\theta }_0}({\theta }^T{x}^{(i)}C+{\theta }_0-y^{(i)})}\\ & =\boxed{2({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})}\end{array}$$

1C

Next we’re interested in the gradient of the empirical loss with respect to $\theta$, ${\nabla }_{\theta }{J}_{emp}$​, but now for a whole data set $X$ (of dimensions $d$ by $n$).

We can recognize that $L_s(x^{(i)},y^{(i)})$ is the square of the $i$-th element of ${\theta }^{T}X+{\theta }_0-Y$. So, a sum of $L_s(x^{(i)},y^{(i)})$ over the whole dataset is just is equivalent to the norm squared:

$$\sum _{i=1}^n{L}_s(x^{(i)},y^{(i)})=\left|\right|({\theta }^{T}X+{\theta }_0-Y{)}^T|{|}^2$$

The square of a norm is is equivalent to taking the dot product of itself:

$$\left|\right|({\theta }^{T}X+{\theta }_0-Y{)}^T|{|}^2=({\theta }^{T}X+{\theta }_0-Y)({\theta }^{T}X+{\theta }_0-Y{)}^T$$

Using the chain rule to take our derivative:

$$\frac{d}{d\theta }\frac{1}{n}\left|\right|({\theta }^{T}X+{\theta }_0-Y{)}^T|{|}^2=\frac{2}{n}X({\theta }^{T}X+{\theta }_0-Y{)}^T$$

where $\frac{d}{d\theta }({\theta }^{T}X)=X$.

Checking dimensions:

• $X$ is $d\times n$
• ${\theta }^{T}X$ is $1\times n$
• $y$ is $1\times n$
• Therefore, ${\theta }^{T}x+{\theta }_0-y$ is $1\times n$
• The matrix product of a $d\times n$ matrix with an $n\times 1$ matrix (the transpose of $1\times n$) thus gives us a gradient that is $d\times 1$, as expected (i.e., ${\nabla }_{\theta }{J}_{emp}$ is a vector where each element is the gradient of $J$ with respect to the corresponding element of $\theta$).

Sources of Error

2A. Penalizing $||\theta |{|}^2$ during training can reduce estimation error.

• Structural error is the error due to selecting an inadequate model class
• Estimation error arises when parameters of a hypothesis were not estimated well during training.
• Adding $||\theta |{|}^2$ is not selecting for a model class (aka selecting the order of polynomial basis) but for preventing overfitting – thus it reduces estimation error.

Minimizing empirical risk

3A

Let data matrix $Z=X^T$ be $n\times d$, let target output vector $T=Y^T$ be $n\times 1$ and recall that $\theta =d\times 1$. Then we can write the whole linear regression as $Z\theta$. Write an equation expressing the mean squared loss of $\theta$ in terms of $Z,T,n,\theta$.

$$\begin{array}{rl}{J}_{emp}& =\frac{1}{n}\sum _{i=1}^n{L}_s(x^{(i)},y^{(i)},\theta ,{\theta }_0)\\ & =\frac{1}{n}({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2\\ & =\frac{1}{n}||(Z\theta -T)|{|}^2\\ & =\boxed{\frac{1}{n}(Z\theta -T{)}^T(Z\theta -T)}\end{array}$$

3B

What is ${\nabla }_{\theta }J(\theta )$ in terms of $Z,T,\theta ,{\theta }_0$?

Let’s re-write the above expression so that we can find the gradient:

$$\begin{array}{rl}{J}_{emp}& =\frac{1}{n}(Z\theta -T{)}^T(Z\theta -T)\\ & =\frac{1}{n}(Z^T{\theta }^T-T^T)(Z\theta -T)\\ & =\frac{1}{n}({\theta }^T{Z}^{T}Z\theta -2T^{T}Z\theta +T^{T}T)\\ & =\frac{1}{n}(Z^{T}Z{\theta }^2-2T^{T}Z\theta +T^{T}T)\end{array}$$

Taking the derivative with respect to $\theta$:

$$\begin{array}{rl}\frac{\partial }{\partial \theta }\left[\frac{1}{n}(Z^{T}Z{\theta }^2-2T^{T}Z\theta +T^{T}T)\right]& =\frac{1}{n}(2Z^{T}Z\theta -2T^{T}Z+0)\\ & =-\frac{2}{n}(Z^{T}T\theta +Z^{T}T)\\ & =-\frac{2}{n}{Z}^T(Z\theta +T)\end{array}$$

…or something like that?

3B

What if we set the above equation to 0 and solve for ${\theta }^{\ast }$, the optimal $\theta$?

$$\begin{array}{rl}\frac{2}{n}\cdot Z^T(Z\theta -T)& =0\\ (Z^{T}Z)\theta -Z^{T}T& =0\\ (Z^{T}Z)\theta & =Z^{T}T\\ \theta & =\boxed{(Z^{T}Z{)}^{-1}{Z}^{T}T}\end{array}$$

3C+D

Converting ${\theta }^{\ast }$ back to the data matrix format we’ve been using:

$$\begin{array}{rl}{\theta }^{\ast }& =(Z^{T}Z{)}^{-1}{Z}^{T}T\\ & =\boxed{(X{X}^T{)}^{-1}X{Y}^T}\end{array}$$

In code form: np.linalg.inv(X@np.transpose(X))@X@np.transpose(Y)

Evaluation