拒绝采样

拒绝采样，也叫接受-拒绝采样。顾名思义，在采样过程中，我们会接受一些样本，也会拒绝一些样本，使得样本最终的分布符合期望。

假设原始分布$p(x)$难以直接采样，我们先将$p(x)$归一化，得到$\hat{p}(x)$。然后引入一个比较容易采样的分布$q(x)$和一个常数$k$，使得$kq(x)$可以覆盖$\hat{p}(x)$，即$kq(x)>\hat{p}(x)$，$q(x)$为提议分布。

比如我们要采集一个分布$p(x)=\frac{1}{2}\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{(x-0.3{)}^2}{2{\sigma }^2}+\frac{3}{2}\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{-(x-0.8{)}^2}{2{\sigma }^2}$，其归一化后多了一个系数$\frac{1}{0.632455}$。我们选择正态分布$q(x)=\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{(x-0.6{)}^2}{2\ast 0.4^2}$为提议分布，$k$取为10。如下图所示：

观测$\hat{p}(x)$的分布，我们在0到1.2之间根据提议分布抽取样本$\hat{x}$，计算$\alpha (\hat{x})=\frac{\hat{p}(\hat{x})}{kq(\hat{x})}$，并以$\alpha (\hat{x})$的概率接受这个样本。

def normal(x,u,sigma):
  p=np.exp(-(x-u)**2/(2*sigma**2))/(np.sqrt(2*np.pi)*sigma)
  return p
  
def f1(x):
  sigma=0.1  
  return (0.5/np.sqrt(2*np.pi*sigma)*np.exp(-(x-0.3)**2/2.0/sigma**2)+1.5/np.sqrt(2.0*np.pi*sigma)*np.exp(-(x-0.8)**2/2.0/sigma**2))/0.632455
  
x_t=[0]
for t in range(100000):
  
  x_=np.random.normal(0.6,0.4)
  alpha=f1(x_)/5/normal(x_,0.6,0.4)
  u=np.random.uniform(0,1)
  if u<alpha:
    x_t.append(x_)

最终采样结果如下：

拒绝采样法的难点在于：如何找到合适的提议分布，尤其是当样本维度很高的时候。

蒙特卡罗法采样

在高维空间中，蒙特卡罗法是一种更好的采样方法。其核心思想是将采样过程看作一个马尔可夫链。$x_1,x_2,...,x_{t-1},x_t,x_{t+1},...$.
第$t+1$次的采样依赖于第$t$次抽取的样本$x_t$和状态转移分布$q(x|x_t)$。如果这个马尔可夫链的平稳分布为$p(x)$，那么在状态平稳时抽取的样本就服从$p(x)$的分布。

Metropolis-Hastings算法

Metropolis-Hastings算法简称MH算法，是一种常用的蒙特卡罗采样法。

在MH算法中，假设第$t$次采样的样本为$x_t$，首先根据提议分布$q(x|x_t)$抽取一个样本$\hat{x}$，并以概率$A(\hat{x},x_t)$来接受$\hat{x}$作为第$t+1$次的采样样本$x_{t+1}$。
$A(\hat{x},x_t)=\text{min}(1,\frac{p(\hat{x})q(x_t|\hat{x})}{p(x_t)q(\hat{x}|x_t)})$
这里相当于对马尔可夫链的状态转移概率做了修正:$q^{\prime }(\hat{x}|x_t)=q(\hat{x}|x_t)A(\hat{x},x_t)$
修正后的马尔可夫链可达平稳状态，且平稳分布为$p(x)$。
其证明可以参考：《神经网络与深度学习》，邱锡鹏，2019 中关于采样的章节。

我们在接受-拒绝采样中举的例子，也可以用MH方法来进行采样。

################ M-H sampling
x_m=[0]
for t in range(200000):
  x_=np.random.normal(x_m[-1],0.1)
#  alpha=f1(x_)*normal(x_,x_m[-1],0.1)/f1(x_m[-1])/normal(x_m[-1],x_,0.1)
  alpha=f1(x_)*normal(x_m[-1],x_,0.1)/f1(x_m[-1])/normal(x_,x_m[-1],0.1)
#  print(normal(x_m[-1],x_,1)/normal(x_,x_m[-1],1))
  alpha=min(alpha,1)
  u=np.random.uniform(0,1)
  if u<alpha:
    x_m.append(x_)

结果如下：

一、Executors

Executors是一个线程相关的工具类。主要提供了以下几种创建线程池的方法：

第1，4，5种：线程最大数量是Integer.MAX_VALUE，当执行大量耗时任务时，容易造成堆外内存溢出
第2，3种：使用的的阻塞队列为无边界队列，当任务量过大时，可能会导致内存溢出

注意： 在java8中新添加了newWorkStealingPool，

二、ThreadPoolExecutor

ThreadPoolExecutor(int corePoolSize, //核心线程数量
                   int maximumPoolSize, // 最大线程数量
                   long keepAliveTime, // 存活时间 
                   TimeUnit unit, // 时间单位
                   BlockingQueue<Runnable> workQueue, //阻塞队列
                   ThreadFactory threadFactory) // 拒绝策略

注意： 有多于corePoolSize但小于maximumPoolSize线程正在运行，则仅当队列已满时才会创建新线程