文章目录

依赖树论文背景

前言

《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,翻译成英文就得花费几倍的时间从公式反推才知道这是指的“二维分布”或者叫“二阶分布”而不是在讲“第二个顺序的分布”:

可是为什么要同时用两种表达n-dimensional和second-order还是没去深究,说不定会有概念的细微差异,不过能用就行。另外等看明白之后,发现这篇文章其实现现在通常都被用作找寻依赖关系,比如用于特征选择,或者单词之间的关联程度,根本不适合于现代图像分割,然而老板的要求必须要做啊,不行也得行。

CLT要解决的事情

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

其中,(m1, ... , mn)是未知的整数1到n的排列,P(xi | x0)定义为P(xi),具备上述式子的概率分布我们称之为一阶树依赖概率分布。由集合x={xi | i = 1,2,...,n}和映射j(i)组成的结构我们称之为这个分布的依赖树以后都将会简写x_mi为xi。由于一共有n(n-1)/2个二阶近似乘积项,只有n-1个会被选择,所以如何选择出使得整体最逼近的乘积项就是CLT的核心问题。举个例子,一个联合概率分布P(x1,x2,x3,x4,x5)可以被近似为:

现在的问题就是要求得最佳的排列m=(1,2,3,4,5),使得整个的一阶二阶乘积估计最逼近整体联合概率分布Pt。CLT将这个数学问题计算机化,把这个乘积式子按照如下规则转为了树:

1) 每个变量xi代表树的一个节点

2) 如果有乘积项P(xa|xb),则画一条从a指向b的箭头

3) 如果有乘积项P(xc),则没有从c节点出去的箭头

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

寻找最优依赖树

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

熵的值越小说明分布越接近,那么整个问题变为了:

给定一个n维概率分布P(x1,x2,...,xn),xi是离散的,我们希望找到这个概率分布的依赖树Pτ(x1,x2,...,xn)使得对任意的t∈Tn, I(P,Pτ) ≤ I(P,Pt)。其中Tn是所有可能的依赖树,这个τ就被成为最优依赖树。

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

【定义一】对于变量xi和xj来说,互信息I(xi, xj)定义为:

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

【定义二】对于Tn中全部的依赖树t',一棵最大权值依赖树是符合如下条件的依赖树:

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

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

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

依赖树寻找实例

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

x1 x2 x3 x4 P(x1,x2,x3,x4) p(x1)p(x2)p(x3)p(x4) 
 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

表的含义是,当P(x1=0, x2=0, x3=0, x4=0) = 0.100。我们通过累加来求得一阶和二阶边缘概率分布,例如P(x1=0) = P(x1=0, x2,x3,x4):

 00 01 10 11 
P(x1)0.450 0.550  - - - -
P(x2)0.4500.550 - - - -
P(x1, x2) -0.3000.150 0.150 0.400 

然后根据互信息公式计算互信息,例如:

于是得到了:

互信息 值 
 I(x1, x2)0.079 
 I(x1, x3)0.00005
 I(x1, x4) 0.0051 
 I(x2, x3) 0.189
 I(x2, x4) 0.0051 
 I(x3, x4) 0.0051

我们只需要选择4-1=3条边,就能把4个节点连起来了,按照从大到小排序(x2→x1)、(x3→x2)必选,剩余三条边都是相同的权值,会按照一些排序算法随机地选择剩余的3条中的一条,生成的依赖树如图:

实现代表真实选择,虚线代表可能替换选择,灰色代表不选择。  

于是整体分布可能被估计为:P(x1, x2, x3, x4) = P(x1)P(x2|x1)P(x3|x2)P(x4|x1),我们可以去计算它的概率分布值,例如:

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

x1x2x3x4 P(x1,x2,x3,x4) x4|x1 x4|x2 x4|x3 
 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

三种方案的熵都是0.094,几乎接近于0,已经非常近似了。

边缘概率分布的近似

上面的例子先给出联合概率分布,再去求的边缘概率。实际中我们本来要求的就是联合概率分布,所以只能利用样本去近似边缘概率。很容易想到计数的方法:

n_uv是xi=u,xj=v的样本简单计数,就能够得到互信息的估计了,由于熵公式只是对互信息线性求和,所以直接用这个估计替代互信息即是熵的估计了。

在实际操作中还会遇到问题,那就是样本量为0的时候会发生除以0的情况,这时候需要预处理样本,所有取值样本数+1,这样不会影响整体分布,又避免了除以0的问题。我在另外的算法里看见过这种处理,因此沿用了过来。

模式识别实例

我们采集了19000张手写数字0-9图片,将其图像数据二值化,希望通过计算机模式识别输入图像输出数字到底是几:

一共有c=10个类别,假设用ai标记第i个类别,p=(p1,...,pc)表示先验概率分布,先验概率可以通过计数简单地进行估计;对于输入的二值特征向量x=(x1,x2...,xn),如果一个样本的特征向量符合:

那么就判别这个样本为第k个类别。问题的关键转变为求条件概率P(x|ai)的分布。按照字面理解,就是在0-9的数字出现的条件下, 特征向量x出现的概率有多大。于是我们的问题可以化为求解:

也就是求在给定ai类别下,特征向量取值的联合概率分布函数,这个分布函数就用CLT来求解,最后的数字“4”的CLT图像是这样的:

整个流程就走通了。

NAFs如何结合CLT

说实话,无法结合……CLT需要离散的特征,标题都已经明确说discrete了,而图像数据通常是不连续的,要想利用CLT,就必须要离散化特征值,离散化特征值,就必然丢失特征精度,得到的效果就变差。所以为了交差,只能将其作为“粗分割”,也就是先用CLT进行一次“粗分割”,确定大致边界,再利用NAFs去精细分割。


转载请注明出处http://www.bewindoweb.com/232.html | 三颗豆子
分享许可方式知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
重大发现:转载注明原文网址的同学刚买了彩票就中奖,刚写完代码就跑通,刚转身就遇到了真爱。
你可能还会喜欢
具体问题具体杠
  • Sun
    评论于2019年07月25日
    楼主GitHub怎么找到你啊
    三颗豆子
    回复于2019年07月25日
    最下面的链接呀~https://github.com/BEWINDOWEB
  • JWSun
    评论于2019年06月25日
    楼主写的太好了,各个点都涉及到了。
    三颗豆子
    回复于2019年06月25日
    谢谢,我还一直想把代码整理出来,一直没有时间……等有空了可以整理,请多关注博客和github。
  • Jonathan Hu
    评论于2019年02月22日
    同学,我是搞机器学习的工程师,你也玩qq三国吗?咱以后可以一起做一下数据挖掘的竞赛呀
    三颗豆子
    回复于2019年02月23日
    谢谢邀请,我也很想不过最近比较忙,等这段时间过了可以一起做~