采样
--------七月在线机器学习笔记
目录
带拒绝的采样分析
在对某区域f(x,y)≤0抽样的过程中，若该区域f(x,y)≤0不容易直接求解，则寻找某容易采样的区域g(x,y)≤0 ，G为F的上界。当采 样(x0,y0)∈G且落在F内部时，接收该采样； 否则拒绝之。
该例中， f(x,y)≤0是圆， g(x,y)≤0是该圆的外包围正方形。
注：区域f(x,y)≤0的可行解集合记做F；区域 g(x,y)≤0的可行解集合记做G；显然F⊆G
上述方法能够一定程度的估算圆周率——虽然精度很差。
上述抽样问题能否用来解决一般概率分布函数的抽样问题？如：根据均匀分布函数得到正态分布的抽样。
Rejection sampling：找到目标函数的上界，然后选取一个已知/容易计算的分布函数（包含整个目标函数）逐点逼近。
对某概率分布函数进行采样的意义
根据抽样结果估算该分布函数的参数，从而完成参数的学习。
前提：系统已经存在，但参数未知；
方法：通过采样的方式，获得一定数量的样本，从而学习该系统的参数。
例：投硬币试验中，进行N次试验，n次朝上，N-n次朝 下——可以认为，是进行了N次(独立)抽样。
假定朝上的概率为p，使用对数似然函数作为目标函数：
用采样改造EM算法本身
在EM算法中，E-Step求出隐变量的条件概率，从而给出期望 Q，M-Step将目标函数Q求极大值，期望Q为：
显然，这仍然可以使用采样的方式近似得到：
这种方式的EM算法被称为MC-EM算法(Monte Carlo EM)MC-EM算法仅改变了E的计算，M的求极值本身没有变化。
极限情况：若MC-EM算法的期望Q的估计，仅采样一个样本， 则称之为随机EM算法(stochastic EM algorithm)。此外，EM算法的M-Step，可以使用MAP而非MLE的方式，从而目标函数最后多一项lnp(θ)。
马尔科夫连模型
采样：给定概率分布p(x)，如何在计算机中生成它的若干样本？
考虑某随机过程π，它的状态有n个，用1~n 表示。记在当前时刻t时位于i状态，它在t+1时刻位于j状态的概率为
P(i,j)=P(j|i)：即状态转移的概率只依赖于前一个状态。
举例
概率转移矩阵
显然，第n+1代中处于第j阶层的概率为：
, 全概率公式（加和规则）
因此，矩阵P即贝叶斯网络中描述的（条件）概率转移矩阵。
第i行元素表示：在上一个状态为i时的分布概率，行和为1
重要性质：初始概率不同，但经过若干次迭代，
最终稳定收敛在某个分布上。转移概率矩阵P的性质，而非初始分布的性 质。事实上，上述矩阵P的n次幂，每行都是 (0.286,0.489,0.225)，n>20
马尔科夫随机过程的平稳分布
如果一个非周期马尔科夫随机过程具有转移概率矩阵P，且它的任意两个状态都是连通的，
则存在，记做
同时，若某概率分布,说明：
该多项分布π是状态转移矩阵P的平稳分布；
线性方程xP=x的非负解为π，而唯一，因此 π是线性方程xP=x的唯一非负解。
马尔科夫随机过程与采样
上述平稳分布的马尔科夫随机过程对采样带来很大的启发：
对于某概率分布π，生成一 个能够收敛到概率分布π的马尔科夫状态转移矩阵P，则经过有限次迭代，一定可以得到概率分布π。
该方法可使用Monte Carlo模拟来完成，称之为MCMC(Markov Chain Monte Carlo)。
细致平稳条件
从稳定分布满足可以抽象出如下定义：
如果非周期马尔科夫过程的转移矩阵P和分布π(x) 满足：
则是马尔科夫过程的平稳分布。上式又被称作细致平稳条件 (detailed balance condition) （可翻转的）。
P(i,j)为矩阵P的第i行第j列，其意思为前一个状态为i时， 后一个状态为j的概率：即P(j|i)，因此，有时也写成P(i—>j)
细致平稳的理解：根据定义，对于任意两个状态i，j，从i转移到j的概率和从j转移到i的概率相等。可直观的理解成每一个状态都是平稳的。
设定接受率
假定当前马尔科夫过程的转移矩阵为Q，对于给定分布p，一般的说，
通过加入因子α的方式，使得上式满足细致平稳条件
满足等式的因子α有很多，根据对称性，可以取：
根据接受率α改造转移矩阵Q：
MCMC：Metropolis-Hastings算法
根据需要满足的细致平稳条件
若令α(j,i)=1，则有：
从而：
将接受率置为恒小于1，从而
改造MCMC算法
分析MCMC：
需要事先给定马尔科夫过程的转移矩阵P；
有一定的拒绝率。
若需要采样二维联合分布p(x,y)，固定x，得
若固定y，可得到对偶的结论。
二维Gibbs采样算法
由
很容易得到二维Gibbs采样算法：
随机初始化(X,Y)=(x0,y0)
对t=0,1,2…，循环采样：
推广到n维即得前面LDA中的Gibbs Sampling采样更新策略。