专栏首页阿林前端开发攻城狮Scrambled后的序列依然具有radical inversion的性质
原创

Scrambled后的序列依然具有radical inversion的性质

原文中陈述了很多具体的例子,而缺乏了一些Halton序列本身的说明,使用场景、以及与其他序列使用对比的差异,故在此处进行补充

HaltonHammersley可以生成在无穷维度上分布均匀的点集,它们都基于Van der Corput序列 Halton序列的定义很简单:

Xi:=(Φb1(i),...,Φbn(i))Xi:=(Φb1(i),...,Φbn(i))

既是每一个维度都是一个基于不同底数bnbn的Van der Corput序列,其中b1...bnb1...bn互为质数(例如第11到第nn个质数) Hammersley点集的定义和Halton非常相似 以下是Hammersley点集的定义

Xi:=(iN,Φb1(i),...,Φbn−1(i))Xi:=(iN,Φb1(i),...,Φbn−1(i))

唯一不同的就是把第一个维度变成iNiN,其中ii为样本点的索引,NN为样本点集中点的个数。根据定义,Hammersley点集只能生成固定数目个样本,而Halton序列则可以生成无穷个样本(当然在计算机里我们只有有限的bit去表示有限个样本点)

上面左边的图为第1-100个Halton序列中的二维的样本点,(Φ2(i),Φ3(i))99i=0(Φ2(i),Φ3(i))i=099,右边则为数量为100的二维Hammersley样本点集,(i100,Φ2(i))99i=0(i100,Φ2(i))i=099。可以看出来它们的分布都远比一般的伪随机数更加均匀。Hammersley的差异性比Halton更稍低一些,但是代价是必须预先知道点的数量,并且一旦固定无法更改虚幻引擎4中对环境贴图的Filter采样就是用的点集大小固定为1024的Hammersley点集。Halton虽然差异性稍高,但可以不受限制的生成无穷多个点,更适合于没有固定样本个数的应用,例如任何progressive或者adaptive的过程。 基于radical inversion的序列还都具有Stratified样本的性质。因为每一个维度都是一个radical inversion,所以每一维度都具有所有之前提到的radical inversion的性质。其中之一就是点集个数到达bmbm个点时对[0,1)[0,1)会形成uniform的划分。下图是第1-12个Halton序列的二维点集,可以看出点0-7在X轴的投影和0-8在Y轴的投影都是均匀覆盖。这也意味着在样本数量等于每个维度底数的公倍数的适合,样本会自然在每个维度上底数的倍数的strata中自然的形成stratified采样。例如下图中的第0-5个点,刚好在图中落在2x3的strata中。

`Halton`序列的一个缺点是,在用一些比较大的质数作为底数时,序列的分布在点的数量不那么多的时候并不会均匀的分布,只有当点的数量接近底数的幂的时候分布才会逐渐均匀。例如下图中以29和31为底的序列,一开始的点会分别是

129,229,329...129,229,329...所以造成了点都集中落在了一条直线上面。解决这个问题的方法也很简单,Scrambling。Scrambling的方法有许多种,例如最简单的XOR Scrambling适用于以2为底数的序列。对于Halton来说,一个比较常用的方法是Faure Scrambling

Φb(i)=∑l=0M−1σb(al(i))b−l−1Φb(i)=∑l=0M−1σb(al(i))b−l−1

如上面的公式所写,Faure Scrambling的做法就是在做radical inverse的时候不直接将数字镜像到小数点右边,而在镜像前先把每个数字通过一个permutationσbσb转换成另一个数字。不同的底数bb有不同的permutationσσ。例如σ4=[0,2,1,3]σ4=[0,2,1,3]。至于σbσb如何具体计算这里不再展开,下一篇专栏在讲实现时会给出参考链接。这里值得一提的时Scrambling完全不会影响radical inversion序列分布的随机性,因为radical inversion会自然的将空间均等划分成底数bb的整数次幂个部分,scrambling本质上就是在交换这些均等划分的部分,所以Scrambled后的序列依然具有radical inversion的性质。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Halton序列均匀产生多维随机数的介绍与实现

    在统计学中,Halton序列是用于生成空间中的点的序列,如Monte Carlo模拟的数值方法,虽然这些序列是确定性的,但它们的差异性很低,也就是说,在许多方面...

    用户7108768
  • 【论文笔记】中文词向量论文综述(二)

    一、Improve Chinese Word Embeddings by Exploiting Internal Structure

    zenRRan
  • 谈谈我对 IoC 和 AOP 的理解

    @JFinal 波总在 JFinal 4.8 发布新闻的评论 中给出了下面的表述:

    老码农
  • 控制反转与依赖注入

    控制反转是Spring框架的核心思想,也是因为Spring的关系这个模式为大众所知晓。

    李鸿坤
  • Serverless 公司的远程团队沟通策略

    首先向不了解我们的人说明一下,Serverless 团队成员总共跨越了 18 个时区,不同成员之间重合的工作时间非常少。

    Aceyclee
  • NER的过去、现在和未来综述-过去

    命名实体识别(NER, Named Entity Recognition),是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等。

    百川AI
  • CNN可视化最新研究方法进展(附结构、算法)

    【AI科技大本营导读】深度学习一直被看做是一个难以解释的“黑匣子”。一方面在于其缺乏数学上的优雅,缺乏基础理论的支撑,另一方面在工程上缺乏解释性,其潜在的安全隐...

    AI科技大本营
  • Spring基础小结

    Spring是一个开源的轻量级Java SE(Java 标准版本)/Java EE(Java 企业版本)开发应用框架,其目的是用于简化企业级应用程序开发。

    WindCoder
  • ICPR 图像识别与检测挑战赛冠军方案出炉,基于偏旁部首来识别 Duang 字

    随着互联网的飞速发展,图片成为信息传播的重要媒介,图片中的文本识别与检测技术也一度成为学界业界的研究热点,应用在诸如证件照识别、信息采集、书籍电子化等领域。

    AI科技评论
  • 元启发式算法 | 遗传算法(GA)解决TSP问题(Python实现)

    遗传算法(Genetic Algorithm, GA),是一种通过模拟生物自然进化过程的随机搜索算法,主要思想是模拟生物进化论中自然选择和遗传学机理的生物进化过...

    学弱猹
  • 用 SOLID 原则保驾 React 组件开发

    本世纪初,美国计算机专家和作者 Robert Cecil Martin 针对 OOP 编程,提出了可以很好配合的五个独立模式;后由重构等领域的专家 Michae...

    江米小枣
  • 比Transformer好用!前谷歌大脑员工创业公司获4000万美元融资,Hinton、李飞飞等支持

    近日,自然语言处理 (NLP) 预训练模型提供商 Cohere 宣布了 4000 万美元的 A 轮融资。此次融资由 Index Ventures 领投,Sect...

    新智元
  • 深入剖析 Laravel 服务容器

    之前在 深度挖掘 Laravel 生命周期 一文中,我们有去探究 Laravel 究竟是如何接收 HTTP 请求,又是如何生成响应并最终呈现给用户的工作原理。

    柳公子
  • Firewalld 2

    Firewalld 是一个本地的网络策略管理软件,与 iptables 启相同的作用

    franket
  • 【愚公系列】2021年12月 面向对象设计原则(四)-依赖倒置原则(Dependence Inversion Principle DIP)

    常用的面向对象设计原则有七个,这七大设计原则都是以可维护性和可复用性为基础的,这些原则并不是孤立存在的,它们相互依赖相互补充,遵循这些设计原则可以有效地提高系统...

    愚公搬代码
  • 设计原则之依赖倒置原则(DIP)

    依赖倒置原则(Dependency Inversion Principle)是 Robert C. Martin 提出的,原则声明了两个方面:

    Dylan Liu
  • Spring源码深度解析(一)

    如果要调用A的method()方法,而method方法又依赖于B的某些处理。原生方式: A a = new A(); B b = new B(); a.s...

    张申傲
  • 架构之路 (七) —— iOS App的SOLID原则(一)

    要编写出色的应用程序,您不仅需要提出一个好主意,还需要考虑未来。快速有效地适应、改进和扩展应用程序功能的灵活性至关重要。无论您是在团队中工作还是独自工作,从长远...

    conanma
  • NLP能否像人脑一样工作?CMU、MIT三篇论文详解机器和大脑范畴下NLP的关系

    自 Google AI 提出 BERT (Bidirectional Encoder Representations from Transformers) 后,...

    机器之心

扫码关注云+社区

领取腾讯云代金券