Bayesian Statistics and Computation
Study notes on Bayesian statistics and computational methods.
Bayesian Foundations
Bayesian and Frequentist Perspectives
使用贝叶斯公式并不意味着在使用贝叶斯方法,频率学派也会经常使用贝叶斯公式,早在贝叶斯之前,贝叶斯公式就已经在Laplce等数学家中非常娴熟的应用,贝叶斯方法在思想上面的含义要远远大于数学形式上的贝叶斯公式。
摘抄知乎上Xiangyu Wang的回答:频率学派和贝叶斯学派最大的差别其实产生于对参数空间的认知上。所谓参数空间,就是你关心的那个参数可能的取值范围。频率学派(其实就是当年的Fisher)并不关心参数空间的所有细节,他们相信数据都是在这个空间里的“某个”参数值下产生的(虽然你不知道那个值是啥),所以他们的方法论一开始就是从“哪个值最有可能是真实值”这个角度出发的。于是就有了最大似然(maximum likelihood)以及置信区间(confidence interval)这样的东西,你从名字就可以看出来他们关心的就是我有多大把握去圈出那个唯一的真实参数。而贝叶斯学派恰恰相反,他们关心参数空间里的每一个值,因为他们觉得我们又没有上帝视角,怎么可能知道哪个值是真的呢?所以参数空间里的每个值都有可能是真实模型使用的值,区别只是概率不同而已。于是他们才会引入先验分布(prior distribution)和后验分布(posterior distribution)这样的概念来设法找出参数空间上的每个值的概率。最好诠释这种差别的例子就是想象如果你的后验分布是双峰的,频率学派的方法会去选这两个峰当中较高的那一个对应的值作为他们的最好猜测,而贝叶斯学派则会同时报告这两个值,并给出对应的概率。
假如我们有一个统计模型$f(x,\theta)$去估计原始数据$x$的分布,频率学派认为$\theta$是固定的,尽管我们现在还没有办法得到,贝叶斯学派认为$\theta$是随机的,是服从一个概率分布的随机变量。
From Prior to Posterior
贝叶斯的观点是符合人脑的认知规律的,也是现代认知心理学的基础:在认识一件事物之前,我们会先对这个事物有一定的认知,在与事物接触的过程中,我们的认知会逐渐的发生变化,或加强我们的认知,或减弱我们的认知,我们的认知从而得到了进步,这与马原中所说的认知随着实践螺旋式上升也有异曲同工之妙。贝叶斯公式就是表述了这个认知的过程:
$$ P(\theta \mid X)=\frac{P(X \mid \theta) P(\theta)}{P(X)} $$贝叶斯学派通过引入三个名词对贝叶斯公式进行解释:
| 名词 | 公式 |
|---|---|
| 先验分布(Prior) | $P(\theta)$ |
| 似然(Likelihood) | $P(X \mid \theta)$ |
| 后验分布(Postertor) | $P(\theta \mid X)$ |
先验分布就是在接触事物数据之前我们已经有的认知,似然是在接触事物的过程中,在给定先验知识的条件下我们对数据的认知,后验分布是我们在数据的基础上对事物的认知,机器学习中的“Learning”这一概念,很大程度上就是贝叶斯方法中的使用后验分布去调整先验分布,当数据量足够大的时候,$P(\theta)$就越来越接近真实的概率模型,另外,分母$P(X)$经常被成为贝叶斯因子。
我们再来观察特殊的情况。如果数据与先验独立,即$X \perp \theta$,有$P(\theta \mid X)=P(\theta)$,即先验等于后验,也就是说在接触数据的过程中,我们并没有学到有用的信息。如果$P(\theta)=0$,我们的先验分布和后验分布会一直等于0,所以在很多机器学习算法中设置初始迭代解的时候,会避开零概率的设置。
Example: Naive Bayes Classification
朴素贝叶斯是一种简单的机器学习分类器,分类任务就是在给定某些特征 $\lbrace F_i \rbrace_{i=1}^N$(Features)的条件下,判断某一事物的分类$C$(Catogories),即我们需要获得:$P(C \mid F_1:F_N)$,数据是给定条件,分类是随机变量,这就是贝叶斯方法中所说的后验分布,我们可以使用先验分布和似然来表示该后验分布:
$$ P(C \mid F_1:F_N)=\frac{P(F_1:F_N \mid C) P(C)}{P(F_1:F_N)} $$对不同特征求给定条件的联合分布是比较困难的,naive bayes做了一个假设,在给定分类条件下,不同特征之间相互独立,即我们可以重写上述公式为
$$ P(C \mid F_1:F_N)=\frac{\prod_{i=1}^N P(F_i \mid C) P(C)}{P(F_1:F_N)} $$分母可以通过统计样本得出,但是并不重要,因为所有的后验分布共享一个分母,当分类器判别样本时,都具有相同的权重。
Example: Posterior for a Gaussian Model
考虑正态似然与正态先验:$X_1,\ldots,X_N\mid\mu\overset{\mathrm{iid}}{\sim}\mathcal{N}(\mu,\sigma_x^2)$,且先验为 $\mu\sim\mathcal{N}(\mu_\theta,\sigma_\mu^2)$。由贝叶斯公式,后验密度满足
$$ p(\mu\mid x_{1:N})\propto p(x_{1:N}\mid\mu)p(\mu). $$忽略与 $\mu$ 无关的项,后验的对数密度为
$$ \begin{aligned} \log p(\mu\mid x_{1:N}) &=-\frac{1}{2}\left(\frac{N}{\sigma_x^2}+\frac{1}{\sigma_\mu^2}\right)\mu^2 +\left(\frac{\sum_{i=1}^N x_i}{\sigma_x^2}+\frac{\mu_\theta}{\sigma_\mu^2}\right)\mu+C\\ &=-\frac{1}{2v_N}(\mu-m_N)^2+C', \end{aligned} $$其中
$$ v_N=\left(\frac{N}{\sigma_x^2}+\frac{1}{\sigma_\mu^2}\right)^{-1},\qquad m_N=v_N\left(\frac{\sum_{i=1}^N x_i}{\sigma_x^2}+\frac{\mu_\theta}{\sigma_\mu^2}\right). $$因此后验分布仍为正态分布:$\mu\mid x_{1:N}\sim\mathcal{N}(m_N,v_N).$
令 $\bar X=N^{-1}\sum_{i=1}^N x_i$,后验均值也可写成数据均值与先验均值的加权平均:
$$ m_N=\frac{N/\sigma_x^2}{N/\sigma_x^2+1/\sigma_\mu^2}\,\bar X +\frac{1/\sigma_\mu^2}{N/\sigma_x^2+1/\sigma_\mu^2}\,\mu_\theta. $$样本量增大时,数据在后验均值中的权重增大;似然方差增大时,先验均值的权重相对增大。
Statistical Decision Theory
贝叶斯方法的核心观点就是利用后验分布去学习统计模型$\hat{\theta}(x)$,去对先验分布进行优化,那么就需要我们定义一种度量$d(\hat{\theta}(x),\theta)$,从而通过最小化这种度量的方式完成先验分布的优化,$d(\hat{\theta}(x),\theta)$是随机的,所以我们希望消除他的随机性求平均距离,即我们的目标为
$$ \hat{\theta}(x) = \underset{\hat{\theta}}{\arg \min }\mathbb{E}_{x,\theta}[d(\hat{\theta}(x),\theta) ] $$平均距离$\mathbb{E}_{x,\theta}[d(\hat{\theta}(x),\theta) ]$ 一般被成为风险(Risk),该目标函数也被称为风险极小化,频率学派和贝叶斯学派对该目标函数有不同方式的处理:
$$ \begin{aligned} E[d(\hat{\theta}(x), \theta)]&=\iint d(\theta, \hat{\theta}(x)) P_{x, \theta}\left(x, \theta\right) d x d\theta\\ &=\iint d(\theta, \hat{\theta}(x)) P_{x\mid \theta}\left(x\mid \theta\right) d xP(\theta) d\theta\\ &=\iint d(\theta, \hat{\theta}(x)) P_{x\mid \theta}\left(\theta \mid x\right) d \theta P(x) dx\\ \end{aligned} $$可见,频率学派尽可能的削弱$\theta$的随机性,因为他们认为$\theta$是确定的(所以在频率学派中有极大化似然这种方法),但是频率学派种所需要的似然往往是不可以直接计算的,因此有了经验风险极小化(Empirical Risk Minimization,ERM)理论,该理论一般将样本均值取代理论均值,即
$$ E[d(\hat{\theta}(x), \theta)]=\frac{1}{N}\sum_{k=1}^Nd(\theta_k, \hat{\theta}_k(x)) $$贝叶斯学派则是尽可能削弱数据的随机性,认为已经发生的实验就是确定的,将问题的重心转化到后验分布的计算上,在后面我们会看到,使用贝叶斯方法处理统计模型的关键就是得到后验分布以及如何处理后验分布。
Loss Functions and Bayes Estimators
Squared Loss and Posterior Mean
平方损失对应的贝叶斯风险为
$$ R(\hat\theta\mid x)=\int(\theta-\hat\theta)^2p(\theta\mid x)\,d\theta. $$使风险最小的估计是后验均值:
$$ \hat\theta_{\mathrm{MSE}}=\mathbb{E}[\theta\mid x] =\int\theta p(\theta\mid x)\,d\theta. $$Absolute Loss and Posterior Median
绝对损失对应的风险为
$$ R(\hat\theta\mid x)=\int|\theta-\hat\theta|p(\theta\mid x)\,d\theta. $$其最小值由后验中位数取得。对连续后验分布,最优点满足
$$ \int_{-\infty}^{\hat\theta}p(\theta\mid x)\,d\theta =\int_{\hat\theta}^{+\infty}p(\theta\mid x)\,d\theta=\frac12. $$Maximum a Posteriori Estimation
最大后验估计选择后验密度的众数:
$$ \hat\theta_{\mathrm{MAP}}\in\operatorname*{arg\,max}_{\theta}p(\theta\mid x). $$它也可由小邻域的零一损失得到。令 $d_\delta(\theta,\hat\theta)=\mathbf{1}\{|\theta-\hat\theta|>\delta\}$,则当 $\delta$ 足够小时,最小化后验风险等价于最大化 $p(\hat\theta\mid x)$。
Example: Bayesian Estimation for Bernoulli Trials
假设我们有先验分布$\theta$,似然$X\sim B(n,\theta)$,目标计算$\theta$的后验分布以及在均方意义下的最优估计。
由Bayes公式,有
$$ \begin{aligned} P(\theta \mid x) & =\frac{P(x \mid \theta) P(\theta)}{P(x)} \\ & =\frac{P(x \mid \theta) P(\theta)}{\int P(x, \theta) d \theta} \end{aligned} $$接下来,我们考虑当先验分布服从标准均匀分布的情况下后验概率的计算,即计算
$$ P(\theta \mid x)=\frac{\theta^x(1-\theta)^{n-x}}{\int_0^1 \theta^x(1-\theta)^{n-x} d \theta} $$在计算后验概率之前,我们需要引入Beta分布来辅助我们的贝叶斯因子的计算,Beta分布的pdf为
$$ \begin{aligned} f(x ; \alpha, \beta) & =\frac{x^{\alpha-1}(1-x)^{\beta-1}}{\int_0^1 u^{\alpha-1}(1-u)^{\beta-1} d u} \\ & =\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha) \Gamma(\beta)} x^{\alpha-1}(1-x)^{\beta-1} \\ & =\frac{1}{\mathrm{~B}(\alpha, \beta)} x^{\alpha-1}(1-x)^{\beta-1} \end{aligned} $$其中,$\alpha,\beta>0$,$\Gamma(x)$是Gamma函数,有性质
$$ \Gamma(x)=\int_0^{+\infty} t^{x-1} e^{-t} d t(x>0)=(x-1)! $$Beta函数$B(\alpha, \beta)$的定义为$B(\alpha, \beta)=\int_0^1 t^{\alpha-1}(1-t)^{\beta-1} \mathbf{d} t$,现在我们来证明$\mathrm{~B}(\alpha, \beta)=\frac{\Gamma(\alpha) \Gamma(\beta)}{\Gamma(\alpha+\beta)}$:
观察Beta函数的定义,类似卷积的定义,注意到:
$$ \begin{aligned} B(\alpha, \beta)&=\int_0^1 t^{\alpha-1}(x-t)^{\beta-1} \mathbf{d} t\mid_{x=1} \\&=f(x)*g(x)\mid_{x=1} \end{aligned} $$在上述公式中,我们定义了两个幂函数$f(x): =x^{\alpha-1},g(x):=x^{\beta-1},$这两个幂函数的支撑集应该是[0,1],这样才能满足积分的上下限要求,现在对两个幂级数的卷积进行Laplce变换:
$$ \mathcal{L}\left\{x^{\alpha-1} * x^{\beta-1}\right\}=\mathcal{L}\left\{x^{\alpha-1}\right\} \cdot \mathcal{L}\left\{x^{\beta-1}\right\} $$而幂级数的Laplace变换可以和Gamma函数联系起来,即
$$ \begin{aligned} \mathcal{L}\left\{t^a\right\}&=\int_0^{\infty} t^a e^{-s t} d t \\ &=\frac{1}{s^{a+1}} \int_0^{\infty}(s t)^a e^{-(s t)}(s d t) \\ &=\frac{1}{s^{a+1}} \int_0^{\infty} \tau^{(a+1)-1} e^{-\tau} d \tau \\ &=\frac{\Gamma(a+1)}{s^{a+1}} \end{aligned} $$继续我们上述的Laplace变换,有
$$ \begin{aligned} \mathcal{L}\left\{x^{\alpha-1}\right\} \cdot \mathcal{L}\left\{x^{\beta-1}\right\}&=\frac{\Gamma(\alpha) \Gamma(\beta)}{s^{\alpha+\beta}} \\ &=\frac{\Gamma(\alpha) \Gamma(\beta)}{\Gamma(\alpha+\beta)}\frac{\Gamma(\alpha+\beta-1+1)}{s^{(\alpha+\beta-1)+1}}\\ &=\frac{\Gamma(\alpha) \Gamma(\beta)}{\Gamma(\alpha+\beta)} \mathcal{L}\left\{x^{\alpha+\beta-1}\right\} \end{aligned} $$这时令$x=1$,便可以得到$\mathrm{~B}(\alpha, \beta)=\frac{\Gamma(\alpha) \Gamma(\beta)}{\Gamma(\alpha+\beta)}$,证毕。
现在我们使用Beta函数来计算后验分布,注意,如果令$\alpha = x+1,\beta = n-x+1$,后验分布的贝叶斯因子为$B(\alpha,\beta)=B(x+1,n-x+1)$,那么有
$$ \begin{aligned} \int_0^1 \theta^x(1-\theta)^{n-x} d \theta & =B(x+1, n-x+1) \\ & =\frac{\Gamma(x+1) \Gamma(n-x+1)}{\Gamma(n+2)} \\ & =\frac{x!(n-x)!}{(n+1)!} \end{aligned} $$则我们计算出来的后验分布最终形式为
$$ P(\theta, x)=\frac{(n+1)!}{x!(n-x)!} \theta^x(1-\theta)^{n-x} $$可见该后验分布实际上是服从Beta分布的。根据MSE意义下的最优估计,有
$$ \begin{aligned} E[\theta \mid x] & =\int_0^1 \theta \frac{(n+1)!}{x!(n-x)!} \theta^x(1-\theta)^{n-x} d \theta \\ & =\frac{(n+1)!}{x!(n-x)!} \int_0^1 \theta^{x+1}(1-\theta)^{n-x} d \theta \\ & =\frac{(n+1)!}{x!(n-x)!} B(x+2, n-x+1) \\ & =\frac{(n+1)!}{n!(n-x)!} \frac{(x+1)!(n-x)!}{(n+2)!} \\ & =\frac{x+1}{n+2} \end{aligned} $$至此,我们求得了后验分布和MSE意义下的模型最优估计。 如果再进一步的处理该条件期望,我们可以得到线型凸组合的形式:
$$ E[\theta \mid x]=\frac{n}{n+2}\frac{x}{n}+\frac{2}{n+2}\frac{1}{2} $$$\frac{x}{n}$反应了似然意义上的某种均值,$\frac{1}{2}$为先验分布的均值,这也显示了在伯努利实验的情况下,最优估计的过程是不断线性凸组合的过程。
Example: Beta Conjugate Prior
在上个例子中,我们一开始假设先验分布服从标准均匀分布,但是我们根据伯努利的似然求出后验分布之后,发现后验分布并不服从标准均匀分布,而是服从Beta分布,这说明我们的先验分布并没有反映事物的客观性质,在统计学中,如果我们的先验分布和后验分布的分布类型一致,我们就称该先验分布为共轭先验。
在一些比较简单的概率模型中,共轭先验是已知的并且可以提前制定的,例如当似然服从伯努利分布时,共轭先验为Beta分布,但是更多的(绝大多数的)概率模型的共轭先验是难以得到的。我们沿用上一个例子的情景,令先验分布为Beta分布,即
$$ P(\theta)=\frac{(a+b+1)!}{(a-1)!(b-1)!}\theta^{a-1}(1-\theta)^{b-1} $$使用与上一个例子同样的方法去求后验分布和条件期望,最终可以求得条件期望为
$$ E[\theta \mid x] = \frac{x+a}{n+a+b} $$同样的,该条件期望也可以写成线型图组合的形式,即
$$ E[\theta \mid x]=\frac{a+b}{n+a+b}\frac{a}{a+b}+\frac{n}{n+a+b}\frac{x}{n} $$依然是某种实验中的均值与先验分布均值的线性凸组合,从我们在上一个章节中的Gauss分布似然到这个章节的伯努利分布似然,最后都得到了线性凸组合的学习形式,这可能并不是一种偶然,这些简单的例子给我们启发:在高维空间中,复杂分布的学习过程也可能是迭代的线性凸组合。
Sampling
使用Bayes方法的核心在于后验分布的处理,但是后验分布的形式往往是极其复杂的,极大多数的后验分布都是难以去积分甚至不可积的,统计中常用的方法就是生成符合后验分布的样本,从而利用样本代替解析表达的分布进行计算,这种生成样本的方法又被称作采样。
模拟是指把某一现实的或抽象的系统的某种特征或部分状态, 用另一系统(称为模拟模型)来代替或近似。 为了解决某问题, 把它变成一个概率模型的求解问题, 然后产生符合模型的大量随机数, 对产生的随机数进行分析从而求解问题, 这种方法叫做随机模拟方法, 又称为蒙特卡洛(Monte Carlo)方法。
Inverse Transform Sampling
逆分布采样的描述很简单。设 $F$ 是目标分布的累积分布函数,先生成 $U\sim\operatorname{Uniform}(0,1)$,再令 $Y=F^{-1}(U)$,其中 $F^{-1}$ 表示广义逆。
这样来看,生成随机变量的样本的过程就很简单,第一步,生成均匀分布的样本(可以利用线性同余法等方法生成),第二步,求得目标分布累积分布函数的逆,第三步,代入累积分布函数的逆求得目标样本。
现在简单的证明一下随机变量$Y$与随机变量$X$服从同一个分布,求$Y$的累积分布函数:$F_Y(y)=\Pr(Y\le y)=\Pr(U\le F(y))=F(y).$
可见,$Y$的累积分布函数实际上就是$X$的累积分布函数,所以它们服从同一个分布,如此,对于易于求得逆累积分布的随机变量,我们便可以通过这种方法求得符合该分布的样本,例如指数分布、泊松分布。
Example: Gaussian Sampling with Box–Muller
Guassian分布的逆分布函数并不好求,虽然我们可以通过中心极限定理生成Gaussian分布,但那种方法并不属于逆分布生成,Box-Muller算法是一种经典的Gaussian分布生成算法,使用了极坐标变换来处理Gaussian分布难以求逆的问题,接下来我们介绍这种方法。
假设我们目标求得两个独立同分布的标准高斯随机变量,$X_1,X_2\overset{\mathrm{iid}}{\sim} N(0,1)$,则它们的联合概率密度为
$$ \begin{aligned} f_{X Y}(x, y) & =\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{x^2}{2 \sigma^2}\right) \frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{y^2}{2 \sigma^2}\right) \\ & =\frac{1}{2 \pi } \exp \left(-\frac{x^2+y^2}{2 }\right) \end{aligned} $$对该联合概率密度进行极坐标变换,有
$$ \begin{aligned} f_{X Y}(x, y) &=f_{XY}(\rho \cos\theta,\rho \sin\theta)\\ &=\frac{1}{2 \pi } \exp \left(-\frac{\rho^2}{2 }\right)\rho \end{aligned} $$Rejection Sampling
令 $c$ 是一个常数,使得
$$ \frac{f(y)}{g(y)} \leqslant c \quad \forall y $$那么,我们用下述技术模拟出具有密度 $f$ 的连续分布函数的随机变量:
步骤 1: 模拟具有密度 $g$ 的随机变量 $Y$ ,并且模拟一个随机数 $U$ .
步骤 2: 如果 $U \leqslant \frac{f(Y)}{c g(Y)}$ ,那么置 $X=Y$ .否则返回步骤 1 .
命题. 由拒绝法生成的随机变量 $X$ 具有密度 $f$ .
Proof: Correctness of Rejection Sampling
证明. 令 $X$ 是得到的值,而以 $N$ 记必需重复的次数.那么
其中 $K=\mathrm{P}\{U \leqslant f(Y) / c g(Y)\}$ ,令 $x \rightarrow \infty$ ,表明 $K=1 / c$ ,故而完成了证明,
可以参考张颢老师在现代数字信号处理(二)中贝叶斯信号处理部分,先对有限支撑集进行采样,再拓展到无限支撑集,非常直观。
Monte Carlo Integration
蒙特卡洛积分用样本平均估计积分。若区域 $\Omega\subset\mathbb{R}^m$ 的体积为 $V$,则 $I=\int_{\Omega}f(x)\,dx$ 等于 $V$ 乘以均匀分布下 $f$ 的期望。独立地从 $\Omega$ 均匀抽取 $X_1,\ldots,X_N$,可用 $Q_N=\frac{V}{N}\sum_{i=1}^N f(X_i)$ 估计 $I$。只要 $f$ 可积,大数定律就保证 $Q_N$ 收敛到 $I$。
更一般地,若积分写成 $I=\int_{\Omega}f(x)p(x)\,dx=\mathbb{E}_p[f(X)]$,从密度 $p$ 独立抽样后,用 $\hat I_N=\frac{1}{N}\sum_{i=1}^N f(X_i)$ 估计该期望。若 $f(X)$ 的方差有限,估计量的标准误差为 $\sqrt{\operatorname{Var}_p(f(X))/N}$。
在贝叶斯推断中,$p$ 可以取后验密度,样本平均便可用于估计后验期望。当目标分布难以直接采样时,可以改从更容易抽样的分布生成样本,再加权修正。这就是下一节的重要性采样。
Importance Sampling
这里摘取知乎上一位答主的回答:一些常见的方差缩减方法:
假设我们要估计 $\theta=\mathbb{E}_f[h(X)]$ ,其中 $X$ 的PDF是 $f$ 。令 $g$ 为另一PDF,其满足当 $f(x) \neq 0, ~ g(x) \neq 0$ ,即 $f$ 和 $g$ 的支集相等。那么,
$$ \theta=\mathbb{E}_f[h(X)]=\int h(x) \frac{f(x)}{g(x)} g(x) d x=\mathbb{E}_g\left[\frac{h(X) f(X)}{g(X)}\right] $$初始的模拟是从密度 $f$ 中生成 $n$ 个 $X$ 的值,并取 $\hat{\theta}_n=\sum h\left(X_j\right) / n$ 。另一种模拟是从密度 $g$ 中生成 $n$ 个 $X$ 的值,并设
$$ \hat{\theta}_{n, i s}=\sum_{j=1}^n \frac{h\left(X_j\right) f\left(X_j\right)}{g\left(X_j\right)} $$这里 $\hat{\theta}_{n, i s}$ 叫作 $\theta$ 的重要性采样估计。我们通常定义 $h^{\*}(x)=h(x) f(x) / g(x)$ ,因此 $\theta=\mathbb{E}_g\left[h^{\*}(X)\right]$ 。
令 X 为联合PDF为 $f$ 的随机向量,并不失一般性地假设 $h(\mathrm{X}) \geq 0$ 。重要性采样估计的方差是
$$ \begin{gathered} \operatorname{Var}_g\left(h^{\*}(\mathrm{X})\right)=\int h(\mathrm{x})^2 g(\mathrm{x}) d \mathrm{x}-\theta^2 \\ \quad=\int h(\mathrm{x})^2 \frac{f(\mathrm{x})}{g(\mathrm{x})} f(\mathrm{x}) d \mathrm{x}-\theta^2 \end{gathered} $$而初始估计的方差是 $\operatorname{Var}_f(h(\mathrm{X}))=\int h(\mathrm{x})^2 f(\mathrm{x}) d \mathrm{x}-\theta^2$ ,所以方差的缩减是
$$ \operatorname{Var}_f(h(\mathrm{X}))-\operatorname{Var}_g\left(h^{\*}(\mathrm{X})\right)=\int h(\mathrm{x})^2\left(1-\frac{f(\mathrm{x})}{g(\mathrm{x})}\right) f(\mathrm{x}) d \mathrm{x} $$为了实现方差缩减,上面的积分应该是正的,这要求
- 当 $h^2(\mathrm{x}) f(\mathrm{x})$ 小时,$f(\mathrm{x}) / g(\mathrm{x})\lt 1$ ,
- 当 $h^2(\mathrm{x}) f(\mathrm{x})$ 大时,$f(\mathrm{x}) / g(\mathrm{x})>1$ 。 若密度 $f$ 的重要的部分定义在区域 $A$ ,则上面的要求指出当 x 在 $A$ 中时,$f(\mathrm{x}) / g(\mathrm{x})$ 很小,即密度 $g$ 给 $A$ 更多的权重,所以这个方法叫作重要性采样。由于 $h$ 包含了一个稀有事件,所以在状态空间中 $h(\mathrm{x})=0$ 。我们选择 $g$ ,使得我们经常从状态空间中 $h(\mathrm{x}) \neq 0$ 的部分抽样。因此,重要性采样对于稀有事件模拟很有用。
若我们选择 $g(\mathrm{x})=h(\mathrm{x}) f(\mathrm{x}) / \theta$ ,我们会得到一个方差为 0 的估计,但这显然是不实际的。然而,这告诉我们,我们可以选择 $g(\cdot)$ ,使得它和 $h(\cdot) f(\cdot)$ 相似。特别地,我们可以使得 $g(\mathrm{x})$ 和 $h(\mathrm{x}) f(\mathrm{x})$ 在同一个值 $\mathrm{x}^{\*}$ 上取到最大值,这叫作最大值原则。有时最大值原则难以应用,比如 $\mathrm{x}^{\*}=\arg \max _{\mathrm{x}} h(\mathrm{x}) f(\mathrm{x})$ 有无数多解。这时我们可以通过缩放 $f$ 来选取 $g$ 。
Remark: Why the Weights Matter
"重要性"一词的直观解释
"重要性采样"之名正是来源于对高贡献区域的聚焦:在估计 $\mathbb{E}_p[f(X)]$ 时,只有那些使 $f(x) p(x)$ 较大的 $x$ 值对积分贡献显著,被称为"重要点"。理想的 $q(x)$ 会对这些重要点给予更高采样概率,而对贡献小的点减少采样,以降低方差。直观地,当 $f(x)$ 很大时,样本点在该处的权重 $p(x) / q(x)$ 较小,多个样本共同估计可获得稳定的贡献;而在 $f(x)$ 很小的区域,即使权重较大,其对期望的贡献也微不足道。统计理论指出,若 $q$ 对重要区域加大权重,那么估计方差会显著减小 。总之,"重要性"一词反映了:理想的采样策略应更多采样那些对期望值贡献最大的区域,从而实现高效无偏估计。
实际上可以利用Jensen不等式求出重要性采样方差的一个lower bound,在$g\propto|h|f$ 时可以取到等号,即方差最小。值得注意的是,使用重要性采样算出的方差要小于接受拒绝采样。
gpt的一份回答.
Sampling Importance Resampling
将重要性采样和重采样进行结合可以得到SIR:
算法步骤
设:
- 目标分布(如后验):$\pi(x) \propto p(x) \cdot L(x)$ ,其中 $p(x)$ 是先验,$L(x)$ 是似然;
- 提议分布(容易采样):$q(x)$ ,需满足 $\pi(x)>0 \Rightarrow q(x)>0$ ;
- 我们的目标是得到近似服从 $\pi(x)$ 的样本集。
步骤如下:
- 采样阶段(Sampling)
从提议分布 $q(x)$ 中采样 $N$ 个样本:$x_1, x_2, \ldots, x_N \sim q(x)$
- 重要性加权(Importance Weighting)
为每个样本计算未归一化权重:
$$ w_i=\frac{\pi\left(x_i\right)}{q\left(x_i\right)} \propto \frac{p\left(x_i\right) L\left(x_i\right)}{q\left(x_i\right)} $$归一化权重:
$$ \tilde{w}_i=\frac{w_i}{\sum_{j=1}^N w_j} $$- 重采样阶段(Resampling)
根据归一化权重 $\tilde{w}_i$ 从 $\left\{x_1, \ldots, x_N\right\}$ 中进行有放回采样,采样 $M \leq N$ 个样本,得到:
$$ x^{\*(1)}, x^{\*(2)}, \ldots, x^{\*(M)} \sim \operatorname{Categorical}\left(\tilde{w}_1, \ldots, \tilde{w}_N\right) $$最终样本集 $x^{\*(1)}, \ldots, x^{\*(M)}$ 可视为来自目标后验 $\pi(x)$ 的近似样本。
Remark: Limitations of SIR
SIR难以处理高维数据,需要进一步引入序贯蒙特卡洛采样,转化为低纬度数据后再进行SIR,我们将在后续章节介绍该技术。
Variance Reduction
Antithetic Variates
定理 1. 设 $g$ 为单调函数,$U \sim U(0,1)$ ,则 $\operatorname{Cov}(g(U), g(1-U)) \leq 0$ 。
定理1可以推广到如下情形。
定理 2. 设 $h\left(x_1, x_2, \ldots, x_n\right)$ 是关于每个自变量单调的函数,$U_1, U_2, \ldots, U_n$ 相互独立同 $\mathrm{U}(0,1)$ 分布,则 $\operatorname{Cov}\left(h\left(U_1, U_2, \ldots, U_n\right), h\left(1-U_1, 1-U_2, \ldots, 1-U_n\right)\right) \leq 0$ 。
对均匀随机数 $U$ 最常见的变换是逆变换 $X=F^{-1}(U)$ 。下面的定理给出了提高 $I=E X$ 估计精度的方法。
定理 3(对立变量法) 设 $F(x)$ 为连续分布函数,$U \sim \mathrm{U}(0,1), X=F^{-1}(U), Y=F^{-1}(1-U)$ , $Z=\frac{X+Y}{2}$ ,则 $X$ 与 $Y$ 同分布 $F(x)$ 且 $\operatorname{Cov}(X, Y) \leq 0$ ,
$$ \operatorname{Var}(Z) \leq \frac{1}{2} \operatorname{Var}(X) $$Conditional Monte Carlo
进行统计估计时,如果有额外的相关信息,利用这样的信息可以提高估计精度。比如,对随机变量 $Y$ ,如果 $Y$ 服从某种模型,在估计 $I=E Y$ 时应当尽量利用模型信息。
设变量 $X$ 与 $Y$ 不独立,根据Rao-Blackwell不等式:
$$ \operatorname{Var}\{\mathrm{E}(Y \mid X)\} \leq \operatorname{Var}(Y) $$又
$$ \mathrm{E}\{\mathrm{E}(Y \mid X)\}=\mathrm{E} Y=I $$所以,对 $Z=\mathrm{E}(Y \mid X)$ 抽样,用 $Z$ 的样本平均值来估计 $I=\mathrm{E} Y$ 比直接用 $Y$ 的样本平均值的精度更高。这种改善随机模拟估计精度的方法叫做条件期望法,或Rao-Blackwell方法。
Example: Conditional Monte Carlo
例14.5 设 $X \sim p(x), \varepsilon \sim \mathrm{N}\left(0, \sigma^2\right)$ 且与 $X$ 独立,
$Y=\psi(X)+\varepsilon$ 估计 $I=\mathrm{E} Y$ 。 可以用条件分布抽样法对二元随机向量 $\boldsymbol{Z}=(X, Y)$ 抽样产生 $Y$ 的样本。从 $p(\cdot)$ 抽样得 $X_1, X_2, \ldots, X_N$ ,独立地从 $\mathrm{N}\left(0, \sigma^2\right)$ 抽样得 $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_N$ ,令
$$ Y_i=\psi\left(X_i\right)+\varepsilon_i, i=1,2, \ldots, N $$然后用 $Y_1, Y_2, \ldots, Y_N$ 的样本平均值估计 $E Y$ :
$$ \hat{I}_1=\frac{1}{N} \sum_{i=1}^N Y_i $$估计方差为
$$ \operatorname{Var}\left(\hat{I}_1\right)=\frac{\operatorname{Var}\left(Y_1\right)}{N}=\frac{\operatorname{Var}\left(\psi\left(X_1\right)\right)}{N}+\frac{\sigma^2}{N} . $$另一方面,注意 $E(Y \mid X)=\psi(X)$ ,也可以只对 $X$ 抽样然后用条件期望法估计 $E Y$ :
$$ \hat{I}_2=\frac{1}{N} \sum_i \psi\left(X_i\right) $$估计方差为
$$ \operatorname{Var}\left(\hat{I}_2\right)=\frac{\operatorname{Var}\left(\psi\left(X_1\right)\right)}{N}\lt \operatorname{Var}\left(\hat{I}_1\right) $$这个例子演示了条件期望法可以缩减误差方差的原因:对 $Y$ 抽样分成两步进行:第一步对 $X$ 抽样,第二步利用 $Y \mid X$ 的条件分布对 $Y$ 抽样。所以使用 $Y$ 的样本估计 $E Y$ 包含了第二步对 $Y$ 抽样的随机误差,而使用 $X$ 的函数 $E(Y \mid X)=\psi(X)$ 的抽样来估计 $E Y$ 则避免了第二步对 $Y$ 抽样引起的随机误差。
Control Variates
同样假设我们要用模拟来估计 $\mathrm{E}[g(\boldsymbol{X})]$ ,其中 $\boldsymbol{X}=\left(X_1, \cdots, X_n\right)$ .但是现在假设对于某个 $f, f(\boldsymbol{X})$ 的期望值已知(例如 $\mathrm{E}[f(\boldsymbol{X})]=\mu$ ).那么,对于任意常数 $a$ ,我们也可以用
$W=g(\boldsymbol{X})+a(f(\boldsymbol{X})-\mu)$ 作为 $\mathrm{E}[g(\boldsymbol{X})]$ 的估计.现在,
$$ \operatorname{Var}(W)=\operatorname{Var}(g(\boldsymbol{X}))+a^2 \operatorname{Var}(f(\boldsymbol{X}))+2 a \operatorname{Cov}(g(\boldsymbol{X}), f(\boldsymbol{X})) $$简单的计算说明了上式当
$$ a=\frac{-\operatorname{Cov}(f(\boldsymbol{X}), g(\boldsymbol{X}))}{\operatorname{Var}(f(\boldsymbol{X}))} $$时达到最小,而对于这个值 $a$ ,
$$ \operatorname{Var}(W)=\operatorname{Var}(g(\boldsymbol{X}))-\frac{[\operatorname{Cov}(f(\boldsymbol{X}), g(\boldsymbol{X}))]^2}{\operatorname{Var}(f(\boldsymbol{X}))} $$因为 $\operatorname{Var}(f(\boldsymbol{X}))$ 和 $\operatorname{Cov}(f(\boldsymbol{X}), g(\boldsymbol{X}))$ 通常是不知道的,所以应该用模拟的数据来估计这些量。
将上式除以 $\operatorname{Var}(g(\boldsymbol{X}))$ 得出
$$ \frac{\operatorname{Var}(W)}{\operatorname{Var}(g(\boldsymbol{X}))}=1-\operatorname{Corr}^2(f(\boldsymbol{X}), g(\boldsymbol{X})) $$其中 $\operatorname{Corr}(X, Y)$ 是 $X$ 和 $Y$ 之间的相关系数.因此,当 $f(\boldsymbol{X})$ 和 $g(\boldsymbol{X})$ 强相关时,使用控制变量将大大地降低模拟估计的方差.
Markov Chain Monte Carlo
之前我们提到过贝叶斯学派的核心,MCMC和变分推断,MCMC速度慢但是精度高,变分推断速度快但是精度低,我们将详细介绍两种MCMC算法,Metropolis-Hasting算法和Gibbs算法。
Metropolis–Hastings
Metropolis–Hastings 的目标是构造一条以给定分布为平稳分布的马尔可夫链。
如何得到有平稳分布的转移概率矩阵?一个充分条件是转移概率满足细致平衡条件。如果存在 $\left\{\pi_j, j \in S\right\}$ , $\pi_j \geq 0, \sum_{j \in S} \pi_j=1$ ,使得
$$ \pi_i p_{i j}=\pi_j p_{j i}, \forall i \neq j $$称这样的马氏链为细致平衡的(detailed balanced),这时 $\left\{\pi_j\right\}$ 是 $\left\{X_t\right\}$ 的平稳分布。
设随机变量 $X$ 分布为 $\pi(x), x \in \mathcal{X}$ 。 为论述简单起见仍假设 $\mathcal{X}$ 是离散集合。算法需要一个试转移概率函数 $T(y \mid x), x, y \in \mathcal{X}$ ,满足 $0 \leq T(y \mid x) \leq 1, \sum_y T(y \mid x)=1$ ,并且
$$ T(y \mid x)>0 \Leftrightarrow T(x \mid y)>0 . $$算法首先从 $\mathcal{X}$ 中任意取初值 $X^{(0)}$ 。设经过 $t$ 步后算法的当前状态为 $X^{(t)}$ ,则下一步由试转移分布 $T\left(y \mid X^{(t)}\right)$ 抽取 $Y$ ,并生成 $U \sim U(0,1)$ ,然后按如下规则转移:
$$ X^{(t+1)}= \begin{cases}Y & \text { if } U \leq r\left(X^{(t)}, Y\right) \\\ X^{(t)} & \text { other. }\end{cases} $$其中(接收$y$的概率为)
$$ r(x, y)=\min \left\{1, \frac{\pi(y) T(x \mid y)}{\pi(x) T(y \mid x)}\right\} $$Remark: Proposal Choices and Normalization
在MH算法中如果取 $T(y \mid x)=T(x \mid y)$ ,则 $r(x, y)=\min \left(1, \frac{\pi(y)}{\pi(x)}\right)$ ,相应的算法称为Metropolis抽样法。如果取 $T(y \mid x)=g(y)$(不依赖于 $x$ ),则 $r(x, y)=\min \left(1, \frac{\pi(y) / g(y)}{\pi(x) / g(x)}\right)$ ,相应的算法称为Metropolis独立抽样法,和重要抽样有相似之处,试抽样分布 $g(\cdot)$ 经常取为相对重尾的分布。
在MH算法中,目标分布 $\pi(x)$ 可以用差一个常数倍的 $\tilde{\pi}(x)=C \pi(x)$ 代替,这样关于目标分布仅知道差一个常数倍的 $\tilde{\pi}(x)$ 的情形,也可以使用此算法。
Proof: Detailed Balance for Metropolis–Hastings
下面说明MH抽样方法的合理性。 我们来验证MH抽样的转移概率 $A(x, y)=P\left(X^{(t+1)}=y \mid X^{(t)}=x\right)$ 满足细致平衡条件。
$$ A(x, y)= \begin{cases}T(y \mid x) r(x, y), & y \neq x \\\ T(x \mid x)+\sum_{z \neq x} T(z \mid x)[1-r(x, z)], & y=x\end{cases} $$分别考虑转移到不同状态和留在原状态的情形。
情况1:$y \neq x$
- 只有当抽样 $Y=y$ 且接受它时,才会从 $x$ 转移到 $y$ 。
- 抽样 $Y=y$ 的概率是 $T(y \mid x)$ ,
- 接受 $y$ 的概率是 $r(x, y)$ ,
因此,
$$ A(x, y)=T(y \mid x) \cdot r(x, y), \quad y \neq x $$情况2:$y=x$(即"留在原地") 有两种情况会导致留在原地: 1.从试转移分布中采样到 $Y=x$ ,然后接受(总是接受); 2.从试转移分布中采样到 $Y=z \neq x$ ,但拒绝了(即 $U>r(x, z)$ ) 所以,转移回 $x$ 的概率为:
$$ A(x, x)=T(x \mid x) \cdot 1+\sum_{z \neq x} T(z \mid x) \cdot(1-r(x, z)) $$即:
$$ A(x, x)=T(x \mid x)+\sum_{z \neq x} T(z \mid x)[1-r(x, z)] $$于是当 $x \neq y$ 时
$$ \pi(x) A(x, y)=\pi(x) T(y \mid x) \min \left\{1, \frac{\pi(y) T(x \mid y)}{\pi(x) T(y \mid x)}\right\}=\min \{\pi(x) T(y \mid x), \pi(y) T(x \mid y)\} $$等式右侧关于 $x, y$ 是对称的,所以等式左侧把 $x, y$ 交换后仍相等。所以,MH构造的马氏链以 $\{\pi(x)\}$ 为平稳分布。多数情况下MH构造的马氏链也以 $\{\pi(x)\}$ 为极限分布。
从构造的 $r$ 可以看出,MH算法也可以由接收拒绝的思想去理解,并且从构造的接受拒绝策略来看,已经有了Langevin采样的思想,即向概率密度高的方向移动。
Gibbs Sampling
Gibbs 采样依次从各坐标的满条件分布抽样。每次更新一个坐标时,可以把这一步看作接受率为 1 的 Metropolis–Hastings 更新。
定义(满条件分布). 对于一个变量集合 $x_I=\left\{x_i: i \in I\right\}(I \subseteq\{1,2, \cdots, k\})$ 和补集变量 $x_{-I}=\left\{x_i: i \notin I\right\}$ ,满条件分布定义为:
$$ p\left(x_I \mid x_{-I}\right)=\frac{p(x)}{\int p(x) d x_I} \propto p(x) $$算法原理:将 Gibbs 看作 Metropolis-Hastings,其中旧状态是 $x=\left(x_i, x_{-i}\right)$ ,新状态是 $x^{\prime}=\left(x_i^{\prime}, x_{-i}\right)$ 。 由于仅更新了 $x_i$ ,且 proposal 是 $\pi\left(x_i^{\prime} \mid x_{-i}\right)$ ,我们写接受概率为:
Proof: Gibbs Updates Have Acceptance Probability One
$$ \alpha\left(x, x^{\prime}\right)=\min \left(1, \frac{\pi\left(x^{\prime}\right) \pi\left(x_i \mid x_{-i}\right)}{\pi(x) \pi\left(x_i^{\prime} \mid x_{-i}\right)}\right) $$注意:
- $\pi(x)=\pi\left(x_i, x_{-i}\right)$
- $\pi\left(x^{\prime}\right)=\pi\left(x_i^{\prime}, x_{-i}\right)$
因此上式变为:
$$ \alpha\left(x, x^{\prime}\right)=\min \left(1, \frac{\pi\left(x_i^{\prime}, x_{-i}\right) \pi\left(x_i \mid x_{-i}\right)}{\pi\left(x_i, x_{-i}\right) \pi\left(x_i^{\prime} \mid x_{-i}\right)}\right) $$利用条件概率定义: $$ \begin{aligned} & \pi\left(x_i, x_{-i}\right)=\pi\left(x_i \mid x_{-i}\right) \pi\left(x_{-i}\right) \ & \pi\left(x_i^{\prime}, x_{-i}\right)=\pi\left(x_i^{\prime} \mid x_{-i}\right) \pi\left(x_{-i}\right) \end{aligned}
代入后得到:
$$ \alpha\left(x, x^{\prime}\right)=\min \left(1, \frac{\pi\left(x_i^{\prime} \mid x_{-i}\right) \pi\left(x_{-i}\right) \pi\left(x_i \mid x_{-i}\right)}{\pi\left(x_i \mid x_{-i}\right) \pi\left(x_{-i}\right) \pi\left(x_i^{\prime} \mid x_{-i}\right)}\right)=\min (1,1)=1 $$- 选取初始状态 $x$。
- 按顺序遍历各坐标 $i$。每次从满条件分布 $\pi(x_i\mid x_{-i})$ 抽样,更新 $x_i$,并在后续步骤中使用更新后的状态。
- 重复遍历,记录每轮更新后的样本。
Convergence of Markov Chains
MCMC算法非常的丰富,我们仅仅阐述了两种最基础的MCMC算法,有一些基于物理学思想的MCMC算法也非常有意思,例如哈密顿蒙特卡洛、朗之万蒙特卡洛,以后有机会我们再介绍,本章节我们从Markov链的理论出发,再次回顾MCMC算法,很大部分参考视频:【贝叶斯统计】MCMC理论2 Metropolis-Hastings与two-stage Gibbs的理论.
另外,本人之前阅读过关于Langevin MCMC的一些论文,可见该网页.
定义 (转移核). Let $(X, \mathcal{A})$ and $(Y, \mathcal{B})$ be measurable spaces. A Markov kernel with source $(X, \mathcal{A})$ and target $(Y, \mathcal{B})$, sometimes written as $\kappa:(X, \mathcal{A}) \rightarrow(Y, \mathcal{B})$, is a function $\kappa: \mathcal{B} \times X \rightarrow[0,1]$ with the following properties:
- For every (fixed) $B_0 \in \mathcal{B}$, the map $x \mapsto \kappa\left(B_0, x\right)$ is $\mathcal{A}$-measurable
- For every (fixed) $x_0 \in X$, the map $B \mapsto \kappa\left(B, x_0\right)$ is a probability measure on $(Y, \mathcal{B})$
In other words it associates to each point $x \in X$ a probability measure $\kappa(d y \mid x): B \mapsto \kappa(B, x)$ on $(Y, \mathcal{B})$ such that, for every measurable set $B \in \mathcal{B}$, the map $x \mapsto \kappa(B, x)$ is measurable with respect to the $\sigma$-algebra $\mathcal{A} .$
在基础的Markov链中,我们应该都接触过不可约的概念,MCMC理论中使用的不可约比常见的不可约条件稍弱:
定义 ( $\varphi$-irreducibility). $\phi$-不可约性:存在一个非零测度 $\phi$ ,使得从任意 $x$ ,对任何测度为正的集合 $A$ ,都有某个时间 $n$ 使 $k^n(x, A)>0$ ;
我们提到过细致平衡条件,以下的运算说明满足细致平衡条件的分布是稳态分布:
$$ \begin{aligned} p(z) & =\sum_{z^{\prime}} p^{(\text {prev })}\left(z^{\prime}\right) T\left(z^{\prime}, z\right) \\ & =\sum_{z^{\prime}} p^{(\text {prev })}(z) T\left(z, z^{\prime}\right) \\ & =p^{(\text {prev })}(z) \sum_{z^{\prime}} T\left(z, z^{\prime}\right) \\ & =p^{(\text {prev })}(z) \sum_{z^{\prime}} p\left(z^{\prime} \mid z\right) \\ & =p^{(\text {prev })}(z) \sum_{z^{\prime}} \frac{p\left(z^{\prime}, z\right)}{p(z)} \\ & =p^{(\text {prev })}(z) \frac{p(z)}{p(z)} \\ & =p^{(\text {prev })}(z) \end{aligned} $$在前面的算法中,我们直接使用细致平衡构造稳态分布,但是对于一个Markov链是否会收敛到稳态分布,以及稳态分布是否可以用来推断缺一无所知,我们接下来回答这两个问题。
对于连续时间Markov链,为了利于问题的分析,我们引入一个“最小单元”:
定义 (Atom). 一个集合 $A \subseteq \mathcal{X}$ 被称为一个 原子(atom),如果存在一个概率测度 $\nu$ 使得对于所有 $x \in A$ 和所有 $B \in$ $\mathcal{B}$ 有:$P(x, B)=\nu(B)$
也就是说:
- 从集合 A 中的任何状态出发,下一步转移的分布是完全一样的,等于 $\nu$ ;
- 因此,集合 $A$"忘记了"进入这个集合前的所有历史,是一个概率上的再生点(regeneration point)。
于是我们可以进而讨论Atom的暂态和常返态,对于MCMC,我们自然希望所有的状态都是常返态,我们将使用更强力的定义来作为以后的条件。
定义(Harris recurrent). 链 $\left\{X_n\right\}$ 被称为是 Harris recurrent,如果它是 $\phi$-不可约的,并且满足: 对于所有 $A \in \mathcal{B}$ 满足 $\phi(A)>0$ ,对所有初始状态 $x \in \mathcal{X}$ ,几乎必然无限次访问 $A$ :
$$ \mathbb{P}_x\left(X_n \in A \text { infinitely often }\right)=1 $$换句话说: 所有测度为正的集合 $A$ ,链几乎总会返回无数次。
在 Harris recurrent 基础上,若存在不变概率测度 𝜋,则成Markov链为 Positive Harris recurrent.
定理(收敛定理). 任意Positive Harris recurrent且非周期的Markovb链,对于所有初始状态 $x \in \mathcal{X}$ ,转移概率 $P^n(x, \cdot)$ 弱收敛到不变测度 $\pi$ :
$$ \lim _{n \rightarrow \infty}\left\|P^n(x, \cdot)-\pi(\cdot)\right\|_{T V}=0 $$这里 $\|\cdot\|_{T V}$ 表示 全变差距离(total variation distance)。
收敛定理表明了满足一定条件下的Markov链可以收敛到稳态分布,我们之前推导出来过M-H算法的转移核,可以验证其复合收敛定理的假设。
细致平衡只能保证 π 是不变分布(stationary distribution),但不能保证马尔可夫链从任意初始状态收敛到 π。而我们做推断时关心的是收敛性,所以还需要 Harris recurrence 等条件。
定理(遍历性定理). 设 $\left\{X_n\right\}$ 是 positive Harris recurrent 且 aperiodic 的 Markov 链,不变分布为 $\pi$ 。那么, 对任何 $f \in L^1(\pi)$ ,有:
$$ \lim _{n \rightarrow \infty} \frac{1}{n} \sum_{k=0}^{n-1} f\left(X_k\right)=\int f d \pi \quad \text { a.s. } \quad \forall X_0=x $$遍历性定理对标的是SLLN,但是这并不是trivial的,因为SLLN要求随机样本,是iid的,但是对于Markov链,样本是强相关的,正因为有了Markov链的遍历性定理,才让我们的采样得以发挥作用,使用生成的后验分布样本去计算一些统计量,这些统计量是一致的。
M-H算法和Gibbs算法是最简单的MCMC算法,其对假设的要求都是最弱的,也容易验证其收敛定理和遍历性定理都是成立的,但是对于一些更复杂的算法,这两个定理未必会成立,这时就需要具体问题具体分析,去检查MCMC带来的误差了。
在实际的数值实验中,MCMC会有各种各样的问题,不同分布的处理方式也多种多样,很可能会碰到MCMC不能良好采样的问题,例如当分布不一致有界时,M-H算法拒绝率可能会很高,甚至最后也不会收敛。
Sequential Monte Carlo
在重要性采样中我们曾经提到过,对于高维分布,重要性采样效率极低,序贯蒙特卡洛采样就是利用重要性采样解决高维采样的一种方法。
Exact Inference
Direct Posterior Calculation
共轭模型可以直接求出后验分布。例如,正态模型和贝塔共轭先验中的更新都能用有限个参数表示。
Belief Propagation
在树形因子图中,sum–product 算法通过传递局部消息计算精确边缘分布。变量节点将其他邻居传来的消息相乘。因子节点将相应消息与局部因子相乘,再对接收变量之外的变量求和或积分。有环图上的同类迭代通常用于近似推断。
Posterior Sampling
Markov Chain Monte Carlo 可以直接以后验分布为平稳分布。在满足收敛条件时,长链上的样本平均可估计后验期望,有限次抽样仍有蒙特卡洛误差。
Expectation–Maximization
本章节主要参考李航的统计学习方法,讲的并不是很贝叶斯,但是原理其实差不多,贝叶斯视角可以将隐变量当成先验分布。
对于含有隐变量的概率模型参数的极大似然或最大后验估计,这里不会详细的推导EM算法,而是讲主要的思想和结果列出。
期望最大化(EM)算法,主要用来解决完全数据未知,即含有隐变量情况下的最大似然估计,有
$L(\theta)\geq B(\theta,\theta^{(i)})$ 采用下方迭代
$$ \begin{aligned} \theta^{(i+1)} &= \operatorname*{arg\,max}_\theta B(\theta,\theta^{(i)})\\ & =\arg \max _\theta\left(\sum_Z P\left(Z \mid Y, \theta^{(i)}\right) \log P(Y, Z \mid \theta)\right) \\ & =\arg \max _\theta Q\left(\theta, \theta^{(i)}\right) \end{aligned} $$$Y$ 为数据,$Z$ 为隐变量,$Q\left(\theta, \theta^{(i)}\right)$ 为完全数据的条件似然,EM算法就是最大化完全数据的条件似然的算法,可以优化似然的下界,给出EM算法的形式如下:
定理 1(EM的似然函数递增). 设 $P(Y \mid \theta)$ 为观测数据的似然函数,$\theta^{(i)}(i=1,2, \cdots)$ 为 EM 算法得到的参数估计序列,$P\left(Y \mid \theta^{(i)}\right)(i=1,2, \cdots)$ 为对应的似然函数序列,则 $P\left(Y \mid \theta^{(i)}\right)$ 是单调递增的,即
$$ P\left(Y \mid \theta^{(i+1)}\right) \geqslant P\left(Y \mid \theta^{(i)}\right) $$注. 事实上,大多数似然函数是有上界的,这也保证了一般EM算法会收敛,但是能否收敛到全局最大值是没有保证的,另外,EM算法对初始值的选取非常敏感。
可以用F函数来解释EM算法,并且给出GEM(广义EM)算法。
定义 2( $\boldsymbol{F}$ 函数). 假设隐变量数据 $Z$ 的概率分布为 $\tilde{P}(Z)$ ,定义分布 $\tilde{P}$ 与参数 $\theta$ 的函数 $F(\tilde{P}, \theta)$ 如下:
$$ F(\bar{P}, \theta)=E_{\tilde{P}}[\log P(Y, Z \mid \theta)]+H(\tilde{P}) $$称为 $F$ 函数。式中 $H(\tilde{P})=-E_{\tilde{P}} \log \tilde{P}(Z)$ 是分布 $\tilde{P}(Z)$ 的熵。
定理 3(F函数的最大值意味着似然的最大值). 设 $L(\theta)=\log P(Y \mid \theta)$ 为观测数据的对数似然函数,$\theta^{(i)}, i=1,2, \cdots$ ,为 EM 算法得到的参数估计序列。如果 $F(\tilde{P}, \theta)$ 在 $\tilde{P}^\*$和 $\theta^\*$ 有局部极大值,那么 $L(\theta)$ 也在 $\theta^\*$ 有局部极大值。类似地,如果 $F(\tilde{P}, \theta)$ 在 $\tilde{P}^\*$和 $\theta^\*$ 达到全局最大值,那么 $L(\theta)$ 也在 $\theta^\*$ 达到全局最大值。
定理 4(MM算法). EM 算法的一次迭代可由 $F$ 函数的极大-极大算法实现,设 $\theta^{(i)}$ 为第 $i$ 次迭代参数 $\theta$ 的估计,$\tilde{P}^{(i)}$ 为第 $i$ 次迭代函数 $\tilde{P}$ 的估计。在第 $i+1$次选代的两步为:
(1)对固定的 $\theta^{(i)}$ ,求 $\tilde{P}^{(i+1)}$ 使 $F\left(\tilde{P}, \theta^{(i)}\right)$ 极大化;
(2)对固定的 $\tilde{P}^{(i+1)}$ ,求 $\theta^{(i+1)}$ 使 $F\left(\tilde{P}^{(i+1)}, \theta\right)$ 极大化。
注. 事实上,若对隐变量的估计 $\tilde{P}(Z)$ 取到最优,此时 $F\left(\tilde{P}^{(i+1)}, \theta\right)=Q\left(\theta, \theta^{(i)}\right)+H\left(\tilde{P}^{(i+1)}\right)$ ,再对 $\theta$ 优化等价于EM算法,所以说MM算法是EM算法的拓展版本。
利用MM算法,我们可以搞出其他的GEM算法,例如,考虑 $Q$ 函数不好优化,在M步可以每次不取到最优,而是有改进即可;或者在M步的时候每次对满条件分布进行优化,即估计其他参数,只对一个参数进行优化,再按这种步骤把参数全部优化一遍完成M步,这种方式与变分推断中的CAVI方法非常像,我们会在变分推断的章节中谈一谈VI和EM算法的关系,以及推广EM算法到变分EM算法。
Remark: The Exact E-Step
标准 EM 的 E 步在当前参数下对隐变量的条件分布取期望。这里的“精确”指条件期望使用真实的条件分布。EM 的目标是最大化观测数据似然,迭代也可能收敛到局部最优。
Approximate Inference
当后验分布难以直接计算时,可以用拉普拉斯近似或变分推断构造一个更容易处理的近似分布。
本章节主要介绍Laplace近似和变分推断,有一个写的不错的ppt: The Laplace Approximation and Variational Inference, Cambridge University.
Laplace Approximation
Laplace 近似先找到后验密度的一个众数,再在该点对数后验做二阶泰勒展开。如果负 Hessian 正定,其逆矩阵就是近似高斯分布的协方差。
下图来自本节引用的讲义。
Remark: Local Nature of the Approximation
近似只描述众数附近的曲率。如果后验有多个明显的峰,一个高斯分布通常只能反映其中一个峰附近的形状。
Variational Inference
变分推断先选定一个容易计算的分布族,再通过优化选择其中的近似后验。近似的表达能力取决于所选分布族。
先介绍两篇不错的paper,介绍的非常清晰:
变分推断的出发点非常简单,在合适的分布族中任选分布,使得该分布和后验分布之间的KL散度最小,即
$$ \min_q KL(p(z\mid x)\mid\mid q(z)) = \min_q \mathbb{E}_p \log\frac{p(z\mid x)}{q(z)} $$但是这里依然需要用到后验分布的具体形式,我们是不能知道后验分布的,为了尽可能减少后验分布的出现,我们考虑反向KL散度(KL散度并不是距离):
$$ \min_q KL(q(z)\mid\mid p(z\mid x)) = \min_q \mathbb{E}_q \log\frac{q(z)}{p(z\mid x)} $$这样虽然看着后验分布占比比较少,但是还是规避不了使用后验分布,其实后验分布之所以难以知道,并不是因为似然和先验分布,而是因为归一化常数难以计算,如果该归一化常数与优化问题无关就好了,继续对该式进行处理:
$$ \begin{aligned} KL(q(\mathbf{z}) \| p(\mathbf{z} \mid \mathbf{x}))&=\mathbb{E}_q[\log q(\mathbf{z})]-\mathbb{E}_q[\log p(\mathbf{z}, \mathbf{x})]+\log p(\mathbf{x}) \\ & = -ELBO(q)+\log p(\mathbf{x}) \end{aligned} $$考虑对 $q$ 的优化问题,可见确实与归一化常数无关,且最小化KL散度等价于最大化ELBO,这样在只有似然和先验分布的条件下,我们也可以对该问题做优化了,在优化之前,我们先用另外一种形式表达ELBO,观察其蕴含的另外意义:
$$ \begin{aligned} \log p(x) & =\log \int_{z \in Z} p(x, z) \mathrm{d} z \\ & =\log \int_{z \in Z} p(x, z) \frac{q(z)}{q(z)} \mathrm{d} z, \\ & =\log \mathbb{E}_{z \sim Q(z)}\left[\frac{p(x, z)}{q(z)}\right], \\ & \geq \mathbb{E}_{z \sim Q(z)}[\log p(x, z)]-\mathbb{E}_{z \sim Q(z)}[\log q(z)] \\ & \geq \operatorname{ELBO}(Q) . \end{aligned} $$可见,最大化ELBO,在某种意义上,提供了似然函数的下界,也可以作为最大似然的证据。
现在来对最大化ELBO问题进行求解,这时泛函上的优化,需要用变分方法进行求解,这里不列出变分过程了,就是变分等于零,最后可以得到:$q^{\*}(z) \propto p(x, z)\propto p(z\mid x)$ 结果是既在意料之外也在情理之中的,既然做后验估计,那么最好的估计就是后验分布本身,也是挺有戏剧性的,这又回到了一开始的矛盾上,不知道后验分布,怎么使用后验分布呢,这又引出了变分推断的另外一个核心点:在限制的分布族下最最优化。
我们在之前为了简单,将正向KL散度换成了反向的KL散度,这带来什么影响了呢,我们为什么要用反向KL散度呢,对于正向KL散度,如果将表达式写出来的话,为了保证KL散度的存在性,需要有$supp(p)\subseteq supp(q)$,这将会使得偏向于估计后验分布的均值,对于反向KL散度,需要有$supp(q)\subseteq supp(p)$,这表明我们构造的分布支撑集是更小的,偏向于估计后验分布的模态,而后者才是统计推断中更需要的,如果仅仅得到一个均值上正确的估计,我们会失去更多的性质。
既然有了对分布集的界定,接下来就是做优化了,在分布集限制下的优化是一个非常困难的问题,一般是需要神经网络去学习的(可以参考diffuison和VAE),为了得到更好的解析性质,我们进而讨论平均场假设下的变分推断。
平均场假设也特别简单,就是假设 $q(z)$ 的各个维度独立,忽略其维度之间的相关性,再对ELBO进行处理:
该优化问题我们之前遇到过,用同样的变分方式对其进行求解,可以得到最优解公式:
$$ q_j^{\*}\left(z_j\right) \propto \exp \left(\mathbb{E}_{q_{-j}}[\log p(x, z)]\right) \propto \exp \left(\mathbb{E}_{q_{-j}}[\log p(z_j\mid z_{-j}, x)]\right) $$虽然这也是后验分布的形式,但是在对目标分布做假设之后求取隐变量,是近似可解的,对于每一个变量都是取最优,并且是互相依赖的满条件分布形式,很自然的需要使用迭代法,这里的迭代法命名为坐标上升变分推断,详见下图:
精确执行每个坐标更新时,ELBO 单调不减。如果 ELBO 有上界,其数值会收敛。最终结果可能依赖初值。
讨论.
- VI与EM算法:一个使用了精确后验,一个使用近似后验,考虑下一个小节描述的变分EM算法,其实变分推断可以看作EM算法在使用近似后验下的推广,也可以使用MM算法进行解释。
- CAVI与Gibbs采样:都使用了满条件分布,迭代形式非常一致(特别是二维的情况,几乎一样),但是本质目的不同,一个为了产生样本,一个为了近似推断,这也反应了我们的近似推断是合理的,在某些条件下可以逼近精确推断。
Variational EM
变分推理中,可以通过迭代的方法最大化证据下界,这时算法是 EM 算法的推广,称为变分 EM 算法。
假设模型是联合概率分布 $p(x, z \mid \theta)$ ,其中 $x$ 是观测变量,$z$ 是隐变量,$\theta$ 是参数。目标是通过观测数据的概率(证据) $\log p(x \mid \theta)$ 的最大化,估计模型的参数 $\theta$ 。使用变分推理,导入平均场 $q(z)=\prod_{i=1}^n q\left(z_i\right)$ ,定义证据下界
$$ ELBO(q, \theta)=E_q[\log p(x, z \mid \theta)]-E_q[\log q(z)] $$通过迭代,分别以 $q$ 和 $\theta$ 为变量对证据下界进行最大化,就得到变分 EM 算法:
- E 步。固定 $\theta$,在选定的分布族内更新 $q$,以提高 ELBO。
- M 步。固定 $q$,更新 $\theta$,以提高同一个 ELBO。
- 重复上述步骤,直到 ELBO 的变化足够小。
Remark: What Increases During Variational EM
两步都以 ELBO 为目标,因此每轮迭代的 ELBO 不下降。只有在变分分布等于当前参数下的真实后验时,ELBO 才等于观测数据的对数似然。受限分布族下,ELBO 的单调性不足以推出观测似然也单调。
EM 算法实际也是对证据下界进行最大化。联系 MM 算法,则其中的 F 函数就是ELBO。 EM 算法假设 $q(z)=p(z \mid x)$ 且 $p(z \mid x)$ 容易计算,而变分 EM 算法则考虑一般情况使用容易计算的平均场 $q(z)=\prod_{i=1}^n q\left(z_i\right)$ 。当模型复杂时,EM 算法末必可用,但变分 EM 算法仍然可以使用。
Gaussian Processes
参考:张灏老师随机过程
这里借鉴了张灏老师的课程,介绍了高斯的线性性质,条件高斯分布,高斯的高阶矩等等。
Gaussian过程的定义很简单,任意有限维的随机变量都服从联合高斯分布的过程,对比随机分析中的布朗运动,可见布朗运动是一类特殊的高斯过程。
Gaussian 过程的特征函数如下:
$$ \varphi_{\mathbf{X}}(\mathbf{t})=\mathbb{E}\left[e^{i \mathbf{t}^{\top} \mathbf{X}}\right]=\exp \left(i \mathbf{t}^{\top} \boldsymbol{\mu}-\frac{1}{2} \mathbf{t}^{\top} \boldsymbol{\Sigma} \mathbf{t}\right), \quad \mathbf{t} \in \mathbb{R}^n $$定理(Gaussian过程的线性性质). $\mathbf{X} \sim \mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ ,对任意线性变换 $\mathbf{Y}=A \mathbf{X}+\mathbf{b}$ ,其中 $A \in \mathbb{R}^{m \times n}, ~ \mathbf{b} \in \mathbb{R}^m$ ,则:
$$ \mathbf{Y} \sim \mathcal{N}\left(A \boldsymbol{\mu}+\mathbf{b}, A \boldsymbol{\Sigma} A^{\top}\right) $$联合高斯具有线性性质,但是高斯的组合未必是高斯,见如下定理:
定理(边缘高斯到联合高斯). 以下两种情况可以判断由边缘分布到联合分布的高斯性质:
(1)若 $X_1,\cdots,X_n$ 独立且均为Gaussian,则联合Gaussian。
(2)$\forall \alpha\in \mathbb{R}^n,\alpha^TX\sim N\iff $ 联合高斯。
在数理统计中有一个基本定理,就是样本均值 $\bar{X}$ 和样本方差 $S$ 相互独立,张老师在课堂上对于Gaussian分布验证了该定理,这里不详细写出该例子,总之构造了一些随机变量,最后发现 $S$ 的自由度为 $n-1$,$\bar{X}$ 自由度为1,显示了二者独立,且 $n-1$ 的出现给样本方差的分母本质带来了更有意思的解释。
定理(条件高斯分布). 设随机向量:
$$ \left[\begin{array}{l} \mathbf{X} \\ \mathbf{Y} \end{array}\right] \sim \mathcal{N}\left(\left[\begin{array}{l} \boldsymbol{\mu}_X \\ \boldsymbol{\mu}_Y \end{array}\right],\left[\begin{array}{ll} \boldsymbol{\Sigma}_{X X} & \boldsymbol{\Sigma}_{X Y} \\ \boldsymbol{\Sigma}_{Y X} & \boldsymbol{\Sigma}_{Y Y} \end{array}\right]\right) $$若 $\boldsymbol{\Sigma}_{YY}$ 可逆,则给定 $\mathbf{Y}=\mathbf{y}$,条件分布为 $\mathbf{X}\mid\mathbf{Y}=\mathbf{y}\sim\mathcal{N}(\boldsymbol{\mu}_{X\mid Y},\boldsymbol{\Sigma}_{X\mid Y})$。条件均值与协方差分别为
$$ \begin{aligned} \boldsymbol{\mu}_{X\mid Y} &=\boldsymbol{\mu}_X+\boldsymbol{\Sigma}_{XY}\boldsymbol{\Sigma}_{YY}^{-1}(\mathbf{y}-\boldsymbol{\mu}_Y),\\ \boldsymbol{\Sigma}_{X\mid Y} &=\boldsymbol{\Sigma}_{XX}-\boldsymbol{\Sigma}_{XY}\boldsymbol{\Sigma}_{YY}^{-1}\boldsymbol{\Sigma}_{YX}. \end{aligned} $$注. (1)该定理由矩阵求逆公式和条件pdf的定义直接导出,矩阵求逆公式对于Gaussian分布来说本质是在配方。
(2)条件均值和协方差的形式非常有趣:条件均值是MSE下的最优估计,条件的信息以投影的形式加入原始信息,只有Gaussian才有如此好的条件期望,可以简单的线性预测;条件协方差在矩阵正定的意义下变小,说明随着信息的增大,未知在减小。
接下来讨论Gaussian分布的高阶矩,包括线性和非线性处理。
定理(一元Gaussian的高阶矩). 令随机变量 $X \sim \mathcal{N}\left(\mu, \sigma^2\right)$ ,则奇数阶中心矩为0,偶数阶中心矩为
$$ \mathbb{E}\left[(X-\mu)^{2 n}\right]=(2 n-1)!!\cdot \sigma^{2 n} $$其中 $(2 n-1)!!=1 \cdot 3 \cdot 5 \cdots(2 n-1)$ 是奇数阶双阶乘。
注. 该定理为直接积分然后递推得出,与点火公式的推导很像。
定理(Isserlis 定理). 设 $X_1, \ldots, X_{2 n}$ 是 零均值的多元高斯变量,即:
$$ \left(X_1, \ldots, X_{2 n}\right) \sim \mathcal{N}(0, \Sigma) $$则:
$$ \mathbb{E}\left[X_1 X_2 \ldots X_{2 n}\right]=\sum_{\text {all pairings }} \prod_{(i, j)} \mathbb{E}\left[X_i X_j\right] $$其中:
- 每个配对(pairing)是将 $\{1,2, \ldots, 2 n\}$ 分成 $n$ 个两两不重叠的对子;
- 总共有 $(2 n-1)$ !!个这样的配对;
- 对每个配对,取所有对应协方差的乘积;
- 奇数阶的高阶矩为0。
注. Isserlis定理反应了Gaussian的高阶矩由二阶协方差决定,这很符号高斯分布完全依赖于均值和方差的事实。
Isserlis定理与free cumulants的定理非常的像,在cumulants的意义下,也有以下类似的更一般的定理,不依赖于Gaussian分布,在介绍该定理之前,需要先介绍累积量,累积量一般可以写成矩的组合。
定义(累积量). 设 $X$ 是一个随机变量,它的矩母函数(moment generating function)是:
$$ M_X(t)=\mathbb{E}\left[e^{t X}\right] $$则定义其 累积生成函数(cumulant generating function) 为:$K_X(t)=\log M_X(t)$ 第 $n$ 阶累积量 $\kappa_n$ 就是 $K_X(t)$ 在 $t=0$ 处的 $n$ 阶导数:
$$ \kappa_n=\left.\frac{d^n}{d t^n} \log \mathbb{E}\left[e^{t X}\right]\right|_{t=0} $$注. 累积量是相比于矩更加高阶的工具,可以更好的反应随机变量的结构性,是最小生成集,无冗余信息,另外,在随机矩阵等非交换概率工具中,还会有自由累积量(free cumulants),在理论分析中具有更大的用处。最后,累积量天然与图论有关,所以在概率图模型中也具有重大作用。
定理(Leonov–Shiryaev 定理). 设 $X_1, \ldots, X_n$ 是一组随机变量,则:
$$ \mathbb{E}\left[X_1 X_2 \cdots X_n\right]=\sum_{\pi \in \mathcal{P}(n)} \prod_{B \in \pi} \kappa(B) $$其中:
- $\mathcal{P}(n)$ 是 $\{1,2, \ldots, n\}$ 的所有划分(partition);
- 对每个划分 $\pi=\left\{B_1, \ldots, B_k\right\}$ ,其中每个 $B_j \subset\{1, \ldots, n\}$ ,我们定义: $$ \kappa\left(B_j\right)=\text { Cumulant of the random variables indexed by } B_j $$ 即,对每个子集 $B=\left\{i_1, \ldots, i_m\right\}$ , $$ \kappa(B):=\kappa\left(X_{i_1}, \ldots, X_{i_m}\right) $$
接下来的定理有利于求解Gaussian通过非线性函数作用的期望。
定理(Price 定理). 假设:
- $X=\left(X_1, \ldots, X_n\right)^T \sim \mathcal{N}(0, \Sigma)$ ,一个零均值的高斯随机向量,协方差矩阵为 $\Sigma$(正定);
- $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是一个满足一定光滑条件的函数,比如可微且被期望包络(技术条件保证期望和导数可以交换);
则Price 定理表明:
$$ \frac{\partial}{\partial \Sigma_{i j}} \mathbb{E}[f(X)]=\frac{1}{2} \mathbb{E}\left[\frac{\partial^2 f(X)}{\partial x_i \partial x_j}\right] $$注. 一般我们需要分析Gaussian经过非线性系统后的分布,主要是一阶矩和二阶矩,即Price定理左边的项(除去求导),利用Price定理,一般右侧的项容易求,然后再求解一个初值ODE问题即可得到 $\mathbb{E}[f(X)]$。
References
- 教材:应用随机过程,Ross
- 教材:统计机器学习,李航
- 网页:统计计算
- 网页:Advanced Statistical Computing.
- 网页:Markov chain Monte Carlo methods
- b站up:徐芝兰.
- b站课程:随机过程 张颢 2024年春
课程来源:张颢老师《现代信号处理》:贝叶斯信号处理。


