独立性测试与高维数据之间的关系范文

【摘要】机器直觉推理与因果模型的研究是AI基础理论体系的重要组成部分之一。针对目前因果关系推断在高维数据情况下，传统的基于条件独立性测试出现消耗时间多和准确率差等现象。本文对两种基于条件独立性测试的高维数据因果关系推断算法进行比较：一种是通过降低条件集维度的方法、另外一种是构建粗糙网络及分裂-合并策略方法，每个算法都有其优缺点。通过分析总结，在今后的工作中，可以根据实际情况选择合适的方法来解决高维数据因果关系推断问题。

【关键词】高维数据；因果关系推断；维度约简；网络分区

1研究背景及意义

1.1研究背景随着人工智能技术的在全球的迅猛发展，它的贡献将深刻影响了人类社会生活模式，把人类社会带进了“第四次工业革命”。在新的国家人工智能发展规划中，也提到了新一代强AI的基础理论体系包括“机器直觉推理与因果模型”。JudeaPearl在近期的国际会议上发表了前沿的论文“TheoreticalImpedimentstoMachineLearningWithSevenSparksfromtheCausalRevolution”，该论文提出了机器学习（ML）无法成为强AI基础，人工智能研究方向由模仿“人脑”转向“因果推理”[1]。因果推断跟传统的关联规则不一样的，关联关系只是简单地从事物的现象观察统计到事物与事物之间存在相关性，而因果关系推断则是透过事物表明，反映了事物内部的机制，而且还决定方向“谁因谁果”，因此因果关系推断真是我们要研究的科学问题以及可以为人工智能等领域提供强有力的理论基础支撑。在现实世界里，因果关系更为复杂，主要表现是：影响事物的因素众多，而且因素变量常常是高维的。例如社交网络领域、经济学领域、基因工程领域等是目前数据科学的研究热点领域，但是这些领域的特点是数据量大、数据维度高。虽然这些高维数据复杂难以处理，但是复杂的网络结构下蕴藏了丰富的事物规则，研究这方面的课题可以产生巨大的经济价值和社会价值。

1.2研究的意义（1）降低高维数据因果关系推断算法的时间复杂度，适用于更多场景；（2）提高因果关系推断算法的准确率，提升该领域的算法的可用性；（3）理论与实际相结合，为算法的顺利推广提供良好的基础。

2两种高维因果关系推断算法的比较

2.1基于条件集维度约简的因果关系推断算法在文献【】中提出了一种基于条件集维度简约的快速因果网络学习方法，通过该算法可以快速的推断出因果网络结构。其算法与传统算法快速的关键是利用mRMR算法能给找到2个节点y、x的候选马尔科夫毯节点集的并集P=PcxUPcy。分析该方法与传统PC算法的区别是：PC算法在除掉y、x的n-2个节点中关于y、x的条件独立测试集合，而基于维度简约的条件独立性测试的条件集规模比PC算法要小很多，PC算法要在n-2的节点集里面求任意组合，而维度约简方法则是在|PAxUPAy|<2m个节点求任意组合。特别是高维情况下2m<<(n-2)，基于维度约简的条件独立性测试的所表现出来的速度会比PC算法好。不过，在进行mRMR算法寻找马尔科夫毯的过程中，难免存在一些冗余变量，从而导致影响了条件独立性测试的准确率，不过总体来说还是可以接受的。条件集维度约简算法的流程如下：（1）步骤1：在n维数据集X={x1,x2,…,xn}，对其节点集任意寻找一个节点xi，设xi=y，然后对y的父子节点集初始化为PC(y)={}。（2）步骤2：求出y的一个父亲节点xi，在节点集合X\xi中，选取任意节点xj∈X\xi。（3）步骤3：利用mRMR算法，求出y和xj的得到共同候选父子节点集Sx,y。（4）步骤4：对节点集Sx,y的任意子集做条件独立测试，如果存在节点集S’，S’属于Sx,y，使得xi┴y|S，则xi与y不存在因果节点，选取X\xj,xi，循环执行步骤2~4，如果没有S’条件集可以使得xi是y能够D分离，则xi与y是因果节点，将xi加入PC(y)。（5）步骤5：重复执行步骤1~4，直到属于X的节点都找到对应的因果节点集PC(y)。（6）步骤6：通过因果节点集PC(y)，把所有的节点之间的因果关系连接起来，构成完整的因果网络图。

2.2基于低阶条件独立测试的因果关系推断算法在做基于约束的因果关系推断方法中，条件独立测试是一个关键的过程，它能够判断网络中的节点x,y之间是否独立，从而觉得是否给x,y存在边。然而，随着维度数量的增长，条件集的所有组合也呈指数级增长。目前基于低阶的条件独立测试方法的总体思想就是首先通过低阶的条件独立测试，意思就是控制条件独立测试集合的数量，保证算法执行的速度，第一阶段迅速地生成粗糙的因果网络图。第二阶段，网络通过分裂成多个子网络，再次降低大网络的维度，然后对各个子网络进行条件独立测试以求得因果网络子图。第三阶段就是通过子网络的整合方法，去掉冗余边，最终整合成完整的因果网络图。这样的算法比传统的分裂-合并方法速度更快，因为传统的分裂子网络的每个子网络都是完整边图，而我们的方法则是相对稀疏的网络图，消耗时间相对比较少。其算法LCSCD流程描述如下：（1）步骤1：在n维数据集V={v1,v2,…,vn}，构建一个完整的全连接图。（2）步骤2：通过网络分区的方法把网络V分成(V1,V2,C)。（3）步骤3：如果|V1∪C|≥δ（δ是规定变量的个数）是真的，则对|V1∪C|继续执行LCSCD算法；否则用PC算法对|V1∪C|进行因果网络学习。（4）步骤4：继续重复执行步骤4~8，保证所有的子网络都进行学习。（5）步骤5：整合所有子网络，网络边冲突进行重新识别，最终构成完整的因果网络图。

3总结

本文讨论了两种高维网络的因果关系推断算法，基于条件集维度简约的快速因果网络学习方法是通过mRMR算法对条件集进行约简，从而减少条件独立测试的次数；而基于低阶条件独立测试的因果关系推断算法是先使得条件集数量少于m个进行粗糙因果网络学习，然后在进行分裂-合并策略把大问题分解成小问题。每种算法各有利弊，在今后的工作中，将对这两种算法进行改进，争取能够把算法的时间复杂度降低同时准确率提高。

【参考文献】

［2］金洲.基于约束学习的观测数据因果关系发现研究[D].合肥：中国科学技术大学,2014.］

［5］洪英汉.一种快速因果网络骨架学习算法.南京理工大学学报(自然科学版).2016,40(3):315-321.

作者：洪英汉 夏文栋 郭才 单位：广东工业大学计算学院 韩山师范学院物理与电子工程学院