记录 Hierarchical Latent Dirichlet Allocation,层次主题模型的学习笔记。 依然大量参考了徐亦达老师的教程。
hLDA改进了什么
改进了两点
引入了Dirichlet Process
引入了层次结构
DP
Dirichlet Process将Dirichlet Distribution的概念扩展到随机过程,一般依概率采样会得到一个样本,一个值,而依据随机过程采样得到的是一个函数,是一个分布。给定DP的超参\(\alpha\),给定度量空间\(\theta\),以及该度量空间上的一个测度\(H\)(称为基分布, Base Distribution),\(DP(\alpha,H)\)中采样得到的就是一个在\(\theta\)上的无限维离散分布\(G\),假如对这个无限维(无限个离散点)做\(\theta\)上的任意一种划分\(A_1,...,A_n\),那么划分之后的\(G\)分布依然满足对应Dirichlet Distribution在超参上的划分:
\[ (G(A_1,...,A_n)) \sim Dir(\alpha H(A_1),...,\alpha H(A_n)) \]
\(G\)定义为Dirichlet Process的一个sample path/function/realization,即\(G=DP(t,w_0) \sim \ DP(\alpha,H)\)。Dirichelt Process的一个realization是一个概率测度,是一个函数,定义域在度量空间\(\theta\)上,函数输出即概率。注意因为是无限维,因此不能预先设置\(\alpha\)的维数,只能设置为一样的\(\alpha\),对比LDA,可以看到DP的超参\(\alpha\)是一个concentration parameter,只能控制G分布趋于均匀分布的确定性,而不能控制G分布趋于怎样的分布,趋于怎样的分布由划分\(A\)决定。
这里可以看到和LDA使用Dir Distribution的区别:DP是直接采样生成了一个概率测度,可以进而生成离散的概率分布;而LDA中对Dir Distribution采样只能得到一个样本,但是这个样本作为了多项式分布的参数,确定了一个多项式分布(也是离散的)。
DP可以用于描述混合模型,在混合组件数量不确定的情况下,通过DP来构造一个组件分配。放在GMM的场景里,假如有n个样本,但我不知道有几个GM来生成这n个样本,那么对样本i,我将其分配给某一个GM,称这个样本i所在GM的参数为\(\theta _i\),那么这个\(\theta\)服从一个基分布\(H(\theta)\),假如\(H\)是连续分布,那么两个样本取到相同的\(\theta\)的概率趋于零,相当于n个样本对应n个GM,那么我们可以把这个\(H\)离散化为G,离散的方式为\(G \sim DP(\alpha,H)\),\(\alpha\)越小越离散,越大则\(G\)越趋近于\(H\)。注意\(H\)也可以是离散的。
DP的两个参数,\(H\)和\(\alpha\),前者决定了\(G\)的每一个离散点的位置,即\(\theta _i\)具体的值;后者决定了离散程度,或者理解为\(\theta\)有多分散,有多不重复,即概率分布是集中的还是分散的,这个Dirichlet Distribution里的\(\alpha\)是一致的。
由于G满足Dirichlet Distribution,因此有很多好的性质,包括对于多项式分布的conjugate,collapsing和splitting,以及renormalization。
\(E[G(A_i)]=H(A_i)\)
\(Var[G(A_i)]=\frac {H(A_i)[1-H(A_i)]}{\alpha + 1}\)
可以看到\(\alpha\)取极端时,方差分别退化为0或者伯努利分布的方差,对应着之前我们说的G去离散化H的两种极端情况。
那么我们想用DP做什么,做一个生成式模型:我们想得到一个概率测度\(G \sim \ DP(H,\alpha)\),根据\(G\)得到每一个样本点i所属的组对应的参数(Group Parameter)\(x_i \sim \ G\),之后根据这个参数和函数\(F\)生成样本点i:\(p_i \sim \ F(x_i)\)
接下来可以用中国餐馆过程(CRP)、折棒过程(Stick Breaking)和Polya Urm模型来细化这个\(x_i\),即将和样本点i对应组的参数拆成样本点i对应的组和每组的参数,写成\(x_i=\phi _{g_i}\),其中\(g\)是样本点的组分配,\(\phi\)是组参数。
接下来套用echen大佬的描述来描述三个模型如何细化\(x_i\)的:
In the Chinese Restaurant Process:
We generate table assignments \(g_1, \ldots, g_n \sim CRP(\alpha)\) according to a Chinese Restaurant Process. (\(g_i\) is the table assigned to datapoint \(i\).)
We generate table parameters \(\phi_1, \ldots, \phi_m \sim G_0\) according to the base distribution \(G_0\), where \(\phi_k\) is the parameter for the kth distinct group.
Given table assignments and table parameters, we generate each datapoint \(p_i \sim F(\phi_{g_i})\) from a distribution \(F\) with the specified table parameters. (For example, \(F\) could be a Gaussian, and \(\phi_i\) could be a parameter vector specifying the mean and standard deviation).
In the Polya Urn Model:
We generate colors \(\phi_1, \ldots, \phi_n \sim Polya(G_0, \alpha)\) according to a Polya Urn Model. (\(\phi_i\) is the color of the ith ball.)
Given ball colors, we generate each datapoint \(p_i \sim F(\phi_i)\).
In the Stick-Breaking Process:
We generate group probabilities (stick lengths) \(w_1, \ldots, w_{\infty} \sim Stick(\alpha)\) according to a Stick-Breaking process.
We generate group parameters \(\phi_1, \ldots, \phi_{\infty} \sim G_0\) from \(G_0\), where \(\phi_k\) is the parameter for the kth distinct group.
We generate group assignments \(g_1, \ldots, g_n \sim Multinomial(w_1, \ldots, w_{\infty})\) for each datapoint.
Given group assignments and group parameters, we generate each datapoint \(p_i \sim F(\phi_{g_i})\).
In the Dirichlet Process:
We generate a distribution \(G \sim DP(G_0, \alpha)\) from a Dirichlet Process with base distribution \(G_0\) and dispersion parameter \(\alpha\).
We generate group-level parameters \(x_i \sim G\) from \(G\), where \(x_i\) is the group parameter for the ith datapoint. (Note: this is not the same as \(\phi_i\). \(x_i\) is the parameter associated to the group that the ith datapoint belongs to, whereas \(\phi_k\) is the parameter of the kth distinct group.)
Given group-level parameters \(x_i\), we generate each datapoint \(p_i \sim F(x_i)\).
折棒过程
折棒过程提供了一种在\(\theta\)上的无限划分,依然令DP的参数为\(\alpha\),折棒过程如下:
\(\beta _1 \sim Beta(1,\alpha)\)
\(A_1 = \beta _1\)
\(\beta _2 \sim Beta(1,\alpha)\)
\(A_2 = (1-\pi _1) * \beta _2\)
这样每次从Beta分布中得到[0,1]上的一个划分,将整个\(\theta\)切成两部分,第一部分作为\(\theta\)上的第一个划分,剩下的部分看成下一次折棒的整体,接着从上面切两部分,第一部分作为\(\theta\)上的第二个划分,像一个棒不断被折断,每次从剩下的部分里折,最后折成的分段就是划分。
DP2CRP
引入一个示性函数,假如两个样本点i,j他们被分配的组件相同,则他们的示性函数\(z\)相同,也就是表征每一个样本属于哪一个组件,\(x_i \sim Component(\theta _{z_i})\)
那么对于混合分布,比如GMM,我们希望得到的是predictive distribution,即已知数据的组件分配情况下,新来了一个未知数据,我想知道他属于哪个组件:
\[ p(z_i=m|z_{not \ i}) \]
结合定义可以知道这个概率应该是和\(H\)无关的,因为我不在乎\(\theta\)具体的值,我只在乎是哪一个\(\theta\),所以predictive distribution与\(\alpha\)密切相关。将其展开:
\[ p(z_i=m|z_{not \ i}) = \frac {p(z_i=m,z_{not \ i})}{p(z_{not \ i})} \\ \]
由于在DP里是划分的类别数可以到无穷多个,因此这里采用了一个小技巧,我们先假设有k类,之后在把k趋于无穷
\[ = \frac {\int _{p_1...p_k} p(z_i=m, z_{not \ i}|p_1...p_k)p(p_1...p_k)}{\int _{p_1...p_k} p(z_{not \ i}|p_1...p_k)p(p_1...p_k)} \]
这里的k个类的概率是符合Dirichlet Distribution的,假设这里的Base Distribution是均匀分布,则
\[ = \frac {\int _{p_1...p_k} p(z_i=m, z_{not \ i}|p_1...p_k)Dir(\frac {\alpha}{k} ... \frac {\alpha}{k})}{\int _{p_1...p_k} p(z_{not \ i}|p_1...p_k)Dir(\frac {\alpha}{k} ... \frac{\alpha}{k})} \]
上面无论分子分母,积分内其实都是一个多项式分布乘以一个Dirichlet分布,根据共轭我们知道后验应该还是一个Dirichlet分布,我们推导一下多项式分布与Dirichlet分布相乘的积分:
\[ \int _{p_1...p_k} p(n_1...n_k|p_1...p_k) p(p_1...p_k|\alpha _1 ... \alpha _k) \\ \]
\[ = \int _{p_1...p_k} Mul(n_1...n_k|p_1...p_k) Dir(p_1...p_k|\alpha _1 ... \alpha _k) \\ \]
\[ = \int _{p_1...p_k} (\frac {n!}{n_1!...n_k!} \prod _{i=1}^k p_i ^{n_i}) \frac {\Gamma(\sum \alpha _i)}{\prod \Gamma (\alpha _i)} \prod _{i=1}^k p_i^{\alpha _i -1} \\ \]
\[ = \frac {n!}{n_1!...n_k!} \frac {\Gamma(\sum \alpha _i)}{\prod \Gamma (\alpha _i)} \int _{p_1...p_k} \prod _{i=1}^k p_i^{n_i+\alpha _i -1} \\ \]
其中积分式内实际上是一个Dirichelt Distribution\(Dir(\alpha _1 + n_1 ... \alpha _k + n_k)\)排除了常数部分,因此积分的结果就是1/常数,即:
\[ = \frac {n!}{n_1!...n_k!} \frac {\Gamma(\sum \alpha _i)}{\prod \Gamma (\alpha _i)} \frac { \prod \Gamma (\alpha _i + n_i)}{\Gamma (n + \sum \alpha _i)} \]
上式包括了三个部分,第一部分的一堆n,它是由多项式分布引入的,代表我们只看划分后每个集合的大小,而不看划分之后每个集合具体的内容,这和我们的需求是不一样的,因此不需要这个常数;第二个部分,是由Dir分布先验产生的,而在predictive distribution中,分布先验都相同,因此抵消了,所以我们主要关注第三部分,回代入predictive distribution那个分式当中。
首先定义一个辅助变量\(n_{l , not \ i} = Count(z_{not \ i} == l)\),那么:
\[ n_1 = n_{1,not \ i} \\ \]
\[ ... \\ \]
\[ n_k = n_{k,not \ i} \\ \]
因为我们是是在求\(p(z_i=m, z_{not \ i})\),那么肯定除了第m类,其余类的数量早已由除了第i个样本以外的样本确定,那么第m类呢?
\[ n_m = n_{m,not \ i} + 1 \]
这样我们就完成了从指示函数表示的概率到多项式分布的转换,分子部分代入之前得到的第三部分有:
\[ \frac {\Gamma(n_{m,not \ i} + \frac {\alpha}{k} + 1) \prod _{l=1,l \neq m}^k Gamma(n_{l,not \ i})}{\Gamma (\alpha + n)} \]
同理计算分子,分子不用考虑第i个样本分给第m类,因此不用在累乘里单独拎出来第m项,形式要简单一些:
\[ \frac {\prod _{l=1}^k \Gamma(n_{l,not \ i})}{\Gamma(\alpha +n -1)} \]
将上面两式相除,再利用Gamma函数\(\Gamma(x) = (x-1) \Gamma (x-1)\)的性质简化,得到:
\[ = \frac {n_{m,not \ i} + \frac {\alpha}{k}}{n + \alpha - 1} \]
再令k趋于无穷,得到:
\[ = \frac {n_{m,not \ i}}{n + \alpha - 1} \]
但是上面这个式子对所有的类别从1到m求和并不为1,而是\(\frac {n-1}{n + \alpha -1}\),剩下一部分概率就设为取一个新类别的概率,这样我们的predictive distribution就算完成了,而且可以发现,这个概率,实际上就对应着中国餐馆过程。
CRP
中国餐馆过程的经典描述就是把n个人,一个一个人来,分到不确定张数目的桌子上,做一个整数集合上的划分。假设集合每个元素是一位顾客,第n位顾客走进了一家参观,则他按照以下概率去选择某一张已经有人的桌子坐下,或者找一张没人的新桌子坐下:
\[ \begin{aligned} p(\text { occupied table } i | \text { previous customers }) &=\frac{n_{i}}{\alpha +n-1} \\ p(\text { next unoccupied table } | \text { previous customers }) &=\frac{\alpha }{\alpha +n-1} \end{aligned} \]
其中\(n_i\)是第i张桌子上已经有的人数,$$是超参数。这样人到桌子的分配就对应了整数集合上的划分。
分析一下,若是选择已经有人的桌子,则顾客倾向于选择人多的桌子;若是在有人的桌子与新桌子之间纠结,则依赖于超参$$
那根据之前的推导,这个\(\alpha\)其实就是Dirichlet Distribution的超参数,且效果完全吻合。由于在CRP中我们base distribution选的是均匀分布,那对应的Dirichlet Distribution选择对称超参,各个\(alpha _i\)相同。那么\(\alpha\)越大,以Dirichlet Distritbuion为参数先验的多项式分布里,取得各个项等概率的可能就越大,在中国餐馆过程中对应着每个顾客进来都想选择一张新桌子,因此每个桌子都只有一个人,等量分配;反之\(\alpha\)越小则越不确定,在中国餐馆过程中桌子的分配也不确定
可以得到第m个人选择之后,桌子数量的期望是\(E(K_m|\alpha ) = O(\alpha \log m)\),具体而言是\(E(K_m|\alpha ) = \alpha (\Psi (\alpha + n) - \Psi (\alpha )) \approx \alpha \log (1 + \frac{n}{\alpha })\), 也就是聚类数的增加与样本数的对数成线性关系。我们可以根据数据量和想要聚类的数量来反估计超参\(\alpha\)的设置。
nCRP
以上仅仅完成了一个利用了DP的不确定数目聚类,我们可以认为餐馆里每个桌子是一个主题,人就是单词,主题模型就是把词分配到主题,把人分配到桌子,但是这样的话和LDA一样,主题之间没有关联。为了建立主题之间的层次关系,Blei提出了嵌套餐馆过程。
在嵌套餐馆过程中,我们统一了餐馆和桌子的概念,餐馆就是桌子,桌子就是餐馆!为什么这么说?首先我们设置一个餐馆作为root餐馆(显然我们要建立一棵树了),然后根据中国餐馆过程选择root餐馆里的一个桌子,餐馆里的每个桌子上都有一张纸条指示顾客第二天去某一个餐馆,因此第二天顾客来到这个餐馆,接着根据CRP选个桌子,同时知晓了自己第三天该去哪个参观。因此桌子对应着餐馆,父节点餐馆的桌子对应着子节点餐馆,每一天就是树的每一层,这样就建立了一个层次结构的中国餐馆过程。
hLDA
接下来我们可以在nCRP的框架上描述hLDA
定义符号
\(z\):主题,假设有\(K\)个
\(\beta\):主题到词分布的参数,Dir先验参数
\(w\):词
\(\theta\):文档到主题的分布
\(\alpha\):文档到主题分布的参数,Dir先验参数
那么可以简单定义LDA:
\[ p(w | \beta) \sim Dir(\beta) \\ p(\theta | \alpha) \sim Dir(\alpha) \\ \theta \sim p(\theta | \alpha) \\ w \sim p(w | \theta , \beta) = \sum _{i=1}^K \theta _i p(w|z=i, \beta _i) \\ \]
hLDA流程如下:
根据nCRP获得一条从root到leaf的长为\(L\)的路径
根据一个\(L\)维的Dirichlet采样一个在路径上的主题分布
根据这L个主题混合生成一个词
概率图如下,其中\(c\)是餐馆,这里把nCRP单独拎出来了,实际上\(c\)决定了主题\(z\),另外\(\gamma\)是nCRP中CRP对应DP的concentration paramter:
Gibbs Sampling in hLDA
定义变量:
\(w_{m,n}\):第m篇文档里的第n个词
\(c_{m,l}\):第m篇文档里路径上第l层选择的主题对应的餐馆,需要采样计算
\(z_{m,n}\):第m篇文档里第n个词分配的主题,需要采样计算
从后验分布中采样的公式分为两部分,第一部分是得到路径,这一部分就会利用到之前的predictive distribution;第二部分是已知路径,剩下的部分就是普通的LDA,最终采样公式为:
\[ p\left(\mathbf{w}_{m} | \mathbf{c}, \mathbf{w}_{-m}, \mathbf{z}\right)=\prod_{\ell=1}^{L}\left(\frac{\Gamma\left(n_{c_{m, \ell},-m}^{(\cdot)}+W \eta\right)}{\prod_{w} \Gamma\left(n_{c_{m, e},-m}^{(w)}+\eta\right)} \frac{\prod_{w} \Gamma\left(n_{c_{m, \ell},-m}^{(w)}+n_{c_{m, \ell}, m}^{(w)}+\eta\right)}{\Gamma\left(n_{c_{m, \ell},-m}^{(\cdot)}+n_{c_{m, \ell}, m}^{(\cdot)}+W \eta\right)}\right) \]