Brains


on NLP, LDA主题模型的实现及思考

LDA 的实现

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

LDA的Gibbs抽样

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

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

代码放在了Github - LDA上了

数据结构的设计

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

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

# 单词到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  

抽样过程

初始化

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

    """
        随机为这些单词,赋值一个主题
        """
        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++的实现如下

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

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

      """
            掷筛子算法
            """
            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

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

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

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。推断过程也是类似,不断这里需要辅助列表来保存新的样本集合,最终的目的还是计算新来的单词生成对应的每个主题的概率,然后利用掷骰子算法选择命中的主题。不断的迭代这个过程,使主题的分布趋于稳定。

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上了

思考和感悟

我之前的想法是:

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

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

comments powered by Disqus

纸上得来终觉浅,绝知此事要躬行~