基于马尔可夫链蒙特卡洛方法的空间填充拉丁超立方体样本构造

《Journal of Statistical Planning and Inference》:A Markov chain Monte Carlo construction of space-filling Latin Hypercube Samples

【字体: 大 中 小 】 时间:2026年02月11日 来源:Journal of Statistical Planning and Inference 1.1

编辑推荐:

  拉米·埃尔·哈达德|迪阿拉·韦赫贝|尼古拉斯·威克|马蒂亚斯·怀永·谭 贝鲁特圣约瑟夫大学科学学院数学与建模研究组,数学与应用实验室,黎巴嫩贝鲁特里阿德·埃尔·索尔赫,邮政编码11072050 摘要 本文旨在构建具有更强点间排斥效应的拉丁超立方抽样。我们的主要贡献是

  拉米·埃尔·哈达德|迪阿拉·韦赫贝|尼古拉斯·威克|马蒂亚斯·怀永·谭
贝鲁特圣约瑟夫大学科学学院数学与建模研究组,数学与应用实验室,黎巴嫩贝鲁特里阿德·埃尔·索尔赫,邮政编码11072050

摘要
本文旨在构建具有更强点间排斥效应的拉丁超立方抽样。我们的主要贡献是一种新的马尔可夫链蒙特卡洛算法,该算法能够生成点对之间欧几里得距离较大的拉丁超立方抽样,从而实现更好的分布效果。所提出的算法属于梅特罗波利斯-黑斯廷斯算法,它所定义的马尔可夫链的稳态分布更倾向于那些点间间距较大的抽样结果。该算法的收敛性已得到严格证明。此外,数值实验表明,该算法生成的拉丁超立方抽样具有更优的点分布,相较于传统拉丁超立方设计,能实现采样空间的更均匀覆盖。同时,该方法还能产生点分布更为分散的设计方案(体现为散布度指标值较低),凸显了在高性能设计方案中多样性的重要性。

引言
许多科学和技术领域依赖数学模型来描述复杂系统。这类模型通常具有如下形式:y=h(x),其中x=(x1,…,xn)∈D,x表示定义域D内的输入变量向量,y为输出变量,h:D→R则是将输入映射为实数输出的函数。这类模型在粒子物理学、排队论、数理金融以及数据回归分析等诸多应用中都发挥着重要作用。然而,使用这些模型时面临的一个常见问题是,函数h往往需要通过计算机代码来计算,不存在已知的封闭形式解析表达式。这一限制使得人们不得不借助仿真方法来有效探索输入空间D。

在此背景下,能够均匀覆盖输入空间的空间填充设计是实验设计中的重要工具。这类设计因适合用于计算机实验而备受青睐,可通过基于特定距离优化准则来优化设计点获得。两种常见的基于距离的优化准则是最小最大准则和最大最小准则(Johnson等人,1990),它们在高斯过程模型中分别渐近等价于熵准则和最大预测方差准则。类似地,诸如最小生成树之类的几何方法(Dussert等人,1986)也可用于改善样本的空间排列,进而生成空间填充设计。此外,还有一些生成空间填充设计的方法依赖于基于模型的准则。例如,最大熵设计(Schwery和Wynn,1987)通过熵作为数据压缩的度量标准来评估样本的信息含量。

尤其值得关注的一种方法是拉丁超立方抽样,它由McKay等人(1979)提出,作为拉丁方在更高维空间中的推广形式。n阶拉丁方是一种n×n的表格,其单元格中填充有n种不同的元素,且每种元素在每一行和每一列中仅出现一次。拉丁超立方抽样则是一种n×s矩阵,其中输入空间的维度s不能超过样本数量n,而且从1到n的每个整数在每一列中恰好出现一次。

在实验设计中,拉丁超立方抽样通常会被转换为分布在s维单位立方体[0,1)s内的形式,这样就能得到一个包含n个样本的集合,这些样本在各个坐标轴上的投影都是等距的。当使用这类样本进行蒙特卡洛仿真时,这一约束条件能够降低样本均值估计量的方差。事实上,McKay等人(1979)已经证明,对于那些各参数均为单调函数的积分,基于拉丁超立方抽样的估计量方差要小于传统蒙特卡洛估计量的方差。Stein(1992)的分析进一步表明,对于任何平方可积函数,从渐近意义上来看——即当样本量增大时——拉丁超立方抽样确实能降低方差。Owen(1997)的研究则发现,规模为n的拉丁超立方抽样的方差永远不会超过使用n?1个点的传统蒙特卡洛抽样的方差。

虽然拉丁超立方抽样仅能对一维边际分布进行分层,但人们已经开发出多种方法来增强这种分层效果,以便以理想的方式填充维度为r
另外,还有一种结合了拉丁超立方抽样和分层技术的混合方法,被用来生成所谓的数独拉丁方抽样(slss)(el haddad等人,2012)。研究表明,使用slss得到的估计量方差与简单分层抽样的方差大致相当。然而数值实验显示,与单纯使用简单分层抽样相比,slss不仅能实现更低的方差,还具有更高的效率(el haddad等人,2020)。

最近,sheikholeslami和razavi(2017)提出了一种名为渐进拉丁超立方抽样的采样策略,它是拉丁超立方抽样的序列版本。作者们证明了,在保持均匀性和一维投影特性方面,渐进拉丁超立方抽样优于传统的拉丁超立方抽样。

上述所有方法在处理高维输入空间时,都难以生成具有良好空间填充特性的大规模拉丁超立方抽样。本文提出了一种新的马尔可夫链蒙特卡洛算法,旨在通过增加样本点之间的间距来优化样本的空间分布,从而更全面地探索输入空间。这一创新方法借鉴了morris和mitchell的奠基性工作(morris和mitchell,1995),他们通过将最小最大距离准则与拉丁超立方抽样的特性相结合,改进了计算实验的设计方法。他们还开发了一种模拟退火算法来生成这类设计,力求在最大化最小最大距离准则与保持拉丁超立方抽样的理想投影特性之间取得平衡。

尽管本文深受morris和mitchell(1995)工作的影响,但我们的目标有所不同。morris和mitchell(1995)中的模拟退火算法旨在最小化某个给定的准则,而我们的方法则是根据后文介绍的目标分布来生成均匀分布的样本。此外,我们还对所提算法的收敛性进行了分析,而morris和mitchell(1995)并未做此分析,而且我们还在更高维度、更大样本量的情况下对该算法进行了测试。

本文的其余结构如下:第2节回顾拉丁超立方抽样的性质及其经典的构造算法;第3节介绍所提出的用于构建多维拉丁超立方抽样的梅特罗波利斯-黑斯廷斯算法;第4节分析该算法的收敛性;第5节通过数值实验表明,所提算法生成的抽样具有更均匀的分布和更大的点间距,因此比传统拉丁超立方抽样能实现更好的采样空间覆盖;最后第6节给出结论。

片段摘录
**拉丁超立方抽样的经典构造及缺陷**
我们将规模为n、维度为s(s≤n)的拉丁超立方抽样记为x=(x1,…,xs),其中对于所有的j∈{1,…,s},xj=(xj,1,…,xj,n)?,且xj,i∈{1,…,n}。要生成拉丁超立方抽样,首先需将1到n的整数按升序排列在第一列x1中,随后通过重新排列1到n的整数来形成其余列xj(j∈{2,…,s}),并确保每个整数在每一列中恰好出现一次。根据这种构造方式,共有(n!)^(s?1)种不同的拉丁超立方抽样配置。

**基于马尔可夫链蒙特卡洛的拉丁超立方抽样构造**
设输入空间的维度为s≥2,样本点数量为n。用sn表示{1,…,n}的所有排列集合,用i?(1,…,n)?表示sn中的恒等排列。如前所述,可以将拉丁超立方抽样视为集合ξ?{i}×s???1中的候选元素。为了提高生成能够有效覆盖输入空间{1,…,n}?s且避免点群聚的拉丁超立方抽样的概率,就需要采用一种能够考虑点对之间距离的度量方法。

**算法的收敛性**
要判断前述构建的马尔可夫链向稳态分布π收敛的速度,可以通过限定混合时间来实现,混合时间是指从初始状态x∈ξ开始,链达到目标分布所需的时间。对于给定的正数?,混合时间可表示为τ?(x)=min{t:δx(t′)≤?,对所有t′≥t},其中δx(t)=max{s?ξ | pt(x,s)?π(s)|}表示初始状态为x时,时间t处的变异距离。

**命题1**
状态空间为ξ、稳态分布为π的马尔可夫链,其混合时间满足τ?(x)≤(s?1)2n3p+3log…

**数值测试**
我们的算法旨在生成相比传统构造方法具有更好覆盖效果的拉丁超立方抽样,因此我们通过数值实验来验证其效率。在计算过程中,我们将使用位于s维单位立方体[0,1)s内的样本点。如前所述,要获得这类样本,可以用xj,i?uj,in替换xj,i,其中{uj,i,j∈{1,…,d},i∈{1,…,n}}是一组在[0,1)上均匀分布的独立同分布随机变量。不过,为了降低采样的复杂性……

**结论**
本文提出了一种用于生成维度为s≥2的拉丁超立方抽样的新算法,该算法能够生成相比传统构造方法具有更均匀分布特性的设计。该算法采用了蒙特卡洛马尔可夫链技术,通过模拟具有特定稳态分布的链结构,促使样本点之间保持更大的间距。通过对链的混合时间进行分析,我们发现其收敛速度为多项式级。同时,我们也将其与传统方法进行了比较评估。

**致谢**
在开展本研究的过程中,拉米·埃尔·哈达德获得了法国学院-法国校园项目提供的资助(资助编号:118166r),同时还得到了里尔大学欧洲数学、物理及其相互作用中心的支持。马蒂亚斯·怀永·谭的研究则得到了中国香港特别行政区研究资助委员会的两项资助(一般研究基金项目编号:cityu 11201519和cityu 11209622)。 另外,还有一种结合了拉丁超立方抽样和分层技术的混合方法,被用来生成所谓的数独拉丁方抽样(slss)(el haddad等人,2012)。研究表明,使用slss得到的估计量方差与简单分层抽样的方差大致相当。然而数值实验显示,与单纯使用简单分层抽样相比,slss不仅能实现更低的方差,还具有更高的效率(el haddad等人,2020)。 最近,sheikholeslami和razavi(2017)提出了一种名为渐进拉丁超立方抽样的采样策略,它是拉丁超立方抽样的序列版本。作者们证明了,在保持均匀性和一维投影特性方面,渐进拉丁超立方抽样优于传统的拉丁超立方抽样。 上述所有方法在处理高维输入空间时,都难以生成具有良好空间填充特性的大规模拉丁超立方抽样。本文提出了一种新的马尔可夫链蒙特卡洛算法,旨在通过增加样本点之间的间距来优化样本的空间分布,从而更全面地探索输入空间。这一创新方法借鉴了morris和mitchell的奠基性工作(morris和mitchell,1995),他们通过将最小最大距离准则与拉丁超立方抽样的特性相结合,改进了计算实验的设计方法。他们还开发了一种模拟退火算法来生成这类设计,力求在最大化最小最大距离准则与保持拉丁超立方抽样的理想投影特性之间取得平衡。 尽管本文深受morris和mitchell(1995)工作的影响,但我们的目标有所不同。morris和mitchell(1995)中的模拟退火算法旨在最小化某个给定的准则,而我们的方法则是根据后文介绍的目标分布来生成均匀分布的样本。此外,我们还对所提算法的收敛性进行了分析,而morris和mitchell(1995)并未做此分析,而且我们还在更高维度、更大样本量的情况下对该算法进行了测试。 本文的其余结构如下:第2节回顾拉丁超立方抽样的性质及其经典的构造算法;第3节介绍所提出的用于构建多维拉丁超立方抽样的梅特罗波利斯-黑斯廷斯算法;第4节分析该算法的收敛性;第5节通过数值实验表明,所提算法生成的抽样具有更均匀的分布和更大的点间距,因此比传统拉丁超立方抽样能实现更好的采样空间覆盖;最后第6节给出结论。 片段摘录 **拉丁超立方抽样的经典构造及缺陷** 我们将规模为n、维度为s(s≤n)的拉丁超立方抽样记为x=(x1,…,xs),其中对于所有的j∈{1,…,s},xj=(xj,1,…,xj,n)?,且xj,i∈{1,…,n}。要生成拉丁超立方抽样,首先需将1到n的整数按升序排列在第一列x1中,随后通过重新排列1到n的整数来形成其余列xj(j∈{2,…,s}),并确保每个整数在每一列中恰好出现一次。根据这种构造方式,共有(n!)^(s?1)种不同的拉丁超立方抽样配置。 **基于马尔可夫链蒙特卡洛的拉丁超立方抽样构造** 设输入空间的维度为s≥2,样本点数量为n。用sn表示{1,…,n}的所有排列集合,用i?(1,…,n)?表示sn中的恒等排列。如前所述,可以将拉丁超立方抽样视为集合ξ?{i}×s???1中的候选元素。为了提高生成能够有效覆盖输入空间{1,…,n}?s且避免点群聚的拉丁超立方抽样的概率,就需要采用一种能够考虑点对之间距离的度量方法。 **算法的收敛性** 要判断前述构建的马尔可夫链向稳态分布π收敛的速度,可以通过限定混合时间来实现,混合时间是指从初始状态x∈ξ开始,链达到目标分布所需的时间。对于给定的正数?,混合时间可表示为τ?(x)=min{t:ΔX(t′)≤?,对所有t′≥t},其中ΔX(t)=max{S?Ξ | pt(x,s)?π(s)|}表示初始状态为x时,时间t处的变异距离。 **命题1** 状态空间为ξ、稳态分布为π的马尔可夫链,其混合时间满足τ?(x)≤(s?1)2n3p+3log… **数值测试** 我们的算法旨在生成相比传统构造方法具有更好覆盖效果的拉丁超立方抽样,因此我们通过数值实验来验证其效率。在计算过程中,我们将使用位于s维单位立方体[0,1)s内的样本点。如前所述,要获得这类样本,可以用xj,i?uj,in替换xj,i,其中{uj,i,j∈{1,…,d},i∈{1,…,n}}是一组在[0,1)上均匀分布的独立同分布随机变量。不过,为了降低采样的复杂性…… **结论** 本文提出了一种用于生成维度为s≥2的拉丁超立方抽样的新算法,该算法能够生成相比传统构造方法具有更均匀分布特性的设计。该算法采用了蒙特卡洛马尔可夫链技术,通过模拟具有特定稳态分布的链结构,促使样本点之间保持更大的间距。通过对链的混合时间进行分析,我们发现其收敛速度为多项式级。同时,我们也将其与传统方法进行了比较评估。 **致谢** 在开展本研究的过程中,拉米·埃尔·哈达德获得了法国学院-法国校园项目提供的资助(资助编号:118166r),同时还得到了里尔大学欧洲数学、物理及其相互作用中心的支持。马蒂亚斯·怀永·谭的研究则得到了中国香港特别行政区研究资助委员会的两项资助(一般研究基金项目编号:cityu 11201519和cityu>

另外,还有一种结合了拉丁超立方抽样和分层技术的混合方法,被用来生成所谓的数独拉丁方抽样(slss)(el haddad等人,2012)。研究表明,使用slss得到的估计量方差与简单分层抽样的方差大致相当。然而数值实验显示,与单纯使用简单分层抽样相比,slss不仅能实现更低的方差,还具有更高的效率(el haddad等人,2020)。

最近,sheikholeslami和razavi(2017)提出了一种名为渐进拉丁超立方抽样的采样策略,它是拉丁超立方抽样的序列版本。作者们证明了,在保持均匀性和一维投影特性方面,渐进拉丁超立方抽样优于传统的拉丁超立方抽样。

上述所有方法在处理高维输入空间时,都难以生成具有良好空间填充特性的大规模拉丁超立方抽样。本文提出了一种新的马尔可夫链蒙特卡洛算法,旨在通过增加样本点之间的间距来优化样本的空间分布,从而更全面地探索输入空间。这一创新方法借鉴了morris和mitchell的奠基性工作(morris和mitchell,1995),他们通过将最小最大距离准则与拉丁超立方抽样的特性相结合,改进了计算实验的设计方法。他们还开发了一种模拟退火算法来生成这类设计,力求在最大化最小最大距离准则与保持拉丁超立方抽样的理想投影特性之间取得平衡。

尽管本文深受morris和mitchell(1995)工作的影响,但我们的目标有所不同。morris和mitchell(1995)中的模拟退火算法旨在最小化某个给定的准则,而我们的方法则是根据后文介绍的目标分布来生成均匀分布的样本。此外,我们还对所提算法的收敛性进行了分析,而morris和mitchell(1995)并未做此分析,而且我们还在更高维度、更大样本量的情况下对该算法进行了测试。

本文的其余结构如下:第2节回顾拉丁超立方抽样的性质及其经典的构造算法;第3节介绍所提出的用于构建多维拉丁超立方抽样的梅特罗波利斯-黑斯廷斯算法;第4节分析该算法的收敛性;第5节通过数值实验表明,所提算法生成的抽样具有更均匀的分布和更大的点间距,因此比传统拉丁超立方抽样能实现更好的采样空间覆盖;最后第6节给出结论。

片段摘录
**拉丁超立方抽样的经典构造及缺陷**
我们将规模为n、维度为s(s≤n)的拉丁超立方抽样记为x=(x1,…,xs),其中对于所有的j∈{1,…,s},xj=(xj,1,…,xj,n)?,且xj,i∈{1,…,n}。要生成拉丁超立方抽样,首先需将1到n的整数按升序排列在第一列x1中,随后通过重新排列1到n的整数来形成其余列xj(j∈{2,…,s}),并确保每个整数在每一列中恰好出现一次。根据这种构造方式,共有(n!)^(s?1)种不同的拉丁超立方抽样配置。

**基于马尔可夫链蒙特卡洛的拉丁超立方抽样构造**
设输入空间的维度为s≥2,样本点数量为n。用sn表示{1,…,n}的所有排列集合,用i?(1,…,n)?表示sn中的恒等排列。如前所述,可以将拉丁超立方抽样视为集合ξ?{i}×s???1中的候选元素。为了提高生成能够有效覆盖输入空间{1,…,n}?s且避免点群聚的拉丁超立方抽样的概率,就需要采用一种能够考虑点对之间距离的度量方法。

**算法的收敛性**
要判断前述构建的马尔可夫链向稳态分布π收敛的速度,可以通过限定混合时间来实现,混合时间是指从初始状态x∈ξ开始,链达到目标分布所需的时间。对于给定的正数?,混合时间可表示为τ?(x)=min{t:δx(t′)≤?,对所有t′≥t},其中δx(t)=max{s?ξ | pt(x,s)?π(s)|}表示初始状态为x时,时间t处的变异距离。

**命题1**
状态空间为ξ、稳态分布为π的马尔可夫链,其混合时间满足τ?(x)≤(s?1)2n3p+3log…

**数值测试**
我们的算法旨在生成相比传统构造方法具有更好覆盖效果的拉丁超立方抽样,因此我们通过数值实验来验证其效率。在计算过程中,我们将使用位于s维单位立方体[0,1)s内的样本点。如前所述,要获得这类样本,可以用xj,i?uj,in替换xj,i,其中{uj,i,j∈{1,…,d},i∈{1,…,n}}是一组在[0,1)上均匀分布的独立同分布随机变量。不过,为了降低采样的复杂性……

**结论**
本文提出了一种用于生成维度为s≥2的拉丁超立方抽样的新算法,该算法能够生成相比传统构造方法具有更均匀分布特性的设计。该算法采用了蒙特卡洛马尔可夫链技术,通过模拟具有特定稳态分布的链结构,促使样本点之间保持更大的间距。通过对链的混合时间进行分析,我们发现其收敛速度为多项式级。同时,我们也将其与传统方法进行了比较评估。

**致谢**
在开展本研究的过程中,拉米·埃尔·哈达德获得了法国学院-法国校园项目提供的资助(资助编号:118166r),同时还得到了里尔大学欧洲数学、物理及其相互作用中心的支持。马蒂亚斯·怀永·谭的研究则得到了中国香港特别行政区研究资助委员会的两项资助(一般研究基金项目编号:cityu 11201519和cityu 11209622)。>
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号