【摘 要】
：
梅特罗波利斯算法(Metropolis algorithm)是一种基本的马尔可夫链蒙特卡罗(Markov chain Monte Carlo,MCMC)采样技术,可用于从概率图模型所表示的高维概率分布(即吉布斯(Gibbs)分布)中进行随机采样.传统的梅特罗波利斯算法是一个串行算法.关于其快速收敛性的一个经典结论是:当满足梅特罗波利斯算法的Dobrushin-Shlosman条件时,该算法在O(nlogn)步内快速收敛,其中n是随机变量的个数.本文研究了梅特罗波利斯算法的分布式版本——局部梅特罗波利斯算法
【机 构】
：
南京大学计算机软件新技术国家重点实验室,南京210023
论文部分内容阅读
梅特罗波利斯算法(Metropolis algorithm)是一种基本的马尔可夫链蒙特卡罗(Markov chain Monte Carlo,MCMC)采样技术,可用于从概率图模型所表示的高维概率分布(即吉布斯(Gibbs)分布)中进行随机采样.传统的梅特罗波利斯算法是一个串行算法.关于其快速收敛性的一个经典结论是:当满足梅特罗波利斯算法的Dobrushin-Shlosman条件时,该算法在O(nlogn)步内快速收敛,其中n是随机变量的个数.本文研究了梅特罗波利斯算法的分布式版本——局部梅特罗波利斯算法.对该算法的正确性与收敛速度进行了分析,证明了该算法总是收敛于正确的吉布斯分布;并且对于一类自然的不包含三角形(triangle-free)概率图模型,如果满足相同的Dobrushin-Shlosman条件,则局部梅特罗波利斯算法在O(logn)轮内快速收敛.相比于传统的串行算法,实现了Ω(n)倍的渐进最优并行加速比.具体应用包括图染色、硬核模型和伊辛(Ising)模型的分布式采样算法.
其他文献
作为改变人脸图像外观的重要方式之一,美妆转移任务在近年来获得了越来越多的关注.美妆转移网络可以将任意参考图像的妆容转移到任意人脸图像上,在节约时间和空间成本的同时帮助人们找到适合自己的妆容,并获得妆容得到美化的图像.美妆转移网络BeautyGAN成功展示了无监督方法妆容迁移的较好效果,然而此类无监督学习策略缺乏可以提供良好妆容细节的监督标签,导致实验结果中出现了背景变色、边缘不自然、容易受光照影响等问题.用素颜-美妆配对标签进一步约束Beau-tyGAN模型训练可以解决上述问题,但当前学术界缺乏此类精细标
针对毫米波在混合窃听无线通信系统面临的安全问题,基于阵列收发结构,提出了一种有效的无线物理层安全传输方法.在发射端采用多波束符号级方向调制、人工噪声(artificial noise,AN)辅助、天线子集方法,以及合法用户(legitimate user,LU)采用阵列接收确保混合窃听环境下的安全可靠传输.考虑窃听者(eavesdropper,Eve)信息未知,通过最小化发射信息功率准则设计发射波束形成矢量,满足合法用户的接收信号指定符号级约束,确保合法用户有效接收.将剩余的发射功率分配给人工噪声,最大限
本文针对一类具有强耦合不确定性因素的连续时间多输入多输出非线性系统,提出了基于历史采样数据的不确定性因素补偿控制策略(sampled-data-based compensation control,SDBCC).与基于观测器的不确定性因素补偿控制不同,本文首先利用当前以及历史采样数据计算出由系统非线性耦合未建模动态和外部扰动构成的总扰动在前一采样周期内某时刻的精确值,然后利用该精确值在反馈环节对总扰动进行补偿以消除它的不利影响.连续时间系统在数据驱动的反馈控制作用下构成了一个混杂闭环控制系统,这连同系统的
高中化学对典型晶体的晶胞、金属晶体的原子堆积模型、离子晶体中离子的配位数及决定因素进行了介绍,这些内容是化学竞赛选手深入理解晶体堆积方式的重要铺垫.以字母表示晶体堆积方式是竞赛培训的难点之一,其涉及阴阳离子堆积、空隙、空隙占有率、空层等诸多知识,要求竞赛选手对晶胞有深入的认识.我们在竞赛教学中发现,国内常见的无机化学、结构化学教材并无对相关内容的介绍,因此竞赛选手往往只能选择囫囵吞枣、死记硬背.
自适应的物理层安全技术是6G通信中具有抗量子攻击实现通信安全一体化的重要挑战问题.本文研究了合法用户信道状态随机衰落,且各状态不满足退化关系的高斯多天线输入输出(MIMO)窃听信道的信道容量问题.我们引入“弱超多数化”(weak supermajorization)理论对各状态排序.并采用广播逼近(broadcast approach)技术,即基于叠加编码(superposition coding)架构设计编码并予以优化,从而完成信道状态信息(channel state information,CSI)未
什么是慢性肾脏病rn慢性肾脏病是指各种原因引起的肾脏结构或功能异常,持续时间超过3个月,并对健康造成影响.依据估算的肾小球滤过率(eGFR)水平将慢性肾脏病分为1～5期,其中慢性肾脏病3～5期就是上述病例中提到的肾功能异常,慢性肾脏病5期又称为终末期肾病或尿毒症期.
在我国,有很大比例的人群存有这样一个观点:传统中药发展几千年了,素有“药食同源”的说法,所以中(成)药是纯天然的,是无毒的.但是,现在我们必须用大量惨痛的教训和案例来纠正这种固有的观念.中药也是药,是药三分毒.
为了提高塔式吊车的实际工作效率,往往需要在驱动旋臂和台车的同时改变绳长,以同步实现负载的运输与起落吊运.然而,目前针对变绳长塔式吊车控制问题的研究非常有限,依然处于起步阶段.对于变绳长塔式吊车而言,如何在保证系统良好暂态性能的基础上,减少运输时间、降低系统能耗,并同时实现综合最优是一个亟待解决的实际问题.为此,本文提出了一种考虑状态约束的五自由度塔式吊车多目标最优轨迹规划方法,首次实现了运输时间和系统能耗的Pareto最优,并可从理论上保证状态变量及其对应速度满足物理约束.具体而言,本文通过微分平坦输出信
针对角速度受限和通信资源有限的航天器姿态系统,考虑转动惯量难以精确获得并且存在外部干扰的情况,提出一种基于神经网络的自适应事件触发姿态机动控制算法.该算法首先基于预设性能技术,将角速度受限约束转换为性能边界约束,进一步通过误差转换,建立姿态系统的等效误差模型,将存在角速度约束的航天器姿态系统机动控制问题巧妙地转化为无约束误差系统的状态有界稳定控制问题;然后,选用径向基神经网络设计自适应律,在线逼近系统中由未知转动惯量带来的不确定性项.与此同时,考虑到星载通信资源有限的问题,通过建立触发控制信号与实时控制信
基于新型非易失性存储器和存内计算架构的神经网络推理芯片在功耗、速度和存储密度等方面展现出突出的优势,使其在物联网和边缘计算等应用领域受到广泛关注.在本文中,我们详细介绍了一款基于可编程线性忆阻器(programmable linear random-access memory,PLRAM)的存算一体化片上系统芯片的设计和实现方法.为了在资源受限条件下实现高效的推理计算,该系统结合了器件、电路和系统层面的一系列新技术,包括具备每单元7比特存储能力的新器件、数据自适应写入、电路失配补偿,以及基于残差模型训练的