[PRML] Chapter2 - Probability Distribution (2)
Gausisan distribution의 성질을 알아보자.
2.3 Gaussian distribution
- Multivariate Gaussian distribution
- D 차원의 vector $\textbf{x}$에 대한 distribution
- entropy가 가장 큰 분포가 gaussian이고 multivariate gaussian도 해당한다.
- ${\Sigma}$ : D*D의 covariance matrix
$$N(\pmb{x} | \pmb{\mu}, \pmb{\Sigma}) = \frac{1}{(2\pi)^{D/2}} \frac{1}{ | \pmb{\Sigma} |^{1/2} } \exp{ -\frac{1}{2}(\pmb{x} - \pmb{\mu})^T \pmb{\Sigma}^{-1}(\pmb{x} - \pmb{ \mu})}$$
Gaussian distribution은 상당히 중요한 특징들을 갖고 있다 하나씩 살펴보자.
$$\Delta^2 = ({\bf x}-{\pmb \mu})^T{\bf \Sigma}^{-1}({\bf x}-{\pmb \mu}) $$
- $\Delta$ : Mahalanobis distance from $\pmb{\mu}$ to $\textbf{x}$
- $\pmb{\Sigma}$가 identity이면 Euclidean distance
$\pmb{\Sigma}$는 (실수)대칭행렬이므로
- 고윳값이 실수
- 고유벡터들은 orthonomal하게 가능
- 고유대각화가 가능하고 아울어 직교대각화가 가능하다.
$${\bf \Sigma}=\sum_{i=1}^{D}{\pmb \Lambda}_i{\bf u}_i{\bf u}_i^T = U{\pmb \Lambda} U^{-1}$$
$${\bf \Sigma}^{-1}=\sum_{i=1}^{D}\dfrac{1}{\pmb \Lambda}_i{\bf u}_i{\bf u}_i^T = U {\pmb \Lambda}^{-1} U^{-1}$$
이를 위에 대입하면
$$\Delta^2 = \sum_{i=1}^{D}\frac{y_i^2}{\pmb \Lambda}_i $$
- $y_i={\bf u}_i^T({\bf x}-{\pmb \mu})$
- 우리는 ${y_i}$를 orthonomal vector $\textbf{u}_i$에 의해 새롭게 정의된 coordinate system이라고 이해할 수 있다.
multivariate gaussian의 평균과 분산은
- $E[\textbf{x}] = {\pmb \mu}$
- $cov[\textbf{x}] = {\pmb \Sigma}$ : 공분산행렬 (covariance matrix)
multivariate gaussian은 유용한 분포지만 한계점도 있다.
- 공분산행렬의 parameter 개수
- 공분산행렬의 parameter는 $D(D+3)/2$ 개 이다. 차원이 커짐에 따라 parameter가 quadratic하게 커진다. 이를 위한 해결책은 2가지가 있는데
- 공분산행렬은 대각행렬로 생각한다. 즉, ${\pmb \Sigma} = diag(\sigma_i^2)$
- 공분산행렬을 isotropic covariance로 만든다. 즉, ${\pmb \Sigma} = \sigma^2{\pmb I}$
- 물론 이런 제약이 생기면 data간의 correlation을 못 잡는 경우가 발생한다.
- 공분산행렬의 parameter는 $D(D+3)/2$ 개 이다. 차원이 커짐에 따라 parameter가 quadratic하게 커진다. 이를 위한 해결책은 2가지가 있는데
- gaussian은 unimodal 하기에 multimodal distribution을 잘 approximation하기 어렵다.
- 이에 대해 해결책은 나중에 뒤에서 배운다. (Mixture 등등)
2.3.1 Conditional Gaussian distributions
conditional distribution의 경우를 살펴보자. $\textbf{x}$는 Gaussian distribution $N(\textbf{x} | {\pmb \mu, \Sigma})$의 D-차원 vector이다. 이를 두 부분으로 나누어 $\textbf{x}_a, \textbf{x}_b$ 라고 하자. D*D covariance matrix는 대칭행렬이다.
$$\textbf{x} = \begin{pmatrix} \textbf{x}_a \\ \textbf{x}_b \end{pmatrix}, {\pmb \mu} = \begin{pmatrix} {\pmb \mu}_a \\ {\pmb \mu}_b \end{pmatrix}$$
$${\pmb \Sigma} = \begin{pmatrix} \Sigma_{aa} & \Sigma_{ab} \\ \Sigma_{ba} & \Sigma_{bb} \end{pmatrix}$$
- precision matrix
$${\pmb \Lambda} \equiv {\pmb \Sigma}^{-1} = \begin{pmatrix} {\pmb \Lambda} _ {aa} & {\pmb \Lambda} _ {ab} \\ {\pmb \Lambda} _ {ba} & {\pmb \Lambda}_{bb} \end{pmatrix}$$
이제 우리는 conditional distribution $p(\textbf{x}_a | \textbf{x}_b)$ 을 살펴보자. (gaussian은 quadratic form in the exponent를 주의깊게 살펴보자) $\textbf{x}_b$는 fixed 되었으며 exp 안의 부분을 나눠서보면
$$-\frac{1}{2}({\bf x}-{\pmb \mu})^T\Sigma^{-1}({\bf x}-{\pmb \mu})=$$
$$ -\frac{1}{2}({\bf x}_a - {\pmb \mu}_a)^T{\pmb \Lambda} _ {aa}({\bf x}_a-{\pmb \mu}_a) - \frac{1}{2}({\bf x}_a - {\pmb \mu}_a)^T {\pmb \Lambda} _ {ab}({\bf x}_b-{\pmb \mu}_b)$$
$$-\frac{1}{2}({\bf x}_b-{\pmb \mu}_b)^T{\pmb \Lambda} _ {ba}({\bf x}_a-{\pmb \mu}_a) - \frac{1}{2}({\bf x}_b - {\pmb \mu}_b)^T{\pmb \Lambda} _ {bb}({\bf x}_b-{\pmb \mu}_b) $$
위 식을 보면 $\textbf{x}_a$ 에 대한 함수이고 quadratic form 임을 알 수 있다. 즉 conditional dist는 Gaussian인 것이다.
이제 평균과 분산을 구하는 과정을 살펴보자. 먼저, $\textbf{x}_a$의 second order인 부분을 먼저보면
$$-\frac{1}{2}\textbf{x}^T_a {\pmb \Lambda}_{aa} \textbf{x}_a$$
따라서 우리는 conditional distribution $p(\textbf{x}_a | \textbf{x}_b)$의 covariance 가
$${\pmb \Sigma_{a|b} = {\pmb \Lambda}_{aa}^{-1}}$$
임을 알 수 있다. 다음은 $\textbf{x}_a$에 linear한 부분을 보면
$$\textbf{x}_a^T { {\pmb \Lambda} _ {aa} {\pmb \mu}_a - {\pmb \Lambda} _ {ab}(\textbf{x}_a - {\pmb \mu}_b)}$$
이를 이용하여 우리는 평균을 구할 수 있다.
$${\pmb \mu} _ {a|b} = {\pmb \Sigma}_{a|b} [ {\pmb \Lambda} _ {aa}{\pmb \mu}_a - {\pmb \Lambda} _ {ab}({\bf x}_b-{\pmb \mu}_b) ] = {\pmb \mu}_a -{\pmb \Lambda} _ {aa}^{-1}{\pmb \Lambda} _ {ab}({\bf x}_b-{\pmb \mu}_b) $$
다음으로 공분산행렬을 구하면
$${\pmb \Sigma}_{a|b} = {\pmb \Sigma} _ {aa} - {\pmb \Sigma} _ {ab}{\pmb \Sigma} _ {bb}^{-1}{\pmb \Sigma} _ {ba} $$
- [참고] 아래의 공식을 이용하여 구한다. $$$$
$$M = (A-BD^{-1}C)^{-1} $$
- 결론 : conditional distribution도 Gaussian distribution이다
- mean은 linear function of $\textbf{x}_b$
- covariance은 independent of $\textbf{x}_b$
2.3.2 Mariginal Gaussian distributions
$$p({\bf x}_a) = \int p({\bf x}_a, {\bf x}_b)d{\bf x}_b $$
joint distribution에서 integrate out $x_b$하면 된다. 이번에도 마찬가지로 quadratic form을 이용하여 문제를 해결한다. 위에서 봤던 joint distribution의 exp부분을 이번에는 $\textbf{x}_b$에 대해 전개하면
$$-\dfrac{1}{2}{\bf x}_b^{T}{\pmb \Lambda} _ {bb}{\bf x}_b + {\bf x}_b^T{\bf m} = -\dfrac{1}{2}({\bf x}_b- {\pmb \Lambda} _ {bb}^{-1}{\bf m})^T {\pmb \Lambda} _ {bb}({\bf x}_b- {\pmb \Lambda} _ {bb}^{-1}{\bf m}) + \dfrac{1}{2}{\bf m}^T {\pmb \Lambda} _ {bb}^{-1}{\bf m}$$
$$\text{where}\;{\bf m} = {\pmb \Lambda}_{bb}{\pmb \mu} _ b - {\pmb \Lambda} _ {ba}({\bf x}_a-{\pmb \mu}_a)$$
위의 식 우항에서 첫번째 부분은 quadratic form으로 만들었다. integrate하면 exp부분을 제외한 Gaussian distribution의 normalization constant가 나온다. 이는 첫번째항의 covariance determinant만 관련이 있고 $\textbf{x}_a$와 independent하다. 결국 중요한건 $\textbf{x}_a$와 dependent한 뒷부분인데 이를 정리하면 ${\bf x}_a$에 대한 marginal gaussian distribution가 된다.
$$\dfrac{1}{2}[{\pmb \Lambda} _ {bb}{\pmb \mu}_b-{\pmb \Lambda} _ {ba}({\bf x}_a-{\pmb \mu}_a)]^T {\pmb \Lambda} _ {bb}^{-1}[{\pmb \Lambda} _ {bb}{\pmb \mu}_b-{\pmb \Lambda} _ {ba}({\bf x}_a-{\pmb \mu}_a)]$$
$$- \dfrac{1}{2}{\bf x}_a^T{\pmb \Lambda} _ {aa}{\bf x}_a + {\bf x}_a^T({\pmb \Lambda} _ {aa}{\pmb \mu}_a+{\pmb \Lambda} _ {ab}{\pmb \mu}_b) + const$$
$$= - \dfrac{1}{2}{\bf x}_a^T({\pmb \Lambda} _ {aa}-{\pmb \Lambda} _ {ab}{\pmb \Lambda} _ {bb}^{-1}{\pmb \Lambda} _ {ba}){\bf x}_a + {\bf x}_a^T({\pmb \Lambda} _ {aa}-{\pmb \Lambda} _ {ab}{\pmb \Lambda} _ {bb}^{-1}{\pmb \Lambda} _ {ba}){\pmb \mu}_a+const $$
이를 이용하여 marginal distribution을 구하면 된다. 먼저, covariance는
$${\pmb \Sigma}_a = ({\pmb \Lambda} _ {aa}-{\pmb \Lambda} _ {ab}{\pmb \Lambda} _ {bb}^{-1}{\pmb \Lambda} _ {ba})^{-1} = {\pmb \Sigma} _ {aa}$$
mean은 아래와 같다.
$${\pmb \Sigma}_a({\pmb \Lambda} _ {aa}-{\pmb \Lambda} _ {ab}{\pmb \Lambda} _ {bb}^{-1}{\pmb \Lambda} _ {ba}){\pmb \mu}_a = {\pmb \mu}_a$$
- 결론 : Marginal distribution도 Gaussian distribution이다.
- $E[\textbf{x}_a] = {\pmb \mu}_a$
- $cov[\textbf{x}_a] = \Sigma _{aa}$
- 직관과 거의 일치한다. (partitioned한 부분)
2.3.3 Bayes’ theorem for Gaussian variables
Gaussian marginal distribution $p(\textbf{x})$ , Gaussian conditional distribution $p(\textbf{y} | \textbf{x})$가 주어진 상태이다. (2.3.1과 2.3.2에서 알게된 사실을 토대로)
$$p({\bf x}) = N({\bf x}|{\pmb \mu}, {\pmb \Lambda}^{-1}) $$
$$p({\bf y}|{\bf x}) = N({\bf y}|{\bf A} {\bf x}+{\bf b} , \textbf{L}^{-1}) $$
우리는 Gaussian marginal distribution $p(\textbf{y})$ , Gaussian conditional distribution $p(\textbf{x} | \textbf{y})$를 구하고자 한다. 먼저 joint distribution을 구한 뒤에 구해보자.
$${\bf z} = \dbinom{ {\bf x} }{ {\bf y} }$$
$$\ln p({\bf z}) = \ln p({\bf x}) + \ln p({\bf y}) \\ = -\frac{1}{2}({\bf x}-{\pmb \mu})^T{\pmb \Lambda}({\bf x}-{\pmb \mu}) -\frac{1}{2}({\bf y}-{\bf A}{\bf x}-{\bf b})^T {\bf L}({\bf y}-{\bf A}{\bf x}-{\bf b})+const $$
위의 식은 quadratic 형태의 함수라는 것을 알수 있고 따라서 Gaussian distribution의 함수일 것이다. 위의 식을 전개하여 이차항을 살펴보면 (for covariance)
$$-\frac{1}{2} {\bf x}^T ({\pmb \Lambda} + {\bf A}^T {\pmb \Lambda} {\bf A}) {\bf x} - \frac{1}{2} {\bf y}^T {\bf L}{\bf y} + \frac{1}{2} {\bf x}^T {\bf A}{\bf L}{\bf y}$$
$$ = -\frac{1}{2} \dbinom{ {\bf x} }{ {\bf y} }^T \left(\begin{array}{cc}{\pmb \Lambda}+{\bf A}^T{\bf L}{\bf A} & -{\bf A}^T{\bf L} \\ - {\bf L}{\bf A} & {\bf L}\end{array} \right) \dbinom{ {\bf x} }{ {\bf y} } = -\frac{1}{2}{\bf z}^T{\bf R}{\bf z}$$
따라서 precision matrix는
$${\bf R} = \left(\begin{array}{cc}{\pmb \Lambda}+{\bf A}^T{\bf L}{\bf A} & -{\bf A}^T{\bf L}\-{\bf L}{\bf A} & {\bf L}\end{array}\right)$$
임을 알 수 있다. 이를 inverse하여 covariance matrix를 구하면
$$cov[{\bf z}]={\bf R}^{-1} = \left(\begin{array}{cc}{\pmb \Lambda}^{-1} & {\pmb \Lambda}^{-1}{\bf A}^T \ {\bf A}{\pmb \Lambda}^{-1} & {\bf L}^{-1}+{\bf A}{\pmb \Lambda}^{-1}{\bf A}^T \end{array}\right)$$
이전의 방법을 이용하여 mean을 구할 수 있다.
$${\bf x}^T{\pmb \Lambda}{\pmb \mu} - {\bf x}^T{\bf A}^T{\bf L}{\bf b} + {\bf y}^T{\bf L}{\bf b} = \dbinom{ {\bf x} }{ {\bf y} }^T \dbinom {\pmb \Lambda}{\pmb \mu}-{\bf A}^T{\bf L}{\bf b} {\bf L}{\bf b} $$
$$E[{\bf z}] = {\bf R}^{-1}\dbinom{ {\bf x} }{ {\bf y} }^T\dbinom {\pmb \Lambda}{\pmb \mu}-{\bf A}^T{\bf L}{\bf b} {\bf L}{\bf b}$$
전개하면 최종적으로 mean은
$$E[{\bf z}] = \dbinom{ {\pmb \mu} }{ {\bf A} {\pmb \mu} - {\bf b}}$$
- 결과
$$E[{\bf y}] = {\bf A}{\pmb \mu} + {\bf b}$$
$$cov[{\bf y}] = {\bf L}^T + {\bf A}{\pmb \Lambda}^{-1}{\bf A}^T $$
다음은 conditional distribution $p(\textbf{x}| \textbf{y})$ 의 mean, covariance를 구하면
$$\Sigma_{a|b}={\pmb \Lambda} _ {aa}^{-1} \ {\pmb \mu}_{a|b}={\pmb \mu}_a - {\pmb \Lambda} _ {aa}^{-1}{\pmb \Lambda} _ {ab}({\bf x}_b-{\pmb \mu}_b)$$
$$E[{\bf x}|{\bf y}] = ({\pmb \Lambda}+{\bf A}^T{\bf L}{\bf A})^{-1}{ {\bf A}^T{\bf L}({\bf y}-{\bf b})+{\pmb \Lambda}{\pmb \mu}} $$
$$cov[{\bf x}|{\bf y}] = ({\pmb \Lambda}+{\bf A}^T{\bf L}{\bf A})^{-1} $$
2.3.4 Maximum likelihood for the Gaussian
- Log likelihood
$$\ln p({\bf X}|{\pmb \mu}, \Sigma) = -\frac{ND}{2}\ln(2\pi) - \frac{N}{2}\ln|\Sigma|-\frac{1}{2}\sum_{n=1}^{N}({\bf x}_n-{\pmb \mu})^T\Sigma^{-1}({\bf x}_n-{\pmb \mu})$$
(과정 생략) $${\pmb \mu} _ {ML} = \frac{1}{N}\sum_{i=1}^{N}{\bf x}_i = \bar{\bf x}$$
$${ \pmb \Sigma} _ {ML} = \frac{1}{N}\sum_{i=1}^{N}({\bf x}_i-\mu)({\bf x}_i-\mu)^T$$
2.3.5 Sequential estimation
data sample이 하나 들어오면 바로 계산하고 버린다. MLE를 구하는 예시를 살펴보자.
$${\pmb \mu} _ {ML}^{(N)} = \frac{1}{N} \sum_{n=1}^{N}{\bf x}_n = \frac{1}{N}{\bf x} _ N + \frac{1}{N} \sum _ {n=1}^{N-1}{\bf x}_n$$
$$= \frac{1}{N}{\bf x}_N + \frac{N-1}{N}{\pmb \mu} _ {ML}^{(N-1)}={\pmb \mu} _ {ML}^{(N-1)}+\frac{1}{N}({\bf x}_N-{\pmb \mu} _ {ML}^{(N-1)}) $$
이전에 구한 parameter를 ’error signal’ $(\textbf{x} _N - {\pmb \mu} _{ML}^{(N-1)})$ 쪽으로 1/N에 비례하도록 수정하여 parameter를 업데이트한다. $N$이 커질수록 새로운 data의 영향은 작아진다. 이번에는 이런 Sequential estimation에서 사용되는 일반적인 방법에 대해 살펴보자.
- 바로 Robbins-Monro algorithm이다.
random variables $\theta, z$가 있다. conditional expectation은
$$f(\theta)\equiv E[z|\theta] = \int zp(z|\theta)dz $$
이고 이러한 형태를 regression function이라고 부른다. 우리의 목표는 $f(\theta^{ * }) = 0$을 만족하는 root $\theta^{ * }$를 찾는 것이다.
- 몇가지 가정을 살펴보면
- data가 많으면 한번에 regression function을 만들고 root를 estimation할 수 있겠지만 지금은 Sequential하게 data가 하나씩 구해진다고 가정한다.
- $E[(z-f)^2 | \theta]<\infty$ : conditional variance는 finite하다고 가정한다.
- $\theta > \theta^{ * } \rightarrow f(\theta) > 0$
- $\theta < \theta^{ * } \rightarrow f(\theta) < 0$
Robbins-Monro의 방법은
$$\theta^{(N)} = \theta^{(N-1)} - a_{N-1} z(\theta^{N-1}) $$
- 여기서 $z(\theta^{(N)})$은 N번째의 $\theta$가 들어왔을 때, $z$의 값을 의미한다.
- $a_N$은 양의 실수이며 다음과 같은 조건을 갖는다.
- $\lim_{N\rightarrow\infty}a_N=0 $ : $\theta$가 특정값에 수렴
- $\sum_{N=1}^{\infty}a_N=\infty $ : root를 찾기도 전에 다른 값에 수렵하지 않도록
- $% $ : 축적되는 noise가 finite하여 수렴을 방해하지 않는다.
이제 이 방법을 통해 이전에 구했던 MLE의 예시에 적용해보자.
$$\frac{\partial}{\partial\theta}{-\frac{1}{N}\sum_{n=1}^{N}\ln p(x_n|\theta)}_ {\theta_{MLE}}=0$$
MLE는 위처럼 log likelihood function을 미분하여 0으로 만드는 값니다.
- as $N \rightarrow \infty$
$$-\lim_{n\rightarrow\infty}\frac{1}{N}\sum_{n=1}^{N}\frac{\partial}{\partial\theta}\ln p(x_n|\theta) = E_x\left[-\frac{\partial}{\partial\theta}\ln p(x|\theta)\right] $$
이제 Robbins-Monro의 방법을 적용하면
$$\theta^{(N)} = \theta^{(N-1)} - a_{N-1}\frac{\partial}{\partial\theta^{(N-1)}}\left[-\ln p(x_N/\theta^{(N-1)})\right] $$
$$z=\frac{\partial}{\partial\mu_{ML}}[-\ln p(x|\mu_{ML}, \sigma^2)]=-\frac{1}{\sigma^2}(x-\mu_{ML}) $$
따라서 $\textbf{x}_N$을 대입하고 $a_N = \sigma^1 / N$을 대입하면 처음에 구한 결과와 같다.