HDP(层次狄利克雷过程)算法代码实现细节梳理（Java）

朴灿烈づ我的快乐病毒、 2022-01-05 06:57 334阅读 0赞

本文作者：合肥工业大学 电子商务研究所 钱洋 email：1563178220@qq.com 。  
**内容可能有不到之处，欢迎交流**。

**未经本人允许禁止转载**。

### 文章目录 ###

*  HDP简介
 *  有向图表示
 *  CRF的关键
 *  HDP的采样
 *  编程角度解读
 *   *  采样桌子
     *  采样主题
     *  完整代码
 *  参考

# HDP简介 #

Teh Y W, Jordan M I, Beal M J, et al. Sharing clusters among related groups: Hierarchical Dirichlet processes\[C\]//Advances in neural information processing systems. 2005: 1385-1392.

来自于2005年，NIPS。HDP可以说是做非参贝叶斯推理必须的模型。

学习该模型前，需要了解DP以及DP的构造方式(stick-breaking construction)。

针对DP过程，**其对应求解策略为中餐馆过程** ；针对HDP，**其求解策略为中餐馆连锁(CRF,Chinese restaurant franchise)**。

关于DP和HDP的学习也可以参照我之前写的几篇博客：  
中餐馆过程：[https://blog.csdn.net/qy20115549/article/details/52371443][https_blog.csdn.net_qy20115549_article_details_52371443]  
我个人分享的PPT：Dirichlet Process和Hierarchical Dirichlet Process的理解([https://blog.csdn.net/qy20115549/article/details/79663483][https_blog.csdn.net_qy20115549_article_details_79663483])  
Dirichlet Process and Stick-Breaking:[https://blog.csdn.net/qy20115549/article/details/62041632][https_blog.csdn.net_qy20115549_article_details_62041632]

# 有向图表示 #

如下为两种有向图的表示形式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 1]

# CRF的关键 #

**HDP之所以使用中餐馆连锁求解，其原因保证餐馆(文档)与餐馆之间是共享菜单(主题)的，这一点非常关键**。如果不能保证共享主题，也就无法进行主题的发现。如下为CRF的示意图。该图来自于中科院曾大军研研究团队。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 2]  
下图，为本人总结的CRF的特点：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 3]

# HDP的采样 #

HDP的采样有多样，其中使用比较多的便是Collapsed Gibbs Sampling。**其采样共分为两个层次，可参考我的PPT**，这里直接上图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 4]  
其中，顾客对应的是每篇文档的每个词。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 5]  
对于每个顾客，可以选择旧桌子就坐，概率和桌子上的人数成正比，也可以选择一张新桌子就坐。**需要注意的是：\*\*如果选择的旧桌子，该顾客就不用点菜了，即**文档该词对应的主题和桌子原有的主题一致，不更新\*\*。  
**如果选择了新桌子，那么则需要进行下一步，为其分配一道菜，即主题**。  
**这种策略也就是编程实现的核心思想**。

如下是为新桌子分配主题的公式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 6]

# 编程角度解读 #

## 采样桌子 ##

如下为编程需要使用到的第一个公式：  
![在这里插入图片描述][20190623100301140.png_pic_center]  
该项表示新桌子生成单词的概率。

针对这个公式，我们可以看到，**在编程时需要统计的变量包括**： p ( x j i ∣ . . . ) p\\left ( x\_\{ji\}|... \\right ) p(xji∣...),所有预料中主题 k k k对应的桌子总数目 m ⋅ k m\_\{\\cdot k\} m⋅k，语料中桌子的总数目 m ⋅ ⋅ m\_\{\\cdot \\cdot\} m⋅⋅，观测数据的条件概率分布 f k − x j i ( ⋅ ) f\_\{k\}^\{-x\_\{ji\}\}\\left ( \\cdot \\right ) fk−xji(⋅)和 f k n e w − x j i ( ⋅ ) f\_\{k^\{new\}\}^\{-x\_\{ji\}\}\\left ( \\cdot \\right ) fknew−xji(⋅)。

注意观测数据的条件概率分布为：  
![在这里插入图片描述][201906231018364.png_pic_center]  
**这个公式看起来很复杂。但实际上，其和LDA的生成词的过程是一致的，利用共轭分布的性质是可以直接得到的。**

如下为采样桌子的公式：  
![在这里插入图片描述][20190623102017658.png_pic_center]  
基于这个公式，**可以看到编程需要统计的变量有**：文档桌子对应的词汇数量 n j t ⋅ − j i n\_\{jt\\cdot \}^\{-ji\} njt⋅−ji和用于轮盘赌的变量 p ( t j i = t ) p\\left ( t\_\{ji\}=t \\right ) p(tji=t)。

/** * sample a table for a word * * new table or old table * * if new table, choose a topic for this table */
    	int sampleTable(int d, int n) { 
    		double pSum = 0.0;
    		f = ensureCapacity(f, K);
    		p = ensureCapacity(p, ndtable[d]);
    		double fNew = gamma / V;
    		for (int k = 0; k < K; k++) { 
    			f[k] = (nkw[k][docword[d][n]] + beta) / 
    					(nksum[k] + V*beta);
    			fNew += nk_table[k] * f[k];
    		}
    		for (int tab = 0; tab < ndtable[d]; tab++) { 
    			if (ndtable_wordCount[d][tab] > 0) 
    				pSum += ndtable_wordCount[d][tab] * f[d_tableToTopic[d][tab]];
    			p[tab] = pSum;
    		}
    		pSum += alpha * fNew / (totalTablesNum + gamma); // Probability for t = tNew
    		p[ndtable[d]] = pSum;
    		double u =  (new Random()).nextDouble() * pSum;
    		int j;
    		for (j = 0; j <= ndtable[d]; j++)
    			if (u < p[j]) 
    				break;	// which table assignment for the word
    		return j;
    	}

由于非参模型，其主体数目和每篇文档的桌子数目是在不断变化的。因此**需要注意和桌子统计相关的变量、和主题相关的变量要扩容**，以防止**数组操作越界**。

## 采样主题 ##

如果文档中的某单词背分配了新桌子，那么则需要对该桌子分配一个主题，如果为采样公式：  
![在这里插入图片描述][20190623103136527.png_pic_center]  
从这个公式中，可以看到编程时需要统计的变量有： p ( k j t n e w = k ) p\\left ( k\_\{jt^\{new\}\}=k \\right ) p(kjtnew=k)。

如下为对应的Java代码：

/** * * if new table, choose a topic for this table * */
    	private int sampleTopic() { 
    		double pSum = 0.0;
    		p = ensureCapacity(p, K);
    		for (int k = 0; k < K; k++) { 
    			pSum += nk_table[k] * f[k];
    			p[k] = pSum;
    		}
    		pSum += gamma/ V;
    		p[K] = pSum;
    		double u = (new Random()).nextDouble() * pSum;
    		int k;
    		for (k = 0; k <= K; k++)
    			if (u < p[k])
    				break;
    		return k;
    	}

## 完整代码 ##

本人的完整代码，会在之后上传到Github中，即本人所编写的TopicModel4J:[https://github.com/soberqian/TopicModel4J][https_github.com_soberqian_TopicModel4J]

如下为该该代码模型的输入：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 7]  
即一行表示一个文档。

模型的使用方式：

public static void main(String[] args) { 
    		HDP hdp = new HDP("data/rawdata_process_lda", "gbk", 10, 1, 0.01,
    				0.1, 1000, 50, "data/ldaoutput/");
    		hdp.MCMCSampling();
    	}

调用该模型非常的简单，只需要输入文件目录和输入目录以及HDP的参数就行。

输入包括文档主题分布和主题词分布，例如：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 8]

# 参考 #

周建英, 王飞跃, 曾大军. 分层 Dirichlet 过程及其应用综述\[J\]. 自动化学报, 2011, 37(4): 389-407.

[https_blog.csdn.net_qy20115549_article_details_52371443]: https://blog.csdn.net/qy20115549/article/details/52371443
[https_blog.csdn.net_qy20115549_article_details_79663483]: https://blog.csdn.net/qy20115549/article/details/79663483
[https_blog.csdn.net_qy20115549_article_details_62041632]: https://blog.csdn.net/qy20115549/article/details/62041632
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20211229/8f59e311f0d7420d88c4b7220cd404de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20211229/ea148e6f552e4b6c91ee45b2ae9e653c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20211229/93748106c8104a13ac63bb9760f96ff4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20211229/8b30edea63024374ae9827c3b64a2bb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20211229/46c1f11f1854437b97f874415d9b5ea3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20211229/c888595fae6043a68497d0fbb460217d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20211229/8cbd05d459954e5495cde3ae714a52af.png
[20190623100301140.png_pic_center]: /images/20211229/da04a70e969349d78aa11cc2df010eb6.png
[201906231018364.png_pic_center]: /images/20211229/93eb9de51d4642f891dd76f26f9403f3.png
[20190623102017658.png_pic_center]: /images/20211229/19fc0d212dfa49a9bfc0505ce71f8761.png
[20190623103136527.png_pic_center]: /images/20211229/c3bf58a2d6c8445a90bfb460cdacc5cd.png
[https_github.com_soberqian_TopicModel4J]: https://github.com/soberqian/TopicModel4J
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20211229/b4cc6b4bea31458f9035874aadb73331.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9xaWFueWFuZy1oZnV0LmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20211229/8bcee0edcb9542b08a462c3835584efc.png