职称论文代写范文：基于互信息的适用高维数据

0 引言

因果网络是一种对可观测数据进行强有力推理的工具，可以方便地表示和分析确定性和概率性的事物.在因果推断的问题中，通常是先对数据集进行无向图的构建，然后再对边的方向进行推断. 然而对于高维数据，暂时还没有快速有效的因果推断方法. 目前的因果推断方法可以被分为两大类：基于估计马尔可夫等价类[1]的贝叶斯网络结构学习算法[2-4]和基于加噪声模型的因果推断算法[5-7]. 其中，贝叶斯网络结构学习算法主要有两种方法. 第一种是基于依赖分析的结构学习方法，第二种是基于打分-搜索的结构学习方法.然而,这两种方法都无法识别一个因果网络中存在的马尔可夫等价类，因此，这类方法尽管能构造无向图，但没办法区对边的方向进行准确的判断.另一方面，由于这类方法在对网络做结构推断时采取一种搜索网络中所有可能存在结构的策略，这种结构的可能存在个数会随着数据集中的变量个数呈指数增长[8]，时间复杂度太高，所以往往只适用于低维网络. 不同于因果马尔可夫假设，Shimizu 等人提出了一种基于线性加噪声模型的算法LINGAM[5]，该算法可以有效地从数据集中的构建出具体的因果网络图. 然而 LINGAM 只适用于线性加噪声模型，无法解决非线性问题. 在非线性方面，Hoyer 等人提出了一种基于非线性加噪声模型的适用于连续型数据的算法ANM[6]. Peters 等人对 ANM 算法进行了深一步的推广，使之适用于离散型数据[7]. 然而，这两种非线性加噪声模型算法都只适用较低维的数据集，一旦数据集的维度较大( n   7)，算法准确率就会降到很低. 近来，Janzing 等人提出了一种基于信息熵的因果推断算法 IGCI[9]，相对于 ANM 算法，IGCI 算法能很好地控制判断率,并且在判断率高的时候其对无向图边的方向推断的准确率要高于其余的因果推断算法. 但类似地，IGCI 仅仅能适用于低维数据，一旦维数超过 2，方法就失效. 所以，这些因果推断方法都不适用于高维数据.

1 预备知识

尽管目前两类方法都不适用于高维数据的因果推断，但可以观察到这两类方法各自的优点：1)贝叶斯网络结构学习算法能够对高维数据进行无向图的构建，却无法识别马尔可夫等价类；2)加噪声模型可以对马尔可夫进行辨别，却无法处理高维数据. 基于此，提出了一种基于互信息的并且可以适用于高维数据的因果推断算法. 该算法将高维网络结构学习问题分解成该网络中每一个节点对应的低维因果网络结构学习问题. 首先利用贝叶斯网络结构学习算法，根据条件互信息来测试数据间的依赖关系构造出每一个低维因果网络对应的无向图. 然后再结合 ANM 和 IGCI 算法，对低维因果网中目标节点与其每一个父子节点之间的无向边进行方向识别，得到目标节点对应的有向无环图. 数据集中的所有变量都迭代完后得到数据集的一个完整因果网络图. 对高维的因果网络结构学习问题采取先分解再组合的策略不仅降低了计算复杂度，而且提高了推断的准确性.仿真数值实验和在应用在真实网络模型的实验结果表明，该算法在高维数据下，该算法的精确度要高于其他因果推断算法.

2 条件互信息与因果推断

对于连续型数据条件互信息的估计，一般的方法是先对连续型数据做等值区间离散化处理. 这样的预处理后，数据本来所蕴含的信息会丢失一部分. 另外这些方法对控制间隔距离的参数依赖过大，而且对样本量需求也比较大. 当样本量没有足够大，又或者在计算条件互信息时候，其条件集的维数较高，那这类方法往往会不可靠. 算法主要分为两部分. 如图 1 所示，算法将高维网络结构学习问题分解成该网络中每一个节点对应的低维因果网络结构学习问题.首先，算法的第一阶段主要是利用条件互信息测试找出每一个目标节点的父子节点集，也就是一个以目标节点为中心的无向图(图 1 左). 算法的第二阶段在已找出目标节点父子节点集的情况下，结合 ANM 和 IGCI 算法对目标节点和每一个父子节点进行方向判别，得到一个目标节点与其父子节点间的具体因果关系(图 1 右). 然后将该节点与其父子节点的因果结构更新到整个数据集的因果网络，直到每个节点的和其的父子节点集 PC(y)的因果图都被更新完. 最后得到一个完整的，表现出数据间因果关系的因果网络图.

3 因果推断算法

由于传统的方向判别方法的种种局限性，对于高维网络无法进行有效推断，而 ANM 和 IGCI 算法可以区分马尔可夫等价类. 尽管如此，这两类方法都无法应用在高维数据上. 文献[9]中的实验结果表明，在判断率低于约65%时候，ANM 准确率高于 IGCI，反之 IGCI 占优. 然而在高维数据上，由于 ANM 的判断率很难由阈值控制，其判断率往往比较低. 相反地，IGCI 的判断率可以简单地通过设定适当的阈值进行控制. 基于此，提出一个结合 ANM 和 IGCI 的判断方法. 首先，采用 ANM 算法对每个目标结合和其父子节点集间的边的方向进行判定，如果无法做出判断，则采用 IGCI进行补判，使得判断率达到 100%. 虽然 ANM 和 IGCI 算法没办法解决较高维的因果网络结构学习问题，但由于在算法第一步已经得到了目标节点 y 的父子节点集合 PC(y)，然后利用 ANM 和 IGCI 对 PC(y)中的每一个变量和 y 间进行方向判别，这等同于在 2 维网络中应用 ANM 和 IGCI 算法，从而保证了算法的有效性.本文提出的算法被记为 Two Phase Casualinference (TPCI).

4 结语

与传统的对数据进行整体结构学习的因果推断算法不同，本文结合了传统的贝叶斯网络结构学习算法和加噪声模型，将高维网络中每一个节点的因果网络作为结构学习的单位，使得推断方法不局限于低维数据.该算法通过采取先降维再整合的策略提高了执行效率，同时保证了结果的准确度.文中采用虚拟网络和真实网络进行实验，实验结果表明在数据集维数较高时候，该算法要大大优于其他因果推断算法.