LDA漫游指南阅读笔记--Gibbs采样
Gibbs采样公式:
LDA并行考虑:
列 某文章的单词A依赖于另外一个文章相同单词A采样后修改的nw,nwsum行 同一篇文章的后一个单词依赖于前一个单词修改后的nd,ndsum
主题 同一个主题后一次采样依赖于同一个主题前一次采样的nwsum
解决方案:
1. AD-LDA 按行进行拆分,nd,ndsum拆分到各台机器, nw,nwsum被完全copy到各台机器.各个节点一轮执行完毕后,进行一次merge.缺点: 1) nw,nwsum互不知道其他机器的存在进行采样,会带来误差; 2)nw内存空间浪费
2. Spark-lda 转换成wordid排序后,只有同一行和同一列的会存在依赖,其他可以采用对角线法组内并行组间串行的方法。在切分时如果不够均衡可以采用随机交换行列的方式找各块差距最大值最小的那一次。整个算法中nwsum肯定会有冲突也就是这个算法的误差所在。采用global update的方法,每台机器merge back。 之后同一个单词的nw和同一个文档的nd统计量合并(spark中采用broadcast的方法)。该算法混淆度已经能和单机差不多。
#
#伪代码
#
输入:文章集合(分词处理后),K(类的个数)
输出:已经随机分派了一次的lda模型
begin
申请几个统计量:
p 概率向量 维度:K
nw 词在类上的分布 维度:M*K 其中M为文章集合的词的总个数
nwsum 每个类上的词的总数 维度:K
nd 每篇文章中,各个类的词个数分布 维度:V*K 其中V为文章的总个数
ndsum 每篇文章中的词的总个数 维度:V
Z 每个词分派一个类 维度:V*每篇文章词的个数
theta 文章->类的概率分布 维度:V*K
phi 类->词的概率分布 维度:K*M
#初始化随机分配类
for x in 文章数:
统计ndsum[文章id][词的个数]
for y in 每篇文章的词个数:
给所有词随机分派一个类
词在此类上的分布数目+1
此文章中此类的词的个数+1
此类的总词数 +1
end
#
#伪代码
#
输入:初始化后的lda_model,迭代次数iter_times,超参数α、β,聚类个数K
输出:theta(文章对应类的分布概率),phi(类对应词的分布概率),tassgin(文章中每个词的分派类结果),twords(每个类topN个高频词)
begin
for i in 迭代次数:
for m in 文章个数:
for v in 文章中词:
取topic = Z[m][v]
令nw[v][topic]、nwsum[topic]、nd[m][topic]的统计量均-1
计算概率p[] #p[]为此词属于每个topic的概率
for k in (1,类的个数-1):
p[k] += p[k-1]
再随机分派一次,记录被分派的新的topic
令nw[v][new_topic]、nwsum[new_topic]、nd[m][new_topic]的统计量均+1
#迭代完成后
输出模型
end