Variational Bayesian Inference with Stochastic Search ( 2012 )
Abstract
MFVI는 full posterior distribution을 근사한다. 이를 풀때, log joint likelihood의 sum을 integrate해야 하지만, 이는 주로 closed-form형태로 존재하지 않기 **때문에, **ELBO를 사용해서 풀어야한다.
이 논문의 핵심
- stochastic optimization방법을 사용하여, ELBO를 direct하게 optimize!
- control variate를 사용하여 stochastic gradient의 variance를 줄인다
1. Introduction
빠른 복습!
minimize KL-divergence = maximize ELBO
- \(\Theta=\left\{\theta_{i}\right\}\): latent variables
- \(X\) = data
- \(P(X, \Theta \mid \Upsilon)\) = joint likelihood of \(X\) and \(\Theta\)
- \(\Upsilon\) = set of hyperparameters
VI 는\(Q\)를 사용해서 \(P(\Theta \mid X, \Upsilon)\) 를 근사하는 것을 목표로 하며,
그러기 위해 아래의 objective function ELBO를 최대화한다.
\[\mathcal{L}(X, \Psi)=\mathbb{E}_{Q}[\ln P(X, \Theta \mid \Upsilon)]+\mathbb{H}[Q(\Theta \mid \Psi)]\]하지만 앞서 말했듯, MFVI는 closed form형태로 풀지 못하는 경우가 많다.
( log of the joint likelihood term 때문에)
solution : problematic function을 (point-wise lower bound인) 다른 function으로 대체!
\(\rightarrow\) 따라서 해당 lower bound를 tight하게 만드는 것이 핵심!
이 논문은 \(\mathcal{L}(X, \Psi)\)를 directly optimize하는 방법을 제안한다.
\(\rightarrow\) “stochastic approximation of \(\nabla_{\psi_{i}} \mathcal{L}\)“
이 stochastic approximation은 MC integration에 기반한다. 필요한 sample 수는 이 approximation의 variance에 따르기 때문에, control variate를 도입하여 variance를 줄이는 방법도 제안한다.
뒤에서 자세히 이야기 하겠지만, control variate는 tractable한 function \(g\)로써, 문제가 되는 우리의 intractable한 function \(f\)와 highly correlated되어 있는 함수이다.
우리는 위의 \(\mathcal{L}(X, \Psi)=\mathbb{E}_{Q}[\ln P(X, \Theta \mid \Upsilon)]+\mathbb{H}[Q(\Theta \mid \Psi)]\)식에서 \(f\)대신 \(g\)를 사용해서 계산 하고, 이에 따른 bias는 stochastically corrected 된다.
control variate의 ex)
-
Taylor expansion 2차 근사
( 좋은 approximation이면서도, closed-form형태로 존재한다! )
2. MFVI
다음과 같이 factorize : \(Q(\Theta \mid \Psi)=\prod_{i} q_{i}\left(\theta_{i} \mid \psi_{i}\right)\)
ELBO :
\(\begin{aligned}\ln P(X \mid \Upsilon)&=\ln \int_{\Theta} P(X, \Theta \mid \Upsilon) d \Theta\\ &\geq \int_{\Theta} Q(\Theta \mid \Psi) \ln \frac{P(X, \Theta \mid \Upsilon)}{Q(\Theta \mid \Psi)} d \Theta \end{aligned}\).
\(\ln P(X, \Theta \mid \Upsilon)=\quad \sum_{j} f_{j}\left(X_{A_{j}}, \Theta_{B_{j}}\right)\).
ELBO를 정리하면, 아래와 같이 나타낼 수 있다.
\[\mathcal{L}=\sum_{j} \mathbb{E}_{Q}\left[f_{j}\left(X_{A_{j}}, \Theta_{B_{j}}\right)\right]+\sum_{i} \mathbb{H}\left[q_{i}\left(\theta_{i} \mid \psi_{i}\right)\right]\]위 ELBO가 intractable할 경우?
$\rightarrow$ \(g\left(\theta_{i}, \xi\right)\)를 도입하여 \(f_{j}\)를 대체하는 방법이 있다 ( 여기서 \(f_{j}\left(\theta_{i}\right) \geq g\left(\theta_{i}, \xi\right)\) )
새로 도입한 함수 \(g\)는 auxiliary variable \(\xi\)를 가지고 있는데, 이는 \(g\)가 \(f\)를 얼마나 tight하게 근사하는지를 나타내는 variable이다.
3. Stochastic search Variational Bayes
이 논문에서는 ELBO를 direct하게 optimize하기 위한 stochastic search 방법에 대해서 설명한다.
( 2에서 MVFI의 문제를 해결하기 위해 $g$를 도입한 indirect한 방법과는 다르게, directly optimize! )
\(f\) : \(\theta\)에 대한 intractable 함수 ( 편의를 위해 indices 생략 )
( \(\theta\)는 \(\phi\)를 parameter로 가지는 variational distribution \(q\)를 따른다 )
Lower bound를 다음과 같이 2개의 부분으로 나눈다
( intractable한 \(\mathbf{E}f\) & tractable한 \(h\) )
Gradient of ELBO : \(\nabla_{\psi} \mathcal{L}=\nabla_{\psi} \mathbb{E}_{q}[f(\theta)]+\nabla_{\psi} h(X, \Psi)\)
위 식에서, intractable한 1번째 term은 log-derivative trick를 사용하여 아래와 같이 풀 수 있다.
\(\begin{aligned} \nabla_{\psi} \mathbb{E}_{q}[f(\theta)] &=\nabla_{\psi} \int_{\theta} f(\theta) q(\theta \mid \psi) d \theta \\ &=\int_{\theta} f(\theta) \nabla_{\psi} q(\theta \mid \psi) d \theta \\ &=\int_{\theta} f(\theta) q(\theta \mid \psi) \nabla_{\psi} \ln q(\theta \mid \psi) d \theta . \end{aligned}\).
그런 뒤, MC Integration을 사용하여 아래와 같이 근사할 수 있다.
\(\nabla_{\psi} \mathbb{E}_{q}[f(\theta)] \approx \frac{1}{S} \sum_{s=1}^{S} f\left(\theta^{(s)}\right) \nabla_{\psi} \ln q\left(\theta^{(s)} \mid \psi\right)\).
where \(\theta^{(s)} \stackrel{i i d}{\sim} q(\theta \mid \psi)\)
( 앞으로 \(\nabla_{\psi} \mathbb{E}_{q}[f(\theta)]\) 를 위에서 근사한 unbiased stochastic approximation으로 사용할 것이고, 이를 \(\zeta\)로 표기할 것이다.)
따라서, 매 gradient step마다의 updating equation은 아래와 같이 나타낼 수 있다.
\(\psi^{(t+1)}=\psi^{(t)}+\rho_{t} \nabla_{\psi} h\left(X, \Psi^{(t)}\right)+\rho_{t} \zeta_{t}\).
4. Searching with control variates
위에서 구한 gradient approximation의 variance는 현실에서 매우 클 수 있다.
이 값이 클 경우, 더 많은 sample수가 필요 하고, 이는 결국 알고리즘의 속도 저하로 이어진다. 따라서 우리는 “variance reduction”을 해야하는데, 이를 위해 control variate를 도입한다.
control variate는 다음과 같은 두 가지 특징이 있다
- highly correlated with an intractable variable
- expectation is tractable
4-1. A control variate for \(f(\theta)\)
variance reduction의 개요
- expectation은 그대로
- variance는 감소!
\(f(\theta)\)를 근사하는 control variate \(g(\theta)\)를 도입한다
( \(g\)는 \(q\)의 expectation 하에서 closed-form을 띈다 )
우리는 이를 사용하여 새로운 function \(\hat{f}\)를 아래와 같이 설계한다.
\(\hat{f}(\theta)=f(\theta)-a\left(g(\theta)-\mathbb{E}_{q}[g(\theta)]\right)\).
여기서 \(a\)는 \(\hat{f}\)의 variance를 minimize하도록 잡아야 하며, 이는 아래와 같다.
\(a=\frac{\operatorname{Cov}(f, g)}{\operatorname{Var}(g)}\).
하지만, 위 \(a\)식의 covariance와 variance는 모두 unknown이기 때문에, 우리는 sample variance/covariance를 계산하여 대신 대입한다.
이로 인한 variance의 감소분은 아래와 같다.
\(\operatorname{Var}(\hat{f}) / \operatorname{Var}(f)=1-\operatorname{Corr}(f, g)^{2}\).
위 식에서 알 수 있듯, \(f\)와 \(g\)사이의 상관관계가 높을 수록, 우리는 더 큰 variance reduction의 효과를 볼 수 있다!
요약) “variance가 reduced된 stochastic gradient”식은 아래와 같다.
\(\begin{aligned} \nabla_{\psi} \mathbb{E}_{q}[\hat{f}(\theta)] & \approx \hat{a} \nabla_{\psi} \mathbb{E}_{q}[g(\theta)] +\frac{1}{S} \sum_{s=1}^{S}\left\{f\left(\theta^{(s)}\right)-\hat{a} g\left(\theta^{(s)}\right)\right\} \nabla_{\psi} \ln q\left(\theta^{(s)} \mid \psi\right) \end{aligned}\).
where \(\theta^{(s)} \stackrel{\text { iid }}{\sim} q(\theta \mid \psi)\) for \(s=1, \ldots, S\)
4.2 The stochastic search case
위에서 우리가 한 것은 \(g(\theta)\)를 사용하여 \(f(\theta)\)를 나타냈다.
하지만 우리가 진짜 minimize하고 싶은 대상은 \(f(\theta) \nabla_{\psi} \ln q(\theta \mid \psi)\)의 variance이기 때문에,
\(f(\theta) \nabla_{\psi} \ln q(\theta \mid \psi)\)를 \(g(\theta) \nabla_{\psi} \ln q(\theta \mid \psi)\)를 사용하여 대체하면 된다.
이 때의 최적의 \(a\)는 아래와 같다.
\(a=\sum_{k} \operatorname{Cov}\left(f \frac{\partial \ln q}{\partial \psi_{k}}, g \frac{\partial \ln q}{\partial \psi_{k}}\right) / \sum_{k} \operatorname{Var}\left(g \frac{\partial \ln q}{\partial \psi_{k}}\right)\).
Algorithm Summary
