PML Exercise 4 Solutions

Exercise 4.1 [MLE for the univariate Gaussian †]

Show that the MLE for a univariate Gaussian is given by

$$\hat{\mu} = \frac{1}{N} \sum_{n=1}^N y_n$$ $$\hat{\sigma}^2 = \frac{1}{N} \sum_{n=1}^N (y_n - \hat{\mu})^2$$

解答： 写出 log

$$\log p(D\mid \mu, \sigma^2)= -\frac{N}{2}(\log2\pi+\log \sigma^2) -\sum_{n=1}^N \frac{(x_n-\mu)^2}{2\sigma^2}$$

令 $\frac{\partial{\log p(D\mid \mu, \sigma^2)}}{\partial{\mu}}=0, \frac{\partial{\log p(D\mid \mu, \sigma^2)}}{\partial{\sigma^2}}=0$，解得上式。

Exercise 4.2 [MAP estimation for 1D Gaussians †]

Consider samples $x_1, \dots, x_n$ from a Gaussian random variable with known variance $\sigma^2$ and unknown mean $\mu$. We further assume a prior distribution (also Gaussian) over the mean, $\mu \sim \mathcal{N}(m, s^2)$, with fixed mean $m$ and fixed variance $s^2$. Thus the only unknown is $\mu$.

• a. Calculate the MAP estimate $\hat{\mu}_{MAP}$. You can state the result without proof. Alternatively, with a lot more work, you can compute derivatives of the log posterior, set to zero and solve.
• b. Show that as the number of samples $n$ increase, the MAP estimate converges to the maximum likelihood estimate.
• c. Suppose $n$ is small and fixed. What does the MAP estimator converge to if we increase the prior variance $s^2$?
• d. Suppose $n$ is small and fixed. What does the MAP estimator converge to if we decrease the prior variance $s^2$?

解答：

• a.

$$\begin{aligned} \hat{\mu}_{MAP} &=\arg \max_{\mu} p(\mu,\sigma^2\mid D)\\ &=\arg \max_{\mu} \frac{p(\mu\mid m, s^2)p(D\mid \mu)}{p(D)}\\ &=\arg \max_{\mu} \log p(\mu\mid m, s^2)+\log p(D\mid \mu)\\ &=\arg \max_{\mu} \log{\left\{\frac{1}{\sqrt{2\pi s^2}}\exp{-\frac{(\mu -m)^2}{2s^2}} \right\}}+\log \left\{(2\pi \sigma^2)^{-\frac{n}{2}}\prod_{i=1}^n \exp{-\frac{(x_i-\mu)^2}{2\sigma^2}}\right\}\\ &=\arg \max_{\mu} -\frac{1}{2}\log (2\pi s^2)-\frac{(\mu-m)^2}{2s^2}-\frac{n}{2}\log{2\pi \sigma^2}-\sum_{i=1}^n \frac{(x_i-\mu)^2}{2\sigma^2}\\ &=\arg \max_{\mu} - \frac{\sigma^2(\mu-m)^2+s^2\sum_{i=1}^n (x_i-\mu)^2}{2s^2 \sigma^2}\\ &=\frac{m\sigma^2+s^2\sum_{i=1}^n x_i}{\sigma^2+ns^2} \end{aligned}$$

• b. 随着采样数量的增加 $\hat{\mu}_{MAP}\rightarrow \frac{\sum_{i=1}^n x_i}{n}$，即MLE。
• c. 随着 $s^2$ 增加也是收敛于 MLE。
• d. 随着 $s^2$ 减小收敛于先验均值 $m$。

Exercise 4.3 [Gaussian posterior credible interval]

Let $X \sim \mathcal{N}(\mu, \sigma^2 = 4)$ where $\mu$ is unknown but has prior $\mu \sim \mathcal{N}(\mu_0, \sigma^2_0 = 9)$. The posterior after seeing $n$ samples is $\mu \sim \mathcal{N}(\mu_n, \sigma^2_n)$. (This is called a credible interval, and is the Bayesian analog of a confidence interval.) How big does $n$ have to be to ensure

$$p(\ell \le \mu_n \le u|D) \ge 0.95$$

where $(\ell, u)$ is an interval (centered on $\mu_n$) of width 1 and $D$ is the data? Hint: recall that 95% of the probability mass of a Gaussian is within $\pm 1.96\sigma$ of the mean.

解答： 由题干可知 $\sigma_n\leq\frac{1}{2\times 1.96}$，又由习题 4.2 可知后验方差 $\sigma_n^2=\frac{s^2\sigma^2}{\sigma^2+s^2n}$，即要求 $\frac{s^2\sigma^2}{\sigma^2+s^2n}\leq \frac{1}{(2\times 1.96)^2}\rightarrow n\geq 61.02$，即要大于等于 62。

Exercise 4.4 [BIC for Gaussians †]

The Bayesian information criterion (BIC) is a penalized log-likelihood function that can be used for model selection. It is defined as

$$BIC = \log p(D|\hat{\theta}_{ML}) - \frac{d}{2} \log(N)$$

where $d$ is the number of free parameters in the model and $N$ is the number of samples. In this question, we will see how to use this to choose between a full covariance Gaussian and a Gaussian with a diagonal covariance. Obviously a full covariance Gaussian has higher likelihood, but it may not be “worth” the extra parameters if the improvement over a diagonal covariance matrix is too small. So we use the BIC score to choose the model. We can write

$$\log p(D|\hat{\Sigma}, \hat{\mu}) = -\frac{N}{2} \text{tr}(\hat{\Sigma}^{-1}\hat{S}) - \frac{N}{2} \log(|\hat{\Sigma}|)$$ $$\hat{S} = \frac{1}{N} \sum_{i=1}^N (x_i - \bar{x})(x_i - \bar{x})^T$$

where $\hat{S}$ is the scatter matrix (empirical covariance), the trace of a matrix is the sum of its diagonals, and we have used the trace trick.

• a. Derive the BIC score for a Gaussian in $D$ dimensions with full covariance matrix. Simplify your answer as much as possible, exploiting the form of the MLE. Be sure to specify the number of free parameters $d$.
• b. Derive the BIC score for a Gaussian in $D$ dimensions with a diagonal covariance matrix. Be sure to specify the number of free parameters $d$. Hint: for the digaonal case, the ML estimate of $\Sigma$ is the same as $\hat{\Sigma}_{ML}$ except the off-diagonal terms are zero:

$$\hat{\Sigma}_{diag} = \text{diag}(\hat{\Sigma}_{ML}(1, 1), \dots, \hat{\Sigma}_{ML}(D,D))$$

解答：

• a. $D$ 维高斯分布的 BIC 得分

$$\begin{aligned} \text{BIC} &=\log p(D\mid \hat{\Sigma},\hat{\mu})-\frac{d}{2}\log(N)\\ &=-\frac{N}{2}\mathrm{tr}(\hat{\Sigma}^{-1}\hat{S})-\frac{N}{2}\log (\lvert\hat{\Sigma}\rvert) - \frac{d}{2}\log (N)\\ &=-\frac{N}{2}-\frac{N}{2}\log (\lvert\hat{\Sigma}\rvert)-\frac{D(D+1)}{2}\log (N) \end{aligned}$$

• b.

$$\begin{aligned} \text{BIC}&=-\frac{N}{2}\mathrm{tr}(\hat{\Sigma}^{-1}\hat{S})-\frac{N}{2}\log (\lvert\hat{\Sigma}\rvert) - \frac{d}{2}\log (N)\\ &=-\frac{N}{2}-\frac{N}{2}\log (\lvert\hat{\Sigma}\rvert)-D\log(N) \end{aligned}$$

⚠️ 修正：

• a.

$$\begin{aligned} \text{BIC}_{full} &= \log p(D\mid \hat{\Sigma}_{ML},\hat{\mu}) - \frac{d}{2}\log(N)\\ &= -\frac{N}{2}\text{tr}(\hat{\Sigma}_{ML}^{-1}\hat{S}) - \frac{N}{2}\log(|\hat{\Sigma}_{ML}|) - \frac{D(D+3)}{4}\log(N) \quad \text{协方差矩阵上三角元素个数和均值个数}\\ &= -\frac{ND}{2} - \frac{N}{2}\log(|\hat{\Sigma}_{ML}|) - \frac{D(D+3)}{4}\log(N) \end{aligned}$$

• b.

$$\begin{aligned} \text{BIC}_{diag} &= \log p(D\mid \hat{\Sigma}_{diag},\hat{\mu}) - \frac{d}{2}\log(N)\\ &= -\frac{N}{2}\text{tr}(\hat{\Sigma}_{diag}^{-1}\hat{S}) - \frac{N}{2}\log(|\hat{\Sigma}_{diag}|) - \frac{2D}{2}\log(N) \\ &= -\frac{ND}{2} - \frac{N}{2}\log(|\hat{\Sigma}_{diag}|) - D\log(N) \end{aligned}$$

Exercise 4.5 [BIC for a 2d discrete distribution]

Let $x \in \{0, 1\}$ denote the result of a coin toss ($x = 0$ for tails, $x = 1$ for heads). The coin is potentially biased, so that heads occurs with probability $\theta_1$. Suppose that someone else observes the coin flip and reports to you the outcome, $y$. But this person is unreliable and only reports the result correctly with probability $\theta_2$; i.e., $p(y|x, \theta_2)$ is given by

	$y = 0$	$y = 1$
$x = 0$	$\theta_2$	$1 - \theta_2$
$x = 1$	$1 - \theta_2$	$\theta_2$

Assume that $\theta_2$ is independent of $x$ and $\theta_1$.

• a. Write down the joint probability distribution $p(x, y|\theta)$ as a 2x2 table, in terms of $\theta = (\theta_1, \theta_2)$.
• b. Suppose have the following dataset: $x = (1, 1, 0, 1, 1, 0, 0)$, $y = (1, 0, 0, 0, 1, 0, 1)$. What are the MLEs for $\theta_1$ and $\theta_2$? Justify your answer. Hint: note that the likelihood function factorizes,

$$p(x, y|\theta) = p(y|x, \theta_2)p(x|\theta_1)$$

What is $p(D|\hat{\theta}, M_2)$ where $M_2$ denotes this 2-parameter model? (You may leave your answer in fractional form if you wish.)

• c. Now consider a model with 4 parameters, $\theta = (\theta_{0,0}, \theta_{0,1}, \theta_{1,0}, \theta_{1,1})$, representing $p(x, y|\theta) = \theta_{x,y}$. (Only 3 of these parameters are free to vary, since they must sum to one.) What is the MLE of $\theta$? What is $p(D|\hat{\theta}, M_4)$ where $M_4$ denotes this 4-parameter model?
• d. Suppose we are not sure which model is correct. We compute the leave-one-out cross validated log likelihood of the 2-parameter model and the 4-parameter model as follows:

$$L(m) = \sum_{i=1}^n \log p(x_i, y_i|m, \hat{\theta}(D_{-i}))$$

and $\hat{\theta}(D_{-i})$ denotes the MLE computed on $D$ excluding row $i$. Which model will CV pick and why? Hint: notice how the table of counts changes when you omit each training case one at a time.

• e. Recall that an alternative to CV is to use the BIC score, defined as

$$BIC(M,D) \triangleq \log p(D|\hat{\theta}_{MLE}) - \frac{\text{dof}(M)}{2} \log N$$

where $\text{dof}(M)$ is the number of free parameters in the model, Compute the BIC scores for both models (use log base $e$). Which model does BIC prefer?

解答：

• a. $p(x=0,y=0\mid\theta)=\theta_2(1-\theta_1), p(x=1,y=0\mid \theta)=(1-\theta_2)\theta_1, p(x=0,y=1)=(1-\theta_2)(1-\theta_1), p(x=1,y=1\mid \theta)=\theta_2\theta_1$。
• b.

$$p(\{x_n, y_n\}_{n=1}^N\mid \theta)=\theta_1^4(1-\theta_1)^3\theta_2^4(1-\theta_2)^3$$

易得 $\theta_1=\theta_2=\frac{4}{7}$，同时求得 $p(D|\hat{\theta}, M_2)=(\frac{4}{7})^8 (\frac{3}{7})^6$。

• c.

$$\begin{aligned} \log p(\{x_n, y_n\}_{n=1}^N\mid \theta)&=\log\theta_{0,0}^2\theta_{0,1}^1\theta_{1,0}^2\theta_{1,1}^2\\ \theta_{0,0} &=\arg \max_{\theta_{0,0}} \log p(\{x_n, y_n\}_{n=1}^N\mid \theta) \text{ s.t. } \theta_{0,0}+\theta_{0,1}+\theta_{1,0}+\theta_{1,1}=1\\ \theta_{0,0}&= \arg \max_{\theta_{0,0}} 2\log \theta_{0,0}+\alpha(\theta_{0,0}+\theta_{0,1}+\theta_{1,0}+\theta_{1,1}-1)\\ \end{aligned}$$

易得 $\theta_{0,0}=\theta_{1,0}=\theta_{1,1}=\frac{2}{7},\theta_{0,1}=\frac{1}{7}$，同时求得 $p(D\mid \hat{\theta},M_4)=(\frac{2}{7})^6\frac{1}{7}$。

• d.

$$\begin{aligned} L(M_2)&=2 \log p(x=0,y=0\mid M_2, \hat{\theta}(D_{-(0,0)}))+2\log p(x=1,y=0)+\log p(x=0,y=1)+2\log p(x=1, y=1)\\ &=2\log p(x=0,y=0\mid \theta_1=\frac{2}{3},\theta_2=\frac{1}{2})+\cdots\\ &=-2 \log 6 +\cdots \quad \text{去掉（0，1）会出现无穷大} \end{aligned}$$ $$\begin{aligned} L(M_4)&=2 \log p(x=0,y=0\mid M_4, \hat{\theta}(D_{-(0,0)}))+2\log p(x=1,y=0)+\log p(x=0,y=1)+2\log p(x=1, y=1)\\ &=2\log p(x=0,y=0\mid \theta_{0,0}=\frac{1}{6}, \theta_{0,1}=\frac{1}{6}, \theta_{1,0}=\frac{1}{3}, \theta_{1,1}=\frac{1}{3})+\cdots\\ &=-2\log 6+\cdots \end{aligned}$$

• e.

$$\text{BIC}(M_2, D)=\log \left((\frac{4}{7})^8 (\frac{3}{7})^6\right)-\log 7$$ $$\text{BIC}(M_4,D)=\log \left((\frac{2}{7})^6\frac{1}{7} \right)-2\log7$$

⚠️ 纠正：

• e. 四参数模型参数和要求为1，所以自由参数为 $4-1=3$，最终答案为 $\text{BIC}(M_4,D)=\log \left((\frac{2}{7})^6\frac{1}{7} \right)-\frac{3}{2}\log7$

Exercise 4.6 [A mixture of conjugate priors is conjugate †]

Consider a mixture prior

$$p(\theta) = \sum_k p(z = k)p(\theta|z = k)$$

where each $p(\theta|z = k)$ is conjugate to the likelihood. Prove that this is a conjugate prior.

解答： 已知 $p(\theta \mid D) = \frac{p(\theta)p(D \mid \theta)}{p(D)}$，代入混合先验

$$\begin{aligned} p(\theta \mid D) &= \frac{\left( \sum_k p(z=k)p(\theta \mid z=k) \right) p(D \mid \theta)}{p(D)}\\ &= \frac{\sum_k p(z=k) \left[ p(\theta \mid z=k) p(D \mid \theta) \right]}{p(D)} \end{aligned}$$

又有在给定隐变量下的后验分布

$$\begin{aligned} p(\theta \mid D, z=k)& = \frac{p(\theta \mid z=k) p(D \mid \theta)}{p(D \mid z=k)}\\ p(\theta \mid z=k) p(D \mid \theta)& = p(\theta \mid D, z=k) p(D \mid z=k)\\ p(\theta \mid D) &= \frac{\sum_k p(z=k) p(D \mid z=k) p(\theta \mid D, z=k)}{p(D)} \quad \text{代入混合先验}\\ &= \sum_k \left( \frac{p(z=k) p(D \mid z=k)}{p(D)} \right) p(\theta \mid D, z=k)\\ &= \sum_k p(z=k \mid D) p(\theta \mid D, z=k) \end{aligned}$$

因为组件的先验 $p(\theta \mid z=k)$ 是共轭的，所以当它乘上似然 $p(D \mid \theta)$ 后，计算出的组件的后验 $p(\theta \mid D, z=k)$，在数学形式上，必定与它原来的组件的先验 $p(\theta \mid z=k)$ 属于同一个分布族。

Exercise 4.7 [ML estimator $\sigma^2_{mle}$ is biased]

Show that $\hat{\sigma}^2_{MLE} = \frac{1}{N} \sum_{n=1}^N(x_n - \hat{\mu})^2$ is a biased estimator of $\sigma^2$, i.e., show

$$\mathbb{E}_{X_1,\dots,X_n \sim \mathcal{N}(\mu,\sigma^2)}[\hat{\sigma}^2(X_1, \dots, X_n)] \neq \sigma^2$$

Hint: note that $X_1, \dots, X_N$ are independent, and use the fact that the expectation of a product of independent random variables is the product of the expectations.

解答：

$$\begin{aligned} \mathbb{E}_{X_1,\dots,X_n\sim \mathcal{N}(\mu,\sigma^2)}[\hat{\sigma}^2(X_1,\dots, X_n)]&=\mathbb{E}[\frac{1}{N}\sum_{n=1}^N (X_n -\hat{\mu})^2]\\ &=\mathbb{E}[\frac{1}{N}(\sum_{n=1}^N X_n^2+\frac{1}{N^2}(\sum_{n=1}^NX_n)^2-\frac{2}{N}(\sum_{n=1}^NX_n)^2)]\\ &=\frac{1}{N}\mathbb{E}[\sum_{n=1}^N X_n^2]+\frac{1}{N^3}\mathbb{E}[(\sum_{n=1}^NX_n)^2]-\frac{2}{N^2}\mathbb{E}[(\sum_{n=1}^NX_n)^2] \\ &=\sigma^2+\mu^2+\frac{1-2N}{N^3}\mathbb{E}[(\sum_{n=1}^NX_n)^2]\\ &=\sigma^2+\mu^2+\frac{1-2N}{N^3}[N(N-1)\mu^2+N(\sigma^2+\mu^2)]\\ &=\frac{N^2-2N+1}{N^2}\sigma^2+\frac{1-N}{N}\mu^2 \end{aligned}$$

⚠️ 纠错： 第二行展开错误

$$\begin{aligned} \mathbb{E}[\hat{\sigma}^2] &= (\sigma^2 + \mu^2) - \left(\mu^2 + \frac{\sigma^2}{N}\right)\\ &= \sigma^2 - \frac{\sigma^2}{N} = \frac{N-1}{N}\sigma^2 \end{aligned}$$

Exercise 4.8 [Estimation of $\sigma^2$ when $\mu$ is known †]

Suppose we sample $x_1, \dots, x_N \sim \mathcal{N}(\mu, \sigma^2)$ where $\mu$ is a known constant. Derive an expression for the MLE for $\sigma^2$ in this case. Is it unbiased?

解答：

$$\begin{aligned} \hat{\sigma}^2&=\arg \max_{\sigma^2} \sum_{n=1}^N [-\frac{1}{2}\log{2\pi}-\frac{1}{2}\log{\sigma^2}-\frac{(x_n-\mu)^2}{2\sigma^2}]\\ &=\arg \max_{\sigma^2} -\frac{N}{2}\log \sigma^2-\frac{1}{2\sigma^2}\sum_{n=1}^N(x_n-\mu)^2\\ &=\frac{\sum_{n=1}^N (x_n-\mu)^2}{2N} \end{aligned}$$

仍然是有偏的

⚠️ 纠正： 求导时犯错，应为 $\frac{\sum_{n=1}^N (x_n-\mu)^2}{N}$，并且在这个特定场景下（$\mu$ 是已知的常数），它是无偏估计。

$$\begin{aligned} \mathbb{E}[\hat{\sigma}^2] &= \mathbb{E}\left[ \frac{1}{N}\sum_{n=1}^N (X_n-\mu)^2 \right] \\ &= \frac{1}{N}\sum_{n=1}^N \mathbb{E}[(X_n-\mu)^2] \end{aligned}$$

由于题目已知 $\mu$ 就是真实的总体均值，所以根据方差的严格数学定义，$\mathbb{E}[(X_n-\mu)^2]$ 就是 $X_n$ 的真实方差 $\sigma^2$。

Exercise 4.9 [Variance and MSE of estimators for Gaussian variance †]

Prove that the standard error for the MLE for a Gaussian variance is

$$\sqrt{\mathbb{V}[\sigma^2_{mle}]} = \sqrt{\frac{2(N - 1)}{N^2}} \sigma^2$$

Hint: use the fact that

$$\frac{N - 1}{\sigma^2} \sigma^2_{unb} \sim \chi^2_{N-1}$$

and that $\mathbb{V}[\chi^2_{N-1}] = 2(N - 1)$. Finally, show that $MSE(\sigma^2_{unb}) = \frac{2}{N-1} \sigma^4$ and $MSE(\sigma^2_{mle}) = \frac{2N-1}{N^2}\sigma^4$.

解答： 已知 $\sigma_{mle}^2=\frac{N-1}{N}\sigma_{unb}^2$，因此 $\frac{N}{\sigma^2}\sigma_{mle}^2\sim\chi_{N-1}^2$，可得 $\sqrt{\mathbb{V}[\sigma^2_{mle}]} = \sqrt{\frac{2(N - 1)}{N^2}} \sigma^2$。

⚠️ 补充： 利用偏差-方差分解公式：

$$\text{MSE}(\hat{\theta}) = \mathbb{V}[\hat{\theta}] + (\text{Bias}(\hat{\theta}))^2$$ $$\begin{aligned} \frac{(N-1)^2}{\sigma^4} \mathbb{V}[\sigma^2_{unb}] &= 2(N-1) \implies \mathbb{V}[\sigma^2_{unb}] = \frac{2}{N-1}\sigma^4\\ \text{MSE}(\sigma^2_{unb}) &= \frac{2}{N-1}\sigma^4 + 0^2 = \frac{2}{N-1}\sigma^4 \end{aligned}$$

由习题 4.7 可知偏差为：

$$\text{Bias}(\sigma^2_{mle}) = \mathbb{E}[\sigma^2_{mle}] - \sigma^2 = \frac{N-1}{N}\sigma^2 - \sigma^2 = -\frac{1}{N}\sigma^2$$

又由前半部分结论 $\mathbb{V}[\sigma_{mle}^2] = \frac{2(N-1)}{N^2} \sigma^4$，可得

$$\text{MSE}(\sigma^2_{mle}) = \frac{2N-2}{N^2} \sigma^4 + \frac{1}{N^2}\sigma^4 = \frac{2N-1}{N^2} \sigma^4$$