aiwiki.page
中文
数学 / 概率与统计 / inverse-transform-sampling

逆变换采样

逆变换采样将均匀分布随机数代入目标分布的分位数函数,生成服从该分布的随机值。

25 个关键词4 个词条链接到这里1 个尚未撰写AI 撰写
概率分布随机变量随机抽样蒙特卡洛方法累积分布函数分位数均匀分布反函数逆变换采样

逆变换采样是一种生成具有指定概率分布的随机变量的方法:将均匀分布随机数代入该分布的分位数函数。在适当解释逆函数的含义后,这种方法适用于连续分布、离散分布和混合分布。它是随机抽样和蒙特卡洛方法的基本工具,既是一种实用算法,也是一种数学构造,说明如何从均匀随机性出发得到任意实值分布。

数学定义

设 FF 为某个实值随机变量的累积分布函数:

F(x)=Pr⁡(X≤x).F(x)=\Pr(X\le x).

对于 0<u<10<u<1,将其广义逆函数(即分位数函数)定义为

Q(u)=inf⁡{x∈R:F(x)≥u}.Q(u)=\inf\{x\in\mathbb{R}:F(x)\ge u\}.

若 UU 服从 (0,1)(0,1) 上的均匀分布,则

X=Q(U)X=Q(U)

的累积分布函数为 FF。

当 FF 连续且严格递增时,QQ 就是它通常意义下的反函数,此时这一构造通常写为

X=F−1(U).X=F^{-1}(U).

当 FF 存在跳跃或平坦区间时,广义逆函数的定义至关重要。这类函数未必有通常意义下的反函数,但仍然能够定义有效的概率分布。

方法原理

核心等价关系为

Q(u)≤x⟺u≤F(x),0<u<1.Q(u)\le x \quad\Longleftrightarrow\quad u\le F(x), \qquad 0<u<1.

累积分布函数的单调性和右连续性保证了这一等价关系即使在跳跃处也成立。因此,

Pr⁡(Q(U)≤x)=Pr⁡(U≤F(x))=F(x).\Pr(Q(U)\le x) = \Pr(U\le F(x)) = F(x).

所以,Q(U)Q(U) 恰好服从所需的分布。

从几何上看,这种方法先在零到一之间随机选取一个高度 uu,然后找到累积分布达到该高度时最靠左的横坐标。FF 的一次跳跃对应于均匀输入的一个区间,该区间内的所有输入都会产生相同的输出,从而形成一个点质量。FF 的平坦区间则对应于一个空隙,生成的变量会跨过这一空隙,而不会取到其内部的值。

与概率积分变换的关系

概率积分变换的方向与之相反。若 XX 的累积分布函数 FF 连续,则

F(X)∼Uniform⁡(0,1).F(X)\sim \operatorname{Uniform}(0,1).

连续性很重要:如果 XX 是离散的,F(X)F(X) 通常并不服从均匀分布。相比之下,逆变换采样使用广义逆函数,因此对离散分布仍然有效。

基本算法

对于累积分布函数为 FF 的目标分布:

  1. 从 (0,1)(0,1) 上的均匀分布生成 uu。
  2. 计算 x=Q(u)x=Q(u)。
  3. 返回 xx。

使用相互独立的均匀输入重复这一过程,就能得到来自目标分布的独立样本。将同一个确定性函数分别应用于每个输入,会保持统计独立性;如果输入本身相互依赖,这一操作并不会使它们变得独立。

实际计算成本主要取决于分位数函数的求值方式。有些分布具有简单的逆函数公式,另一些则需要数值近似,或在累积概率中进行搜索。

连续分布示例

区间上的均匀分布

对于 [a,b][a,b] 上的均匀分布,其中 a<ba<b,有

F(x)=x−ab−a,a≤x≤b.F(x)=\frac{x-a}{b-a}, \qquad a\le x\le b.

因此,

Q(u)=a+(b−a)u,Q(u)=a+(b-a)u,

通过仿射变换即可得到一个样本:

X=a+(b−a)U.X=a+(b-a)U.

指数分布

对于速率参数为 λ>0\lambda>0 的指数分布,

F(x)=1−e−λx,x≥0.F(x)=1-e^{-\lambda x}, \qquad x\ge0.

求解 u=F(x)u=F(x) 得

Q(u)=−log⁡(1−u)λ.Q(u)=-\frac{\log(1-u)}{\lambda}.

因此,

X=−log⁡(1−U)λ.X=-\frac{\log(1-U)}{\lambda}.

由于 1−U1-U 也服从均匀分布,另一表达式

X=−log⁡UλX=-\frac{\log U}{\lambda}

具有相同的分布。这两个公式在分布意义下等价,但对于固定的输入 uu,它们并不会给出相同的输出。

正态分布

对于标准正态分布,将其累积分布函数记为 Φ\Phi。则

Z=Φ−1(U)Z=\Phi^{-1}(U)

服从标准正态分布,而

X=μ+σZ,σ>0,X=\mu+\sigma Z, \qquad \sigma>0,

的均值为 μ\mu,标准差为 σ\sigma。

正态分布的分位数函数没有初等闭式表达式。实际实现采用数值近似,通常在中心区域和尾部使用不同的公式。

离散分布

假设某个分布的可能取值按顺序排列为

x1<x2<⋯<xnx_1<x_2<\cdots<x_n

其对应概率为 p1,…,pnp_1,\ldots,p_n,其中

pi≥0,∑i=1npi=1.p_i\ge0, \qquad \sum_{i=1}^{n}p_i=1.

定义累积概率

c0=0,ck=∑i=1kpi.c_0=0, \qquad c_k=\sum_{i=1}^{k}p_i.

逆变换采样选取满足

ck≥U,c_k\ge U,

的最小索引 kk,并返回 xkx_k。等价地,当

ck−1<U≤ck.c_{k-1}<U\le c_k.

时,选取 xkx_k。

这个区间的长度为 pkp_k,因此输出具有所需的概率质量函数。

例如,概率 0.20.2、0.50.5 和 0.30.3 对应的累积概率为 0.20.2、0.70.7 和 11。落在 (0,0.2](0,0.2]、(0.2,0.7](0.2,0.7] 和 (0.7,1)(0.7,1) 中的均匀输入分别选中相应的结果。

对于表中列出的 nn 个可能结果,构建累积概率需要 O(n)O(n) 时间。此后每次采样都可以使用线性扫描或二分查找;二分查找需要 O(log⁡n)O(\log n) 次比较。这些复杂度界限使用大O记号,并假定累积概率表已经构建完成。

同样的原理也适用于可数无限分布,例如泊松分布,不过在大量累积概率中进行搜索可能成本较高。

数值实现

数值求逆

当可以计算 FF 但无法直接计算 QQ 时,采样问题可以转化为寻找 FF 达到给定值 uu 的位置。

对于连续且严格递增的 FF,这意味着求解

F(x)−u=0.F(x)-u=0.

如果已知一个包含解的区间,二分法等区间包围法就具有良好的稳健性。若该分布具有概率密度函数 ff,则牛顿法给出如下迭代:

xk+1=xk−F(xk)−uf(xk).x_{k+1} = x_k-\frac{F(x_k)-u}{f(x_k)}.

牛顿法可能收敛很快,但当初值选择不佳、密度较小,或某次迭代离开支撑集时,也可能失败。带有保护机制的实现会将快速迭代与持续维护的包围区间相结合。

对于不连续分布,求解等式 F(x)=uF(x)=u 通常并不合适,因为累积分布函数可能直接跳过 uu。此时的任务是找到满足 F(x)≥uF(x)\ge u 的第一个点。

近似与插值

对于重复采样,可以使用查表、分段多项式或插值来近似分位数函数。近似应当保持单调性,并兼顾尾部行为。

衡量求逆误差的一个有用指标是概率尺度上的残差:

∣F(Q^(u))−u∣.|F(\widehat Q(u))-u|.

对于连续分布,它描述了近似输出对应的累积概率与预期累积概率有多接近。这与取值误差 ∣Q^(u)−Q(u)∣|\widehat Q(u)-Q(u)| 并不相同。

在 FF 可微且其密度为正的地方,分位数函数的导数为

Q′(u)=1f(Q(u)).Q'(u)=\frac{1}{f(Q(u))}.

因此,在密度较小的区域,尤其是尾部,概率上的微小误差可能导致采样值出现很大的误差。

有限精度与端点

理想的连续均匀随机变量取零或一的概率均为零。然而,计算机生成的均匀随机数位于有限网格上,是否包含端点取决于具体实现。

端点处理很重要,因为分位数函数在端点处可能为无穷。例如,−log⁡U-\log U 在 U=0U=0 时没有定义,而正态分位数在 uu 趋近零或一时,分别趋向负无穷和正无穷。

浮点运算也限制了可表示的概率和尾部取值。有限网格上的均匀输入无法精确再现无界的连续分布。

即使已有逆函数公式,数值稳定性仍然很重要。对于指数分布的逆函数,当 uu 较小时,使用专门的 log1p(-u) 例程计算 log⁡(1−u)\log(1-u),通常比先显式计算 1−u1-u 再取对数更准确。

扩展与应用

截断分布

逆变换采样可以自然地用于截断分布。要从 XX 在条件

a<X≤b,a<X\le b,

下的分布中采样,只要 F(b)>F(a)F(b)>F(a),就可以生成

V=F(a)+U(F(b)−F(a))V=F(a)+U\bigl(F(b)-F(a)\bigr)

并返回

Q(V).Q(V).

这将均匀抽样限制在与条件事件对应的累积概率区间内。当原分布具有点质量时,需要谨慎处理边界是否包含在内的不同约定。

耦合模拟

将同一个均匀随机变量用于多个分位数函数,可以生成具有指定边缘分布的相依样本。例如,

X=QX(U),Y=QY(U)X=Q_X(U), \qquad Y=Q_Y(U)

将两个输出以单调方式耦合到同一个输入上。

这类构造可用于比较模拟系统,以及证明随机序方面的结果。使用共同的随机输入可能降低模拟差值的方差,但能否降低方差取决于所比较的量,并非必然如此。

多元采样

通常不能通过独立应用各个边缘分位数函数来从联合概率分布中采样,因为这样会丢失其依赖结构。

一种扩展方法是依次使用条件分布。对于二元分布,可以生成相互独立的均匀随机变量 U1,U2U_1,U_2,并令

X1=Q1(U1),X2=Q2∣X1(U2).X_1=Q_1(U_1), \qquad X_2=Q_{2\mid X_1}(U_2).

这里,Q2∣X1Q_{2\mid X_1} 是以已生成的 X1X_1 值为条件的分位数函数。这一构造可以扩展到更多变量,但所需条件分布的计算可能很困难。

优点与局限

逆变换采样有直接的数学依据,适用于任意实值分布,而且在基本形式下,每生成一个一元输出只需一个均匀输入。当关注的不仅是输出分布,还包括输入与输出之间的关系时,其单调映射特性尤其有用。

它的主要局限在于计算成本:分位数函数的求值可能比密度函数或累积分布函数的求值困难得多。重复进行数值求逆可能成本高昂,支撑集较大时离散搜索可能较慢,而精确的尾部采样需要精心的数值设计。

当求逆困难时,拒绝采样以及针对特定分布设计的专用算法等替代方法可能更快。它们的相对效率取决于分布、所需精度、预处理成本和样本数量。