UDL Chapter 2 Problems

Problem 2.1

To walk “downhill” on the least squares loss function

$$L[\varphi ]=\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i{)}^2$$

we measure its its gradient with respect to the parameters ${\varphi }_0$ and ${\varphi }_1$. Calculate expressions for the slopes $\partial L/\partial {\varphi }_0$ and $\partial L/\partial {\varphi }_1$.

For ${\varphi }_0$:

$$\begin{array}{rl}\frac{\partial }{\partial {\varphi }_0}({\varphi }_0+{\varphi }_1{x}_i-y_i{)}^2& =2({\varphi }_0+{\varphi }_1{x}_i-y_i)\cdot \frac{\partial }{\partial {\varphi }_0}({\varphi }_0+{\varphi }_1{x}_i-y_i)\\ & =2({\varphi }_0+{\varphi }_1{x}_i-y_i)\cdot 1\end{array}$$

Taking the summation into account, we have

$$\frac{\partial L}{\partial {\varphi }_0}=2\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i)$$

For ${\varphi }_1$:

$$\begin{array}{rl}\frac{\partial }{\partial {\varphi }_1}({\varphi }_0+{\varphi }_1{x}_i-y_i{)}^2& =2({\varphi }_0+{\varphi }_1{x}_i-y_i)\cdot \frac{\partial }{\partial {\varphi }_1}({\varphi }_0+{\varphi }_1{x}_i-y_i)\\ & =2({\varphi }_0+{\varphi }_1{x}_i-y_i)\cdot x_i\end{array}$$

Taking the summation into account, we have:

$$\frac{\partial L}{\partial {\varphi }_1}=2\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i)x_i$$

Problem 2.2

Show that we can find the minimum of the loss function in closed form by setting the expression for the derivatives from Problem 2.1 to zero and solving for ${\varphi }_0$ and ${\varphi }_1$. Note that this works for linear regression but not for more complex models; this is why we use iterative model fitting methods like gradient descent.

For ${\varphi }_0$:

$$\begin{array}{rl}\frac{\partial L}{\partial {\varphi }_0}=2\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i)& =0\\ \sum _{i=1}^I{\varphi }_0+\sum _{i=1}^I{\varphi }_1{x}_i-\sum _{i=1}^I{y}_i& =0\\ I{\varphi }_0+{\varphi }_1\sum _{i=1}^I{x}_i-\sum _{i=1}^I{y}_i& =0\\ {\varphi }_0& =\frac{1}{I}\sum _{i=1}^I{y}_i-{\varphi }_1\frac{1}{I}\sum _{i=1}^I{x}_i\\ {\varphi }_0& =\boxed{\bar{y}-{\varphi }_1\bar{x}}\end{array}$$

For ${\varphi }_1$:

$$\begin{array}{rl}\frac{\partial L}{\partial {\varphi }_1}=2\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i)x_i& =0\\ \sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i)x_i& =0\\ \sum _{i=1}^I{\varphi }_0{x}_i+\sum _{i=1}^I{\varphi }_1{x}_i^2-\sum _{i=1}^I{y}_i{x}_i& =0\\ {\varphi }_0\sum _{i=1}^I{x}_i+{\varphi }_1\sum _{i=1}^I{x}_i^2-\sum _{i=1}^I{y}_i{x}_i& =0\end{array}$$

Substitute ${\varphi }_0=\bar{y}-{\varphi }_1\bar{x}$ into the equation:

$$\begin{array}{rl}\left(\bar{y}-{\varphi }_1\bar{x}\right)\sum _{i=1}^I{x}_i+{\varphi }_1\sum _{i=1}^I{x}_i^2-\sum _{i=1}^I{y}_i{x}_i& =0\\ \bar{y}\sum _{i=1}^I{x}_i-{\varphi }_1\bar{x}\sum _{i=1}^I{x}_i+{\varphi }_1\sum _{i=1}^I{x}_i^2-\sum _{i=1}^I{y}_i{x}_i& =0\\ \bar{y}\sum _{i=1}^I{x}_i-\sum _{i=1}^I{y}_i{x}_i+{\varphi }_1\left(\sum _{i=1}^I{x}_i^2-\bar{x}\sum _{i=1}^I{x}_i\right)& =0\\ \sum _{i=1}^I(\bar{y}-y_i)x_i+{\varphi }_1\sum _{i=1}^I(x_i-\bar{x})x_i& =0.\end{array}$$

Then:

$$\begin{array}{rl}\sum _{i=1}^I(\bar{y}-y_i)x_i+{\varphi }_1\sum _{i=1}^I(x_i-\bar{x})x_i& =0\\ \sum _{i=1}^I\bar{y}{x}_i-\sum _{i=1}^I{y}_i{x}_i+{\varphi }_1\sum _{i=1}^I\left(x_i^2-\bar{x}{x}_i\right)& =0\\ \bar{y}\sum _{i=1}^I{x}_i-\sum _{i=1}^I{y}_i{x}_i+{\varphi }_1\left(\sum _{i=1}^I{x}_i^2-\bar{x}\sum _{i=1}^I{x}_i\right)& =0\\ {\varphi }_1\left(\sum _{i=1}^I{x}_i^2-\bar{x}\sum _{i=1}^I{x}_i\right)& =\sum _{i=1}^I{y}_i{x}_i-\bar{y}\sum _{i=1}^I{x}_i\\ {\varphi }_1& =\frac{{\sum }_{i=1}^I{y}_i{x}_i-\bar{y}{\sum }_{i=1}^I{x}_i}{{\sum }_{i=1}^I{x}_i^2-\bar{x}{\sum }_{i=1}^I{x}_i}\\ {\varphi }_1& =\frac{{\sum }_{i=1}^I(x_i-\bar{x})(y_i-\bar{y})}{{\sum }_{i=1}^I(x_i-\bar{x}{)}^2}.\end{array}$$

Problem 2.3

Consider reformulating linear regression as a generative model, so we have $x=g[y,\varphi ]={\varphi }_0+{\varphi }_{1}y$. What is the new loss function? Find an expression for the inverse function $y=g^{-1}[x,\varphi ]$ that we would use to perform inference. Will this model make the same predictions as the discriminative version for a given training dataset $\{x_i,y_i\}$? One way to establish this is to write code that fits a line to three data points using both methods and see if the result is the same.

The generative model is

$$x=g[y,\varphi ]={\varphi }_0+{\varphi }_{1}y$$

Here, $x$ is generated as a function of $y$ and parameters ${\varphi }_0,{\varphi }_1$.

The new least squares loss becomes:

$$L[\varphi ]=\sum _{i=1}^I(x_i-({\varphi }_0+{\varphi }_1{y}_i){)}^2$$

We want to find the inverse function $y=g^{-1}[x,\varphi ]$, starting from:

$$\begin{array}{rl}x& ={\varphi }_0+{\varphi }_{1}y\\ y& =\frac{x-{\varphi }_0}{{\varphi }_1}\end{array}$$

• The discriminative model directly minimizes the loss on $y$ given $x$.
• The generative model minimizes the loss on $x$ given $y$, and we invert it to predict $y$ from $x$.

Discriminative Model: y = 1.17 + 0.75x
Generative Model: x = -1.43 + 1.29y
Inverse Generative Model: y = 1.11 + 0.78x