gibbssampling

马尔科夫链定义：P(𝑋𝑡+1=𝑥|𝑋𝑡,𝑋𝑡−1,…)=P(𝑋𝑡+1=𝑥|𝑋𝑡)，即当前状态转移的概率只依赖于前一个状态。有个重要的性质，一个非周期的马尔科夫链，根据其转移矩阵，可以使得初始状态分布𝜋0沿着转移矩阵最终转为平稳分布π.如何构造转移矩阵，获得平稳分布π?马尔科夫链蒙特卡罗算法（MCMC）该算法提出细致平稳条件，对于分布π上的任意两个状态i,j，有π(i)𝑃𝑖,𝑗=π(j)𝑃𝑗,𝑖即从通过转移矩阵从状态i转移到状态j的概率值等于从状态j转移到状态i的概率值。当满足细致平稳条件时，这个分布𝛑就是平稳分布。但是并不是所有用户提出的转移矩阵(有转移概率q组成)（先验知识）都是满足该条件的。于是引入接受率𝛂通过观察其中满足了细致平稳条件，将q(i,j)a(i,j)看作转移概率q’于是得到MCMC采样算法，马尔科夫链上的每一个状态（收敛后）就是平稳分布的样本。Gibbssampling因为存在接受率的情况，就是不一定转移状态，为了加速马尔科夫链收敛（遍历完所有状态空间），要使得每一次一定发生转移，即接受率为1，出现了Gibbssampling。考察二维的概率分布p(x,y)，对于A(x1,y1),B(x1,y2)两个状态点，有满足细致平稳条件。于是得出结论：当对于固定y轴不动，在x轴上变动的任意两点，且转移概率为条件概率p(y|x)时，满足细致平稳条件。因而Gibbssampling的状态点的转移都是沿着坐标轴的。如下图所示当推广到多维度情形下，转移概率为条件概率p(xi|x-i).算法收敛后就得到概率分布p(x)的样本，每一个马尔科夫链的状态可以得到一个样本点。Gibbssampling关于LDA由于整个语料中的词是可以观察得到的𝑤⃗⃗，因而我们需要采样的是条件概率p(𝑧|𝑤⃗⃗)假设整个语料库的词(有10个)被分配的主题（状态）为如下【1235344312】现在要根据第5个单词w5，重新采样它的主题。转移概率：即Gibbssampling公式为：p(𝑧5=其他主题|𝑧−5⃗⃗⃗⃗⃗⃗𝑤⃗⃗)上述公式满足细致平稳条件，公式意思是给第5个单词，即第5维度跳转到其他值的概率，假设跳转到主题1，于是新的马尔科夫链状态点产生。即如下【1235144312】通过不停地采样，到达p(𝑧|𝑤⃗⃗)的平稳分布，然后通过每一个马尔科夫链状态点获得平稳分布的样本。例如：【1235144312】这些样本点作为参数先验分布Dir(𝜃𝑚⃗⃗⃗⃗⃗|𝑎)的多项式分布的数据Mult(𝜃𝑚⃗⃗⃗⃗⃗,𝑛⃗)(参数的似然函数)，从而估计出参数的后验分布Dir(𝜃𝑚⃗⃗⃗⃗⃗|𝑎+𝑛⃗).