为什么贝叶斯统计中后验分布（posterior distortion）没有闭式解，以及变分推断的形式

参考：
StackExchange
Variational Inference: A Review for Statisticians

这个问题是变分推断(variational inference)的一个基础问题。很奇怪的是，我没有在中文社区发现这个问题的详细解释。一句话总结，如果求解过程出现了不可约掉的积分，该过程就是不可直接计算的（intractable），或者说没有闭式解。而机器学习所有解决该问题的办法，就是巧妙地去掉积分。
下面通过一个例子，来解释这个问题。

问题描述

符号定义： $\textbf{x}=x_{1:n}$ 表示观察变量， $\textbf{z}=z_{1:m}$ 表示隐变量，它们的联合概率密度为 $p(\textbf{x}, \textbf{z})$ 。
目标：求解条件概率 $p(\textbf{z}|\textbf{x})$ 。在贝叶斯框架下，这一过程叫做推断，而 $p(\textbf{z}|\textbf{x})$ 叫做后验概率。
后验概率密度：
$p(\textbf{z}|\textbf{x})=\frac{p(\textbf{z}, \textbf{x})}{p(\textbf{x})}=\frac{p(\textbf{z}, \textbf{x})}{\int p(\textbf{z}, \textbf{x})d\textbf{z}}$
其中 $p(\textbf{x})$ 被称为“证据”（evidence）
下面的例子用来说明，证据的积分形式通常没有闭式解。

例子：混合高斯模型的后验概率估计

设有 $K$ 个混合分支，分支的均值集合为 $\mathbf{\mu}=\{\mu_1,...,\mu_K\}$ ，这些均值服从高斯分布 $\mathcal{N}(0,\sigma^2)$ ，其中参数 $\sigma^2$ 表示方差。采样 $K$ 次得到 $\mathbf{\mu}$ 。
每个观察数据 $x_i$ 的产生过程如下：从类别 ${1,...,K}$ 中选出一个分支，记为 $c_i$ ，其数学形式为one-hot（一个长为 $K$ 的向量，其中一位是1，其余位是0）。从（另一个）高斯分布 $\mathcal{N}({c_i}^T\mu,1)$ 采样，得到 $x_i$ 。连续采样n次。
即：
$\mu_k \sim \mathcal{N}(0,\sigma^2),其中k=1,...,K$
$c_i \sim Categorical(\frac{1}{K},...,\frac{1}{K}),其中i=1,...,n$
$x_i|c_i,\mu \sim \mathcal{N}({c_i}^T\mu,1),其中i=1,...,n$
联合概率密度为：
$p(\mathbf{\mu},\textbf{c},\textbf{x})=p(\mathbf{\mu})\prod_{i=1}^{n}p(c_i)p(x_i|c_i,\mathbf{\mu})$
隐变量 $\mathbf{z}=\{\mathbf{\mu},\mathbf{c}\}$ 。
证据为：
$p(\textbf{x})=\int p(\mathbf{\mu})\prod_{i=1}^{n}\sum_{c_i}p(c_i)p(x_i|c_i,\mathbf{\mu})d\mu$
$=\int p(\mu_1,...\mu_K)\prod_{i=1}^{n}\sum_{c_i}p(c_i)p(x_i|c_i,\mu_1,...\mu_K)d\mu_1d\mu_2...d\mu_K$ 。
上式中，每一个 $\mu_k$ 都无法从连乘项里分离出来，所以计算该积分的复杂度为 $\mathcal{O}(K^n)$ ，为K的指数级别的复杂度。所以一般没有闭式解（intractable）。
（想象某个场景，在10个混合分支中，采样100个点，计算该积分的复杂度高达 $10^{100}$ !）

ELBO（证据下界）

对目标 $p(\mathbf{z}|\mathbf{x})$ 求解，一味蛮干是行不通的。通行的做法有两种，要么通过蒙特卡洛法近似，要么通过变分推断近似。这里介绍后一种。
我们利用容易处理的“代理人”函数 $q(\mathbf{z})$ 近似 $p(\mathbf{z}|\mathbf{x})$ 。
$q^*(z)=argmin_{q(z)\in \mathcal{Q}} KL[q(z)||p(\mathcal{z}|\mathcal{x})]$
其中KL表示相对熵，由定义，
$KL[q(z)||p(\mathcal{z}|\mathcal{x})]=\mathbb{E}[\log q(\mathcal{z})]-\mathbb{E}[\log p(\mathcal{z}|\mathcal{x})]=\mathbb{E}[\log q(\mathcal{z})]-\mathbb{E}[\log p(\mathcal{z},\mathcal{x})]+\log p(\mathcal{x})$
由此可见，
$\mathbb{E}[\log p(\mathcal{z},\mathcal{x})]-\mathbb{E}[\log q(\mathcal{z})]=\log p(\mathcal{x})-KL[q(z)||p(\mathcal{z}|\mathcal{x})] \leq \log p(\mathcal{x})$
定义
$ELBO(q) =\mathbb{E}[\log p(\mathcal{z},\mathcal{x})]-\mathbb{E}[\log q(\mathcal{z})]$ 。
最大化ELBO就是最小化 $KL[q(z)||p(\mathcal{z}|\mathcal{x})]$ ，成功避开计算 $p(\mathcal{z}|\mathcal{x})$ 。

拿掉积分！

上面的混合高斯的例子，应用变分方法，我们得到
$\int p(\mu_1,...\mu_K)\prod_{i=1}^{n}\sum_{c_i}p(c_i)p(x_i|c_i,\mu_1,...\mu_K)d\mu_1d\mu_2...d\mu_K \\ \approx \mathbb{E}_{q(\mu_1,...\mu_K;\lambda)}\prod_{i=1}^{n}\sum_{c_i}p(c_i)p(x_i|c_i,\mu_1,...\mu_K)+KL[q(\mu;\lambda)||p(\mathcal{\mu}|\mathcal{x})]$
虽然多引入一个参数，但是不用求积分，只要算乘法和加减就够了。生活一下子美好了有木有！

求积分为啥这么难

来自：https://xkcd.com/2117/

微分与积分

至今的算法中，求微分（导数）的一大堆，求积分的寥寥可数。计算机和人类一样不擅长算积分啊！