采样方法的调研归纳，ML基础知识。

取样算法

Uniform Random Sampling 均匀随机取样

生成[0,1]之间的伪随机数序列equal to均匀分布

Low-Discrepancy Sampling 低差异取样

Discrepancy（差异值）

衡量采样序列质量，描述采样点在采样空间内分布的均匀程度

$ D_N(P)=\sup _{B\in J}|\frac{A(B)}{N}-\lambda_s(B)|$

对于一个在 $[0,1]^n$ 空间中的点集，任意选取一个空间中的区域 $B$ ，此区域内点的数量 $A$ 和点集个数的总量 $N$ 的比值和此区域的体积 $\lambda_s$ 的差的绝对值的最大值，就是这个点集的Discrepancy。分布越均匀的点集，任意区域内的点集数量占点总数量的比例也会越接近于这个区域的体积。

LHS/Latin hypercube sampling算法

多维算法，需要将采样空间按照维度进行分层。假设现在要采样 $N$ 个点, LHS算法先将整个采样区域每个维度分成 $N$ 份, 然后沿着对角线带抖动采样, 再将每个轴坐标进行随机进行排列。

具有良好的点分布，避免多维下分层采样随机数的聚集。

Halton序列

任意一个非负整数 $a$ 都可以表示为 $b$ 进制的一串数字 $d_m(a)...d_2(a)d_1(a)$ ，Radical inverse函数 $\phi_b$ 表示将数字串取反, 并在前面加上0.，变为
$\phi_{b}a=0.d_1(a)d_2(a)...d_m(a)$ ，非负整数转化为[0,1)小数，第
$i$ 位上的数字 $d_i(a)$ 对Radical inverse的贡献值为 $\frac{d_i(a)}{b^i}$ 。

取 $b=2$ ，得到van der Corput 序列

要生成n维下的Halton序列, 我们只需要在每个维度上使用不同的基, 产生Radical Inverse序列即可. 因为每个维度上的基必须是互质的, 因此一个很自然的选择是使用前n个质数 $p_n$ 作为每个维度的基：

$x_a=(\phi_2(a),\phi_3(a),...,\phi_{p_n}(a))$

Halton序列不需要提前设定需要用到的采样点总个数, 序列前面的采样点总是良好分布的。

当Halton中使用的基的值比较大时, 如果采样点较少, 会出现采样点聚集的情况。

scambling操作就是将 Halton进制表示中的每个数字进行一次重映射：

$\phi_ba=0.p(d_1(a))p(d_2(a))...,p(d_m(a))$
$p$ 表示一个表示重映射的数字排列, 每个基使用一个不同的排列(第一位必须是0). 每个质数基对应的排列可以查表获取：Leonhard Grünschloß

Hammersley序列

如果需要的采样点个数 $N$ 是提前确定的, 则可以得到Hammersley序列:

$x_a=(\frac{a}{N},\phi_{b_1}(a),\phi_{b_2}(a),...,\phi_{b_n}(a))$

Sobol序列

Sobol序列的每一个维度都是由底数为2的radical inversion组成，但每一个维度的radical inversion都有各自不同的矩阵。

因为Sobol序列需要一个生成矩阵 $C$ ，而且所有维度都以2为底，所以没有Halton那样在以比较大的数为底时需要用Scrambling来消除分布间的correlation这个问题。Sobol sequence generator 网站可生成矩阵。

Cross-Entropy Sampling 交叉熵取样

交叉熵

事件发生的概率越小，可获取的信息量越大，事件 $x_0$ 的信息量是 $I(x_0)=−log(p(x_0))$

熵用来表示所有信息量的期望，即：

$H(X)=−\sum_{i=1}^np(x_i)log(p(x_i))$

相对熵又称KL散度,如果我们对于同一个随机变量 x 有两个单独的概率分布 P(x) 和 Q(x)，我们可以使用 KL 散度（Kullback-Leibler (KL) divergence）来衡量这两个分布的差异
$n$ 为事件的所有可能性。 $D$ 的值越小，表示 $p$ 分布和 $q$ 分布越接近。

$D_{KL}(p||q)=\sum_{j=1}^np(x_j)ln\frac{p(x_j)}{q(x_j)}$

交叉熵方法，与进化算法类似，进化算法在空间中按照某种规则撒点，获得每个点的误差，再根据这些误差信息决定下一轮撒点的规则。交叉熵方法从理论上来说目标是最小化随机撒点得到的数据分布与数据实际分布的交叉熵（等价于最小化KL距离），尽量使采样分布（撒的点）与实际情况同分布。
交叉熵（Cross Entropy）是Shannon信息论中一个重要概念，主要用于度量两个概率分布间的差异性信息。在信息论中，交叉熵是表示两个概率分布 $p, q$ 的差异，其中 $p$ 表示真实分布， $q$ 表示预测分布，那么 $H(p,q)$ 就称为交叉熵：

$H(p,q)=\sum_ip_iln\frac{1}{q_i}=-\sum_ip_ilnq_i$

公式为KL公式变形后（ $-H(p(x))+H(p,q)$ ）的后一部分，机器学习中需要评估标签值和预测值之间的差距，可使用KL散度，由于KL散度中的前一部分是p的熵不变，故在优化过程中，只需要关注交叉熵。所以一般在机器学习中直接用交叉熵做损失函数来评估模型。

单个样本， $n$ 为分类个数： $loss=-\sum_{j=1}^ny_jlna_j$

批量样本交叉熵， $m$ 为样本个数， $n$ 为分类个数：

$J=-\sum_{i=1}^m\sum_{j=1}^ny_{ij}lna_{ij}$

首先从一个初始的高斯分布中取样参数w，对取样的参数计算函数f值大小
保留最大的几个样本，从这些样本中估计新的高斯分布的均值和方差，随后从新的分布中再次取样，迭代
f: 目标函数，从向量w到数值的映射，数值代表w的优秀程度

CEM 交叉熵方法

考虑估计一个期望，用朴素蒙特卡罗采样从真实概率密度函数 $f(x;u)$ 中采样一些样本 $x_i$
，然后计算 $\frac{1}{n}\sum_nH(x_i)$ ，若事件 $H(x)$ 发生的概率很小，那么朴素蒙特卡罗需要非常多的样本代价才能估计准这个期望；CEM算法则引入重要性采样(importance sampling)，从另一个类似的概率密度函数 $f(x;v)$ 中进行采样，则期望计算变成：

$\frac{1}{n}\sum_nH(x_i)W(z;u,v)$ ， $W(z;u,v)=\frac{f(x;u)}{f(x,v)}$

于是现在的目标变成了如何找到一个最优的采样函数 $f(x,v)$ 去指导采样出一些少量的样本来准确地估计这个期望，CEM通过在每次迭代中找到较好的采样样本 $x$ 来更新重要性函数的参数 $v$ (reference parameter)，目的是减小两个分布的差距，而这个差距是由KL散度来衡量的.

详细论文：https://dke.maastrichtuniversity.nl/m.winands/documents/crossmc.pdf

参考

鳴轉のブログ

采样算法调研