一种基于高阶累积量的因果结构学习算法

从观测数据中学习因果结构具有重要的应用价值。目前,一类学习因果结构的方法是基于函数因果模型假设,通过检验噪声与原因变量的独立性来学习因果结构。然而,该类方法涉及高计算复杂度的独立性检验过程,影响结构学习算法的实用性和鲁棒性。为此,提出了一种在线性非高斯模型下,利用高阶累积量作为独立性评估的因果结构学习算法。该算法主要分为两个步骤,第一个步骤是利用基于条件独立性约束的方法学习到因果结构的马尔可夫等价类,第二个步骤是定义了一种基于高阶累积量的得分,该得分可以判别两个随机变量的独立性,从而可以从马尔可夫等价类中搜索到最佳独立性得分的因果结构作为算法的输出。该算法的优势在于：a)相比基于核方法的独立性检验,该方法有较低的计算复杂度;b)基于得分搜索的方法,可以得到一个最匹配数据生成过程的模型,提高学习方法的鲁棒性。实验结果表明,基于高阶累积量的因果结构学习方法在合成数据中F₁得分提高了5%,并在真实数据中学习到更多的因果方向。     

基于级联加性噪声模型的因果结构学习算法

现有级联非线性加性噪声模型可解决隐藏中间变量的因果方向推断问题,然而对于包含隐变量和级联传递因果关系的因果网络学习存在全局结构搜索、等价类无法识别等问题。设计一种面向非时序观测数据的两阶段因果结构学习算法,第一阶段根据观测数据变量间的条件独立性,构建基本的因果网络骨架,第二阶段基于级联非线性加性噪声模型,通过比较骨架中每个相邻因果对在不同因果方向假设下的边缘似然度进行因果方向推断。实验结果表明,该算法在虚拟因果结构数据集的不同隐变量数量、平均入度、结构维度、样本数量下均表现突出,且在真实因果结构数据集中的F1值相比主流因果结构学习算法平均提升了51%,具有更高的准确率和更强的鲁棒性。     

基于递归分解的因果结构学习算法

在高维小样本场景下，针对现有基于约束的因果结构学习方法存在因果结构学习效率低、马尔可夫等价类的问题，以非线性非高斯的高维小样本为研究对象，提出一种基于递归分解的因果结构学习算法CADR。在高维小样本的因果结构学习效率方面，结合递归分解的思想，将高维变量集递归分解为多个更小的子集，直到无法再分解或子集的大小达到阈值为止。在该过程中，变量集的减少缩减了条件独立性检验的条件候选集的搜索空间，从而提高学习效率。同时，为进一步识别马尔可夫等价类，根据非线性非高斯模型的因果方向的不可逆性，通过判断拟合噪声项与原因变量是否独立来识别马尔可夫等价类的因果方向。在仿真数据和真实因果结构数据上的实验结果表明，CADR不仅提高条件独立性检验的效率，而且能有效地区分马尔可夫等价类，学习到更精确的因果结构，其中，在真实因果结构实验中，与现有Xie＿rec、PC＿ANM和Notear＿Sob方法相比，F1评分提高5%～12%。     

局部因果关系分析的隐变量发现算法

结构分析的隐变量发现方法难以有效地发现隐变量且可解释性较差。基于因果关系和局部结构的不确定性,提出了一种基于局部因果关系分析的隐变量发现算法（hidden variable discovering algorithm based on local causality analysis,LCAHD）。LCAHD算法给出了因果结构熵的定义,将因果知识和不确定性知识相融合,以因果关系的不确定性程度作为隐变量存在的判定依据,并对这一依据进行了理论上的论证。LCAHD算法首先通过寻找目标变量的马尔科夫毯来提取局部依赖结构,并基于扰动学习获得扰动数据,联合扰动数据和观测数据学习局部依赖结构中的因果关系;然后利用因果结构熵对局部因果结构中因果关系的不确定性进行度量,并利用隐变量和因果关系不确定性之间的相关性判定条件,确定隐变量的存在性。分别针对标准网络和股票网络进行了实验,结果表明,该算法能准确地确定隐变量的位置,具有较好的解释性。     

基于条件独立性的LiNGAM模型剪枝算法

如何根据观察数据来推断因果网络结构是统计学和机器学习领域的重要问题。近年来学者们取得了许多研究成果,Li NGAM算法是其中一种经典的线性因果推断算法。但Li NGAM算法采用的剪枝策略时间复杂度较高,且在稀疏图上准确率低。为此,提出一种基于条件独立性测试的剪枝算法来解决这个问题。该算法首先将变量根据因果顺序重新排列,再按照该次序采用偏相关系数检验变量之间的条件独立性。大量的实验结果表明,基于条件独立性的剪枝算法在稀疏图上比Li NGAM的剪枝算法获得更高的准确率与执行效率。     

基于因果自回归流模型的因果结构学习算法

因果自回归流模型已经在非独立噪声等场景的因果方向推断问题上取得了一定的进展,但在多个结点的场景下仍存在全局结构搜索带来的准确度低和计算时间复杂度高的问题。面向非时序观察数据设计一种两阶段因果结构学习算法。在第一阶段,基于观测数据的条件独立性,对完全无向图通过条件独立性检验得到基本的因果骨架;在第二阶段,基于因果自回归流模型,通过标准化流的方法计算骨架中每条无向边在不同方向上的边缘似然概率,进而通过比较边缘似然概率进行因果方向推断。实验结果表明：该算法在多组不同参数生成的仿真因果结构数据集上均有较好的表现,与现有的主流因果结构学习算法相比,F1值平均提升15%～28%;在真实因果结构数据集实验中,该算法能够较为完整准确地学习到变量间的因果关系,与主流的因果结构学习算法相比,F1值平均提升28%～48%,具有更强的鲁棒性。     

一种基于因果强度的局部因果结构主动学习方法

因果结构学习是贝叶斯网络学习中一种重要的结构学习方法,因果关系揭示了系统要素作用的本质。由于 仅利用观测数据很难准确地发现变量间的因果关系,且通常人们仅关心网络中关于某一变量的局部因果关系,因此针 对难以从观测数据中仅获取所感兴趣的变量的局部因果结构的问题,提出了一种局部结构学习方法,即一种基于因果 强度的局部因果结构主动学习方法(CSI-I_CS工力。CSI一工CSI方法融合了马尔可夫毯的结构划分能力和扰动学习的因 果发现能力,并且引入了因果强度进行扰动结点的选择。利用HITON MI3算法寻找目标结点的马尔可夫毯,生成关 于目标结点的局部模型;然后,利用不对称信息墒对局部模型中的每一结点进行因果强度分析,选取因果强度值较大 的结点进行扰动,生成扰动数据;进而,联合扰动数据和观测数据利用准确方法(exact method)学习边的后验概率,从 而获得一个关于目标结点的局部因果网络。利用结构信息嫡对CSI-LCSL方法的学习结果进行评估。在标准网络上 的实验结果证实了CSI一LCSI、算法的有效性。     

一种任意分布下的隐变量因果结构学习算法

因果发现旨在通过观测数据挖掘变量间的因果关系,在实际应用中需要从观测数据中学习隐变量间的因果结构。现有方法主要利用观测变量间的协方差信息（如四分体约束）或引入非高斯假设（如三分体约束）来解决线性因果模型下的隐变量结构学习问题,但大多限定于分布明确的情况,而实际应用环境往往并不满足这种假设。给出任意分布下隐变量结构的识别性证明,指出在没有混淆因子影响的情况下,两个隐变量的因果方向可识别所需要的最小条件是仅需要其中一个隐变量的噪声服从非高斯分布。在此基础上,针对线性隐变量模型提出一种在任意分布下学习隐变量因果结构的算法,先利用四分体约束方法学习得到隐变量骨架图,再通过枚举骨架图的等价类并测量每一个等价类中的三分体约束来学习因果方向,同时将非高斯约束放宽到尽可能最小的变量子集,从而扩展线性隐变量模型的应用范围。实验结果表明,与MIMBuild和三分体约束方法相比,该算法得到了最佳的F1值,能够在任意分布下学习更多的隐变量因果结构信息,且具有更强的鲁棒性。     

非线性因果模型辨识方法

近来,基于观测变量的因果模型辨识受到了较多关注。一般使用线性无环因果模型对数据生成过程建模,而实际上,许多因果模型包含非线性关系,使用纯线性方法求解是无效的。将线性模型泛化为非线性模型,提出一种两步骤的辨识算法,首先使用特征选择算法获得d分离等价类,然后使用非线性成对独立性测试为图中的边标注因果方向。实验结果验证了该算法的有效性,并表明其优于其他算法。     

基于因果影响独立模型的贝叶斯网络参数学习

基于因果影响独立模型及其中形成的特定上下文独立关系,提出一种适于样本学习的贝叶斯网络参数学习算法。该算法在对局部概率模型降维分解的基础上,通过单父节点条件下的子节点概率分布来合成局部结构的条件概率分布,参数定义复杂度较低且能较好地处理稀疏结构样本集。实验结果表明,该算法与标准最大似然估计算法相比,能充分利用样本信息,具有较好的学习精度。     

A hybrid algorithm for Bayesian network structure learning with application to multi-label learning

We present a novel hybrid algorithm for Bayesian network structure learning, called H2PC. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. The algorithm is based on divide-and-conquer constraint-based subroutines to learn the local structure around a target variable. We conduct two series of experimental comparisons of H2PC against Max–Min Hill-Climbing (MMHC), which is currently the most powerful state-of-the-art algorithm for Bayesian network structure learning. First, we use eight well-known Bayesian network benchmarks with various data sizes to assess the quality of the learned structure returned by the algorithms. Our extensive experiments show that H2PC outperforms MMHC in terms of goodness of fit to new data and quality of the network structure with respect to the true dependence structure of the data. Second, we investigate H2PC’s ability to solve the multi-label learning problem. We provide theoretical results to characterize and identify graphically the so-called minimal label powersets that appear as irreducible factors in the joint distribution under the faithfulness condition. The multi-label learning problem is then decomposed into a series of multi-class classification problems, where each multi-class variable encodes a label powerset. H2PC is shown to compare favorably to MMHC in terms of global classification accuracy over ten multi-label data sets covering different application domains. Overall, our experiments support the conclusions that local structural learning with H2PC in the form of local neighborhood induction is a theoretically well-motivated and empirically effective learning framework that is well suited to multi-label learning. The source code (in R) of H2PC as well as all data sets used for the empirical tests are publicly available.     

基于双尺度约束模型的BN结构自适应学习算法

在无先验信息的情况下, 贝叶斯网络(Bayesian network, BN)结构搜索空间的规模随节点数目增加呈指数级增长, 造成BN结构学习难度急剧增加. 针对该问题, 提出基于双尺度约束模型的BN结构自适应学习算法. 该算法利用最大互信息和条件独立性测试构建大尺度约束模型, 完成BN结构搜索空间的初始化. 在此基础上设计改进遗传算法, 在结构迭代优化过程中引入小尺度约束模型, 实现结构搜索空间小尺度动态缩放. 同时, 在改进遗传算法中构建变异概率自适应调节函数, 以降低结构学习过程陷入局部最优解的概率. 仿真结果表明, 提出的基于双尺度约束模型的BN结构自适应学习算法能够在无先验信息的情况下保证BN结构学习的精度和迭代寻优的收敛速度.     

LEARNING STRUCTURED BAYESIAN NETWORKS: COMBINING ABSTRACTION HIERARCHIES AND TREE-STRUCTURED CONDITIONAL PROBABILITY TABLES

Context-specific independence representations, such as tree-structured conditional probability distributions, capture local independence relationships among the random variables in a Bayesian network (BN). Local independence relationships among the random variables can also be captured by using attribute-value hierarchies to find an appropriate abstraction level for the values used to describe the conditional probability distributions. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. In this paper, we introduce Tree-Abstraction-Based Search (TABS), an approach for learning a data distribution by inducing the graph structure and parameters of a BN from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. To construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. We present empirical results for three real-world domains, finding that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.     

Learning Causal Bayesian Networks Using Minimum Free Energy Principle

Constraint-based search methods, which are a major approach to learning Bayesian networks, are expected to be effective in causal discovery tasks. However, such methods often suffer from impracticality of classical hypothesis testing for conditional independence when the sample size is insufficiently large. We present a new conditional independence (CI) testing method that is designed to be effective for small samples. Our method uses the minimum free energy principle, which originates from thermodynamics, with the “Data Temperature” assumption recently proposed by us. This CI method incorporates the maximum entropy principle and converges to classical hypothesis tests in asymptotic regions. In our experiments using repository datasets (Alarm/Insurance/Hailfinder/Barley/Mildew), the results show that our method improves the learning performance of the well known PC algorithm in the view of edge-reversed errors in addition to extra/missing errors.     

一种基于CDC的适用于高维数据的因果推断算法

一对观测变量之间的因果关系的推断是科学中的基本问题,基于观测数据分析提出因果关系的方法对于产生假设和加速科学发现具有实用价值。利用传统的因果推断算法从高维数据中学习因果网络结构和提高学习准确率是目前研究的难点。在引入耦合相关系数(copula dependence coefficient,CDC)的基础上,提出了一种适用于高维数据的两步骤因果推断算法。首先该算法利用优于最大信息系数的CDC对变量间的关联度进行检测,寻找目标节点的父子节点集;然后使用非线性最小二乘独立回归算法,为图中的目标节点与其父子节点之间标注因果方向;最后迭代所有的节点完成完整的因果网络结构。实验结果表明,该算法提高了高维数据下因果网络结构学习的准确率。同时在大样本数据集中,该算法的时间复杂度优于传统算法,对异常值具有鲁棒性。     

基于神经网络的混合数据的因果发现

因果推理正在成为机器学习领域一个越来越受关注的研究热点,现阶段的因果发现主要是在研究某一种假设条件下,基于纯粹的观测数据推断变量之间的因果方向。然而在现实世界中观察到的数据往往是由一些假设生成,使得传统因果推断方法的识别率不高、稳定性较差。针对当前的问题,提出了一种基于神经网络来解决混合数据因果推断的方法。该方法在混合加性噪声模型(ANM-MM)的假设下,使用梯度下降法最优化改进的损失函数得到混合数据的抽象因果分布参数,然后将分布参数看作是原因变量和结果变量之间的隐变量,通过比较原因变量和分布参数之间的HilberSchmidt独立性来确定二元变量的因果方向。在理论上证明了该方法的可行性,并通过实验表明该算法在人工数据和真实数据的表现较传统的IGCI,ANM,PNL,LiNGAM,SLOPE方法具有较好的准确率和稳定性。     

基于均匀局部搜索和可变步长的萤火虫算法

针对萤火虫算法（FA）收敛速度慢和求解精度不高的问题,提出一种基于均匀局部搜索和可变步长策略的萤火虫优化算法（UVFA）。首先,根据均匀设计理论建立局部搜索算子,对FA的搜索过程进行改进,以提升算法的局部开采能力和收敛速度;其次,利用可变步长策略,动态地调整算法搜索步长,以平衡全局和局部的勘探能力和开采能力;最后将均匀局部搜索算子和可变步长进行融合。通过对12个标准测试函数进行仿真实验,结果表明,UVFA的目标函数均值均明显优于FA、明智步长策略的萤火虫算法（WSSFA）、可变步长萤火虫算法（VSSFA）和基于均匀局部搜索的萤火虫优化算法（UFA）,并且时间复杂度明显降低,并且在低维和高维问题中均显示出了较好的质量,具有良好的鲁棒性。