基于近似渐近方差与分数提议数的自适应提议数迭代抽样重要性重采样（i-SIR）算法

《Stochastic Processes and their Applications》：Iterated sampling importance resampling with adaptive number of proposals

　　

迭代抽样重要性重采样（iterated sampling importance resampling, i-SIR）是一种基于 N 个独立提议（proposal）的马尔可夫链蒙特卡罗（Markov chain Monte Carlo, MCMC）算法。随着 N 增大，其样本趋于近似独立，但计算成本随之增加。研究人员讨论一种方法，从渐近效率（asymptotic efficiency）角度寻找近似最优的提议数 N。最优 N 取决于 i-SIR 链的混合性质（mixing properties）以及（并行）计算成本。研究人员用于寻找合适 N 的方法基于 i-SIR 的一个近似渐近方差（approximate asymptotic variance），该近似方差具有与 i-SIR 渐近方差类似的性质，并基于具有分数“提议数”（fractional “number of proposals”）的广义 i-SIR 转移（generalised i-SIR transition）。这些结果导出一个自适应 i-SIR（adaptive i-SIR）算法，可在采样过程中自动调节提议数。研究人员的实验表明，其近似效率（approximate efficiency）和自适应 i-SIR 算法具有良好的经验表现（empirical behaviour）。研究人员还给出关于 i-SIR 的新理论结果，例如渐近方差关于提议数的凸性（convexity），该结果可能具有独立兴趣。

Pietari Laitinen 与 Matti Vihola 的论文研究在重要性采样（importance sampling，一种以提议分布加权估计目标期望的方法）框架下，如何为迭代抽样重要性重采样（i-SIR，一种基于独立提议并迭代重采样的 MCMC 方法）自动选择提议数 N。研究背景是：i-SIR 基于 N 个独立提议，N 增大时样本趋于近似独立但计算成本增加；i-SIR 可产生无权样本，也可用于自归一化重要性采样的预烧或潜变量模型中的马尔可夫更新；与分组独立 Metropolis–Hastings（GIMH）不同，i-SIR 的混合行为可随 N 增大而改善。存在的问题是：最优 N 同时取决于 i-SIR 链的混合性质与（并行）计算成本；真实渐近方差（asymptotic variance，衡量 MCMC 估计长期效率的方差常数）未知且难以估计，多测试函数时更复杂。因此，研究人员提出自适应 i-SIR，以成本加权近似渐近方差为目标自动调节 N，并给出理论保证与实验验证；其意义在于提供可自动选择提议数且保持估计一致性的实用算法，同时建立渐近方差关于提议数的凸性等理论结果。

关键技术方法（不超过250字）：采用 i-SIR 及其分数提议数连续松弛（continuous relaxation，将整数提议数扩展为实数）；以平均拒绝概率构造近似转移 P?_λ；采用成本函数 c(λ)=a+bλ 与逆相对效率（inverse relative efficiency，成本乘以渐近方差）；用随机逼近（stochastic approximation，以含噪观测迭代求解）自动更新 λ=1+e^ξ，步长 γ_k=k^?β（β=0.75），并投影到 [2,N_max]；有限状态空间用谱分解直接计算或蒙特卡洛估计；混合模型维度 d=7、10；贝叶斯 logistic 回归使用 Wisconsin Diagnostic Breast Cancer 数据集（569 名患者，30 个协变量加截距，Gaussian 先验 N(0,20I₃₁)，防御性混合提议）；Julia 实现并采用四线程。

研究结果：2. i-SIR算法：定义了基于 N 个提议的转移概率及分数提议数 λ 的连续松弛算法。3. i-SIR的性质：在权重有界假设下给出强 minorisation 条件，说明中心极限定理成立，并证明渐近方差 var(P_λ, f) 有界、关于 λ 严格递减且凸。4. 基于平均接受率的整体效率与近似：以 c(λ)=a+bλ 定义成本，并用平均拒绝概率 ?(λ) 构造近似转移 P?_λ，得到显式近似渐近方差及其与真实渐近方差相似的界、凸性和单调性。5. 提议数的自适应：构造损失 L?(λ)=c(λ)(1+?(λ))/(1??(λ))，给出近似梯度与 Algorithm 3；Theorem 7 证明自适应算法对任意有界可测测试函数满足强相合（strong law of large numbers，样本平均几乎必然收敛到目标期望）。6. i-SIR协方差和接受率的凸性与单调性：通过对称性与二次型表示证明协方差和拒绝概率随 N 的单调性与序列凸性，并推广到连续松弛。7. 渐近方差：证明 I?P_λ 在 L₀²(π) 上可逆，并由 Dirichlet 型得到 λ?var(P_λ, f) 严格凸且递减。8. 有原子情形下的近似i-SIR：给出基于 ψ(λ) 的近似转移 Q?_λ 及相应渐近方差性质。9. 实验：9.1 有限状态空间中渐近方差近似的质量：Experiment 1 在小状态空间直接计算，子优因子接近1，近似良好；Experiment 2 的权重上界约430.99，近似与真实方差差异明显，最小化点可相差约十倍且子优因子增大；Experiment 3 将状态6的概率质量较 Experiment 2 缩小1000倍，多数测试函数结果类似 Experiment 1，说明大权重点不常出现时近似仍有用，但集中在极端权重上的 k? 出现类似 Experiment 2 的差异；Experiment 4 的权重上界约2.50，g? 与 l? 的极端值落在链不常访问的状态5，大 a 时成本最小化器远小于近似，其余函数结果相近；Experiment 5 对 [?3,3] 上61个等距状态离散化并用蒙特卡洛估计，子优因子相对较小，g? 最高但随 a 增大而变小。9.2 Mixture distribution（混合分布）：在 d=7、10 的 Gaussian 混合目标上运行自适应 i-SIR，用 IACT 与 IRE 估计评估，适应过程最小化近似 IRE，并近似最小化第二个测试函数的 IRE；第一个测试函数需更多提议数，但效率损失不大。9.3 Logistic regression（logistic 回归）：在 Wisconsin 数据集上运行自适应算法，适应过程似乎最小化近似 IRE，第一个测试函数的 IACT 与 IRE 形状与近似一致，第二个测试函数大致被最小化，但其 IACT 估计仍有波动，无法得出明确结论。

讨论与结论：论文总结其提出的是基于接受率渐近方差近似的自适应提议数 i-SIR 算法；该近似渐近方差具有与真实 i-SIR 渐近方差相似的凸性和单调性，实验表明其常能给出合适的提议数选择。研究结论翻译如下：研究人员提出了一种具有自适应提议数的 i-SIR 算法，其基于以接受率为基础的渐近方差近似。该近似渐近方差具有与真实 i-SIR 渐近方差相似的凸性和单调性，实验表明它通常能导致合适的提议数选择。数值结果说明，在 w^{^}=sup_xw(x) 较大的某些场景中，该近似可能较差；但如果 w(x) 较大的状态并不容易出现，近似仍可有用。针对自适应方法行为的实验确认，该方法在大 w^{^} 下仍可有用，并提示 Experiment 3 中观察到的现象可能对实际场景具有指示意义。