東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目II 問題6

标签：

• Tokyo-University
• Normal-Distribution
• Conditional-Density
• Maximum-Likelihood-Estimation
• Expectation-Maximization-Algorithm

Author

zephyr

Description

The probability density function of the normal distribution $N(\mu, \sigma^2)$ with mean $\mu \in \mathbb{R}$ and variance $\sigma^2 > 0$ is given by

$$f(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x - \mu)^2}{2\sigma^2}\right).$$

Let $X$ and $Z$ be random variables that independently follow $N(\mu, 1)$ and $N(0, 1)$, respectively, and define $Y = \theta X + Z$ for some constant $\theta \in \mathbb{R}$. For an integer $n > 1$, let $(X_1, Y_1), (X_2, Y_2), \ldots, (X_n, Y_n)$ be two-dimensional random variables that independently follow the same distribution as $(X, Y)$, for which we write $X^{(n)} = (X_1, X_2, \ldots, X_n)$ and $Y^{(n)} = (Y_1, Y_2, \ldots, Y_n)$.

Answer the following questions.

(1) Express the expectation $\mathbb{E}[Y]$ and variance $\mathbb{V}[Y]$ of $Y$ using $\mu$ and $\theta$.

(2) Show that the conditional distribution of $X$ given $Y$ is a normal distribution, and express its expectation $\mathbb{E}[X|Y]$ and variance $\mathbb{V}[X|Y]$ using $\mu$, $\theta$, and $Y$.

(3) Let $(x^{(n)}, y^{(n)})$ denote a realization of $(X^{(n)}, Y^{(n)})$. Express the joint probability density function $p_{\mu, \theta}(x^{(n)}, y^{(n)})$ of $(X^{(n)}, Y^{(n)})$ using $\mu, \theta, x^{(n)} = (x_1, x_2, \ldots, x_n)$ and $y^{(n)} = (y_1, y_2, \ldots, y_n)$.

(4) Consider maximum-likelihood estimation of $(\mu, \theta)$ by the EM algorithm for the case where the observation of $X_n$ is missing from $(X^{(n)},Y^{(n)})$, that is, the case where $(X^{(n-1)},Y^{(n)})$ is observed. Then the update rule of estimators of $(\mu, \theta)$ by the EM algorithm for some initial value $(\mu_0, \theta_0) \in \mathbb{R}^2$ is given by

$$(\mu_{t+1}, \theta_{t+1}) = \mathop{\arg\max}\limits_{(\mu, \theta) \in \mathbb{R}^2} \mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}[\log p_{\mu, \theta}(X^{(n)},Y^{(n)})], \quad t = 0, 1, \ldots,$$

where $\bar{\mu}$ and $\bar{\sigma}^2$ are the values obtained by the substitution $(\mu, \theta, Y) := (\mu_t, \theta_t, Y_n)$ in the expressions of $\mathbb{E}[X|Y]$ and $\mathbb{V}[X|Y]$ obtained in question (2), respectively, and $\mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}$ denotes the expectation when $X_n$ follows $N(\bar{\mu}, \bar{\sigma}^2)$ and $(X^{(n-1)},Y^{(n)})$ is fixed.

• (i) Express $\mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}[\log p_{\mu, \theta}(X^{(n)},Y^{(n)})]$ using $\mu, \theta, \bar{\mu}, \bar{\sigma}^2, X^{(n-1)}$ and $Y^{(n)}$.
• (ii) Express $(\mu_{t+1}, \theta_{t+1})$ using $n, \bar{\mu}, \bar{\sigma}^2, X^{(n-1)}$ and $Y^{(n)}$.

题目描述

均值为 $\mu\in\mathbb R$、方差为 $\sigma^2>0$ 的正态分布 $N(\mu,\sigma^2)$ 的密度为

$$f(x)=\frac1{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right).$$

设随机变量 $X,Z$ 相互独立，分别服从 $N(\mu,1)$ 与 $N(0,1)$，并令 $Y=\theta X+Z$，其中 $\theta\in\mathbb R$。对整数 $n>1$，令 $(X_i,Y_i)\ (i=1,\ldots,n)$ 独立同分布于 $(X,Y)$，记 $X^{(n)}=(X_1,\ldots,X_n)$、$Y^{(n)}=(Y_1,\ldots,Y_n)$。回答下列问题。

（1）用 $\mu,\theta$ 表示 $\mathbb E[Y]$ 和 $\mathbb V[Y]$。

（2）证明给定 $Y$ 时 $X$ 的条件分布仍为正态分布，并用 $\mu,\theta,Y$ 表示 $\mathbb E[X\mid Y]$ 与 $\mathbb V[X\mid Y]$。

（3）设 $(x^{(n)},y^{(n)})$ 是 $(X^{(n)},Y^{(n)})$ 的一个实现。用 $\mu,\theta,x^{(n)},y^{(n)}$ 写出其联合密度 $p_{\mu,\theta}(x^{(n)},y^{(n)})$。

（4）现在 $X_n$ 缺失，仅观测到 $(X^{(n-1)},Y^{(n)})$，用 EM 算法估计 $(\mu,\theta)$。从任意初值 $(\mu_0,\theta_0)$ 出发，更新规则为

$$(\mu_{t+1},\theta_{t+1}) =\mathop{\arg\max}_{(\mu,\theta)\in\mathbb R^2} \mathbb E_{X_n\sim N(\bar\mu,\bar\sigma^2)} [\log p_{\mu,\theta}(X^{(n)},Y^{(n)})],$$

其中 $\bar\mu,\bar\sigma^2$ 分别是在第（2）问的条件均值、条件方差表达式中代入 $(\mu,\theta,Y)=(\mu_t,\theta_t,Y_n)$ 所得；取期望时固定 $(X^{(n-1)},Y^{(n)})$。

• （i）用 $\mu,\theta,\bar\mu,\bar\sigma^2,X^{(n-1)},Y^{(n)}$ 表示上述期望对数似然。
• （ii）用 $n,\bar\mu,\bar\sigma^2,X^{(n-1)},Y^{(n)}$ 表示更新后的 $(\mu_{t+1},\theta_{t+1})$。

Kai

(1)

The random variable $Y$ is defined as $Y = \theta X + Z$, where $X \sim N(\mu, 1)$ and $Z \sim N(0, 1)$. Since $X$ and $Z$ are independent, we can calculate the expectation and variance of $Y$ as follows:

1. Expectation of $Y$:

$$\mathbb{E}[Y] = \mathbb{E}[\theta X + Z] = \theta \mathbb{E}[X] + \mathbb{E}[Z] = \theta \mu + 0 = \theta \mu$$

2. Variance of $Y$:

$$\mathbb{V}[Y] = \mathbb{V}[\theta X + Z] = \theta^2 \mathbb{V}[X] + \mathbb{V}[Z] = \theta^2 \cdot 1 + 1 =\theta^2 + 1$$

(2)

To find the conditional distribution of $X$ given $Y$, note that $Y = \theta X + Z$, where $X \sim N(\mu, 1)$ and $Z \sim N(0, 1)$. The joint distribution of $(X, Y)$ is bivariate normal, which implies that the conditional distribution $X|Y$ is also normal.

1. Expectation of $X|Y$:

$$\mathbb{E}[X|Y] = \mu + \frac{\theta}{\theta^2 + 1} (Y - \theta\mu)$$

2. Variance of $X|Y$:

$$\mathbb{V}[X|Y] = \frac{1}{\theta^2 + 1}$$

This can be derived using the properties of conditional distributions for bivariate normal distributions.

(3)

The joint probability density function $p_{\mu, \theta}(\mathbf{x}^{(n)}, \mathbf{y}^{(n)})$ for the random variables $\mathbf{X}^{(n)} = (X_1, X_2, \ldots, X_n)$ and $\mathbf{Y}^{(n)} = (Y_1, Y_2, \ldots, Y_n)$ can be expressed as the product of the marginal distributions of $X_i$ and the conditional distributions of $Y_i$ given $X_i$:

$$p_{\mu, \theta}(\mathbf{x}^{(n)}, \mathbf{y}^{(n)}) = \prod_{i=1}^{n} \left( \frac{1}{\sqrt{2\pi}} \exp\left(-\frac{(x_i - \mu)^2}{2}\right) \cdot \frac{1}{\sqrt{2\pi}} \exp\left(-\frac{(y_i - \theta x_i)^2}{2}\right) \right)$$

Expanding this, we get:

$$p_{\mu, \theta}(\mathbf{x}^{(n)}, \mathbf{y}^{(n)}) = \frac{1}{(2\pi)^{n}} \exp\left(-\sum_{i=1}^{n} \left[\frac{(x_i - \mu)^2}{2} + \frac{(y_i - \theta x_i)^2}{2}\right]\right)$$

(4)

(i)

The expectation $\mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}[\log p_{\mu, \theta}(\mathbf{X}^{(n)}, \mathbf{Y}^{(n)})]$ is given by:

$$\mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}[\log p_{\mu, \theta}(\mathbf{X}^{(n)}, \mathbf{Y}^{(n)})] = \mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}\left[-\sum_{i=1}^{n-1} \left(\frac{(x_i - \mu)^2}{2} + \frac{(y_i - \theta x_i)^2}{2}\right) - \left(\frac{(X_n - \mu)^2}{2} + \frac{(y_n - \theta X_n)^2}{2}\right)\right]$$

Simplifying further using the properties of the expectation for a normal distribution:

$$\mathbb{E}_{X_n \sim N(\bar{\mu}, \bar{\sigma}^2)}[\log p_{\mu, \theta}(\mathbf{X}^{(n)}, \mathbf{Y}^{(n)})] = -\sum_{i=1}^{n-1} \left(\frac{(x_i - \mu)^2}{2} + \frac{(y_i - \theta x_i)^2}{2}\right) - \frac{1}{2}\left((\bar{\mu} - \mu)^2 + \bar{\sigma}^2 + \frac{(y_n - \theta \bar{\mu})^2}{\theta^2 + 1}\right)$$

(ii)

The update rule for $(\mu_{t+1}, \theta_{t+1})$ in the EM algorithm is obtained by maximizing the expression found in part (i):

$$(\mu_{t+1}, \theta_{t+1}) = \mathop{\arg\max}\limits_{(\mu, \theta) \in \mathbb{R}^2} \left[-\sum_{i=1}^{n-1} \left(\frac{(x_i - \mu)^2}{2} + \frac{(y_i - \theta x_i)^2}{2}\right) - \frac{1}{2}\left((\bar{\mu} - \mu)^2 + \bar{\sigma}^2 + \frac{(y_n - \theta \bar{\mu})^2}{\theta^2 + 1}\right)\right]$$

Solving this for $\mu$ and $\theta$, we find:

$$\mu_{t+1} = \frac{1}{n} \left(\sum_{i=1}^{n-1} x_i + \bar{\mu}\right)$$

$$\theta_{t+1} = \frac{\sum_{i=1}^{n-1} y_i x_i + y_n \bar{\mu}}{\sum_{i=1}^{n-1} x_i^2 + \bar{\mu}^2 + \frac{1}{\theta^2 + 1}}$$

This update rule depends on the observed data $\mathbf{X}^{(n-1)}, \mathbf{Y}^{(n)}$ and the estimates $\bar{\mu}, \bar{\sigma}^2$ obtained from the conditional expectation.

Knowledge

正态分布 条件分布 数值期望 EM算法 最大似然估计

难点思路

推导条件分布涉及到二元正态分布的性质，尤其是推导条件期望和方差时，需要对协方差矩阵有深刻理解。EM 算法的难点在于构建对数似然函数的期望，并通过优化找到参数的更新规则。

解题技巧和信息

1. 条件分布：对于二元正态分布，条件分布仍然是正态分布，且其参数可以通过边际分布的参数计算得到。
2. EM 算法：EM 算法通过最大化对数似然函数的期望来迭代更新参数，对于缺失数据的问题尤为有效。
3. 最大似然估计：通常情况下，EM 算法能够保证参数的渐进一致性，即经过多次迭代，参数估计会收敛到真值。

重点词汇

• Expectation-Maximization (EM) Algorithm: 期望最大化算法
• Conditional distribution: 条件分布
• Maximum likelihood estimation: 最大似然估计
• Normal distribution: 正态分布

参考资料

1. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Chapter 9: Mixture Models and EM.
2. Casella, G., & Berger, R. L. (2001). Statistical Inference (2nd ed.). Duxbury. Chapter 7: Estimation.