2018-11-27发表2018-11-27更新计算机 / 机器学习和人工智能17 分钟读完 (大约2595个字)

毕业论文整理（二）：用依赖树近似离散概率分布

《Approximating Discrete Probability Distributions with Dependence Trees》是一篇1968年的经典论文了，即使在2018年也有28次的引用量：

是由两位IEEE大牛C.K. CHOW和C.N.LIU所写，所以通常都被称为“Chow-Liu Tree”、“周刘树”、“CLT”，或者叫“依赖树”。整篇论文一共就6页，虽然是6页，刚开始看得真的头大，完全不知道在讲什么，更别说用了，百度一下啥都不知道，最后到外网才找到一些资料。我本科也是做这个相关的内容，当时连分类和分割的区别都不懂，也没有人讲解强行上手，真是被坑哭了。本科大四的时候每天早上起来就硬盯着一遍一遍地重复看，终于才慢慢理解。举个例子：

Abstract —— A method is presented to approximate optimally an n-dimensional discrete probability distribution by a product of second-order distributions, or the distribution of the first-order tree dependence.

什么叫做second-order distribution，翻译成英文就得花费几倍的时间从公式反推才知道这是指的“二维分布”或者叫“二阶分布”而不是在讲“第二个顺序的分布”。

CLT要解决的事情

对于很多模式识别、学习系统来说，一个很重要的事情就是根据有限的数据集来估计整体n维联合概率分布。举个例子，有两个特征（花颜色、叶子密度），采集了一些数据集：（红色、密）→ 果实好吃，（黄色，稀）→ 果实好吃……，那么我想知道当花是什么颜色、叶子是什么密度，果实会好吃，如果估计出整体的二维联合概率分布，把公式一套进去，就能知道好吃的概率多大了。根据文章《A class of nonlinear recognition procedures》我们将联合概率分布估计为：

其中，(\(m_1\), … , \(m_n\))是未知的整数1到n的排列，\(P(x_i|x_0)\)定义为\(P(x_i)\)，具备上述式子的概率分布我们称之为一阶树依赖概率分布。由集合\(\bold{x}=\{x_i|i= 1,2,…,n\}\)和映射j(i)组成的结构我们称之为这个分布的依赖树。以后都将会简写\(x_{m_i}\)为\(x_i\)。由于一共有\(\frac{n(n-1)}{2}\)个二阶近似乘积项，只有n-1个会被选择，所以如何选择出使得整体最逼近的乘积项就是CLT的核心问题。举个例子，一个联合概率分布\(P(x_1, x_2, x_3, x_4, x_5)\)可以被近似为：

现在的问题就是要求得最佳的排列m=(1,2,3,4,5)，使得整个的一阶二阶乘积估计最逼近整体联合概率分布\(P_t\)。

CLT将这个数学问题计算机化，把这个乘积式子按照如下规则转为了树：

每个变量\(x_i\)代表树的一个节点
如果有乘积项量\(P(x_a|x_b)\)，则画一条从a指向b的箭头
如果有乘积项\(P(x_c)\)，则没有从c节点出去的箭头

这样的依赖树有n-1条边，例如上述的依赖树应该画为：

寻找最优依赖树

我们设原始概率分布为\(P(\bold{x})\)，估计的概率分布为\(P_a(\bold{x})\)，\(\bold{x}\)是n维离散变量\(x_1, x_2, …, x_n\)，那么要想知道估计逼近的程度，很容易用一个距离去度量两棵树的近似程度，CLT使用了前人使用过的相对熵（Relative Entropy）的概念。相对熵，也叫KL散度（Kullback-Leibler Divergence, KLD），经常被用来描述两个分布的差异。于是\(P\)和\(P_a\)的差异可以定义为：

熵的值越小说明分布越接近，那么整个问题变为了：
给定一个n维概率分布\(P(x_1, x_2, …, x_n)\)，\(x_i\)是离散的，我们希望找到这个概率分布的依赖树\(P_\tau(x_1, x_2, …, x_n)\)使得对任意的\(t \in T_n\)，有\(I(P, P_\tau) ≤ I(P, P_t)\)。其中\(T_n\)是所有可能的依赖树，这个\(\tau\)就被成为最优依赖树。

对于n个节点来说，一共可能产生\(n^{n-2}\)棵不同的树，就不要妄想去遍历了。CLT做了两个定义。

【定义一】对于变量\(x_i\)和\(x_j\)来说，互信息\(I(x_i, x_j)\)定义为：

这是互信息的一个普遍定义，互信息值非负。然后CLT将这个互信息作为节点之间的权重赋予在每个分支上面。

【定义二】对于\(T_n\)中全部的依赖树\(t^’\)，一棵最大权值依赖树是符合如下条件的依赖树：

很容易理解这就是一个贪心，详细的证明在原论文上给出了，我也推导过一次。

用这两个定义，通过一系列的变换，熵被变换为了：

后两项是独立于依赖树的常量，因此要想使得分布越逼近，就要使得熵最小；要想使得熵最小，就要使得依赖树的权值和最大，也就是寻找一棵以互信息为权值、变量为节点的最大生成树作为依赖树。这就可以借鉴像Kruskal之类的最小生成树的算法了。

依赖树寻找实例

考虑如下二值四维联合概率分布：

\(x_1 x_2 x_3 x_4\)	\(P(x_1,x_2,x_3,x_4)\)	\(P(x_1)P(x_2)P(x_3)P(x_4)\)
0000	0.100	0.046
0001	0.100	0.046
0010	0.050	0.056
0011	0.050	0.056
0100	0.000	0.056
0101	0.000	0.056
0110	0.100	0.068
0111	0.050	0.068
1000	0.050	0.056
1001	0.100	0.056
1010	0.000	0.068
1011	0.000	0.068
1100	0.050	0.068
1101	0.050	0.068
1110	0.150	0.083
1111	0.150	0.083

例如第1行的含义是，\(P(x_1=0,x_2=0,x_3=0,x_4=0)\)=0.100。我们通过累加来求得一阶和二阶边缘概率分布，例如\(P(x_1=0)=P(x_1=0,x_2,x_3,x_4)\)：

0	1	00	01	10	11
\(P(x_1)\)	0.450	0.550	-	-	-
\(P(x_2)\)	0.450	0.550	-	-	-
\(P(x_1, x_2)\)	-	-	0.300	0.150	0.150

然后根据互信息公式计算互信息，例如：

于是得到了：

互信息	值
\(I(x_1,x_2)\)	0.079
\(I(x_1,x_3)\)	0.00005
\(I(x_1,x_4)\)	0.0051
\(I(x_2,x_3)\)	0.189
\(I(x_2,x_4)\)	0.0051
\(I(x_3,x_4)\)	0.0051

我们只需要选择4-1=3条边，就能把4个节点连起来了，按照从大到小排序（\(x_2 \rightarrow x_1\)）、（\(x_3 \rightarrow x_2\)）必选，剩余三条边都是相同的权值，会按照一些排序算法随机地选择剩余的3条中的一条，生成的依赖树如图（实现代表真实选择，虚线代表可能替换选择，灰色代表不选择）：

于是整体分布可能被估计为：\(P(x_1,x_2,x_3,x_4)=P(x_1)P(x_2|x_1)P(x_3|x_2)P(x_4|x_1)\)，我们可以去计算它的概率分布值，例如：

得到如下三种方案的对比表：

\(x_1 x_2 x_3 x_4\)	\(P(x_1,x_2,x_3,x_4)\)	\(P(x_4\|x_1)\)	\(P(x_4\|x_2)\)	\(P(x_4\|x_3)\)
0000	0.100	0.130	0.104	0.104
0001	0.100	0.104	0.130	0.130
0010	0.050	0.037	0.030	0.037
0011	0.050	0.030	0.037	0.030
0100	0.000	0.015	0.015	0.012
0101	0.000	0.012	0.012	0.015
0110	0.100	0.068	0.068	0.068
0111	0.050	0.054	0.055	0.055
1000	0.050	0.053	0.052	0.052
1001	0.100	0.064	0.065	0.065
1010	0.000	0.015	0.015	0.018
1011	0.000	0.018	0.019	0.015
1100	0.050	0.033	0.040	0.032
1101	0.050	0.040	0.032	0.040
1110	0.150	0.149	0.182	0.182
1111	0.150	0.178	0.146	0.146