Dirichlet Process and Stick-Breaking（DP的Stick-breaking 构造）

[toc]

本文作者：合肥工业大学 管理学院 钱洋 email：1563178220@qq.com 内容可能有不到之处，欢迎交流。 
未经本人，允许禁止转载。

下面是本文博客的另一个地址，http://blog.csdn.net/qy20115549/article/details/62041632

#Dirichlet Process简介
DP是一种**非参数贝叶斯模型**, 其优点是参数的个数和性质灵活可变, 可通过模型和数据来计算数目, 近年来它已成为机器学习和自然语言处理研究领域中的一个研究热点。举个例子，**我们在使用聚类方法k-means时，需要指定k的值(聚成k个簇)；在使用LDA时需要指定主题的数目k，但通过DP过程这种非参方法，可以不指定k，而是通过数据学习，自动获取k值。**

如下所示为混合模型对等的两个图，其中图二是从随机测度的角度画的概率图。正如图中提到的问题，当k趋向于无穷大的时候，该怎么办呢？

![这里写图片描述](http://img.blog.csdn.net/20170314122200419?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXkyMDExNTU0OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

#Stick-Breaking构造

在上图中，当 $k\to\infty$时，有 $G=\sum\_{k=1}^\infty \pi\_k \delta\_{\phi\_k}$，所有的$\phi\_k$是独立的，并且从 $G\_0$抽取。随机序列$\lbrace\pi\_k\rbrace{^\infty\_{k=1}} $的总和为1。Sethuraman 证明如此构造的分布函数服从 Dirichlet 过程 $DP(\alpha\_0,G\_0)$ 分布的一个随机分布。
![这里写图片描述](http://img.blog.csdn.net/20170314123021202?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXkyMDExNTU0OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

如下公式表达为Stick-breaking 构造：
```math
\beta_k|\alpha_0,G_0 \sim Beta(1,\alpha_0)
\phi_k|\alpha_0,G_0 \sim G_0
```
则定义随机分布$G$如下：
```math
\pi_k=\beta_k \sum_{l=1}^{k-1}(1-\beta_l)
```
```math
G=\sum_{k=1}^\infty \pi_k \delta_{\phi_k}
```
其中，$Beta(1,\alpha\_0)$为常见的beta分布。$\delta\_{\phi}$为$\phi$点的概率测度。

Stick-breaking 构造可以形象地解释为:对长度为1的棒子在比例$\beta_1 $处切割, 并将**切掉的这部分长度**赋值给$\pi\_1$, 而后对剩余长度为$1-\pi\_1$ 的棒在其**比例** $\beta\_2$处切割, 并**将切掉的棒的长度**赋值给$\pi_2$,而后按照相同的方式对剩余的棒在比例 $\beta\_k$ 处切割,并将切掉的棒的长度赋值给$\pi\_k$。
<center>
![这里写图片描述](http://img.blog.csdn.net/20170314131310896?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXkyMDExNTU0OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
![这里写图片描述](http://img.blog.csdn.net/20170314131756896?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXkyMDExNTU0OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
</center>
第一次减掉的比例为：$ \beta\_1 $，则$\pi\_1=\beta_1$。此时，棒子的剩余长度为：$1-\beta\_1 $。
第二次减掉的比例为：$\beta_2 $，此时$\pi_2=\beta_2 (1-\beta_1)$。棒子的剩余长度为：$1-\beta_1-\beta_2 (1-\beta_1)=(1-\beta_1)(1-\beta_2)$。
以此类推。。。。。
<center>
![这里写图片描述](http://img.blog.csdn.net/20170314132538713?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXkyMDExNTU0OQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
</center>

参考文献：
(1)徐谦, 周俊生, 陈家骏. Dirichlet 过程及其在自然语言处理中的应用[J]. 中文信息学报, 2009, 23(5): 25-33.
(2)周建英, 王飞跃, 曾大军. 分层 Dirichlet 过程及其应用综述[J]. 自动化学报, 2011, 37(4): 389-407.
(3)Dirichlet Process and Stick-Breaking

Dirichlet Process and Stick-Breaking（DP的Stick-breaking 构造）

欢迎大家关注DataLearner官方微信，接受最新的AI技术推送

相关博客

最热博客