6
$\begingroup$

I'm reading a paper (He, et al. 2010) that has used variational Bayesian inference to solve an inverse problem. I have difficulties deriving the relations for updating the variational approximations used in this problem.

Problem statement:

Suppose observed data $\boldsymbol{v}$ is yield by $$ \boldsymbol{v}=\boldsymbol{\Phi} \boldsymbol{\theta}+\boldsymbol{\epsilon} $$ where $\boldsymbol{\Phi}\in\mathbb{R}^{n\times N}$ is a random projection matrix, $\boldsymbol{\epsilon}\in\mathbb{R}^{n}$, and $\boldsymbol{\theta}\in\mathbb{R}^{N}$. Given noisy observation $\boldsymbol{v}\in\mathbb{R}^{n}$, we would like to recover the sparse signal $\boldsymbol{\theta}$.

Reconstruction method:

The noisy observations can be modeled as $$ \boldsymbol{v}\sim p(\boldsymbol{v} \mid \boldsymbol{\theta}, \alpha_{0}) = \mathcal{N}\left(\boldsymbol{\Phi} \boldsymbol{\theta}, \alpha_{0}^{-1} \boldsymbol{I}\right) $$ with $$ \alpha_{0} \sim \operatorname{Gamma}\left(a_{0}, b_{0}\right) $$ The spareness of $\boldsymbol{\theta}$ is modeled by $$ \boldsymbol{\theta}=\boldsymbol{w} \odot \boldsymbol{z}, \quad\text{with } w_{k, s, i} \sim \mathcal{N}\left(0, \alpha_{s}^{-1}\right), \quad z_{k, s, i} \sim \operatorname{Bernoulli}\left(\pi_{k, s, i}\right) $$ where $\odot$ is Hadamard product, with $$ \pi_{k, s, i}=\left\{\begin{array}{ll}\pi^{s}, & s=0,1 \\ \pi^{s 0}, & 2 \leq s \leq L, z_{p a(k, s, i)}=0 \\ \pi^{s 1}, & 2 \leq s \leq L, z_{p a(k, s, i)}=1\end{array}\right. $$

\begin{aligned} \alpha_{s} & \sim \operatorname{Gamma}\left(c_{0}, d_{0}\right), \quad 0 \leq s \leq L \\ \pi^{s} & \sim \operatorname{Beta}\left(e_{0}^{s}, f_{0}^{s}\right), s=0,1 \\ \pi^{s 0} & \sim \operatorname{Beta}\left(e_{0}^{s 0}, f_{0}^{s 0}\right) \\ \pi^{s 1} & \sim \operatorname{Beta}\left(e_{0}^{s 1}, f_{0}^{s 1}\right), 2 \leq s \leq L \end{aligned}

We use a set of distributions $q(\Theta)$, with $\Theta=\left\{\boldsymbol{w}, \boldsymbol{z}, \alpha_{0},\left\{\alpha_{s}\right\}_{s=0: L}, \pi^{0}, \pi^{1},\left\{\pi^{s 0}, \pi^{s 1}\right\}_{s=2: L}\right\}$, to approximate the posterior $p(\Theta|\boldsymbol{v})$. To this end, we derive a lower-bound $\mathcal{L}$ and maximize it until the model converges.

enter image description here

My question:

I'm having a hard time to understand the update equations for the posterior distributions. The paper present them as follows

$$ q\left(z_{k, s, i}\right)=\operatorname{Beronulli}\left(z_{k, s, i} \mid p_{k, s, i}\right) $$ $$ q\left(w_{k, s, i}\right)=\mathcal{N}\left(w_{k, s, i} \mid \mu_{k, s, i}, \sigma_{k, s, i}^{2}\right) $$ $$ q\left(\alpha_{0}\right)=\operatorname{Gamma}\left(\alpha_{0} \mid a, b\right) $$ $$ q\left(\alpha_{s}\right)=\operatorname{Gamma}\left(\alpha_{s} \mid c_{s}, d_{s}\right) $$ $$ q(\boldsymbol{\pi})=\prod_{s=0}^{1} \operatorname{Beta}\left(\pi^{s} \mid e^{s}, f^{s}\right) \prod_{s=2}^{L}\left[\operatorname{Beta}\left(\pi^{s 0} \mid e^{s 0}, f^{s 0}\right) \operatorname{Beta}\left(\pi^{s 1} \mid e^{s 1}, f^{s 1}\right)\right] $$ My understanding so far is that we had previously defined a set of prior distributions to model the problem. We choose a set of variational approximate posteriors $q$ and iteratively maximize a lower-bound on the log-likelihood (although, I thought it should be the marginal log-likelihood instead, but seems the paper is just stating log-likelihood) to update the $q$ and shape it into the posterior $p$. We choose $q$ similar to the prior model, with it's own parameters and update the parameters. For instance, paper states that $$ \sigma_{k, s, i}^{2}=\left(\left\langle\alpha_{s}\right\rangle+\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}^{2}\right\rangle \mathbf{\Phi}_{(j)}^{T} \mathbf{\Phi}_{(j)}\right)^{-1} $$ and $$ \mu_{k, s, i}=\sigma_{k, s, i}^{2}\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}\right\rangle \boldsymbol{\Phi}_{(j)}^{T}\left(\boldsymbol{v}-\sum_{l=1 \atop l \neq j}^{N} \boldsymbol{\Phi}_{(l)}\left\langle z_{(l)}\right\rangle\left\langle w_{(l)}\right\rangle\right) $$ I'm having a hard time seeing where the update equations are coming from.

My Attempt

I have used two approaches, but none got close to the relation above. One was to find a lower-bound by writing down the KL-distance between $q$ and $p$. The other is using Mean field approximation. Below I have detailed my attempts

Mean field approximation:

First, I'm not sure if this is the approach that the paper has taken, as it specifically states that it founds a lower bound. Nonetheless, here goes my attempt:

We write the joint probability of the variables as

$$ p\left(v, w, z, \alpha_{0}, \alpha_{s},\pi\right) = p\left(v \mid w, z, \alpha_{0}\right) p\left(\omega \mid \alpha_{s}\right) p(z \mid \pi) p\left(\alpha_{0}\right) p\left(\alpha_{S}\right) p(\pi) $$

\begin{align} \ln q^*(w) &= \mathbb{E}_{z, \alpha_{0}, \alpha_{s},\pi}[\ln p(v, w, z, \alpha_{0}, \alpha_{s},\pi)] + C\\ &=\mathbb{E}_{z, \alpha_{0}, \alpha_{s},\pi}[\ln p\left(v \mid w, z, \alpha_{0}\right) p\left(\omega \mid \alpha_{s}\right) p(z \mid \pi) p\left(\alpha_{0}\right) p\left(\alpha_{S}\right) p(\pi)] + C\\ &=\mathbb{E}_{z, \alpha_{0}, \alpha_{s},\pi}[\ln p\left(v \mid w, z, \alpha_{0}\right) p\left(\omega \mid \alpha_{s}\right)] + C_2\\ &=\mathbb{E}_{z, \alpha_{0}}[\ln p\left(v \mid w, z, \alpha_{0}\right)]+\mathbb{E}_{\alpha_{s}}[\ln p\left(\omega \mid \alpha_{s}\right)] + C_2 \end{align}

The way I understand it, this will lead to the probability density function for the normal distribution $ q\left(w_{k, s, i}\right)=\mathcal{N}\left(w_{k, s, i} \mid \mu_{k, s, i}, \sigma_{k, s, i}^{2}\right)$ and that way we find the update relations for the hyperparameters $\mu_{k, s, i}$ and $\sigma_{k, s, i}^{2}$.

\begin{align} \mathbb{E}_{z, \alpha_{0}}[\ln p\left(v \mid w, z, \alpha_{0}\right)]+\mathbb{E}_{\alpha_{s}}[ \ln p\left(\omega \mid \alpha_{s}\right)] =& \mathbb{E}_{z, \alpha_{0}}[\ln \mathcal{N}\left(\mathbf{\Phi} \boldsymbol{\theta}, \alpha_{0}^{-1} \boldsymbol{I}\right)]+\mathbb{E}_{\alpha_{s}}[\ln \mathcal{N}\left(0, \alpha_{s}^{-1}\right)]\\ =& \mathbb{E}_{z, \alpha_{0}}[\ln \mathcal{N}\left(\mathbf{\Phi} \boldsymbol{\theta}, \alpha_{0}^{-1} \boldsymbol{I}\right)]+\mathbb{E}_{\alpha_{s}}[\ln (\frac{1}{\sqrt{2\pi\alpha_s^{-1}}}\exp(\frac{-w^2}{2\alpha_s^{-1}}))]\\ =&\mathbb{E}_{z, \alpha_{0}}[\dots]+\mathbb{E}_{\alpha_{s}}[\ln(\sqrt{\alpha_s})-\ln(\sqrt{2\pi})-\frac{w^2}{2\alpha_s^{-1}}]\\ =&\mathbb{E}_{z, \alpha_{0}}[\ln((2 \pi)^{-\frac{n}{2}} \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})^{-\frac{1}{2}}\\ &\exp(-\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})))]\\ &+\mathbb{E}_{\alpha_{s}}[\frac12\ln(\alpha_s-2\pi)-\frac{w^2}{2\alpha_s^{-1}}]\\ =&\mathbb{E}_{z, \alpha_{0}}[-\frac{n}{2}\ln(2 \pi)-\frac{1}{2}\ln( \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I}))\\ &-\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})]\\ &+\mathbb{E}_{\alpha_{s}}[\frac12\ln(\alpha_s-2\pi)-\frac{w^2}{2\alpha_s^{-1}}]\\ =&-\mathbb{E}_{z, \alpha_{0}}[\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})]-\mathbb{E}_{\alpha_{s}}[\frac{w^2}{2\alpha_s^{-1}}]\\ &+\mathbb{E}_{\alpha_{s}}[\frac12\ln(\alpha_s-2\pi)]+\mathbb{E}_{z, \alpha_{0}}[-\frac{n}{2}\ln(2 \pi)-\frac{1}{2}\ln( \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I}))]\\ &+C\\ =&-\mathbb{E}_{z, \alpha_{0}}[\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})]-\mathbb{E}_{\alpha_{s}}[\frac{w^2}{2\alpha_s^{-1}}]+C_2 \end{align}

So I expect this derivation to be equivalent with plugging $\sigma_{k, s, i}^{2}$ and $\mu_{k, s, i}$ into $q\left(w_{k, s, i}\right)$. So I expect to get from the derivation above to

\begin{align*} q\left(w_{k, s, i}\right)=&\frac{1}{\sqrt{\left(\left\langle\alpha_{s}\right\rangle+\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}^{2}\right\rangle \mathbf{\Phi}_{(j)}^{T} \mathbf{\Phi}_{(j)}\right)^{-1}2 \pi}}\\ &\exp(-\frac{1}{2}\left(\frac{w_{k, s, i}-\left(\left\langle\alpha_{s}\right\rangle+\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}^{2}\right\rangle \mathbf{\Phi}_{(j)}^{T} \mathbf{\Phi}_{(j)}\right)^{-1}\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}\right\rangle \boldsymbol{\Phi}_{(j)}^{T}\left(\boldsymbol{v}-\sum_{l=1 \atop l \neq j}^{N} \boldsymbol{\Phi}_{(l)}\left\langle z_{(l)}\right\rangle\left\langle w_{(l)}\right\rangle\right)}{\sqrt{\left(\left\langle\alpha_{s}\right\rangle+\left\langle\alpha_{0}\right\rangle\left\langle z_{k, s, i}^{2}\right\rangle \mathbf{\Phi}_{(j)}^{T} \mathbf{\Phi}_{(j)}\right)^{-1}}}\right)^{2}) \end{align*} But I can't quite make the connection.

My 2nd Attempt

Based on the answer from @Microhaus, I've tried to find a lower-bound for $\sigma$

$$ L = \mathbb{E}_{q}[\ln p(\Theta, \mathbf{v})] - \mathbb{E}_q[\ln q(\boldsymbol{\pi}, \alpha_0, \left\{ \alpha_s \right\}_{s=0:L}, \mathbf{w} , \mathbf{z})] $$

Denoting those parts of the ELBO in which $\sigma_{k, s, i}$ appears as $L_{[\sigma_{k, s, i}]}$, we have:

\begin{align} L_{[\sigma_{k, s, i}]} =& \mathbb{E}_q[\ln(p(\mathbf{v} | \alpha_0, \mathbf{w}, \mathbf{z}])\\ &+ \mathbb{E}_q \left[\sum^L_{s=0} \sum^{I(s)}_{s=1} \sum^K_{k=1} \ln p\left(w_{k, s, i} \mid \alpha_{s}\right) \right]\\ &- \mathbb{E}_q \left[\sum^L_{s=0} \sum^{I(s)}_{s=1} \sum^K_{k=1} \ln q\left(w_{k, s, i} \mid \mu_{k, s, i}, \sigma_{k, s, i}^{2}\right) \right] \end{align}

For the $1$st expectation, we have:

\begin{align} \mathbb{E}_q[\ln(p(\mathbf{v} | \alpha_0, \mathbf{w}, \mathbf{z}])=& \mathbb{E}_q[\ln((2 \pi)^{-\frac{n}{2}} \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})^{-\frac{1}{2}}\\ &\exp(-\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})))]\\ =& \mathbb{E}_q[-\frac{n}{2}\ln(2 \pi)-\frac{1}{2}\ln \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})\\ &-\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})]\\ =& \mathbb{E}_q[-\frac{1}{2}\ln \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})-\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})] \end{align}

For the $2$nd expectation, we have:

\begin{align} \mathbb{E}_q \left[\ln p\left(w_{k, s, i} \mid \alpha_{s}\right) \right]=&\mathbb{E}_q \left[\ln \sqrt{\frac{\alpha_s}{ 2 \pi}} \exp(-\frac{1}{2}\alpha_s w^2_{k, s, i}) \right]\\ =&\mathbb{E}_q \left[\frac{1}{2}\ln\alpha_s -\frac{1}{2}\ln 2 \pi -\frac{1}{2}\alpha_s w^2_{k, s, i} \right]\\ =&\mathbb{E}_q \left[\frac{1}{2}\ln\alpha_s -\frac{1}{2}\alpha_s w^2_{k, s, i} \right] + C \end{align}

For the $3$rd expectation, we have:

\begin{align} \mathbb{E}_q \left[\ln q\left(w_{k, s, i} \mid \mu_{k, s, i}, \sigma_{k, s, i}^{2}\right) \right]=&\mathbb{E}_q \left[\ln \frac{1}{\sigma_{k, s, i} \sqrt{2 \pi}} \exp(-\frac{1}{2}\left(\frac{w_{k, s, i}-\mu_{k, s, i}}{\sigma_{k, s, i}}\right)^{2}) \right]\\ =&\mathbb{E}_q \left[-\ln\sigma_{k, s, i} -\frac{1}{2}\ln 2\pi -\frac{1}{2}\left(\frac{w_{k, s, i}-\mu_{k, s, i}}{\sigma_{k, s, i}}\right)^{2} \right]\\ =&\mathbb{E}_q \left[-\ln\sigma_{k, s, i} -\frac{1}{2}\left(\frac{w_{k, s, i}-\mu_{k, s, i}}{\sigma_{k, s, i}}\right)^{2} \right] + C \end{align}

By summing the expressions we find \begin{align} L_{[\sigma_{k, s, i}]} =& \mathbb{E}_q\left[-\frac{1}{2}\ln \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})\right]-\mathbb{E}_q\left[\frac{1}{2}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})\right]\\ &+ \mathbb{E}_q \left[\frac{1}{2}\ln\alpha_s\right] -\mathbb{E}_q \left[\frac{1}{2}\alpha_s w^2_{k, s, i} \right] + \mathbb{E}_q \left[-\ln\sigma_{k, s, i} \right]\\ &-\mathbb{E}_q \left[\frac{1}{2}\left(\frac{w_{k, s, i}-\mu_{k, s, i}}{\sigma_{k, s, i}}\right)^{2} \right] + C\\ =& -\frac{1}{2}\mathbb{E}_q\left[\ln \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})\right]-\frac{1}{2}\mathbb{E}_q\left[(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})\right]\\ &+ \frac{1}{2} \langle\ln\alpha_s\rangle -\frac{1}{2}\mathbb{E}_{q(\alpha_s)} \left[\alpha_s\right]\cdot \mathbb{E}_{q(w_{k, s, i}|\mu_{k, s, i}, \sigma^2_{k, s, i})} \left[(w_{k, s, i}|\mu_{k, s, i}, \sigma^2_{k, s, i})^2 \right] - \langle\ln\sigma_{k, s, i} \rangle\\ &-\frac{1}{2}\mathbb{E}_q \left[\left(\frac{w_{k, s, i}-\mu_{k, s, i}}{\sigma_{k, s, i}}\right)^{2} \right] + C\\ =& -\frac{1}{2}\mathbb{E}_q\left[\ln \operatorname{det}(\alpha_{0}^{-1} \boldsymbol{I})\right]-\frac{1}{2}\mathbb{E}_q\left[(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})^{\top} (\alpha_{0}^{-1} \boldsymbol{I})^{-1}(\boldsymbol{v}-\mathbf{\Phi} \boldsymbol{\theta})\right]\\ &+ \frac{1}{2} \langle\ln\alpha_s\rangle -\frac{1}{2} \langle\alpha_s\rangle\cdot \langle w_{k, s, i}^2 \rangle - \langle\ln\sigma_{k, s, i} \rangle\\ &-\frac{1}{2}\mathbb{E}_q \left[\frac{w^2_{k, s, i}+\mu^2_{k, s, i}-2 w_{k, s, i}\mu_{k, s, i}}{\sigma^2_{k, s, i}} \right] + C \end{align}

We find the partial derivative of the lower bond and solve $\frac{\partial}{\partial \sigma_{k,s,i}}L_{[\sigma_{k,s,i}]}=0$ to find the update relation for $\sigma_{k,s,i}$.

$\endgroup$
9
  • $\begingroup$ Is there a directed acyclic graph/plate notation representation of the model readily available? $\endgroup$
    – microhaus
    Jan 5 at 5:29
  • $\begingroup$ @microhaus added. $\endgroup$
    – Blade
    Jan 5 at 5:42
  • $\begingroup$ Perhaps you might consider using this diagram to specify: (i) the log of the joint distribution over all your variables of interest (circles), conditioned on the parameters (diamonds). Then use the variational distributions you've defined and take the (ii) the log of the variational distribution over all variables of interest conditioned on the variational parameters, having made the mean-field assumption. Your ELBO is then the difference between the expectation of (i) and the expectation of (ii), where expectations are w.r.t. to the product of variational distributions. $\endgroup$
    – microhaus
    Jan 5 at 6:10
  • 1
    $\begingroup$ I'm going to write up a brief stab I had at this. It will be rough and far from a final answer (there are details such as indexing and dimensionality that need to be tweaked which I cannot do without having read the paper). However, it may more clearly convey to you what I had in mind when I wrote the comments. $\endgroup$
    – microhaus
    Jan 5 at 18:16
  • 1
    $\begingroup$ Yes, the general strategy you have implemented in your 2nd attempt to derive $\sigma_{k,s,i}$ is sound. However, I cannot yet comment on the accuracy of the algebra. $\endgroup$
    – microhaus
    Jan 6 at 18:03
5
+50
$\begingroup$

Joint distribution.

Using the graphical model you provided, we get the following joint distribution over all variables of interest, conditioning on model parameters.

$$p(\Theta, \mathbf{v} | a_0, b_0, c_0, d_0, \left\{e_0^s, f_0^s \right\}_{s = 0,1}, \left \{ e_0^{s0}, f_0^{s0}, e_0^{s1}, f_0^{s1} \right\}_{s=2:L})$$

In more detail, this gives the provisional joint distribution:

$$\begin{align} p(\Theta, \mathbf{v}) = p(\alpha_0 | a_0, b_0) p(\mathbf{v} | \alpha_0 \mathbf{w}, \mathbf{z}) \prod^L_{s=0} \left \{ p(a_s | c_0, d_0) p(\pi^s | e_0^s, f_0^s) p(\pi^{s0} | e_0^{s0}, f_0^{s0}) p(\pi^{s1} | e_0^{s1}, f_0^{s1}) \prod^{I(s)}_{i=1} \prod^K_{k=1} p(z_{k, s, i} | \pi^s, \pi^{s0}, \pi^{s1}, {z_{pa(k, s, i)}}) p(w_{k,s,i} | \alpha_s) \right\} \tag{1} \\ \end{align}$$

Now the above is rough - you will need to tweak the $s$-indexing on $\pi^s, \pi^{s0}, \pi^{s1}$ over which $\prod^L_{s}$ operates to better comply with the written details, and I'm not entirely sure about what is going on with $z_{pa(k, s, i)}$, which is dotted in the plate notation.

Variational distribution.

Now the variational distribution on all latent variables of interest is specified by the following, with conditioning on the variational parameters:

$$q \left(\boldsymbol{\pi}, \alpha_0, \{ \alpha_s \}_{s=0:L}, \mathbf{w} , \mathbf{z} \space | \space a, b, \{c_s, d_s \}_{s=0:L},\{e^s, f^s \}_{s = 0,1}, \{ e^{s0}, f^{s0}, e^{s1}, f^{s1} \}_{s=2:L}, \{ \mu_{k, s, i}, \sigma^2_{k,s,i}, p_{k,s,i} \}_{s=0:L, i=1:I(s), k=1:K} \right) \\ $$

We then have:

$$q(\boldsymbol{\pi}, \alpha_0, \left\{ \alpha_s \right\}_{s=0:L}, \mathbf{w} , \mathbf{z}) = q(\alpha_0 | a, b)q \left(\boldsymbol{\pi} | \left\{e^s, f^s \right\}_{s = 0,1},\left \{e^{s0}, f^{s0}, e^{s1}, f^{s1} \right\}_{s=2:L} \right) \prod^L_{s=0} \left \{ q(\alpha_s | c_s, d_s) \prod^{I(s)}_{i=1} \prod^K_{k=1} q(w_{k,s,i} | \mu_{k,s,i}, \sigma^2_{k, s, i}) q(z_{k, s, i} | p_{k, s, i}) \right\} \tag{2} $$

The mean-field approximation implies that we can specify the variational distribution $q(\boldsymbol{\pi}, ..., \mathbf{z})$ as a product of individual variational distributions as we have done so above - and it can be thought of as an independence assumption between latent variables specified.

Evidence Lower Bound (ELBO).

Consider computing the log-marginal likelihood of the observed data $\mathbf{v}$, that is, $\ln p(\mathbf{v} | a_0, ..., \left \{ e_0^{s0}, f_0^{s0}, e_0^{s1}, f_0^{s1} \right\}_{s=2:L})$. As computing this exactly is likely intractable (hence the need for approximate inference methods such as MCMC/variational inference), we instead consider a lower bound on the log-marginal likelihood, known as the evidence lower bound (ELBO). Writing the log-marginal likelihood as the log of the joint likelihood having integrated/summed out all the latent variables $\Theta$, we have:

$$\begin{align}\ln p(\mathbf{v} | ...) &= \ln \int p(\Theta, \mathbf{v}) | ...) d\Theta \\ &= \ln \int q(\boldsymbol{\pi}, ..., \mathbf{z}) \cdot \frac{p(\Theta, \mathbf{v})}{q(\boldsymbol{\pi}, ..., \mathbf{z})} d \Theta \\ &= \ln \mathbb{E}_{q(\boldsymbol{\pi}, ..., \mathbf{z})}\left[\frac{p(\Theta, \mathbf{v})}{q(\boldsymbol{\pi}, ..., \mathbf{z})} \right] \\ &\geq \mathbb{E}_q \left[\ln \frac{p(\Theta, \mathbf{v})}{q(\boldsymbol{\pi}, ..., \mathbf{z})} \right] \\ &= \mathbb{E}_q[ \ln p(\Theta, \mathbf{v})] - \mathbb{E}_q[\ln q(\boldsymbol{\pi}, ..., \mathbf{z})] \end{align}$$

Where I have used the notation $\int d\Theta$ as shorthand for the appropriate combination of multiple integrals/summations associated with the continuous/discrete latent variables in $\Theta$. The reasoning in going from the 3rd to the 4th line is that $g(u) = \ln(u)$ is a concave function, so by Jensen's inequality, we have $\ln \mathbb{E}_q[U] \geq \mathbb{E}_q[\ln (U)]$.

Hence the ELBO, which I from hereon denote $L$, will be the following:

$$L = \mathbb{E}_{q}[\ln p(\Theta, \mathbf{v})] - \mathbb{E}_q[\ln q(\boldsymbol{\pi}, \alpha_0, \left\{ \alpha_s \right\}_{s=0:L}, \mathbf{w} , \mathbf{z})] \tag{3} $$

Where both expectations are taken with respect to $q(\boldsymbol{\pi}, \alpha_0, \left\{ \alpha_s \right\}_{s=0:L}, \mathbf{w} , \mathbf{z})$.

The entire ELBO is computed by substituting $(1)$ and $(2)$ into $(3)$. You will additionally need to insert the specific functional forms of the model probability distributions e.g. $p(\alpha_0 | a_0, b_0) = \text{Gamma}(\alpha_0 | a_0, b_0) = \frac{1}{b_0^{a_0} \Gamma(a_0)} \alpha_0^{a_0 - 1} e^{-\alpha_0 / b_0}$ and variational distributions e.g. $q(w_{k, s, i} | \mu_{k, s, i}, \sigma^2_{k, s, i}) = \mathcal{N}(w_{k, s, i} | \mu_{k, s, i}, \sigma^2_{k, s, i})$ etc.

This is something that will require at least a few pages of algebra to fully derive.

If you want to derive all the update equations, you will need to plug-in the functional forms of all the distributions specified by the model, and the all variational distributions.

Towards updates for $p_{k,s,i}$. (needs work on details of $(*)$).

In order to get update equations we need to maximise the ELBO, $L$ with respect to the variational parameters of interest, one of which is $p_{k,s,i}$.

As the ELBO is cumbersome to write out in full, and we are currently only interested in updates on $p_{k, s, i}$, we selectively specify the parts of the ELBO we need.

Now the only way in which the variational parameter $p_{k, s, i}$ of the variational Bernoulli on $z_{k, s, i}$ can appear in the ELBO is when we compute $\mathbb{E}_q[\ln f(z_{k, s, i})]$, that is expectations of log terms containing $z_{k,s,i}$ as arguments (where $\ln f(z_{k,s,i})$ may be log-model-probabilities of the form $\ln p(\cdot)$ or log-variational probabilities of the form $\ln q(\cdot)$).

To that end, we need to isolate terms in $(3)$ containing $z_{k,s,i}$. The only terms that will contain $z_{k,s,i}$ in $(3)$ are $\mathbb{E}_q[\ln p(\mathbf{v} | \alpha_0 , \mathbf{w}, \mathbf{z})]$, $\mathbb{E}_q[\sum_s \sum_i \sum_k \ln p(z_{k,s,i} | \pi^s ... z_{pa(k,s,i)}]$, and $\mathbb{E}_q[\sum_s \sum_i \sum_k \ln q(z_{k,s,i} | p_{k,s,i})]$.

We denote those parts of the ELBO in which the variational parameter $p_{k, s, i}$ will appear as $L_{[p_{k, s, i}]}$. Yielding:

$$L_{[p_{k, s, i}]} = \underbrace{\mathbb{E}_q[\ln(p(\mathbf{v} | \alpha_0, \mathbf{w}, \mathbf{z}])}_{(*)} + \mathbb{E}_q \left[\sum^L_{s=0} \sum^{I(s)}_{s=1} \sum^K_{k=1} \ln p(z_{k, s, i} | \pi^s, \pi^{s0}, \pi^{s1}, z_{pa(k, s, i)})\right] - \mathbb{E}_q \left[\sum^L_{s=0} \sum^{I(s)}_{s=1} \sum^K_{k=1} \ln q(z_{k, s, i} | p_{k, s, i}) \right]$$

Now I have managed to squeeze out something vaguely sensible resembling the contribution of the 1st expectation $(*)$ to the update but it's not quite there yet. But here is what you do for the 2nd and 3rd expectation.

For the 2nd expectation, we have:

$$\begin{align} \mathbb{E}_q[\ln p(z_{k, s, i} | \pi_{k, s, i})] = &\space \mathbb{E}_q[\ln ({\pi_{k, s, i}}^{z_{k, s, i}} (1 - \pi_{k, s, i})^{1 - z_{k, s, i}} ]\\ = &\space \mathbb{E}_q[z_{k, s, i} \ln \pi_{k, s, i} + (1 - z_{k,s,i}) \ln (1 - \pi_{k, s, i})] \\ = &\space \mathbb{E}_{q(z_{k, s, i} | p_{k, s, i})}[z_{k, s, i} | p_{k,s, i}] \cdot \mathbb{E}_{q(\pi_{k, s, i})}[\ln \pi_{k, s, i} ] \\ &+ \mathbb{E}_{q(z_{k, s, i} | p_{k, s, i})}[1- z_{k, s, i} | p_{k,s, i}] \cdot \mathbb{E}_{q(\pi_{k, s, i})}[\ln 1- \pi_{k, s, i} ] \\ = &\space p_{k,s,i} \langle\ln \pi_{k, s, i} \rangle + (1 - p_{k, s, i}) \langle\ln (1 - \pi_{k, s, i}) \rangle \end{align}$$

Where in the 3rd equality we have used the fact that the expectation of the product of $z_{k, s, i}$ and $\ln \pi_{k, s, i}$ is the product of expectations - this is because of the mean-field assumption, they are independent once we have conditioned on our variational parameters $p_{k, s, i}$ on $z_{k, s, i}$ and $e^s, f^s, e^{s0}, f^{s0}, e^{s1}, f^{s1}$ on $ \pi_{k,s,i}$.

For the 3rd expectation, we have:

$$\begin{align} \mathbb{E}_q[\ln q(z_{k, s, i} | p_{k, s, i})] &= \mathbb{E}_q[z_{k, s, i} \ln p_{k, s, i} + (1 - z_{k,s,i}) \ln (1 - p_{k, s, i})] \\ &= \mathbb{E}_{q(z_{k, s, i} | p_{k, s, i})}[z_{k, s, i} | p_{k,s, i}] \ln p_{k, s, i} + \mathbb{E}_{q(z_{k, s, i} | p_{k, s, i})}[1- z_{k, s, i} | p_{k,s, i}] \ln (1- \pi_{k, s, i}) \\ &= p_{k, s, i} \ln p_{k, s, i} + (1 - p_{k, s, i}) \ln (1 - p_{k, s,i}) \end{align}$$

Putting this all together, with $(*)$ to be completed, we have:

\begin{align}L_{[p_{k,s,i}]} =& \underbrace{\mathbb{E}_q[\ln(p(\mathbf{v} | \alpha_0, \mathbf{w}, \mathbf{z}])}_{(*)} \\ &+ p_{k,s,i} \langle\ln \pi_{k, s, i} \rangle + (1 - p_{k, s, i}) \langle\ln (1 - \pi_{k, s, i}) \rangle \\ &- p_{k, s, i} \ln p_{k, s, i} - (1 - p_{k, s, i}) \ln (1 - p_{k, s,i}) \end{align}

After simplifying $(*)$, which I can't quite get exactly, you then maximise w.r.t $p_{k, s, i}$ by computing partial derivatives. After collecting terms, you then rearrange for $p_{k, s, i}$ to get your update equation.

You should now be able to see how it is we get the $exp$ and $\langle \ln \pi_{k, s, i} \rangle$ terms in the update equation for $p_{k, s, i}$.

To derive the rest of the update equations, you need to follow a similar strategy for each variational parameter.


Addressing the 1st expectation $(*)$.

Here is the working for the 1st expectation which I can't quite complete, as I don't have the context-specific knowledge (of the paper) to appropriately deal with the dimensionality of $\mathbf{z}$ and $\mathbf{w}$. I will go as far as I can before stating the specifics that prevent me from proceeding further. Perhaps you can assist on that front.

$$\begin{align} \mathbb{E}_q[\ln p(\mathbf{v} | \alpha_0, \mathbf{w}, \mathbf{z})] = &\space \mathbb{E}_q \left[\ln \frac{1}{(2 \pi)^{n/2} | \alpha_0^{-1} \mathbf{I} |^{1/2}} \exp \left( -\frac{1}{2}(\mathbf{v} - \boldsymbol{\Phi} \boldsymbol{\theta})^T(\alpha_0^{-1} \mathbf{I})^{-1}(\mathbf{v} - \boldsymbol{\Phi} \boldsymbol{\theta}) \right) \right] \\ = &\space \mathbb{E}_q\left[-\frac{\alpha_0}{2} (\mathbf{v}^T\mathbf{v} - 2 \mathbf{v}^T \boldsymbol{\Phi} \boldsymbol{\theta} + \boldsymbol{\theta}^T \boldsymbol{\Phi}^T \boldsymbol{\Phi} \boldsymbol{\theta}) - \frac{1}{2} \ln((2 \pi)^n |a_0^{-1} \mathbf{I}|) \ \right] \\ = &\space \mathbb{E}_q\left[-\frac{\alpha_0}{2} (\mathbf{v}^T\mathbf{v} - 2 \mathbf{v}^T \boldsymbol{\Phi} (\mathbf{w} \odot \mathbf{z}) + (\mathbf{w} \odot \mathbf{z})^T \boldsymbol{\Phi}^T \boldsymbol{\Phi} (\mathbf{w} \odot \mathbf{z})) - \frac{n}{2} \ln(2 \pi) - \frac{n}{2} \ln (\alpha_0) \right] \\ = &\space -\frac{\langle a_0 \rangle}{2} (\mathbf{v}^T\mathbf{v} -2 \mathbf{v}^T \boldsymbol{\Phi} (\langle \mathbf{w} \rangle \odot \langle \mathbf{z} \rangle) + (\langle \mathbf{w} \rangle^T \odot \langle \mathbf{z} \rangle^T) \boldsymbol{\Phi}^T \boldsymbol{\Phi} (\langle \mathbf{w} \rangle \odot \langle \mathbf{z} \rangle) \\ &\space- \frac{n}{2} \ln(2 \pi) - \frac{n}{2} \langle \ln(\alpha_0)\rangle \\ = &\space -\frac{\langle a_0 \rangle}{2} (\mathbf{v}^T\mathbf{v} -2 \mathbf{v}^T \boldsymbol{\Phi} (\langle \mathbf{w} \rangle \odot \mathbf{p}) + (\langle \mathbf{w} \rangle^T \odot \mathbf{p}^T) \boldsymbol{\Phi}^T \boldsymbol{\Phi} (\langle \mathbf{w} \rangle \odot \mathbf{p} ) \\ &\space- \frac{n}{2} \ln(2 \pi) - \frac{n}{2} \langle \ln(\alpha_0)\rangle \\ \end{align}$$

Where in going from the 2nd equality to 3rd quality I have used the fact that the determinant of a diagonal matrix is a product of its entries. In going from the 3rd equality to 4th equality, I have treated $\mathbf{v}$ and $\mathbf{\Phi}$ as constants - they do not appear in the variational distribution over which you are taking expectations. The expectations $\langle \alpha_0 \rangle$ and $\langle \ln( \alpha_0 ) \rangle$ with respect to the variational distribution $q(\alpha_0 | a, b)$; the expectations $\langle \mathbf{w} \rangle$ and $\langle \mathbf{z} \rangle$ are with respect to $\prod_s \prod_i \prod_k q (w_{k, s, i} | \mu_{k,s,i}, \sigma^2_{k, s, i})$ and $\prod_s \prod_i \prod_k q (z_{k, s, i} | p_{k,s,i})$. And I have again used the mean-field approximation to justify the expectation of a product of these latent variables under the variational distribution as being the product of expectations.

For the purposes of computing update equations with respect to $p_{k, s, i}$, this final equality should be viewed with a focus on all terms containing $p_{k, s, i}$. Now what I've isolated as preventing me from going further with this is details concerning the dimensionality of $\mathbf{w}$, $\mathbf{z}$, and what I've denoted as $\mathbf{p}$. In going from the 4th to 5th equality, I have written $\langle \mathbf{z} \rangle = \mathbf{p}$ to convey the fact that $\langle z_{k, s, i} \rangle = p_{k, s, i}$, which allows me to defer specifying details about how the dimensionality/indexing of this works.

You will notice that the update equation on $p_{k, s, i}$ in the paper is much more precise concerning how this dimensionality is treated, and that is something I will not be able to assist on without more intimate knowledge of the paper.

In particular, the paper states under "B. Tree-Structured Bayesian Compressive Sensing" that "$\mathbf{w} \in \mathbb{R}^N$ and $\mathbf{z} \in \mathbb{R}^N$", and that "$w_i \sim \mathcal{N}(0, \alpha_i^{-1})$ and $z_i \sim \text{Bernoulli}(\pi_i)$". However, the model and variational distribution specifies that $w_{k, s, i}$, $z_{k, s, i}$ and $p_{k, s, i}$ are indexed by $k, s, i$, and not just $i$.

Hence what needs to be accounted for to get the precise update equation on $p_{k,s,i}$, is how the "block" indexing $k = 1, ..., K$ and "level" indexing $s = 1,..., L$ are treated.

$\endgroup$
9
  • $\begingroup$ Thank you. Quick question: Where does the ELBO, in the form that you wrote down, come from? Is there a reference that I can look at? $\endgroup$
    – Blade
    Jan 5 at 23:20
  • $\begingroup$ Just to be absolutely clear, are you asking how to derive the ELBO conceptually in terms of model joint probabilities and variational distributions, or are you asking how I wrote down the ELBO containing terms that will contain the variational parameter $p_{k,s,i}$ after having taken expectations (what I have denoted as $L_{[p_{k,s,i}]}$? $\endgroup$
    – microhaus
    Jan 6 at 0:31
  • $\begingroup$ I haven't used any references per se, but used the experience I gleaned having studied variational inference very generally. I essentially used a similar strategy for doing variational inference as the one used in "Latent Dirichlet Allocation" by Blei, Ng, Jordan - the principles are the same. It may be instructive to peek at it to see, as the authors show you how to derive updates on the variational parameters quite clearly, from which you can extrapolate a strategy that better fits with your own contextual knowledge of the paper you referenced. $\endgroup$
    – microhaus
    Jan 6 at 0:37
  • $\begingroup$ However, it may be the case that some of the references in the paper you linked may contain someone who has already used variational inference on your problem. In particular, the paper from which you took the picture of the plate notation? $\endgroup$
    – microhaus
    Jan 6 at 0:39
  • 1
    $\begingroup$ @Blade Not a problem at all - as someone who has done self-study in machine learning, I know just how demoralising it can feel playing "fill in the gaps" in the "jungle" of papers where the authors aren't sufficiently precise or explicit, especially when you do not have an instructor to assist. I hope you manage to reconcile your working with the update equations, and as I have stated, that requires knuckling down on the dimensionality issues I've outlined. If it's taking excessive time and you aren't getting anywhere, do consider posting a further question, or emailing the authors themselves. $\endgroup$
    – microhaus
    Jan 10 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.