Generative Model Learning (2) - Monte Carlo Estimation

 

목차

• Learning Density Estimation
  • Monte Carlo Estimation
  • Monte Carlo Estimation and Maximum Likelihood

 

 

이번 포스팅에는 Pre-knowledges for Generative Models (1) 글에 이어 Monte Carlo Estimation에 대해 다뤄보려 한다.

Pre-knowledges for Generative Models (1) - KL-divergence, Maximum likelihood

 

 

 

Learning Density Estimation

 

 

 

Monte Carlo Estimation

 

Monte Carlo estimation은 random sampling을 여러 번 하여 기댓값 계산을 근사하기 위해 사용한다. 딥러닝의 Stochastic Gradient Descent처럼 데이터를 여러 번 샘플링하는 개념으로 볼 수 있다.

 

먼저, 관심있는 quantity를 random variable의 기댓값으로 표현한다.

${\mathbb{E}}_{x\sim P}[g(x)]=\sum _{x}g(x)P(x)$

 

Distribution $P$에서 기댓값의 입력으로 들어갈 $\{x^{(1)},\cdots ,x^{(T)}\}$ $T$개를 샘플링한 후, 다음 식을 사용하여 샘플들로부터 기댓값을 추정한다.

$\hat{g}(x^{(1)},\cdots ,x^{(T)})\triangleq \frac{1}{T}\sum _{t=1}^{T}g(x^t)$

여기서 sample들은 서로 독립적이며, $P$를 따른다.

 

큰 수의 법칙에 의해, $T\to \mathrm{\infty }$이면 $\hat{g}$는 ${\mathbb{E}}_P[g(x)]$에 수렴한다.

이렇게 근사하게 되면 두 가지 특징을 갖게 된다.

• Unbiased : ${\mathbb{E}}_P[\hat{g}]={\mathbb{E}}_P[g(x)]$
• Variance reduction : $V_P[\hat{g}]=V_P[\frac{1}{T}\sum _{t=1}^{T}g(x)]=\frac{V_P[g(x)]}{T}$

 

 

 

 

Monte Carlo Estimation and Maximum Likelihood

 

Biased coin을 던지는 sinvle variable 예시를 들어보자. 가능한 결과는 heads(H)나 tails(T)이고 ($x\in \{H,T\}$, dataset은 예를 들어 $\mathcal{D}=\{H,H,T,H,T\}$로 나왔다고 하자. 이 과정은 probability distribution $P_{\text{data}}(x)$을 따른다.

$x$에 대한 모든 probability distribution, 즉 가능한 model들의 집합을 $M$이라 할 때, $\mathcal{D}$에서 코인을 100번 던졌을 때 60번 앞면(head)일 확률 $P_{\theta }(x)$ $M$으로부터 어떻게 고를 수 있을까?

 

우선 $P_{\theta }(x=H)=\theta$, $P_{\theta }(x=T)=1-\theta$로 둔다. Example data $\mathcal{D}=\{H,H,T,H,T\}$이므로, 이 데이터에 대한 likelihood는 다음과 같이 나타낼 수 있다.

$L(\theta |\mathcal{D})={\theta }^3\cdot (1-\theta {)}^2$

여기서 log를 취하면 log-likelihood를 다음과 같이 구할 수 있다.

$\log L(\theta )=3\log (\theta )+2\log (1-\theta )$

 

Maximum likelihood estimation(MLE)의 목표는 $\log L({\theta }^{\ast })$를 최대로 하는 0과 1 사이의 최적의 $\theta$를 찾는 것이다.

 

이를 autoregressive representation에 적용시켜보자.

Training data $\mathcal{D}=\{{\mathbf{x}}^{(1)},\cdots ,{\mathbf{x}}^{(m)}\}$에 대해 다음과 같은 autoregressive model이 있다.

$P_{\theta }(x)=\prod _i^n{P}_{\text{neural}}(x_i|pa(x_i);{\theta }_i)$

 

여기서 MLE를 적용하려면, 우선 likelihood function을 분해(decompose)해야 한다.

$L(\theta |\mathcal{D})=\prod _{j=1}^m{P}_{\theta (x^{(j)})}=\prod _{j=1}^m\prod _{i=1}^n{P}_{\text{neural}}(x_i^{(j)}|pa(x_1{)}^{(j)};{\theta }_i)$

 

여기에 log를 취하면,

$\sum _{j=1}^m\sum _{i=1}^n\log P_{\text{neural}}(x_i^{(j)}|pa(x_1{)}^{(j)};{\theta }_i)$

 

이제 $\underset{\theta }{\mathrm{argmax}}\log L(\theta |\mathcal{D})$를 풀기위해 아래와 같이 optimize한다.

• Initialization : ${\theta }^{(0)}$을 랜덤하게 initialize
• Back propgation : ${\mathrm{\nabla }}_{\theta }\log L(\theta )$ 계산
• Weight update : ${\theta }^{(t+1)}={\theta }^t+{\alpha }_t{\mathrm{\nabla }}_{\theta }\log L(\theta )$

 

Weight update 과정을 수식으로 나타내면 다음과 같다.

${\mathrm{\nabla }}_{\theta }\log L(\theta )=\sum _{j=1}^m\sum _{i=1}^n{\mathrm{\nabla }}_{\theta }\log P_{\text{neural}}(x_i^{(j)}|pa{\left(x_i\right)}^{(j)};{\theta }_i)$

만약 $m=\left|D\right|$가 크다면,

$\begin{array}{rl}{\mathrm{\nabla }}_{\theta }\log L(\theta )& =m\sum _{j=1}^m\frac{1}{m}\sum _{i=1}^n{\mathrm{\nabla }}_{\theta }\log P_{\text{neural}}(x_i^{(j)}|pa{\left(x_i\right)}^{(j)};{\theta }_i)\\ & =m{\mathbb{E}}_{x^{(j)}\sim \mathcal{D}}[\sum _{i=1}^n{\mathrm{\nabla }}_{\theta }\log P_{\text{neural}}(x_i^{(j)}|pa{\left(x_i\right)}^{(j)};{\theta }_i)]\end{array}$

 

여기서 Monte Carlo estimation을 통해 다음과 같이 근사할 수 있다.

$\text{Sample }{x}^{(j)}\sim \mathcal{D};{\mathrm{\nabla }}_{\theta }\log L(\theta )=m\sum _{i=1}^n{\mathrm{\nabla }}_{\theta }\log P_{\text{neural}}(x_i^{(j)}|pa{\left(x_i\right)}^{(j)};{\theta }_i)$