lda

2024-04-01 20:56:40

LDA

共轭先验分布

在贝叶斯概率理论中，如果后验概率P(θ|x)和先验概率p(θ)满足同样的分布律，那么，先验分布和后验分布被叫做共轭分布，同时，先验分布叫做似然函数的共轭先验分布
Beta分布是二项式分布的共轭先验分布，而狄利克雷(Dirichlet)分布是多项式分布的共轭分布。
共轭的意思是，以Beta分布和二项式分布为例，数据符合二项分布的时候，参数的先验分布和后验分布都能保持Beta分布的形式，这种形式不变的好处是，我们能够在先验分布中赋予参数很明确的物理意义，这个物理意义可以延续到后续分布中进行解释，同时从先验变换到后验过程中从数据中补充的知识也容易有物理解释。

似然函数
在数理统计学中，似然函数是一种关于统计模型中的参数的函数，表示模型参数中的似然性。似然函数在统计推断中有重大作用，如在最大似然估计和费雪信息之中的应用等等。“似然性”与“或然性”或“概率”意思相近，都是指某种事件发生的可能性，但是在统计学中，“似然性”和“概率”（或然性）又有明确的区分。概率用于在已知一些参数的情况下，预测接下来的观测所得到的结果，而似然性则是用于在已知某些观测所得到的结果时，对有关事物的性质的参数进行估计。
在这种意义上，似然函数可以理解为条件概率的逆反

reference
LDA数学八卦
变分推断求解 http://blog.csdn.net/happyer88/article/details/46723941
https://segmentfault.com/a/1190000012215533

符号含义: N：所有词的数量
V:所有词的种类数量
K:主题数量
D:文档数
$w^j=1\ and\ w^{-j}=0$ wj=1 and w−j=0
using superscripts to denote components

summary:：

LDA首先在主题的词分布的分布中抽取K次，得到K个主题的分布()。并以此对所有文档采用该先验分布。
LDA中然后从主题分布的分布抽样1次得到一篇文档的主题分布，然后该主题分布不变的情况下每个词抽样N次得到N的词的主题。
对于所有文档中，每个文档的主题分布的系数，依然未知；对于K个主题中，每个主题的词分布的系数，依然未知；
目的就是已知 $\alpha, \beta$ α,β的情况下，求3中参数，使得 $p(w|\alpha,\beta)$ p(w∣α,β)最大，最大likelihood。
方法有两种，一种是collapsed gibbs sampling，一种是variational inference。

gibbs sampling

对LDA exact inference很难,一般使用approximate inference，其中gibbs sampling更加简单易懂；
gibbs sampling是mcmc算法的一个特例，运行方式是每次选取概率向量的一个维度，给定其他维度的变量值sampling出当前维度的值，直到收敛。

初始时根据先验随机地给每个单词分配主题，然后更新5个数据，分别为

nd: M*K（M表示文档数量，K表示主题数量）每个doc中各个topic的词数量（规则矩阵）
nw: V*K （V表示语料库中所有词的数量，相同词合并为一个）词word在主题topic中的数量（规则矩阵）
Z: M*n（n表示对于文档m中所有词的数量，相同词不合并为一个）主题（非规则list集合）
nwsum K （每各topic词的总数）
ndsum M （每各doc中词的总数）

对弈每个文档的每个词（按文档顺序逐个词，一遍中词可能有重复），利用gibbs为每个词采样主题

gibbs updaing rules: $$p(Z_i=k|Z_{-i},w)正比于\frac{n_{k,-i}^{t+\beta_t}{\sum_{t=1}}Vn_{k,-i}^{t+\beta_t}(n_{m,-i}}k+\alpha_k)\$$
sample topic k~ $p(z_i|z_{-i,w})$ p(zi∣z−i,w)
使用更新的 $z_{m,n}$ zm,n对于单词 $w_{m,n}，重新计算n_k^m+=1,n_m+=1,n_k^t+=1,n_k+=1$ wm,n，重新计算nkm+=1,nm+=1,nkt+=1,nk+=1

两个multinomial分布的参数 $主题分布\theta_m和词语分布\phi_k$ 主题分布θm和词语分布ϕk的计算公式如下：
$\theta_{m,k}=\frac{n_m^k+\alpha_k}{\sum_{k=1}^Kn_m^k+\alpha_k}\\ \phi_{k,t}=\frac{n_k^t+\beta_t}{\sum_{t=1}^Vn_k^t+\beta_t}$ θm,k=∑k=1Knmk+αknmk+αkϕk,t=∑t=1Vnkt+βtnkt+βt

def sampling(self,i,j):
    topic = self.Z[i][j]
    word = self.dpre.docs[i].words[j]
    self.nw[word][topic] -= 1
    self.nd[i][topic] -= 1
    self.nwsum[topic] -= 1
    self.ndsum[i] -= 1
    
    Vbeta = self.dpre.words_count * self.beta
    Kalpha = self.K * self.alpha
    self.p = (self.nw[word] + self.beta)/(self.nwsum + Vbeta) * \
             (self.nd[i] + self.alpha) / (self.ndsum[i] + Kalpha)
    for k in xrange(1,self.K):
        self.p[k] += self.p[k-1] 
    
    u = random.uniform(0,self.p[self.K-1])
    for topic in xrange(self.K):
        if self.p[topic]>u:
            break
    
    self.nw[word][topic] +=1
    self.nwsum[topic] +=1
    self.nd[i][topic] +=1
    self.ndsum[i] +=1

def est(self):
    # Consolelogger.info(u"迭代次数为%s 次" % self.iter_times)
    for x in xrange(self.iter_times):
        for i in xrange(self.dpre.docs_count):
            for j in xrange(self.dpre.docs[i].length):
                topic = self.sampling(i,j)
                self.Z[i][j] = topic

如：主题为3个，文档为11个，第一步取出113矩阵; 针对其中一篇文档的中每个词，先从主题分布中选一个主题，再从该主题的词分布中选一个词，即得；其中每个主题下有各个词的分布情况，为1N的矩阵,N为词个数

variational inference

$logp(w|\alpha,\beta)-\int\sum_zq(\theta,z)log\frac{p(\theta,z,w|\alpha,\beta)}{q(\theta,z)}\\ \\ = \int\sum_zq(\theta,z)logp(w|\alpha,\beta)d\theta- \int\sum_zq(\theta,z)log\frac{p(\theta,z,w|\alpha,\beta)}{q(\theta,z)}\\ =\int \sum_z q(\theta,z)log\frac{p(w|\alpha,\beta)q(\theta,z)}{p(\theta,z,w|\alpha,\beta)}d\theta \\ =\int \sum_zq(\theta,z)log\frac{q(\theta,z)}{p(\theta,z|w,\alpha,\beta)}d\theta \\ = D(q(\theta,z|\gamma,\phi)||p(\theta,z|w,\alpha,\beta))$ logp(w∣α,β)−∫z∑q(θ,z)logq(θ,z)p(θ,z,w∣α,β)=∫z∑q(θ,z)logp(w∣α,β)dθ−∫z∑q(θ,z)logq(θ,z)p(θ,z,w∣α,β)=∫z∑q(θ,z)logp(θ,z,w∣α,β)p(w∣α,β)q(θ,z)dθ=∫z∑q(θ,z)logp(θ,z∣w,α,β)q(θ,z)dθ=D(q(θ,z∣γ,ϕ)∣∣p(θ,z∣w,α,β))
即得到：
$logp(w|\alpha, \beta) = L(\gamma,\phi;\alpha,\beta)+D(q(\theta,z|\gamma,\phi)||p(\theta,z|w,\alpha,\beta))$ logp(w∣α,β)=L(γ,ϕ;α,β)+D(q(θ,z∣γ,ϕ)∣∣p(θ,z∣w,α,β))
目标是左边最大，同时我们假设的分布 $q(z,\theta|\gamma,\phi)$ q(z,θ∣γ,ϕ)与实际分布相对熵最小，即右边第二项KL散度最小，所有可以转化为求L的极大值。

真实分布和近似分布

真实
[外链图片转存失败(img-bjQ1SBhJ-1562498931882)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000093)]

1. 此时$\beta$仅仅指的是多项式分布其是一个K*V的矩阵*k为topic的数量，V为词的种类数量 2. $\beta$不是dirichlet分布

近似
[外链图片转存失败(img-oCW7qhoR-1562498931883)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008e)]
即 $\theta到z到w的线断了$ θ到z到w的线断了

求解

$logp(w|\alpha,\beta)=L(\gamma,\phi;\alpha,\beta)+D(q(\theta,z|\gamma,\phi)||p(\theta,z|w,\alpha,\beta))$ logp(w∣α,β)=L(γ,ϕ;α,β)+D(q(θ,z∣γ,ϕ)∣∣p(θ,z∣w,α,β))**
至此优化
$(r^*,\phi^*)=argmin_{r,\phi}D(q(\theta,z|\gamma,\phi)||p(\theta,z|w,\alpha,\beta))$ (r∗,ϕ∗)=argminr,ϕD(q(θ,z∣γ,ϕ)∣∣p(θ,z∣w,α,β))转化为 $L(\gamma,\phi;\alpha,\beta)$ L(γ,ϕ;α,β)的最大化问题，也就是基于 $\gamma,\phi最大化L$ γ,ϕ最大化L
[外链图片转存失败(img-LlXN7CIq-1562498931883)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008b)]
[外链图片转存失败(img-Sxa3CjMg-1562498931884)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008a)]
variational inference
: 已知 $\alpha, \beta$ α,β
[外链图片转存失败(img-s8t7JIfd-1562498931884)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000091)]

1. $\phi_n$ ϕn为文档第n个词的主题分布情况为1K矩阵
$2. \gamma$ 2.γ为1K矩阵

parameter estimater
:
给定一系列文档 $\{w_1,w_2,..., w_M\}$ {w1,w2,...,wM}, 目标找到 $\alpha, \beta$ α,β能够最大化marignal log likelihood of data
$\ell(\alpha, \beta) = \sum_{d=1}^Mlog p(w_d|\alpha, \beta)$ ℓ(α,β)=d=1∑Mlogp(wd∣α,β)

[外链图片转存失败(img-Om2HVSvt-1562498931885)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000094)]

在M步时有
[外链图片转存失败(img-j8TWjXUw-1562498931885)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000084)]
[外链图片转存失败(img-Nm2dZBDW-1562498931885)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000097)]
其中 $\alpha$ α可以quasi-newton方法求得

EM算法

summary

变分推断

求解过程实际上求解 $log\ p(w|α,η)$ log p(w∣α,η),得到其下界函数 $L(\lambda,\phi, \gamma; \alpha, \eta) = E_q\; log{p(\theta,\beta, z, w| \alpha, \eta) } - E_q\; log{q(\beta, z, \theta|\lambda,\phi, \gamma)}$ L(λ,ϕ,γ;α,η)=Eqlogp(θ,β,z,w∣α,η)−Eqlogq(β,z,θ∣λ,ϕ,γ)
可以通过求解该下届，得到逼近该数值
通过计算化简得到该L函数关于 $\lambda,\phi, \gamma$ λ,ϕ,γ的表达式。
通过对ELBO函数求导并令其为0，得到 $\lambda,\phi, \gamma$ λ,ϕ,γ的表达式的值，三者之间存在联系，迭代更新直到收敛。得到固定 $\alpha, \eta$ α,η情况下的最大值。
由ELBO函数对 $\alpha, \eta$ α,η求导，另其为0，得到其对应的表达式。由4步得到的值对两者进行更新
重复上述过程，即求解。

Q函数也即 $log\ p(w|α,η)$ log p(w∣α,η)

原则上求Q函数，然后再极大化Q函数
对于单隐变量条件下Q函数为 $E_{z}[log \ p(z,o|\lambda)|o,\lambda^i]=\sum_z p(z|o,\lambda^i)log\ p(z,o|\lambda)$ Ez[log p(z,o∣λ)∣o,λi]=∑zp(z∣o,λi)log p(z,o∣λ)
LDA中隐变量分布 $p(\theta,\beta,z|w, \alpha,\eta)$ p(θ,β,z∣w,α,η)不可直接得到,由 $q(\theta,\beta,z|\lambda, \phi,\gamma)近似得到$ q(θ,β,z∣λ,ϕ,γ)近似得到，得到该分布后，代入Q函数，极大化求取 $\alpha, \eta$ α,η
在求Q函数时，由KL散度代表两分布的差异性，此时第一个分布的参数 $w, \alpha, \eta$ w,α,η已知，求KL散度时，可转化为求ELBO（evidence lower bound）的极大值
Q步时，需迭代求取参数 $\lambda, \phi, \gamma$ λ,ϕ,γ，直到收敛
M步时，同样需迭代求取参数 $\alpha, \gamma$ α,γ，直到收敛
为KaTeX parse error: No such environment: align at position 7: \begin{̲a̲l̲i̲g̲n̲}̲ D(q(\beta, z, …

首先求隐变量 $\theta,Z$ θ,Z的期望，隐变量的后验概率可以计算得到：
$p(\theta,z|w,\alpha,\beta)=\frac{p(\theta,z,w|\alpha,\beta)}{p(w|\alpha,\beta)}$ p(θ,z∣w,α,β)=p(w∣α,β)p(θ,z,w∣α,β)

[外链图片转存失败(img-GVWQam2M-1562498931886)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000092)]

所以作者考虑变分推断的方法。简化原先的LDA模型，找一个与原来不能直接求解的后验概率等价或近似的分布q，这个q要好解，一般比较简单粗暴的方法就是直接假设q中θ,z相互独立.对原模型去掉θ,z,w之间的边，删掉w，这样θ和z就相互独立了。
从模型中可以得出 $\theta,z的分布q:$ θ,z的分布q:

$q(\theta,z|\gamma,\phi)=q(\theta|\phi)\prod_{n=1}^{N}q(z_n|\phi_n)$ q(θ,z∣γ,ϕ)=q(θ∣ϕ)n=1∏Nq(zn∣ϕn)

$logp(w|\alpha,\beta)=log\int\sum_zp(\theta,z,w|\alpha,\beta)d\theta \\ =log\int\sum_z\frac{p(\theta,z,w|\alpha,\beta)q(\theta,z)}{q(\theta,z)}d\theta$ logp(w∣α,β)=log∫z∑p(θ,z,w∣α,β)dθ=log∫z∑q(θ,z)p(θ,z,w∣α,β)q(θ,z)dθ

[外链图片转存失败(img-In4x0FxB-1562498931886)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000089)]
E-step
实际模型图
[外链图片转存失败(img-LdmzaVZV-1562498931886)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000083)]

带有 $\lambda$ λ的假设模型图为
[外链图片转存失败(img-HXkOS7rl-1562498931887)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000086)]

$$L(\gamma,\phi;\alpha,\beta) = log\Gamma(\sum_{j=1}^{k\alpha_i)-\sum_{i=1}}klog\Gamma(\alpha_i)+\sum_{i=1}^{{k}(\alpha_i-1)(\Psi(\gamma_i)-\Gamma(\sum_{j=1}}k\gamma_j)) \

\sum_{n=1}^N\sum_{k=1}k\psi_{ni}(\Psi(\gamma_i)-\Psi(\sum_{j=1}^k \gamma_j)) \
\sum_{n=1}^N\sum_{i=1}k\sum_{j=1}^{V\psi_{ni}w_n}jlog\beta_{ij} \
-log\Gamma(\sum_{j=1}^{k\gamma_j)+\sum_{i=1}}klog\Gamma(\gamma_i)-\sum_{i=1}^{k(\gamma_i-1)(\Psi(\gamma_i)-\Psi(\sum_{j=1}}k\gamma_j)) \
-\sum_{n=1}^N\sum_{i=1}k\phi_{ni}log\phi_{ni}$$

[外链图片转存失败(img-T3uX6YZB-1562498931887)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008d)]
[外链图片转存失败(img-T6aJzV7q-1562498931887)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000090)]

M-step
这一步，我们根据E-step求出来的(γ,ϕ)，最大化L(γ,ϕ|α,β)，求解模型参数α,β：用拉格朗日乘数法求解参数β，用牛顿方法求解参数α。

online learing

[外链图片转存失败(img-irQE5zCC-1562498931887)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000096)]

[外链图片转存失败(img-FzjkC8S5-1562498931888)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008f)]\

$E[log\theta_i|\alpha] = \Psi(\alpha_i)-\Psi(\sum_{j=1}^k\alpha_j)$ E[logθi∣α]=Ψ(αi)−Ψ(j=1∑kαj)
[外链图片转存失败(img-E8zD3OwR-1562498931888)(leanote://file/getImage?fileId=5c4db9e68613cf02ec000098)]

question

对于K个主题，是这所有的K各位主题满足dirichlet分布，还是单个主题满足分布。
对于所有的文档，主题的词分布都相同，1中疑问针对于先验分布的过程。
无论1怎样，结果都不变。
再读发现是主题都是独立抽取后定义的！

[外链图片转存失败(img-fd96EOgt-1562498931888)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000088)]

VB 优势

faster than and as accurate as MCMC, which makes it an attractive option when applying Bayesian models to large datasets

appendix

相对熵（kl散度）

p(x)和q(x)是X取值的两个概率分布，则p对q的相对熵为
$D(p||q)=\sum_{i=1}^{n}p(x)log{\frac{p(x)}{q(x)}}$ D(p∣∣q)=i=1∑np(x)logq(x)p(x)
在一定程度上，熵可以度量两个随机变量的距离。KL散度是两个概率分布p和q差别的非对称性的度量。KL散度是用来度量使用基于Q的编码来编码来自p的样本平均所需的额外的位元数。典型情况下，p表示数据的真实分布，q表示数据的理论分布，模型分布或p的近似分布。

性质

（1）尽管KL散度从直观上是个度量或距离函数，但并不是一个真正的度量或距离，因为它不具有对称性
$D(p||q)!=D(q||p)$ D(p∣∣q)!=D(q∣∣p)
(2) 相对熵的值为非负值，即
$D(p||q)>=0$ D(p∣∣q)>=0

吉布斯不等式

若 $\sum_{i=1}^{n}p_i=\sum_{i=1}^{n}q_i=1，且p_i, q_i\in (0,1]$ ∑i=1npi=∑i=1nqi=1，且pi,qi∈(0,1],则有：
$-\sum_{i=1}^{n}p_ilogp_i\leq-\sum_{i=1}^{n}p_ilogq_i\\当且仅当p_i=q_i 对于任意i等号成立$ −i=1∑npilogpi≤−i=1∑npilogqi当且仅当pi=qi对于任意i等号成立
这样有
$0\ge\sum_{i=1}^{n}p_ilogq_i-\sum_{i=1}^{n}p_ilogp_i=\sum_{i=1}^{n}p_ilog(q_i/p_i)=-D_{KL}(P||Q)$ 0≥i=1∑npilogqi−i=1∑npilogpi=i=1∑npilog(qi/pi)=−DKL(P∣∣Q)
证明吉布斯不等式

已知 $ln(x)\le x-1$ ln(x)≤x−1等号成立当且仅当x=1.
[外链图片转存失败(img-N9YO3of3-1562498931889)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000095)]

####应用
相对熵可以衡量两个随机分布之间的距离，当两个随机分布相同时，他们的相对熵为0，当两个随机分布的差别增大时，他们的相对熵会增大。
所以可以比较文本的相似度，先统计出词的频率，然后计算KL散度就行了。另外，在多指标系统评估中，指标权重分配是一个重点和难点，通过相对熵可以处理。

L函数

$L(\gamma,\phi;\alpha,\beta) = E_q[logp(\theta,z,w|\alpha,\beta)]-E_q[logq(\theta,z)] \\ = E_q[logp(\theta|\alpha)]+E_q[logp(z|\theta)]+E_q[logp(w|z,\beta)] \\ -E_q[logq(\theta)]-E_q[logq(z)]$ L(γ,ϕ;α,β)=Eq[logp(θ,z,w∣α,β)]−Eq[logq(θ,z)]=Eq[logp(θ∣α)]+Eq[logp(z∣θ)]+Eq[logp(w∣z,β)]−Eq[logq(θ)]−Eq[logq(z)]

$(1) E_q[logp(\theta|\alpha)]=E_q[log \frac{\Gamma(\sum_{i=1}^k\alpha_i)}{\prod_{i=1}^k\Gamma(\alpha_i)}\theta_1^{\alpha_1-1}...\theta_k^{\alpha_k-1}] \\ =E_q[log\prod_{i=1}^k\theta_i^{\alpha_i-1}+log\Gamma(\sum_{i=1}^k\alpha_i)-log\prod_{i=1}^k\Gamma(\alpha_i)] \\ = log\Gamma(\sum_{i=1}^k\alpha_i)-\sum_{i=1}^klog\Gamma(\alpha_i)+\sum_{i=1}^k(\alpha_i-1)(E_q(log\theta_i)) \\ = log\Gamma(\sum_{i=1}^k\alpha_i)-\sum_{i=1}^klog\Gamma(\alpha_i)+\sum_{i=1}^k(\alpha_i-1)(\Psi(\alpha_i)-\Psi(\sum_{j=1}^k\gamma_j)))$ (1)Eq[logp(θ∣α)]=Eq[log∏i=1kΓ(αi)Γ(∑i=1kαi)θ1α1−1...θkαk−1]=Eq[logi=1∏kθiαi−1+logΓ(i=1∑kαi)−logi=1∏kΓ(αi)]=logΓ(i=1∑kαi)−i=1∑klogΓ(αi)+i=1∑k(αi−1)(Eq(logθi))=logΓ(i=1∑kαi)−i=1∑klogΓ(αi)+i=1∑k(αi−1)(Ψ(αi)−Ψ(j=1∑kγj)))
$(2) E_q[logp(z|\theta)]=\int\sum_zq(\theta,z|r,\phi)log(z|\theta)d\theta \\ = \int\sum_zq(\theta|\gamma)q(z|\phi)log(z|\theta)d\theta \\ = \int q(\theta|\gamma)\sum_zq(z|\phi)log(z|\theta)d\theta \\ = \sum_{n=1}^N\sum_{i=1}^k q(z_n=i|\phi_n)log p(z_n=i|\phi) \\ = \sum_{n=1}^N\sum_{i=1}^k\phi_{ni}log \phi_i \\ = \sum_{n=1}^N\sum_{i=1}^k\phi_{ni}(\Gamma(\gamma_i)-\Gamma(\sum_{j=1}^k)\gamma_)j$ (2)Eq[logp(z∣θ)]=∫z∑q(θ,z∣r,ϕ)log(z∣θ)dθ=∫z∑q(θ∣γ)q(z∣ϕ)log(z∣θ)dθ=∫q(θ∣γ)z∑q(z∣ϕ)log(z∣θ)dθ=n=1∑Ni=1∑kq(zn=i∣ϕn)logp(zn=i∣ϕ)=n=1∑Ni=1∑kϕnilogϕi=n=1∑Ni=1∑kϕni(Γ(γi)−Γ(j=1∑k)γ)j

(3) $E_q[logp(w| alpha,\beta)] \\ = \int \sum_z q(\theta,z|\gamma,\phi)logp(w|z,\beta)d\theta \\ = \sum_{z_1} ... \sum_{z_n}\prod_{n=1}^N q(z_n|\phi_n)log (\prod_{n=1}^N p(w_n|z_n,\beta_{z_n}))$ Eq[logp(w∣alpha,β)]=∫z∑q(θ,z∣γ,ϕ)logp(w∣z,β)dθ=z1∑...zn∑n=1∏Nq(zn∣ϕn)log(n=1∏Np(wn∣zn,βzn))

(4)
…

$$L(\gamma,\phi;\alpha,\beta) = log\Gamma(\sum_{j=1}^{k\alpha_i)-\sum_{i=1}}klog\Gamma(\alpha_i)+\sum_{i=1}^{{k}(\alpha_i-1)(\Psi(\gamma_i)-\Gamma(\sum_{j=1}}k\gamma_j)) \

\sum_{n=1}^N\sum_{k=1}k\psi_{ni}(\Psi(\gamma_i)-\Psi(\sum_{j=1}^k \gamma_j)) \
\sum_{n=1}^N\sum_{i=1}k\sum_{j=1}^{V\psi_{ni}w_n}jlog\beta_{ij} \
-log\Gamma(\sum_{j=1}^{k\gamma_j)+\sum_{i=1}}klog\Gamma(\gamma_i)-\sum_{i=1}^{k(\gamma_i-1)(\Psi(\gamma_i)-\Psi(\sum_{j=1}}k\gamma_j)) \
-\sum_{n=1}^N\sum_{i=1}k\phi_{ni}log\phi_{ni}$$

$\Psi(x)为digamma function$ Ψ(x)为digammafunction $\Psi(x)=\frac{ln(\Gamma(x))}{x}$ Ψ(x)=xln(Γ(x)) $=\frac{\Gamma^{'}(x)}{\Gamma(x)}$ =Γ(x)Γ′(x)

[外链图片转存失败(img-Lmh3dRYd-1562498931889)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000087)]

online variational inference

batch variational bayes for LDA
另一个假设分布 $q(z,\theta, \beta)$ q(z,θ,β)
$log p(w|\alpha,\eta)\geq \zeta(w,\phi,\gamma,\lambda) = E_q[log p(w,z,\theta,\beta|\alpha,\eta)]-E_q[log q(z,\theta,\beta)]$ logp(w∣α,η)≥ζ(w,ϕ,γ,λ)=Eq[logp(w,z,θ,β∣α,η)]−Eq[logq(z,θ,β)]
最小化KL是散度 $q(z,\theta,\beta)$ q(z,θ,β)与 $p(z,\theta,\beta|w,\alpha,\eta)$ p(z,θ,β∣w,α,η)

$q(z_{di}=k) = \phi_{dw_{di}k} \\ q(\theta_d)= Dirichlet(\theta_d;\gamma_d)\\ q(\beta_k)=Dirichlet(\beta_k;\gamma_k)$ q(zdi=k)=ϕdwdikq(θd)=Dirichlet(θd;γd)q(βk)=Dirichlet(βk;γk)

求解即：
$\phi_{dwk} \propto exp\{E_q[log \theta_{dk}]+E_q[log \beta_{kw}]\} \\ \gamma_{dk} = \alpha+\sum_w n_{dk}\phi_{dwk}\\ \lambda_{kw} = \eta+\sum_d n _{dw}\phi_{dwk} (5)$ ϕdwk∝exp{Eq[logθdk]+Eq[logβkw]}γdk=α+w∑ndkϕdwkλkw=η+d∑ndwϕdwk(5)

$E_q[log \theta_{dk}] = \Psi(\gamma_{dk})-\Psi(\sum_{i=1}^K \gamma_{di});\ E_q[log \beta_{kw}] = \Psi(\lambda_{kw})-\Psi(\sum_{i=1}^W \lambda_{ki}) (6)$ Eq[logθdk]=Ψ(γdk)−Ψ(i=1∑Kγdi); Eq[logβkw]=Ψ(λkw)−Ψ(i=1∑Wλki)(6)

[外链图片转存失败(img-K7sDiueg-1562498931890)(leanote://file/getImage?fileId=5c4db9e58613cf02ec00008c)]
[外链图片转存失败(img-xWSVWlDc-1562498931890)(leanote://file/getImage?fileId=5c4db9e68613cf02ec000099)]

算法1有constant memory requirements 和比collapsed gibbs sampling更快的收敛速度;
但是每次迭代过程中都需要扫描the entire corpus。

online variational inference algorithm for fitting $\lambda$ λ,the parameters to the variabtional posterior over the topic distributions $\beta$ β,该算法和batch VB一样简单，并且对于大数据集收敛速度更快。用到inference.

summary

变分推断假设隐含量相互独立independent
gibbs sampling 模拟采样更准确，但是收敛速度比较慢；variational inference采用一个对后验概率的近似，求解速度快，但近似用的比较多，没有gibbs那样准确。

other
变分贝叶斯算法理解及推导http://blog.huajh7.com/2013/03/06/variational-bayes/

变分推断https://www.zhihu.com/question/41765860?sort=created

mean field

平均场假设复杂的多变量Z可拆分为一系列相互独立的多变量Zi，i=1,⋯,M，且q分布可以因子化为这些多变量集的乘积
$q(Z)=\prod_{i=1}^Mq_i(Z_i)$ q(Z)=i=1∏Mqi(Zi)

在实践中使用平均场方法时，最重要的是考虑如何对隐变量进行拆解，以及假设各变量子集服从何种分布。

ref:

https://blog.csdn.net/step_forward_ML/article/details/78077383

collapsed VB for LDA

结合标准VB和collapsed Gibbs sampling的优点
模拟了参数对隐变量的依赖，平均场近似，实际上变量之间仍可认为是相互独立的，只是非常弱的依赖关系

TODO

[] collapsed
[] mean field
[] PRML

Ref:
1.Teh, Y. W., Newman, D. & Welling, M. A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation: (Defense Technical Information Center, 2007). doi:10.21236/ADA629956

#perplexity

[外链图片转存失败(img-xfCYn1rD-1562498931890)(leanote://file/getImage?fileId=5c4db9e58613cf02ec000085)]
由公式可知，句子概率越大，语言模型越好，迷惑度越小
评价语言模型的好坏
这节的核心就是句子概率越大，语言模型越好，迷惑度越小;
我们的LDA模型有多不确定它是属于某个topic的”。topic越多，Perplexity越小，但是越容易overfitting。

Ref:

https://www.zhihu.com/question/58482430

码农公寓

LDA