抽样的基本问题是，对于给定目标概率p（x），如何抽取一组满足该分布的变量。在某些问题中可能还有别的约束条件，如iid等。
基本的抽样算法有
1.基本方法
基本思路通过函数变换将一个均匀分布转化为目标分布，缺点是，对函数性质有一定要求，性质较差的可能没有解析解或无法求解。
具体方法是，设原pdf为p（x），其对应的分布函数F（x）。设y=F（x），当y服从0~1的均匀分布，则反函数求x即满足对应pdf
几何说明如下图
2.rejection sampling
这个算法需要先找到一个能够抽样的参照分布（proposal distribution）q（x），使得p(x)<=M*q(x)对任意的x成立，其中M是一个常数
接下来，对q(x)进行抽样，按照均匀分布拒绝掉其中的某些点，剩余的点即满足分布p。
具体算法为
其几何解释为
p(x)和q(x)的积分都为1，按照上述算法，满足q（x）的抽样点，只有1/M能被接受。所以，我们希望p和q形状能尽可能的接近，M尽可能小，以获得更好的采样效率。
但是在高维的情况下，这个接受率按照指数降低。这个缺点使得rejection方法很难实际应用于高维抽样的情况。
3.importance sampling(重要性抽样？)
和以上两种方法不同，重要性抽样并不生成符合目标概率p的抽样点，而是通过对满足一个参照分布q的样本点进行加权，获得对应p分布的某个函数f的数学期望
如上式，z为符合参考分布q的抽样点，对z的操作可以近似获得d（z）dz的积分，p(z)/q(z) 称为importance weights，加权后，d(z)dz的积分变换为对p(z)dz的积分。
在实际应用中，为了方便起见，经常把q（x）取为对应区间的均匀分布。
实际应用中，p,q可能未经过归一化，也可以把归一化的步骤放到权重中，则zl对应的归一化后的权重wl为
跟rejection sampling一样，importance sampling也希望参照分布q和p能尽量接近。否则，若p集中在某个区间，而q在这个区间概率很低，也就是说，极少数落在该区间的样本点很少将在很大程度上决定了上述的E（f），这样获得的结果跟真实值差异可能很大。
在Bayes网络中，设联合分布为p（Z1，Z2），其中Z1为未知变量，Z2为观察值。
3.1 likelihood weighted sampling
如果直接使用importance sampling的方法，取q(Z1,Z2)为对应区间上的均匀分布,然后丢弃掉其中和观察值不匹配的采样点，仅留下Z2=z2的样本点，利用这些点,加权p(Z)/c计算期望(c为均匀分布对应的均值)。当z的定义域很大时，可能导致抽样接受率很低。
为了解决这个问题，有人提出了一种改进：likelihood weighted sampling。这种方法，根据Bayes Net中的依赖关系依次抽取每个变量。当变量为观察值，直接设为观察值，否则，按条件概率p（Zi|pai）抽取Zi。则对应权重p（x）/q(x) =
3.2 sampling-importance-resampling(SIR)
importance sampling只能计算对应的期望值，本身无法生成满足p的样本点。SIR算法则是在importance sampling结果上进行加工，生成满足p的样本点，以弥补这个缺陷
算法分两步
1.按照IS方式生成满足分布q的L个样本点z1， z2， .....,zL，以及对应的权重wl ，有/sum wi =1
2.按照概率分布（w1,w2,...wL）取出对应的z1，...zL. 这个步骤应该这样理解：Z只能取值z1，z2...,ZL有限个离散值，其中P（Z=zi）=wi
参考文献：
PRML:11章
An Introduction to MCMC for Machine Learning，ANDRIEU等
