Introduction to Machine Learning Homework #1

Author： Bi_Gu
发布时间：March 8, 2023
74 views
No comments
11868 words
Categories：课堂笔记机器学习引论

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/105852657_p0.png","_blank")'><i class="fa fa-camera"></i>$\quad$ **雲圖計畫 by 抠肉肚脐@Kuroduki** </button>

# Introduction to Machine Learning

## Homework 1

### Problem 1.

Given the input variables $X\in\mathbb{R}^p$ and output variable $Y\in\mathbb{R}$, the Expected Prediction Error (EPE) is defined by

$$
\text{EPE}(\hat{f})=\mathbb{E}\left[L(Y,f(X))\right],
$$

where $\mathbb{E}(\cdot)$ denotes the expectation over the joint distribution $\text{Pr}(X,Y)$, and $L(Y,f(X))$ is a loss function measuring the difference between the estimated $f(X)$ and observed $Y$. We have shown in our course that for the squared error loss $L(Y,f(X))=(Y-f(X))^2$, the regression function $f(x)=\mathbb{E}(Y|X=x)$ is the optimal solution of $\min_f\text{EPE}(f)$ in the pointwise manner.

(a) In Least Squares, a linear model $X^T\beta$ is used to approximate $f(X)$ according to

$$
\mathop{\min}\limits_{\beta}\mathbb{E}\left[(Y-X^T\beta)^2\right].
$$

Please derive the optimal solution of the model parameters $\beta$.

**Solution.**

First we calculate the first derivative as follows

$$
\begin{aligned}\bigg(\mathbb{E}[(Y-X^T\beta)^2]\bigg)'&=\bigg(\mathbb{E}[(Y-X^T\beta)^T(Y-X^T\beta)]\bigg)'\\
		&=\mathbb{E}[-X^T(Y-X^T\beta)-X^T(Y-X^T\beta)']\\&=\mathbb{E}[-2X^T(Y-X^T\beta)]\end{aligned}
$$

Therefore for optimal $\beta=\hat{\beta}$, we have that

$$
\mathbb{E}[-X^T(Y-X^T\hat{\beta})]=0\Leftrightarrow \mathbb{E}[YX^T]=\mathbb{E}[XX^T\hat{\beta}]\Leftrightarrow\hat{\beta}=\mathbb{E}[YX^T(XX^T)^{-1}].
$$

(b) Please explain how the nearest neighbors and least squares approximate the regression function, and discuss their difference.

**Solution.**

**Nearest neighbors** regression predicts the output for a new input by finding the nearest training inputs and averaging their outputs;  **Least squares** regression predicts the output for a new input by finding the linear combination of the training inputs that best fits the training outputs, getting the best linear parameters by using some optimization algorithm.

The difference is that nearest neighbors is non-parametric, that it does not make any assumptions about the regression function, while least squares assumes that the function is a linear one. Therefore nearest neighbors is more flexible that it can capture more non-linear patterns in the data, but takes a longer time to train, while least squares is more efficient but less flexible.

(c) Given absolute error loss $L(Y,f(X))=\left|Y-f(X)\right|$, please prove that $f(x)=\text{median}(Y\mid X=x)$ minimizes $\text{EPE}(f)\text{ w.r.t. }f$.

**Solution.**

First we see the fact that

$$
c=\text{median}(Y)\Rightarrow\frac{\partial}{\partial c}\sum_{i=1}^N\left|Y-c\right|=\sum_{i=1}^N\text{sgn}(Y-c)=0
$$

Thus $\displaystyle\sum_{i=1}^N\left|Y-c\right|$ is minimized by $c=\text{median}(Y)$;

Therefore, $f(x)=\text{median}(Y\mid X=x)$ minimizes $\text{EPE}(f)$ for $L(Y,f(X))=\left|Y-f(X)\right|$, $\text{ w.r.t. }f$.

**The proof is complete.**

### Problem 2.

(a) Ridge regression can be considered as an unconstrained optimization problem

$$
\mathop{\min}\limits_{\mathbf{w}}||\mathbf{y-Xw}||_2^2+\lambda||\mathbf{w}||_2^2.
$$

where $\mathbf{X}\in\mathbb{R}^{n\times d}$ is a data matrix, and $\mathbf{y}\in\mathbb{R}^n$ is the target vector. Consider the following augmented target vector $\hat{\mathbf{y}}$ and data matrix $\hat{\mathbf{X}}$

$$
\hat{\mathbf{y}}=\begin{bmatrix}\mathbf{y}\\\mathbf{0}_d\end{bmatrix}\ \hat{\mathbf{X}}=\begin{bmatrix}\mathbf{X}\\\sqrt{\lambda}\mathbf{I}_d\end{bmatrix}
$$

where $\mathbf{0}_d$ is the zero vector in $\mathbb{R}_d$ and $\mathbf{I}_d\in\mathbb{R}^{d\times d}$ is an identity matrix. Please derive the optimal solution of the optimization problem $\min_{\omega}||\hat{\mathbf{y}}-\hat{\mathbf{X}}\mathbf{w}||_2^2$ only use $\mathbf{X},\mathbf{y}$.

**Solution.**

First we apply the Least Squares regression as follows

$$
\hat{\beta}^{\text{ls}}=\mathop{\text{argmin}}\limits_{\mathbf{w}}||\hat{\mathbf{y}}-\hat{\mathbf{X}}\mathbf{w}||_2^2
	=(\hat{\mathbf{X}}^T\hat{\mathbf{X}})^{-1}\hat{\mathbf{X}}^T\hat{\mathbf{y}}=(\mathbf{X}^T\mathbf{X}+\lambda\mathbf{I}_d)^{-1}\mathbf{X}^T\mathbf{y}
$$

Therefore we have that

$$
\begin{aligned}\mathop{\min}\limits_{\mathbf{w}}||\hat{\mathbf{y}}-\hat{\mathbf{X}}\mathbf{w}||_2^2
    &=\left|\left|\begin{bmatrix}\mathbf{y}\\\mathbf{0}_d\end{bmatrix}-\begin{bmatrix}\mathbf{X}\\\sqrt{\lambda}\mathbf{I}_d\end{bmatrix}\cdot\hat{\beta}^{\text{ls}}\right|\right|_2^2
	\\&=||\mathbf{y}-\mathbf{X}\hat{\beta}^{\text{ls}}||_2^2+\lambda||\hat{\beta}^{\text{ls}}||_2^2.\end{aligned}
$$

(b) Let's consider another situation by constructing an augmented matrix in the following way

$$
\hat{\mathbf{X}}=\begin{bmatrix}\mathbf{X}&\alpha\mathbf{I}_n\end{bmatrix}
$$

where $\alpha$ is a scalar multiplier. Then consider the following problem

$$
\mathop{\min}\limits_{\beta}||\beta||_2^2\quad\text{s.t.}\quad\hat{\mathbf{X}}\beta=\mathbf{y}
$$

If $\beta^*$ is the optimal solution of (4), show that the first $d$ coordinates of $\beta^*$ form the optimal solution of (3) for a specific $\alpha$, and find the $\alpha$. And what the final $n$ coordinates of $\beta^*$ represent?

**Solution.**

Denote $\beta$ as $\begin{bmatrix}\beta_d\\\beta_n\end{bmatrix}$. In order to express $\beta_n$ in terms of $\beta_d$, consider

$$
\hat{\mathbf{X}}\beta=\hat{\mathbf{y}}\Leftrightarrow\begin{bmatrix}\hat{\mathbf{X}}&\alpha\mathbf{I}_n\end{bmatrix}\begin{bmatrix}\beta_d\\\beta_n\end{bmatrix}
	=\mathbf{y}\Rightarrow\beta_n=\frac{\mathbf{y}-\mathbf{X}\beta_d}{\alpha}
$$

Then for the problem in (4), first we calculate that

$$
\begin{aligned}||\beta||_2^2&=||\beta_d||_2^2+\frac{1}{\alpha^2}||\mathbf{y}-\mathbf{X}\beta_d||_2^2
		\\&=\beta_d^T\left(\mathbf{I}_d+\frac{\mathbf{X}^T\mathbf{X}}{\alpha^2}\right)\beta_d-\beta_d^T\cdot\frac{2\mathbf{X}^T\mathbf{y}}{\alpha^2}+\frac{\mathbf{y}^T\mathbf{y}}{\alpha^2} \end{aligned}
$$

Apply the first derivative, we have that

$$
\frac{\mathbf{d}||\beta||_2^2}{\mathbf{d}\beta_d}=2\left(\mathbf{I}_d+\frac{\mathbf{X}^T\mathbf{X}}{\alpha^2}\right)\beta_d-\frac{2\mathbf{X}^T\mathbf{y}}{\alpha^2}
$$

Therefore for the optimal solution $\beta^*$, we have that

$$
2\left(\mathbf{I}_d+\frac{\mathbf{X}^T\mathbf{X}}{\alpha^2}\right)\beta_d-\frac{2\mathbf{X}^T\mathbf{y}}{\alpha^2}=0\Leftrightarrow \beta_d=(\alpha^2\mathbf{I}_d+\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}
$$

To find the value of $\alpha$, we have

$$
\beta_d=\hat{\beta}^{\text{ridge}}=(\mathbf{X}^T\mathbf{X}+\lambda\mathbf{I}_d)^{-1}\mathbf{X}^T\mathbf{y}\Leftrightarrow \alpha=\pm\sqrt{\lambda}.
$$

The final $n$ coordinates of $\beta^*$ represents the $\beta_n$.

(c) As we all know, the standard formula for Ridge Regression is the optimal solution of (3). Suppose the SVD of $\mathbf{X}$ is $\mathbf{X}=\mathbf{U\Sigma V}^T$, then we can make some changes on coordinates in the feature space, so that $\mathbf{V}$ becomes identity, where $\mathbf{X}'=\mathbf{XV}$ and $\mathbf{w}=\mathbf{V}^T\mathbf{w}$, and denote $\hat{\mathbf{w}}'$ as the solution of the ridge regression in new coordinates. Please write down the $i$-th coordinate of $\hat{\mathbf{w}}'$.

**Solution.**

We calculate the whole $\hat{\mathbf{w}}'$ first as follows

$$
\begin{aligned}\hat{\mathbf{w}}'&=\mathbf{V}^T\mathbf{w}\\&=\mathbf{V}^T(\mathbf{X}^T\mathbf{X}+\lambda\mathbf{I}_d)^{-1}\mathbf{X}^T\mathbf{y}
		\\&=\mathbf{V}^T(\mathbf{V\Sigma}^T\cdot\mathbf{\Sigma V}^T+\lambda\mathbf{I}_d)^{-1}\cdot\mathbf{\Sigma}^T\mathbf{U}^T\mathbf{y}
		\\&=\text{diag}\left[\frac{\sigma_i}{\sigma_i^2+\lambda}\right]\mathbf{U}^T\mathbf{y}
	\end{aligned}
$$

Therefore the $i$-th coordinate of $\hat{\mathbf{w}}'$ is represented as

$$
\hat{\mathbf{w}}'_i=\frac{\sigma_i}{\sigma_i^2+\lambda}\left\langle\mathbf{U}_i,\mathbf{y}\right\rangle
$$

where $\mathbf{U}_i$ is the $i$-th column of $\mathbf{U}$.

### Problem 3.

A random variable $\mathbf{X}$ has unknown mean and variance: $\mu,\sigma^2$. $n$ iid realizations $\mathbf{X}_1=\mathbf{x}_1,\mathbf{X}_2=\mathbf{x}_2,\cdots,\mathbf{X}_n=\mathbf{x}_n$ from the random variable $\mathbf{X}$ are used to estimate the mean of $\mathbf{X}$. We will call our estimate of $\mu$ the random variable $\hat{\mathbf{X}}$, which has mean $\hat{\mu}$. There are two possible ways to estimate $\mu$ with the realizations of $n$ samples:

1. Average the $n$ samples: $\displaystyle\frac{\mathbf{x}_1+\mathbf{x}_2+\cdots+\mathbf{x}_n}{n}$
2. Average the $n$ samples and $n_0$ samples of 0: $\displaystyle\frac{\mathbf{x}_1+\mathbf{x}_2+\cdots+\mathbf{x}_n}{n+n_0}$

The bias is defined as $\mathbb{E}[\hat{\mathbf{X}}-\mu]$ and the variance of $\text{Var}[\hat{\mathbf{X}}]$

(a) What are the bias and the variance of each of two estimators above?

**Solution.**

For the first estimator, we have that

$$
\begin{aligned}\mathbb{E}[\hat{\mathbf{X}_1}-\mu]&=\mathbb{E}\left[\frac{\sum_{i=1}^n\mathbf{x}_i}{n}\right]-\mu
		=\sum_{i=1}^n\frac{\mathbb{E}[\mathbf{x}_i]-\mu}{n}=0;\\
	\text{Var}[\hat{\mathbf{X}_1}]&=\mathbb{E}\left[\left(\frac{\sum_{i=1}^n\mathbf{x}_i}{n}-\hat{\mu}\right)^2\right]
	=\mathbb{E}\left[\left(\frac{\sum_{i=1}^n(\mathbf{x}_i)-\mu}{n}\right)^2\right]
	\\&=\mathbb{E}\left[\frac{\sum_{i=1}^n(\mathbf{x}_i-\mu)^2}{n^2}\right]\\&=\mathbb{E}\left[\frac{\mathbb{E}[(\mathbf{x}_i-\mu)^2]}{n}\right]
	=\mathbb{E}\left[\frac{\sigma^2}{n}\right]=\frac{\sigma^2}{n}.
	\end{aligned}
$$

For the second estimator, we have that

$$
\begin{aligned}\mathbb{E}[\hat{\mathbf{X}_2}-\mu]&=\mathbb{E}\left[\frac{\sum_{i=1}^n\mathbf{x}_i}{n+n_0}\right]-\mu=\frac{\sum_{i=1}^n(\mathbb{E}[\mathbf{x}_i]-\mu)}{n+n_0}+\frac{n\mu}{n+n_0}-\mu\\&=-\frac{n_0\mu}{n+n_0};
	\\\text{Var}[\hat{\mathbf{X}_2}]&=\mathbb{E}\left[\left(\frac{\sum_{i=1}^n\mathbf{x}_i}{n+n_0}-\hat{\mu}\right)^2\right]
	=\mathbb{E}\left[\left(\frac{\sum_{i=1}^n(\mathbf{x}_i-\mu)}{n+n_0}+\frac{n\mu}{n+n_0}-\hat{\mu}\right)^2\right]
	\\&=\mathbb{E}\left[\left(\frac{\sum_{i=1}^n(\mathbf{x}_i-\mu)}{n+n_0}\right)^2\right]=\frac{n^2\text{Var}[\hat{\mathbf{X}_1}]}{(n+n_0)^2}
	\\&=\frac{n\sigma^2}{(n+n_0)^2}.
	\end{aligned}
$$

(b) Now we denote a new independent sample of $\mathbf{X}$ as $\mathbf{X}'$, in order to test how well $\hat{\mathbf{X}}$ estimates a new sample of $\mathbf{X}$. Please derive an expression for $\mathbb{E}[(\hat{\mathbf{X}}-\mu)^2]$ and $\mathbb{E}[(\hat{\mathbf{X}}-\mathbf{X}')^2]$, and then make some comments on the difference between them. (Hints: Using the Bias-Variance Tradeoff)

**Solution.**

We have that

$$
\begin{aligned}
		\mathbb{E}\left[(\hat{\mathbf{X}}-\mu)^2\right]&=\mathbb{E}\left[(\hat{\mathbf{X}}-\hat{\mu}+\hat{\mu}-\mu)^2\right]
		=\mathbb{E}[(\hat{\mathbf{X}}-\hat{\mu})^2]+\mathbb{E}[(\hat{\mu}-\mu)^2]
		\\&=\hat{\sigma}^2+(\hat{\mu}-\mu)^2;
		\\\mathbb{E}\left[(\hat{\mathbf{X}}-\mathbf{X}')^2\right]&=\mathbb{E}\left[(\hat{\mathbf{X}}-\hat{\mu}+\hat{\mu}-\mu+\mu-\mathbf{X}')^2\right]
		\\&=\mathbb{E}[(\hat{\mathbf{X}}-\hat{\mu})^2]+\mathbb{E}[(\hat{\mu}-\mu)^2]+\mathbb{E}[(\mu-\mathbf{X}')^2]-2\mathbb{E}[(\hat{\mathbf{X}}-\hat{\mu})(\mu-\mathbf{X}')]
		\\&=\hat{\sigma}^2+\sigma^2+(\hat{\mu}-\mu)^2.
	\end{aligned}
$$

**Solution.**

We have that

$$
\begin{aligned}
		\mathbb{E}[(\hat{\mathbf{X}_1}-\mu)^2]&=\text{Var}[\hat{\mathbf{X}_1}]=\frac{\sigma^2}{n};
		\\\mathbb{E}[(\hat{\mathbf{X}_2}-\mu)^2]&=\text{Var}[\hat{\mathbf{X}_2}]+\text{Bias}[\hat{\mathbf{X}_2}]^2=\frac{\sigma^2}{n}+\left(\frac{n_0\mu}{n+n_0}\right)^2.
	\end{aligned}
$$

Last modification：March 16, 2023

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/625/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

随机文章记一次帮人做但摆了的ee作业好康的竖版图分享【长期更新】 Maths Analysis II - Homework #12 20220324

Introduction to Machine Learning Homework #1

Bi_Gu • 2023 年 03 月 08 日

# Introduction to Machine Learning

## Homework 1

### Problem 1.

Given the input variables $X\in\mathbb{R}^p$ and output variable $Y\in\mathbb{R}$, the Expected Prediction Error (EPE) is defined by

$$
\text{EPE}(\hat{f})=\mathbb{E}\left[L(Y,f(X))\right],
$$

(a) In Least Squares, a linear model $X^T\beta$ is used to approximate $f(X)$ according to

$$
\mathop{\min}\limits_{\beta}\mathbb{E}\left[(Y-X^T\beta)^2\right].
$$

Please derive the optimal solution of the model parameters $\beta$.

**Solution.**

First we calculate the first derivative as follows

Therefore for optimal $\beta=\hat{\beta}$, we have that

$$
\mathbb{E}[-X^T(Y-X^T\hat{\beta})]=0\Leftrightarrow \mathbb{E}[YX^T]=\mathbb{E}[XX^T\hat{\beta}]\Leftrightarrow\hat{\beta}=\mathbb{E}[YX^T(XX^T)^{-1}].
$$

(b) Please explain how the nearest neighbors and least squares approximate the regression function, and discuss their difference.

**Solution.**

(c) Given absolute error loss $L(Y,f(X))=\left|Y-f(X)\right|$, please prove that $f(x)=\text{median}(Y\mid X=x)$ minimizes $\text{EPE}(f)\text{ w.r.t. }f$.

**Solution.**

First we see the fact that

$$
c=\text{median}(Y)\Rightarrow\frac{\partial}{\partial c}\sum_{i=1}^N\left|Y-c\right|=\sum_{i=1}^N\text{sgn}(Y-c)=0
$$

Thus $\displaystyle\sum_{i=1}^N\left|Y-c\right|$ is minimized by $c=\text{median}(Y)$;

Therefore, $f(x)=\text{median}(Y\mid X=x)$ minimizes $\text{EPE}(f)$ for $L(Y,f(X))=\left|Y-f(X)\right|$, $\text{ w.r.t. }f$.

**The proof is complete.**

### Problem 2.

(a) Ridge regression can be considered as an unconstrained optimization problem

$$
\mathop{\min}\limits_{\mathbf{w}}||\mathbf{y-Xw}||_2^2+\lambda||\mathbf{w}||_2^2.
$$

$$
\hat{\mathbf{y}}=\begin{bmatrix}\mathbf{y}\\\mathbf{0}_d\end{bmatrix}\ \hat{\mathbf{X}}=\begin{bmatrix}\mathbf{X}\\\sqrt{\lambda}\mathbf{I}_d\end{bmatrix}
$$

**Solution.**

First we apply the Least Squares regression as follows

Therefore we have that

(b) Let's consider another situation by constructing an augmented matrix in the following way

$$
\hat{\mathbf{X}}=\begin{bmatrix}\mathbf{X}&\alpha\mathbf{I}_n\end{bmatrix}
$$

where $\alpha$ is a scalar multiplier. Then consider the following problem

$$
\mathop{\min}\limits_{\beta}||\beta||_2^2\quad\text{s.t.}\quad\hat{\mathbf{X}}\beta=\mathbf{y}
$$

**Solution.**

Denote $\beta$ as $\begin{bmatrix}\beta_d\\\beta_n\end{bmatrix}$. In order to express $\beta_n$ in terms of $\beta_d$, consider

Then for the problem in (4), first we calculate that

Apply the first derivative, we have that

$$
\frac{\mathbf{d}||\beta||_2^2}{\mathbf{d}\beta_d}=2\left(\mathbf{I}_d+\frac{\mathbf{X}^T\mathbf{X}}{\alpha^2}\right)\beta_d-\frac{2\mathbf{X}^T\mathbf{y}}{\alpha^2}
$$

Therefore for the optimal solution $\beta^*$, we have that

To find the value of $\alpha$, we have

$$
\beta_d=\hat{\beta}^{\text{ridge}}=(\mathbf{X}^T\mathbf{X}+\lambda\mathbf{I}_d)^{-1}\mathbf{X}^T\mathbf{y}\Leftrightarrow \alpha=\pm\sqrt{\lambda}.
$$

The final $n$ coordinates of $\beta^*$ represents the $\beta_n$.

**Solution.**

We calculate the whole $\hat{\mathbf{w}}'$ first as follows

Therefore the $i$-th coordinate of $\hat{\mathbf{w}}'$ is represented as

$$
\hat{\mathbf{w}}'_i=\frac{\sigma_i}{\sigma_i^2+\lambda}\left\langle\mathbf{U}_i,\mathbf{y}\right\rangle
$$

where $\mathbf{U}_i$ is the $i$-th column of $\mathbf{U}$.

### Problem 3.

The bias is defined as $\mathbb{E}[\hat{\mathbf{X}}-\mu]$ and the variance of $\text{Var}[\hat{\mathbf{X}}]$

(a) What are the bias and the variance of each of two estimators above?

**Solution.**

For the first estimator, we have that

For the second estimator, we have that

**Solution.**

We have that

**Solution.**

We have that

Introduction to Machine Learning Homework #1

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Discrete Mathematics Homework #13

Discrete Mathematics Homework #7

Linear Algebra Notes - Section 1.2

好康的竖版图分享【长期更新】

Signals and Systems Chapter 0

使用RD Client实现Windows远程桌面

Discrete Mathematics Homework #2

Introduction to Machine Learning Homework #1