LDA的实现

发表于 | | 阅读次数: |

参考LDA数学八卦和GibbsLDA++实现的LDA模型，以及自己对这个模型的理解

LDA的Gibbs抽样

在上一篇文章中提到了Gibbs抽样的推导最终结果，根据这个推导公式可以在计算机上模拟文档集的生成过程。Gibbs抽样的推导结果如下：

实现思路：
1：先随机为每个单词赋予一个主题
2：根据抽样公式计算当前单词生成每个主题的概率
3：利用掷骰子算法生成下一个主题
4：一直迭代下去，最后计算文档——主题、主题——单词的概率分布

代码放在了Github - LDA上了

数据结构的设计

根据抽样公式公式可知，需要保存的东西有
1：每个主题对应单词的个数
2：每个单词对应某个主题的单词个数
3：每篇文章单词的个数
4：每篇文章的每个主题对应的单词总数

用Python定义的数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 单词到ID的映射表
self.word_map = {}
# ID到单词的映射
self.id2word = []
# 保存每篇文章的词数
self.doc_word_num = []
# 保存每篇文章
self.doc = []
# 保存每篇文章的每个单词对应的主题
self.doc_word_topic = []
# 保存每个主题的词数
self.topic = []
# 保存每篇文章的主题单词个数
self.doc_topic = []
# 这个词属于哪个主题
self.word_id_topic = []
# 文档--主题的概率分布
self.theta = []
# 主题--单词的概率分布
self.phi = []
# 样本中文档的个数
self.M = 0
# 样本中单词的个数
self.V = 0
# 样本中主题的个数
self.K = 0
# 文档——主题的Dirichlet分布参数
self.alpha = 0
# 主题——单词的Dirichlet分布参数
self.beta = 0
# 最大迭代次数
self.max_iter = 0

抽样过程

初始化

首先解析样本文件，随机为每个单词指定一个主题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
随机为这些单词，赋值一个主题
"""
doc_id = 0
while doc_id < doc_num :
	document = self.doc[doc_id]
	word_num = self.doc_word_num[doc_id]
	word_index = 0
	word_topic = []
	while word_index < word_num:
		random_topic = random.randint(0, self.K-1)
		word_id = self.word_map[document[word_index]]
		self.word_id_topic[word_id][random_topic] += 1
		self.topic[random_topic] += 1
		self.doc_topic[doc_id][random_topic] += 1
		#  每个单词对应的主题
		word_topic.append(random_topic)
		word_index += 1
	# 每篇文章m的第n个单词对应的主题 doc_word_topic[m][n] = random_topic
	self.doc_word_topic.append(word_topic)
	doc_id += 1

掷骰子算法

利用上述的抽样公式计算当前单词生成每个主题对应概率数组，在借鉴了GibbsLDA++的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def sampling( self, doc_id, word_index ):
	word_id = self.word_map[self.doc[doc_id][word_index]]
	topic = self.doc_word_topic[doc_id][word_index]
	self.doc_topic[doc_id][topic] -= 1
	self.topic[topic] -= 1
	self.word_id_topic[word_id][topic] -= 1
	self.doc_word_num[doc_id] -= 1

	vbeta = self.V * self.beta
	kalpha = self.K * self.alpha

	k = 0
	pro = []
	while k < self.K:
		"""
		Gibbs Sampling 推导的抽样公式
		"""
		probility = ( self.word_id_topic[word_id][k] + self.beta ) \
				/ ( self.topic[k] + vbeta ) \
				* ( self.doc_topic[doc_id][k] + self.alpha ) \
				/ ( self.doc_word_num[doc_id] + kalpha )

		pro.append(probility)
		k += 1

把对应生成每个主题的概率计算出来之后，在计算机中如何生成指定概率分布条件下的样本值呢？掷骰子算法（像极了轮盘赌算法）的做法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
掷筛子算法
"""
k = 1
while k < self.K:
	pro[k] += pro[k-1]
	k += 1

possible = random.random() * pro[self.K - 1]

topic = 0
while topic < self.K:
	if pro[topic] > possible :
		break
	topic += 1

文档——主题、主题——单词概率分布的计算

最后在再分别计算文档——主题、主题单词的概率分布

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def compute_theta( self ):
  doc_id = 0
  while doc_id < self.M:
    topic_index = 0
    theta_pro = []
  	while topic_index < self.K:
  		temp_pro = ( self.doc_topic[doc_id][topic_index] + self.alpha ) / \
  			   ( self.doc_word_num[doc_id] + self.K * self.alpha )
  		theta_pro.append(temp_pro)
  		topic_index += 1
  	self.theta.append(theta_pro)
  	doc_id += 1

def compute_phi( self ):
  topic_index = 0
  while topic_index < self.K:
  	word_id = 0
  	phi_pro = []
  	while word_id < self.V:
  		temp_pro = ( self.word_id_topic[word_id][topic_index] \
  				+ self.beta ) / ( self.topic[topic_index] \
  				+ self.V * self.beta )	 
  		phi_pro.append(temp_pro)
  		word_id += 1
  	self.phi.append(phi_pro)
  	topic_index += 1

LDA的推断过程

这里我是用PHP实现的，因为工程实践的服务器采用的编程语言是PHP。推断过程也是类似，不断这里需要辅助列表来保存新的样本集合，最终的目的还是计算新来的单词生成对应的每个主题的概率，然后利用掷骰子算法选择命中的主题。不断的迭代这个过程，使主题的分布趋于稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public function sampling( $index )
	{
		$topic = $this->new_doc_word_topic[$index];
		$word = $this->new_doc[$index];

		$word_id = -1;
    /* 在训练好的模型中没有发现此单词，返回-1 */
		if( array_key_exists($word, $this->word2id) )
			$word_id = $this->word2id[$word];
		else return -1;
		$new_word_id = $this->new_word2id[$word];
		$this->new_topic[$topic] -= 1;
		$this->new_word_id_topic[$new_word_id][$topic] -= 1;
		$this->word_num -= 1;
		$Vbeta = $this->V * $this->beta;
		$Kalpha = $this->K * $this->alpha;
		$probe = Array();
    /* 借鉴GibbsLDA++的推断过程 */
		for( $i = 0; $i < $this->K; $i++ ) {
			$p = ($this->word_id_topic[$word_id][$i]
				+ $this->new_word_id_topic[$new_word_id][$i]
				+ $this->beta);
			$p /= ($this->topic[$i] + $this->new_topic[$i] + $Vbeta);
			$p *= (($this->new_topic[$i] + $this->alpha) / ($this->word_num + $Kalpha));
			$probe[$i] = $p;
		}
		for( $i = 1; $i < $this->K; $i++ ) {
			$probe[$i] += $probe[$i-1];
		}
		$priot = ((float)rand() / getrandmax() ) * $probe[$this->K - 1];
		for( $i = 0; $i < $this->K; $i++ ){
			if( $probe[$i] > $priot ) break;
		}
		$this->new_topic[$i] += 1;
		$this->new_word_id_topic[$new_word_id][$i] += 1;
		$this->word_num += 1;
		return $i;
	}

这里需要注意的是：样本集很少的情况下，那么在训练好的模型中很可能无法找到新来的待推断的单词，我的做法就是直接返回-1，也就是忽略了这篇文章中的这个单词。。。

代码放在了Github - SearchEngine上了

思考和感悟

我之前的想法是：

计算每篇文章的主题分布，然后利用计算好的模型推断出用户输入集合的主题分布，根据主题分布的相似性来判断用户在查找哪篇文章。

但实际编码出来之后的效果很不好，
一方面由于文档集中太多无关紧要的单词参与到整个抽样过程，可选的方法有只选文档中的名词或者形容词进行抽样。
一方面可能由于文档集规模很小的缘故，掷骰子算法还是不可避免的产生抖动，也就是说它不能像马尔科夫链那样最终收敛。
还有一方面主题分布之间的相似性度量我选择的是欧式距离，这样的度量在美食文章领域是否准确呢？